• 数据结构之单链表代码总结

    今天，我带来单链表的讲解。

    目录

    顺序表的缺陷

    在前面的文章中，我已经写过顺序表的代码。顺序表本身存在着缺陷，如:

    1.空间不够，需要扩容(尤其异地扩容)是有一定的代价的，其次，还可能存在一定的空间浪费(没有完全利用空间)。
    2.头部或者中部插入或者删除数据，需要挪动数据，效率低下。

    优化方案:

    1.按需申请释放空间
    2.不要挪动数据

    链表就是这样的一种存在。

    单链表的三个文档

    SList.h--------头文件的引用和函数的声明
    SList.c--------函数的定义
    test.c--------单链表的检验

    创建结点函数

    //创建结点
SLTNode* BuySLTNode(SListDataType x)
{
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL)
	{
		perror("BuySLTNode()");
		exit(1);
	}
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    按元素从小到大的顺序创建链表

    //创建链表
SLTNode* CreatSList(int n)
{
	SLTNode* Phead = NULL, * Ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* NewNode = BuySLTNode(i);

		if (NewNode == NULL)
		{
			perror("CreatSList()");
			exit(1);
		}

		if (Phead == NULL)
		{
			Phead = Ptail = NewNode;
		}
		else
		{
			Ptail->next = NewNode;
			Ptail = NewNode;
		}
	}
	return Phead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    打印链表

    //打印链表
