【数据结构】 链表 + 手动实现单链表和双链表的接口(图文并茂附完整源码)

文章目录

一、 链表的概念及结构

二、链表的分类

​编辑

三、手动实现单链表

1、定义单链表的一个节点

2、打印单链表

3、创建新节点

4、单链表的尾插

5、单链表的头插

6、单链表的尾删

7、单链表的头删

8、单链表的查找

 9、在指定位置之前插入一个新节点

10、在指定位置之后插入一个新节点

11、删除指定节点

12、删除指定节点之后的节点

13、销毁链表

四、单链表实现完整代码

五、手动实现双向链表

1、定义双向链表的一个节点

2、创建新节点

3、双向链表的初始化

4、打印

5、尾插

6、头插

7、尾删

8、头删

9、查找

10、指定位置之后插入

11、删除指定位置的节点

12、销毁

 六、双向链表完整源码


一、 链表的概念及结构

链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。即链表的逻辑结构是线性的物理结构是非线性的

如上图所示,链表的每个节点在内存中都是随机分布着的,所以其物理结构(存储结构)为非连续,非顺序的;但是,链表的每个节点中的指针指向下一个节点,所以其逻辑结构是线性的。 

 如图,链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车厢,每节车厢都是独立存在的。 车厢是独立存在的,且每节车厢都有车门。想象一下这样的场景,假设每节车厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带一把钥匙的情况下如何从车头走到车尾? 最简单的做法:每节车厢里都放一把下一节车厢的钥匙。

再对应到链表,火车的车厢就是链表的节点,而下一节车厢中放的钥匙就是链表的每个节点中存放的下一个节点的地址。

链表的每个类似于车厢的结构,都是独立申请的空间,我们称之为节点。每个节点都由两部分组成:想要存储的数据存储下一个节点地址的指针。链表中每个节点都是独立申请的(即需要插⼊数据时才去申请⼀块节点的空间),我们需要通过指针 变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

二、链表的分类

链表的结构非常多样,以下情况组合起来就有8种(2x2x2)链表结构:

 1、带头与不带头

带头即链表有头节点(哨兵位),头节点不存放实际有意义的数据,只是用来占位置。有哨兵位的链表就是带头链表,如果带头链表只有一个头节点,该链表就为空链表。反之,没有哨兵位就是不带头链表,这时,链表的第一个节点就不能称为头节点。

2、单向与双向 

单向即链表的节点只有一个指向下一个节点的next指针。

双向即链表的节点不仅有一个指向下一个节点的next指针,还有指向上一个节点的prev指针。

3、循环与不循环

循环链表的尾节点的指针并不指向NULL,而是指向第一个有效的节点 。

三、手动实现单链表

根据上面链表的分类,单链表为不带头单向不循环链表。

为了方便阅读和查阅,我们先将单链表的头文件代码展示出来

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DateType;
//创建单链表的一个节点
typedef struct SList
{DateType val;struct SList* next;//指向下一个节点的指针
}SLT;//打印单链表
void PrintSLT(SLT* phead);
//链表尾插
void SLTpushBack(SLT** pphead, DateType x);
//链表头插
void SLTpushFront(SLT** pphead, DateType x);
//链表尾删
void SLTpopBack(SLT** pphead);
//链表头删
void SLTpopFront(SLT** pphead);
//链表的查找
SLT* SLTFind(SLT* ps, DateType x);
//在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x);
//在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x);
//删除指定节点
void SLTErase(SLT** pphead, SLT* pos);
//删除指定节点之后的节点
void SLTEraseAfter(SLT* pos);
//销毁链表中的所有节点
void SLTDestry(SLT** pphead);

1、定义单链表的一个节点

typedef int DateType;
//创建单链表的一个节点
typedef struct SList
{DateType x;struct SList* next;//指向下一个节点的指针
}SLT;

节点中有两个变量,一个用来存储数据,一个用来存储下一个节点的地址。由于next指针指向下一个节点,所以next为struct SList* 类型的指针变量。用typedef关键字来重定义,既方便我们修改,也方便我们书写。

2、打印单链表

想要打印单链表,只需要将单链表遍历一次。但是有个小细节,我们需要创建另一个SLT*类型的指针pcur,然后用这个指针来遍历单链表,防止指针指向改变而找不到链表的第一个节点。

//打印单链表
void PrintSLT(SLT* phead)
{SLT* pcur = phead;while (pcur){printf("%d->", pcur->val);pcur = pcur->next;}
}

