网站哪家公司做的好,广告设计和平面设计有什么区别,教育网站建设情况报告,wordpress百家号采集文章目录 单链表的实现代码位置概念与结构概念#xff1a;结构#xff1a; 链表的性质链表的分类单链表的实现单链表的创建和打印及销毁单链表的创建单链表的打印单链表的销毁 单链表的插入单链表头插单链表尾插单链表在指定位置之前插入数据单链表在指定位置之后插入数据 单… 文章目录 单链表的实现代码位置概念与结构概念结构 链表的性质链表的分类单链表的实现单链表的创建和打印及销毁单链表的创建单链表的打印单链表的销毁 单链表的插入单链表头插单链表尾插单链表在指定位置之前插入数据单链表在指定位置之后插入数据 单链表的删除单链表的头删单链表的尾删单链表在指定位置删除数据单链表在指定位置之后删除数据 单链表的查找指定位置节点 单链表的实现
代码位置
[Gitee](sllist/sllist · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))
概念与结构
概念
链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
类比火车地铁都是一节一节的 淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/ 加上不会影响其他车厢每节车厢都是独立存在的。
在链表⾥每节“⻋厢”是什么样的呢?
结构
与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点/结点”。 结点的组成主要有两个部分当前结点要保存的数据和保存下⼀个结点的地址指针变量。 图中指针变量plist保存的是第⼀个结点的地址我们称plist此时“指向”第⼀个结点如果我们希望 plist“指向”第⼆个结点时只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独立申请的即需要插⼊数据时才去申请⼀块结点的空间我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
链表的性质 1、链式机构在逻辑上是连续的在物理结构上不⼀定连续 2、结点⼀般是从堆上申请的 3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续 链表的分类 链表的结构⾮常多样以下情况组合起来就有8种2x2x2链表结构 链表说明 虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构单链表和双向带头循环链表 无头单向非循环链表结构简单⼀般不会单独⽤来存数据。实际种更多是作为其他数据结构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都是带头双向循环链表。但是这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带来很多优势实现反⽽简单了在下一篇博客我们将进行双向链表的实现。
单链表的实现
即不带头单向不循环链表
单链表的创建和打印及销毁 SList.h(其中方法会一一讲到)
定义链表结构将存储数据类型重命名(方便之后替换-例如我们要求单链表内存储char类型数据只用改一行代码即可)函数的声明声明的时候参数只需要类型就可以了名字加不加都一样
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void creatlist();
SLTNode* SLTBuyNode(SLTDataType x);
void printlist(SLTNode*);//插入
void SLTPushBack(SLTNode**, SLTDataType);
void SLTPushFront(SLTNode**, SLTDataType);//删除
void SLTPopBack(SLTNode**);
void SLTPopFront(SLTNode**);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//指定位置插入数据
void SLTInsert(SLTNode**, SLTDataType, SLTNode*);
void SLTInsertAfter( SLTDataType, SLTNode*);//删除指定节点
void SLTErase(SLTNode**, SLTNode*);
void SLTEraseAfter(SLTNode*);//销毁链表
void SListDestroy(SLTNode**);test.c
用来测试我们写的函数(函数的调用)这一部分就是自己写的时候用的测试用例随便什么都行
养成好习惯写一个方法测试一次不然找错误的时候会很痛苦
#include sllist.h
//实际操作中不会这么去创建链表
void creatlist()
{SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLTNode* plist node1;printlist(plist);}void test1(){SLTNode* plist NULL;//SLTPushBack(plist, 1);//SLTPushBack(plist, 2);//SLTPushBack(plist, 3);//SLTPushBack(plist, 4);SLTPushBack(NULL, 4);SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 4);SLTPushFront(plist, 3);//SLTPopBack(plist);//SLTPopBack(plist);//SLTPopFront(plist);//SLTPopFront(plist);//SLTNode* mSLTFind(plist, 3);//if (m! NULL)//{// printf(找到了\n);//}SLTInsert(plist, 3, m);//SLTInsertAfter( 6, m);// SLTErase(plist, m);//SLTEraseAfter(m);SListDestroy(plist);printlist(plist);}int main()
{//creatlist();test1();return 0;
}单链表的创建 可以看到在creatlist中我们是先随便申请几个节点然后将他们首尾相连 但链表的性质是每个节点都是独立申请的即我们有需要才去申请一块节点的空间所以我们实际中我们不会这样创建链表只需一开始创建一个链表结点类型的指针plist并将其置为空表示此时链表为空之后需要的时候我们通过插入一个节点并始终保持plist指向单链表第一个节点即可。
单链表的打印
void printlist(SLTNode* phead)
{assert(phead);SLTNode* p1 phead;while (p1){printf(%d , p1-data);p1 p1-next;}
}一般情况下单链表已知的都是指向第一个节点的指针plist因为我们只是打印不需要改变plist的指向即不需要改变plist的值所以我们用一级指针即可。基本思想仍是遍历 单链表的销毁
void SListDestroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* p1 pcur;pcur pcur-next;free(p1);p1 NULL;}*pphead NULL;
}- 这里我们要改变plist的值了所以传二级指针其实也可以传一级只不过在调用完后别忘了把plist置为空哦(❁´◡❁) 单链表的插入
单链表头插 既然要插入我们就要先申请一块空间 SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next NULL;return node;
}将申请新节点的函数分装起来便于调用
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}连接新节点和plist再让plist指向新节点
单链表尾插
void SLTPushBack(SLTNode** pphead , SLTDataType x)
{//申请新节点assert(pphead);SLTNode* newnode SLTBuyNode(x);if (*ppheadNULL){*pphead newnode;}else{SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}ptail-next newnode;}
}分两种情况 链表为空plist直接指向新节点链表不为空找尾节点再插入
单链表在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTDataType x, SLTNode* pos)
{assert(pphead pos);if (pos *pphead){SLTPushFront(pphead,x);}else{SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}newnode-next pos;prev-next newnode;}
}
分两种情况 若是pos和plist相同说明就是头插调用即可第二种情况找到pos之前一个节点一定要先改newnode的next指针否则找不到pos下一个节点了
单链表在指定位置之后插入数据
void SLTInsertAfter( SLTDataType x, SLTNode* pos)
{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}还是记得先改插入进来newnode的next指针 单链表的删除
单链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}删除都别忘了判断链表是否为空即plist是否为空
单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}if (prev)//处理只有一个节点的情况{prev-next NULL;prevNULL;}else*pphead NULL;free(ptail);ptail NULL;
}同样分两种情况 当链表多于一个节点时找尾节点以及其前一个节点将尾节点释放并把前一个节点next指针置为空 当链表只有一个节点时不需要将前一个节点next指针置为空此时需要将plist置为空
单链表在指定位置删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos )
{assert(pos pphead*pphead);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}分两种情况 pos和plist相同即为头删第二种情况先找到pos之前节点再进行指针的更改即可
单链表在指定位置之后删除数据
void SLTEraseAfter( SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
先保存pos之后节点改变pos的next指针后再释放del 单链表的查找指定位置节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-datax){return pcur;}pcur pcur-next;}return NULL;
}找到就返回指向节点的指针否则返回空老规矩遍历就行了
SList.c(完整版)
#define _CRT_SECURE_NO_WARNINGS 1
#include sllist.h
void printlist(SLTNode* phead)
{SLTNode* p1 phead;while (p1){printf(%d , p1-data);p1 p1-next;}
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next NULL;return node;
}void SLTPushBack(SLTNode** pphead , SLTDataType x)
{//申请新节点assert(pphead);SLTNode* newnode SLTBuyNode(x);if (*ppheadNULL){*pphead newnode;}else{SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}ptail-next newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}if (prev)//处理只有一个节点的情况prev-next NULL;else*pphead NULL;free(ptail);ptail NULL;
}void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-datax){return pcur;}pcur pcur-next;}return NULL;}void SLTInsert(SLTNode** pphead, SLTDataType x, SLTNode* pos)
{assert(pphead pos);if (pos *pphead){SLTPushFront(pphead,x);}else{SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}newnode-next pos;prev-next newnode;}
}void SLTInsertAfter( SLTDataType x, SLTNode* pos)
{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}void SLTErase(SLTNode** pphead, SLTNode* pos )
{assert(pos pphead*pphead);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}void SLTEraseAfter( SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}void SListDestroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* p1 pcur;pcur pcur-next;free(p1);p1 NULL;}*pphead NULL;
} 在单链表实现的函数中特别有两点要注意 1. 涉及到plist(指向第一个节点的指针)的指向改变时一定记得传plist的地址使用二级指针 2. 在尾插/尾删中都需要依据链表是否为空/链表是否多于一个节点来分情况讨论目的是避免对空指针进行解引用造成的错误。 以上就是单链表的实现方法啦各位大佬有什么问题欢迎在评论区指正您的支持是我创作的最大动力❤️