void SLTPrint(SLTNode* Phead)
{
	SLTNode* cur = Phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    尾插函数

    //尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	if (NewNode == NULL)
	{
		perror("SLTPushBack()");
		exit(1);
	}

	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		SLTNode* cur = *PPhead;
		//找尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = NewNode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    尾删函数

    //尾删函数
void SLTPopBack(SLTNode** PPhead)
{
	assert(PPhead != NULL);

	if ((*PPhead)->next == NULL)
	{
		free(*PPhead);
		*PPhead = NULL;
	}
	else
	{
		SLTNode* cur = *PPhead;
		//找尾
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    头插函数

    //头插函数
void SLTPushFront(SLTNode** PPhead, SListDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = *PPhead;
	*PPhead = NewNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    头删函数

    //头删函数
void SLTPopFront(SLTNode** PPhead)
{
	assert(PPhead != NULL);
	SLTNode* next = (*PPhead)->next;
	free(*PPhead);
	*PPhead = next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在pos位置后面插入数据的函数

    //在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos,SListDataType x)
{
	assert(pos != NULL);
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = pos->next;
	pos->next = NewNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在pos位置插入数据的函数

    //在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x)
{
	assert(pos != NULL);
	if ((*PPhead) == pos)
	{
		SLTPushFront(PPhead,x);
	}
	else
	{
		SLTNode* cur = *PPhead;
		SLTNode* NewNode = BuySLTNode(x);
		//找到pos前的位置
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		NewNode->next = pos;
		cur->next = NewNode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    删除pos位置后面的数据的函数

    //删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos != NULL);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* NextNode = pos->next;
		pos->next = NextNode->next;
		free(NextNode);
		NextNode = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    删除pos位置数据的函数

    //删除pos位置的数据
void SLTErase(SLTNode** PPhead,SLTNode* pos)
{
	assert(*PPhead != NULL);
	assert(pos != NULL);

	if (pos == *PPhead)
	{
		SLTPopFront(PPhead);
	}
	else
	{
		SLTNode* cur = *PPhead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    销毁链表的函数

    //销毁链表
void SLTDestroy(SLTNode** PPhead)
{
	SLTNode* cur = *PPhead;
	while (cur != NULL)
	{
		SLTNode* NextNode = cur->next;
		free(cur);
		cur = NextNode;
	}
	*PPhead = NULL;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    查找数据的函数

    //查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x)
{
	SLTNode* cur = Phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    删除相应元素的所有结点

    //删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead, SListDataType x)
{
	SLTNode* cur = Phead;
	SLTNode* NewHead = NULL, *Ptail = NULL;
	while (cur)
	{
		//分别判断不是相应结点    判断不是最后一个结点  判断是倒数第二个结点      判断最后一个是相应结点
		if (cur->data != x && cur->next != NULL && cur->next->next == NULL && cur->next->data == x)
		{
			free(cur->next);    //释放最后一个结点
			cur->next = NULL;    
			Ptail->next = cur;  //倒数第二个结点地址传过去
			cur = cur->next;
		}
		else if (cur->data != x)
		{
			if (Ptail == NULL)
			{
				NewHead = Ptail = cur;
			}
			else
			{
				Ptail->next = cur;
				Ptail = Ptail->next;
			}
			cur = cur->next;
		}
		else if(cur->data == x)       
		{
			SLTNode* NextNode = cur->next;
			free(cur);
			cur = NextNode;
		}
	}
	return NewHead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    利用数组创建结点的函数

    //使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n)
{
	SLTNode* Phead = NULL, * Ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* NewHead = BuySLTNode(arr[i]);
		if (Ptail == NULL)
		{
			Phead = Ptail = NewHead;
		}
		else
		{
			Ptail->next = NewHead;
			Ptail = Ptail->next;
		}
	}
	return Phead;
}

#define MAX 100

//输入数组的元素
SListDataType* CreatArr()
{
	int N = 0;
	printf("请输入数组元素个数:>");
	scanf("%d", &N);
	SListDataType arr[MAX];
	printf("请依次输入数组的元素，按空格隔开\n");
	for (int i = 0; i < N; i++)
	{
		scanf("%d",&arr[i]);
	}
	return CreatSLTByArr(arr,N);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    结构体的定义和函数的声明

    typedef int SListDataType;
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SLTNode;

//创建结点
SLTNode* BuySLTNode(SListDataType x);

//创建链表
SLTNode* CreatSList(int n);

//打印链表
void SLTPrint(SLTNode* Phead);

//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x);

//尾删函数
void SLTPopBack(SLTNode** PPhead);

//头插函数
void SLTPushFront(SLTNode** PPhead,SListDataType x);

//头删函数
void SLTPopFront(SLTNode** PPhead);

//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos, SListDataType x);

//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x);

//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos);

//删除pos位置的数据
void SLTErase(SLTNode** PPhead, SLTNode* pos);

//销毁链表
void SLTDestroy(SLTNode** PPhead);

//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x);

//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead,SListDataType x);

//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n);

//输入数组的元素
SListDataType* CreatArr();

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    菜单和主函数

    void menu()
{
	printf("***********************************************************************************\n");
	printf("******      1.创建连续的链表                     2.通过数组元素创建链表      ******\n");
	printf("******      3.在pos位置后面插入数据              4.pos位置后面删除数据       ******\n");
	printf("******      5.在pos位置插入数据                  6.删除pos位置的数据         ******\n");
	printf("******      7.删除对应元素的所有结点             8.查找元素                  ******\n");
	printf("******      9.头插                               10.头删                     ******\n");
	printf("******      11.尾插                              12.尾删                     ******\n");
	printf("******      13.打印                              0.退出                      ******\n");
	printf("***********************************************************************************\n");
}

int main()
{
	int input = 0;
	int Max = 0;
	SLTNode* Phead = NULL;
	int flag = 1;
	do
	{
		menu();
		if (flag == 1)
		{
			printf("请优先在选项1或者选项2进行选择，创建一个链表\n");
			flag = -1;
		}
		printf("请选择:>\n");
		scanf("%d",&input);
		switch (input)
		{
		case 1:
			printf("请输入该连续链表的结点个数:>");
			scanf("%d", &Max);
			Phead = CreatSList(Max);
			break;
		case 2:
			Phead = CreatArr();
			break;
		case 3:
		{
			int FindNum = 0;
			SListDataType x = 0;
			printf("请输入你要在哪个值后面插入数据:>\n");
			scanf("%d", &FindNum);
			printf("请输入想要插入的值:>\n");
			scanf("%d",&x);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTInsertAfter(pos, x);
			break;
		}
		case 4:
		{
			int FindNum = 0;
			printf("请输入你要在哪个值后面删除数据:>\n");
			scanf("%d", &FindNum);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTEraseAfter(pos);
			break;
		}
		case 5:
		{
			int FindNum = 0;
			SListDataType x = 0;
			printf("请输入你要在哪个值的位置插入数据:>\n");
			scanf("%d", &FindNum);
			printf("请输入想要插入的值:>\n");
			scanf("%d",&x);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTInsert(&Phead, pos, x);
			break;
		}
		case 6:
		{
			int FindNum = 0;
			printf("请输入你删除哪个值的第一次出现的位置:>\n");
			scanf("%d", &FindNum);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTErase(&Phead, pos);
			break;
		}
		case 7:
		{
			SListDataType Number = 0;
			printf("请输入你要删除哪个值:>\n");
			scanf("%d", &Number);
			Phead = RemoveElements(Phead, Number);
			break;
		}
		case 8:
		{
			SListDataType Number = 0;
			printf("请输入你要查找的元素:>\n");
			scanf("%d", &Number);
			SLTNode* Ptail = SLTFind(Phead, Number);
			if(Ptail->next != NULL)
				printf("地址是:%p   在元素%d的前面\n", Ptail, Ptail->next->data);
			else
				printf("地址是:%p   链表的最后一个结点\n", Ptail);
			break;
		}
		case 9:
		{
			SListDataType Number = 0;
			printf("请输入你要插入的值:>");
			scanf("%d", &Number);
			SLTPushFront(&Phead, Number);
			break;
		}
		case 10:
			SLTPopFront(&Phead);
			break;
		case 11:
		{
			SListDataType Number = 0;
			printf("请输入你要插入的值:>");
			scanf("%d", &Number);
			SLTPushBack(&Phead,Number);
			break;
		}
		case 12:
			SLTPopBack(&Phead);
			break;
		case 13:
			SLTPrint(Phead);
			break;
		case 0:
			printf("销毁链表成功\n");
			SLTDestroy(&Phead);
			break;
		default:
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (input);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136

    SList.h文档的代码

    #pragma once

#include
#include
#include

typedef int SListDataType;
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SLTNode;

//创建结点
SLTNode* BuySLTNode(SListDataType x);

//创建链表
SLTNode* CreatSList(int n);

//打印链表
void SLTPrint(SLTNode* Phead);

//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x);

//尾删函数
void SLTPopBack(SLTNode** PPhead);

//头插函数
void SLTPushFront(SLTNode** PPhead,SListDataType x);

//头删函数
void SLTPopFront(SLTNode** PPhead);

//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos, SListDataType x);

//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x);

//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos);

//删除pos位置的数据
void SLTErase(SLTNode** PPhead, SLTNode* pos);

//销毁链表
void SLTDestroy(SLTNode** PPhead);

//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x);

//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead,SListDataType x);

//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n);

//输入数组的元素
SListDataType* CreatArr();

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    SList.c文档的代码

    #include"SList.h"

//创建结点
SLTNode* BuySLTNode(SListDataType x)
{
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL)
	{
		perror("BuySLTNode()");
		exit(1);
	}
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

//创建链表
SLTNode* CreatSList(int n)
{
	SLTNode* Phead = NULL, * Ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* NewNode = BuySLTNode(i);

		if (NewNode == NULL)
		{
			perror("CreatSList()");
			exit(1);
		}

		if (Phead == NULL)
		{
			Phead = Ptail = NewNode;
		}
		else
		{
			Ptail->next = NewNode;
			Ptail = NewNode;
		}
	}
	return Phead;
}

//打印链表
void SLTPrint(SLTNode* Phead)
{
	SLTNode* cur = Phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	if (NewNode == NULL)
	{
		perror("SLTPushBack()");
		exit(1);
	}

	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		SLTNode* cur = *PPhead;
		//找尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = NewNode;
	}
}

//尾删函数
void SLTPopBack(SLTNode** PPhead)
{
	assert(PPhead != NULL);

	if ((*PPhead)->next == NULL)
	{
		free(*PPhead);
		*PPhead = NULL;
	}
	else
	{
		SLTNode* cur = *PPhead;
		//找尾
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}

//头插函数
void SLTPushFront(SLTNode** PPhead, SListDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = *PPhead;
	*PPhead = NewNode;
}

//头删函数
void SLTPopFront(SLTNode** PPhead)
{
	assert(PPhead != NULL);
	SLTNode* next = (*PPhead)->next;
	free(*PPhead);
	*PPhead = next;
}

//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos,SListDataType x)
{
	assert(pos != NULL);
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = pos->next;
	pos->next = NewNode;
}

//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x)
{
	assert(pos != NULL);
	if ((*PPhead) == pos)
	{
		SLTPushFront(PPhead,x);
	}
	else
	{
		SLTNode* cur = *PPhead;
		SLTNode* NewNode = BuySLTNode(x);
		//找到pos前的位置
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		NewNode->next = pos;
		cur->next = NewNode;
	}
}

//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos != NULL);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* NextNode = pos->next;
		pos->next = NextNode->next;
		free(NextNode);
		NextNode = NULL;
	}
}

//删除pos位置的数据
void SLTErase(SLTNode** PPhead,SLTNode* pos)
{
	assert(*PPhead != NULL);
	assert(pos != NULL);

	if (pos == *PPhead)
	{
		SLTPopFront(PPhead);
	}
	else
	{
		SLTNode* cur = *PPhead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//销毁链表
void SLTDestroy(SLTNode** PPhead)
{
	SLTNode* cur = *PPhead;
	while (cur != NULL)
	{
		SLTNode* NextNode = cur->next;
		free(cur);
		cur = NextNode;
	}
	*PPhead = NULL;
}

//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x)
{
	SLTNode* cur = Phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL; 
}

//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead, SListDataType x)
{
	SLTNode* cur = Phead;
	SLTNode* NewHead = NULL, *Ptail = NULL;
	while (cur)
	{
		//分别判断不是相应结点    判断不是最后一个结点  判断是倒数第二个结点      判断最后一个是相应结点
		if (cur->data != x && cur->next != NULL && cur->next->next == NULL && cur->next->data == x)
		{
			free(cur->next);    //释放最后一个结点
			cur->next = NULL;    
			Ptail->next = cur;  //倒数第二个结点地址传过去
			cur = cur->next;
		}
		else if (cur->data != x)
		{
			if (Ptail == NULL)
			{
				NewHead = Ptail = cur;
			}
			else
			{
				Ptail->next = cur;
				Ptail = Ptail->next;
			}
			cur = cur->next;
		}
		else if(cur->data == x)       
		{
			SLTNode* NextNode = cur->next;
			free(cur);
			cur = NextNode;
		}
	}
	return NewHead;
}

//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n)
{
	SLTNode* Phead = NULL, * Ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* NewHead = BuySLTNode(arr[i]);
		if (Ptail == NULL)
		{
			Phead = Ptail = NewHead;
		}
		else
		{
			Ptail->next = NewHead;
			Ptail = Ptail->next;
		}
	}
	return Phead;
}

#define MAX 100

//输入数组的元素
SListDataType* CreatArr()
{
	int N = 0;
	printf("请输入数组元素个数:>");
	scanf("%d", &N);
	SListDataType arr[MAX];
	printf("请依次输入数组的元素，按空格隔开\n");
	for (int i = 0; i < N; i++)
	{
		scanf("%d",&arr[i]);
	}
	return CreatSLTByArr(arr,N);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294

    test.c文档的代码

    #include"SList.h"

void menu()
{
	printf("***********************************************************************************\n");
	printf("******      1.创建连续的链表                     2.通过数组元素创建链表      ******\n");
	printf("******      3.在pos位置后面插入数据              4.pos位置后面删除数据       ******\n");
	printf("******      5.在pos位置插入数据                  6.删除pos位置的数据         ******\n");
	printf("******      7.删除对应元素的所有结点             8.查找元素                  ******\n");
	printf("******      9.头插                               10.头删                     ******\n");
	printf("******      11.尾插                              12.尾删                     ******\n");
	printf("******      13.打印                              0.退出                      ******\n");
	printf("***********************************************************************************\n");
}

int main()
{
	int input = 0;
	int Max = 0;
	SLTNode* Phead = NULL;
	int flag = 1;
	do
	{
		menu();
		if (flag == 1)
		{
			printf("请优先在选项1或者选项2进行选择，创建一个链表\n");
			flag = -1;
		}
		printf("请选择:>\n");
		scanf("%d",&input);
		switch (input)
		{
		case 1:
			printf("请输入该连续链表的结点个数:>");
			scanf("%d", &Max);
			Phead = CreatSList(Max);
			break;
		case 2:
			Phead = CreatArr();
			break;
		case 3:
		{
			int FindNum = 0;
			SListDataType x = 0;
			printf("请输入你要在哪个值后面插入数据:>\n");
			scanf("%d", &FindNum);
			printf("请输入想要插入的值:>\n");
			scanf("%d",&x);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTInsertAfter(pos, x);
			break;
		}
		case 4:
		{
			int FindNum = 0;
			printf("请输入你要在哪个值后面删除数据:>\n");
			scanf("%d", &FindNum);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTEraseAfter(pos);
			break;
		}
		case 5:
		{
			int FindNum = 0;
			SListDataType x = 0;
			printf("请输入你要在哪个值的位置插入数据:>\n");
			scanf("%d", &FindNum);
			printf("请输入想要插入的值:>\n");
			scanf("%d",&x);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTInsert(&Phead, pos, x);
			break;
		}
		case 6:
		{
			int FindNum = 0;
			printf("请输入你删除哪个值的第一次出现的位置:>\n");
			scanf("%d", &FindNum);
			SLTNode* pos = SLTFind(Phead, FindNum);
			SLTErase(&Phead, pos);
			break;
		}
		case 7:
		{
			SListDataType Number = 0;
			printf("请输入你要删除哪个值:>\n");
			scanf("%d", &Number);
			Phead = RemoveElements(Phead, Number);
			break;
		}
		case 8:
		{
			SListDataType Number = 0;
			printf("请输入你要查找的元素:>\n");
			scanf("%d", &Number);
			SLTNode* Ptail = SLTFind(Phead, Number);
			if(Ptail->next != NULL)
				printf("地址是:%p   在元素%d的前面\n", Ptail, Ptail->next->data);
			else
				printf("地址是:%p   链表的最后一个结点\n", Ptail);
			break;
		}
		case 9:
		{
			SListDataType Number = 0;
			printf("请输入你要插入的值:>");
			scanf("%d", &Number);
			SLTPushFront(&Phead, Number);
			break;
		}
		case 10:
			SLTPopFront(&Phead);
			break;
		case 11:
		{
			SListDataType Number = 0;
			printf("请输入你要插入的值:>");
			scanf("%d", &Number);
			SLTPushBack(&Phead,Number);
			break;
		}
		case 12:
			SLTPopBack(&Phead);
			break;
		case 13:
			SLTPrint(Phead);
			break;
		case 0:
			printf("销毁链表成功\n");
			SLTDestroy(&Phead);
			break;
		default:
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (input);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    单链表的实现就到此结束，关注点一点，下期更精彩。

  • 相关阅读:
    Js内置对象相关知识点整理
    Jmeter的使用说明
    使用dd命令创建swap交换分区
    Python深度学习实践代码实现
    【Spring】AOP的三种方式
    java boot项目读取yml配置信息
    Linux进程地址空间
    Java#23(常见API--1)
    教程更新 | RK3568驱动指南第六篇-平台总线
    深度学习之PyTorch实战（4）——迁移学习
  • 原文地址：https://blog.csdn.net/GD_small_bit/article/details/128071071