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

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

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

返回指定位置元素

  • 函数功能：获取一个指定位置的元素
  • 函数参数：list 双向链表句柄 pos 要获取的元素标号
  • 函数返回：获取的结点元素
1. DoubleLinkedListNode* DoubleLinkedList_Get(DoubleLinkedList* list, int pos)
2. {
3.  int i = 0;
4.  DoubleLinkedListHead* pHead = NULL;
5.  DoubleLinkedListNode* pCurrent = NULL;
6.  if ((list == NULL) || (pos < 0))
7.  {
8.    printf("err: (list == NULL) || (pos < 0)\n");
9.    return NULL;
10.   }
11.   pHead = (DoubleLinkedListHead*)list;
12.   pCurrent = &(pHead->head);
13.   for (i = 0; i < pos; i++)
14.   {
15.     pCurrent = pCurrent->next;
16.   }
17.   return pCurrent->next;
18. }

删除结点并返回被删除结点

  • 函数功能：按位置删除一个结点并返回该结点
  • 函数参数：list 双向链表句柄 pos 要删除的链表结点位置
  • 函数返回：被删除的结点
1. DoubleLinkedListNode* DoubleLinkedList_Delete(DoubleLinkedList* list, int pos)
2. {
3.  int i = 0;
4.  DoubleLinkedListHead* pHead = NULL;
5.  DoubleLinkedListNode* pCurrent = NULL;
6.  DoubleLinkedListNode* pNext = NULL;
7.  DoubleLinkedListNode* pTemp = NULL;
8.  if ((list == NULL) || (pos < 0))
9.  {
10.     printf("err: (list == NULL) || (pos < 0)\n");
11.     return NULL;
12.   }
13.   pHead = (DoubleLinkedListHead*)list;
14.   pCurrent = &(pHead->head);
15.   for (i = 0; i < pos; i++)
16.   {
17.     pCurrent = pCurrent->next;
18.   }
19.   pTemp = pCurrent->next;
20.   pNext = pTemp->next;
21.   pCurrent->next = pNext;
22.   if (pNext != NULL)
23.   {
24.     //如果pNext是NULL，不进行pNext->previous的操作
25.     pNext->previous = pCurrent;
26.     if (pCurrent == (DoubleLinkedListNode*)list) //见分析示意图，删除0号结点
27.     {
28.       //在0号位置删除结点，要修正pNext->previous = pCurrent;
29.       pNext->previous = NULL;
30.     }
31.   }
32.   if (pTemp == pHead->slider)
33.   {
34.     pHead->slider = pNext;
35.   }
36.   pHead->length--;
37.   return pTemp;
38. }

删除元素异常分析示意图

（1）普通位置删除

因为需要返回被删除结点，所以，在插入结点的基础上又多了一个辅助指针pTemp用于缓存被删除的结点。

（2）尾部删除

和在尾部插入元素一样，在删除尾部结点的时候，应去掉pNext->previous = pCurrent操作。

（3）头部删除

在头部删除时，和在头部插入一样，应加一步修正，pNext->previous = NULL。

（4）删除唯一结点

删除唯一结点的异常情况已被(2)(3)情况覆盖。

按元素删除结点

  • 函数功能：按元素删除一个结点并返回该结点
  • 函数参数：list 双向链表句柄 node要删除的链表结点元素
  • 函数返回：被删除的结点
1. DoubleLinkedListNode* DoubleLinkedList_DeleteNode(DoubleLinkedList* list, DoubleLinkedListNode* node)
2. {
3.  int i = 0;
4.  DoubleLinkedListHead* pHead = NULL;
5.  DoubleLinkedListNode* pTemp = NULL;
6.  DoubleLinkedListNode* pCurrent = NULL;
7.  if ((list == NULL) || (node == NULL))
8.  {
9.    printf("err: (list == NULL) || (node == NULL)");
10.     return NULL;
11.   }
12.   pHead = (DoubleLinkedListHead*)list;
13.   pCurrent = &(pHead->head);
14.   for (i = 0; i < pHead->length; i++)
15.   {
16.     if (pCurrent == node)
17.     {
18.       pTemp = pCurrent;
19.       break;
20.     }
21.     pCurrent = pCurrent->next;
22.   }
23.   if (pTemp != NULL)
24.   {
25.     if (NULL == DoubleLinkedList_Delete(list, i - 1))
26.     {
27.       printf("DoubleLinkedList_DeleteNode err\n");
28.       return NULL;
29.     }
30.   }
31.   return pTemp;
32. }

重置游标

  • 函数功能：将游标指向第一个元素
  • 函数参数：list 双向链表句柄
  • 函数返回：游标位置
1. DoubleLinkedListNode* DoubleLinkedList_Reset(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("err: list == NULL\n");
7.    return NULL;
8.  }
9.  pHead = (DoubleLinkedListHead*)list;
10.   pHead->slider = pHead->head.next;
11.   return pHead->slider;
12. }

返回当前游标

  • 函数功能：获取游标当前指向的结点
  • 函数参数：list 双向链表句柄
  • 函数返回：游标位置
1. DoubleLinkedListNode* DoubleLinkedList_Current(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("err: list == NULL\n");
7.    return NULL;
8.  }
9.  pHead = (DoubleLinkedListHead*)list;
10.   return pHead->slider;
11. }

游标下移

  • 函数功能：获取游标当前指向的结点，并将游标下移
  • 函数参数：list 双向链表句柄
  • 函数返回：下移前的游标位置