3、创建新节点

想要实现单链表的尾插,头插以及指定位置插入数据,就避免不了要创建新的节点。由于链表再存储结构上非连续,所以我们用malloc来动态申请内存空间,然后将新节点的地址返回。

//创建新节点
SLT* BuyNode(DateType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;
}

4、单链表的尾插

(1)对pphead断言操作,因为我们不能对空指针进行解引用操作。但是,*pphead可以为空,此时链表为空链表。

 (2)创建一个新节点newnode,用来存放指定的数据,并返回新节点的地址。

(3)链表是否为空:

空链表:即*pphead=NULL,我们只需要让*pphead=newnode;

非空链表:因为要尾插,我们先要找到链表的尾节点,注意,while循环结束的条件是:

pcur->next = NULL。然后让尾节点的next指针指向新节点。

注意:当我们在尾插时,如果直接将plist作为实参传递给形参phead,那么我们发现,形参phead并不会影响实参plist的值。我们想要改变实参plist的值,就要传地址,而不是传值。由于plist是SLT*类型的指针,所以需要用SLT**类型的二级指针来接收实参。

如下图为传值调用,经过调试和运行,plist中的val值并没有发生改变。

//链表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//断言pphead不能为NULL,不能对空指针解引用assert(pphead);//创建新节点SLT* newnode = BuyNode(x);//处理空链表if (*pphead == NULL){*pphead = newnode;}//处理非空链表else{SLT* pcur = *pphead;while (pcur->next)//找尾节点{pcur = pcur->next;}pcur->next = newnode;}
}

5、单链表的头插

首先同样是对pphead断言操作,然后创建新节点,让新节点的next指针指向原来的第一个节点,这时候我们就不需要关注;吧是否为空了。

//链表头插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode = BuyNode(x);SLT* pcur = *pphead;newnode->next = pcur;*pphead = newnode;
}

6、单链表的尾删

由于链表的节点的空间都是malloc动态申请的,因此,删除链表的节点即释放节点所占的空间。

(1)对pphead断言;且对*pphead断言,因为,如果*pphead = NULL,则链表为空链表,不需要尾删。

(2)处理不同节点数量的情况:

只有一个节点:当 *pphead->next = NULL时,即只有一个节点,直接将*pphead释放。

不止一个节点:我们需要先找到链表的尾节点(遍历),然后释放。然后将尾节点的前一个节点的next指针置为空。因此,我们需要用创建pcur指针,防止找不到第一个节点;同时,创建prev指针记录尾节点的前一个节点。

//链表尾删
void SLTpopBack(SLT** pphead)
{//断言assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);//释放*pphead = NULL;}//不止一个节点else{SLT* pcur = *pphead;SLT* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);//释放pcur = NULL;prev->next = NULL;}
}

7、单链表的头删

(1)对pphead断言;且对*pphead断言,因为,如果*pphead = NULL,则链表为空链表,不需要尾删。

(2)释放第一个节点。但在释放之前需要用一个指针pcur记下第一个节点之后的节点,因为释放后,*pphead应该为原来的第二个节点。

//链表头删
void SLTpopFront(SLT** pphead)
{//断言assert(pphead && *pphead);SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}

8、单链表的查找

先断言,phead不能为空链表;然后创建pcur指针遍历链表,防止改变phead指针指向而找不到第一个节点。

//链表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur = phead;while (pcur){if (pcur -> val == x){return pcur;}pcur = pcur->next;}return NULL;
}

 9、在指定位置之前插入一个新节点

(1)断言;

(2)创建新节点;

(3)将新节点与链表连接起来。我们需要找到指定位置之前的节点prev,然后将prev节点,新节点newnode和指定位置的节点pos连接起来。

//在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead && *pphead);assert(pos);SLT* newnode = BuyNode(x);//找pos节点之前的节点SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//连接prev,newnode,posprev->next = newnode;newnode->next = pos;
}

10、在指定位置之后插入一个新节点

(1)断言;

(2)创建新节点;

(3)将新节点与链表连接起来。我们需要找到指定位置之后的节点pback,然后将指定位置的节点、新节点newnode和pback节点连接起来。

//在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode = BuyNode(x);SLT* pback = pos->next;//连接pos,newnode,pbackpos->next = newnode;newnode->next = pback;
}

11、删除指定节点

(1)断言;

(2)pos为第一个节点:释放后首节点改变。

