AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】双向链表的API及C语言实现（一）

2023-02-08 100
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】双向链表的API及C语言实现

数据类型及API声明

双向链表是指链表的每个结点有两个指针域，一个next指针指向后继结点，一个previous指针指向前驱结点。另外，双向链表也包含一个游标slider。

1. //链表句柄
2. typedef void DoubleLinkedList;
3. 
4. //链表结点
5. typedef struct DoubleLinkedListNode DoubleLinkedListNode;
6. 
7. //链表头
8. typedef struct DoubleLinkedListHead DoubleLinkedListHead;
9. 
10. DoubleLinkedList* DoubleLinkedList_Create();
11. 
12. void DoubleLinkedList_Destroy(DoubleLinkedList* list);
13. 
14. void DoubleLinkedList_Clear(DoubleLinkedList* list);
15. 
16. int DoubleLinkedList_Length(DoubleLinkedList* list);
17. 
18. int DoubleLinkedList_Insert(DoubleLinkedList* list, DoubleLinkedListNode* node, int pos);
19. 
20. DoubleLinkedListNode* DoubleLinkedList_Get(DoubleLinkedList* list, int pos);
21. 
22. DoubleLinkedListNode* DoubleLinkedList_Delete(DoubleLinkedList* list, int pos);
23. 
24. //按元素值删除指定某个结点
25. DoubleLinkedListNode* DoubleLinkedList_DeleteNode(DoubleLinkedList* list, DoubleLinkedListNode* node);
26. 
27. //重置游标
28. DoubleLinkedListNode* DoubleLinkedList_Reset(DoubleLinkedList* list);
29. 
30. //获取当前游标
31. DoubleLinkedListNode* DoubleLinkedList_Current(DoubleLinkedList* list);
32. 
33. //游标下移
34. DoubleLinkedListNode* DoubleLinkedList_Next(DoubleLinkedList* list);
35. 
36. //游标上移
37. DoubleLinkedListNode* DoubleLinkedList_Pre(DoubleLinkedList* list);

双向链表的API实现

双向链表结点结构体

链表结点包含了指向后继结点的指针和指向前驱结点的指针。

1. struct DoubleLinkedListNode
2. {
3.  DoubleLinkedListNode* previous;
4.  DoubleLinkedListNode* next;
5. };

表头结构体

表头包含一个链表结点结构体head，用于指向链表的0号结点，包含一个游标slider，用于指示当前结点，包含一个长度length，用于指示链表元素个数。

1. struct DoubleLinkedListHead
2. {
3.  DoubleLinkedListNode head;
4.  DoubleLinkedListNode* slider;
5.  int length;
6. };

创建双向链表并返回双向链表的句柄

  • 函数功能：创建一个双向链表并返回双向链表句柄，其实就是创建一个表头
  • 函数参数：无
  • 函数返回：表头
1. DoubleLinkedList* DoubleLinkedList_Create()
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  pHead = (DoubleLinkedListHead*)malloc(sizeof(DoubleLinkedListHead));
5.  if (pHead == NULL)
6.  {
7.    printf("pHead = (DoubleLinkedListHead*)malloc(sizeof(DoubleLinkedListHead)) err\n");
8.    return NULL;
9.  }
10.   memset(pHead, 0, sizeof(DoubleLinkedListHead));
11.   return pHead;
12. }

销毁双向链表

  • 函数功能：销毁双向链表就是释放表头资源，销毁双向链表前需要逐个删除链表结点
  • 函数参数：双向链表的句柄
  • 函数返回：无
1. void DoubleLinkedList_Destroy(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("err: list == NULL\n");
7.    return;
8.  }
9.  pHead = (DoubleLinkedListHead*)list;
10.   free(pHead);
11. }

清空双向链表

  • 函数功能：返回到双向链表刚创建的状态，即表头指针域指向NULL，长度置为0
  • 函数参数：双向链表的句柄
  • 函数返回：无
1. void DoubleLinkedList_Clear(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("err: list == NULL\n");
7.    return;
8.  }
9.  pHead = (DoubleLinkedListHead*)list;
10.   pHead->head.next = NULL;
11.   pHead->head.previous = NULL;
12.   pHead->slider = NULL;
13.   pHead->length = 0;
14. }

