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

数据结构之双向链表的实现

news 2025/7/8 4:43:09

目录

一、双向线链表的原理

1.为什么要存在双向链表？

2.双向链表的结构

二、双向链表的实现

1.链表的定义

2.链表的初始化

3.链表的长度

4.获取指定元素e的位置

5.获取指定位置index的元素

6.插入指定位置的元素

7.删除指定位置的元素

8.清空链表

9.打印链表的中元素的值

三、打印测试功能

1.测试

2.结果输出

3.总代码

一、双向线链表的原理

        在上一节我们讲了数据结构之线性表（单链表的实现），这一节我们来讲解双向链表的实现，以及双向链表的优缺点。

1.为什么要存在双向链表？

        我们都知道每存在一种数据结构都是解决某项问题的。我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗？当然可以，只不过需要加点东西而已。

        我们在单链表中，有了 next 指针，这就使得我们要查找下一结点的时间复杂度为 O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是 O(n) 了，因为我们每次都要从头开始遍历查，所以就有了双向链表。

2.双向链表的结构

        如下图所示：双向链表（double linkedlist）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另 一个指向直接前驱。        

二、双向链表的实现

        双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如 求长度的 ListLength，查找元素的 GetElem，获得元素位置的 LocateElem 等，这 些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

1.链表的定义

         主要是定义一些功能常量和单链表的结构，和之前的数据结构的文章一样。代码如下：

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct DuLNode
{struct DuLNode* prior;ElemType data;struct DuLNode* next;
}*DuLinkList;
2.链表的初始化

          这里链表的初始化我选择的是用户输入的形式，用户输入一个值就往链表添加一个用户输入的元素，当用户输入的值为 -1 时，代表用户输入结束。 

// 链表的初始化
DuLinkList InitList(DuLinkList L)
{int data, size;DuLinkList Last, p;L = (DuLinkList)malloc(sizeof(DuLNode));L->prior = NULL;L->next = NULL;Last = L;printf("请输入节点的值（输入-1表示输入完成）:\n");size = 0;printf("当前链表的大小为：%d\n",size);while (true){if (scanf("%d", &data) != 1)break;if (data == -1)break;p = (DuLinkList)malloc(sizeof(DuLNode));if (p == NULL){printf("内存不足！\n");break;}p->data = data;p->prior = Last;p->next = NULL;Last->next = p;Last = p;}Last->next = NULL;return L;
}
3.链表的长度

        求链表的长度和单链表相同，设置一个变量  length++ ，然后 while 遍历，最后返回 length。 

// 链表的长度
int ListLength(DuLinkList L)
{int length = 0;if (L == NULL) return length;if (L->next == NULL) return length;while (L->next){L = L->next;length++;}return length;
}
4.获取指定元素e的位置

        不断用while遍历链表，当有data 与 e 相同时，打印当前 index。

// 获取指定元素的位置
int GetElem(DuLinkList L, ElemType e)
{int found = 0;int index = 1;if (L == NULL) return ERROR;if (L->next == NULL) return ERROR;L = L->next;do{if (L->data == e){printf("找到一个节点，位置在%d\n", index);found = 1;}L = L->next;index++;} while (L != NULL);if (found == 0){printf("指定位置的元素一个都没有找到\n");return ERROR;}return OK;
}
5.获取指定位置index的元素

        定义一个变量，进行index操作，判断是否与指定位置 i 相同，获取其节点值。

// 根据位置获取元素
int GetElembyIndex(DuLinkList L, int index, ElemType* e)
{int i = 0;if (L == NULL || L->next == NULL || index < 1) return ERROR;while (L->next && i < index){L = L->next;i++;}if (i == index){*e = L->data;return OK;}return ERROR;
}
6.插入指定位置的元素

        和单链表操作几乎一样，就是多了一个指针域的赋值。    

