数据结构（C）之单链表

单链表目录单链表单链表定义链表的基本结构单链表的操作链表的创建和初始化链表尾部插入元素链表的遍历打印链表查找按位置查找按元素查找链表指定位置插入元素链表指定位置删除节点删除链表释放空间整体代码单链表定义单链表Singly Linked List是一种线性的数据结构它由一系列节点Node组成每个节点包含两部分数据域Data存储节点的数据。指针域Next指向链表中下一个节点的指针或引用。每个节点除了最后一个节点外都通过指针连接到下一个节点形成链式结构。单链表中的节点是按顺序连接的但没有下标所以访问特定位置的元素时需要从头节点开始逐个遍历。链表的基本结构单链表的核心是一个节点Node的结构定义。常见的 C 语言定义如下typedef int data_t; typedef struct node{ data_t data; struct node* next; }listnode,* linklist;data存储节点的数据可以是任意类型。next指向下一个节点的指针如果当前节点是链表的最后一个节点则next指针为NULL。链表本身通常由一个指向第一个节点的头指针来表示。如果链表为空头指针head的next会是NULL。一个链表的结构如下图所示。其中的p0.p1.p2.p3为各节点的地址。这里需要注意一点对于一个节点它的地址其实有两份拿第一个节点来举例说明在第一个节点的创立之初他就返回了地址p0而我们将p0赋值给了前面一个结点的next也就是对于节点1而言p0是他的地址前面一个结点的next也是他的地址。我们后面的操作就遗弃了p0其实p0就是等于前面节点的next如果需要随时可以恢复p0这里说明这一点主要是为了理解后面的循环初学的时候可能会不理解这个遍历的循环好像差一次但是为什么结果是对的。不理解循环次数的时候将每个节点的地址还原出来非常有用本文后面对于每个循环都有详细的解释这里先做一下说明。单链表的操作链表的创建和初始化对于单链表的一个节点包数据部分和存储的下一个节点的地址两部分所以我们构建一个结构体来定义这个节点对于头节点我们将数据部分置为0另外头节点创建时将next置为NULL。linklist list_create() { linklist H; H (linklist)malloc(sizeof(listnode)); if (H NULL) { printf(list create failed!\n); return NULL; } H-data -1; H-next NULL; return H; }要注意的点是检查链表是否建立函数的返回值是建立的链表的头节点地址。链表尾部插入元素有时候我们需要快速地建立一个链表就可以用到尾插。在链表尾部插入节点主要分为以下几步首先创建一个新节点可以用刚才的list_create()函数创建也可以按照相同的方法手动创建一个为了避免函数嵌套提高程序运行速度这里用手动的方法创建将新建节点的data中存入数据next置为NULL找到尾节点这一步容易忽视如果是在头节点之后插入默认头节点位置是知道的但是如果在节点3后面插入如图所示则需要先确定节点3的位置将新节点的地址赋给尾节点的next下面图中的p0表示第一个节点的地址后面的以此类推。int list_tail_insert(linklist H, data_t tail_data) { linklist L; linklist q; //检查链表是否建立 if (H NULL) { printf(list create failed!\n); return -1; } //创建新节点创建失败返回-1 if ((L(linklist)malloc(sizeof(listnode))) NULL) { printf(listnode create failed!\n); return -1; } //初始化节点内容 L-next NULL; L-data tail_data; //查找尾节点 q H; while (q-next ! NULL) { q q-next; } //更新前一个节点 q-next L; return 0; }这里有几点需要注意:if ((L(linklist)malloc(sizeof(listnode))) NULL) 这个判断语句中的(L(linklist)malloc(sizeof(listnode))要加上括号因为的优先级高于另外查找尾结点的循环是利用最后一个节点的next为空来找的。具体的循环实现在下面的链表打印中有详细的介绍。链表的遍历打印假若有以下链表对列表的遍历可以用一个循环来做对于节点的next域从头节点一直循环到尾节点知道next为NULL为止。这里需要注意的是每个节点创建的时候都是有自己的地址的也就是图中的p0.p1.p2.p3。但是我们将每个结点的地址都赋值给了前一个节点的next例如对于存储p1的节点它的地址既是p1也是H-next。搞清楚这一点非常重要搞清楚这个了才能理解为什么判断语句中的Temp-nextNULL可以不漏掉最后一个节点。对于链表打印来说循环的时候要以前一个域的next来循环也就是判断语句的判断条件是前一个节点的next这样做的效果就是前一个节点判断条件是不是最后一节点然后打印后面一个节点的data。也就是如下图所示,对前一个节点next来判断打印的是下一个节点的值。这个循环不仅对打印有用等会我们实现查找对应位置元素的值的时候同样也要用到这个方法。int list_show(linklist H) { //定义一个中间变量来循环检查链表是否建立 linklist Temp; Temp H; if (H NULL) { printf(listnode create failed!\n); return -1; } if (H-next NULL) { printf(list is empty!\n); return -1; } //循环打印 while (Temp - next ! NULL) { printf(%d , Temp-next-data); Temp Temp-next; } puts(); //输出换行 return 0; }用一个while循环即可实现这里需要注意对链表进行判断链表是否建立链表建立了是否只有一个头节点也就是链表为空//定义一个中间变量来循环检查链表是否建立 linklist Temp; Temp H; if (H NULL) { printf(listnode create failed!\n); return -1; } if (H-next NULL) { printf(list is empty!\n); return -1; }这两种情况都可能导致程序报dump错误。到这一步我们对前面写的代码做一下验证#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); return 0; }输入-1代表结束输入可以看到结果是正确的。链表查找按位置查找将第一个位置的元素设为data0 p0对于要查找的位置的元素只需要将Temp移动pos次移动后位置上的next即是pos位置的地址。例如要查找p2位置上的元素从i0到i2总共要移动两次。例如要查找p3位置上的元素从i0到i3总共要移动三次i0,i1,i2。在p1节点的next中即是p2的地址。这里也是和遍历打印一样的思路用前一个结点next来找下一个节点而不能用p2。这里我们定义头节点的位置为-1第一个节点的位置为0。linklist list_get_loc(linklist H, int pos) { //定义中间变量和循环次数 linklist Temp; int i 0; //初始化判断 if (H NULL) { printf(list create failed!\n); return NULL; } if (pos -1) { return H; } // Temp H; while (i pos1) { Temp Temp-next; if (Temp NULL) { printf(inalid position!\n); return NULL; } i; } return Temp; }这里需要注意对pos进行检查确保其合法。这里的做法是在主循环中加入以下代码来实现的。if (Temp NULL) { printf(inalid position!\n); return NULL; }也就是说如果循环到了最后一个位置的节点的next则代表位置不合法返回NULL。这个函数是返回对应节点的地址如果只想返回对应的data值修改函数的返回值类型即可。验证#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); linklist L list_get_loc(H, 2); printf(查找到的元素为%d \n, L-data); return 0; }查找第二个位置这里的位置是按照下标来的的元素可以看到结果是正确的。按元素查找查找相应元素在不在链表里只需要对链表遍历一下将链表里的每个值与查找值对比即可若找到则返回相应节点的地址。linklist list_get_elem(linklist H, int elem){ linklist Temp; Temp H; //初始化判断 if (H NULL) { printf(list create failed!\n); return NULL; } if (H-next NULL) { printf(list is empty!\n); return NULL; } //循环判断 while (Temp-next ! NULL) { if (Temp-data elem) { return Temp; } Temp Temp-next; } printf(element is not in list!\n); return NULL; }验证#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); //linklist L list_get_loc(H, 2); //printf(查找到的元素为%d \n, L-data); linklist N list_get_elem(H, 2); if (N ! NULL) { printf(查找到的元素%d \n, N-data); } return 0; }查找2在不在链表中在主函数中打印信息的时候要注意判断N是不是为NULL如果直接打印可能会遇到N为NULL的情况可能会报core dumped错误。链表指定位置插入元素在指定位置插入元素需要用到前面的按照位置查找节点先确定插入位置的前一个节点。例如要在下图中的p1位置插入节点主要分为以下几步建立新节点更新要插入的数据确认插入结点的前一个节点将前一个结点的next赋值给新建节点的next将新建节点的地址赋值给前一个结点的next这里赋值的时候要注意步骤先将p0-next赋值给p3-next再将p3赋值给p0-next。顺序不能反否则要是先将p3赋值给p0-next的话p0-next中存储的p1就丢失了。这里有一个诀窍赋值的时候先赋给空的这样不管怎么样不会丢失信息。从最后的结果来看的话插入操作实际上就是将前一个节点的next图中的p0-next赋值给后一个节点next将后一个节点的地址图中的p3赋值给前一个结点的next就是两次交换内容和后面的节点无关因此我们可以推导就算是在最后一个节点后插入也是有效的在仅有一个头节点的情况下插入也是有效的。int list_insert(linklist H, int pos, data_t insert_data) { //存储前一个节点和新节点 linklist P; linklist Temp; if (H NULL) { printf(listnode create failed!\n); return -1; } //定位前一个节点 P list_get_loc(H, pos - 1); if (P NULL) { printf(insert position is invalid!\n); return -1; } //建立新节点并更新内容 if ((Temp (linklist)malloc(sizeof(listnode))) NULL) { printf(node create failed!\n); return -1; } Temp-data insert_data; Temp-next P-next; P-next Temp; return 0; }#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); //linklist L list_get_loc(H, 2); //printf(查找到的元素为%d \n, L-data); //linklist N list_get_elem(H, 2); //if (N ! NULL) { // printf(查找到的元素%d \n, N-data); //} //list_insert(H, 0, 100); //list_show(H); //list_insert(H, 2, 100); //list_show(H); list_insert(H, 3, 100); list_show(H); return 0; }验证头插入位置0插入100验证中间插入位置2插入100验证尾插入位置3插入100链表指定位置删除节点链表删除节点和插入节点类似但是要注意找一个中间变量存储要删除的节点的地址然后将删除的节点所占空间释放删除节点可以分为以下几步找到删除节点的前驱定义中间变量存储p1更新前一个结点的next释放删除节点的内存int list_pos_delete(linklist H, int pos) { //存储前驱节点和删除节点 linklist Temp; linklist P; if (H NULL) { printf(list create failed!\n); return -1; } //注意判断删除节点的有效性 P list_get_loc(H, pos-1); if (P NULL) { printf(delete position is invalid!\n); return -1; } //最后一个节点单独处理 Temp list_get_loc(H, pos); if (Temp-next NULL) { P-next NULL; free(Temp); Temp NULL; return 0; } //更新链表 P-next Temp-next; //释放空间 free(Temp); Temp NULL; return 0; }这里要注意删除最后一个节点的方法需要单独写因为最后一个节点没有后继。我们直接将前一个节点的next置为NULL然会释放最后一个结点的空间即可。#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); //linklist L list_get_loc(H, 2); //printf(查找到的元素为%d \n, L-data); //linklist N list_get_elem(H, 2); //if (N ! NULL) { // printf(查找到的元素%d \n, N-data); //} //list_insert(H, 0, 100); //list_show(H); //list_insert(H, 2, 100); //list_show(H); //list_insert(H, 3, 100); //list_show(H); //list_pos_delete(H, 3); //list_show(H); //list_pos_delete(H, 0); //list_show(H); list_pos_delete(H, 2); list_show(H); return 0; }验证删除最后一个节点验证删除第一个节点验证中间节点删除链表释放空间链表删除和列表打印的思路相同让中间变量检查节点的next直到next为空但是要注意这里要删除头节点和尾节点。我们先定义一个中间变量来存储H的值然后让H每次循环之后都指向下一个节点然后free(Temp)也就是释放了H节点的空间注意这里的先后顺序不能反先存储H的值再移动在free。如果把free放在了前面的话就会导致H中的内容丢失找不到下一个节点了。这里要注意循环次数是从头节点地址开始一直到最后一个节点的地址也就是说每个节点都循环到了。循环次数看几遍图就能理解了。这里简单解释一下循环次数第一次循环是用的头结点的地址H然后将Temp的值置为H-next也就是p0然后释放掉了头节点的空间从后一次循环开始都可以看作用前一次的next作为判断条件来决定是否清空后一个结点所以每一个节点都能循环到。int list_free(linklist H) { //定义中间变量 linklist Temp; Temp H; if (H NULL) { printf(list not create !\n); return -1; } //循环释放空间 while (H ! NULL) { Temp H; H H-next; free(Temp); } return 0; }这里要注意在主函数中执行完这一段之后H的值仍为头结点的地址因为list_free(H)函数在释放链表的内存时并没有修改H的值。虽然在list_free(H)中释放了链表的所有节点但是H变量在main函数中的值没有被改变因为H作为参数传递给list_free函数时是按值传递的。H本身就是一个参数我们在函数中是借用H的形参来访问H指向的地址函数中的存储在栈上面的具体关于栈和堆的内容请看栈内存 vs 堆内存-CSDN博客。我们在主函数中验证一下#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); printf(释放前地址为%p \n, H); //linklist L list_get_loc(H, 2); //printf(查找到的元素为%d \n, L-data); //linklist N list_get_elem(H, 2); //if (N ! NULL) { // printf(查找到的元素%d \n, N-data); //} //list_insert(H, 0, 100); //list_show(H); //list_insert(H, 2, 100); //list_show(H); //list_insert(H, 3, 100); //list_show(H); //list_pos_delete(H, 3); //list_show(H); //list_pos_delete(H, 0); //list_show(H); //list_pos_delete(H, 2); //list_show(H); list_free(H); printf(释放后地址为%p \n, H); H NULL; return 0; }所以在主函数中清空列表后要手动将H置为NULL如果想用list_free()函数一步到位在函数里面就将H值修改为NULL可以修改函数的参数类型为list_free(linklist H),然后对函数做相应的修改即可这里就不在详细解释了。整体代码sqlink.h#ifndef __SQLINK_H__ #define __SQLINK_H__ typedef int data_t; typedef struct node{ data_t data; struct node* next; }listnode,* linklist; linklist list_create(); int list_tail_insert(linklist H, data_t tail_data); int list_show(linklist H); linklist list_get_loc(linklist H, int pos); linklist list_get_elem(linklist H, int elem); int list_insert(linklist H, int pos, data_t insert_data); int list_pos_delete(linklist H, int pos); int list_free(linklist H); #endifsqlink.c#include stdio.h #include sqlink.h #include stdlib.h linklist list_create() { linklist H; H (linklist)malloc(sizeof(listnode)); if (H NULL) { printf(list create failed!\n); return NULL; } H-data 0; H-next NULL; return H; } int list_tail_insert(linklist H, data_t tail_data) { linklist L; linklist q; //检查链表是否建立 if (H NULL) { printf(list create failed!\n); return -1; } //创建新节点创建失败返回-1 if ((L(linklist)malloc(sizeof(listnode))) NULL) { printf(listnode create failed!\n); return -1; } //初始化节点内容 L-next NULL; L-data tail_data; //查找尾节点 q H; while (q-next ! NULL) { q q-next; } //更新前一个节点 q-next L; return 0; } int list_show(linklist H) { //定义一个中间变量来循环检查链表是否建立 linklist Temp; Temp H; if (H NULL) { printf(listnode create failed!\n); return -1; } if (H-next NULL) { printf(list is empty!\n); return -1; } //循环打印 while (Temp - next ! NULL) { printf(%d , Temp-next-data); Temp Temp-next; } puts(); //输出换行 return 0; } linklist list_get_loc(linklist H, int pos) { //定义中间变量和循环次数 linklist Temp; int i 0; //初始化判断 if (H NULL) { printf(list create failed!\n); return NULL; } if (pos -1) { return H; } // Temp H; while (i pos1) { Temp Temp-next; if (Temp NULL) { printf(inalid position!\n); return NULL; } i; } return Temp; } linklist list_get_elem(linklist H, int elem){ linklist Temp; Temp H; //初始化判断 if (H NULL) { printf(list create failed!\n); return NULL; } if (H-next NULL) { printf(list is empty!\n); return NULL; } //循环判断 while (Temp-next ! NULL) { if (Temp-data elem) { return Temp; } Temp Temp-next; } printf(element is not in list!\n); return NULL; } int list_insert(linklist H, int pos, data_t insert_data) { //存储前一个节点和新节点 linklist P; linklist Temp; if (H NULL) { printf(listnode create failed!\n); return -1; } //定位前一个节点 P list_get_loc(H, pos - 1); if (P NULL) { printf(insert position is invalid!\n); return -1; } //建立新节点并更新内容 if ((Temp (linklist)malloc(sizeof(listnode))) NULL) { printf(node create failed!\n); return -1; } Temp-data insert_data; Temp-next P-next; P-next Temp; return 0; } int list_pos_delete(linklist H, int pos) { //存储前驱节点和删除节点 linklist Temp; linklist P; if (H NULL) { printf(list create failed!\n); return -1; } //注意判断删除节点的有效性 P list_get_loc(H, pos-1); if (P NULL) { printf(delete position is invalid!\n); return -1; } //最后一个节点单独处理 Temp list_get_loc(H, pos); if (Temp-next NULL) { P-next NULL; free(Temp); Temp NULL; return 0; } //更新链表 P-next Temp-next; //释放空间 free(Temp); Temp NULL; return 0; } int list_free(linklist H) { //定义中间变量 linklist Temp; Temp H; if (H NULL) { printf(list not create !\n); return -1; } //循环释放空间 while (H ! NULL) { Temp H; H H-next; free(Temp); } return 0; }test.c#include stdio.h #include sqlink.h int main() { linklist H; int value; H list_create(); if (H NULL) return -1; printf(input: ); while(1){ scanf_s(%d, value); if (value -1) break; list_tail_insert(H, value); printf(input: ); } list_show(H); printf(释放前地址为%p \n, H); //linklist L list_get_loc(H, 2); //printf(查找到的元素为%d \n, L-data); //linklist N list_get_elem(H, 2); //if (N ! NULL) { // printf(查找到的元素%d \n, N-data); //} //list_insert(H, 0, 100); //list_show(H); //list_insert(H, 2, 100); //list_show(H); //list_insert(H, 3, 100); //list_show(H); //list_pos_delete(H, 3); //list_show(H); //list_pos_delete(H, 0); //list_show(H); //list_pos_delete(H, 2); //list_show(H); list_free(H); printf(释放后地址为%p \n, H); H NULL; return 0; }