devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构与算法】顺序表与链表（单链表和双链表）超详解图示与源码。_顺序表单链表双链表

作者：IT小白 | 2024-08-01 19:32:59

赞

踩

顺序表单链表双链表

                                                  

大家好，今天我们来学习数据结构中的顺序表与链表！源码在最后附上

首先我们先来认识一下顺序表：

                                     

**如上图所示：很多人会以为数组就是顺序表，顺序表就是数组，这种理解时错误的。

数组：

数组是相同数据类型的元素按一定顺序排列的的集合。数组中的元素存储在一个连续性的内存块中，并通过索引来访问。

简单的说，数组是在物理空间中连续存储的相同数据类型的元素的集合。

而顺序表：

顺序表，全名顺序存储结构，是线性表的一种。（线性表（linear list）是数据结构的一种，一个线性表是 n 个具有相同特性的数据元素的有限序列。线性表在逻辑上是线性结构，也就说是连续的一条直线，但是在物理结构上并不一定是连续的。常见的线性表：顺序表、链表、栈、队列、字符串等。）

顺序表不仅要求数据在逻辑上是连续的一条直线，还要求用一段物理地址连续的存储单元以存储表中数据元素，一般情况下采用数组存储。

总结：

顺序表是在计算机内存中以数组的形式保存的线性表，只能从头开始连续存储。
此处将「数组」理解为物理结构，「顺序表」理解为逻辑结构比较合理
我们可以用数组实现顺序表，但我们同样可以用数组实现二叉树、队列等结构，因此不能直接认为顺序表就是数组
在顺序表中我们可以定义表中元素个数、表空间大小等变量，在数组中是没有的

                     

首先我们来学习一下顺序表的静态存储：

                                         

而顺序表的静态存储又存在明显的缺陷和不足：

不知道需要给确定的多少个空间，N给小了不够用，N给大了会浪费。

那么如何解决这个问题呢？

在这里我们使用malloc来动态开辟空间，再使用realloc来进行空间的管理。

顺序表的动态存储：

                                   

在这里我们要注意realloc扩容存在异地扩容和原地扩容俩种情况；

注意地址，当你realloc的空间没有那么大时，这里就是原地扩容：

                         

注意地址，当你realloc的空间很大的时候，就会异地扩容：

          

这里先让我们简单的来实现顺序表的几个功能：（完整功能最后附上源码）

实现顺序表的头插，即往前边插进去数据：

 

实现顺序表中间插入数据：

实现顺序表的删除：

通过以上学习，我们大概了解了顺序表的一些基础知识，那么顺序表是否存在一些缺点呢？

顺序表的缺点：

1.尾部插入数据还不错，但是头部和中间插入删除数据，效率低下，需要挪动数据。 

2.满了之后只能扩容，而扩容是有一定的消耗的，扩容一般是存在一定的空间浪费（假如空间100已经满了，扩容到200，只需要插入120个数据，那么就有80个浪费掉了）

3.一次扩的多了，可能浪费掉了；一次扩的少了，有需要频繁去扩容。

                                                      

接下来让我们来学习链表： 

链表：链表采用链式存储结构，其内存空间不连续

而链表分为单链表和双链表，我们先来学习单链表：

          

                          

它是由一个一个结点结合在一起的，而每个节点的地址没有关联，都是随机的，东一个西一个。

注意单链表的最后一个结点指向NULL;

这里我们简单的定义一个单链表：

                                        

如何去访问链表里的各个结点呢：我们定义一个cur指针指向单链表的头节点，然后通过cur->next来依次访问剩下的结点，如果cur==NULL，说明链表访问完了。

接下来我们来实现单链表几个基本的功能：（完整源码结尾附上）

单链表的尾插：

                           

这里需要额外注意：因为phead是plist的临时拷贝，使用要注意二级指针与一级指针的使用，当然不使用二级指针也是可以 ，也有不同的写法，这里这样写是让大家小心注意一下其中的大坑。

单链表的头插：

 

单链表的尾删：

                                        

                                                       

需要注意，这里需要区分一个结点和多个结点的不同情况。

单链表的头删：

                            

这里需要注意：我们的思路是把头节点的指向原本头结点的下一个结点，然后还需要free掉原本的头节点，这里会出现一种很常见的错误：

                             

先free掉tmp后，就没办法再进行头结点的链接，丢失了地址。

而正确的写法：（大家注意区分）

                                

关于链表还有一个知识点，就是哨兵位：

                           

