AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】链表-C语言版（一）

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

顺序表缺点

顺序表随机访问很方便，但是也会有不足啊：

（1）挪动数据时间开销较大：头部/中间的插入删除，需要挪动后面的所有数据，时间复杂度为O(N)

（2）增容有代价：增容需要重新申请空间，拷贝数据，释放旧空间，系统消耗不小

（3）空间浪费：增容一般增至原来的2倍大空间，会有空间浪费，假如当前容量为100，满了以后增容到200，再继续插入了5个数据，后面没有插入数据了，这就浪费了95个空间。

不存在扩容代价、不存在空间浪费、按需申请空间、头部或者中间插入数据而不需要挪动数据的链表可以解决以上问题。


链表的概念和结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

注意：

（1）链式结构在逻辑上连续，逻辑上不一定连续。（逻辑结构是想象的，物理结构是内存中实际存储的）。

（2）结点一般从堆上申请。

（3）堆上申请的空间时按照一定策略分配的，两次申请的空间可能连续也可能不连续。


链表的分类

有8种链表结构 ：

（1）单向和双向

（2）带头单链表和不带头单链表

（3）非循环链表和循环链表

以上3种分类的链表一共有2*2*2=8种组合，最实用的有两种：

（1）无头单向非循环链表：结构简单，一般不会用来单独存储数据。十几种更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。

（2）带头双向循环链表：结构最复杂，一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。虽然结构复杂，但是使用代码实现以后会发现该结构会带来很多优势，实现反而简单。


链表的实现

如果需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针。

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. 
4. void swap(int* pa, int* pb)//用两个指针作为形参接收两个地址
5. {
6.  int temp = *pa;
7.  *pa = *pb;
8.  *pb = temp;
9. }
10. 
11. int main()
12. {
13.   int a = 3;
14.   int b = 5;
15.   swap(&a, &b);//实参是两个int的地址
16.   printf("a = %d\n", a);
17.   printf("a = %d\n", b);
18.   return 0;
19. }

同理，对于链表的增删，如果需要改变指针指向，就要传指针的地址，即二级指针。

链表实现：

025-SList.h 链表函数定义

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. 
4. typedef int SLTDataType;
5. 
6. typedef struct SListNode
7. {
8.  SLTDataType data;
9.  struct SListNode* next;
10. }SLTNode;
11. 
12. //单向+不带头+非循环
13. 
14. //打印
15. void SListPrint(SLTNode* plist);
16. 
17. //尾插(需要改变指针指向，就要传指针的地址，即二级指针，如需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针)
18. void SListPushBack(SLTNode** plist,SLTDataType x);
19. 
20. //头插
21. void SListPushFront(SLTNode** plist, SLTDataType x);
22. 
23. //尾删
24. void SListPopBack(SLTNode** plist);
25. 
26. //头删
27. void SListPopFront(SLTNode** plist);
28. 
29. //单链表查找
30. SLTNode* SListFind(SLTNode* plist, SLTDataType x);
31. 
32. //在pos之后插入x
33. void SListInsertAfter(SLTNode* pos, SLTDataType x);
34. 
35. //在pos之前插入x
36. void SListInsertBefore(SLTNode** plist,SLTNode* pos, SLTDataType x);
37. 
38. //在pos之前插入x，没有头的情况:后插一个值为x的节点，再跟前面的结点值交换。
39. void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x);
40. 
41. //删除后一个节点
42. void SListEraseAfter(SLTNode* pos);
43. 
44. //删除当前位置
45. void SListEraseCur(SLTNode** plist, SLTNode* pos);

025-SList.c 链表函数实现

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. 
7. #include "025-SList.h"
8. 
9. //打印
10. void SListPrint(SLTNode* plist)
11. {
12.   SLTNode* cur = plist;
13. 
14.   //找空节点，找到后不再打印
15.   while (cur != NULL)
16.   {
17.     printf("%d->", cur->data);
18. 
19.     //让cur指向下一个节点
20.     cur = cur->next;
21.   }
22. 
23.   printf("NULL\n");
24. }
25. 
26. //创建新节点
27. SLTNode* BuySLTNode(SLTDataType x)
28. {
29.   //申请空间
30.   SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
31.   if (node == NULL)
32.   {
33.     return NULL;
34.   }
35. 
36.   //数据赋值
37.   node->data = x;
38. 
39.   //指针赋值
40.   node->next = NULL;
41. 
42.   return node;
43. }

（1）尾插：

1. //尾插
2. void SListPushBack(SLTNode** pplist, SLTDataType x)
3. {
4.  SLTNode* newNode = BuySLTNode(x);
5. 
6.  //不能使用tail->next != NULL直接作为判断条件，因为有可能是空链表，对空指针解引用会造成非法访问，因此要分两种情况
7. 
8.  if (*pplist == NULL)//链表为空
9.  {
10.     *pplist = newNode;
11.   }
12.   else //链表不为空
13.   {
14.     SLTNode* tail = *pplist;
15. 
16.     //找尾节点
17.     while (tail->next != NULL)
18.     {
19.       tail = tail->next;
20.     }
21.     tail->next = newNode;
22.   }
23. }

