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

【数据结构】线性表的链式存储（链表）API及实现

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

数据类型及API声明

线性表的链式存储是指每个结点都含有一个指针域，指针域指向下一个结点，这样每个节点包含了自身信息和下一个结点的位置，像链条一样连在一起，线性表的链式存储就是我们常说的链表。一般来说，我们都会给链表加一个表头，表头的指针域指向链表的第一个元素（链表的0号位置），在表头中可以存储链表长度信息。

1. //声明一个链表类型，他可以根据需要转为我们需要的类型
2. typedef void LinkedList;
3. 
4. //链表结点
5. typedef struct LinkedListNode LinkedListNode; 
6. 
7. //链表表头
8. typedef struct LinkedListHead LinkedListHead;
9. 
10. //创建线性表并返回线性表句柄
11. LinkedList* LinkedList_Create();
12. 
13. //销毁线性表（释放内存）
14. void LinkedList_Destroy(LinkedList* lList);
15. 
16. //清空线性表（不释放内存）
17. void LinkedList_Clear(LinkedList* lList);
18. 
19. //返回线性表长度（元素个数）
20. int LinkedList_Length(LinkedList* lList);
21. 
22. //插入元素
23. int LinkedList_Insert(LinkedList* lList, LinkedListNode* node, int pos);
24. 
25. //返回pos处的元素
26. LinkedListNode* LinearList_Get(LinkedList* lList, int pos);
27. 
28. //删除一个结点并返回结点值
29. LinkedListNode* LinearList_Delete(LinkedList* lList, int pos);
30.

链表的API实现

链表结点结构体

链表的结点数据类型是一个结构体，结构体内部只有一个指向本身数据类型的指针，用于存放下一个结点的位置。链表结点只起到连接的作用，它负责把插入的结点一个个链接在链表中，不包含任何业务数据。当我们需要根据自己的业务创建链表时，只需要把我们自己的数据结构体第一个域设置为该链表结点LinkedListNode类型的指针即可，也就是我们的数据结构包含链表结点，并且起始地址相同（链表结点放在数据结构第一个域），这样在做类型转换等操作时，就免去了通过偏移量寻址的操作。

1. struct LinkedListNode
2. {
3.  LinkedListNode* next;
4. };

表头结构体

表头包含一个链表结构体，用于指向链表的0号结点，包含一个数据，用于指示链表长度。

1. struct LinkedListHead
2. {
3.  LinkedListNode head;
4.  int length;
5. };

创建链表并返回链表句柄

  • 函数功能：创建一个链表并返回链表句柄，其实就是创建一个表头
  • 函数参数：无，链式结构不需要提前分配内存，而线性表的顺序结构需要提前分配内存
  • 函数返回：表头
1. LinkedList* LinkedList_Create()
2. {
3.  LinkedList* head = NULL;
4.  head = (LinkedList*)malloc(sizeof(LinkedListHead));
5.  if (head == NULL)
6.  {
7.    printf("err: head = (LinkedList*)malloc(sizeof(LinkedListHead))\n");
8.    return NULL;
9.  }
10.   memset(head, 0, sizeof(LinkedListHead));
11.   return head;
12. }

销毁链表

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

清空链表

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

返回链表长度

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

插入元素

  • 函数功能：在链表中插入一个元素，被插入的元素已经在主调函数分配好内存，只需把链表结点LinkedListNode串接起来即可
  • 函数参数：lList 链表句柄 node 待插入元素 pos 插入位置
  • 函数返回：成功返回0
1. int LinkedList_Insert(LinkedList* lList, LinkedListNode* node, int pos)
2. {
3.  int i = 0;
4.  LinkedListHead* pList = NULL;
5.  LinkedListNode* pCurrent = NULL;
6.  if ((lList == NULL) || (node == NULL) || (pos < 0))
7.  {
8.    printf("err: (lList == NULL) || (node == NULL) || (pos < 0)\n");
9.    return -1;
10.   }
11.   pList = (LinkedListHead*)lList;
12.   pCurrent = &(pList->head);
13.   for (i = 0; i < pos; i++)
14.   {
15.     pCurrent = pCurrent->next;
16.   }
17.   node->next = pCurrent->next;
18.   pCurrent->next = node;
19.   pList->length++;
20.   return 0;
21. }

插入元素示意图

 

