欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 健康 > 养生 > 双向链表的实现

双向链表的实现

2025/5/1 22:17:19 来源：https://blog.csdn.net/2301_80934913/article/details/140871706  浏览:  次   关键词：双向链表的实现

双向链表

  • 1. 双向链表
  • 2. 双向链表的基本操作
  • 3. 实现双线链表的准备
  • 4. 代码的实现
    • 4.1 在头文件中进行函数声明
    • 4.2 链表的初始化
    • 4.3 链表的销毁
    • 4.4 链表的打印
    • 4.5 链表的头插
    • 4.6 链表的头删
    • 4.7 链表的尾插
    • 4.8 链表的尾删
    • 4.9 查找
    • 4.10 在指定位置之后插入
    • 4.11 删除指定位置pos的值
  • 5. 完整代码

1. 双向链表

在这里插入图片描述

  • 一个典型的双向链表节点包含三个部分：

    • 数据域（data），用于存储节点的实际数据。
    • 指向前一个节点的指针（prev）。
    • 指向下一个节点的指针（next）。

2. 双向链表的基本操作

  1. 初始化
  2. 打印
  3. 头插
  4. 尾插
  5. 头删
  6. 尾删
  7. 查找
  8. 在指定位置pos之后插入
  9. 删除指定位置pos
    10.销毁链表

3. 实现双线链表的准备

  • 定义List.h,List.c,Test.c三个文件，头文件包含双向链表相关的数据结构的定义和函数声明，实现文件包含双向链表功能的具体实现细节，测试文件用于测试双向链表的功能。

4. 代码的实现

4.1 在头文件中进行函数声明

#include <stdio.h>
#include<assert.h>
#include<stdlib.h>//创建双向链表
typedef int LTDataType;
typedef struct LTNode {LTDataType data;struct LTNode* next;struct LTNode* prev;
}LTNode;//初始化
void LTInit(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);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之后插入
LTNode* LTInsertBack(LTNode* phead, LTDataType x,LTNode* pos);//删除结点pos
void LTDel(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

4.2 链表的初始化

  • 创建一个哨兵位，不储存有效数据
//初始化
void LTInit(LTNode** phead) 
{//创建一个哨兵位*phead = buyNode(-1);
}

4.3 链表的销毁

  1. 断言检查：
    assert(phead); 这一行用于确保传入的头节点 phead 不是 NULL。防止尝试释放一个不存在的链表。
  2. 初始化遍历指针：
    LTNode* pcur = phead->next; 初始化一个指针 pcur 为头节点 phead 的下一个节点。
  3. 遍历并释放节点：
    • while (pcur != phead) { ... } 开始一个循环，条件是在 pcur 指向的节点不是头节点 phead 时继续执行。
    • LTNode* next = pcur->next; 在释放当前节点之前，保存下一个节点的地址到 next 中。
    • free(pcur); 释放当前节点 pcur 占用的内存。
    • pcur = next; 将 pcur 更新为下一个节点。
  4. 释放头节点：
    • free(phead); 当循环结束时，说明所有中间节点已经被释放，此时释放头节点 phead。
    • 设置头节点为 NULL：
    • phead = NULL; 将头节点指针设置为 NULL。
//销毁
void LTDestroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

4.4 链表的打印

  1. 断言检查；
  2. 处理空链表：
    • if (phead->next == phead) { printf("NULL"); } 这一行检查如果链表为空（即只有一个头节点，且 phead->next 指向自己），则输出 “NULL”。
  3. 初始化遍历指针：
    • LTNode* pcur = phead->next; 初始化一个指针 pcur 为头节点 phead 的下一个节点。这是遍历链表的起点。
  4. 遍历并打印数据：
    • while (pcur != phead) { ... } 开始一个循环，条件是在 pcur 指向的节点不是头节点 phead 时继续执行。
    • printf("%d->", pcur->data); 打印当前节点的数据，后面跟着一个箭头。
    • pcur = pcur->next; 将 pcur 更新为下一个节点。
  5. 结束打印：
    • printf("\n"); 在循环结束后打印换行符，以确保输出格式清晰。
//打印
void LTPrint(LTNode* phead) {assert(phead && phead->next != phead);if (phead->next == phead) {printf("NULL");}LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}

4.5 链表的头插

  1. 断言检查
  2. 创建新节点：
    LTNode* newnode = buyNode(x); 创建一个新节点，其中 x 是要插入的数据。
  3. 更新新节点的指针：
    newnode->next = phead->next; 设置新节点的 next 指针指向原来的头节点的下一个节点。
    newnode->prev = phead; 新节点的 prev 指针指向头节点 phead。
  4. 更新原头节点下一个节点的指针：
    phead->next->prev = newnode; 原头节点下一个节点的 prev 指针指向新节点。
  5. 更新头节点的指针：
    phead->next = newnode; 头节点的 next 指针指向新节点。
//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead -> next = newnode;
}