哨兵位就是在头节点的前面给它再加一个结点，让它充当头节点，但它不存储具体的数据，只是更方便进行头插头删等操作，哨兵位的含金量不是很高，有时候方便用来刷OJ题，这里大家简单了解下，有兴趣的朋友自己敲敲代码试一下把。

单链表我们就学到这里，接下来我们学习一下双链表：

这里我们先再来了解下链表有哪些分类：

        

我们注意到，单链表和双链表的区别是：单链表一个结点只能指向下一个结点，而双边表一个结点可以指向前一个结点也可以指向后一个结点。

而循环链表的特殊之处则是尾结点直接指向了头节点，实现了一个循环。

接下来我们先来比较一下俩种链表：

我们主要学习一下带头双向循环链表： 

根据上面单链表的学习，我们简单写几个功能让加强大家对双向链表的理解：

带头双向循环链表的尾插：

                         

我们可以明显感受到，双向循环链表的数据处理只需要几个简单的指向就可以简单完成；

带头双向循环链表的尾删：

                                 

知识的分享就结束了，接下来附上顺序表与链表的源码：（因为内容较多，所以不是很全，但有具体的框架，大家可以根据自己的需要进行补全）

顺序表：

SeqList.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6.  
  7. typedef int SLDataType;
  8.  
  9. typedef struct SeqList
  10. {
  11. 	SLDataType* a;
  12. 	int size;      // 有效数据
  13. 	int capacity;  // 空间容量
  14. }SL;
  15.  
  16. void SLInit(SL* psl);
  17. void SLDestroy(SL* psl);
  18.  
  19. void SLPrint(SL* psl);
  20. void SLCheckCapacity(SL* psl);
  21.  
  22. // 头尾插入删除
  23. void SLPushBack(SL* psl, SLDataType x);
  24. void SLPushFront(SL* psl, SLDataType x);
  25. void SLPopBack(SL* psl);
  26. void SLPopFront(SL* psl);
  27.  
  28. // 任意下标位置的插入删除
  29. void SLInsert(SL* psl, int pos, SLDataType x);
  30. void SLErase(SL* psl, int pos);
  31.

 SeqList.c

  1. #include"SeqList.h"
  2.  
  3. void SLInit(SL* psl)
  4. {
  5. 	assert(psl);
  6.  
  7. 	psl->a = NULL;
  8. 	psl->size = 0;
  9. 	psl->capacity = 0;
  10. }
  11.  
  12. void SLDestroy(SL* psl)
  13. {
  14. 	assert(psl);
  15.  
  16. 	if (psl->a != NULL)
  17. 	{
  18. 		free(psl->a);
  19. 		psl->a = NULL;
  20. 		psl->size = 0;
  21. 		psl->capacity = 0;
  22. 	}
  23. }
  24.  
  25. void SLPrint(SL* psl)
  26. {
  27. 	assert(psl);
  28.  
  29. 	for (int i = 0; i < psl->size; i++)
  30. 	{
  31. 		printf("%d ", psl->a[i]);
  32. 	}
  33. 	printf("\n");
  34. }
  35.  
  36. void SLCheckCapacity(SL* psl)
  37. {
  38. 	assert(psl);
  39.  
  40. 	if (psl->size == psl->capacity)
  41. 	{
  42. 		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  43. 		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType)*newCapacity);
  44. 		if (tmp == NULL)
  45. 		{
  46. 			perror("realloc fail");
  47. 			return;
  48. 		}
  49.  
  50. 		psl->a = tmp;
  51. 		psl->capacity = newCapacity;
  52. 	}
  53. }
  54.  
  55. // 10：37
  56. void SLPushBack(SL* psl, SLDataType x)
  57. {
  58. 	assert(psl);
  59.  
  60. 	SLCheckCapacity(psl);
  61.  
  62. 	psl->a[psl->size] = x;
  63. 	psl->size++;
  64. }
  65.  
  66. void SLPushFront(SL* psl, SLDataType x)
  67. {
  68. 	assert(psl);
  69.  
  70. 	SLCheckCapacity(psl);
  71.  
  72. 	// 挪动数据
  73. 	int end = psl->size - 1;
  74. 	while (end >= 0)
  75. 	{
  76. 		psl->a[end + 1] = psl->a[end];
  77. 		--end;
  78. 	}
  79.  
  80. 	psl->a[0] = x;
  81. 	psl->size++;
  82. }
  83.  
  84. void SLPopBack(SL* psl)
  85. {
  86. 	assert(psl);
  87.  
  88. 	// 空
  89. 	// 温柔的检查
  90. 	/*if (psl->size == 0)
  91. 	{
  92. 		return;
  93. 	}*/
  94.  
  95. 	// 暴力检查
  96. 	assert(psl->size > 0);
  97.  
  98. 	//psl->a[psl->size - 1] = -1;
  99. 	psl->size--;
  100. }
  101.  
  102. // 10:47
  103. void SLPopFront(SL* psl)
  104. {
  105. 	assert(psl);
  106.  
  107. 	// 暴力检查
  108. 	assert(psl->size > 0);
  109.  
  110. 	int begin = 1;
  111. 	while (begin < psl->size)
  112. 	{
  113. 		psl->a[begin - 1] = psl->a[begin];
  114. 		++begin;
  115. 	}
  116.  
  117. 	psl->size--;
  118. }
  119.  
  120. // 注意pos是下标
  121. // size是数据个数，看做下标的话，他是最后一个数据的下一个位置
  122. void SLInsert(SL* psl, int pos, SLDataType x)
  123. {
  124. 	assert(psl);
  125. 	assert(pos >= 0 && pos <= psl->size);
  126.  
  127. 	SLCheckCapacity(psl);
  128.  
  129. 	// 挪动数据
  130. 	int end = psl->size - 1;
  131. 	while (end >= pos)
  132. 	{
  133. 		psl->a[end + 1] = psl->a[end];
  134. 		--end;
  135. 	}
  136.  
  137. 	psl->a[pos] = x;
  138. 	psl->size++;
  139. }
  140.  
  141. void SLErase(SL* psl, int pos)
  142. {
  143. 	assert(psl);
  144. 	assert(pos >= 0 && pos < psl->size);
  145.  
  146. 	// 挪动覆盖
  147. 	int begin = pos + 1;
  148. 	while (begin < psl->size)
  149. 	{
  150. 		psl->a[begin - 1] = psl->a[begin];
  151. 		++begin;
  152. 	}
  153.  
  154. 	psl->size--;
  155. }

