动态链表创建及操作（对静态的补充）
0.修改上两节中结构体形式和遍历链表函数
1、原因：不妨增加一个结构体中的成员变量用来表示数据，修改打印链表的函数，让它同时打印节点序号和节点数据。这样，我们能直观地看出头插法和尾插法创建动态链表时的特点。
2、修改之处：
//修改点1：结构体
struct Test
{int node;int idata; //新增了一个代表链表元素数据的变量idatastruct Test *next;
};//修改点2：printLink函数
void printLink(struct Test *head) //同时打印节点序号node和数据idata
{struct Test *p = head; printf("node: ");while(p != NULL){printf("%d ", p->node);p = p->next;}putchar('\\n');p = head;printf("idata: ");while(p != NULL){printf("%d ", p->idata);p = p->next;}putchar('\\n');
}1.头插法创建动态链表（延续上一节：节点前插入新节点的思路）
1、封装头插法创建动态链表的API：如果把低节点位置类比于入口，那么头插法就类似于栈的先进后出的特点，不断让新节点涌进来，同时新节点总是作为链表头。头插法是在上一节“节点前插入新节点”的特殊情况，但是你不知道一开始的链表头是不是NULL。它的特点是：先输入的数据，离链表头远，后显示。
- 思路：用malloc动态开辟我们再熟悉不过了，因此先暂时忽略动态开辟的新节点，只知道它保存在结构体指针new中。另外，相比于上一节中：节点前插入新节点，我们不需要形参nodePosition。
f1. 封装头插法的API1: struct Test* insertFromHead(struct Test *head, struct Test *new); 形参head用来接收链表头，new用来接收新节点，返回值是结构体指针，用来在别处修改链表头headf1.1 新定义一个代表节点的结构体指针变量p，用来保存链表头head: struct Test *p = head;f1.2 把节点new的node修改成1，因为我们总是认为新节点是链表头: new->node = 1;f1.3 判断head是否是NULL，f1.3.1 如果是，那么说明本来链表是空的，那么就把新节点new当做链表头返回f1.3.1.1 把节点new的next成员修改成NULL，这是必要的语句: new->next = NULL;//内在逻辑：head为NULL是大概率的，若不把new的next设成NULL，那么链表尾巴就无法指向NULLf1.3.1.2 直接返回new，修改别处的链表头headf1.3.2 否则，说明链表一开始不是空，所以f1.3.2.1 那么让新节点指向旧链表头: new->next = head;f1.4 while循环，控制循环的变量是节点p，当p!=NULL 时，进入循环，让head及以后的节点的node都自加1f1.4.1 修改节点p的node，让它自加1: p->node = p->node + 1;f1.4.2 修改代表节点的循环变量p，让p往后走: p = p->next;f1.5 返回节点new，让新节点作为链表头 - 代码：
struct Test* insertFromHead(struct Test *head, struct Test *new) {struct Test *p = head;new->node = 1;/* 如果head确实是NULL，即本来链表是空的，那么就把new返回，提前结束函数就行了 */if(head == NULL){new->next = NULL;return new;}else{new->next = head; //否则让新节点new指向旧链表头head}/* 另外，让head及之后的node都自加1 */while(p != NULL){ p->node = p->node + 1;p = p->next;}return new; }
2、封装用头插法批量创建动态链表的API：
- 分开写的好处：既可以通过initLink()函数批量动态创建多个节点。又可以通过insertFromHead()函数根据需要单独用头插法动态创建一个新的链表头。
- 思路：
f2. 封装头插法批量创建动态链表的API2: struct Test* initLink(struct Test *head); 形参是链表头head，函数返回值是结构体指针，用来修改main函数中head的指向f2.1 定义一个代表新节点的结构体指针变量new，用来保存开辟的动态内存: struct Test *new = NULL;f2.2 while死循环，直到输入的数是0才终止开辟动态内存，同时把输入的数放在new.idata中f2.2.1 输入新链表头中的数据，暂时保存在变量data中: scanf("%d", &data);f2.2.2 判断输入的值是否是0，f2.2.2.1 如果是，说明要终止开辟动态内存，用break结束死循环f2.2.2.2 否则，继续开辟动态节点f2.2.2.2.1 用malloc函数开辟一个动态内存，大小是结构体的占用空间，地址保存在new中:new = (struct Test*)malloc(sizeof(struct Test));f2.2.2.2.2 malloc后面接个必要语句，判断是否成功，不成功就exit结束整个程序f2.2.2.2.3 将键盘输入data赋值给新节点new中的idata: new->idata = idata;f2.2.2.2.4 设置完毕新节点new的数据后，调用API1. 把原链表头head和新节点new放到头插法的函数中，实现动态链表的创建: head = insertFromHead(head,new);f2.3 返回head - 代码：
struct Test* initLink(struct Test *head) {int data;struct Test *new = NULL;while(1){puts("请输入新链表头的数据(输入0代表停止创建动态链表节点)");scanf("%d", &data);if(data == 0){break;}else{new = (struct Test*)malloc(sizeof(struct Test));if(new == NULL){puts("malloc error");exit(-1);}new->idata = data;head = insertFromHead(head, new);}}return head; }
3、结合以上两个函数，实现动态链表创建：它的特点是：先输入的数据，离链表头远，后显示。
- 总体代码和演示结果：
#include <stdio.h> #include <stdlib.h> struct Test {int node;int idata;struct Test *next; }; void printLink(struct Test *head); struct Test* insertFromHead(struct Test *head, struct Test *new); struct Test* initLink(struct Test *head); int main(int argc, char const *argv[]) {struct Test *head = NULL;puts("没有申请动态节点之前");printLink(head);head = initLink(head); //头插法批量初始化动态链表puts("初始化完毕，结果为:");printLink(head);return 0; } void printLink(struct Test *head) {struct Test *p = head; printf("node: ");while(p != NULL){printf("%d ", p->node);p = p->next;}putchar('\\n');p = head;printf("idata: ");while(p != NULL){printf("%d ", p->idata);p = p->next;}putchar('\\n'); } struct Test* insertFromHead(struct Test *head, struct Test *new) {struct Test *p = head;new->node = 1;/* 如果head确实是NULL，即本来链表是空的，那么就把new返回，提前结束函数就行了 */if(head == NULL){new->next = NULL;return new;}else{new->next = head; //否则让新节点new指向旧链表头head}while(p != NULL){ //让head及之后的node都自加1p->node = p->node + 1;p = p->next;}return new; } struct Test* initLink(struct Test *head) {int data;struct Test *new = NULL;while(1){puts("请输入新链表头的数据(输入0代表停止创建动态链表节点)");scanf("%d", &data);if(data == 0){break;}else{new = (struct Test*)malloc(sizeof(struct Test));if(new == NULL){puts("malloc error");exit(-1);}new->idata = data;head = insertFromHead(head, new);}}return head; }
2.尾插法创建动态链表（延续上一节：节点后插入新节点的思路）
1、封装尾插法创建动态链表的API：如果把低节点位置类比于出口，那么尾插法就类似于队列的先进先出的特点，新节点总是作为链表尾巴。尾插法是在上一节“节点后插入新节点”的特殊情况，而且你不知道一开始的链表头是不是NULL。尾插法创建动态链表时的特点就是：（先输入的数据，离链表头近，先显示）。
- 思路：
f1. 封装尾插法的API1: struct Test* insertFromTail(struct Test *head, struct Test *new); 形参head用来接收链表头，new用来接收新节点，返回值是结构体指针，用来在别处修改链表头headf1.1 新定义一个代表节点的结构体指针变量p，用来保存链表头head: struct Test *p = head;f1.2 把节点new的next修改成NULL，因为这是在链表尾插入新节点的必要语句，否则链表尾就无法指向NULLf1.3 判断head是否是NULL，f1.3.1 如果是，那么说明本来链表是空的，那么就把新节点new当做链表头返回f1.3.1.1 把节点new的node成员修改成1，示意它现在是链表头: new->node = 1;f1.3.1.2 直接返回new，修改别处的链表头head//否则，说明链表一开始不是空，所以让链表尾巴指向新节点new，首先要做的就是定位到原先的链表尾f1.4 while循环，控制循环的变量是节点p的指向，当p->next !=NULL 时，进入循环//内在逻辑：控制循环的条件不能是p != NULL，否则最后节点p会定位在NULL，无法建立链表尾和new的关系f1.4.1 修改代表节点的循环变量p，让p往后走: p = p->next;f1.4.2 修该记录节点数的循环变量cnt，让它自加1: cnt++; f1.5 把节点p定位到链表尾后，让链表尾指向新节点new: p->next = new;//最后通过cnt记录新节点的node是多少f1.6 因为循环控制变量是p->next的缘故，所以cnt少加了1: cnt = cnt + 1;f1.7 修改新节点new的node，由于新节点插入在节点数为cnt的链表尾部，所以: new->node = cnt + 1;f1.8 返回链表头head - 代码：
truct Test* insertFromTail(struct Test *head, struct Test *new) {int cnt = 0;struct Test *p = head;new->next = NULL;/* 如果head确实是NULL，即本来链表是空的，那么就把new返回，提前结束函数就行了 */if(head == NULL){new->node = 1;return new;}/* 否则让链表尾巴指向新节点new */while(p->next != NULL){ p = p->next;cnt++;}p->next = new;/* 另外记录new的node是多少 */cnt = cnt + 1;new->node = cnt + 1;return head; }
2、封装用尾插法批量创建动态链表的API：
- 两个函数分开写的好处：既可以通过initLink()函数批量动态创建多个节点。又可以通过insertFromTail()函数根据需要单独用尾插法动态创建一个新的链表尾巴。
- 思路：
f2. 封装尾插法批量创建动态链表的API2: struct Test* initLink(struct Test *head); 形参是链表头head，函数返回值是结构体指针，用来修改main函数中head的指向f2.1 定义一个代表新节点的结构体指针变量new，用来保存开辟的动态内存: struct Test *new = NULL;f2.2 while死循环，直到输入的数是0才终止开辟动态内存，同时把输入的数放在new.idata中f2.2.1 输入新链表头中的数据，暂时保存在变量data中: scanf("%d", &data);f2.2.2 判断输入的值是否是0，f2.2.2.1 如果是，说明要终止开辟动态内存，用break结束死循环f2.2.2.2 否则，继续开辟动态节点f2.2.2.2.1 用malloc函数开辟一个动态内存，大小是结构体的占用空间，地址保存在new中:new = (struct Test*)malloc(sizeof(struct Test));f2.2.2.2.2 malloc后面接个必要语句，判断是否成功，不成功就exit结束整个程序f2.2.2.2.3 将键盘输入data赋值给新节点new中的idata: new->idata = idata;f2.2.2.2.4 设置完毕新节点new的数据后，调用API1. 把原链表头head和新节点new放到尾插法的函数中，实现动态链表的创建: head = insertFromTail(head,new);f2.3 返回head - 代码：
struct Test* initLink(struct Test *head) {int data;struct Test *new = NULL;while(1){puts("请输入新链表尾的数据(输入0代表停止创建动态链表节点)");scanf("%d", &data);if(data == 0){break;}else{new = (struct Test*)malloc(sizeof(struct Test));if(new == NULL){puts("malloc error");exit(-1);}new->idata = data;head = insertFromTail(head, new);}}return head; }
3、结合以上两个函数，实现动态链表创建：（先输入的数据，离链表头近，先显示）
- 总体代码和演示结果：
#include <stdio.h> #include <stdlib.h> struct Test {int node;int idata;struct Test *next; }; void printLink(struct Test *head); struct Test* insertFromTail(struct Test *head, struct Test *new); struct Test* initLink(struct Test *head); int main(int argc, char const *argv[]) {struct Test *head = NULL;puts("没有申请动态节点之前");printLink(head);head = initLink(head); //尾插法批量初始化动态链表puts("初始化完毕，结果为:");printLink(head);return 0; } void printLink(struct Test *head) {struct Test *p = head; printf("node: ");while(p != NULL){printf("%d ", p->node);p = p->next;}putchar('\\n');p = head;printf("idata: ");while(p != NULL){printf("%d ", p->idata);p = p->next;}putchar('\\n'); } struct Test* insertFromTail(struct Test *head, struct Test *new) {int cnt = 0;struct Test *p = head;new->next = NULL;/* 如果head确实是NULL，即本来链表是空的，那么就把new返回，提前结束函数就行了 */if(head == NULL){new->node = 1;return new;}/* 否则让链表尾巴指向新节点new */while(p->next != NULL){ p = p->next;cnt++;}p->next = new;/* 另外记录new的node是多少 */cnt = cnt + 1;new->node = cnt + 1;return head; } struct Test* initLink(struct Test *head) {int data;struct Test *new = NULL;while(1){puts("请输入新链表尾的数据(输入0代表停止创建动态链表节点)");scanf("%d", &data);if(data == 0){break;}else{new = (struct Test*)malloc(sizeof(struct Test));if(new == NULL){puts("malloc error");exit(-1);}new->idata = data;head = insertFromTail(head, new);}}return head; }
3.头插法和尾插法代码总结
tip1：这两个程序很相近，我们都可以分为两个函数，第一个就是头插法或尾插法的API1，它们只负责：①建立新节点new和原先链表head的联系，②注明节点序号。
tip2：第二个是批量初始化动态节点的API2，它们负责：①循环开辟新节点new，②键盘输入初始化新节点new中的数据idata，③把head和new打包给API1。
4.完善删除链表节点的API
代码心得：
- 被删除的那个节点，我们不希望它再占用空间了，可以使用free函数（<stdlib.h>）把垃圾清除掉，其中free函数在“为字符串开辟动态内存”一节中讲过。
- 在Linux中出现忘记函数声明在哪个头文件中的情况时，使用man指令能为开发带来便利，man是manual(手册)的缩写。比如man 3 free ：代表尝试去手册第3页找库函数free的函数声明所在的头文件。
- 在delNode函数中，我们可以提前定义一个结构体指针deletedNode，用来代表将来要释放的链表节点，这是因为：在被删除节点还与它前面的节点有连接关系之前，不能随意释放它，如果释放后再对它操作会发生段错误，于是，要等被删节点与其他东西没关系的时候再释放。
- 删除节点时，要考虑删除的是否是第一个节点。①如果删除第一个节点，那么链表头会发生变化，体现在main函数中的head的指向发生变化。②如果删除的不是第一个节点，那么不需要修改链表头，以删除节点4为例，这里要注意：不能等到节点p移到4的位置才进行删除，而是需要通过节点3找节点4，因为我们需要修改节点3的指向（绕过节点4，指向节点5）。如图：
1、delNode()函数完善后的代码：
- 思路：先用头插法或者尾插法创建一个动态链表，然后再对delNode()函数进行测试
f1. 封装删除静态链表某节点的API: struct Test* delNode(struct Test *head, int nodePosition); 形参head用来接收链表头，形参nodePosition代表想要删除第几个， 返回值是结构体指针，用来修改main函数的链表头headf1.1 新定义一个代表节点的结构体指针变量p，用来保存链表头head: struct Test *p = head;f1.2 新定义一个代表被删节点的结构体指针变量deletedNode: struct Test *deletedNode;f1.3 判断是否删除的是第1个节点f1.3.1 如果是，说明链表头被删除，并且链表头需要改动f1.3.1.1 记录被删节点: deletedNode = head;f1.3.1.2 修改链表头的指向，让head指向节点2: head = head->next;f1.3.1.2 用free函数释放掉被删节点: free(deletedNode);f1.3.1.3 将节点p移动到新链表头，接下来准备修改往后各个节点的node: p = head;f1.3.1.4 while循环，控制循环的变量p，当p!=NULL 时，进入循环，把后面所有节点的node-1f1.3.1.4.1 从节点p开始，也就是从新链表头开始，修改node: p->node = p->node - 1;f1.3.1.4.2 修改代表节点的循环变量p，让p往后走: p = p->next;f1.3.1.5 修改完毕，返回节点head，提前结束函数: return head;//否则，说明删除的不是链表头，不用修改链表头，接下来就正常删除f1.4 while循环，控制循环的变量是链表头p，当p->next!=NULL 时，进入循环，希望找出被删节点//内在逻辑：控制循环条件不能是p!=NULL，否则最后节点p会定位在被删节点，无法解除被删节点和前节点的关系f1.4.1 通过前一个节点访问后一个节点的node，判断 p->next->node 是否等于nodePositionf1.4.1.1 如果是，说明找到可删除节点f1.4.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1;//内在逻辑：用flag=1代表找到了位置删除，flag=0代表没有找到位置删除，flag初始化成0f1.4.1.1.2 记录被删节点: deletedNode = p->next;f1.4.1.1.3 让节点p指向设定删除节点的后一个节点，断开节点p和它原先后面节点的连接: p->next = p->next->next;f1.4.1.1.4 用free函数释放掉被删节点: free(deletedNode);f1.4.1.1.5 删除成功后，break提前退出循环，不急着return，f1.4中来改后面节点的nodef1.4.1.2 否则，修改代表节点的循环变量p，让p往后走: p = p->next;f1.5 判断代表找到设定节点位置nodePosition的变量flag是否等于1//内在逻辑：删除成功后，在return head之前，修改被删除节点后面节点的node，让它们减1。f1.5.1 如果是，接下来让被删节点后面的节点中的node成员变量自减1f1.5.1.1 修改代表节点的变量p，让p往后走: p = p->next;//内在逻辑：比如说删除节点4之后，那么就从节点3跳到节点5，从原先的节点5位置开始修改nodef1.5.1.2 while循环，控制循环的变量p，当p!=NULL 时，进入循环f1.5.1.2.1 修改循环变量p中的node成员变量，自减1: p->node = p->node - 1;f1.5.1.2.2 修改代表节点的循环变量p，让p往后走: p = p->next;f1.5.1.3 修改完毕，返回head，结束函数。f1.4.2 否则，代表删除失败（比如被删节点的位置输入的过大）那么，返回head //即使删除失败，我们也不希望链表头发生改变 - 代码与演示：
#include <stdio.h> #include <stdlib.h> struct Test {int node;int idata;struct Test *next; }; void printLink(struct Test *head); struct Test* insertFromTail(struct Test *head, struct Test *new); struct Test* initLink(struct Test *head); struct Test* delNode(struct Test *head, int nodePosition); int main(int argc, char const *argv[]) {struct Test *head = NULL;int nodePosition;puts("没有申请动态节点之前");printLink(head);head = initLink(head); //尾插法批量初始化动态链表puts("初始化完毕，结果为:");printLink(head);puts("请输入删除哪个节点");scanf("%d", &nodePosition);head = delNode(head, nodePosition); puts("删除节点以后");printLink(head);return 0; } void printLink(struct Test *head) {struct Test *p = head; printf("node: ");while(p != NULL){printf("%d ", p->node);p = p->next;}putchar('\\n');p = head;printf("idata: ");while(p != NULL){printf("%d ", p->idata);p = p->next;}putchar('\\n'); } struct Test* insertFromTail(struct Test *head, struct Test *new) {int cnt = 0;struct Test *p = head;new->next = NULL;/* 如果head确实是NULL，即本来链表是空的，那么就把new返回，提前结束函数就行了 */if(head == NULL){new->node = 1;return new;}/* 否则让链表尾巴指向新节点new */while(p->next != NULL){ p = p->next;cnt++;}p->next = new;/* 另外记录new的node是多少 */cnt = cnt + 1;new->node = cnt + 1;return head; } struct Test* initLink(struct Test *head) {int data;struct Test *new = NULL;while(1){puts("请输入新链表尾的数据(输入0代表停止创建动态链表节点)");scanf("%d", &data);if(data == 0){break;}else{new = (struct Test*)malloc(sizeof(struct Test));if(new == NULL){puts("malloc error");exit(-1);}new->idata = data;head = insertFromTail(head, new);}}return head; } struct Test* delNode(struct Test *head, int nodePosition) {int flag = 0;struct Test *p = head;struct Test *deletedNode;if(nodePosition == 1){deletedNode = head;head = head->next;free(deletedNode);p = head;while(p != NULL){p->node = p->node - 1;p = p->next;}return head;}while(p->next != NULL){if(p->next->node == nodePosition){flag = 1;deletedNode = p->next;p->next = p->next->next;free(deletedNode);break;}else{p = p->next;}}if(flag == 1){p = p->next;while(p != NULL){p->node = p->node - 1;p = p->next;}return head;}else{puts("删除失败");return head;} }