建设网站需要用到哪些软件,网站开发 慕课,同行抄袭公司网站,做外汇的网站欢迎来到 Claffic 的博客 #x1f49e;#x1f49e;#x1f49e; “仅仅活着是不够的#xff0c;还需要有阳光#xff0c;自由和花的芬芳。” 前言#xff1a; 在日常使用的网站和软件中#xff0c;列表属于最常见的一种东西了#xff0c;其实现形式有顺序表#xff0… 欢迎来到 Claffic 的博客 “仅仅活着是不够的还需要有阳光自由和花的芬芳。” 前言 在日常使用的网站和软件中列表属于最常见的一种东西了其实现形式有顺序表链表等主要功能有增删查改那么链表具体是什么如何实现这篇博客为你解答。 注 这篇博客属于数据结构内容建议学习完C语言的小伙伴食用~ 目录
Part1: 何为链表
1.链表的概念
2.链表的结构
Part2: 链表的实现
1.开工准备
1.1创建项目
1.2建立结点
1.3动态申请结点
2.相关功能实现
2.1打印链表
2.2尾部插入
2.3头部插入
2.4尾部删除
2.5头部删除
2.6查找位置
2.7在pos位置之后插入
2.8删除pos之后的值
2.9pos之前插入
2.10删除pos结点 Part1: 何为链表
1.链表的概念 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 简单理解下这个概念就是一个存储单元中有 存储的数据 和 下一个存储单元的地址 经过这个存储单元可利用地址找到下一个存储单元。
下面讲到结构就会更加明白
2.链表的结构 一个简单链表的逻辑图
注意 • 链式结构在逻辑上连续在物理上不一定连续存储的地址不连续 • 现实中的结点一般是从堆上申请出来的 • 从堆上申请的空间按照一定策略分配两次申请的空间不一定连续。 Part2: 链表的实现
1.开工准备
1.1创建项目
按照惯例在 Single linked list 解决方案中创建三个项 SList.h头文件声明所有函数 SList.c源文件实现各函数 test.c 源文件主函数所在项可调用各函数。 1.2建立结点
这里创建一个结点的结构体包含要储存的数据和下一个结点的地址
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;//指向结构体的指针可通过它找到下一个结构体
}SLTNode;//将此结点简易命名方便引用1.3动态申请结点
关于为什么要动态申请
动态申请按需分配内存既不会空间多余也不会浪费。
SLTNode* BuySListNode(SLTDateType x)
{//动态申请SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc failed);return;}//初始化newnode-data x;newnode-next NULL;return newnode;
}
注意动态申请后要进行判断和初始化。
2.相关功能实现
2.1打印链表
我们打印的是一个结点中的数据
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;//地址不一定连续不可}printf(NULL\n);
}
这里值得注意的是 遍历过程中是如何前进的 因为地址不一定连续所以要进行赋值不可直接这一点很重要
2.2尾部插入
尾部插入在申请一个新的结点后要做的最重要的一点就是 末端节点 中的 结构体指针 要指向 新的结点
尾部插入有两种情况 • phead 为NULL • phead 不为NULL。 我们一个个分析
第一种情况 比较简单phead 为空
要让 phead 指向 newnode 指向的结点 直接赋值即可 *pphead newnode;//pphead 是指向 phead 的指针后面会讲利用二级指针的原因
第二种情况 就比较复杂
因为要实现上下的链接 再寻找一个 tail 用来遍历整个链表遇到 NULL 时停止。
void SListPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);if (*pphead NULL){*pphead newnode;}else{//查找尾部SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;//改变的是结构体成员用结构体的指针当然可以}
}
需要注意的是
形参的改变不影响实参需要通过二级指针来改变 phead.
如要改变 int* ,就需要通过 int** 来改变。
2.3头部插入
头部插入包括前后两个方向的链接一是 phead 要指向新的结点 二是 新结点中的结构体指针 指向原链表的第一个结点 我是图示
void SListPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
2.4尾部删除
我的思路是找到倒数第二个结点但还有只有一个结点的情况。
当只有一个结点时不用查找直接释放并置空该节点
当有多个结点时先找到倒数第二个结点将该节点的下一个结点释放并置空即可。
void SListPopBack(SLTNode** pphead)
{assert(pphead);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;}
}
2.5头部删除
要头部删除令 phead 指向第二个结点后释放第一个结点即可。
void SListPopFront(SLTNode** pphead)
{assert(pphead);SLTNode* first *pphead;*pphead first-next;free(first);first NULL;
}
2.6查找位置
查找特定数值所在的位置思路是通过头指针遍历最多遍历一遍链表
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{SLTNode* cur plist;while (cur){if (cur-data x){return cur;}cur cur-next;}return cur;
}
最后返回的是 结构体指针 也就是数值所在结构体的地址。
2.7在pos位置之后插入 在创建 newnode 之后改变指针指向即可 我是图示
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}注意要先改变 newnode.next 的值再改变 pos.next 的值否则会被覆盖。
2.8删除pos之后的值
可以先找到要删除的结点也就是pos的下一个结点再将该节点释放置空 我是图示
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos del-next;free(del);del NULL;
}
2.9pos之前插入
如果pos指向第一个结点就相当于前插
其他情况下需要找到pos的前一个再进行修改。 我是图示
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SListPushFront(pphead, x);}else{//查找pos前一个SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}
2.10删除pos结点
寻找pos的前一个修改其指向pos释放置空即可 我是图示
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//查找pos前一个SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
代码已上传至我的 gitee
拿走不谢~ 总结 这篇博客介绍了最简单的链表 -- 单链表的概念和结构并进行了相关功能的实现第一次接触可能会难很消化建议充分理解结构后进行实现呐~ 码文不易
如果你觉得这篇文章还不错并且对你有帮助不妨支持一波哦