（2）头插，不需要区分空链表和非空链表

1. //头插
2. void SListPushFront(SLTNode** pplist, SLTDataType x)
3. {
4.  SLTNode* newNode = BuySLTNode(x);
5.  newNode->next = *pplist;//新节点的下一个指向第一个节点
6.  *pplist = newNode;//链表指向新节点
7. }

（3）尾删

1. //尾删
2. void SListPopBack(SLTNode** pplist)
3. {
4.  //链表为空
5.  if (*pplist == NULL)
6.  {
7.    return;
8.  }
9.  //链表只有一个结点
10.   else if ((*pplist)->next == NULL)
11.   {
12.     free(*pplist);
13.     *pplist = NULL;
14.   }
15.   //链表有多个结点
16.   else
17.   {
18.     SLTNode* pre = NULL;//后面用该结点指向尾节点的前驱结点，因为删除为节点后，尾节点的前驱结点的后继结点要赋为空指针
19.     SLTNode* tail = *pplist;
20. 
21.     //寻找最后一个结点，循环结束后，tail为尾结点，pre为尾结点的前驱结点
22.     while (tail->next != NULL)
23.     {
24.       pre = tail;
25.       tail = tail->next;
26.     }
27. 
28. 
29.     free(tail);
30.     tail = NULL;
31. 
32.     pre->next = NULL;
33.   }
34. }

（4）头删

1. //头删
2. void SListPopFront(SLTNode** pplist)
3. {
4.  if (*pplist == NULL)
5.  {
6.    return;
7.  }
8.  else
9.  {
10.     SLTNode* next = (*pplist)->next;//保存后一个节点
11.     free(*pplist);
12.     *pplist = next;//链表指向下一个节点
13.   }
14. }

（5）单链表查找

1. //单链表查找
2. SLTNode* SListFind(SLTNode* plist, SLTDataType x)
3. {
4.  SLTNode* cur = plist;
5.  while (cur)//没找到就往后继续走
6.  {
7.    if (cur->data == x)
8.    {
9.      return cur;//找到了就返回
10.     }
11.     cur = cur->next;
12.   }
13.   return NULL;
14. }

（6） 在pos之后插入

1. //在pos之后插入
2. void SListInsertAfter(SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);//插入需要先创建结点
7.  newNode->next = pos->next;//新节点的下一个指向pos的下一个
8.  pos->next = newNode;//pos的下一个指向新节点
9. }

（7）在pos之前插入x

1. //在pos之前插入x
2. void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);
7. 
8.  //第一个节点就是pos，即头插
9.  if (pos == *pplist)
10.   {
11.     newNode->next = pos;
12.     *pplist = newNode;
13.   }
14.   else
15.   {
16.     SLTNode* prev = NULL;//用来记录pos的前一个结点
17.     SLTNode* cur = *pplist;
18. 
19.     while (cur != pos)//找pos
20.     {
21.       prev = cur;
22.       cur = cur->next;
23.     }
24. 
25.     newNode->next = cur;//新节点的下一个指向pos，此时跳出while循环的cur=pos
26.     prev->next = newNode;//前一个结点的下一个指向新节点
27.   }
28. }

（8）在pos之前插入x，没有头(plist)：后插一个值为x的节点，再跟前面的结点值交换

1. //在pos之前插入x，没有头(plist)的情况:后插一个值为x的节点，再跟前面的结点值交换。
2. void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);
7. 
8.  //后插新节点
9.  newNode->next = pos->next;
10.   pos->next = newNode;
11. 
12.   //将新结点的值和pos的值进行交换
13.   SLTDataType temp = pos->data;
14.   newNode->data = temp;
15.   pos->data = x;
16. }

（9）删除后一个结点

1. //删除后一个节点
2. void SListEraseAfter(SLTNode* pos)
3. {
4.  assert(pos);
5. 
6.  if (pos->next == NULL)
7.  {
8.    return;
9.  }
10.   SLTNode* next = pos->next;
11.   pos->next = next->next;//pos的下一个指向pos的下一个结点的下一个结点
12.   free(next);
13.   next = NULL;
14. }

（10） 删除当前位置

1. //删除当前位置
2. void SListEraseCur(SLTNode** pplist, SLTNode* pos)
3. {
4.  assert(pos);
5.  SLTNode* prev = NULL;
6.  SLTNode* cur = *pplist;
7.  while (cur != pos)//寻找pos
8.  {
9.    prev = cur;
10.     cur = cur->next;
11.   }
12.   prev->next = cur->next;//前一个结点的下一个指向当前结点即pos的下一个
13.   free(cur);
14.   cur = NULL;
15. }

