欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

数据结构 | 双向链表、双向循环链表、栈

2026-02-01 分类：服务器技术 阅读(33) 评论(0)

一、双向链表

        双向链表是一种线性链式存储结构，和单向链表的核心区别是：每个节点不仅保存指向下一个节点的指针（next），还保存指向上一个节点的指针（pre）

二、双向链表的基本操作

        与单向链表相比较，双向链表的创建、插入、和删除与单向链表稍有区别，别的操作都是相同的，这里我将主要说明怎样创建、插入和删除。

类型定义：

typedef int DataType;

typedf struct node
{
DataType Data;
struct *pNext;
struct *pPre;
}

1.创建

        与单向链表不同的是，双向链表保存两个指针，在创建好空白节点后，我们需要将pnext和ppre都置为空值。

关键代码示例：

Node_t *CreatEmptyDouList(void)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if(NULL == pNewNode)
{
perror("fail to malloc");
return NULL;
}
pNewNode->pNext = NULL;
pNewNode->pPre = NULL;

return pNewNode;
}

2.插入

（1）头插法

  • 申请节点空间pNewNode;
  • 存放数据到pNewNode->pData空间；
  • 将pNewNode的pNext成员赋值为空白节点的pNext；
  • 将pNewNode的pPre成员赋值为空白节点的地址；
  • 如果后续有节点，需将后面节点（pNewNode->pNext）的pPre指向新申请的节点

关键代码示例：

int InsertHeadDoulist(Node_t *pHead, DataType TmpData)
{
Node_t *pNewNode = NULL;
pNewNode = malloc(sizeof(Node_t));
if(NULL == pNewNode)
{
perror("fail to malloc");
return -1;
}

pNewNode->Data = TmpData;
pNewNode->pNext = pHead->pNext;
pNewNode->pPre = pHead;
pHead->pNext = pNewNode;

if(pNewNode->pNext != NULL)
{
pNewNode->pNext->pPre = pNewNode;
}

return 0;
}

（2）尾插法

关键代码示例：

  • 定义一个指针pLastNode指向头指针；
  • 遍历找到最后一个节点；
  • 申请节点空间pNewNode；
  • 存放数据到pNewNode->pData空间，并将pNewNode的pNext置空；
  • 让pNewNode的pPre成员指向最后一个节点空间；
  • 让最后一个节点空间的pNext成员指向新申请的节点空间。

int InsertTailDouList(Node_t *pHead, DataType TmpData)
{
Node_t *pNewNode = NULL;
Node_t *pLsatNode = NULL;

pLsatNode = pHead;

while(pLsatNode->pNext != NULL)
{
pLsatNode = pLsatNode->pNext;
}

pNewNode = malloc(sizeof(Node_t));
if(pNewNode == NULL)
{
perror("fail to malloc");
return -1;
}

pNewNode->Data = TmpData;
pNewNode->pNext = NULL;
pNewNode->pPre = pLsatNode;
pLsatNode->pNext = pNewNode;

return 0;
}

3.删除

  • 遍历查找要删除的节点；
  • 让pTmpNode前面节点的pNext指向pTmpNode的pNext；
  • 如果后面有节点，让pTmpNode后面的节点的pPre指向pTmpNode的pPre；
  • 定义一个指针pFreeNode指向pTmpNode，pTmpNode向后走；
  • 释放pFreeNode，将pFreeNode置空

关键代码示例：

int DeleteDouListNode(Node_t *pHead, DataType TmpData)
{
int cnt = 0;
Node_t *pTmpNode = NULL;
Node_t *pFreeNode = NULL;

pTmpNode = pHead->pNext;

while(pTmpNode != NULL)
{
if(TmpData == pTmpNode->Data)
{
pTmpNode->pPre->pNext = pTmpNode->pNext;
if(pTmpNode->pNext != NULL)
{
pTmpNode->pNext->pPre = pTmpNode->pPre;
}

pFreeNode = pTmpNode;
pTmpNode = pTmpNode->pNext;
free(pFreeNode);
pFreeNode = NULL;
cnt++;
}
else
{
pTmpNode = pTmpNode->pNext;
}
}

return cnt;
}

三、双向循环链表

1.创建

        与双向链表类似，注意pPre和pNext不为NULL，则是指向自己。

关键代码示例：

Node_t *CreatEmptyCirList(void)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if(NULL == pNewNode)
{
perror("fail to malloc");
return NULL;
}

pNewNode->pPre = pNewNode;
pNewNode->pNext = pNewNode;

return pNewNode;
}

2.插入

（1）头插法

关键代码示例：

int InsertHeadCirList(Node_t *pHead, DataType TmpData)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if(NULL == pNewNode)
{
perror("fail to malloc");
return -1;
}

pNewNode->Data = TmpData;
pNewNode->pNext = pHead->pNext;
pNewNode->pPre = pHead;

pNewNode->pPre->pNext = pNewNode;
pNewNode->pNext->pPre = pNewNode;