pos不是第一个节点:释放指定节点,但在此之前需要先将指定节点之前的节点prev和指定节点之后的节点pback记录下来,最后连接prev节点和pback节点。

//删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead && *pphead);assert(pos);//指定节点为第一个节点if (*pphead == pos){SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}else{SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//先连接pos节点的前一个节点与pos的后一个节点prev->next = pos->next;free(pos);pos = NULL;}
}

12、删除指定节点之后的节点

先断言,看pos是否为空且pos之后的节点是否为尾节点;若断言通过,则创建std记录pos之后的节点,以及创建later 记录std的后一个节点,然后连接pos与later;最后释放指定节点之后的节点。


//删除指定节点之后的节点
void SLTEraseAfter(SLT* pos)
{assert(pos&&pos->next);//pos->next:处理当pos是最后一个节点的情况SLT* std = pos->next;SLT* later = std->next;free(std);std = NULL;pos->next = later;
}

13、销毁链表

断言,是否传了空指针,链表是否为空;然后遍历链表,逐个释放。

//销毁链表中的所有节点
void SLTDestry(SLT** pphead)
{assert(pphead && *pphead);SLT* std = *pphead;while (std){//记录要销毁节点的下一个节点,防止释放而找不到SLT* next = std->next;free(std);std = next;}*pphead = NULL;
}

四、单链表实现完整代码

SList.c

#include"SList.h"//打印单链表
void PrintSLT(SLT* phead)
{SLT* pcur = phead;while (pcur){printf("%d->", pcur->val);pcur = pcur->next;}
}//创建新节点
SLT* BuyNode(DateType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;
}//链表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//断言pphead不能为NULL,不能对空指针解引用assert(pphead);//创建新节点SLT* newnode = BuyNode(x);//处理空链表if (*pphead == NULL){*pphead = newnode;}//处理非空链表else{SLT* pcur = *pphead;while (pcur->next)//找尾节点{pcur = pcur->next;}pcur->next = newnode;}
}//链表头插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode = BuyNode(x);SLT* pcur = *pphead;newnode->next = pcur;*pphead = newnode;
}//链表尾删
void SLTpopBack(SLT** pphead)
{//断言assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);//释放*pphead = NULL;}//不止一个节点else{SLT* pcur = *pphead;SLT* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);//释放pcur = NULL;prev->next = NULL;}
}//链表头删
void SLTpopFront(SLT** pphead)
{//断言assert(pphead && *pphead);SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}//链表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur = phead;while (pcur){if (pcur -> val == x){return pcur;}pcur = pcur->next;}return NULL;
}//在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead && *pphead);assert(pos);SLT* newnode = BuyNode(x);//找pos节点之前的节点SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//连接prev,newnode,posprev->next = newnode;newnode->next = pos;
}
//在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode = BuyNode(x);SLT* pback = pos->next;//连接pos,newnode,pbackpos->next = newnode;newnode->next = pback;
}//删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead && *pphead);assert(pos);//指定节点为第一个节点if (*pphead == pos){SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}else{SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//先连接pos节点的前一个节点与pos的后一个节点prev->next = pos->next;free(pos);pos = NULL;}
}//删除指定节点之后的节点
void SLTEraseAfter(SLT* pos)
{assert(pos && pos->next);//pos->next:处理当pos是最后一个节点的情况SLT* std = pos->next;SLT* later = std->next;free(std);std = NULL;pos->next = later;
}//销毁链表中的所有节点
void SLTDestry(SLT** pphead)
{assert(pphead && *pphead);SLT* std = *pphead;while (std){//记录要销毁节点的下一个节点,防止释放而找不到SLT* next = std->next;free(std);std = next;}*pphead = NULL;
}

test.c 

#include"SList.h"void test01()
{SLT* s1 = (SLT*)malloc(sizeof(SLT));SLT* s2 = (SLT*)malloc(sizeof(SLT));SLT* s3 = (SLT*)malloc(sizeof(SLT));s1->val = 1;s2->val = 2;s3->val = 3;s1->next = s2;s2->next = s3;s3->next = NULL;PrintSLT(s1);//打印//SLTpopBack(&s1);//尾删//SLTpopFront(&s1);//头删//SLTpopFront(&s1);//头删printf("\n");//PrintSLT(s1);SLT*ret = SLTFind(s1, 2);//查找//printf("%d\n", ret->val);//SLTInsert(&s1, ret, 4);//指定位置之前插入//PrintSLT(s1);//SLTInsertAfter(ret, 4);//指定位置之后插入//PrintSLT(s1);//删除指定节点SLTErase(&s1, ret);PrintSLT(s1);
}void test02()
{SLT* s1 = (SLT*)malloc(sizeof(SLT));SLT* s2 = (SLT*)malloc(sizeof(SLT));s1->val = 1;s2->val = 2;s1->next = s2;s2->next = NULL;SLT* plist = s1;SLTpushFront(&plist, 3);//头插PrintSLT(plist);
}void test03()
{SLT* plist = NULL;//SLTpushBack(&plist, 1);//尾插//SLTpushFront(&plist, 1);//头插//SLTpopBack(&plist);//尾删PrintSLT(plist);
}
int main()
{test01();//test02();//test03();return 0;
}

五、手动实现双向链表

根据前面的分类,双向链表即带头双向循环链表

先展示头文件

LTNode.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define DateType int
//创建双向链表:带头双向循环链表
typedef struct LTNode
{DateType date;struct LTNode* prev;struct LTNode* next;
}LTNode;//初始化
void LTInit(LTNode**pphead);
//创建双向链表中的节点
LTNode* BuyNode(DateType x);
//打印双向链表
void PrintLT(LTNode* phead);
//双向链表尾插
void LTPushBack(LTNode* phead, DateType x);
//头插
void LTPushFront(LTNode* phead, DateType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, DateType x);
//指定位置之后插入
void LTInsert(LTNode* pos, DateType x);
//删除指定位置的节点
void LTEarse(LTNode* pos);
//销毁
void LTDestry(LTNode* phead);/*所有传的都是一级指针,保证了接口的一致性,降低了记忆的成本*/

1、定义双向链表的一个节点

双向链表中有一个存储Dateype类型的数据的变脸,一个用来指向下一个节点的指针next,还有一个用来指向上一个节点的指针prev。

typedef int DateType;
//定义双向链表(带头双向循环链表)的一个节点
typedef struct LTNode
{DateType date;struct LTNode* prev;//指向前一个节点struct LTNode* next;//指向后一个节点
}LTNode;

2、创建新节点

想要实现双向链表的初始化,尾插,头插以及指定位置插入数据,就避免不了要创建新的节点。由于链表再存储结构上非连续,所以我们用malloc来动态申请内存空间,然后赋值,改变两个指针的指向,使其形成自循环,最后将新节点的地址返回。

//创建双向链表中的节点
LTNode* BuyNode(DateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->date = x;newnode->prev = newnode->next = newnode;return newnode;
}

3、双向链表的初始化

双向链表是带头链表,所以对双向链表初始化即对头节点(哨兵位)初始化。由于哨兵位不存储有效数据,一般将date初始化为-1,然后,改变两个指针的指向,使其形成自循环,即直接调用创建新节点的函数。

//初始化
void LTInit(LTNode** pphead)
{*pphead = BuyNode(-1);
}

4、打印

打印则要遍历双向链表,同时,要打印的是双向链表的有效节点。因此,用一个pcur指针指向头节点的下一个节点,由于是双向链表,遍历时的结束条件就应该是pcur != phead。

//打印双向链表
void PrintLT(LTNode* phead)
{//pcur指向第一个有效节点LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->date);pcur = pcur->next;}
}

5、尾插

先要找到双向链表的尾节点。即phead->prev。

然后连接新节点与原来的尾节点:

phead->prev->next=newnode,newnode->prev=phead->prev

最后连接头节点与新节点:

phead->prev=newnode,newnode->next=phead;

注意连接的顺序,不然会改变phead->prev的指向。

//双向链表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//连接原来的尾节点与新节点phead->prev->next = newnode;newnode->prev = phead->prev;//连接头节点与新节点phead->prev = newnode;newnode->next = phead;
}

