本文主要是介绍链表(静态/动态创建,遍历,计数,查找,在节点的前/后方插入新节点,头插法,尾插法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、前言
二、链表的静态创建和遍历
三、链表统计节点,查找节点是否存在
四、从指定节点的后方插入新节点
五、从指定节点的前方插入新节点
六、动态创建链表&尾插法
七、头插法
八、删除节点
一、前言
链表本质是一个结构体,结构体里不仅包含不同类型的数据,最重要的是定义了一个指向相同结构体类型的指针(必须是相同类型的结构体),通过这个指针我们就可以将一个又一个的结构体链接(指针存放下一个结构体的地址)起来,每一个结构体就是链表的其中一个节点。
掌握以上概念,只要结合代码,相信手撕链表也不是什么难事,无非就是指针和地址的一些操作罢了。
二、链表的静态创建和遍历
我们使用链表的时候可以和数组类比,但两者还是有区别,数组是内存中连续的空间;而链表不一定在内存中连续。
我们遍历数组时,要把数组的所有元素都打印出来,一个for循环就能搞定,而链表的遍历也类似
struct test
{int id;//存放节点的编号struct test *next;//链接下一个节点的地址
};/*静态创建链表*/
struct test n1 = {1,NULL};
struct test n2 = {2,NULL};
struct test n3 = {3,NULL};/*我们先手动建立链接,n3.next为空*/
n1.next = &n2;
n2.next = &n3;void printLink(struct test *head)
{while(head != NULL){printf("%d ",head->id);//打印每个节点的idhead = head->next;//把下个节点的地址给head,head从指向n1变成指向n2}
}
以上就是链表的最最基本的操作,看一下步骤:
head指向n1,打印1;
head->next是n2的地址,head指向n2,打印2;
head->next是n3的地址,head指向n3,打印3;
head->next为NULL,不进入while,结束。
遍历的核心就是 head = head->next 这个操作。
三、链表统计节点,查找节点是否存在
统计节点就很简单了,看得懂遍历就会:
int getLinkNodeNum(struct test *head)
{int cnt = 0;while(head != NULL){cnt++;head = head->next;//关键}return cnt;
}
查找节点,我这里演示代码实现的功能就只是检查是否存在该id的节点,原理也是遍历:
int searchLink(struct test *head, int data)//data传入你想要找的id
{while(head != NULL){if(head->id == data);return 1;//找到了直接退出该函数head = head->next;//遍历}return 0;//失败返回0
}
四、从指定节点的后方插入新节点
在指定节点的后方插入,首先还是要遍历链表,那么函数要传入头节点的地址;还要传入指定节点的id;接着传入新节点的地址(因为我们这里还是使用静态创建的方法,每一个节点都要手动初始化)。来看代码:
int insertFromBehind(struct test *head, int data, struct test *new)
{while(head != NULL){if(head->id == data)//指定id{new->next = head->next;//让新节点的next指向指定节点的nexthead->next = new;//指定节点的next指向新节点,完成插入return 1;}head = head->next;//遍历}return 0;
}
自己画图理解一下最好,你的next存的是谁的地址,就相当于你指向它,只要能理解这句话,链表的任何操作都不难。
五、从指定节点的前方插入新节点
从节点前方插入新节点,有可能是在头节点插入,而链表最重要的就是链表头的地址,那么函数的返回值就是结构体指针,需要返回头节点的地址(头节点可能会改变)
struct test* insertFromFront(struct test *head, int data, struct test *new)
{struct test *p = head;if(p->id == data)//表示想在头节点前面添加新节点{new->next = head;//新节点的next是原先的头节点return new;}while(p->next != NULL){/*如果当前遍历到的节点的下一个节点是我们要找的*/if(p->next->id == data){/*新节点的下一个节点是当前遍历到的节点的下一个节点*/new->next = p->next;/*当前遍历到的节点的下一个节点是新节点*/p->next = new;/*头节点不变,原样返回*/return head;}p = p->next;//遍历}printf("no this id\n");return head;
}
从指定节点前方插入新节点分两种情况:
(1)从头节点前插入新节点:
直接让新节点的下一个节点为原先的头节点,返回新节点的地址。(一般一个链表的头节点head会定义成全局变量,如果头节点不知道,那就无从下手)
(2)除头节点外的其他节点前插入新节点:
遍历链表,假设我们要在节点3前插入,那么遍历到节点2时:node2->next->id=3,new-> = node2->next,运行到这里,新节点的下一个节点就是节点3,但这时节点2和新节点都指向节点3,把节点2指向新节点即可。思路清晰就很简单。
六、动态创建链表&尾插法
静态创建链表还要自己一个个定义,手动建立链接,非常麻烦,而且删除节点的时候,被删除的节点无法释放内存空间,可能会造成溢出等情况,所以要动态创建链表,之前静态创建是为了方便理解一些基础操作。
/*head全局变量*/
struct test *head = NULL;/*动态创建链表*/
struct test* createLink(struct test *head)
{struct test *new;struct test *p = head;while(1){/*给新节点分配内存空间*/new = (struct test*)malloc(sizeof(struct test));/*用户键盘输入新节点id*/scanf("%d",&(new->id));/*id为0结束创建,返回头节点地址*/if(new->id == 0){printf("0 quit\n");free(new);//释放最后建立的新节点的内存空间return head;}/*初始化新节点的next指针*/new->next = NULL;/*建立连接*/if(head == NULL)//如果头节点为NULL{/*创建头节点*/head = new;}else{// 遍历到最后一个节点p = head;while(p->next != NULL){p = p->next;}// 将新节点添加到最后p->next = new;}}
}
使用malloc函数来为每一个新节点分配内存,如果输入的节点id为0代表结束创建,free函数释放最后建立的节点,并返回head头节点的地址。
七、头插法
struct test* insertFromHead(struct test *head)
{struct test *new;while(1){/*和尾插法一样*/new = (struct test*)malloc(sizeof(struct test));scanf("%d",&(new->id));if(new->id == 0){printf("0 quit\n");free(new);return head;} new->next = head;head = new;}return head;
}
原本我在插入节点的时候判断了head是否为空,后来发现没必要,如果不为空,直接插在头节点前面,然后更新头节点即可;如果为空,那new就是尾巴节点,new->next为NULL,这也合理,然后更新头节点。
八、删除节点
struct test* deleteNode(struct test *head, int data)
{struct test *p = head;if(p->id == data){head = head->next;free(p);return head;}while(p->next != NULL){if(p->next->id == data){struct test *temp = p->next;/*关键操作*/p->next = p->next->next;free(temp);return head;}p = p->next;//遍历}return head;
}
操作和从指定节点前方插入节点类似,判断当前p指向的节点的 next->id ,也就是下一个节点是否为要删除的节点,如果是:p->next->next 是要删除的节点的下一个,将它赋值给 p->next 就是跳过要删除的节点,要删除的节点的前一个节点指向要删除的节点的后一个节点。
至此链表的基础操作都讲完了,如果自己用画图的方式,跟着代码一步步走,手撕链表也不在话下,后面我会更新贪吃蛇小游戏,他的核心就是链表的操作,用来锻炼链表的使用能力。
这篇关于链表(静态/动态创建,遍历,计数,查找,在节点的前/后方插入新节点,头插法,尾插法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!