return 0;
}

（2）尾插法

关键代码示例：

int InsertTailCirList(Node_t *pHead, DataType TmpData)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if(NULL == pNewNode)
{
perror("fail to malloc");
return -1;
}

pNewNode->Data = TmpData;
pNewNode->pNext = pHead;
pNewNode->pPre = pNewNode->pNext->pPre;

pNewNode->pNext->pPre = pNewNode;
pNewNode->pPre->pNext = pNewNode;

return 0;
}

图示：

3.遍历

        遍历方法与双向链表基本一致，只是pTmpNode != pHead时进入循环遍历

关键代码示例：

nt ShowCirList(Node_t *pHead)
{
Node_t *pTmpNode = NULL;

pTmpNode = pHead->pNext;

while(pTmpNode != pHead)
{
printf("%d ",pTmpNode->Data);
pTmpNode = pTmpNode->pNext;
}
printf("\\n");

return 0;
}

4.删除

  • 定义pTmpNode指向第一个有效节点；
  • 遍历查找要删除的节点；
  • 找到目标节点时，前驱节点的pNext指向后继节点，后继节点的pPre指向前驱节点；
  • 定义一个指针pFreeNode暂存待删节点，移动指针释放pFreeNode；
  • 未找到目标节点时，继续向后遍历。

关键代码示例：

int DeleteCirList(Node_t *pHead, DataType TmpData)
{
Node_t *pTmpNode = NULL;
Node_t *pFreeNode = NULL;
int cnt = 0;

pTmpNode = pHead->pNext;

while(pTmpNode != pHead)
{
if(pTmpNode->Data == TmpData)
{
pTmpNode->pPre->pNext = pTmpNode->pNext;
pTmpNode->pNext->pPre = pTmpNode->pPre;
pFreeNode = pTmpNode;
pTmpNode = pTmpNode->pNext;
free(pFreeNode);
pFreeNode = NULL;
cnt++;
}
else
{
pTmpNode = pTmpNode->pNext;
}
}

return cnt;
}

5.销毁

        与双向链表不同的是，定义两个指针从第一个有效节点开始，向后遍历释放空间，最后单独将头指针释放。

关键代码示例：

int DetoryCirList(Node_t **ppHead)
{
Node_t *pTmpNode = NULL;
Node_t *pFreeNode = NULL;

pTmpNode = pFreeNode = (*ppHead)->pNext;

while(pTmpNode != *ppHead)
{
pTmpNode = pTmpNode->pNext;
free(pFreeNode);
pFreeNode = pTmpNode;
}

free(*ppHead);

四、数组和链表的区别：

        数组空间是连续的；链表空间可以是不连续的；

        数组必须元素有限；链表元素是没有上限的；

        数组插入和删除的效率低；链表插入和删除的效率高；

        数组访问元素比较方便；链表访问元素不太方便。

五、栈

1. 栈是一种先进后出，后进先出的数据结构

2. 队列是一种先进先出，后进后出的数据结构

3. 栈、队列和表的区别：

  • 栈和队列是一种特殊的表状机构
  • 栈和队列只能在指定的位置插入和删除
  • 表可以在任意位置插入和删除

4. 栈的构成：

  • 栈顶：允许入栈和出栈的一端称为栈顶
  • 栈底：不允许入栈和出栈的一端称为栈底
  • 栈针：指向栈顶位置的指针或下标

4. 栈的分类：

  • 增栈：栈向高地址增长
  • 减栈：栈向低地址增长
  • 空栈：栈针指向入栈位置，称为空栈
  • 满栈：栈针指向栈顶位置，称为满栈

5. 分类：

  • 空增栈
  • 满增栈
  • 空减栈
  • 满减栈

6. 入栈（压栈）：将数据插入栈顶元素的位置

7.出栈（弹栈）：将数据从栈顶元素位置取出；

六、顺序栈的实现

顺序栈是用顺序存储结构（数组 / 列表）实现的栈，栈本身是遵循 后进先出规则的线性表，只能在栈顶进行插入（入栈）和删除（出栈）操作，栈底固定。

  • 底层依赖连续的内存空间；
  • 核心操作：入栈、出栈、取栈顶元素、判空、获取长度；
赞(0)
未经允许不得转载：171主机测评 » 数据结构 | 双向链表、双向循环链表、栈
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(59425)#python(20146)#开发语言(16891)#java(15497)#运维(15378)#linux(14966)#大数据(14592)#服务器(13075)#算法(11794)#前端(10919)#网络(9387)#ai(8940)#数据库(8912)#c++(8181)#课程设计(6804)#学习(6781)#机器学习(6720)#区块链(5924)#OpenClaw(5390)#后端(5163)#spring boot(5014)#深度学习(4958)#c语言(4382)#毕业设计(4294)#数据结构(4205)#安全(4074)#docker(3934)#架构(3867)#javascript(3811)#大模型(3658)

热门文章

最新文章

归档

分类