6、头插

头插是指插入到第一个有效节点之前。找到第一个有效节点,然后连接头节点,新节点与第一个节点。注意:phead->next的连接顺序,防止改变这种指向。

//头插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//连接新节点与原来第一个与有效节点newnode->next = phead->next;phead->next->prev = newnode;//连接头节点与新节点phead->next = newnode;newnode->prev = phead;
}

7、尾删

(1)断言:排除传过来NULL和空链表(只有一个头节点)的情况;

(2)找到尾节点:phead->prev;再顺藤摸瓜找到尾节点的前一个节点:phead->prev->prev

(3)连接头节点与新的尾节点,即phead与phead->prev->prev;注意:连接顺序

(4)释放尾节点。

//尾删
void LTPopBack(LTNode* phead)
{//排除传过来NULL和空链表(只有一个头节点)的情况assert(phead && phead->next != phead);LTNode* del = phead->prev;//尾节点//尾节点的前一个节点:del->prev//连接尾节点的前一个节点与头节点del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

8、头删

删除第一个有效节点。

(1)断言:排除传过来NULL和空链表(只有一个头节点)的情况;

(2)找到第一个有效节点:phead->next;第一个有效节点之后的节点:phead->next->next;

(3)连接头节点与第一个有效节点之后的节点,即连接phead与phead->next->next;注意:连接顺序

(4)释放第一个有效节点。

//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//第一个有效节点//第一个有效节点之后的节点;del->next//连接头节点与第一个有效节点之后的节点del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

9、查找

 查找则要遍历双向链表,且要查找的是双向链表的有效节点。因此,断言排除传过来NULL和只有一个头节点,然后,用一个pcur指针指向头节点的下一个节点,由于是双向链表,遍历时的结束条件就应该是pcur != phead。

//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead && phead->next != phead);LTNode* std = phead->next;//让std指针指向第一个有效节点//遍历while (std != std->next){if (std->date == x){return std;}std = std->next;}return NULL;
}