Test.c：

  1. #include<stdio.h>
  2. #include"SeqList.h"
  3.  
  4.  
  5. void TestSL1()
  6. {
  7. 	SL sl;
  8. 	SLInit(&sl);
  9. 	SLPushBack(&sl, 1);
  10. 	SLPushBack(&sl, 2);
  11. 	SLPushBack(&sl, 3);
  12. 	SLPushBack(&sl, 4);
  13. 	SLPushBack(&sl, 5);
  14. 	SLPushBack(&sl, 6);
  15. 	SLPushBack(&sl, 7);
  16. 	SLPushBack(&sl, 8);
  17. 	SLPushBack(&sl, 9);
  18. 	SLPrint(&sl);
  19.  
  20. 	SLPushFront(&sl, 10);
  21. 	SLPushFront(&sl, 20);
  22. 	SLPushFront(&sl, 30);
  23. 	SLPushFront(&sl, 40);
  24. 	SLPrint(&sl);
  25.  
  26. 	SLDestroy(&sl);
  27. }
  28.  
  29. void TestSL2()
  30. {
  31. 	SL sl;
  32. 	SLInit(&sl);
  33. 	SLPushBack(&sl, 1);
  34. 	SLPushBack(&sl, 2);
  35. 	SLPushBack(&sl, 3);
  36. 	SLPushBack(&sl, 4);
  37. 	SLPushBack(&sl, 5);
  38. 	SLPrint(&sl);
  39.  
  40. 	SLPopBack(&sl);
  41. 	SLPrint(&sl);
  42.  
  43. 	SLPopBack(&sl);
  44. 	SLPopBack(&sl);
  45. 	SLPopBack(&sl);
  46. 	SLPopBack(&sl);
  47. 	SLPrint(&sl);
  48.  
  49.  
  50.  
  51. 	SLPushFront(&sl, 10);
  52. 	SLPushFront(&sl, 20);
  53. 	SLPushFront(&sl, 30);
  54. 	SLPushFront(&sl, 40);
  55. 	SLPrint(&sl);
  56.  
  57. 	SLDestroy(&sl);
  58. }
  59.  
  60. void TestSL3()
  61. {
  62. 	SL sl;
  63. 	SLInit(&sl);
  64. 	SLPushBack(&sl, 1);
  65. 	SLPushBack(&sl, 2);
  66. 	SLPushBack(&sl, 3);
  67. 	SLPushBack(&sl, 4);
  68. 	SLPushBack(&sl, 5);
  69. 	SLPrint(&sl);
  70.  
  71. 	SLPopFront(&sl);
  72. 	SLPrint(&sl);
  73.  
  74. 	SLPopFront(&sl);
  75. 	SLPrint(&sl);
  76.  
  77. 	SLPopFront(&sl);
  78. 	SLPrint(&sl);
  79.  
  80. 	SLPopFront(&sl);
  81. 	SLPrint(&sl);
  82.  
  83. 	SLPopFront(&sl);
  84. 	SLPrint(&sl);
  85.  
  86. 	//SLPopFront(&sl);
  87. 	//SLPrint(&sl);
  88. }
  89.  
  90. void TestSL4()
  91. {
  92. 	
  93.  
  94. 	SL sl;
  95. 	SLInit(&sl);
  96. 	SLPushBack(&sl, 1);
  97. 	SLPushBack(&sl, 2);
  98. 	SLPushBack(&sl, 3);
  99. 	SLPushBack(&sl, 4);
  100. 	SLPushBack(&sl, 5);
  101. 	SLPrint(&sl);
  102.  
  103. 	SLInsert(&sl, 2, 20);
  104. 	SLPrint(&sl);
  105.  
  106. 	SLInsert(&sl, 6, 20);
  107. 	SLPrint(&sl);
  108.  
  109. 	SLInsert(&sl, 0, 20);
  110. 	SLPrint(&sl);
  111.  
  112. 	SLInsert(&sl, 10, 20);
  113. 	SLPrint(&sl);
  114.  
  115. 	SLDestroy(&sl);
  116. }
  117.  
  118. void TestSL5()
  119. {
  120. 	SL sl;
  121. 	SLInit(&sl);
  122. 	SLPushBack(&sl, 1);
  123. 	SLPushBack(&sl, 2);
  124. 	SLPushBack(&sl, 3);
  125. 	SLPushBack(&sl, 4);
  126. 	SLPushBack(&sl, 5);
  127. 	SLPrint(&sl);
  128.  
  129. 	SLErase(&sl, 3);
  130. 	SLPrint(&sl);
  131.  
  132. 	SLErase(&sl, 3);
  133. 	SLPrint(&sl);
  134.  
  135. 	//SLErase(&sl, 3);
  136. 	//SLPrint(&sl);
  137. }
  138.  
  139. int main()
  140. {
  141. 	TestSL5();
  142. 	return 0;
  143. }