// 插入链表
Status ListInsert(DuLinkList* L, int i, ElemType e)
{DuLinkList inserted, temp;int index = 1;int length = ListLength(*L);if ((*L == NULL) || (i > length + 1) || (i <= 0)) return ERROR;temp = *L;while (temp->next != NULL && index < i){  temp = temp->next;index++;}inserted = (DuLinkList)malloc(sizeof(DuLNode));inserted->data = e;inserted->next = temp->next;inserted->prior = temp;temp->next = inserted;if (temp->next) temp->next->prior = inserted;return OK;
}
7.删除指定位置的元素

        如图所示。

// 删除指定位置链表
Status ListDelete(DuLinkList* L, int i, ElemType* e)
{int length = ListLength(*L);int index = 0;if (i <= 0 || L == NULL || (*L)->next == NULL || i > length) return ERROR;DuLinkList temp = *L;while (temp->next != NULL && index < i){temp = temp->next;index++;}temp->prior->next = temp->next;if (temp->next){temp->next->prior = temp->prior;} *e = temp->data;free(temp);return OK;
}
8.清空链表

        链表的清空操作。

// 清空链表
void ListClear(DuLinkList* L)
{DuLinkList p, q;p = (*L)->next;while (p){q = p->next;free(p);p = q;}(*L)->next = NULL;
}
9.打印链表的中元素的值

         功能比较简单，通过不断遍历打印其节点的data值。

// 打印链表
void print(DuLinkList L)
{if (L == NULL || L->next == NULL){printf("链表为空！！\n");return;}int index = 0;while (L->next){if (index > 0){printf("->");}L = L->next;printf("%d", L->data);index = 1;}printf("\n");
}

三、打印测试功能

1.测试

        测试主要为测试以上的功能是否可以实现。

void test()
{ElemType e;int index;DuLinkList L{};L = InitList(L);printf("双链表的长度：%d\n", ListLength(L));print(L);printf("请输入想要知道的第几个位置上的元素:");scanf("%d", &index);GetElembyIndex(L, index, &e);printf("该位置上的数字为：%d\n", e);printf("请输入想知道某个元素在哪个位置上：");scanf("%d", &e);GetElem(L, e);printf("请输入你想在第几个位置上插入元素：");scanf("%d", &index);printf("请输入你想插入元素的值：");scanf("%d", &e);ListInsert(&L, index, e);print(L);printf("输入你想删除元素的位置：");scanf("%d", &index);ListDelete(&L, index, &e);printf("删除元素的值为：%d\n", e);print(L);printf("清空列表\r\n");ListClear(&L);printf("列表的长度为：%d\n", ListLength(L));
}
2.结果输出

         结果输出如图所示：