10、指定位置之后插入

先找到指定位置之后的节点:pos->next;然后。连接pos节点,新节点newnode与指定位置之后的节点pos->next。注意:连接顺序,防止改变pos->next的指向。

//指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode = BuyNode(x);//指定位置之后的节点:pos->next//连接新节点与原来指定位置之后的节点newnode->next = pos->next;pos->next->prev = newnode;//连接新节点与指定位置的节点pos->next = newnode;newnode->prev = pos;
}

11、删除指定位置的节点

现在的指定位置节点之前的节点:pos->prev;指定位置之后的节点:pos->next。然后,连接pos->prev与pos->next。最后,释放指定位置节点。

//删除指定位置的节点
void LTEarse(LTNode* pos)
{//指定位置之后的节点:pos->next//指定位置之前的节点:pos->prev//连接指定位置之后的节点与指定位置之前的节点pos->prev->next = pos->next;pos->next->prev = pos->prev;//删除pos节点free(pos);pos = NULL;
}

12、销毁

先找到第一个有效节点std,然后用std指针遍历链表,逐个节点释放,但在释放结构之前需要记下该节点的下一个节点,防止因为释放而找不到,到不到销毁整个链表的效果。最后将头节点释放。

//销毁
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std = phead->next;//让std指针指向第一个有效节点while (std != std->next){LTNode* next = std->next;//保证在std被释放后,std的下一个节点还能找到free(std);std = next;//下一个节点}//释放哨兵位free(phead);phead = NULL;
}

 六、双向链表完整源码

LTNode.c

#include"LTNode.h"
//初始化
void LTInit(LTNode** pphead)
{*pphead = BuyNode(-1);
}//创建双向链表中的节点
LTNode* BuyNode(DateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->date = x;newnode->prev = newnode->next = newnode;return newnode;
}//打印双向链表
void PrintLT(LTNode* phead)
{//pcur指向第一个有效节点LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->date);pcur = pcur->next;}
}//双向链表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//连接原来的尾节点与新节点phead->prev->next = newnode;newnode->prev = phead->prev;//连接头节点与新节点phead->prev = newnode;newnode->next = phead;
}//头插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//连接新节点与原来第一个与有效节点newnode->next = phead->next;phead->next->prev = newnode;//连接头节点与新节点phead->next = newnode;newnode->prev = phead;
}	//尾删
void LTPopBack(LTNode* phead)
{//排除传过来NULL和空链表(只有一个头节点)的情况assert(phead && phead->next != phead);LTNode* del = phead->prev;//尾节点//尾节点的前一个节点:del->prev//连接尾节点的前一个节点与头节点del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//第一个有效节点//第一个有效节点之后的节点;del->next//连接头节点与第一个有效节点之后的节点del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead && phead->next != phead);LTNode* std = phead->next;//让std指针指向第一个有效节点//遍历while (std != std->next){if (std->date == x){return std;}std = std->next;}return NULL;
}//指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode = BuyNode(x);//指定位置之后的节点:pos->next//连接新节点与原来指定位置之后的节点newnode->next = pos->next;pos->next->prev = newnode;//连接新节点与指定位置的节点pos->next = newnode;newnode->prev = pos;
}
//删除指定位置的节点
void LTEarse(LTNode* pos)
{//指定位置之后的节点:pos->next//指定位置之前的节点:pos->prev//连接指定位置之后的节点与指定位置之前的节点pos->prev->next = pos->next;pos->next->prev = pos->prev;//删除pos节点free(pos);pos = NULL;
}
//销毁
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std = phead->next;//让std指针指向第一个有效节点while (std != std->next){LTNode* next = std->next;//保证在std被释放后,std的下一个节点还能找到free(std);std = next;//下一个节点}//释放哨兵位free(phead);phead = NULL;
}

