有谁知道知乎网站是谁做的,以春天为主题的网站建设资源,怎么用dw做可上传文件的网站,wordpress英文模板下载地址#x1f984;个人主页:小米里的大麦-CSDN博客 #x1f38f;所属专栏:C语言数据结构_小米里的大麦的博客-CSDN博客 #x1f381;代码托管:黄灿灿/数据结构 (gitee.com) ⚙️操作环境:Visual Studio 2022 目录
一、前言
二、单链表的概念
1. 单链表的特点
2. 单链表的基本… 个人主页:小米里的大麦-CSDN博客 所属专栏:C语言数据结构_小米里的大麦的博客-CSDN博客 代码托管:黄灿灿/数据结构 (gitee.com) ⚙️操作环境:Visual Studio 2022 目录
一、前言
二、单链表的概念
1. 单链表的特点
2. 单链表的基本操作
3. 画图思想
三、单链表分步详解
1. 函数声明
2. 打印函数
3. 尾插函数很重要
4. 头插函数
5. 尾删函数
6. 头删函数
7. 查找函数
8. 在指定节点 pos 之前插入一个新节点
9. 删除指定节点 pos
10. 在指定节点 pos 之后插入一个新节点
11. 删除指定节点 pos 之后的节点
12. 链表的销毁
13. 测试用例
四、源文件展示链表 · 07c4d36 · 黄灿灿/数据结构 - Gitee.com
头文件SList.h
函数部分源文件SList.c
测试部分文件同上text.c
总结
希望这篇文章能帮助读者你更好地理解单链表的概念和操作。如果您有任何疑问或建议请随时留言交流。
共勉 一、前言
在计算机科学中链表是一种常见的数据结构它通过一系列的节点来存储数据元素其中每个节点包含一个数据字段和一个指向链表中下一个节点的引用。单链表是最简单的链表形式本文将深入探讨单链表的基本概念、实现步骤及其易错点帮助大家以最快速度学会单链表
本文从0到尾基本涵盖了所有经典问题所有的资料全都有 (单词注释、链接直达)全部都准备好了不用您再东找找、四看看了接下来我们会先分步讲单独的函数不想细看的可以直接跳转至文尾的 “源文件” 处 一点要求如下 先要对单链表有概念常识清楚单链表的链表形式。仔细思考示例中的实现方法尤其是能够理解错误示例的错误点这是第一遍凭借画图和逻辑思考尽量不要有所参考自行尝试手撕代码进行单链表的实现这是第二遍 二、单链表的概念 单链表由一系列节点组成每个节点包含两个部分 数据域用于存储实际的数据。指针域存储指向链表中下一个节点的地址。 链表的第一个节点通常被称为“头节点”或“首节点”而最后一个节点的指针域通常为空NULL表明链表的结束。 如果你不理解可以点击链接跳转至 “单链表动画” 五分钟左右清楚理解其链表形式后再回来【C语言】发明链表的人真是太有才啦_哔哩哔哩_bilibili 或者【动画演示】链表详解及其底层机制 C语言_哔哩哔哩_bilibili 1. 单链表的特点
动态分配与数组不同链表的大小可以在运行时改变因此可以有效地管理内存资源。插入和删除操作简便不需要像数组那样移动大量元素只需修改相关节点的指针即可完成插入或删除操作。顺序访问由于链表中的元素不是连续存储的因此只能通过遍历的方式访问元素不能像数组那样随机访问。
2. 单链表的基本操作
单链表的基本操作包括
初始化取值按值查找插入删除
3. 画图思想
数据结构最核心的思想是画图这里给出几个样例可自行导入画图板进行演示 一个个人演示示例画图板很实用!: 好了到此你应该对单链表有了一定的认识难的是如何实现下面我们开始分步讲解 (注意这里的示例为8种链表中经典的无头单项非循环链表) 选择原因无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 三、单链表分步详解
1. 函数声明
要实现单链表首先就要有节点我们先创建节点构建我们的数据域和指针域这里的数据域用最简单的整形代替学会进阶可增加/丰富数据域的内容使其可以存储更多更丰富发内容
//Single-linked lists单链表(SList)
//list:列表#includestdio.h
#includestdlib.h
#includeassert.h//node:节点
//next:下一个
//data数据
//Singly linked list nodes:单链表节点(SLLN)typedef struct SListnode
{int data;struct SListnode* next;
}SLLN;
//等价于
//struct SListnode
//{
// int data;
// struct SListnode* next;
//};
//typedef struct SListnode SLLN; 此处顺便将所有函数声明给出可看可不看 看要注意函数命名函数较多切记不要混淆(说实话这里的函数名不那么恰当可自行更改)不看只要记得有此处的函数声明即可 //找节点
SLLN* lookup(int x);// 动态申请一个节点:Dynamically apply for a node
//SLLN* Da_node(int x);// 单链表打印
void SList_print(SLLN* phead);// 单链表尾插 Tail plugging:尾插
//void SList_tplug(SLLN* phead, int x);//错
void SList_tplug(SLLN** pphead, int x);//对// 单链表的头插 Header:头插
void SList_header(SLLN** pphead, int x);// 单链表的尾删 Tail deletion:尾删
void SList_tdel(SLLN** pphead);// 单链表头删 Header deleted:头删
void SList_hdel(SLLN** pphead);// 单链表查找 Find:查找
SLLN* SList_find(SLLN* phead, int x);
//void SList_print_matching(SLLN* phead, int x);//在指定节点 pos 之前插入一个新节点:Inserts a new node before specifying it
void SList_before(SLLN** pphead, SLLN* pos, int x);//删除指定节点 pos :Deletes the specified node
void SList_del(SLLN** pphead, SLLN* pos);//后after
//在指定节点 pos 之后插入一个新节点:Inserts a new node after the specified node
void SList_after(SLLN* pos, int x);//删除指定节点 pos 之后的节点:Deletes a node after the specified node
void SList_del2(SLLN* pos);//链表销毁Destroyed销毁
void Destroyed(SLLN* phead);
//void Destroyed(SLLN** pphead);或者
函数部分注意引用部分
#define _CRT_SECURE_NO_WARNINGS 1
//Single-linked lists单链表
//Singly linked list nodes:单链表节点(SLLN)
//list:列表
//head:头
//tail:尾尾巴
//temp:临时的#include SList.h
2. 打印函数
好了下面开始我们的第一个函数——打印函数 提醒一下空链表可以打印空链表是指没有数据节点的链表也就是说除了可能存在的头节点外链表中没有任何数据节点。在空链表中通常会有一个头节点有时也称为哨兵节点这个节点不包含任何数据它的作用主要是方便对链表进行操作例如插入和删除等。 空链表本身没有数据节点。是否包含头节点取决于具体的实现方式。空链表的特征是链表的最后一个节点如果有的话的next指针指向NULL。 // 单链表打印
//可以使用二级指针但没必要要改变实参用二级不改变用一级可以加 const不建议会带来一些不必要的麻烦
void SList_print(SLLN* phead)
{//此处切不可断言assert空链表可以打印此处使用断言会终止程序//(单链表为空此处指针phead为空。顺序表此处需断言assert顺序表是一个结构体结构体里有一个指针指向一块数组空间结构体指针为空程序就走不了了)SLLN* temp phead;//注意切不可写成 while (temp-next ! NULL),最后一个数据无法打印//正确写法//while (temp ! NULL)while (temp){printf(%d-, temp-data);temp temp-next;//temp/temp,注意切不可加加节点地址不能保证连续}printf(NULL\n);
}
3. 尾插函数很重要
下面是最为复杂的尾插函数注意深刻体会注释部分明白注释中错误部分非常非常重要对应的行数部分注释只有在 “源文件” 处才对应得上
//提取一个公共函数找一个新节点,lookup查找
//这个函数全部内容来自void SList_tplug(SLLN** pphead, int x)函数的 122-135 行
SLLN* lookup(int x)
{SLLN* newnode (SLLN*)malloc(sizeof(SLLN)); // newnode: 新节点if (newnode NULL) // 检查{perror(malloc fail);return NULL; // 返回 NULL 表示失败}// 新节点初始化为空newnode-data x;newnode-next NULL;return newnode;
}虽然是错但要从中吸取教训总结结论着重看和理解注释部分单链表尾插 Tail plugging:尾插
//void SList_tplug(SLLN* phead, int x)
//{
// //此处切不可断言assert链表为空指针phead为空此处使用断言会终止程序
//
// SLLN* newnode (SLLN*)malloc(sizeof(SLLN));//newnode:新节点
// if (newnode NULL)//检查
// {
// perror(malloc fail);
// return;
// }
//
// //新节点初始化为空
// newnode-data x;
// newnode-next NULL;
//
// if (phead NULL)
// {
// phead newnode;
// }
// else
// {
// //找尾尾插的本质原尾节点中要存储新的尾节点地址
// //正确写法(相对于此情况但此情况函数部分有错)
// SLLN* tail phead;//tail:尾
// while (tail-next ! NULL)
// {
// tail tail-next;
// }
// tail-next newnode;//精华所在
//
// //错误写法
// //SLLN* tail phead;//tail:尾
// //while (tail ! NULL)
// //{
// // tail tail-next;
// //}
// //tail newnode;
// //原因函数栈帧知识tail是局部变量之后会销毁
// }
//}//整个函数错误原因
请对比void temp(int *p) void temp(int *ptr)
{ {*p 1; ptr (int*)malloc(sizeof(int));
} }
int main() 和 int main()
{ 和 {int x 0; 和 int* pxNULL;temp(x); temp(px);return 0; return 0;
} }改变的是int使用的是int的指针改变int*要使用int*的地址int**指针
所以要改变*ptr使用的是*ptr的指针
即
int main()
{int* px NULL;Func(px);free(px);return 0;
}
正确的函数写法
void SList_tplug(SLLN** pphead, int x)
{//为了使用 35 行的 lookup 函数将此 122 到 135 行注释掉改成 137 行的 SLLN* newnode lookup(x);此处切不可断言assert链表为空指针phead为空此处使用断言会终止程序//SLLN* newnode (SLLN*)malloc(sizeof(SLLN));//newnode:新节点//if (newnode NULL)//检查//{// perror(malloc fail);// return;//}新节点初始化为空//newnode-data x;//newnode-next NULL;SLLN* newnode lookup(x);if (*pphead NULL){*pphead newnode;}else{//找尾尾插的本质原尾节点中要存储新的尾节点地址SLLN* tail *pphead;//tail:尾while (tail-next ! NULL){tail tail-next;}tail-next newnode;//精华所在改变指针改变结构体成员用一级指针函数栈帧的知识要深挖}
}
4. 头插函数
比较简单注意调用关系层次关系要理解二级指针动画演示链表的头插法数据结构与算法完整代码动画考研408 期末考试数据结构_哔哩哔哩_bilibili
// 单链表的头插 Header:头插
void SList_header(SLLN** pphead, int x)
{assert(pphead);SLLN* newnode lookup(x);newnode-next *pphead;*pphead newnode;
}
5. 尾删函数
注意链表本身的顺序和节点规律这里唯一重要的是要清晰当前节点和旁边的两个节点关系后面很多地方也是一样动画演示链表的尾插法 完整代码动画版数据结构与算法。附在线数据结构交互式工具_哔哩哔哩_bilibili
// 单链表的尾删 Tail deletion:尾删
void SList_tdel(SLLN** pphead)
{错误写法//SLLN* tail *pphead;//while (tail-next ! NULL)//{// tail tail-next;//}//free(tail);//tail NULL;//错误原因此行tail是局部变量没有把前一个next节点置空前一个节点是一个结构体要将前一个结构体节点置空需要一个结构体的指针//检查二选一//暴力的检查assert(pphead);assert(*pphead);//或者assert(*pphead!NULL);//温柔的检查//if (*pphead NULL)//{// return;//}if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//正确写法1SLLN* temp NULL;SLLN* tail *pphead;while (tail-next ! NULL){temp tail;tail tail-next;}free(tail);tail NULL;temp-next NULL;//正确写法2//SLLN* tail *pphead;//while (tail-next-next ! NULL)//{//tail tail-next;//}//free(tail-next);//tail-next NULL;}
}
6. 头删函数
比较简单不进行过多赘述。
// 单链表头删 Header deleted:头删
void SList_hdel(SLLN** pphead)
{//检查二选一//暴力的检查assert(pphead);assert(*pphead);//或者assert(*pphead!NULL);//温柔的检查//if (*pphead NULL)//{// return;//}SLLN* first *pphead;//first:第一*pphead first-next;free(first);first NULL;
}
7. 查找函数
这里本身的查找函数人是不好观察的所以又提供了注释部分的查找打印函数这里需要理解的是更新/迭代的逻辑
// 单链表查找 Find:查找
SLLN* SList_find(SLLN* phead, int x)
{SLLN* temp phead;while (temp){if (temp-data x){return temp;}temp temp-next;//更新temp}return NULL;
}
//或者使用查找打印函数
//void SList_print_matching(SLLN* phead, int x)
//{
// SLLN* temp phead;
// int found 0; // 标记是否找到了匹配的节点
//
// while (temp)
// {
// if (temp-data x)
// {
// printf(%d , temp-data); // 打印匹配的节点数据
// found 1; // 标记找到了匹配的节点
// }
// temp temp-next;
// }
//
// if (!found)
// {
// printf(No matching elements found.\n); // 如果没有找到匹配的节点
// }
// else
// {
// printf(\n); // 打印换行符使输出更加清晰
// }
//}
8. 在指定节点 pos 之前插入一个新节点
注意分情况因为有一种情况是头插可以 “偷懒” 。
//在指定节点 pos 之前插入一个新节点:Inserts a new node before specifying it
void SList_before(SLLN** pphead, SLLN* pos, int x)
{assert(pos);assert(pphead);if (pos *pphead){SList_header(pphead, x);}else{//找pos的前一个位置SLLN* temp *pphead;while (temp-next ! pos){temp temp-next;}SLLN* newnode lookup(x);temp-next newnode;newnode-next pos;}
}
9. 删除指定节点 pos
注意情况分析
//删除指定节点 pos :Deletes the specified node
void SList_del(SLLN** pphead, SLLN* pos)
{assert(pphead);assert(pos);//assert(*pphead);可要可不要if (*pphead pos){SList_hdel(pphead);}else{//找到pos的前一个位置SLLN* temp *pphead;while (temp-next ! pos){temp temp-next;}temp-next pos-next;free(pos);//posNULL;没用因为形参不改变实参对应text6}
}
10. 在指定节点 pos 之后插入一个新节点
迭代问题注意保存下一个节点地址。
//后after
//在指定节点 pos 之后插入一个新节点:Inserts a new node after the specified node
void SList_after(SLLN* pos, int x)
{//经典错误//assert(pos);//SLLN* newnode lookup(x);//pos-next newnode;//newnode-next pos-next;//在将 pos 的 next 指针指向新节点 newnode 之前必须先保存 pos 节点的下一个节点的地址否则这部分链表将丢失。//正确写法assert(pos);SLLN* newnode lookup(x);newnode-next pos-next;//保存 pos 节点的下一个节点的地址pos-next newnode;//将 pos 的 next 指针指向新节点 newnode
}
11. 删除指定节点 pos 之后的节点
还是注意更新迭代的问题。
//删除指定节点 pos 之后的节点:Deletes a node after the specified node
void SList_del2(SLLN* pos)
{assert(pos);assert(pos-next);//错误写法不可单独出现//pos-next pos-next-next;//正确写法1SLLN* temp pos-next;pos-next pos-next-next;free(temp);temp NULL;//正确写法2//SLLN* temp pos-next;//pos-next temp-next;//free(temp);//temp NULL;
}
12. 链表的销毁
注意销毁的顺序迭代问题这里要着重注意稍有疏忽很容易造成内存泄漏
//链表销毁Destroyed销毁
void Destroyed(SLLN* phead)
{//经典错误//错误写法1//SLLN* temp phead;//while (temp)//{// free(temp);// temp temp-next;//}//错误写法2//SLLN* temp phead;//while (temp)//{// SLLN* tmp temp;// free(temp);// temp tmp-next;//}//正确写法SLLN* temp phead;while (temp){SLLN* tmp temp-next;free(temp);temp tmp;}//pheadNULL;
}
//或者
//void Destroyed(SLLN** pphead)
//{
// assert(pphead);
// SLLN* temp *pphead;
// while (temp)
// {
// SLLN* tmp temp-next;
// free(temp);
// temp tmp;
// }
//
// *pphead NULL;
//}
13. 测试用例 下面是我的个人测试用例大家可自行采纳欢迎大家去实践、去测试、去加入自己的想法
#define _CRT_SECURE_NO_WARNINGS 1
//list:列表
//text:测试#include SList.h//第一次测试
void text1()
{//此处错误对应 SList.c 文件 51 到 119 行两处错误需同时取消注释并将正确部分注释掉可查看错误效果/*SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);*///不改变实参直接传要改变传地址//正确写法要传地址SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);//不改变实参直接传要改变传地址}//第二次测试
void text2()
{SLLN* plist NULL;SList_header(plist, 1);SList_header(plist, 2);SList_header(plist, 3);SList_header(plist, 4);SList_header(plist, 5);SList_print(plist);SList_tdel(plist);SList_print(plist);SList_tdel(plist);SList_print(plist);SList_tdel(plist);SList_print(plist);
}//第三次测试
void text3()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);
}//第四次测试
void text4()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);//值为2的那个节点 *2SLLN* temp SList_find(plist, 2);temp-data * 2;SList_print(plist);}//第五次测试
void text5()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);// 值为2那个节点 *2SLLN* temp SList_find(plist, 2);SList_before(plist, temp, 20);SList_print(plist);}//第六次测试
void text6()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);// 值为2那个节点 *2SLLN* temp SList_find(plist, 2);SList_del(plist, temp);temp NULL;//此处置空或者别用即可SList_print(plist);Destroyed(plist);plist NULL;//或者 用于void Destroyed(SLLN** pphead); 生效时 //Destroyed(plist);//plist NULL;
}int main()
{//每次开一个测试也可自行写测试内容//text1();//text2();text3();//text4();//text5();//text6();return 0;
}
四、源文件展示链表 · 07c4d36 · 黄灿灿/数据结构 - Gitee.com 在这里注释对应的行号才准确
头文件SList.h
#pragma once
//Single-linked lists单链表(SList)
//list:列表#includestdio.h
#includestdlib.h
#includeassert.h//node:节点
//next:下一个
//data数据
//Singly linked list nodes:单链表节点(SLLN)typedef struct SListnode
{int data;struct SListnode* next;
}SLLN;
//等价于
//struct SListnode
//{
// int data;
// struct SListnode* next;
//};
//typedef struct SListnode SLLN;//找节点
SLLN* lookup(int x);// 动态申请一个节点:Dynamically apply for a node
//SLLN* Da_node(int x);// 单链表打印
void SList_print(SLLN* phead);// 单链表尾插 Tail plugging:尾插
//void SList_tplug(SLLN* phead, int x);//错
void SList_tplug(SLLN** pphead, int x);//对// 单链表的头插 Header:头插
void SList_header(SLLN** pphead, int x);// 单链表的尾删 Tail deletion:尾删
void SList_tdel(SLLN** pphead);// 单链表头删 Header deleted:头删
void SList_hdel(SLLN** pphead);// 单链表查找 Find:查找
SLLN* SList_find(SLLN* phead, int x);
//void SList_print_matching(SLLN* phead, int x);//在指定节点 pos 之前插入一个新节点:Inserts a new node before specifying it
void SList_before(SLLN** pphead, SLLN* pos, int x);//删除指定节点 pos :Deletes the specified node
void SList_del(SLLN** pphead, SLLN* pos);//后after
//在指定节点 pos 之后插入一个新节点:Inserts a new node after the specified node
void SList_after(SLLN* pos, int x);//删除指定节点 pos 之后的节点:Deletes a node after the specified node
void SList_del2(SLLN* pos);//链表销毁Destroyed销毁
void Destroyed(SLLN* phead);
//void Destroyed(SLLN** pphead);或者函数部分源文件SList.c
#define _CRT_SECURE_NO_WARNINGS 1
//Single-linked lists单链表
//Singly linked list nodes:单链表节点(SLLN)
//list:列表
//head:头
//tail:尾尾巴
//temp:临时的#include SList.h// 单链表打印
//可以使用二级指针但没必要要改变实参用二级不改变用一级可以加 const不建议会带来一些不必要的麻烦
void SList_print(SLLN* phead)
{//此处切不可断言assert空链表可以打印此处使用断言会终止程序//(单链表为空此处指针phead为空。顺序表此处需断言assert顺序表是一个结构体结构体里有一个指针指向一块数组空间结构体指针为空程序就走不了了)SLLN* temp phead;//注意切不可写成 while (temp-next ! NULL),最后一个数据无法打印//正确写法//while (temp ! NULL)while (temp){printf(%d-, temp-data);temp temp-next;//temp/temp,注意切不可加加节点地址不能保证连续}printf(NULL\n);
}//提取一个公共函数找一个新节点,lookup查找
//这个函数全部内容来自void SList_tplug(SLLN** pphead, int x)函数的 122-135 行
SLLN* lookup(int x)
{SLLN* newnode (SLLN*)malloc(sizeof(SLLN)); // newnode: 新节点if (newnode NULL) // 检查{perror(malloc fail);return NULL; // 返回 NULL 表示失败}// 新节点初始化为空newnode-data x;newnode-next NULL;return newnode;
}虽然是错但要从中吸取教训总结结论着重看和理解注释部分单链表尾插 Tail plugging:尾插
//void SList_tplug(SLLN* phead, int x)
//{
// //此处切不可断言assert链表为空指针phead为空此处使用断言会终止程序
//
// SLLN* newnode (SLLN*)malloc(sizeof(SLLN));//newnode:新节点
// if (newnode NULL)//检查
// {
// perror(malloc fail);
// return;
// }
//
// //新节点初始化为空
// newnode-data x;
// newnode-next NULL;
//
// if (phead NULL)
// {
// phead newnode;
// }
// else
// {
// //找尾尾插的本质原尾节点中要存储新的尾节点地址
// //正确写法(相对于此情况但此情况函数部分有错)
// SLLN* tail phead;//tail:尾
// while (tail-next ! NULL)
// {
// tail tail-next;
// }
// tail-next newnode;//精华所在
//
// //错误写法
// //SLLN* tail phead;//tail:尾
// //while (tail ! NULL)
// //{
// // tail tail-next;
// //}
// //tail newnode;
// //原因函数栈帧知识tail是局部变量之后会销毁
// }
//}//整个函数错误原因
请对比void temp(int *p) void temp(int *ptr)
{ {*p 1; ptr (int*)malloc(sizeof(int));
} }
int main() 和 int main()
{ 和 {int x 0; 和 int* pxNULL;temp(x); temp(px);return 0; return 0;
} }改变的是int使用的是int的指针改变int*要使用int*的地址int**指针
所以要改变*ptr使用的是*ptr的指针
即
int main()
{int* px NULL;Func(px);free(px);return 0;
}
正确的函数写法
void SList_tplug(SLLN** pphead, int x)
{//为了使用 35 行的 lookup 函数将此 122 到 135 行注释掉改成 137 行的 SLLN* newnode lookup(x);此处切不可断言assert链表为空指针phead为空此处使用断言会终止程序//SLLN* newnode (SLLN*)malloc(sizeof(SLLN));//newnode:新节点//if (newnode NULL)//检查//{// perror(malloc fail);// return;//}新节点初始化为空//newnode-data x;//newnode-next NULL;SLLN* newnode lookup(x);if (*pphead NULL){*pphead newnode;}else{//找尾尾插的本质原尾节点中要存储新的尾节点地址SLLN* tail *pphead;//tail:尾while (tail-next ! NULL){tail tail-next;}tail-next newnode;//精华所在改变指针改变结构体成员用一级指针函数栈帧的知识要深挖}
}// 单链表的头插 Header:头插
void SList_header(SLLN** pphead, int x)
{assert(pphead);SLLN* newnode lookup(x);newnode-next *pphead;*pphead newnode;
}// 单链表的尾删 Tail deletion:尾删
void SList_tdel(SLLN** pphead)
{错误写法//SLLN* tail *pphead;//while (tail-next ! NULL)//{// tail tail-next;//}//free(tail);//tail NULL;//错误原因此行tail是局部变量没有把前一个next节点置空前一个节点是一个结构体要将前一个结构体节点置空需要一个结构体的指针//检查二选一//暴力的检查assert(pphead);assert(*pphead);//或者assert(*pphead!NULL);//温柔的检查//if (*pphead NULL)//{// return;//}if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//正确写法1SLLN* temp NULL;SLLN* tail *pphead;while (tail-next ! NULL){temp tail;tail tail-next;}free(tail);tail NULL;temp-next NULL;//正确写法2//SLLN* tail *pphead;//while (tail-next-next ! NULL)//{//tail tail-next;//}//free(tail-next);//tail-next NULL;}
}// 单链表头删 Header deleted:头删
void SList_hdel(SLLN** pphead)
{//检查二选一//暴力的检查assert(pphead);assert(*pphead);//或者assert(*pphead!NULL);//温柔的检查//if (*pphead NULL)//{// return;//}SLLN* first *pphead;//first:第一*pphead first-next;free(first);first NULL;
}// 单链表查找 Find:查找
SLLN* SList_find(SLLN* phead, int x)
{SLLN* temp phead;while (temp){if (temp-data x){return temp;}temp temp-next;//更新temp}return NULL;
}
//或者使用查找打印函数
//void SList_print_matching(SLLN* phead, int x)
//{
// SLLN* temp phead;
// int found 0; // 标记是否找到了匹配的节点
//
// while (temp)
// {
// if (temp-data x)
// {
// printf(%d , temp-data); // 打印匹配的节点数据
// found 1; // 标记找到了匹配的节点
// }
// temp temp-next;
// }
//
// if (!found)
// {
// printf(No matching elements found.\n); // 如果没有找到匹配的节点
// }
// else
// {
// printf(\n); // 打印换行符使输出更加清晰
// }
//}//在指定节点 pos 之前插入一个新节点:Inserts a new node before specifying it
void SList_before(SLLN** pphead, SLLN* pos, int x)
{assert(pos);assert(pphead);if (pos *pphead){SList_header(pphead, x);}else{//找pos的前一个位置SLLN* temp *pphead;while (temp-next ! pos){temp temp-next;}SLLN* newnode lookup(x);temp-next newnode;newnode-next pos;}
}//删除指定节点 pos :Deletes the specified node
void SList_del(SLLN** pphead, SLLN* pos)
{assert(pphead);assert(pos);//assert(*pphead);可要可不要if (*pphead pos){SList_hdel(pphead);}else{//找到pos的前一个位置SLLN* temp *pphead;while (temp-next ! pos){temp temp-next;}temp-next pos-next;free(pos);//posNULL;没用因为形参不改变实参对应text6}
}//后after
//在指定节点 pos 之后插入一个新节点:Inserts a new node after the specified node
void SList_after(SLLN* pos, int x)
{//经典错误//assert(pos);//SLLN* newnode lookup(x);//pos-next newnode;//newnode-next pos-next;//在将 pos 的 next 指针指向新节点 newnode 之前必须先保存 pos 节点的下一个节点的地址否则这部分链表将丢失。//正确写法assert(pos);SLLN* newnode lookup(x);newnode-next pos-next;//保存 pos 节点的下一个节点的地址pos-next newnode;//将 pos 的 next 指针指向新节点 newnode
}//删除指定节点 pos 之后的节点:Deletes a node after the specified node
void SList_del2(SLLN* pos)
{assert(pos);assert(pos-next);//错误写法不可单独出现//pos-next pos-next-next;//正确写法1SLLN* temp pos-next;pos-next pos-next-next;free(temp);temp NULL;//正确写法2//SLLN* temp pos-next;//pos-next temp-next;//free(temp);//temp NULL;
}//链表销毁Destroyed销毁
void Destroyed(SLLN* phead)
{//经典错误//错误写法1//SLLN* temp phead;//while (temp)//{// free(temp);// temp temp-next;//}//错误写法2//SLLN* temp phead;//while (temp)//{// SLLN* tmp temp;// free(temp);// temp tmp-next;//}//正确写法SLLN* temp phead;while (temp){SLLN* tmp temp-next;free(temp);temp tmp;}//pheadNULL;
}
//或者
//void Destroyed(SLLN** pphead)
//{
// assert(pphead);
// SLLN* temp *pphead;
// while (temp)
// {
// SLLN* tmp temp-next;
// free(temp);
// temp tmp;
// }
//
// *pphead NULL;
//}
测试部分文件同上text.c
#define _CRT_SECURE_NO_WARNINGS 1
//list:列表
//text:测试#include SList.h//第一次测试
void text1()
{//此处错误对应 SList.c 文件 51 到 119 行两处错误需同时取消注释并将正确部分注释掉可查看错误效果/*SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);*///不改变实参直接传要改变传地址//正确写法要传地址SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);//不改变实参直接传要改变传地址}//第二次测试
void text2()
{SLLN* plist NULL;SList_header(plist, 1);SList_header(plist, 2);SList_header(plist, 3);SList_header(plist, 4);SList_header(plist, 5);SList_print(plist);SList_tdel(plist);SList_print(plist);SList_tdel(plist);SList_print(plist);SList_tdel(plist);SList_print(plist);
}//第三次测试
void text3()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);SList_hdel(plist);SList_print(plist);
}//第四次测试
void text4()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);//值为2的那个节点 *2SLLN* temp SList_find(plist, 2);temp-data * 2;SList_print(plist);}//第五次测试
void text5()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);// 值为2那个节点 *2SLLN* temp SList_find(plist, 2);SList_before(plist, temp, 20);SList_print(plist);}//第六次测试
void text6()
{SLLN* plist NULL;SList_tplug(plist, 1);SList_tplug(plist, 1);SList_tplug(plist, 2);SList_tplug(plist, 3);SList_tplug(plist, 4);SList_tplug(plist, 5);SList_print(plist);// 值为2那个节点 *2SLLN* temp SList_find(plist, 2);SList_del(plist, temp);temp NULL;//此处置空或者别用即可SList_print(plist);Destroyed(plist);plist NULL;//或者 用于void Destroyed(SLLN** pphead); 生效时 //Destroyed(plist);//plist NULL;
}int main()
{//每次开一个测试也可自行写测试内容//text1();//text2();text3();//text4();//text5();//text6();return 0;
}
总结
单链表是一种灵活的数据结构适用于多种应用场景。理解和掌握了单链表的基本操作后可以更高效地使用它们来解决实际问题。在后续的文章中我们还将继续探索单链表的其他高级特性和操作。
希望这篇文章能帮助读者你更好地理解单链表的概念和操作。如果您有任何疑问或建议请随时留言交流。
共勉