3.总代码

        总代码如下：

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct DuLNode
{struct DuLNode* prior;ElemType data;struct DuLNode* next;
}*DuLinkList;// 链表的初始化
DuLinkList InitList(DuLinkList L)
{int data, size;DuLinkList Last, p;L = (DuLinkList)malloc(sizeof(DuLNode));L->prior = NULL;L->next = NULL;Last = L;printf("请输入节点的值（输入-1表示输入完成）:\n");size = 0;printf("当前链表的大小为：%d\n",size);while (true){if (scanf("%d", &data) != 1)break;if (data == -1)break;p = (DuLinkList)malloc(sizeof(DuLNode));if (p == NULL){printf("内存不足！\n");break;}p->data = data;p->prior = Last;p->next = NULL;Last->next = p;Last = p;}Last->next = NULL;return L;
}// 链表的长度
int ListLength(DuLinkList L)
{int length = 0;if (L == NULL) return length;if (L->next == NULL) return length;while (L->next){L = L->next;length++;}return length;
}// 获取指定元素的位置
int GetElem(DuLinkList L, ElemType e)
{int found = 0;int index = 1;if (L == NULL) return ERROR;if (L->next == NULL) return ERROR;L = L->next;do{if (L->data == e){printf("找到一个节点，位置在%d\n", index);found = 1;}L = L->next;index++;} while (L != NULL);if (found == 0){printf("指定位置的元素一个都没有找到\n");return ERROR;}return OK;
}// 根据位置获取元素
int GetElembyIndex(DuLinkList L, int index, ElemType* e)
{int i = 0;if (L == NULL || L->next == NULL || index < 1) return ERROR;while (L->next && i < index){L = L->next;i++;}if (i == index){*e = L->data;return OK;}return ERROR;
}// 插入链表
Status ListInsert(DuLinkList* L, int i, ElemType e)
{DuLinkList inserted, temp;int index = 1;int length = ListLength(*L);if ((*L == NULL) || (i > length + 1) || (i <= 0)) return ERROR;temp = *L;while (temp->next != NULL && index < i){  temp = temp->next;index++;}inserted = (DuLinkList)malloc(sizeof(DuLNode));inserted->data = e;inserted->next = temp->next;inserted->prior = temp;temp->next = inserted;if (temp->next) temp->next->prior = inserted;return OK;
}// 删除指定位置链表
Status ListDelete(DuLinkList* L, int i, ElemType* e)
{int length = ListLength(*L);int index = 0;if (i <= 0 || L == NULL || (*L)->next == NULL || i > length) return ERROR;DuLinkList temp = *L;while (temp->next != NULL && index < i){temp = temp->next;index++;}temp->prior->next = temp->next;if (temp->next){temp->next->prior = temp->prior;} *e = temp->data;free(temp);return OK;
}// 清空链表
void ListClear(DuLinkList* L)
{DuLinkList p, q;p = (*L)->next;while (p){q = p->next;free(p);p = q;}(*L)->next = NULL;
}// 打印链表
void print(DuLinkList L)
{if (L == NULL || L->next == NULL){printf("链表为空！！\n");return;}int index = 0;while (L->next){if (index > 0){printf("->");}L = L->next;printf("%d", L->data);index = 1;}printf("\n");
}void test()
{ElemType e;int index;DuLinkList L{};L = InitList(L);printf("双链表的长度：%d\n", ListLength(L));print(L);printf("请输入想要知道的第几个位置上的元素:");scanf("%d", &index);GetElembyIndex(L, index, &e);printf("该位置上的数字为：%d\n", e);printf("请输入想知道某个元素在哪个位置上：");scanf("%d", &e);GetElem(L, e);printf("请输入你想在第几个位置上插入元素：");scanf("%d", &index);printf("请输入你想插入元素的值：");scanf("%d", &e);ListInsert(&L, index, e);print(L);printf("输入你想删除元素的位置：");scanf("%d", &index);ListDelete(&L, index, &e);printf("删除元素的值为：%d\n", e);print(L);printf("清空列表\r\n");ListClear(&L);printf("列表的长度为：%d\n", ListLength(L));
}
int main()
{test();return 0;
}

http://www.mrgr.cn/news/21168.html

相关文章：

  • CRUD的最佳实践，联动前后端，包含微信小程序，API，HTML等(三)
  • erlang学习：用ETS和DETS存储数据3，保存元组到磁盘
  • 别再羡慕别人啦，四种方法轻松打造自己的IP形象
  • 《机器学习》 基于SVD的矩阵分解 推导、案例实现
  • 【鸿蒙HarmonyOS NEXT】调用后台接口及List组件渲染
  • k8s技术架构
  • Linux日志-sar日志
  • AI基础 L2 Agents1
  • 类和对象（中）
  • 灰光模块，彩光模块-介绍
  • Zotero引用参考文献常见问题及解决方法
  • 鸿蒙轻内核M核源码分析系列十一(1) 信号量Semaphore
  • 监理工程师专业划分-注册监理工程师每人最多可以申请两个专业注册
  • 兴业小知识|什么 法拍房保证金还有不予退回的情况
  • Lenze伦茨E82ZBC, E82ZBB E82ZMBRB安装说明手测
  • 考研英语作文高频20大句式总结
  • 如何测试一个算法
  • 使用Selenium WebDriver捕获网络请求
  • 牛客刷题之JZ31.栈的压入、弹出序列（C++）
  • Pytest插件pytest-selenium-让自动化测试更简洁