4.6 链表的头删

  1. 断言检查
  2. 选择要删除的节点：
    LTNode* del = phead->next; 获取要删除的节点，即头节点 phead 的下一个节点。
  3. 更新头节点的指针：
    phead->next = del->next; 将头节点的 next 指针更新为原来被删除节点的下一个节点。
  4. 更新被删除节点的下一个节点的指针：
    del->next->prev = phead; 将原来被删除节点的下一个节点的 prev 指针更新为头节点 phead。
  5. 释放被删除的节点：
    free(del); 释放被删除节点 del 占用的内存。
  6. 设置被删除节点指针为 NULL：
    del = NULL; 将 del 指针设置为 NULL。
//头删
void LTPopFront(LTNode* phead) {assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

4.7 链表的尾插

  1. 断言检查
  2. 创建新节点：
    LTNode* newnode = buyNode(x); 创建一个新节点，其中 x 是要插入的数据。这里假设 buyNode 函数已经被定义好，用于分配新节点所需的内存，并初始化节点的数据成员。
  3. 更新新节点的指针：
    newnode->prev = phead->prev; 新节点的 prev 指针指向原来的尾节点。
    newnode->next = phead; 新节点的 next 指针指向头节点 phead。
  4. 更新原尾节点的 next 指针：
    phead->prev->next = newnode; 原尾节点的 next 指针指向新节点。
  5. 更新头节点的 prev 指针：
    phead->prev = newnode; 头节点的 prev 指针指向新节点。
//尾插
void LTPushBack(LTNode* phead, LTDataType x) 
{assert(phead);LTNode* newnode = buyNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

4.8 链表的尾删

  1. 断言检查
  2. 选择要删除的节点：
    LTNode* del = phead->prev; 获取要删除的节点，即头节点 phead 的前一个节点，也就是链表的尾部节点。
  3. 更新头节点的指针：
    phead->prev = del->prev; 将头节点的 prev 指针更新为原来被删除节点的前一个节点。
  4. 更新被删除节点的前一个节点的指针：
    del->prev->next = phead; 将原来被删除节点的前一个节点的 next 指针更新为头节点 phead。
  5. 释放被删除的节点：
    free(del); 释放被删除节点 del 占用的内存。
  6. 设置被删除节点指针为 NULL：
    del = NULL; 将 del 指针设置为 NULL。
//尾删
void LTPopBack(LTNode* phead) {assert(phead && phead->next != phead);//确保链表不为空LTNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}

4.9 查找

  1. 初始化遍历指针：
    LTNode* pcur = phead->next; 初始化一个指针 pcur 为头节点 phead 的下一个节点。这是遍历链表的起点。
  2. 遍历链表：
    while (pcur != phead) { ... } 开始一个循环，条件是在 pcur 指向的节点不是头节点 phead 时继续执行。
    if (pcur->data == x) { return pcur; } 如果当前节点的数据等于查找的数据 x，则返回当前节点。
    pcur = pcur->next; 将 pcur 更新为下一个节点。
  3. 未找到节点：
    如果循环结束还没有找到匹配的节点，则返回 NULL。
//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

4.10 在指定位置之后插入

  1. 断言检查
  2. 创建新节点：
    LTNode* newnode = buyNode(x); 创建一个新节点，其中 x 是要插入的数据。这里假设 buyNode 函数已经被定义好，用于分配新节点所需的内存，并初始化节点的数据成员。
  3. 更新新节点的指针：
    newnode->next = pos->next; 新节点的 next 指针指向位置节点 pos 的下一个节点。
    newnode->prev = pos; 新节点的 prev 指针指向位置节点 pos。
  4. 更新位置节点的下一个节点的指针：
    pos->next->prev = newnode; 位置节点 pos 的下一个节点的 prev 指针指向新节点。
  5. 更新位置节点的指针：
    pos->next = newnode; 位置节点 pos 的 next 指针指向新节点。
//在指定位置之后插入
LTNode* LTInsertBack(LTNode* phead, LTDataType x,LTNode* pos) {assert(pos);LTNode* newnode = buyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

4.11 删除指定位置pos的值

  1. 断言检查：
  2. 更新节点的前后指针：
    pos->prev->next = pos->next; 节点 pos 的前一个节点的 next 指针指向节点 pos 的下一个节点。
    pos->next->prev = pos->prev; 节点 pos 的下一个节点的 prev 指针指向节点 pos 的前一个节点。
  3. 释放节点：
    free(pos); 释放节点 pos 占用的内存。
  4. 设置节点指针为 NULL：
    pos = NULL; 将 pos 指针置为 NULL。
//删除结点pos
void LTDel(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

5. 完整代码

List.h:

#include <stdio.h>
#include<assert.h>
#include<stdlib.h>//创建双向链表
typedef int LTDataType;
typedef struct LTNode {LTDataType data;struct LTNode* next;struct LTNode* prev;
}LTNode;//初始化
void LTInit(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);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之后插入
LTNode* LTInsertBack(LTNode* phead, LTDataType x,LTNode* pos);//删除结点pos
void LTDel(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

List.c:

#include"List.h"//创建节点
LTNode* buyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//打印
void LTPrint(LTNode* phead) {assert(phead && phead->next != phead);if (phead->next == phead) {printf("NULL");}LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}//初始化
void LTInit(LTNode** phead) 
{//创建一个哨兵位*phead = buyNode(-1);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x) 
{assert(phead);LTNode* newnode = buyNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead -> next = newnode;
}//尾删
void LTPopBack(LTNode* phead) {assert(phead && phead->next != phead);//确保链表不为空LTNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead) {assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之后插入
LTNode* LTInsertBack(LTNode* phead, LTDataType x,LTNode* pos) {assert(pos);LTNode* newnode = buyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除结点pos
void LTDel(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDestroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

Test.c:

#include"List.h"
#include<stdio.h>void Test() {LTNode* plist = NULL;LTInit(&plist);//测试尾插/*LTPushBack(plist, 1);LTPushBack(plist, 3);LTPushBack(plist, 1);LTPushBack(plist, 4);LTPrint(plist);*///测试头插LTPushFront(plist, 0);LTPushFront(plist, 3);LTPushFront(plist, 5);LTPrint(plist);//测试尾删//LTPopBack(plist);//LTPrint(plist);//测试头删LTPopFront(plist);LTPrint(plist);//测试查找LTNode* find = LTFind(plist, 3);if (find != NULL) {printf("找到了！\n");}else {printf("没找到！\n");}//测试在指定位置之后插入LTInsertBack(plist, 8, find);LTPrint(plist);//测试删除结点posLTDel(find);LTPrint(plist);//测试销毁LTDestroy(plist);plist = NULL;
}int main() {Test();return 0;
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词