test.c 

#include"LTNode.h"
void test01()
{LTNode* plist = NULL;LTInit(&plist);//初始化//LTPushBack(plist, 4);//尾插//LTPushFront(plist, 4);//头插//LTPopBack(plist);//尾删LTPopFront(plist);PrintLT(plist);
}
void test02()
{LTNode* s = NULL;LTInit(&s);LTNode* s1 = (LTNode*)malloc(sizeof(LTNode));LTNode* s2 = (LTNode*)malloc(sizeof(LTNode));LTNode* s3 = (LTNode*)malloc(sizeof(LTNode));s1->date = 1;s2->date = 2;s3->date = 3;//连接s->next = s1;s->prev = s3;s1->prev = s;s1->next = s2;s2->prev = s1;s2->next = s3;s3->prev = s2;s3->next = s;PrintLT(s);//打印printf("\n");//LTPushBack(s, 4);//尾插//LTPushFront(s,4);//头插//LTPopBack(s);//尾删//LTPopFront(s);//头删LTNode* ret = LTFind(s, 2);//查找//printf("%d\n", ret->date);//LTInsert(ret, 4);//指定位置之后插入LTEarse(ret);PrintLT(s);
}
int main()
{//test01();test02();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/news/914869.shtml
繁体地址,请注明出处:http://hk.pswp.cn/news/914869.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Go语言时间控制:定时器技术详细指南

1. 定时器基础&#xff1a;从 time.Sleep 到 time.Timer 的进化为什么 time.Sleep 不够好&#xff1f;在 Go 编程中&#xff0c;很多人初学时会用 time.Sleep 来实现时间控制。比如&#xff0c;想让程序暂停 2 秒&#xff0c;代码可能是这样&#xff1a;package mainimport (&q…

C# 转换(显式转换和强制转换)

显式转换和强制转换 如果要把短类型转换为长类型&#xff0c;让长类型保存短类型的所有位很简单。然而&#xff0c;在其他情况下&#xff0c; 目标类型也许无法在不损失数据的情况下容纳源值。 例如&#xff0c;假设我们希望把ushort值转化为byte。 ushort可以保存任何0~65535的…

浅谈自动化设计最常用的三款软件catia,eplan,autocad

笔者从上半年开始接触这三款软件&#xff0c;掌握了基础用法&#xff0c;但是过了一段时间不用&#xff0c;发现再次用&#xff0c;遇到的问题短时间解决不了&#xff0c;忘记的有点多&#xff0c;这里记录一下&#xff0c;防止下次忘记Elpan:问题1QF01是柜安装板上的一个部件&…

网络编程7.17

练习&#xff1a;服务器&#xff1a;#include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include &…

c++ 模板元编程

听说模板元编程能在编译时计算出常量&#xff0c;简单测试下看看&#xff1a;template<int N> struct Summation {static constexpr int value N Summation<N - 1>::value; // 计算 1 2 ... N 的值 };template<> struct Summation<1> { // 递归终…

【深度学习】神经网络过拟合与欠拟合-part5

八、过拟合与欠拟合训练深层神经网络时&#xff0c;由于模型参数较多&#xff0c;数据不足的时候容易过拟合&#xff0c;正则化技术就是防止过拟合&#xff0c;提升模型的泛化能力和鲁棒性 &#xff08;对新数据表现良好 对异常数据表现良好&#xff09;1、概念1.1过拟合在训练…

JavaScript的“硬件窥探术”:浏览器如何读取你的设备信息?

JavaScript的“硬件窥探术”&#xff1a;浏览器如何读取你的设备信息&#xff1f; 在Web开发的世界里&#xff0c;JavaScript一直扮演着“幕后魔术师”的角色。从简单的页面跳转到复杂的实时数据处理&#xff0c;它似乎总能用最轻巧的方式解决最棘手的问题。但你是否想过&#…

论安全架构设计(层次)

安全架构设计&#xff08;层次&#xff09; 摘要 2021年4月&#xff0c;我有幸参与了某保险公司的“优车险”项目的建设开发工作&#xff0c;该系统以车险报价、车险投保和报案理赔为核心功能&#xff0c;同时实现了年检代办、道路救援、一键挪车等增值服务功能。在本项目中&a…

滚珠导轨常见的故障有哪些?

在自动化生产设备、精密机床等领域&#xff0c;滚珠导轨就像是设备平稳运行的 “轨道”&#xff0c;为机械部件的直线运动提供稳准导向。但导轨使用时间长了&#xff0c;难免会出现这样那样的故障。滚珠脱落&#xff1a;可能由安装不当、导轨损坏、超负荷运行、维护不当或恶劣环…

机器视觉的包装盒丝印应用

在包装盒丝网印刷领域&#xff0c;随着消费市场对产品外观精细化要求的持续提升&#xff0c;传统印刷工艺面临多重挑战&#xff1a;多色套印偏差、曲面基材定位困难、异形结构印刷失真等问题。双翌光电科技研发的WiseAlign视觉系统&#xff0c;通过高精度视觉对位技术与智能化操…

Redis学习-03重要文件及作用、Redis 命令行客户端

Redis 重要文件及作用 启动/停止命令或脚本 /usr/bin/redis-check-aof -> /usr/bin/redis-server /usr/bin/redis-check-rdb -> /usr/bin/redis-server /usr/bin/redis-cli /usr/bin/redis-sentinel -> /usr/bin/redis-server /usr/bin/redis-server /usr/libexec/red…

SVN客户端(TortoiseSVN)和SVN-VS2022插件(visualsvn)官网下载

SVN服务端官网下载地址&#xff1a;https://sourceforge.net/projects/win32svn/ SVN客户端工具(TortoiseSVN):https://plan.io/tortoise-svn/ SVN-VS2022插件(visualsvn)官网下载地址&#xff1a;https://www.visualsvn.com/downloads/

990. 等式方程的可满足性

题目&#xff1a;第一次思考&#xff1a; 经典并查集 实现&#xff1a;class UnionSet{public:vector<int> parent;public:UnionSet(int n) {parent.resize(n);}void init(int n) {for (int i 0; i < n; i) {parent[i] i;}}int find(int x) {if (parent[x] ! x) {pa…

HTML--教程

<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>菜鸟教程(runoob.com)</title> </head> <body><h1>我的第一个标题</h1><p>我的第一个段落。</p> </body> </html&g…

Leetcode刷题营第二十七题:二叉树的最大深度

104. 二叉树的最大深度 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff…

微信小程序翻书效果

微信小程序翻书效果 wxml <viewwx:for"{{imgList}}" hidden"{{pagenum > imgList.length - index - 1}}"wx:key"index"class"list-pape" style"{{index imgList.length - pagenum - 1 ? clipPath1 : }}"bindtouchst…

个人IP的塑造方向有哪些?

在内容创业和自媒体发展的浪潮下&#xff0c;个人IP的价值越来越受到重视。个人IP不仅是个人品牌的延伸&#xff0c;更是吸引流量来实现商业变现的重要工具。想要塑造个人IP&#xff0c;需要我们有明确的内容方向和策略&#xff0c;下面就让我们来简单了解下。一、展现自我形象…

Spring之【BeanDefinition】

目录 BeanDefinition接口 代码片段 作用 BeanDefinitionRegistry接口 代码片段 作用 RootBeanDefinition实现类 GenericBeanDefinition实现类 BeanDefinition接口 代码片段 public interface BeanDefinition {// ...void setScope(Nullable String scope);NullableSt…

GD32VW553-IOT LED呼吸灯项目

GD32VW553-IOT LED呼吸灯项目项目简介这是一个基于GD32VW553-IOT开发板的LED呼吸灯演示项目。通过PWM技术控制LED亮度&#xff0c;实现多种呼吸灯效果&#xff0c;展示RISC-V MCU的PWM功能和实时控制能力。功能特性1. 多种呼吸灯效果正弦波呼吸&#xff1a;自然平滑的呼吸效果线…