当前位置：首页 > news >正文

政务网站建设要求网站模板怎么建站

news 2025/8/1 9:27:48

政务网站建设要求,网站模板怎么建站,怎样查公司注册信息查询,app开发策划书范文前言前面两期数据结构的文章我们介绍了顺序表和单向链表，那么本篇博文我们将来了解双向链表，作为最好用的一种链表，双向链表有什么特殊之处呢，接下来就让我们一起了解一下吧。下面是前两篇数据结构的文章： 数据结…

前言

前面两期数据结构的文章我们介绍了顺序表和单向链表，那么本篇博文我们将来了解双向链表，作为最好用的一种链表，双向链表有什么特殊之处呢，接下来就让我们一起了解一下吧。

下面是前两篇数据结构的文章：

数据结构(一)——顺序表的介绍

数据结构(二)——链表的介绍以及单链表的实现

双向链表的概念

什么是双向链表呢？实际上，双向链表全称是带头双向循环链表，是一种最复杂但最好用的一种链表形式，它不同于单项链表，它拥有一个头节点，正是由于头节点的存在，弥补了单项链表尾插的不便，同时它拥有两个指针，分别指向前驱和后继，从而方便链表进行数据的挪动等操作。

双向链表的实现

1.定义

前言

双向链表的概念

双向链表的实现

1.定义

2.双向链表接口定义

1.初始化

2.销毁

4.打印

5.尾插/尾删

6.头插/头删

7.任意位置插入/删除

8.查找

小结

typedef int LTDataType;
typedef struct LTNode
{struct LTNode* next;struct LTNode* prev;LTDataType x;
}LTNode;

双向链表的定义如上所示，我们发现，在这个结构体内，我们定义了两个结构体指针，分别指向结构体变量（双向链表）的前驱和后继节点，后续我们将通过这个结构体指针完成链表的头插，尾插等一系列操作。

2.双向链表接口定义

接下来我们将定义一系列链表的接口，通过这些函数，我们将完成链表的初始化、销毁、头插、尾插、头删、尾删、打印等一系列操作。

//链表的初始化
void LTInit(LTNode** pphead);
LTNode* LTInit();
//链表的销毁
void LTDestroy(LTNode* phead);
//链表的打印
void LTPrint(LTNode* phead);//链表的尾插
void LTPushBack(LTNode* phead,LTDataType x);
//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//链表的尾删
void LTPopBack(LTNode* phead);
//链表的头删
void LTPopFront(LTNode* phead);//在指定位置之后插入
void LTInsert(LTNode* pos, LTNode* phead);
//删除指定位置的节点
void LTErase(LTNode* pos);//查找一个值返回相应节点
LTNode* LTFind(LTNode* phead, LTDataType x);

从上述节点的定义我们发现，不同于单向链表，我们传的大多是一级指针，这是为什么呢？原因在于，双向链表多了一个哨兵位，当链表中只有哨兵位时我们称之为空链表，即哨兵位是不能删除的，而我们大多数操作是不会改变哨兵位的，所以只需要传一级指针。

1.初始化

我们看到，我们给出了两种链表的初始化方式一种是传二级指针，一种则是通过返回值接收，下面我们将实现代码如下：

void LTInit(LTNode** pphead)
{*pphead = (LTDataType*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc fail!");exit(1);}(*pphead)->a = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}

首先是二级指针初始化，我们看到，对二级指针解引用我们可以拿到这个地址，然后malloc一块空间，最后让前驱节点和后继节点都指向自己，这样我们就完成了链表的初始化。但是细心观察我们发现，这一段代码的逻辑是先开一块新的节点，然后再完成初始化，后续我们对链表的插入修改还要用到这一段逻辑，因此我们可以把这个逻辑写成申请节点的函数，这样既减少了代码量，还提高了可读性，所以就有了第二种初始化方式，代码如下：

LTNode* LTBuyNode(LTDataType x)
{//申请一个新的节点LTNode* newnode = (LTDataType*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->a = x;//让新节点的next prev指针指向自己newnode->next = newnode->prev = newnode;return newnode;
}
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

2.销毁

由于链表的每个节点不是连续的，所以我们需要循环销毁每一个节点，有了这个逻辑，我们就可以写下如下代码：

void LTDestroy(LTNode* phead)
{assert(phead);//pcur指向第一个节点LTNode* pcur = phead->next;while (pcur != phead){//记录下一个节点LTNode* next = pcur->next;//销毁该节点free(pcur);//让pcur指向下一个节点pcur = next;}//销毁哨兵位头节点free(phead);phead = NULL;
}

4.打印

与链表销毁类似，打印每个节点的值都是先找到该节点，然后再将该节点的值打印出来，因此我们可以写下如下代码：

void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->a);pcur = pcur->next;}printf("\n");
}

5.尾插/尾删

链表插入删除的关键是改变节点的指针，对于尾插而言，我们实际上是将该节点插入哨兵位的前面；对于尾删而言，我们实际上是删除的是哨兵位的前驱节点。因此改变指针指向实际上就是改变哨兵位前驱和后继节点的指向。代码如下：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* prve = phead->next->prev;phead->prev = prve;prve->next=phead;free(del);del = NULL;
}

6.头插/头删

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;phead->next->prev = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* prve = phead->next;LTNode* del = phead->next->next;phead->next = del;del->prev = phead;free(prve);prve = NULL;
}

这里有个小技巧，在我们插入时，我们可以先让新节点的前驱和后继节点指向相应位置，改变其他指针的指向

7.任意位置插入/删除

我们在有了前面插入删除的逻辑之后，我们可以用相同的逻辑如法炮制，就可以很快写出任意位置插入删除的代码：

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

8.查找

查找的逻辑十分简单，通过遍历链表，找到相应元素，然后返回当前节点，如果没有找到，就返回空，代码如下：

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->a == x){return pcur;}}return NULL;
}