• 【数据结构与算法】顺序表

    作者：旧梦拾遗186

    专栏：数据结构成长日记

     

    每日励志：

    生活从来都不会辜负谁，觉得丧的时候就要让自己忙起来，世界没有变小，我们一定要让自己越来越可爱的活下去，不要消耗生命，而是享受生活。

    前言：

    今天小编带大家学习数据结构当中的顺序表

    目录

    一.线性表

    二.顺序表 

    2.1概念及结构

    2.2 接口实现

    SeqList.h

    SeqList.c

    test.c 

    简化的顺序表代码 SeqList.c

    一.线性表

    线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
    线性表在逻辑上是线性结构，也就说是连续的一条直线 。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储

     

     

    二.顺序表 

    2.1概念及结构

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

    对于顺序表：我们可以分为静态顺序表和动态顺序表。

    对于静态顺序表，我们该如何去定义呢?

     

    我们可以看到，对于静态顺序表而言，里面的数组元素个数是固定的，不够灵活

    对于动态顺序表：

    1. //动态顺序表
    2. typedef int SLDataType;
    3. typedef struct SeqLIst
    4. {
    5. 	SLDataType* a;
    6. 	int size;//存储数据的个数
    7. 	int capacity;//存储空间的大小
    8. }SL;

     

    这里有一个问题

    对于应该扩容多少究竟扩多少倍这个问题?
    我们这里的代码实现默认的是扩容2倍（实际上空间满之后，不一定是扩容2倍）：因为2倍比较合适，并不是必须一定是2倍，2倍2不会导致扩容过大或过小，如果扩容一次扩多了，将会存在空间浪费，扩少了，会导致频繁扩容，会导致效率损失。这并不是我们想要的

    同时，还有另外一个问题，需要我们进行探讨一下：

    在进行删除相关操作（如下面会说到的头删操作时）后面剩余的空间要不要进行缩容?
    对于删除顺序表没有缩容的概念，虽然可以缩容，都是我们不会去缩容，缩容要付出极大的代价。对于realloc我们知道扩容有2种情况(取决于后面的空间够不够)：一种是原地扩容，返回原来的地址，另一种是异地扩容，返回的不是同一个地址。

    如果我们扩容扩的比原来还小呢？会不会进行缩容?可能会原地缩容或者异地缩容

    对于删除数据后面剩余的空间有点多，我们确实可以用realloc进行缩容，但是付出的代价有点多：可能会在新空间开一个空间，将其里面的数据进行拷贝，将旧空间释放掉。这就是要付出的代价，这是性能的代价。
    有没有想过，缩容之后，如果又要插入数据，这时候我们又得扩容，扩容又得申请新的空间，在释放旧空间，在插入数据。这不就是在反复横跳。况且现在计算机的空间也没那么少
    我们可以认为缩容是一种以时间换空间的方案。不缩容是在以空间换时间，而不缩容后面插入数据我们可能都不需要进行扩容，这就是不缩容的优势。虽然缩容是可以的，但是没有系统会去做。
     

    2.2 接口实现

    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了，空 间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现 动态顺序表 。

     

    我们将会实现的功能是：

    初始化顺序表、销毁顺序表、尾插数据、头插数据、尾删数据、头删数据、查找数据、在某个位置插入数据、在某个位置删除数据、修改数据。以及中间实现过程中会涉及到的打印数据、扩容操作等。

    很显然，在实现某个位置插入数据的功能的时候，我们就能用在某个位置插入函数取代尾插和头插操作

    在实现某个位置删除数据的功能，我们就能用这个函数取代尾删和头删操作

    面对这么多的操作，我们采用模块化设计，分为3个板块，同时，我们应该在边实现功能函数的过程中边进行调试操作，不要让自己的代码出现过多的错误。我们可以在主函数的部分通过设计void TestSeqList()里面存放一些功能函数来看看自己的代码是否能够达到预期的效果，这点能够大大提高我们代码的准确性。
     

    SeqList.h

    1. #pragma once
    2.  
    3. //#ifndef __SEQLIST_H__
    4. //#define __SEQLIST_H__
    5. //#endif
    6.  
    7. #include 
    8. #include 
    9. #include 
    10.  
    11. 静态顺序表
    12. //#define N 10
    13. //typedef int SLDataType;
    14. //struct SeqList
    15. //{
    16. //	SLDataType a[N];
    17. //	int size;
    18. //};
    19.  
    20.  
    21. //动态顺序表
    22. typedef int SLDataType;
    23. typedef struct SeqLIst
    24. {
    25. 	SLDataType* a;
    26. 	int size; //存储数据的个数
    27. 	int capacity;//存储空间的大小
    28. }SL;
    29.  
    30.  
    31. //初始化
    32. void SLInit(SL* psl);
    33.  
    34.  
    35. //销毁
    36. void SLDestory(SL* psl);
    37.  
    38. //打印
    39. void SLPrint(const SL* psl);
    40.  
    41.  
    42. //尾插头插 尾删头删
    43.  
    44. //尾插
    45. void SLPushBack(SL* psl, SLDataType x);
    46.  
    47. //头插
    48. void SLPushFront(SL* psl, SLDataType x);
    49.  
    50. //尾删
    51. void SLPopBack(SL* psl);
    52.  
    53. //头删
    54. void SLPopFront(SL* psl);
    55.  
    56.  
    57. //查找
    58. int SLFind(SL* psl, SLDataType x);
    59.  
    60.  
    61. //插入
    62. void SLInsert(SL* psl, size_t pos, SLDataType x);
    63.  
    64.  
    65. //删除
    66. void SLErase(SL* psl, size_t pos);
    67.  
    68. //修改
    69. void SLModify(SL* psl, size_t pos, SLDataType x);

    SeqList.c

    这一部分就是对SeqList.h里面声明的函数进行实现的部分，是最为重要的部分，对于这一部分的函数，千万不要把SeList.h里面的函数全部实现完再去测试，那样子会大大提高工作量，出现错误很不好找，最好的办法就是写完一个函数去测试一个函数，调试看看有没有bug。这点至关重要。

    1. #include "SeqList.h"
    2. void SLPrint(const SL* psl)
    3. {
    4. 	assert(psl);
    5. 	for (int i = 0; i < psl->size; i++)
    6. 	{
    7. 		printf("%d ", psl->a[i]);
    8. 	}
    9. 	//注意换行
    10. 	printf("\n");
    11. }
    12.  
    13. void SLInit(SL* psl)
    14. {
    15. 	assert(psl);
    16. 	psl->a = NULL;
    17. 	psl->capacity = psl->size = 0;
    18. }
    19.  
    20.  
    21. void SLDestory(SL* psl)
    22. {
    23. 	assert(psl);
    24. 	if (psl->a)
    25. 	{
    26. 		free(psl->a);
    27. 		psl->a = NULL;
    28. 		psl->capacity = psl->size = 0;
    29. 	}
    30. }
    31.  
    32. //扩容,后面会用到扩容这个操作，我们干脆将其封装成一个函数即可
    33. void SLCheckCapacity(SL* psl)
    34. {
    35. 	assert(psl);
    36. 	//检查容量
    37. 	if (psl->size == psl->capacity)
    38. 	{
    39. 		//如果是0那就容量初始化为4，否则就增加2倍
    40. 		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    41.  
    42. 		//注意是sizeof(SLDataType)*newCapacity
    43. 		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
    44. 		//注意realloc会出现的情况
    45. 		if (NULL == tmp)
    46. 		{
    47. 			perror("realloc fail");
    48. 			return;
    49. 			//exit(-1);
    50. 		}
    51. 		psl->a = tmp;
    52. 		psl->capacity = newCapacity;
    53. 	}
    54. }
    55.  
    56. //尾插
    57. void SLPushBack(SL* psl, SLDataType x)
    58. {
    59. 	assert(psl);
    60. 	SLCheckCapacity(psl);
    61. 	psl->a[psl->size] = x;
    62. 	psl->size++;
    63. 	//SLInsert(psl, psl->size, x);//直接调用SLInsetrt函数也可以实现尾插
    64. }
    65.  
    66. //头插
    67. void SLPushFront(SL* psl, SLDataType x)
    68. {
    69. 	assert(psl);
    70. 	SLCheckCapacity(psl);
    71. 	int end = psl->size-1;
    72. 	while (end>=0)
    73. 	{
    74. 		psl->a[end+1] = psl->a[end];
    75. 		--end;
    76. 	}
    77. 	psl->a[0] = x;
    78. 	psl->size++;
    79.  
    80. 	//SLInsert(psl, 0, x);//直接调用SLInsert也可以实现头插
    81.  
    82. }
    83.  
    84. //尾删
    85. void SLPopBack(SL* psl)
    86. {
    87. 	assert(psl);
    88.  
    89. 	//温柔的检查——元素的合理性
    90. 	/*if (psl->size == 0)
    91. 	{
    92. 		return;
    93. 	}*/
    94.  
    95. 	//暴力的检查，直接报错——元素的合理性
    96. 	assert(psl->size > 0);
    97. 	psl->size--;
    98. 	//SLErase(psl, psl->size - 1);//直接调用SLErase也可以实现尾删
    99. }
    100.  
    101. //头删
    102. void SLPopFront(SL* psl)
    103. {
    104. 	assert(psl);
    105. 	assert(psl->size > 0);
    106. 	int begin = 0;
    107. 	while (begin < psl->size - 1)
    108. 	{
    109. 		psl->a[begin] = psl->a[begin + 1];
    110. 		++begin;
    111. 	}
    112. 	psl->size--;
    113. 	//SLErase(psl, 0);//直接调用SLErase也可以实现头删
    114. }
    115.  
    116.  
    117. //查找
    118. int SLFind(SL* psl, SLDataType x)
    119. {
    120. 	assert(psl);
    121. 	for (int i = 0; i < psl->size; i++)
    122. 	{
    123. 		if (psl->a[i] == x)
    124. 		{
    125. 			return i;
    126. 		}
    127. 	}
    128. 	return -1;
    129. }
    130.  
    131.  
    132. //插入
    133. void SLInsert(SL* psl, size_t pos, SLDataType x)
    134. {
    135. 	assert(psl);
    136. 	assert(pos <=psl->size);
    137.  
    138. 	SLCheckCapacity(psl);
    139.  
    140. 	int end = psl->size - 1;
    141.  
    142. 	//强转为int，这点很重要，因为pos为size_t类型，不强转会发生算术转化，永远跳不出循环
    143. 	while (end >=(int)pos)
    144. 	{
    145. 		psl->a[end + 1] = psl->a[end];
    146. 		--end;
    147. 	}
    148. 	psl->a[pos] = x;
    149. 	psl->size++;
    150. }
    151.  
    152. //删除
    153. void SLErase(SL* psl, size_t pos)
    154. {
    155. 	assert(psl);
    156. 	assert(pos < psl ->size);
    157.  
    158. 	size_t begin = pos;
    159. 	while (begin < psl->size - 1)
    160. 	{
    161. 		psl->a[begin] = psl->a[begin + 1];
    162. 		++begin;
    163. 	}
    164. 	psl->size--;
    165.  
    166. }
    167.  
    168.  
    169. //修改
    170. void SLModify(SL* psl, size_t pos, SLDataType x)
    171. {
    172. 	assert(psl);
    173. 	assert(pos < psl->size);
    174.  
    175. 	psl->a[pos] = x;
    176. }

    test.c 

    温馨提示：一定要通过调用每个TestSeqList()函数确认里面涉及到的功能函数没有bug我们在去进行菜单的实现，同时，一旦里面的函数多了，我们极有可能忘记这个是测试什么功能函数的，所以我的建议是：写好注释，方便自己的理解复习，同时也让别人能够看得懂。不要本末倒置了。导致出现问题而不知道错在哪里，这样子得不偿失。

    （对于菜单，博主这里并没有全部完善，但是整个框架已经搭起来了，而且可以正确运行起来。如果有需要，直接进行补充即可,可以参考之前博主类似的菜单内容。）
     

    1. //测试尾插、打印、头插
    2. void TestSeqList1()
    3. {
    4. 	SL s;
    5. 	SLInit(&s);
    6. 	SLPushBack(&s, 1);
    7. 	SLPushBack(&s, 2);
    8. 	SLPushBack(&s, 3);
    9. 	SLPushBack(&s, 4);
    10. 	SLPushBack(&s, 5);
    11. 	SLPushBack(&s, 6);
    12. 	SLPrint(&s);
    13.  
    14. 	SLPushFront(&s, 10);
    15. 	SLPushFront(&s, 20);
    16. 	SLPushFront(&s, 30);
    17. 	SLPrint(&s);
    18.  
    19. 	SLDestory(&s);
    20. }
    21.  
    22. //测试尾删
    23. void TestSeqList2()
    24. {
    25. 	SL s;
    26. 	SLInit(&s);
    27. 	SLPushBack(&s, 1);
    28. 	SLPushBack(&s, 2);
    29. 	SLPushBack(&s, 3);
    30. 	SLPushBack(&s, 4);
    31. 	SLPrint(&s);
    32.  
    33. 	SLPopBack(&s);
    34. 	SLPopBack(&s);
    35. 	SLPrint(&s);
    36.  
    37. 	SLPopBack(&s);
    38. 	SLPopBack(&s);
    39. 	SLPrint(&s);
    40.  
    41. 	SLPopBack(&s);
    42. 	SLPrint(&s);
    43.  
    44. 	SLPushBack(&s, 10);
    45. 	SLPushBack(&s, 20);
    46. 	SLPushBack(&s, 30);
    47. 	SLPushBack(&s, 40);
    48. 	SLPrint(&s);
    49.  
    50.  
    51. 	SLDestory(&s);
    52. }
    53.  
    54. //测试头删
    55. void TestSeqList3()
    56. {
    57. 	SL s;
    58. 	SLInit(&s);
    59. 	SLPushBack(&s, 1);
    60. 	SLPushBack(&s, 2);
    61. 	SLPushBack(&s, 3);
    62. 	SLPushBack(&s, 4);
    63. 	SLPrint(&s);
    64.  
    65. 	SLPopFront(&s);
    66. 	SLPopFront(&s);
    67. 	SLPrint(&s);
    68.  
    69. 	SLDestory(&s);
    70. }
    71.  
    72. //测试插入
    73. void TestSeqList4()
    74. {
    75. 	SL s;
    76. 	SLInit(&s);
    77. 	SLPushBack(&s, 1);
    78. 	SLPushBack(&s, 2);
    79. 	SLPushBack(&s, 3);
    80. 	SLPushBack(&s, 4);
    81. 	SLPrint(&s);
    82.  
    83. 	SLInsert(&s, 2, 30);
    84. 	SLPrint(&s);
    85. 	SLInsert(&s, 0, 30);
    86.  
    87. 	SLPrint(&s);
    88.  
    89. 	/*int x = 0;
    90. 	scanf("%d", &x);
    91. 	int pos = SLFind(&s, x);
    92. 	if (pos != -1)
    93. 	{
    94. 		SLInsert(&s, pos, x * 100);
    95. 	}*/
    96. 	SLPrint(&s);
    97. }
    98.  
    99. //测试删除
    100. void TestSeqList5()
    101. {
    102. 	SL s;
    103. 	SLInit(&s);
    104. 	SLPushBack(&s, 1);
    105. 	SLPushBack(&s, 2);
    106. 	SLPushBack(&s, 3);
    107. 	SLPushBack(&s, 4);
    108. 	SLPushBack(&s, 5);
    109. 	SLPrint(&s);
    110.  
    111.  
    112. 	SLErase(&s, 0);
    113. 	SLPrint(&s);
    114. 	int x = 0;
    115. 	scanf("%d", &x);
    116. 	int pos = SLFind(&s, x);
    117. 	if (pos != -1)
    118. 	{
    119. 		SLErase(&s, pos);
    120. 	}
    121. 	SLPrint(&s);
    122. }
    123. void menu()
    124. {
    125. 	printf("**********************\n");
    126. 	printf("1.尾插数据  2.头插数据\n");
    127. 	printf("3.尾删数据  4.头删数据\n");
    128. 	printf("5.查找数据  6.插入数据\n");
    129. 	printf("7.删除数据  8.修改数据\n");
    130. 	printf("9.打印数据  -1.退出\n");
    131. 	printf("**********************\n");
    132. }
    133. int main()
    134. {
    135. 	SL s;
    136. 	SLInit(&s);
    137. 	int option = 0;
    138. 	int x = 0;
    139. 	do
    140. 	{
    141. 		menu();
    142. 		printf("请输入你的操作：>");
    143. 		scanf("%d", &option);
    144. 		switch (option)
    145. 		{
    146. 		case 1:
    147. 			printf("请连续输入要插入的数据，-1为结束\n");
    148. 			scanf("%d", &x);
    149. 			while (x != -1)
    150. 			{
    151. 				SLPushBack(&s, x);
    152. 				scanf("%d", &x);
    153. 			}
    154. 			break;
    155. 		case 2:
    156. 			//后面内容自己进行补充说明
    157. 			break;
    158. 		case 3:
    159. 			break;
    160. 		case 4:
    161. 			break;
    162. 		case 5:
    163. 			break;
    164. 		case 6:
    165. 			break;
    166. 		case 7:
    167. 			break;
    168. 		case 8:
    169. 			break;
    170. 		case 9:
    171. 			SLPrint(&s);
    172. 		default:
    173. 			return;
    174. 		}
    175. 	} while (option);
    176. 	SLDestory(&s);
    177. 	return 0;
    178. }

    简化的顺序表代码 SeqList.c

    1. #include "SeqList.h"
    2.  
    3. void SLPrint(const SL* psl)
    4. {
    5. 	assert(psl);
    6. 	for (int i = 0; i < psl->size; ++i)
    7. 	{
    8. 		printf("%d ", psl->a[i]);
    9. 	}
    10. 	printf("\n");
    11. }
    12.  
    13. void SLInit(SL* psl)
    14. {
    15. 	assert(psl);
    16.  
    17. 	psl->a = NULL;
    18. 	psl->capacity = psl->size = 0;
    19. }
    20.  
    21. void SLDestory(SL* psl)
    22. {
    23. 	assert(psl);
    24.  
    25. 	/*if (psl->a)
    26. 	{*/
    27. 		free(psl->a);
    28. 		psl->a = NULL;
    29. 		psl->capacity = psl->size = 0;
    30. 	//}
    31. }
    32.  
    33. void SLCheckCapacity(SL* psl)
    34. {
    35. 	// 检查容量
    36. 	if (psl->size == psl->capacity)
    37. 	{
    38. 		int newCapcity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    39. 		SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapcity*sizeof(SLDataType));
    40. 		if (tmp == NULL)
    41. 		{
    42. 			perror("realloc fail");
    43. 			return;
    44. 			//exit(-1);
    45. 		}
    46.  
    47. 		psl->a = tmp;
    48. 		psl->capacity = newCapcity;
    49. 	}
    50.  
    51. }
    52.  
    53. // https://cplusplus.com/reference/
    54. void SLPushBack(SL* psl, SLDataType x)
    55. {
    56. 	/*assert(psl);
    58. 	SLCheckCapacity(psl);
    60. 	psl->a[psl->size] = x;
    61. 	psl->size++;*/
    62.  
    63. 	SLInsert(psl, psl->size, x);
    64. }
    65.  
    66. void SLPushFront(SL* psl, SLDataType x)
    67. {
    68. 	//assert(psl);
    69. 	//SLCheckCapacity(psl);
    70.  
    71. 	 挪动数据
    72. 	//int end = psl->size - 1;
    73. 	//while (end >= 0)
    74. 	//{
    75. 	//	psl->a[end + 1] = psl->a[end];
    76. 	//	--end;
    77. 	//}
    78. 	//psl->a[0] = x;
    79. 	//psl->size++;
    80.  
    81. 	SLInsert(psl, 0, x);
    82. }
    83.  
    84. void SLPopBack(SL* psl)
    85. {
    86. 	//assert(psl);
    87.  
    88. 	 温柔的检查
    89. 	///*if (psl->size == 0)
    90. 	//{
    91. 	//return;
    92. 	//}*/
    93.  
    94. 	 暴力的检查
    95. 	//assert(psl->size > 0);
    96.  
    97. 	//psl->size--;
    98. 	SLErase(psl, psl->size - 1);
    99. }
    100.  
    101. void SLPopFront(SL* psl)
    102. {
    103. 	//assert(psl);
    104. 	//assert(psl->size > 0);
    105.  
    106. 	///*int begin = 0;
    107. 	//while (begin < psl->size-1)
    108. 	//{
    109. 	//	psl->a[begin] = psl->a[begin + 1];
    110. 	//	++begin;
    111. 	//}*/
    112.  
    113. 	//int begin = 1;
    114. 	//while (begin < psl->size)
    115. 	//{
    116. 	//	psl->a[begin-1] = psl->a[begin];
    117. 	//	++begin;
    118. 	//}
    119.  
    120. 	//--psl->size;
    121. 	SLErase(psl, 0);
    122. }
    123.  
    124. int SLFind(SL* psl, SLDataType x)
    125. {
    126. 	assert(psl);
    127.  
    128. 	for (int i = 0; i < psl->size; ++i)
    129. 	{
    130. 		if (psl->a[i] == x)
    131. 		{
    132. 			return i;
    133. 		}
    134. 	}
    135.  
    136. 	return -1;
    137. }
    138.  
    139. //void SLInsert(SL* psl, int pos, SLDataType x)
    140. void SLInsert(SL* psl, size_t pos, SLDataType x)
    141. {
    142. 	assert(psl);
    143. 	assert(pos <= psl->size);
    144.  
    145. 	SLCheckCapacity(psl);
    146.  
    147. 	// 挪动数据
    148. 	/*int end = psl->size - 1;
    149. 	while (end >= (int)pos)
    150. 	{
    151. 		psl->a[end + 1] = psl->a[end];
    152. 		--end;
    153. 	}*/
    154.  
    155. 	size_t end = psl->size;
    156. 	while (end > pos)
    157. 	{
    158. 		psl->a[end] = psl->a[end-1];
    159. 		--end;
    160. 	}
    161.  
    162. 	psl->a[pos] = x;
    163. 	++psl->size;
    164. }
    165.  
    166. // 顺序表删除pos位置的值
    167. void SLErase(SL* psl, size_t pos)
    168. {
    169. 	assert(psl);
    170. 	assert(pos < psl->size);
    171.  
    172. 	size_t begin = pos;
    173. 	while (begin < psl->size - 1)
    174. 	{
    175. 		psl->a[begin] = psl->a[begin + 1];
    176. 		++begin;
    177. 	}
    178.  
    179. 	psl->size--;
    180. }
    181.  
    182. void SLModify(SL* psl, size_t pos, SLDataType x)
    183. {
    184. 	assert(psl);
    185. 	assert(pos < psl->size);
    186.  
    187. 	psl->a[pos] = x;
    188. }

     结语：

    每个人的成长都是能力和想要得到的东西，不断匹配的过程，当你的才华和欲望不匹配时，你就该静下心来学习了，如果小编的总结能对你有所帮助，希望小伙伴们三连加关注哦，你的支持是小编创作的最大动力。

     

     

  • 相关阅读:
    企业AI虚拟ip形象定制的应用场景
    微服务性能分析｜Pyroscope 在 Rainbond 上的实践分享
    [Java]_[初级]_[以SAX流的方式高效读取XML大文件]
    Matlab：指定时区
    【系统架构设计师】第三章 数据库系统
    MySQL-数据类型
    vuejs3+elementPlus后台管理系统，左侧菜单栏制作，跳转、默认激活菜单
    数据库设计 Relational Language
    Windows10下Tomcat8.5安装教程
    如何获取HuggingFace的Access Token；如何获取HuggingFace的API Key
  • 原文地址：https://blog.csdn.net/weixin_67900732/article/details/126120248