一.了解项目功能
在本次项目中我们的目标是实现一个单链表:
该单链表使用动态内存分配空间,可以用来存储任意数量的同类型数据.
单链表结点(Node)需要包含两个要素:数据域data,指针域next.
结点(Node)逻辑结构图示如下:
单链表提供的功能有:
- 单链表的初始化.
- 单链表的新节点创建.
- 单链表元素的尾插.
- 单链表元素的头插.
- 单链表的元素位置查找.
- 单链表的任意指定元素前插入.
- 单链表的任意指定位置后插入.
- 单链表的尾删.
- 单链表的头删.
- 单链表的任意指定元素删除.
- 单链表的指定元素后删除.
- 单链表打印.
- 单链表的元素位序查找.
- 单链表的销毁.
二.项目功能演示
要编写一个单链表项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下单链表程序运行时的样子：
单链表的C语言实现
三.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对单链表的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
1.实现单链表程序菜单
菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了，代码如下：
该部分功能实现代码如下:
//菜单 void SLTMenu() { printf("************************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.单链表尾插 ******\n"); printf("******2.单链表头插 ******\n"); printf("******3.单链表指定元素前插入 ******\n"); printf("******4.单链表指定元素后插入 ******\n"); printf("******5.单链表尾删 ******\n"); printf("******6.单链表头删 ******\n"); printf("******7.单链表指定元素删除 ******\n"); printf("******8.单链表指定元素后删除 ******\n"); printf("******9.单链表打印 ******\n"); printf("******10.单链表元素查找 ******\n"); printf("******11.单链表销毁 ******\n"); printf("******0.退出单链表程序 ******\n"); printf("************************************\n"); printf("请选择:>"); }
2.实现单链表程序功能可循环使用
由于我们要实现单链表的功能可以反复使用的逻辑，因此选择do...while的循环语句来实现这一部分的逻辑.
该部分功能实现代码如下:
// 导入SLTNode结构体的定义 int main() { SLTNode* plist=NULL; // 定义一个单链表的头指针，并初始化为NULL int swi = 0; // 创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do // 使用do...while实现单链表可循环使用 { SLTMenu(); // 调用SLTMenu函数，显示菜单 scanf("%d", &swi); // 从标准输入读取用户输入的选项 switch (swi) // 根据用户选择的选项执行相应的操作 { case 0: // 退出程序 SLTDestroy(&plist); // 销毁单链表 printf("您已退出程序:>\n"); // 释放链表内存 break; case 1: // 尾插数据 printf("请输入要尾插的数据:>"); SLTDataType pushback_data = 0; scanf("%d", &pushback_data); SLTPushBack(&plist, pushback_data); // 调用尾插函数 printf("已成功插入:>\n"); break; case 2: // 头插数据 printf("请输入要头插的数据:>"); SLTDataType pushfront_data = 0; scanf("%d", &pushfront_data); SLTPushFront(&plist, pushfront_data); // 调用头插函数 printf("已成功插入:>\n"); break; case 3: // 在指定位置前插入数据 printf("请输入要插入的数据:>"); SLTDataType insert_data = 0; scanf("%d", &insert_data); printf("请输入要插入的位置上的数据:>"); SLTDataType insert_posdata = 0; scanf("%d", &insert_posdata); SLTNode* insert_pos = SLTFind(plist, insert_posdata); // 查找插入位置 SLTInsert(&plist, insert_pos, insert_data); // 调用插入函数 printf("已成功在'%d'数据前插入'%d':>\n", insert_posdata, insert_data); break; case 4: //在指定位置后插入数据 printf("请输入要插入的数据:>"); SLTDataType insertafter_data = 0; scanf("%d", &insertafter_data); printf("请输入要插入的位置上的数据:>"); SLTDataType insertafter_posdata = 0; scanf("%d", &insertafter_posdata); SLTNode* insertafter_pos = SLTFind(plist, insertafter_posdata); if (insertafter_pos == NULL) { printf("该元素不存在,无法插入:<\n"); } else { SLTInsertAfter(insertafter_pos, insertafter_data); printf("已成功在'%d'数据后插入'%d':>\n", insertafter_posdata, insertafter_data); } break; case 5://单链表尾删 SLTPopBack(&plist); break; case 6://单链表头删 SLTPopFront(&plist); break; case 7: //单链表删除指定元素 printf("请输入要删除的数据:>"); SLTDataType erase_data = 0; scanf("%d", &erase_data); SLTNode* erase_pos = SLTFind(plist, erase_data); if (erase_pos == NULL) { printf("该元素不存在:<\n"); } else { SLTErase(&plist, erase_pos); printf("已成功删除:>\n"); } break; case 8: //单链表删除指定元素后元素 printf("请输入要删除数据的前一个数据:>"); SLTDataType eraseafter_data = 0; scanf("%d", &eraseafter_data); SLTNode* eraseafter_pos = SLTFind(plist, eraseafter_data); if (eraseafter_pos == NULL) { printf("该元素不存在:<\n"); } else { SLTEraseAfter(eraseafter_pos); printf("已成功删除:>\n"); } break; case 9: //单链表打印 printf("打印单链表:>\n"); SLTPrint(plist); break; case 10: //单链表元素位序查找 printf("请输入要查找的单链表元素:>"); SLTDataType find_data = 0; scanf("%d", &find_data); int find_pos = SLTFind_NO(plist, find_data); if (find_pos != -1) { printf("元素%d在单链表的第%d个\n", find_data, find_pos); } else { printf("没找到该元素:<\n"); } break; case 11: //单链表销毁 SLTDestroy(&plist); printf("单链表销毁成功:>\n"); break; default: // 输入错误 printf("输入错误,请重新输入\n"); break; } } while (swi); // 循环条件 return 0; }
3.创建单链表
创建单链表成员的结构体应该包括:存储数据的数据域data,以及存储下一个结点地址的指针域next.
图示如下:
因此我们创建SListNode结构体类型时应由一个数据成员类型及一个指向该结构体的结构体指针组成.
这里的第一行使用的typedef类定义的作用是方便我们后续在使用单链表时对存储的数据类型做更改,比如后续我们的链表不想存储int类型数据了,就可以很方便的在这里对单链表数据域的存储数据类型做更改.比如改成char类型,或者double类型,甚至改成任意自己构造的结构类型.
在之前的实战项目通讯录中,我们就创建过类似的自定义结构体,如下图:
综上,该部分代码如下:
typedef int SLTDataType; typedef struct SListNode //对SlistNode类型进行重命名,方便后续操作 { SLTDataType data; struct SListNode* next; //typedef在7行之后才起作用. }SLTNode;
4.初始化单链表
初始化单链表部分的逻辑与之前顺序表以及通讯录不同.
在初始化顺序表部分,我们是实打实申请了一块空间以备后续使用,因此需要对这块空间进行初始化.
而在单链表部分,我们是需要插入数据时才会创建结点,因此结点空间在开辟时就会被使用,这样也就不需要初始化空间这个动作了.
因此,在初始化单链表部分,我们只需要创建一个头指针,将它初始化为NULL或让它指向头结点即可:
空链表:头指针无头结点示意图:
空链表:头指针有头结点示意图:
在本次项目中,我们采用的是无头结点指针链表,因此在初始化的时候只需要开辟一个头指针并将它置为NULL即可.
该部分功能实现代码如下:
SLTNode* plist=NULL;
5.单链表的新节点创建
因为后续我们单链表尾插,头插等插入操作时都需要先创建一个新结点,为了使代码的利用效率变高,我们不如将创建新节点这一操作封装成一个函数,后续当需要创建新节点时,直接调用该函数即可.
函数的参数需要接收新结点的数据域,至于新结点的指针域,在我们不清楚新结点的用途时,直接将其置为NULL即可.
该部分功能实现代码如下:
//开辟新结点 SLTNode* BuySLTNode(SLTDataType x) //定义函数BuySLTNode，参数为SLTDataType类型的变量x { //使用malloc开辟新结点 //声明一个SLTNode类型的指针newnode，并使用malloc动态分配内存空间，大小为SLTNode结构体的大小 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail::"); //如果newnode为空，输出"malloc fail::",提示malloc开辟空间出错 return NULL; //并返回一个空指针 } //将newnode指向的结点的data成员赋值为x newnode->data = x; //将newnode指向的结点的next成员赋值为NULL newnode->next = NULL; //返回newnode结点指针 return newnode; }
6.单链表元素的尾插
在单链表尾插部分,我们要特别注意理解:函数形参的改变不影响实参.
因此在函数内想改变SLTNode类型的实参需要传SLTNode*的指针,
而在函数内想改变的是尾结点的指针域SLTNode*类型的实参需要传SLTNode**的二级指针.
尾插的逻辑为:
先判断单链表是不是空链表,
如果是,直接让头指针指向newnode即可.
如果不是,则需要先找尾,再将newnode的地址链接到尾结点的指针域.
尾插逻辑示意图:
该部分功能实现代码如下:
//链表尾插 //形参的改变,不影响实参 void SLTPushBack(SLTNode** pphead, SLTDataType x)//不能断言,链表为空也可插入数据 { assert(pphead);//因为pphead是plist的地址,所以绝对不是空的,但是,防止有传参时传错的现象,所以断言一下 //创建新节点 SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //链接 tail->next = newnode; } }
7.单链表元素的头插
头插我们同样分为两种情况来看:
一种是当单链表为空时,另一种是当单链表不为空时.
通过观察分析我们可以发现,这两种情况下,单链表的插入逻辑都是相同的:
即,先让newnode的指针域指向原来头指针pphead指向的内容(结点或NULL),然后让头指针pphead指向newnode即可.
头插逻辑示意图:
void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //创建新结点 SLTNode* newnode = BuySLTNode(x); //先将newnode的next指向首结点 newnode->next = *pphead; //再将pphead指向newnode *pphead = newnode; }
8.单链表的元素位置查找
因为后续我们要使用的单链表按位插入和按位删除都需要知道用户传入的链表元素在链表中的位置在哪,因此我们把查找链表元素位置的操作封装成一个单独的函数,后续需要查找某一链表元素的位置直接调用这个函数就行.
注意,查找只需要遍历链表,而不需要改变链表内容,因此我们传给函数链表的一级头指针即可,函数的参数还应该接收待查找的结点的数据域,以便我们在遍历链表的过程中能够找到它.
函数的返回值是链表结点指针型(SLTNode*),这样可以方便我们在找到要查找的指针后直接对齐进行相关操作,而不需要再在函数外再遍历一遍链表了.
该部分功能实现代码如下:
//单链表的元素位置查找 // 定义函数SLTFind，参数为SLTNode类型的指针phead和SLTDataType类型的变量x SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { // 声明一个SLTNode类型的指针cur，初始化为phead SLTNode* cur = phead; // 当cur不为空时进入循环 while (cur) { // 如果cur指向的结点的data成员等于x if (cur->data == x) { // 返回cur指针 return cur; } // 将cur指向下一个结点 cur = cur->next; } // 循环结束后，如果未找到匹配的结点，返回空指针 return NULL; }
9.单链表的任意指定元素前插入
在指定元素前插入函数中我们需要三个参数,一个是头指针的地址,一个是指定元素的地址,一个是新结点的数据域的数据值.
在插入时我们会遇到两种情况:
一种是pos指针指向首结点,这种情况下函数的插入逻辑是和头插相同的,因此我们可以直接调用头插函数来实现该操作.
示意图:
还有一种情况是当pos不指向首结点时,我们的链接逻辑是:
- 先让newnode的指针域链接到pos指针指向的位置.
- 再找到pos前一个结点的指针域,将其指向newnode.
注意,当传入的pos指针为NULL时,不能认为此时相当于单链表的尾插执行尾插逻辑.
因为这里pos为空的原因还可能是因为SLTFind函数根本没有在单链表中找到指定插入元素的位置.因此传回了一个代表没有找到该元素的NULL指针.
所以如果遇到pos为NULL的情况我们直接断言报错即可,不需要加入判断的操作为别的函数传入的错误指针而买单了.
该部分功能实现代码如下:
//pos之前插入 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); //pos为NULL不一定是尾插!并且我们不要在函数内去判断pos为NULL是不是尾插 //每个函数只要完成自己分内的工作即可,不需要为别人可能出现的错误买单! if (pos == *pphead)//当pos位置与头指针相等时,相当于头插 { SLTPushFront(pphead, x); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //创建新节点 SLTNode* newnode = BuySLTNode(x); //链接 prev->next = newnode; newnode->next = pos; } }
10.单链表的任意指定位置后插入.
在pos位置后插入的逻辑比在pos位置前插入简单,我们甚至不需要链表头指针遍历链表,只需要pos位置的指针就可以访问pos结点的指针域然后修改其相关值了.
该部分操作示意图:
在这里我们的链接逻辑同样是先让newnode连接上pos结点的指针域指向的内容(下一结点/NULL),再将pos结点的指针域指向newnode即可.
该部分功能实现代码如下:
//pos后面插入 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos);//pos为NULL,无法进行插入操作,因此直接让assert报错 SLTNode* newnode = BuySLTNode(x); //先让newnode连上后面,再让前面连上newnode.不然就断了 newnode->next = pos->next; pos->next = newnode; }
11.单链表的尾删
尾删分为三种情况,对这三种情况我们要分别处理:
如果不判断单链表只有一个结点时的情况二，按照有多个节点的逻辑操作，会导致在只有一个结点的情况下出现空指针访问的问题。
在这种情况下，如果直接执行 (*pphead)->next，会出现空指针访问，导致程序崩溃。
因此，在进行尾删操作之前，需要先判断单链表是否只有一个结点，如果只有一个结点，则需要特殊处理，而不是按照有多个节点的逻辑操作。
其中情况三是我们需要特别注意的,在找到尾后,我们要使用一个指针记录下尾结点的前一个结点的地址,因为在释放尾结点后,我们还需要将它的前一个结点的指针域置为空.
该部分功能实现代码如下:
void SLTPopBack(SLTNode** pphead) { assert(pphead);//如果pphead为空,头指针不存在,则链表是不存在的 //如果*pphead为空,代表头指针存在,但首结点不存在,链表没法继续删除 if (*pphead == NULL) { printf("链表为空,无法进行尾删:<\n"); return; } //只有一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//多个结点 { //找尾 SLTNode* tail = *pphead; SLTNode* prev = NULL; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } printf("已成功尾删数据:>\n"); }
12.单链表的头删
头删也有三种情况,我们分别画图看一下:
通过对三种情况的分析,我们发现情况二和情况三可以归为一种情况处理,并且在头删部分不会出现和尾删一样的对空指针的解引用操作,所以我们只需要对情况一作单独处理就行.
该部分功能实现代码如下:
// 从链表头部删除结点 // 定义函数SLTPopFront，参数为指向指针的指针pphead void SLTPopFront(SLTNode** pphead) { assert(pphead); // 断言pphead不为空 if (*pphead == NULL) // 如果链表为空 { printf("链表为空,无法进行头删:<\n");// 打印提示信息 return; // 返回 } SLTNode* first = *pphead; // 定义指针first指向头结点 *pphead = first->next; // 将头结点指向下一个结点 free(first); // 释放first指向的内存 first= NULL; // 将first置为空 printf("已成功头删:>\n"); // 打印成功提示信息 }
13.单链表的任意指定元素删除
既然要删除单链表中的某一元素,那么前提是这个元素要存在于单链表中,因此pos不能为NULL.
当pos指针指向的位置和头指针指向的位置相同时,则相当于头删,执行头删逻辑即可.
函数逻辑示意图:
该部分功能实现代码如下:
// 从链表中删除指定位置的结点 // 定义函数SLTErase，参数为指向指针的指针pphead和要删除的结点位置pos void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); // 断言pphead不为空 assert(pos); // 断言pos不为空 if (pphead == pos) // 如果要删除的位置是头结点 { SLTPopFront(pphead); // 调用SLTPopFront删除头结点 } else { // 找到pos的前一个位置 SLTNode prev = *pphead; // 定义指针prev指向头结点 while (prev->next != pos) // 当prev的下一个结点不等于pos时 { prev = prev->next; // prev指向下一个结点 } prev->next = pos->next; // 将prev的下一个结点指向pos的下一个结点 free(pos); // 释放pos指向的内存 } }
14.单链表的指定元素后删除
我们要删除pos结点后一个结点,只需要一个参数,即pos的位置.
因为删除pos结点后的结点,需要更改的指针域就是pos的指针域,而pos的指针域我们拿pos指针就可以访问,所以也就不需要链表的头指针来遍历链表了.
该部分功能实现代码如下:
// 定义函数SLTEraseAfter，参数为SLTNode类型的指针pos，用于删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { // 断言pos不为空，确保pos指向的节点存在 assert(pos); // 断言pos的下一个节点不为空，确保pos之后还有节点 assert(pos->next); // 声明一个SLTNode类型的指针del，指向pos的下一个节点 SLTNode* del = pos->next; // 将pos的next指针指向del的下一个节点 pos->next = del->next; // 释放del指向的节点的内存 free(del); // 将del指针置为NULL，防止出现悬空指针 del = NULL; }
15.单链表打印
单链表的打印逻辑很简单,顺着头指针向后循环遍历打印整个链表结点的数据域即可,当结点的指针域为空时,则代表已经遍历打印完链表的所有元素,这时跳出循环即可.
该部分功能实现代码如下:
// 打印链表 void SLTPrint(SLTNode* phead) // 定义函数SLTPrint，参数为指向链表头结点的指针phead { //不用断言phead,因为phead为空不代表链表为空 SLTNode* cur = phead; // 定义指针cur指向phead while (cur != NULL) // 当cur不为空时 { printf("%d->", cur->data); // 打印当前结点的数据 cur = cur->next; //使cur指向下一个结点 } printf("NULL\n"); // 打印NULL表示链表结束 }
16.单链表的元素位序查找
元素位序的查找和元素位置的查找的区别是:
- 位序查找需要返回元素在链表中的第几个,因此返回值是int,而位置查找需要返回元素的地址,因此返回值是结构体指针(SLTNode*).
- 位序查找在遍历链表查找时需要一个计数器来记录链表当前遍历到第几个元素,而位置查找则不需要计数器来记录,只需要在找到时返回该元素的地址即可.
该部分功能实现代码如下:
// 根据值查找结点位序 int SLTFind_NO(SLTNode* phead, SLTDataType x) // 定义函数SLTFind_NO，参数为指向链表头结点的指针phead和要查找的值x { SLTNode* cur = phead; // 定义指针cur指向phead int count = 1; // 初始化计数器count为1 while (cur) // 当cur不为空时 { if (cur->data == x) // 如果当前结点的数据等于x { return count; // 返回当前位置 } count++; // 计数器加1 cur = cur->next; // 移动到下一个结点 } return -1; // 如果未找到，返回-1 }
17.单链表的销毁
当我们使用完单链表想要退出程序时,就应该将之前动态开辟的内存释放掉,还给操作系统.即销毁单链表操作.
我们使用free()函数将前面开辟的结点的内存逐一释放,释放完将头指针置为空即可.
该部分功能实现代码如下:
// 单链表的销毁 void SLTDestroy(SLTNode** pphead) // 定义函数SLTDestroy，参数为指向指针的指针pphead { assert(pphead); // 断言pphead不为空 SLTNode* cur = *pphead; // 定义指针cur指向pphead所指向的地址 while (cur != NULL) // 当cur不为空时 { SLTNode* prev = cur->next; // 定义指针prev指向cur的下一个结点 free(cur); // 释放cur指向的内存 cur = prev; // cur指向下一个结点 } *pphead = NULL; // 将pphead指向的地址置为空 }
四.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件
#include"SList.h" int main() { SLTNode* plist=NULL; int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do //使用do...while实现 { SLTMenu(); scanf("%d", &swi); switch (swi) { case 0: SLTDestroy(&plist); printf("您已退出程序:>\n"); // 释放链表内存 break; case 1: printf("请输入要尾插的数据:>"); SLTDataType pushback_data = 0; scanf("%d", &pushback_data); SLTPushBack(&plist, pushback_data); printf("已成功插入:>\n"); break; case 2: printf("请输入要头插的数据:>"); SLTDataType pushfront_data = 0; scanf("%d", &pushfront_data); SLTPushFront(&plist, pushfront_data); printf("已成功插入:>\n"); break; case 3: printf("请输入要插入的数据:>"); SLTDataType insert_data = 0; scanf("%d", &insert_data); printf("请输入要插入的位置上的数据:>"); SLTDataType insert_posdata = 0; scanf("%d", &insert_posdata); SLTNode* insert_pos = SLTFind(plist, insert_posdata); SLTInsert(&plist, insert_pos, insert_data); printf("已成功在'%d'数据前插入'%d':>\n", insert_posdata, insert_data); break; case 4: printf("请输入要插入的数据:>"); SLTDataType insertafter_data = 0; scanf("%d", &insertafter_data); printf("请输入要插入的位置上的数据:>"); SLTDataType insertafter_posdata = 0; scanf("%d", &insertafter_posdata); SLTNode* insertafter_pos = SLTFind(plist, insertafter_posdata); if (insertafter_pos == NULL) { printf("该元素不存在,无法插入:<\n"); } else { SLTInsertAfter(insertafter_pos, insertafter_data); printf("已成功在'%d'数据后插入'%d':>\n", insertafter_posdata, insertafter_data); } break; case 5: SLTPopBack(&plist); break; case 6: SLTPopFront(&plist); break; case 7: printf("请输入要删除的数据:>"); SLTDataType erase_data = 0; scanf("%d", &erase_data); SLTNode* erase_pos = SLTFind(plist, erase_data); if (erase_pos == NULL) { printf("该元素不存在:<\n"); } else { SLTErase(&plist, erase_pos); printf("已成功删除:>\n"); } break; case 8: printf("请输入要删除数据的前一个数据:>"); SLTDataType eraseafter_data = 0; scanf("%d", &eraseafter_data); SLTNode* eraseafter_pos = SLTFind(plist, eraseafter_data); if (eraseafter_pos == NULL) { printf("该元素不存在:<\n"); } else { SLTEraseAfter(eraseafter_pos); printf("已成功删除:>\n"); } break; case 9: printf("打印单链表:>\n"); SLTPrint(plist); break; case 10: printf("请输入要查找的单链表元素:>"); SLTDataType find_data = 0; scanf("%d", &find_data); int find_pos = SLTFind_NO(plist, find_data); if (find_pos != -1) { printf("元素%d在单链表的第%d个\n", find_data, find_pos); } else { printf("没找到该元素:<\n"); } break; case 11: SLTDestroy(&plist); printf("单链表销毁成功:>\n"); break; default: printf("输入错误,请重新输入\n"); break; } } while (swi); return 0; }
SList.h文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdio.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next;//typedef在15行之后才起作用. }SLTNode; void SLTMenu(); void SLTPrint(SLTNode* phead);//不改变指针,就不传二级 void SLTPushBack(SLTNode** pphead, SLTDataType x);//要改变指针,那就传二级 void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead);//找假尾,释放真尾会导致他野指针 void SLTPopFront(SLTNode** pphead); //单链表查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //pos之前插入 void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x); //pos位置删除 void SLTErase(SLTNode** pphead,SLTNode* pos); //pos后面插入 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //pos位置后面删除 void SLTEraseAfter(SLTNode* pos); //单链表查找位序 int SLTFind_NO(SLTNode* phead, SLTDataType x); //单链表的销毁 void SLTDestroy(SLTNode** pphead);
SList.c文件
#include"SList.h" //菜单 void SLTMenu() { printf("************************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.单链表尾插 ******\n"); printf("******2.单链表头插 ******\n"); printf("******3.单链表指定元素前插入 ******\n"); printf("******4.单链表指定元素后插入 ******\n"); printf("******5.单链表尾删 ******\n"); printf("******6.单链表头删 ******\n"); printf("******7.单链表指定元素删除 ******\n"); printf("******8.单链表指定元素后删除 ******\n"); printf("******9.单链表打印 ******\n"); printf("******10.单链表元素查找 ******\n"); printf("******11.单链表销毁 ******\n"); printf("******0.退出单链表程序 ******\n"); printf("************************************\n"); printf("请选择:>"); } SLTNode* BuySLTNode(SLTDataType x) { //开辟新结点 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail::"); return NULL; } //赋值 newnode->data = x; newnode->next = NULL; return newnode; } //打印链表 void SLTPrint(SLTNode* phead)//不用断言phead,因为phead为空不代表链表为空 { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; //使cur指向下一个结点 } printf("NULL\n"); } //链表尾插 //形参的改变,不影响实参 void SLTPushBack(SLTNode** pphead, SLTDataType x)//不能断言,链表为空可插 { assert(pphead);//因为pphead是plist的地址,所以绝对不是空的,但是,防止有传参时传错的现象,所以断言一下 //创建新节点 SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //链接 tail->next = newnode; } } //单链表头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //创建新结点 SLTNode* newnode = BuySLTNode(x); //先将newnode的next指向首结点 newnode->next = *pphead; //再将phead指向newnode *pphead = newnode; } //单链表尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead); //如果链表为空,温柔检查一下,暴力检查assert if (*pphead == NULL) { printf("链表为空,无法进行尾删:<\n"); return; } //只有一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//多个结点 { //找尾 SLTNode* tail = *pphead; SLTNode* prev = NULL; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } printf("已成功尾删数据:>\n"); } //单链表头删 void SLTPopFront(SLTNode** pphead) { assert(pphead); if (*pphead == NULL) { printf("链表为空,无法进行头删:<\n"); return; } SLTNode* first = *pphead; *pphead = first->next; free(first); first= NULL; printf("已成功头删:>\n"); } //单链表查找元素地址 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //单链表查找位序 int SLTFind_NO(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; int count = 1; while (cur) { if (cur->data == x) { return count; } count++; cur = cur->next; } return -1; } //pos之前插入 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); //pos为NULL不一定是尾插!别为别人的错误买单! if (pos == *pphead)//相当于头插 { SLTPushFront(pphead, x); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //创建新节点 SLTNode* newnode = BuySLTNode(x); //链接 prev->next = newnode; newnode->next = pos; } } //pos位置删除 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SLTPopFront(pphead); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } } //pos后面插入 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); //先让newnode连上后面,再让前面连上newnode.不然就断了 newnode->next = pos->next; pos->next = newnode; } //pos位置后面删除 void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } //单链表的销毁 void SLTDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur != NULL) { SLTNode* prev = cur->next; free(cur); cur = prev; } *pphead = NULL; }
结语
希望这篇顺序表的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
数据结构线性表篇思维导图:
