C语言双向链表的内存释放,（C语言版）链表（三）——实现双向链表创建、删除、插入、释放内存等简单操作...

客官°小女子只卖身不卖艺 2022-10-15 00:59 322阅读 0赞

上午写了下单向循环链表的程序，今天下午我把双向链表的程序写完了。其实双向链表和单向链表也是有很多相似的地方的，听名字可以猜到，每个节点都包含两个指针，一个指针指向上一个节点，一个指针指向下一个节点。这里有两个特殊的地方，第一就是头节点的一个指针指向NULL空指针(没有前驱节点)，第二就是尾节点的一个指针指向NULL指针(没有后继节点)。

我们可以看下双向链表的示意图(自己画的比较难看)：

![bbb5657f64350c83b9d2af07bec8584b.png][]

所以，我们在编程序的时候，这两个指针的控制就是我们的难点，因为我们始终要让这个链表保持这样的链接不管是在创建的时候、插入的时候、删除的时候等，一定要让节点的两个指针指向正确的节点。下面我们来看下双向链表的代码。

DbLinkList.h  头文件——包含节点结构的定义和各种操作函数的声明。

\#ifndef DOUBLY\_LINKED\_LIST\_H\#define DOUBLY\_LINKED\_LIST\_H typedefstructNode

\{intdata;struct Node \*pNext;struct Node \*pPre;

\}NODE,\*pNODE;//创建双向链表

pNODE CreateDbLinkList(void);//打印链表

voidTraverseDbLinkList(pNODE pHead);//判断链表是否为空

intIsEmptyDbLinkList(pNODE pHead);//计算链表长度

intGetLengthDbLinkList(pNODE pHead);//向链表插入节点

int InsertEleDbLinkList(pNODE pHead, int pos, intdata);//从链表删除节点

int DeleteEleDbLinkList(pNODE pHead, intpos);//删除整个链表，释放内存

void FreeMemory(pNODE \*ppHead);\#endif

DbLinkList.cpp 双向链表的源文件——包含了各种操作函数的定义。

(1)这部分是创建双向链表，和单向链表很相似，但是呢，有些地方还是得注意，就是每创建一个节点的时候都要注意初始化它的两个指针。

\#include \#include\#include"DbLinkList.h"

//创建双向链表

pNODE CreateDbLinkList(void)

\{int i, length = 0, data = 0;

pNODE pTail= NULL, p\_new =NULL;

pNODE pHead= (pNODE)malloc(sizeof(NODE));if (NULL ==pHead)

printf("内存分配失败！");

exit(EXIT\_FAILURE);

pHead->data = 0;

pHead->pPre =NULL;

pHead->pNext =NULL;

pTail=pHead;

printf("请输入想要创建链表的长度：");

scanf("%d", &length);for (i=1; i

p\_new= (pNODE)malloc(sizeof(NODE));if (NULL ==p\_new)

printf("内存分配失败！");

exit(EXIT\_FAILURE);

printf("请输入第%d个元素的值：", i);

scanf("%d", &data);

p\_new->data =data;

p\_new->pNext =NULL;

p\_new->pPre =pTail;

pTail->pNext =p\_new;

pTail=p\_new;

\}returnpHead;

(2)这部分是获得双向链表的信息，这里和单向链表基本一致，因为遍历的时候只用到了一个指针。

//打印链表

void TraverseDbLinkList(pNODE pHead)

pNODE pt = pHead->pNext;

printf("打印链表如：");

while (pt != NULL)

printf("%d ", pt->data);

pt = pt->pNext;

putchar('

');

//判断链表是否为空

int IsEmptyDbLinkList(pNODE pHead)

pNODE pt = pHead->pNext;

if (p == NULL)

return 1;

else

return 0;

//计算链表的长度

int GetLengthDbLinkList(pNODE pHead)

int length = 0;

pNODE pt = pHead->pNext;

while (pt != NULL)

length++;

pt = pt->pNext;

return length;

(3)这部分是向双向链表插入节点，也跟单向链表很多相似的地方。我们先来看下插入节点时的示意图：

![87cfdbc1b803084bf90ac95993fc5b55.png][]

从图中可以看到，每次我们添加一个节点都有很多地方要调节的，也就是每个节点的那两个指针，一定要认真仔细自己动手写一遍，有可能有些细节就会出错。这里有一个地方需要注意，是和单向链表不同的地方，单向链表在插入节点的时候不需要判断最后一个节点是否为空，因为这不影响程序的结果，但是对于双向链表就不一样了，因为我们后面要用到最后一个节点的一个指针指向前一个节点，如果最后一个节点是空的话(就是程序中的pt)，就不存在pt->pPre了,那么程序运行到这里时就会报错，所以我们要加个判断，判断此时节点是NULL的话就不需要控制它的指针了。

//向双向链表中插入节点

int InsertEleDbLinkList(pNODE pHead, int pos, int data)

pNODE pt = NULL, p\_new = NULL;

if (pos > 0 && pos

p\_new = (pNODE)malloc(sizeof(NODE));

if (NULL == p\_new)

printf("内存分配失败！

");

exit(EXIT\_FAILURE);

while (1)

pos--;

if (0 == pos)

break;

pHead = pHead->pNext;

pt = pHead->pNext;

p\_new->data = data;

p\_new->pNext = pt;

if (NULL != pt)

pt->pPre = p\_add;

p\_new->pPre = pHead;

pHead->pNext = p\_new;

return 1;

else

return 0;

(4)这部分是从链表中删除节点，当然这里和单向链表差不多，要注意的地方和插入节点时是一样的，上面已经说明了。

//从链表中删除节点

int DeleteEleDbLinkList(pNODE pHead, int pos)

pNODE pt = NULL;

if (pos > 0 && pos

while (1)

pos--;

if (0 == pos)

break;

pHead = pHead->pNext;

pt = pHead->pNext->pNext;

free(pHead->pNext);

pHead->pNext = pt;

if (NULL != pt)

pt->pPre = pHead;

return 1;

else

return 0;

(5)这部分是用来释放内存的，注意的地方和上面一样。

//删除整个链表，释放内存

void FreeMemory(pNODE \*ppHead)

pNODE pt = NULL;

while (\*ppHead != NULL)

pt = (\*ppHead)->pNext;

free(\*ppHead);

if (NULL != pt)

pt->pPre = NULL;

\*ppHead = pt;

main.cpp 测试程序源文件——通过简单的交互信息来测试各个函数功能是否正确。

\#include

\#include "DbLinkList.h"

int main(void)

int flag = 0, length = 0;

int position = 0, value = 0;

pNODE head = NULL;

head = CreateDbLinkList();

flag = IsEmptyDbLinkList(head);

if (flag)

printf("双向链表为空！

");

else

length = GetLengthDbLinkList(head);

printf("双向链表的长度为：%d

", length);

TraverseDbLinkList(head);

printf("请输入要插入节点的位置和元素值(两个数用空格隔开)：");

scanf("%d %d", &position, &value);

flag = InsertEleDbLinkList(head, position, value);

if (flag)

printf("插入节点成功！

");

TraverseDbLinkList(head);

else

printf("插入节点失败！

");

flag = IsEmptyDbLinkList(head);

if (flag)

printf("双向链表为空，不能进行删除操作！

");

else

printf("请输入要删除节点的位置：");

scanf("%d", &position);

flag = DeleteEleDbLinkList(head, position);

if (flag)

printf("删除节点成功！

");

TraverseDbLinkList(head);

else

printf("删除节点失败！

");

FreeMemory(&head);

if (NULL == head)

printf("已成功删除双向链表，释放内存完成！

");

else

printf("删除双向链表失败，释放内存未完成！

");

return 0;

PS：相信对很多人来说链表的相关知识其实不难，很快能把这个程序编出来。但是还是有很多细节的问题要自己编过才知道的，我自己在学习的过程中就遇到过，所以我不让大家再走弯路。

[bbb5657f64350c83b9d2af07bec8584b.png]: /images/20221014/a2cb8c3d53ec42bab5ba720b5243045f.png
[87cfdbc1b803084bf90ac95993fc5b55.png]: /images/20221014/90f9e0b9c3b44f66b691bdbadbc497f4.png