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初始化成0 f1.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是否等于idata f1.1.1.1 如果是, 那么,返回1 f1.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,用来保存链表头head f1.2 while循环,控制循环的变量是链表头p,当p!=NULL 时,进入循环,找出位置插入新节点new //内在逻辑:当结构体指针head不等于NULL时,说明没有访问到链表尾巴的后面 f1.2.1 通过结构体指针间接访问成员变量node(node代表当前第几个节点), 判断 p->node 是否等于nodePosition f1.2.1.1 如果是, f1.2.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1; //内在逻辑:用flag=1代表找到了位置插入,flag=0代表没有找到位置插入,可以初始化成0 f1.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 插入成功后,提前退出循环,不急着退出函数,一会来改后面节点的node f1.2.1.2 修改代表节点的循环变量p,让p往后走: p = p->next; f1.3 判断代表找到设定节点位置nodePosition的变量flag是否等于1 //内在逻辑:插入成功后,在return 1之前,修改新插入节点后面节点的节点位置标志node,让它们加1。 f1.3.1 如果是,接下来让new节点后面的节点中的node成员变量自增1 f1.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的指向要设置成NULL int 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函数的链表头head f1.1 新定义一个代表节点的结构体指针变量p,用来保存链表头head f1.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+1 f1.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 是否等于nodePosition f1.3.1.1 如果是, f1.3.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1; //内在逻辑:用flag=1代表找到了位置插入,flag=0代表没有找到位置插入,flag初始化成0 f1.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 插入成功后,提前退出循环,不急着退出函数,一会来改后面节点的node f1.3.1.2 修改代表节点的循环变量p,让p往后走: p = p->next; f1.4 判断代表找到设定节点位置nodePosition的变量flag是否等于1 //内在逻辑:插入成功后,在return head之前,修改新插入节点后面节点的node,让它们加1。 f1.4.1 如果是,接下来让new节点后面的节点中的node成员变量自增1 f1.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函数的链表头head f1.1 新定义一个代表节点的结构体指针变量p,用来保存链表头head f1.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-1 f1.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 是否等于nodePosition f1.3.1.1 如果是, f1.3.1.1.1 修改代表找到设定节点位置nodePosition的变量flag: flag = 1; //内在逻辑:用flag=1代表找到了位置删除,flag=0代表没有找到位置删除,flag初始化成0 f1.3.1.1.2 让节点p指向设定删除节点的后一个节点,断开节点p和它原先后面节点的连接: p->next = p->next->next; f1.3.1.1.3 删除成功后,提前退出循环,不急着退出函数,一会来改后面节点的node f1.3.1.2 修改代表节点的循环变量p,让p往后走: p = p->next; f1.4 判断代表找到设定节点位置nodePosition的变量flag是否等于1 //内在逻辑:删除成功后,在return head之前,修改被删除节点后面节点的node,让它们减1。 f1.4.1 如果是,接下来让被删节点后面的节点中的node成员变量自减1 f1.4.1.1 修改代表节点的变量p,让p往后走: p = p->next; //内在逻辑:比如说删除节点4之后,那么就从节点3跳到节点5,从原先的节点5位置开始修改node f1.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; } }