数据结构之带头节点的单链表增删改查操作实现
单链表的定义
什么是单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
单链表的各个数据元素在物理上可以是离散存放的，每个结点除了存放数据元素外，还要存储指向下一个节点的指针。而顺序表是连续存放的，每个结点中只存放数据元素。
单链表的优点：不要求大片连续空间，改变容量方便，只需在内存单元中随便找个位置作为新节点的区域；缺点：不可随机存储，要耗费一定空间存放指针。
顺序表的优点：可随机存储，存储密度高；缺点：要求大片连续空间，改变容量不方便，要在内存中再申请一片连续空间。
先理解并记住专业术语 ：
首节点：第一个有效节点。
尾节点：最后一个有效节点。
头节点：头节点的数据类型和首节点的类型一样，没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作（不理解的话，先记住）。
头指针：指向头节点的指针变量。
尾指针：指向尾节点的指针。
确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作，我们至少需要接收链表的那些信息？？？）
只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。
用代码定义一个单链表
大概思路：由一个个节点组成一个单链表 ，所以从定义节点出发，来创建单链表。那节点里都有什么呢？每个节点里不光有存放的数据元素，还要有一个指向下一个节点的指针。这两个也称为数据域和指针域。为什么要有指针域呢？因为单链表的每个节点在物理上是离散存放的，有了一个节点后，那下一个节点就需要通过这个节点找到，这个节点的指针域可以理解为起着连接的作用。需要注意的是指针域的类型是我们此时定义的节点类型。之后为了方便写代码和区分，用typedef 起了节点和节点指针的别名。单链表的英文单词是LinkList，LNode是简写了单链表节点的英文单词 LinkNode。
1 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强
2 int data;//每个节点存放一个数据元素
3 struct LNode *next;//指针指向下一个节点
4 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
在后续代码中 ，使用LinkList，强调这是一个单链表； 使用LNode，强调这是一个节点。
1 void test()
2 {
3 LinkList L; // //声明一个指向单链表的指针,强调声明了一个单链表
4 }
初始化单链表
大概思路：在初始化的过程中，给单链表分配好一个头节点，让头节点的指向下一个节点的指针域指向空，因为在整个单链表中，此时还是空表，也就是没有有效节点，头节点虽然起着节点的名字，并且在写专业术语的时候说过，它只是为了便于操作，注意不要混淆了。
1 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
2 {
3 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
4 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
5 return false;
6 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
7 return true;
8 }
9 void test()
10 {
11 LinkList L; //声明一个指向单链表的指针
12 InitList(L); //初始化一个空表
13 // .......后续代码......
14 }
如果要判断带头节点的单链表是否为空，代码如下：
1 bool Empty(LinkList L) //判断单链表是否为空（带头节点） 头节点不存储数据，只有指针域，且表内没有有效节点
2 {
3 if(L->next == NULL)
4 return true;
5 else
6 return false;
7 }
带头结点的单链表的
InsertList(&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e，刚开始建议看b站的动画，再来理解代码 。
利用while循环找到第 i - 1 个结点，将新结点插入其后，头结点可以看作 “ 第0个” 结点。
1 bool InsertList(LinkList &L, int i, ElemType e) //在第 i 个位置插入元素 e （带头结点） 2 { 3 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个 4 return false; 5 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点 6 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点 7 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始 8 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环 9 { 10 p = p->next; //p指向下一个结点 11 j++; 12 } 13 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置 14 return false; 15 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e 16 s->data = e; 17 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点 18 p->next = s; //将结点s连到p之后 19 return true; //插入成功 20 }
带头结点的单链表的删除
DeleteList(&L,i,&e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
利用while循环找到第 i - 1 个结点，将其指针指向 第 i + 1个结点，并释放第 i 个结点。
1 bool DeleteList(LinkList &L, int i, ElemType &e)
2 {
3 if(i < 1)
4 return false;
5 LNode *p;
6 p = L;
7 int j = 0;
8 while(p != NULL && j < i - 1) //循环找第 i-1 个节点
9 {
10 p = p->next;
11 j++;
12 }
13 if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到
14 return false;
15 if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
16 return false;
17 LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点
18 e = q->data; //用e返回元素的值
19 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点
20 free(q); //释放节s点的存储空间
21 return true;
22 }
带头结点的单链表的修改
UpdateList(&L, i, num)：修改操作，把第i个位置的数修改为num
1 int UpdateList(LinkList &L, int i, int num)//把第i个位置的数修改为num
2 {
3 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
4 return 0;
5 LNode *p;
6 int j = 0;
7 p = L;
8 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
9 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
10 p = p->next;
11 j++;
12 }
13 p->data = num;
14 return p->data;
15 }
带头结点的单链表的查找
GetList(L,i)：按位查找操作。获取表L中第 i 个位置的元素的值。
1 int GetList(LinkList L, int i)//按位查找，返回第 i 个元素（带头节点）
2 {
3 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
4 return NULL;
5 LNode *p;
6 int j = 0;
7 p = L;
8 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
9 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
10 p = p->next;
11 j++;
12 }
13 return p->data;
14 } //平均时间复杂度为O(n)
带头结点的单链表的销毁
1 void Destroy(LinkList &L)
2 {
3 LNode *p;
4 while(L != NULL)
5 {
6 p = L;
7 L = L->next;
8 free(p);
9 }
10 }
完整的增删改查操作的代码，我自己一开始全写在main函数里，只能调用成功一个函数，我也不知道为啥，所以就用了switch选择结构来分别实现这些功能。这些代码理解了，就不难，建议多敲几遍！
1 #include <stdio.h>
2 #include <malloc.h>
3 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强
4 int data;//每个节点存放一个数据元素
5 struct LNode *next;//指针指向下一个节点
6 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
7 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
8 {
9 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
10 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
11 return false;
12 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
13 return true;
14 }
15 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e （带头结点）
16 {
17 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个
18 return false;
19 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点
20 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点
21 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始
22 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环
23 {
24 p = p->next; //p指向下一个结点
25 j++;
26 }
27 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置
28 return false;
29 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e
30 s->data = e;
31 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点
32 p->next = s; //将结点s连到p之后
33 return true; //插入成功
34 }
35 void ShowList(LinkList L) //显示
36 {
37 if(L->next == NULL)
38 printf("这是一个空表\n");
39 while(L != NULL)
40 {
41 L = L->next;
42 printf("%d ",L->data);
43 }
44
45 }
46 bool DeleteList(LinkList &L, int i, int &e)//删除表L中第 i 个位置的元素，并用e返回删除元素的值。
47 {
48 if(i < 1)
49 return false;
50 LNode *p;
51 p = L;
52 int j = 0;
53 while(p != NULL && j < i - 1) //循环找第 i-1 个节点
54 {
55 p = p->next;
56 j++;
57 }
58 if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到
59 return false;
60 if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
61 return false;
62 LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点
63 e = q->data; //用e返回元素的值
64 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点
65 free(q); //释放节s点的存储空间
66 return true;
67 }
68 int GetList(LinkList &L, int i)//按位查找，返回第 i 个元素（带头节点）
69 {
70 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
71 return 0;
72 LNode *p;
73 int j = 0;
74 p = L;
75 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
76 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
77 p = p->next;
78 j++;
79 }
80 return p->data;
81 } //平均时间复杂度为O(n)
82 int UpdateList(LinkList &L, int i, int num)
83 {
84 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
85 return 0;
86 LNode *p;
87 int j = 0;
88 p = L;
89 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
90 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
91 p = p->next;
92 j++;
93 }
94 p->data = num;
95 return p->data;
96 }
97 void Destroy(LinkList &L) //销毁单链表
98 {
99 LNode *p;
100 while(L != NULL)
101 {
102 p = L;
103 L = L->next;
104 free(p);
105 }
106 }
107 void ShowMenu()
108 {
109 printf("************************\n");
110 printf("***** 1,添加数据 *****\n");
111 printf("***** 2,删除数据 *****\n");
112 printf("***** 3,查找数据 *****\n");
113 printf("***** 4,修改数据 *****\n");
114 printf("***** 5,显示数据 *****\n");
115 printf("***** 0,销毁并退出 ***\n");
116 }
117 int main()
118 {
119 LinkList L;//声明一个单链表
120 InitList(L);//初始化函数调用
121
122 int select = 0; //创建选择输入的变量
123 while (true)
124 {
125 //菜单调用
126 ShowMenu();
127 printf("请输入你的选择\n");
128 scanf("%d", &select);
129 switch (select)
130 {
131 case 1: //1,添加数据
132 InsertList(L,1,1);
133 InsertList(L,2,2);
134 InsertList(L,3,3);
135 InsertList(L,4,4);
136 InsertList(L,5,5);
137 printf("数据添加成功！\n");
138 getchar();
139 break;
140 case 2: //2,删除数据
141 int e;
142 if(DeleteList(L,4,e))
143 {
144 printf("删除的数是：%d\n",e);
145 }
146 getchar();
147 break;
148 case 3: //3,查找数据
149 printf("查找的元素是：%d\n",GetList(L,1));
150 getchar();
151 break;
152 case 4: //4,修改数据
153 UpdateList(L,1,0);
154 printf("修改成功！\n");
155 getchar();
156 break;
157 case 5: //4,显示数据
158 printf("单链表的数据有：");
159 ShowList(L);
160 getchar();
161 break;
162 case 0: //0,退出
163 Destroy(L);
164 printf("单链表已销毁！");
165 printf("欢迎下次使用");
166 return 0;
167 break;
168
169 default:
170 break;
171 }
172 }
173 return 0;
174 }
运行结果如下：
在单链表中添加数据并显示数据成功：
在单链表中删除数据并显示数据成功：
在单链表中查找数据并显示数据成功：
在单链表中修改数据并显示数据成功：