单链表： 

 SList.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. typedef int SLNDataType;
  7.  
  8. // Single List
  9. typedef struct SListNode
  10. {
  11. 	SLNDataType val;
  12. 	struct SListNode* next;
  13. }SLNode;
  14.  
  15. void SLTPrint(SLNode* phead);
  16. void SLTPushBack(SLNode** pphead, SLNDataType x);
  17. void SLTPushFront(SLNode** pphead, SLNDataType x);
  18.  
  19. void SLTPopBack(SLNode** pphead);
  20. void SLTPopFront(SLNode** pphead);
  21.  
  22. SLNode* SLTFind(SLNode* phead, SLNDataType x);
  23.  
  24. // posǰ
  25. SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
  26.  
  27. // ɾposλ
  28. void SLTErase(SLNode** pphead, SLNode* pos);
  29. void SLTDestroy(SLNode** pphead);

SList.c

  1. #include"SList.h"
  2.  
  3. void SLTPrint(SLNode* phead)
  4. {
  5. 	SLNode* cur = phead;
  6. 	while (cur != NULL)
  7. 	{
  8. 		printf("%d->", cur->val);
  9. 		cur = cur->next;
  10. 	}
  11. 	printf("NULL\n");
  12. }
  13.  
  14. SLNode* CreateNode(SLNDataType x)
  15. {
  16. 	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  17. 	if (newnode == NULL)
  18. 	{
  19. 		perror("malloc fail");
  20. 		exit(-1);
  21. 	}
  22.  
  23. 	newnode->val = x;
  24. 	newnode->next = NULL;
  25. 	return newnode;
  26. }
  27.  
  28. void SLTPushBack(SLNode** pphead, SLNDataType x)
  29. {
  30. 	SLNode* newnode = CreateNode(x);
  31.  
  32. 	if (*pphead == NULL)
  33. 	{
  34. 		*pphead = newnode;
  35. 	}
  36. 	else
  37. 	{
  38. 		// 找尾
  39. 		SLNode* tail = *pphead;
  40. 		while (tail->next != NULL)
  41. 		{
  42. 			tail = tail->next;
  43. 		}
  44.  
  45. 		tail->next = newnode;
  46. 	}	
  47. }
  48.  
  49. void SLTPushFront(SLNode** pphead, SLNDataType x)
  50. {
  51. 	SLNode* newnode = CreateNode(x);
  52. 	newnode->next = *pphead;
  53. 	*pphead = newnode;
  54. }
  55.  
  56. void SLTPopBack(SLNode** pphead)
  57. {
  58. 	// 温柔的检查
  59. 	//if (*pphead == NULL)
  60. 	//	return;
  61.  
  62. 	// 空
  63. 	assert(*pphead);
  64.  
  65. 	// 1、一个节点
  66. 	// 2、一个以上节点
  67. 	if ((*pphead)->next == NULL)
  68. 	{
  69. 		free(*pphead);
  70. 		*pphead = NULL;
  71. 	}
  72. 	else
  73. 	{
  74. 		// 找尾
  75. 		/*SLNode* prev = NULL;
  76. 		SLNode* tail = *pphead;
  77. 		while (tail->next != NULL)
  78. 		{
  79. 			prev = tail;
  80. 			tail = tail->next;
  81. 		}
  83. 		free(tail);
  84. 		tail = NULL;
  86. 		prev->next = NULL;*/
  87.  
  88. 		SLNode* tail = *pphead;
  89. 		while (tail->next->next != NULL)
  90. 		{
  91. 			tail = tail->next;
  92. 		}
  93.  
  94. 		free(tail->next);
  95. 		tail->next = NULL;
  96. 	}
  97. }
  98.  
  99. void SLTPopFront(SLNode** pphead)
  100. {
  101.  
  102. 	assert(*pphead);
  103.  
  104. 	
  105. 	SLNode* tmp = *pphead;
  106. 	free(tmp);
  107. 	*pphead = (*pphead)->next;
  108. }