1. DoubleLinkedListNode* DoubleLinkedList_Next(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  DoubleLinkedListNode* pTemp = NULL;
5.  if (list == NULL)
6.  {
7.    printf("err: list == NULL\n");
8.    return NULL;
9.  }
10.   pHead = (DoubleLinkedListHead*)list;
11.   pTemp = pHead->slider;
12.   pHead->slider = pHead->slider->next;
13.   return pTemp;
14. }

游标上移

  • 函数功能：获取游标当前指向的结点，并将游标上移
  • 函数参数：list 双向链表句柄
  • 函数返回：上移前的游标位置
1. DoubleLinkedListNode* DoubleLinkedList_Pre(DoubleLinkedList* list)
2. {
3.  DoubleLinkedListHead* pHead = NULL;
4.  DoubleLinkedListNode* pTemp = NULL;
5.  if (list == NULL)
6.  {
7.    printf("err: list == NULL\n");
8.    return NULL;
9.  }
10.   pHead = (DoubleLinkedListHead*)list;
11.   pTemp = pHead->slider;
12.   pHead->slider = pHead->slider->previous;
13.   return pTemp;
14. }

测试函数

1. #include "DoubleLinkedList.h"
2. 
3. typedef struct MyData
4. {
5.  DoubleLinkedListNode node;
6.  int value;
7. }MyData;
8. 
9. int main()
10. {
11.   int i = 0;
12.   MyData mVector[5];
13.   MyData* m = NULL;
14.   DoubleLinkedList* mList = NULL;
15.   mList = DoubleLinkedList_Create();
16.   if (mList == NULL)
17.   {
18.     printf("DoubleLinkedList_Create() err\n");
19.     return -1;
20.   }
21.   for (i = 0; i < 5; i++)
22.   {
23.     mVector[i].value = 3 + i;
24.     DoubleLinkedList_Insert(mList, (DoubleLinkedListNode*)(&mVector[i]), DoubleLinkedList_Length(mList));
25.   }
26. 
27.   m = (MyData*)DoubleLinkedList_Current(mList);
28.   printf("游标结点：%d\n", m->value);
29. 
30.   for (i = 0; i < DoubleLinkedList_Length(mList); i++)
31.   {
32.     if (i == 0)
33.     {
34.       printf("链表内容：");
35.     }
36.     printf("%d ", ((MyData*)DoubleLinkedList_Get(mList, i))->value);
37.   }
38.   printf("\n");
39. 
40.   DoubleLinkedList_DeleteNode(mList, (DoubleLinkedListNode*)(&mVector[2]));
41. 
42.   for (i = 0; i < DoubleLinkedList_Length(mList); i++)
43.   {
44.     if (i == 0)
45.     {
46.       printf("链表内容：");
47.     }
48.     printf("%d ", ((MyData*)DoubleLinkedList_Get(mList, i))->value);
49.   }
50.   printf("\n");
51. 
52.   for (i = 0; i < DoubleLinkedList_Length(mList); i++)
53.   {
54.     DoubleLinkedList_Delete(mList, i);
55.   }
56. 
57.   DoubleLinkedList_Destroy(mList);
58. 
59.   system("pause");
60.   return 0;
61. }

代码资源已上传，链接如下：

image.png

文章标签：
C语言
API
缓存
关键词：
C语言数据结构
数据结构链表
数据结构c语言
数据结构链表C语言
链表c语言
Mindtechnist
目录
相关文章
土木林森
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
634 1
LucianaiB
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
LucianaiB
197 4
LucianaiB
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
LucianaiB
192 4
LucianaiB
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
LucianaiB
164 4
LucianaiB
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
LucianaiB
226 4
LucianaiB
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
LucianaiB
213 4
羑悻的小杀马特
|
11月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
361 13
羑悻的小杀马特
|
12月前
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
196 13
龙大吉
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
417 5
土木林森
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
499 1

热门文章

最新文章

  • 1
    careercup-栈与队列 3.4
  • 2
    数据结构和算法学习记录——时间复杂度的计算（嵌套循环、大O的渐进表示法、双重循环、常数循环、strchr、冒泡排序、二分查找、斐波那契数列递归）
  • 3
    数据结构复习笔记(5)
  • 4
    linux内核数据结构之kfifo【转】
  • 5
    Oracle 数据结构知多少（一）
  • 6
    数据结构例程——插入排序之直接插入排序
  • 7
    数据结构-第三章-循环顺序队-增设标记法实现各种基本功能
  • 8
    两个栈实现一个队列
  • 9
    栈解决回文
  • 10
    数据结构C#版笔记--顺序表(SeqList)
  • 1
    203. 移除链表元素，707.设计链表，206. 反转链表
    115
  • 2
    24. 两两交换链表中的节点， 19.删除链表的倒数第N个节点 ，面试题 02.07. 链表相交
    204
  • 3
    解析局域网内控制电脑机制：基于 Go 语言链表算法的隐秘通信技术探究
    183
  • 4
    【LeetCode 热题100】23：合并 K 个升序链表（详细解析）（Go语言版）
    341
  • 5
    员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
    210
  • 6
    课时142：链表（清空链表）
    211
  • 7
    课时141：链表（数据删除）
    222
  • 8
    课时140：链表（判断数据是否存在）
    180
  • 9
    课时139：链表（修改指定索引数据）
    213
  • 10
    课时133：链表实现简介
    155

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 传统企业的“+互联网”API服务在京东方的实践
  • 数据资源的基础设施API总线
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 基于Assistant Api的旅游助手
  • 快速体验智能体API应用
    • 下一篇
    附部署代码｜云数据库RDS 全托管 Supabase服务：小白轻松搞定开发AI应用