返回双向链表元素个数

  • 函数功能：获取双向链表长度，即结点个数
  • 函数参数：双向链表句柄
  • 函数返回：结点个数
1. int DoubleLinkedList_Length(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("err: list == NULL\n");
7.    return -1;
8.  }
9.  pHead = (DoubleLinkedListHead*)list;
10.   return pHead->length;
11. }

插入元素

  • 函数功能：在双向链表中插入一个元素，被插入的元素已经在主调函数分配好内存，只需把链表结点DoubleLinkedListNode串接起来即可
  • 函数参数：list 双向链表句柄 node 待插入元素 pos 插入位置
  • 函数返回：成功返回0
1. int DoubleLinkedList_Insert(DoubleLinkedList* list, DoubleLinkedListNode* node, int pos)
2. {
3.  int i = 0;
4.  DoubleLinkedListHead* pHead = NULL;
5.  DoubleLinkedListNode* pCurrent = NULL;
6.  DoubleLinkedListNode* pNext = NULL;
7.  if ((list == NULL) || (node == NULL) || (pos < 0))
8.  {
9.    printf("err: (list == NULL) || (node == NULL) || (pos < 0)\n");
10.     return -1;
11.   }
12.   pHead = (DoubleLinkedListHead*)list;
13.   pCurrent = &(pHead->head);
14.   for (i = 0; i < pos; i++)
15.   {
16.     pCurrent = pCurrent->next;
17.   }
18.   pNext = pCurrent->next;
19.   node->next = pNext;
20.   pCurrent->next = node;
21.   node->previous = pCurrent;
22.   if (pNext != NULL) //见分析示意图：在尾部插入
23.   {
24.     //在尾部插入的时候，pNext = NULL
25.     pNext->previous = node;
26.   }
27.   if (pCurrent == (DoubleLinkedListNode*)list) //见分析示意图，在0号位置插入
28.   {
29.     //在0号位置插入，要修正node->previous = pCurrent;
30.     node->previous = NULL;
31.   }
32.   if (pHead->length == 0)
33.   {
34.     pHead->slider = node;
35.   }
36.   pHead->length++;
37.   return 0;
38. }

插入元素时的异常处理

（1）普通位置插入

因为双向链表既有后继结点的指针，又有前驱结点的指针，所以需要两个辅助指针pCurrent和pNext。pCurrent指针为当前指针，初始位置指向head头结点，然后根据传入的参数pos往后移动pos步，要插入的元素就是当前pCurrent后面的位置，在插入前应保存原来的pos位处的结点，也就是pCurrent->next，因为被插入的node结点应放在pCurrent->next结点的前驱指针域中，所以就有了pNext = pCurrent->next的操作。

（2）尾部插入

尾部插入时会有一个异常情况，那就是pNext指向NULL，而NULL没有指针域，所以在尾部插入元素时，应该去掉pNext->previous = node这一步。

（3）头部位置插入

在头部插入，应该对node的previous域做修正，使它指向NULL，即node->previous = NULL。

（4）首次插入

首次插入的异常情况刚好是在头部插入和在尾部插入两种情况的综合，即(2)(3)中的分析。


文章标签：
C语言
API
关键词：
数据结构c语言
C语言数据结构
数据结构链表
数据结构双向链表
API数据结构
Mindtechnist
目录
相关文章
土木林森
|
29天前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树：一场数据结构与算法的华丽舞蹈，让你的程序效率飙升，直击性能巅峰！"
【8月更文挑战第20天】红黑树是自平衡二叉查找树，通过旋转和重着色保持平衡，确保高效执行插入、删除和查找操作，时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中，节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架，用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
土木林森
47 1
2的n次方_
|
13天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
31 10
【数据结构】链表从实现到应用，保姆级攻略
小徐在进步
|
7天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
25 8
小徐在进步
|
7天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
21 8
小徐在进步
|
9天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
25 6
小徐在进步
|
9天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
26 6
小徐在进步
|
9天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
34 5
小徐在进步
|
9天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
13 3
小徐在进步
|
9天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
35 3
小徐在进步
|
9天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
16 2