Test.c

  1. #include"SList.h"
  2.  
  3. void TestSLT1()
  4. {
  5. 	SLNode* plist = NULL;
  6. 	SLTPushBack(&plist, 1);
  7. 	SLTPushBack(&plist, 2);
  8. 	SLTPushBack(&plist, 3);
  9. 	SLTPushBack(&plist, 4);
  10. 	SLTPrint(plist);
  11.  
  12. 	SLTPopBack(&plist);
  13. 	SLTPrint(plist);
  14.  
  15. 	SLTPopBack(&plist);
  16. 	SLTPrint(plist);
  17.  
  18. 	SLTPopBack(&plist);
  19. 	SLTPrint(plist);
  20.  
  21. 	SLTPopBack(&plist);
  22. 	SLTPrint(plist);
  23.  
  24. 	//SLTPopBack(&plist);
  25. 	//SLTPrint(plist);
  26. }
  27.  
  28. void TestSLT2()
  29. {
  30. 	SLNode* plist = NULL;
  31. 	SLTPushFront(&plist, 1);
  32. 	SLTPushFront(&plist, 2);
  33. 	SLTPushFront(&plist, 3);
  34. 	SLTPushFront(&plist, 4);
  35. 	SLTPrint(plist);
  36.  
  37. 	SLTPopFront(&plist);
  38. 	SLTPrint(plist);
  39.  
  40.  
  41. 	//SLNode* pos = SLTFind(plist, 3);
  42. 	//SLTInsert(&plist, pos, 30);
  43. }
  44.  
  45. //int main()
  46. //{
  47. //	TestSLT2();
  48. //
  49. //	return 0;
  50. //}
  51.  
  52. struct ListNode
  53. {
  54. 	struct ListNode* next;
  55. 	int val;
  56. };
  57.  
  58. struct ListNode* removeElements(struct ListNode* head, int val)
  59. {
  60. 	struct ListNode* prev = NULL;
  61. 	struct ListNode* cur = head;
  62.  
  63. 	//while(cur != NULL)
  64. 	while (cur)
  65. 	{
  66. 		if (cur->val == val)
  67. 		{
  68. 			struct ListNode* next = cur->next;
  69. 			free(cur);
  70.  
  71. 			if (prev)
  72. 				prev->next = next;
  73.  
  74. 			cur = next;
  75. 		}
  76. 		else
  77. 		{
  78. 			prev = cur;
  79. 			cur = cur->next;
  80. 		}
  81. 	}
  82.  
  83. 	return head;
  84. }
  85.  
  86. int main()
  87. {
  88. 	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
  89. 	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
  90. 	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
  91. 	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
  92. 	n1->val = 7;
  93. 	n2->val = 7;
  94. 	n3->val = 7;
  95. 	n4->val = 7;
  96.  
  97. 	n1->next = n2;
  98. 	n2->next = n3;
  99. 	n3->next = n4;
  100. 	n4->next = NULL;
  101.  
  102. 	struct ListNode* head = removeElements(n1, 7);
  103.  
  104. 	return 0;
  105. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/915598
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号