自学网站建设和seo,安溪网站建设,亚马逊网站建设与维护方法分析,网络空间搜索引擎目录
一、前言
#x1f34e; 为什么要学习链表
#x1f4a6;顺序表有缺陷
#x1f4a6; 优化方案#xff1a;链表 二、链表详解
#x1f350;链表的概念 #x1f349;链表的结构组成#xff1a;节点 #x1f353;链表节点的连接#xff08;逻辑结构与物理结构的区…目录
一、前言 为什么要学习链表
顺序表有缺陷 优化方案链表 二、链表详解
链表的概念 链表的结构组成节点 链表节点的连接逻辑结构与物理结构的区分 链表的分类
单链表各个接口的实现 ⭕接口1定义结构体SLTNode ⭕接口2创建一个新的节点SLTNode* BuySLTNode ⭕接口3单链表创建连续的节点SLTNode* CreateSlist ⭕接口4单链表的尾插SLTPushBack
⭕接口5单链表的尾删SLTPopBack
⭕接口6单链表的头插SLTPushFront ⭕接口7单链表的头删 SLTPopFront
⭕接口8单链表的节点查找 SLTNode* SLTFind
⭕接口9单链表在pos位置之后插入数据x SLTInsertAfter
⭕接口10单链表在pos位置之前插入数据x SLTInsert
⭕接口11删除单链表中pos位置之后的数据 SLTEraseAfter ⭕接口12删除单链表中pos位置的数据 SLTErase
⭕接口13单链表的数值打印 SLTPrint
⭕接口14单链表的销毁 SLTDestory 三、单链表的完整代码
SList.h
SList.c
Test.c
代码运行的菜单界面
四、共勉 一、前言 在之前的几篇文章中已经详细介绍了什么是数据结构什么是线性表什么是顺序表。其中线性表中包含了数组、顺序表、链表、队列等。那么此刻为什么还要再去学习链表链表在数据结构里面代表了什么呢这里我将给大家依次解惑让大家真正的搞懂数据结构学习起来才更有动力 为什么要学习链表
顺序表有缺陷 缺陷一空间经常不够需要扩容 1️⃣根据上一节对顺序表的讲解大家都应该知道顺序表和数组的本质是差不多的存放的数据都是连续的but在需要进行尾插和头插等操作时可能会出现空间不够需要进行扩容的操作。 2️⃣针对于扩容这个度我们就很难掌控扩容大了容易浪费空间扩容小了又要重复性的进行反复扩容影响效率。 缺陷二插入或者删除数据是需要挪动大量的数据效率低下 1️⃣由于顺序表存放的数据都是连续的当对顺序表进行头插时需要将所有数据从后往前挪动进行头删时需要将所有数据从前往后挪动。因此我们发现顺序表对数据的插入和删除都需要挪动大量的数据时间复杂度过高导致效率低下。 优化方案链表 优化一使用链表节点解决空间不够的情况 1️⃣对于空间不够需要扩容的情况我们采用malloc动态申请所需要的空间需要存储一个数据就开辟一块空间此时这一块空间就叫做---------节点。 优化二 使用链表中节点与节点之间的关系解决复杂度高的问题 1️⃣我们可以让前一个节点存放下一个节点的地址让它们相互关联起来当我们需要使用的时候只需要修改当前节点所存储放的内存地址即可。 此时此刻大家看到链表有如此强大的功能是不是很想看看链表到底是什么样子接下来让我们一起去学习吧 二、链表详解
链表的概念 概念链表是一种物理存储结构上非连续、非顺序的存储结构但链表在逻辑上是连续的顺序的而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 此时链表就像一个火车由一个个节点连接起来且节点是无序的每一个车厢可以切换和插入去除节点的插入和删除。 链表的结构组成节点 链表是由一个个节点组成的。 节点由俩个部分组成。 ▶一部分用来存储数据 ▶另一部分用来存储下一个节点的地址。 注意节点在内存中是散乱分布的它们是通过地址来寻找下一个节点。这和数组的连续存储有着很大的区别。 链表节点的连接逻辑结构与物理结构的区分 链表的逻辑结构图 注意此时的链表是我们人为想象出来的是为了让大家更好的去理解链表现实中并不存在箭头并且现实中每一个节点的地址都不一定连续而且可能会离得很远。 链表的物理结构图 总结通过上面两个结构图我们清楚的了解到链表其实是通过指针地址来依次找到每一个节点。这也就是大家经常说的链表只在逻辑结构上连续方便理解在物理结构上不连续实际情况。 链表的分类 1、单向或者双向 2、带头或者不带头 3、循环或者非循环 注意我们经常使用的链表主要是单链表和带头双向循环链表一个结构最简单一个结构最复杂。 这里就给打击简单介绍一下这两种链表的特点以及用处 ▶无头单向非循环链表也就是我们俗称的单链表。其结构简单一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构如哈希桶、栈的链式结构等。因为单链表本身有缺陷所以为常见的考核点之一。 ▶带头双向循环链表结构最复杂一般用来单独存储数据。实际使用的链表大多都是带头双向循环链表。虽然这种链表结构最复杂但是其实有很多优势并且在一定程度上对单链表的缺陷做出了一定的纠正。 针对本次的博客分享呢我呢先从结构最简单的单链表开始讲解 单链表各个接口的实现 这里先建立三个文件 1️⃣ SList.h文件用于函数声明 2️⃣ SList.c文件用于函数的定义 3️⃣ Test.c文件用于测试函数 建立三个文件的目的 将单链表作为一个项目来进行书写方便我们的学习与观察。 ⭕接口1定义结构体SLTNode 单链表的结构体由两个部分组成 ▶一部分用来存储数据 ▶另一部分用来存储下一个节点的地址。 typedef int SLTDataType; //数据类型
typedef struct SListNode
{int data; // 每一个节点上存储的数据struct SListNode* next; // 在结构体内定义指针用的时候需要开辟新的空间 在堆上开辟新的空间// 注意这个 next指向的是结构体本身 的地址 ---- 在链表里面 此时 next 指向下一个结构体的地址。
}SLTNode; ⭕接口2创建一个新的节点SLTNode* BuySLTNode 函数原理在堆上开辟一个新的空间用于存放新的数据和下一个节点的地址 // 单链表创建一个新节点
// 此时返回的是 newnode (newnode是结构体指针所以函数名为SLNode* BuySLTNode(int x))
// 此时是一个传值调用函数的形参与实参的转换
SLTNode* BuySLTNode(SLTDataType x)
{// 1.开辟出结构本身的 内存空间 将空间地址 存放在 指针变量结构体指针newnode 中// 2.此时每一个结构体的 地址就完成了赋值SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); // 为这个结构体开辟空间并将首地址传递给结构体指针if (newnode NULL) // 如果为空表示申请失败{perror(malloc fail);exit(-1);}newnode-data x; // 将这个节点的值存放进去newnode-next NULL; // 将这个节点的地址先设置为空为后续的 节点二做准备因为一般情况下next里面存放的是下一个节点的地址return newnode; // 返回开辟的结构体本身的地址
} ⭕接口3单链表创建连续的节点SLTNode* CreateSlist 函数原理根据接口2形成一个完成的单链表 // 单链表创建连续的节点
SLTNode* CreateSlist(int n)
{SLTNode* phead NULL;SLTNode* ptail NULL; //用于保存头节点for (int i 0; i n; i){SListNode* newnode BuySLTNode(i); //创建一个新的节点if (phead NULL){ptail phead newnode; //开始在头节点的时候将 结构体指针 ptail,phead都指向 第一个创建的节点 }else // 当判断此时这个节点不是头节点的时候{ptail-next newnode; // 先把此时这个节点的 新地址mewnode 传给next 以便于他们连接起来ptail newnode; // 再把指针ptail 转移到这个节点依次往后推就形成了一条来链子一样的链表 }}return phead; // 返回头指针
} // 注意 在局部变量里面的 phead 和 ptail 出了局部变量之后就会被销毁 ⭕接口4单链表的尾插SLTPushBack 函数原理在链表的尾部插入数据们需要考虑两点当链表为空时直接插入。若链表不为空先找到尾部在进行插入。 // 尾插
// 传址调用
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
// 注意pphead 是 plist 的拷贝 ------ pphead 的改变plist是不会改变的
void SLTPushBack(SLTNode** pphead, SLTDataType x) // pphead 是 plist的地址 *pphead 就是 plist, **pphead就是plist地址里面存放的东西
{// assert(phead); 此处不能进行断言因为空链表也可以进行尾插SLTNode* newnode BuySLTNode(x); //新插入的数据和数据的地址if (*pphead NULL) //判断是头节点是否为空{*pphead newnode;}else{SLTNode* tail *pphead; // 找尾巴while (tail-next ! NULL) // 注意我们此时寻找的是 指向下一个地址的 next {tail tail-next; // tail向后移动一位}tail-next newnode; // 将新的节点插入在尾部 同时 BuySTLNode(x) 将会是最后一个 next 指向空.}
}注意此时需要大家重视的是函数的二级指针传参问题大家可以参考我上一篇文章对函数的形参实参的的深度理解。 https://blog.csdn.net/weixin_45031801/article/details/128069009 ⭕接口5单链表的尾删SLTPopBack 函数原理和单链表的尾插一样分两步进行 // 尾删
void SLTPopBack(SLTNode** pphead)
{// 暴力检查assert(*pphead); // 防止链表已经删除完了继续删除空链表就不能尾删了//温柔检查/*if (*pphead NULL){return;}*/if ((* pphead)-next NULL) //只有一个节点单独处理{free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead; while (tail-next-next ! NULL){tail tail-next;}free(tail-next); //删除尾节点将其从空间中除去tail-next NULL; // 防止野指针的出现}
} ⭕接口6单链表的头插SLTPushFront 函数原理创建一个新的节点接在原有的链表上即可 // 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x); //创建一个新的节点newnode-next *pphead; //把原来的头节点给与next*pphead newnode; //把新创建得节点变成头节点
} ⭕接口7单链表的头删 SLTPopFront 函数原理需要进行断言判断函数头节点是否为空同时保存第二个节点的地址 // 头删 注意插入都不需要断言删除需要断言防止要删除得第一个为空
void SLTPopFront(SLTNode** pphead)
{assert(*pphead); //断言SLTNode* next (*pphead)-next; //先保存第二个节点得地址free(*pphead);*pphead next; //将第二个节点地址变为头节点地址
} ⭕接口8单链表的节点查找 SLTNode* SLTFind 函数原理进行链表的遍历查找即可 // 链表的查找 ---- 返回一个地址
// 有返回值此时是传值调用
// 因为返回值是结构体里面的成员所以返回函数为SLTNode* SLFind()
// 实参传过来的是一个头节点地址所以接收也是用指针形参接收
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead; //保存头节点while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
} ⭕接口9单链表在pos位置之后插入数据x SLTInsertAfter 函数原理根据接口9先找到pos的位置在进行插入即可 // 单链表在pos位置之后插入x
// 注意此时改变的是结构体的成员---next地址并没有改变实际的数值
void SLTInsertAfter(SLTNode* p, SLTDataType x) //此时这里的 *p 是pos节点的地址
{assert(p); //检查 p 是否为空SLTNode* newnode BuySLTNode(x); // 创建一个新的节点newnode-next p-next; // 把原本pos下一个节点的位置传给newnode-nextp-next newnode; // 再把newnode设置为pos位置的next
} ⭕接口10单链表在pos位置之前插入数据x SLTInsert 函数原理此时需要判断Pos的位置是否在头节点处分情况处理 //在pos之前插入x
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos); // 判断pos是否存在if(*ppheadpos) //如果pos就是头节点{SLTPushFront(pphead, x); //头插函数}else //pos不是头节点{SLTNode* prev *pphead; //保存头节点while (prev-next ! pos) //找到pos之前的位置{prev prev-next;}SLTNode* newnode BuySLTNode(x); //新建一个节点prev-next newnode;newnode-next pos;}
} ⭕接口11删除单链表中pos位置之后的数据 SLTEraseAfter 函数原理找到pos位置进行删除即可 void SLTEraseAfter(SLTNode* pos)
{assert(pos); // 检查pos位置是否存在if (pos-next NULL) //判断pos位置之后是否为空{return; //若是空什么都不做}else{SLTNode* nextNode pos-next; //此时需要将pos的next的地址换掉pos-next nextNode-next;free(nextNode);}
} ⭕接口12删除单链表中pos位置的数据 SLTErase 函数原理需要进行判断pos是否在头节点分情况进行 //删除pos位置
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos); //判断pos是否存在if (pos *pphead) //如果pos位置在头部就是头删{SLTPopFront(pphead);}else{ SLTNode* prev *pphead; //保存头节点while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
} ⭕接口13单链表的数值打印 SLTPrint // 单链表的数值打印
void SLTPrint(SLTNode* phead) // 这里的phead 与上边的phead 是不一样的
{// assert(phead); 此处不能进行断言因为空链表也可以进行打印SLTNode* cur phead;while (cur ! NULL){//printf(%d- , cur-data); //打印出头节点的值//printf(\n);printf(%d-, cur-data);// 继续走向下一个节点// 因为每一个节点的 next 都是指向下一个节点的地址// 所以此时将第一个节点的 next 传给 cur 就走向了下一个节点直到最后一个节点 next 为空结束cur cur-next;}printf(NULL\n);
} ⭕接口14单链表的销毁 SLTDestory // 单链表的销毁
// 注意顺序表是申请的一大块空间销毁时就直接销毁了
// 注意但是单链表是一个节点一个节点申请的所以释放的时候也需要一个一个释放
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTDestory(SLTNode** pphead)
{SLTNode* cur *pphead; //保存头节点while (cur ! NULL){SLTNode* next cur-next; //先保存下一个地址在释放防止到不到下一个地址free(cur);cur next;}*pphead NULL; // 将头指针制空防止野指针出现虽然释放了但是地址依然存在防止继续访问野指针
} 三、单链表的完整代码
SList.h #pragma once
#include stdio.h
#include string.h
#include stdlib.h
#include math.h
#include assert.htypedef int SLTDataType; //数据类型
typedef struct SListNode
{int data; // 每一个节点上存储的数据struct SListNode* next; // 在结构体内定义指针用的时候需要开辟新的空间 在堆上开辟新的空间// 注意这个 next指向的是结构体本身 的地址 ---- 在链表里面 此时 next 指向下一个结构体的地址。
}SLTNode;void SLTDestory(SLTNode** pphead); // 单链表的销毁SLTNode* BuySLTNode(SLTDataType x); // 将数据放在节点中并返回节点的地址-----创建一个新节点.SLTNode* CreateSlist(int n); // 创建做需要的 节点个数 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 SLTInsertAfter(SLTNode* pos, SLTDataType x); //单链表在pos位置之后插入x// 分析思考为什么不删除pos位置
void SLTEraseAfter(SLTNode* pos); //单链表删除pos位置之后的值void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos之前插入xvoid SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos位置// 总结1.改变int,传递int* 给形参*形参进行交换改变
// 2.改变int*,传递给int**给形参*形参进行交换改变//在数组中 [] 其实解引用的意思 SList.c #define _CRT_SECURE_NO_WARNINGS 1
#include SList.h// 什么时候用到二级指针 当需要改写时候进行使用
// 当程序只是进行 读 的时候就不需要用到二级指针// 单链表的销毁
// 注意顺序表是申请的一大块空间销毁时就直接销毁了
// 注意但是单链表是一个节点一个节点申请的所以释放的时候也需要一个一个释放
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTDestory(SLTNode** pphead)
{SLTNode* cur *pphead; //保存头节点while (cur ! NULL){SLTNode* next cur-next; //先保存下一个地址在释放防止到不到下一个地址free(cur);cur next;}*pphead NULL; // 将头指针制空防止野指针出现虽然释放了但是地址依然存在防止继续访问野指针
}// 单链表创建一个新节点
// 此时返回的是 newnode (newnode是结构体指针所以函数名为SLNode* BuySLTNode(int x))
// 此时是一个传值调用函数的形参与实参的转换
SLTNode* BuySLTNode(SLTDataType x)
{// 1.开辟出结构本身的 内存空间 将空间地址 存放在 指针变量结构体指针newnode 中// 2.此时每一个结构体的 地址就完成了赋值SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); // 为这个结构体开辟空间并将首地址传递给结构体指针if (newnode NULL) // 如果为空表示申请失败{perror(malloc fail);exit(-1);}newnode-data x; // 将这个节点的值存放进去newnode-next NULL; // 将这个节点的地址先设置为空为后续的 节点二做准备因为一般情况下next里面存放的是下一个节点的地址return newnode; // 返回开辟的结构体本身的地址
}// 单链表创建连续的节点
SLTNode* CreateSlist(int n)
{SLTNode* phead NULL;SLTNode* ptail NULL; //用于保存头节点for (int i 0; i n; i){SListNode* newnode BuySLTNode(i); //创建一个新的节点if (phead NULL){ptail phead newnode; //开始在头节点的时候将 结构体指针 ptail,phead都指向 第一个创建的节点 }else // 当判断此时这个节点不是头节点的时候{ptail-next newnode; // 先把此时这个节点的 新地址mewnode 传给next 以便于他们连接起来ptail newnode; // 再把指针ptail 转移到这个节点依次往后推就形成了一条来链子一样的链表 }}return phead; // 返回头指针
} // 注意 在局部变量里面的 phead 和 ptail 出了局部变量之后就会被销毁// 单链表的数值打印
void SLTPrint(SLTNode* phead) // 这里的phead 与上边的phead 是不一样的
{// assert(phead); 此处不能进行断言因为空链表也可以进行打印SLTNode* cur phead;while (cur ! NULL){//printf(%d- , cur-data); //打印出头节点的值//printf(\n);printf(%d-, cur-data);// 继续走向下一个节点// 因为每一个节点的 next 都是指向下一个节点的地址// 所以此时将第一个节点的 next 传给 cur 就走向了下一个节点直到最后一个节点 next 为空结束cur cur-next;}printf(NULL\n);
}// 尾插
// 传址调用
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
// 注意pphead 是 plist 的拷贝 ------ pphead 的改变plist是不会改变的
void SLTPushBack(SLTNode** pphead, SLTDataType x) // pphead 是 plist的地址 *pphead 就是 plist, **pphead就是plist地址里面存放的东西
{// assert(phead); 此处不能进行断言因为空链表也可以进行尾插SLTNode* newnode BuySLTNode(x); //新插入的数据和数据的地址if (*pphead NULL) //判断是头节点是否为空{*pphead newnode;}else{SLTNode* tail *pphead; // 找尾巴while (tail-next ! NULL) // 注意我们此时寻找的是 指向下一个地址的 next {tail tail-next; // tail向后移动一位}tail-next newnode; // 将新的节点插入在尾部 同时 BuySTLNode(x) 将会是最后一个 next 指向空.}
}// 尾删
void SLTPopBack(SLTNode** pphead)
{// 暴力检查assert(*pphead); // 防止链表已经删除完了继续删除空链表就不能尾删了//温柔检查/*if (*pphead NULL){return;}*/if ((* pphead)-next NULL) //只有一个节点单独处理{free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead; while (tail-next-next ! NULL){tail tail-next;}free(tail-next); //删除尾节点将其从空间中除去tail-next NULL; // 防止野指针的出现}
}// ******* 单链表的优势就在于 头删和头插 **********
// 注意插入都不需要断言删除需要断言防止要删除得第一个为空
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x); //创建一个新的节点newnode-next *pphead; //把原来的头节点给与next*pphead newnode; //把新创建得节点变成头节点
}// 头删 注意插入都不需要断言删除需要断言防止要删除得第一个为空
void SLTPopFront(SLTNode** pphead)
{assert(*pphead); //断言SLTNode* next (*pphead)-next; //先保存第二个节点得地址free(*pphead);*pphead next; //将第二个节点地址变为头节点地址
}// 链表的查找 ---- 返回一个地址
// 有返回值此时是传值调用
// 因为返回值是结构体里面的成员所以返回函数为SLTNode* SLFind()
// 实参传过来的是一个头节点地址所以接收也是用指针形参接收
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead; //保存头节点while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}// 单链表在pos位置之后插入x
// 注意此时改变的是结构体的成员---next地址并没有改变实际的数值
void SLTInsertAfter(SLTNode* p, SLTDataType x) //此时这里的 *p 是pos节点的地址
{assert(p); //检查 p 是否为空SLTNode* newnode BuySLTNode(x); // 创建一个新的节点newnode-next p-next; // 把原本pos下一个节点的位置传给newnode-nextp-next newnode; // 再把newnode设置为pos位置的next
}//在pos之前插入x
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos); // 判断pos是否存在if(*ppheadpos) //如果pos就是头节点{SLTPushFront(pphead, x); //头插函数}else //pos不是头节点{SLTNode* prev *pphead; //保存头节点while (prev-next ! pos) //找到pos之前的位置{prev prev-next;}SLTNode* newnode BuySLTNode(x); //新建一个节点prev-next newnode;newnode-next pos;}
}//单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{assert(pos); // 检查pos位置是否存在if (pos-next NULL) //判断pos位置之后是否为空{return; //若是空什么都不做}else{SLTNode* nextNode pos-next; //此时需要将pos的next的地址换掉pos-next nextNode-next;free(nextNode);}
}//删除pos位置
// plistpphead *(plist)*ppheadplist *(*(plist))**pphead
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos); //判断pos是否存在if (pos *pphead) //如果pos位置在头部就是头删{SLTPopFront(pphead);}else{ SLTNode* prev *pphead; //保存头节点while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
} Test.c #define _CRT_SECURE_NO_WARNINGS 1
// ------- 单链表 ----------//// 顺序表的缺陷
// 1. 空间不够需要扩容 realloc
// 扩容 尤其是异地扩容 是有一定的代价的。
// 其次还可能存在一定的空间浪费
// 2.头部或者中部的插入删除需要挪动数据效率低下.// 改进优化 链表的出现
// 1. 按需申请释放.(按照需求去申请释放)用指针将他们连接起来
// 2. 不要挪动数据.
// 3. 存储数据的空间叫做节点结点#include SList.h// 创建一个链表----进行每一个节点的测试
void TestSList1()
{// BuySLTNode()函数 求出每一个节点的地址// SLTNode * n :表示指针变量将每个节点的地址传给指针变量// 也就是说每次都是不同的结构体但是每一个结构体的类型都是相同的/*SLTNode* n1 BuySLTNode(1); SLTNode* n2 BuySLTNode(2); SLTNode* n3 BuySLTNode(3);SLTNode* n4 BuySLTNode(4);n1-next n2;n2-next n3;n3-next n4;n4-next NULL;*/// 例如创建一个 n 个节点的链表SLTNode* plist CreateSlist(4); // 此时就创建了 一个链表 有4个链子SLTPrint(plist); // 0-1-2-3-NULL
}// 创建一个链表并且进行尾插的测试
void TestSList2()
{SLTNode* plist CreateSlist(4); // 此时就创建了 一个链表 有4个链子SLTPushBack(plist, 100);SLTPrint(plist); // 0-1-2-3-100-NULLSLTDestory(plist); //进行销毁单链表SLTPrint(plist);
}
// 不创建链表直接进行尾插.
void TestSList3()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);
}// 尾删.
void TestSList4()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist); SLTPopBack(plist);SLTPrint(plist);
}// 头插.
void TestSList5()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);SLTPushFront(plist, 20);SLTPrint(plist);
}
// 头删 (头删是单链表的优势).
void TestSList6()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);
}
// 单链表的查找.
void TestSList7()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);SLTNode* pos SLTFind(plist, 300);if (pos ! NULL){printf(找到了\n);}else{printf(找不到\n);}SLTPrint(pos);
}
// 单链表在pos位置之后插入数据.
void TestSList8()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPrint(plist);SLTNode* pos SLTFind(plist, 200);if (pos ! NULL){SLTInsertAfter(pos, 30); // 插入数据30.printf(找到了\n);}else{printf(找不到\n);}SLTPrint(plist);
}
// 单链表在pos位置之前插入数据.
void TestSList9()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPushBack(plist, 400);SLTPushBack(plist, 500);SLTPrint(plist);SLTNode* pos SLTFind(plist, 300);if (pos ! NULL){SLTInsert(plist,pos, 30); // 插入数据30.printf(找到了\n);}else{printf(找不到\n);}SLTPrint(plist);
}
// 单链表删除pos位置之后的节点.
void TestSList10()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPushBack(plist, 400);SLTPushBack(plist, 500);SLTPrint(plist);SLTNode* pos SLTFind(plist, 500);if (pos ! NULL){SLTEraseAfter(pos); // 删除pos位置之后的数据.printf(找到了\n);}else{printf(找不到\n);}SLTPrint(plist);
}
// 单链表中删除pos位置
void TestSList11()
{SLTNode* plist NULL;SLTPushBack(plist, 100);SLTPushBack(plist, 200);SLTPushBack(plist, 300);SLTPushBack(plist, 400);SLTPushBack(plist, 500);SLTPrint(plist);SLTNode* pos SLTFind(plist, 300);if (pos ! NULL){SLTErase(plist, pos); // 删除pos位置之后的数据.printf(找到了\n);}else{printf(找不到\n);}SLTPrint(plist);
}
void menu()
{printf(***********************************************************\n);printf(1、头插节点 2、头删节点 \n);printf(\n);printf(3、尾插节点 4、尾删节点 \n);printf(\n);printf(5、在单链表中查找pos数据 6、在单链表pos位置之后插入一个新的节点\n);printf(\n);printf(7、删除单链表pos位置之后的节点 8、在单链表pos位置之前插入新的节点 \n);printf(\n);printf(9、在单链表中删除pos位置的数据 10、打印数据 \n);printf(\n);printf(-1、退出 \n);printf(***********************************************************\n);}
int main()
{printf(*************** 欢迎大家来到单链表的测试 ****************\n);int option 0;SLTNode* plist NULL;SLTNode* pos NULL;do{menu();printf(请输入你的操作);scanf(%d, option);int sum 0; int x 0;int y 0;int z 0;int w 0;int a 0;int b 0;int c 0;int d 0;switch (option){case 1:printf(请依次输入你要尾插的数据以-1结束\n);scanf(%d, sum);while (sum ! -1){SLTPushBack(plist, sum); // 1.头插scanf(%d, sum);}break;case 2:SLTPopFront(plist); // 2.头删break;case 3:printf(请输入想要尾插的数据);scanf(%d, x); // 3.尾插SLTPushBack(plist, x);break;case 4:SLTPopBack(plist); // 4.尾删break;case 5: printf(请输入想要查找的pos数据);scanf(%d, y);pos SLTFind(plist, y);if (pos ! NULL) // 5.在单链表中查找pos数据{printf(找到了\n);}else{printf(找不到pos位置\n);}break;case 6: // 6.在单链表pos位置后插入一个新的节点printf(请输入想要查找的pos数据);scanf(%d, z);pos SLTFind(plist, z);if (pos ! NULL){printf(请输入想要在pos位置后插入的数据);scanf(%d, w);SLTInsertAfter(pos, w); // 插入数据w.}else{printf(找不到pos位置无法插入\n);}break;case 7:printf(请输入想要查找的pos数据);scanf(%d, a);pos SLTFind(plist, a); if (pos ! NULL){SLTEraseAfter(pos); // 7.删除pos位置之后的数据.}else{printf(找不到pos位置无法删除\n);}break;case 8:printf(请输入想要查找的pos数据);scanf(%d, b);pos SLTFind(plist, b);if (pos ! NULL){printf(请输入想要在pos位置后插入的数据);scanf(%d, c);SLTInsert(plist, pos, c); // 在单链表pos位置之前插入数据c.}else{printf(找不到pos位置无法插入\n);}break;case 9:printf(请输入想要查找的pos数据);scanf(%d, d);pos SLTFind(plist, d);if (pos ! NULL){SLTErase(plist, pos); // 删除pos位置的数据.}else{printf(找不到pos位置无法删除\n);}case 10:SLTPrint(plist);break;default:if (option -1){exit(0); // 退出程序 }else{printf(输入错误请重新输入\n);}break;}} while (option ! -1);return 0;
} 代码运行的菜单界面 四、共勉
以下就是我对数据结构---单链表的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对数据结构-------单链表OJ请持续关注我哦