插入元素时需要借助一个辅助指针变量pCurrent，pCurrent为当前指针位置，初始状态他应该指向表头，当我们需要在pos号位置插入元素时，就将pCurrent后移pos位，比如要在2号位置插入，将pCurrent后移2次，那么pCurrent将指在1号结点处，而1号结点的next域指向2号结点，这时只需要把待插入结点插在pCurrent后面即可完成插入。插入时，应先将2号结点的位置赋给待插入结点的指针域，这样做是为了防止后续结点（2号结点）丢失，然后再把待插入结点赋给pCurrent的指针域即可完成整个插入过程。

返回指定位置元素

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

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

  • 函数功能：删除一个结点并返回该结点
  • 函数参数：lList 链表句柄 pos 要删除的链表结点元素
  • 函数返回：被删除的结点
1. LinkedListNode* LinearList_Delete(LinkedList* lList, int pos)
2. {
3.  int i = 0;
4.  LinkedListHead* pList = NULL;
5.  LinkedListNode* pCurrent = NULL;
6.  LinkedListNode* pTemp = NULL;
7.  if ((lList == NULL) || (pos < 0))
8.  {
9.    printf("err: lList == NULL \n");
10.     return NULL;
11.   }
12.   pList = (LinkedListHead*)lList;
13.   pCurrent = &(pList->head);
14.   for (i = 0; i < pos; i++)
15.   {
16.     pCurrent = pCurrent->next;
17.   }
18.   pTemp = pCurrent->next;
19.   pCurrent->next = pTemp->next;
20.   pList->length--;
21.   return pTemp;
22. }

删除元素示意图

删除结点需要借助两个辅助指针，一个pCurrent指示当前结点，其作用类似于插入节点中的pCurrent，另一个pTemp用于保存被删除结点，删除时，只需要pCurrent的指针域指向pTemp指针域的内容即可完成删除。

测试函数

1. #include "LinkedList.h"
2. 
3. typedef struct
4. {
5.  LinkedListNode* node;
6.  int len;
7.  char* str;
8. }MyStr;
9. 
10. int main()
11. {
12.   int i = 0;
13.   LinkedList* mList = NULL;
14.   MyStr s1, s2, s3, s4, s5;
15.   MyStr* temp = NULL;
16.   s1.str = "hello";
17.   s2.str = "Linked";
18.   s3.str = "List";
19.   s4.str = "C";
20.   s5.str = "!";
21. 
22.   mList = LinkedList_Create();
23.   LinkedList_Insert(mList, (LinkedListNode*)&s5, 0);
24.   LinkedList_Insert(mList, (LinkedListNode*)&s4, 0);
25.   LinkedList_Insert(mList, (LinkedListNode*)&s3, 0);
26.   LinkedList_Insert(mList, (LinkedListNode*)&s2, 0);
27.   LinkedList_Insert(mList, (LinkedListNode*)&s1, 0);
28. 
29.   for (i = 0; i < 5; i++)
30.   {
31.     temp = (MyStr*)LinearList_Get(mList, i);
32.     printf("%s ", temp->str);
33.   }
34.   printf("\n");
35. 
36.   for (i = 0; i < 5; i++)
37.   {
38.     temp = (MyStr*)LinearList_Delete(mList, 0);
39.     printf("str: %s\n", temp->str);
40.   }
41. 
42.   printf("len: %d\n", LinkedList_Length(mList));
43. 
44.   LinkedList_Destroy(mList);
45. 
46.   system("pause");
47.   return 0;
48. }

具体代码资源已上传，可在下面的链接免费下载

image.png

文章标签：
API
存储
关键词：
数据结构存储
数据结构链表
线性表链表
数据结构线性表
数据结构线性表链表
Mindtechnist
目录
相关文章
XIAZHI
|
2月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
67 4
RossyYan
|
2天前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储（头歌实践教学平台习题）【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系，邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵，预期输出为Prim算法求解结果。通关代码提供了完整的C++实现，包括输入、构建和打印邻接矩阵与邻接表的功能。
RossyYan
24 10
RossyYan
|
3天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
20 5
三三是该溜子
|
17天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
29 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
2月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
79 5
XIAZHI
|
2月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
57 0
ephemerals__
|
2月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
86 0
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
262 9
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
42 1
RossyYan
|
2天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
112 75