美食杰网站的建设目的,阿里巴巴出口贸易平台,工业品外贸平台,app 微信 网站三合一单链表 文章目录单链表1.链表1.1链表的概念和结构1.2链表的分类2.单链表的模拟实现2.1单链表的打印2.2单链表的尾插2.3单链表的头插2.4单链表的尾删2.5单链表的头删2.6单链表的查找2.7单链表的中间插入(在结点前插入)2.8单链表的中间删除(删除该结点)2.9单链表的中间插入(在结点…单链表 文章目录单链表1.链表1.1链表的概念和结构1.2链表的分类2.单链表的模拟实现2.1单链表的打印2.2单链表的尾插2.3单链表的头插2.4单链表的尾删2.5单链表的头删2.6单链表的查找2.7单链表的中间插入(在结点前插入)2.8单链表的中间删除(删除该结点)2.9单链表的中间插入(在结点后插入)2.10单链表的中间删除(删除该结点的后继)2.11单链表的销毁3.单链表的优缺点4. 链表的经典OJ题目训练1.链表 1.1链表的概念和结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 现实中 数据结构中 1.2链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构2*2*2 单向或者双向 带头或者不带头哨兵位的头结点 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势。 2.单链表的模拟实现
SList.h中
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDateType;//单链表结点结构
typedef struct SLTNode
{SLTDateType data;struct SLTNode* next;
}SLTNode;//单链表打印
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
//结点前插入
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDateType x);
//删除该结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//结点后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
//删除该结点的后继
void SLTEraseAfter(SLTNode* pos);
//单链表的销毁
void SLTDestroy(SLTNode** pphead);//free完所有结点将phead置空SList.c中
ps单链表是使用一个SLTNode*的指针plist头指针来维护的。
⚠注意1 由于要通过函数接口来实现单链表的增删查改(修改单链表)就要进行址传递传入plist 对于不需要修改单链表的接口直接传入plist即可 ⚠注意2 由于单链表的初始化比较简单我们在测试文件中(test.c)中直接SLTNode* plist NULL即可 单链表的销毁并不是简单地对头指针进行free而是要对每个结点进行free 2.1单链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}ps由于一个结点存着下一个结点的地址所以我们可以通过cur cur-next的方式来找下一个结点遍历下去。 2.2单链表的尾插
SLTNode* BuyNewnode(SLTDateType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail\n);return NULL;}else{newnode-data x;newnode-next NULL;}return newnode;
}//链表的插入操作是不需要对phead进行判空的因为空链表phead就是NULL
//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);//防止使用者传参时传的plist而不是plist特殊情况如果是空链表找不到尾结点所以直接将newnode作为phead//1.构造新结点SLTNode* newnode BuyNewnode(x);//特殊情况空链表if (*pphead NULL){*pphead newnode;return;}else//一般情况非空链表{//2.找到尾结点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//3.嫁接tail-next newnode;}}ps对于单链表的尾部操作需要先找到尾结点。时间复杂度O(N)。
而且对于空链表的情况无法找到尾结点需要特殊处理。 2.3单链表的头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode BuyNewnode(x);newnode-next *pphead;*pphead newnode;SLTInsert(pphead, *pphead, x);
}ps头部操作只需要注意连接关系即可时间复杂度为O(1) 2.4单链表的尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//删除操作链表不可为空//特殊情况如果链表只有一个结点是找不到前驱的要进行特殊处理SLTNode* tail *pphead;if (tail-next NULL)//1个结点的情况{free(tail);*pphead NULL;}else//多个结点的情况{SLTNode* prev NULL;//1.找到尾结点和尾结点的前驱while (tail-next ! NULL){prev tail;//每次去下一个用prev记录下来tail tail-next;}//2.删除尾结点进行嫁接和NULLfree(tail);tail NULL;prev-next NULL;}}ps找尾时间复杂度为O(N)
由于尾删需要找尾结点的前驱而只有一个结点的链表无法找到尾结点前驱需要进行特殊处理。 2.5单链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first *pphead;*pphead first-next;free(first);
}ps时间复杂度为O(N) 2.6单链表的查找
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}2.7单链表的中间插入(在结点前插入)
//结点前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode BuyNewnode(x);//特殊情况//头插if (pos *pphead){SLTPushFront(pphead, x);}SLTNode* prev *pphead;//1.找pos的前驱while (prev-next ! pos){prev prev-next;}//2.嫁接prev-next newnode;newnode-next pos;
}ps由于需要找结点pos的前驱时间复杂度O(N)
当pos为首结点时无法找到pos的前驱需要进行特殊处理头插操作 2.8单链表的中间删除(删除该结点)
//删除该结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//特殊情况//头删if (*pphead pos){SLTPopFront(pphead);}SLTNode* prev *pphead;//1.找前驱while (prev-next ! pos){prev prev-next;}//2.嫁接prev-next pos-next;free(pos);
}ps由于需要找结点pos的前驱时间复杂度O(N)
当pos为首结点时无法找到pos的前驱需要进行特殊处理头删操作 2.9单链表的中间插入(在结点后插入)
//结点后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode BuyNewnode(x);newnode-next pos-next;pos-next newnode;
}2.10单链表的中间删除(删除该结点的后继)
//删除该结点的后继
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//不能尾删SLTNode* next pos-next;pos-next next-next;free(next);next NULL;
}2.11单链表的销毁
void SLTDestroy(SLTNode** pphead)//free完所有结点将phead置空
{SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}3.单链表的优缺点
优点 1. 头部操作效率很高时间复杂度为O(1) 2. 结点之间不是连续存储的在进行插入操作时无法考虑增容。 缺点 1. 不支持随机访问即使知道是第几个结点也要进行遍历才能找到该结点。 2. 尾部操作要找结点效率低下(如果使用一个直接来指向尾结点也可实现O(1)的效率) ps对于空链表进行尾部操作时需要进行特殊处理这个时候我们可以构造一个哨兵位的头结点使问题简化。 4. 链表的经典OJ题目训练 删除链表中等于给定值 val 的所有结点。 OJ链接 反转一个单链表。 OJ链接 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。OJ链接 输入一个链表输出该链表中倒数第k个结点。 OJ链接 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。OJ链接 链表的回文结构。OJ链接 输入两个链表找出它们的第一个公共结点。OJ链接 给定一个链表判断链表中是否有环。 OJ链接 给定一个链表返回链表开始入环的第一个结点。 如果链表无环则返回 NULL OJ链接 给定一个链表每个结点包含一个额外增加的随机指针该指针可以指向链表中的任何结点或空结点。 要求返回这个链表的深度拷贝。OJ链接 其他 。ps链表的题当前因为难度及知识面等等原因还不适合我们当前学习以后大家自己下去以后 Leetcode OJ链接 牛客 OJ链接
