静态链表常用操作(节点计数/查找/增加/删除)
1.封装计算链表节点个数的API
代码心得:
- cnt是count的缩写,用来计数。
- 节点,我们一般指的是链表中数据的地址(指针)。比如节点1就是第一个结构体的地址,节点2就是第2个结构体的地址,以此类推。
- 函数接收链表头以后,再修改head指向,看起来有点奇怪(实际上没什么问题,因为main函数中的head不会变),最好养成习惯,在函数中另外定义一个代表节点的结构体指针p保存head的值,让p去移动。
1、计算链表节点个数:
- 思路:
f1. 封装计算链表节点个数的API: int getLinkNodeNum(struct Test *head); 形参head用来接收链表头f1.1 while,控制循环的变量是链表头head,当head!=NULL 时,进入循环//内在逻辑:当结构体指针head不等于NULL时,说明没有访问到链表尾巴的后面f1.1.1 修改代表节点个数的变量cnt: cnt++; //注意一开始要将cnt初始化成0f1.1.2 修改代表节点的循环变量head,让head往后走: head = head->next;f1.2 返回代表节点个数的变量cnt
- 代码:
#include <stdio.h> struct Test {int idata;struct Test *next; }; int getLinkNodeNum(struct Test *head); int main(int argc, char const *argv[]) {int cnt = 0;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; t2.next = &t3; t3.next = &t4; cnt = getLinkNodeNum(&t1);printf("node numbers: %d\\n", cnt);return 0; } int getLinkNodeNum(struct Test *head) {int cnt = 0;while(head != NULL){cnt++;head = head->next;}return cnt; }
2.封装链表查找的API
- 思路:
f1. 封装链表查找的API: int searchLink(struct Test *head, int idata); 形参head用来接收链表头,形参idata是想要找的整型数据f1.1 while,控制循环的变量是链表头head,当head!=NULL 时,进入循环//内在逻辑:当结构体指针head不等于NULL时,说明没有访问到链表尾巴的后面f1.1.1 通过结构体指针间接访问成员变量idata,判断head->idata是否等于idataf1.1.1.1 如果是,那么,返回1f1.1.2 修改代表节点的循环变量head,让head往后走: head = head->next;f1.2 返回0//内在逻辑:如果顺利通过f1.1,说明没有提前退出循环,也就是没找到idata
- 代码:
#include <stdio.h> struct Test {int idata;struct Test *next; }; int searchLink(struct Test *head, int idata); int main(int argc, char const *argv[]) {struct Test t1 = {1,NULL};struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; t2.next = &t3; t3.next = &t4; if(searchLink(&t1, 5)){puts("找到了");}else{puts("没找到");}return 0; } int searchLink(struct Test *head, int idata) {while(head != NULL){if(head->idata == idata){return 1;}head = head->next;}return 0; }
3.封装链表中插入新节点的API
代码心得:
- 我们如何表示链表中的数据(结构体)是第几个节点呢?其实可以在结构体中定义一个代表当前节点位置的成员变量,不妨叫做node。
- 插入前,新插入的节点new的指向要设置成NULL,因为我们不知道这个链表数据的后面是什么,如果选择在链表末尾那个数据后面插入节点new的话,那么节点new就成为了链表的末尾,因此NULL是必须的。
- 如果有必要修改main函数中的链表头head的指向,也就是修改指针head的值,我们之前讲过,有两种思路,一是用指针函数返回一个结构体指针,二是传递&head后在函数中用结构体二级指针修改head的值。我们推荐用前一种,不容易出错。
- 初始化链表的时候,可以提前定义一个结构体指针变量head表示链表头,在链表创建完毕后令head=&t1
- 以下两种插入方法,只要是正常插入(不涉及链表头的改变),成功插入新节点new后,p->next立马就变成了new,因此成功插入后最好直接退出while循环,不要让p往后移动了,防止死循环(见f1.2、f1.3)。
知识点:插入新节点有两种方式,每种方式中修改节点指向时,需要注意赋值的顺序
- 节点后插入:以在节点3后方插入新节点New为例,必须要让原先节点3和节点4之间的连线最后断掉。
- 找到节点3
- 让节点New先指向节点3原先的指向,也就是节点4
- 让节点3指向节点New,断开3与4的连接
- 依次修改new节点后面节点的节点位置标志node(必要的话)
- 节点前插入:要考虑插入的是否是第一个节点之前。①如果在第一个节点之前插入新节点,那么链表头会发生变化,体现在main函数中的head的指向发生变化。②如果不是在第一个节点之前插入,那么不需要修改链表头,以在节点4前方插入新节点New为例,这里要注意:不能等到节点p移到4的位置才插入,而是需要通过节点3找节点4,因为我们需要修改节点3的指向,所以这部分代码和在节点后插入类似。
1、节点后插入的方式:
- 思路:
f1. 封装在链表某节点后插入新节点的API: int inserFromBehind(struct Test *head, int nodePosition, struct Test *new); 形参head用来接收链表头,形参nodePosition代表想要在第几个节点后插入,形参new代表新节点f1.1 新定义一个代表节点的结构体指针变量p,用来保存链表头headf1.2 while循环,控制循环的变量是链表头p,当p!=NULL 时,进入循环,找出位置插入新节点new//内在逻辑:当结构体指针head不等于NULL时,说明没有访问到链表尾巴的后面f1.2.1 通过结构体指针间接访问成员变量node(node代表当前第几个节点),判断 p->node 是否等于nodePositionf1.2.1.1 如果是,f1.2.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1;//内在逻辑:用flag=1代表找到了位置插入,flag=0代表没有找到位置插入,可以初始化成0f1.2.1.1.2 让节点new先指向节点p原先的指向: new->next = p->next;f1.2.1.1.3 让节点p指向节点new,断开节点p和它原先后面节点的连接f1.2.1.1.4 修改节点new中的成员node: new->node = nodePosition + 1;//内在逻辑:找到可插入位置并插入后,把代表节点编号的node成员变量修改一下f1.2.1.1.5 插入成功后,提前退出循环,不急着退出函数,一会来改后面节点的nodef1.2.1.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.3 判断代表找到设定节点位置nodePosition的变量flag是否等于1//内在逻辑:插入成功后,在return 1之前,修改新插入节点后面节点的节点位置标志node,让它们加1。f1.3.1 如果是,接下来让new节点后面的节点中的node成员变量自增1f1.3.1.1 修改代表节点的变量p,让p往后走: p = p->next;f1.3.1.2 修改代表节点的变量p,让p往后走: p = p->next;//内在逻辑:两次往后走是因为想跳过新插入的节点f1.3.1.3 while循环,控制循环的变量p,当p!=NULL 时,进入循环f1.3.1.3.1 修改循环变量p中的node成员变量,自增1: p->node = p->node + 1;f1.3.1.3.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.3.1.4 修改完毕,返回1,结束函数。f1.3.2 否则,代表插入失败(比如新节点插入的位置输入的过大)那么,返回0
- 代码:
#include <stdio.h> struct Test {int node;struct Test *next; }; void printLink(struct Test *head); int inserFromBehind(struct Test *head, int nodePosition, struct Test *new); int main(int argc, char const *argv[]) {struct Test t1 = {1,NULL};struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; t2.next = &t3; t3.next = &t4; struct Test new = {0,NULL}; //新插入的节点new的指向要设置成NULLint nodePosition;puts("插入新节点以前");printLink(&t1);puts("请输入在哪个节点后插入新节点");scanf("%d", &nodePosition);inserFromBehind(&t1, nodePosition, &new);puts("插入新节点以后");printLink(&t1);return 0; } void printLink(struct Test *head) {while(head != NULL){printf("%d ", head->node);head = head->next;}putchar('\\n'); } int inserFromBehind(struct Test *head, int nodePosition, struct Test *new) {struct Test *p = head;int flag = 0;while(p != NULL){if(p->node == nodePosition){flag = 1;new->next = p->next;p->next = new;new->node = nodePosition + 1;break;}p = p->next;}if(flag == 1){p = p->next;p = p->next;while(p != NULL){p->node = p->node + 1;p = p->next;}return 1;}else{return 0;} }
2、节点前插入的方式:
- 思路:
f1. 封装在链表某节点前插入新节点的API: struct Test* inserFromFront(struct Test *head, int nodePosition, struct Test *new); 形参head用来接收链表头,形参nodePosition代表想要在第几个节点前插入,形参new代表新节点, 返回值是结构体指针,用来修改main函数的链表头headf1.1 新定义一个代表节点的结构体指针变量p,用来保存链表头headf1.2 判断是否要在第一个节点前插入新节点,f1.2.1 如果是,说明链表头需要改动f1.2.1.1 让新节点指向旧链表头,让节点new成为新链表头: new->next = head;f1.2.1.2 修改节点new的node为1: new->node = 1;f1.2.1.3 while循环,控制循环的变量p,当p!=NULL 时,进入循环,把后面所有节点的node+1f1.2.1.3.1 从节点p开始,也就是从旧链表头开始,修改node: p->node = p->node + 1;f1.2.1.3.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.2.1.4 返回new节点,提前结束函数: return new;f1.3 while循环,控制循环的变量是链表头p,当p->next!=NULL 时,进入循环,找出位置插入新节点new//内在逻辑1:如果跳过了f1.2,那么说明不用修改链表头,接下来就正常插入//内在逻辑2:因为我们希望通过设定节点的上一个节点来找设定节点,不能等到p移到设定节点的位置才插入f1.3.1 通过前一个节点访问后一个节点的node,判断 p->next->node 是否等于nodePositionf1.3.1.1 如果是,f1.3.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1;//内在逻辑:用flag=1代表找到了位置插入,flag=0代表没有找到位置插入,flag初始化成0f1.3.1.1.2 让节点new先指向节点p原先的指向: new->next = p->next;f1.3.1.1.3 让节点p指向节点new,断开节点p和它原先后面节点的连接: p->next = new;f1.3.1.1.4 修改节点new的node: new->node = nodePosition;//内在逻辑:找到可插入位置并插入后,把代表节点编号的node成员变量修改一下f1.3.1.1.5 插入成功后,提前退出循环,不急着退出函数,一会来改后面节点的nodef1.3.1.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.4 判断代表找到设定节点位置nodePosition的变量flag是否等于1//内在逻辑:插入成功后,在return head之前,修改新插入节点后面节点的node,让它们加1。f1.4.1 如果是,接下来让new节点后面的节点中的node成员变量自增1f1.4.1.1 修改代表节点的变量p,让p往后走: p = p->next;f1.4.1.2 修改代表节点的变量p,让p往后走: p = p->next;//内在逻辑:两次往后走是因为想跳过新插入的节点f1.4.1.3 while循环,控制循环的变量p,当p!=NULL 时,进入循环f1.4.1.3.1 修改循环变量p中的node成员变量,自增1: p->node = p->node + 1;f1.4.1.3.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.4.1.4 修改完毕,返回head,结束函数。//内在逻辑,不需要修改链表头时,直接返回原先的链表头即可f1.4.2 否则,代表插入失败(比如新节点插入的位置输入的过大)那么,返回head//内在逻辑:即使插入失败,我们也不希望链表头发生改变
- 代码:
#include <stdio.h> struct Test {int node;struct Test *next; }; void printLink(struct Test *head); struct Test* inserFromFront(struct Test *head, int nodePosition, struct Test *new); int main(int argc, char const *argv[]) {struct Test *head;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; t2.next = &t3; t3.next = &t4; head = &t1;struct Test new = {0,NULL};int nodePosition;puts("插入新节点以前");printLink(head);puts("请输入在哪个节点前插入新节点");scanf("%d", &nodePosition);head = inserFromFront(head, nodePosition, &new); puts("插入新节点以后");printLink(head);return 0; } void printLink(struct Test *head) { while(head != NULL){printf("%d ", head->node);head = head->next;}putchar('\\n'); } struct Test* inserFromFront(struct Test *head, int nodePosition, struct Test *new) {int flag = 0;struct Test *p = head;if(nodePosition == 1){new->next = head;new->node = 1;while(p != NULL){p->node = p->node + 1;p = p->next; }return new;}while(p->next != NULL){if(p->next->node == nodePosition){flag = 1;new->next = p->next;p->next = new;new->node = nodePosition;break;} p = p->next;}if(flag == 1){p = p->next;p = p->next;while(p != NULL){p->node = p->node + 1;p = p->next;}return head;}else{puts("插入失败");return head;} }
4.封装删除静态链表节点的API
代码心得:
- 我们现在所讲的删除链表节点的方法,不涉及到释放被删除节点的内存空间,因为目前我们学习到的链表的内存是静态分配的。我们将在第3节(链表动态创建)中去完善删除节点的代码。
知识点:
- 删除节点时,要考虑删除的是否是第一个节点。①如果删除第一个节点,那么链表头会发生变化,体现在main函数中的head的指向发生变化。②如果删除的不是第一个节点,那么不需要修改链表头,以删除节点4为例,这里要注意:不能等到节点p移到4的位置才进行删除,而是需要通过节点3找节点4,因为我们需要修改节点3的指向(绕过节点4,指向节点5)。
1、删除链表节点的方式:
- 思路:
f1. 封装删除静态链表某节点的API: struct Test* delNode(struct Test *head, int nodePosition); 形参head用来接收链表头,形参nodePosition代表想要删除第几个, 返回值是结构体指针,用来修改main函数的链表头headf1.1 新定义一个代表节点的结构体指针变量p,用来保存链表头headf1.2 判断是否删除的是第1个节点f1.2.1 如果是,说明链表头需要改动f1.2.1.1 修改链表头的指向,让head指向节点2: head = head->next;f1.2.1.2 将节点p移动到新链表头,接下来准备修改往后各个节点的node: p = head;f1.2.1.3 while循环,控制循环的变量p,当p!=NULL 时,进入循环,把后面所有节点的node-1f1.2.1.3.1 从节点p开始,也就是从新链表头开始,修改node: p->node = p->node - 1;f1.2.1.3.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.2.1.4 返回节点head,提前结束函数: return new;f1.3 while循环,控制循环的变量是链表头p,当p->next!=NULL 时,进入循环,找出位置插入新节点new//内在逻辑1:如果跳过了f1.2,那么说明不用修改链表头,接下来就正常删除//内在逻辑2:因为我们希望通过设定节点的上一个节点来找设定节点,不能等到p移到设定节点的位置才删除f1.3.1 通过前一个节点访问后一个节点的node,判断 p->next->node 是否等于nodePositionf1.3.1.1 如果是,f1.3.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1;//内在逻辑:用flag=1代表找到了位置删除,flag=0代表没有找到位置删除,flag初始化成0f1.3.1.1.2 让节点p指向设定删除节点的后一个节点,断开节点p和它原先后面节点的连接: p->next = p->next->next;f1.3.1.1.3 删除成功后,提前退出循环,不急着退出函数,一会来改后面节点的nodef1.3.1.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.4 判断代表找到设定节点位置nodePosition的变量flag是否等于1//内在逻辑:删除成功后,在return head之前,修改被删除节点后面节点的node,让它们减1。f1.4.1 如果是,接下来让被删节点后面的节点中的node成员变量自减1f1.4.1.1 修改代表节点的变量p,让p往后走: p = p->next;//内在逻辑:比如说删除节点4之后,那么就从节点3跳到节点5,从原先的节点5位置开始修改nodef1.4.1.2 while循环,控制循环的变量p,当p!=NULL 时,进入循环f1.4.1.3.1 修改循环变量p中的node成员变量,自减1: p->node = p->node - 1;f1.4.1.3.2 修改代表节点的循环变量p,让p往后走: p = p->next;f1.4.1.4 修改完毕,返回head,结束函数。//内在逻辑,不需要修改链表头时,直接返回原先的链表头即可f1.4.2 否则,代表删除失败(比如被删节点的位置输入的过大)那么,返回head//内在逻辑:即使删除失败,我们也不希望链表头发生改变
- 代码:
#include <stdio.h> struct Test {int node;struct Test *next; }; void printLink(struct Test *head); struct Test* delNode(struct Test *head, int nodePosition); int main(int argc, char const *argv[]) {struct Test *head;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; t2.next = &t3; t3.next = &t4; head = &t1;int nodePosition;puts("删除节点以前");printLink(head);puts("请输入删除哪个节点");scanf("%d", &nodePosition);head = delNode(head, nodePosition); puts("删除节点以后");printLink(head);return 0; } void printLink(struct Test *head) { while(head != NULL){printf("%d ", head->node);head = head->next;}putchar('\\n'); } struct Test* delNode(struct Test *head, int nodePosition) {int flag = 0;struct Test *p = head;if(nodePosition == 1){head = head->next;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;p->next = p->next->next;break;}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;} }