025-test.c 测试代码

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. #include<assert.h>
4. 
5. #include "025-SList.h"
6. 
7. void TestSList1()
8. {
9.  SLTNode* plist = NULL;
10.   SListPushBack(&plist, 1);
11.   SListPushBack(&plist, 2);
12.   SListPushBack(&plist, 3);
13.   SListPushBack(&plist, 4);
14. 
15.   SListPrint(plist);
16. 
17.   SListPushFront(&plist, 0);
18.   SListPrint(plist);
19. 
20.   SListPopBack(&plist);
21.   SListPrint(plist);
22.   SListPopBack(&plist);
23.   SListPrint(plist);
24.   SListPopBack(&plist);
25.   SListPrint(plist);
26.   SListPopBack(&plist);
27.   SListPrint(plist);
28. 
29. }
30. void TestSList2()
31. {
32.   SLTNode* plist = NULL;
33.   SListPushBack(&plist, 1);
34.   SListPushBack(&plist, 2);
35.   SListPushBack(&plist, 3);
36.   SListPushBack(&plist, 4);
37.   SListPrint(plist);
38. 
39.   SListPopFront(&plist);
40.   SListPopFront(&plist);
41.   SListPopFront(&plist);
42.   SListPopFront(&plist);
43.   SListPopFront(&plist);
44.   SListPrint(plist);
45. }
46. 
47. void TestSList3()
48. {
49.   SLTNode* plist = NULL;
50.   SListPushBack(&plist, 1);
51.   SListPushBack(&plist, 2);
52.   SListPushBack(&plist, 3);
53.   SListPushBack(&plist, 4);
54.   SListPrint(plist);
55. 
56.   SLTNode* pos = SListFind(plist, 3);
57.   if (pos)
58.   {
59.     //单链表查找兼具修改功能
60.     pos->data = 100;
61.     printf("找到了\n");
62.   }
63.   else
64.   {
65.     printf("没找到\n");
66.   }
67. 
68.   SListPrint(plist);
69. }
70. 
71. void TestSList4()
72. {
73.   SLTNode* plist = NULL;
74.   SListPushBack(&plist, 1);
75.   SListPushBack(&plist, 2);
76.   SListPushBack(&plist, 3);
77.   SListPushBack(&plist, 4);
78.   SListPrint(plist);
79. 
80.   SLTNode* pos = SListFind(plist, 3);
81.   SListInsertAfter(pos, 300);
82.   SListPrint(plist);
83. 
84.   SListInsertBefore(&plist, pos,400);
85.   SListPrint(plist);
86. 
87.   SListEraseCur(&plist, pos);
88.   SListPrint(plist);
89. }
90. 
91. int main()
92. {
93.   TestSList4();
94. 
95.   return 0;
96. }

执行结果：


文章标签：
存储
关键词：
数据结构链表
C语言链表
C语言数据结构
数据结构c语言
数据结构链表C语言
玲娜贝儿～
目录
相关文章
土木林森
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
58 1
XIAZHI
|
2月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
57 4
XIAZHI
|
2月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
51 4
XIAZHI
|
2月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
54 4
XIAZHI
|
2月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
56 4
XIAZHI
|
2月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
47 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
39 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例，包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法，涵盖了链表操作的多种场景，旨在帮助读者深入理解链表数据结构的应用，提升算法设计与编程能力。
XIAZHI
48 4
RossyYan
|
1天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
19 5
三三是该溜子
|
15天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
27 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充

热门文章

最新文章

  • 1
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 2
    基于OHCI的USB主机 —— UFI数据结构2
  • 3
    数据结构示例——堆排序过程
  • 4
    SpringBoot高级篇Redis之Set数据结构使用姿势
  • 5
    初学python数据结构-切片
  • 6
    HashMap 之底层数据结构和扩容机制
  • 7
    今天给同学写5个数据结构算法的题...感觉很有价值的几个题..感兴趣的坐下。。
  • 8
    5.[数据结构和算法分析笔记]树 Tree
  • 9
    数据结构思维 第一章 接口
  • 10
    [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序
  • 1
    链表遍历，链表查找和统计节点，链表插入新节点，链表删除节点，链表修改指定节点,链表头插法，尾插法总结
    51
  • 2
    剑指offer（牛客）——合并两个排序的链表
    51
  • 3
    剑指offer（牛客）——从尾到头打印链表
    47
  • 4
    每日一题：力扣328. 奇偶链表
    56
  • 5
    数据结构与算法 数组和链表
    53
  • 6
    leetcode代码记录（移除链表元素
    39
  • 7
    单链表的应用
    65
  • 8
    数据结构第二课 -----线性表之单向链表
    62
  • 9
    数据结构第三课 -----线性表之双向链表
    57
  • 10
    链表练习题-2
    58

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