• 数据结构·顺序表

    目录

    线性表

    概念及结构

    顺序表

    静态顺序表

    动态顺序表

    接口实现 

    SeqList.h

    SeqList.c

     Test.c

    结束语

    线性表

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

    概念及结构

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

    连续存储顺序，是不能跳跃的

    顺序表

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

    静态顺序表

    使用定长数组存储元素

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

    静态顺序表价值较低 -- 不考虑 

    动态顺序表

     扩容方式 -- 使用 realloc 库函数 -- 有两种扩容方式 原地扩容 与 异地扩容 后者代价大

    扩容选择 -- 两倍

    扩容两倍的原因

    一次扩容多了，存在空间的浪费。一次扩容少了，频繁扩容，效率损失

    接口实现 

    SeqList.h

    1. #pragma once	//方式二次引用
    2. #define _CRT_SECURE_NO_DEPRECATE	//VS里面的检查 -- 其他编辑器不需要
    3. #include
    4. #include
    5. #include
    6.  
    7. //或者
    8. //#ifndef __SEQLIST_H__
    9. //#define __SEQLIST_H__
    10. //……
    11. //#endif 
    12.  
    13. //静态的顺序表	 -- 缺陷：当不知道要存储多少数据的时候就体现出来了
    14. //#define N 10
    15. //typedef int SLDataType;
    16. //struct Seqlist
    17. //{
    18. //	SLDataType a[N];
    19. //	int size;	//存储数据的个数
    20. //};
    21.  
    22. //动态顺序表	-- 有两种扩容方式 原地扩容与异地扩容 后者代价大
    23.  
    24. //重命名类型 -- 方便后续改变存储类型
    25. typedef int SLDataType;
    26.  
    27. typedef struct Seqlist
    28. {
    29. 	SLDataType* a;
    30. 	int size;	//存储数据的个数
    31. 	int capacity;//存储空间的大小
    32. }SL;
    33.  
    34. //初始化 -- 这里要接收地址，用指针接收，利用地址来与外部产生联系
    35. void SLInit(SL* psl);
    36.  
    37. //销毁 -- 
    38. void SLDestory(SL* psl);
    39.  
    40. //顺序表的打印 -- 方便检查
    41. void SLPrint(SL* psl);
    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 SLPoPhFront(SL* psl);
    55.  
    56. // 顺序表查找 -- 没找到返回-1
    57. int SLFind(SL* psl, SLDataType x);
    58.  
    59. //顺序表在pos位置插入x
    60. void SLInsert(SL* psl, size_t pos, SLDataType x);
    61.  
    62. // 顺序表删除pos位置的值
    63. void SLErase(SL* psl, size_t pos);
    64.  
    65. //修改
    66. void SLModify(SL* psl, size_t pos, SLDataType x);

    SeqList.c

    1. #include "SeqList.h"
    2.  
    3.  
    4. //初始化
    5. void SLInit(SL* psl)
    6. {
    7. 	assert(psl);	//自身断言不可以为空 不可以传NULL过来
    8. 	psl->a = NULL;
    9. 	psl->size = psl->capacity = 0;
    10. }
    11.  
    12. //销毁
    13. void SLDestory(SL* psl)
    14. {
    15. 	assert(psl);
    16. 	//if (psl->a)	//free自己会检查是否为NULL -- free NULL 没意义
    17. 	//{
    18. 		free(psl->a); 
    19. 		psl->a = NULL;
    20. 		psl->size = psl->capacity = 0;
    21. 	//}
    22. }
    23.  
    24.  
    25. //检查并扩容
    26. void SLCheckCapacity(SL* psl)
    27. {
    28. 	//检查容量
    29. 	if (psl->size == psl->capacity)
    30. 	{
    31. 		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;	//扩容两倍 -- 当为0的时候赋值4字节
    32. 		SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapacity * sizeof(SLDataType));	//三种情况，原地、异地与失败 -- 为防止失败应使用临时指针
    33. 		if (tmp == NULL)					// 这里开辟空间大小容易出错，必须要记得后面的* sizeof(SLDataType) 不然开辟的空间不够
    34. 		{
    35. 			perror("realloc fail");
    36. 			return;
    37. 			//exit(-1); //或者这样直接返回，更直接
    38. 		}
    39. 		psl->a = tmp;
    40. 		psl->capacity = newCapacity;
    41. 	}
    42. }
    43.  
    44. //打印
    45. void SLPrint(SL* psl)
    46. {
    47. 	assert(psl);
    48. 	for (int i = 0; i < psl->size; i++)
    49. 	{
    50. 		printf("%d ", psl->a[i]);
    51. 	}
    52. 	printf("\n");
    53. }
    54.  
    55. //尾插
    56. void SLPushBack(SL* psl, SLDataType x)
    57. {	
    58.  
    59. 	//assert(psl);
    60. 	//检查并扩容
    61. 	//SLCheckCapacity(psl);
    62.  
    63. 	//psl->a[psl->size] = x;
    64. 	//psl->size++;
    65. 	
    66. 	//当SLInsert写好后就不需要这些了，直接调用
    67. 	SLInsert(psl, psl->size, x);
    68. }
    69.  
    70. //头插
    71. void SLPushFront(SL* psl, SLDataType x)
    72. {
    73. 	//assert(psl);
    74. 	//SLCheckCapacity(psl);
    75.  
    76. 	//挪动数据
    77. 	//int end = psl->size - 1;
    78. 	//while (end >= 0)
    79. 	//{
    80. 	//	psl->a[end+1] = psl->a[end];
    81. 	//	--end;
    82. 	//}
    83. 	//psl->a[0] = x;
    84. 	//psl->size++;
    85.  
    86. 	//这里也不需要了，直接调用
    87. 	SLInsert(psl, 0, x); // -- 这就相当与头插了
    88.  
    89. }
    90.  
    91. //尾删
    92. void SLPoPBack(SL* psl)
    93. {
    94. 	//assert(psl);
    95.  
    96. 	//比较温柔的检查
    97. 	//if (psl->size == 0)
    98. 	//{
    99. 	//	return;
    100. 	//}
    101.  
    102. 	//暴力的检查		-- 会直接报错  在C++中更常用
    103. 	//assert(psl->size > 0);
    104.  
    105. 	//psl->size--;		//realloc是不可以释放一部分的空间的所以不要free
    106. 	//					//也不需要清除掉数据，但是没必要，可以直接覆盖
    107. 	//					//这种的情况是由size为基准，由它访问
    108. 	//					//但是有bug：删掉的多了就会出现数据的越界
    109.  
    110. 	//写完之后就可以替换掉之前的了
    111.  
    112. 	SLErase(psl, psl->size-1);
    113.  
    114. }
    115.  
    116. //头删
    117. void SLPoPhFront(SL* psl)
    118. {
    119. 	//assert(psl);
    120. 	//assert(psl->size > 0);
    121.  
    122. 	//一
    123. 	//int begin = 0;
    124. 	//while (begin < psl->size - 1)
    125. 	//{
    126. 	//	psl->a[begin] = psl->a[begin + 1];
    127. 	//	++begin;
    128. 	//}
    129. 	//--psl->size;
    130.  
    131. 	//写完之后就可以替换掉之前的了
    132. 	SLErase(psl, 0);
    133.  
    134. }
    135. //缩容：以时间换空间 -- 不常用
    136. //不缩容：以空间换时间 -- 现在的设备比较空间都比较强
    137. //realloc 缩容可能会异地缩容
    138.  
    139.  
    140. //顺序表查找 -- 没找到返回-1
    141. //这里直接遍历数组就可以了，在数据少的情况下这样反而更快 O(N) 级别
    142. int SLFind(SL* psl, SLDataType x)
    143. {
    144. 	assert(psl);
    145.  
    146. 	for (int i = 0; i < psl->size; ++i)
    147. 	{
    148. 		if (psl->a[i] == x)
    149. 		{
    150. 			return i;
    151. 		}
    152. 	}
    153. 	return -1;
    154. }
    155.  
    156. //顺序表在pos位置插入x -- 在前面插入
    157. void SLInsert(SL* psl, size_t pos, SLDataType x)	//size_t 更符合库函数的设计
    158. {
    159. 	assert(psl);
    160. 	assert(pos <= psl->size);
    161.  
    162. 	SLCheckCapacity(psl);
    163.  
    164. 	//挪动数据 法一： 用这种方法要注意算术转化，容易死循环
    165. 	//int end = psl->size - 1;
    166. 	//while (end>=(int)pos)
    167. 	//{	
    168. 	//	psl->a[end] = psl->a[end - 1];
    169. 	//	--end;
    170. 	//}
    171.  
    172. 	//挪动数据 法二：这种方法更好，不需要强制转化
    173. 	size_t end = psl->size;
    174. 	while (end > pos)
    175. 	{
    176. 		psl->a[end] = psl->a[end - 1];
    177. 		end--;
    178. 	}
    179.  
    180. 	psl->a[pos] = x;
    181. 	++psl->size;
    182. }
    183.  
    184.  
    185. // 顺序表删除pos位置的值
    186. void SLErase(SL* psl, size_t pos)
    187. {
    188. 	assert(psl);
    189. 	assert(pos < psl->size);
    190.  
    191. 	size_t begin = pos;
    192. 	while (begin < psl->size - 1)
    193. 	{
    194. 		psl->a[begin] = psl->a[begin + 1];
    195. 		++begin;
    196. 	}
    197.  
    198. 	--psl->size;
    199.  
    200. }
    201.  
    202. //修改
    203. void SLModify(SL* psl, size_t pos, SLDataType x)
    204. {
    205. 	assert(psl);
    206. 	assert(pos < psl->size);
    207.  
    208. 	psl->a[pos] = x;
    209.  
    210. }

     Test.c

    1. #include "SeqList.h"
    2.  
    3. //尾插、头插、销毁测试
    4. void TestSeqList1()
    5. {
    6. 	SL s;
    7. 	//初始化 
    8. 	SLInit(&s);
    9. 	//尾插
    10. 	SLPushBack(&s, 1);
    11. 	SLPushBack(&s, 2);
    12. 	SLPushBack(&s, 3);
    13. 	SLPushBack(&s, 4);
    14. 	SLPushBack(&s, 5);
    15. 	SLPushBack(&s, 6);
    16. 	//打印观察
    17. 	SLPrint(&s);
    18. 	
    19. 	//头插
    20. 	SLPushFront(&s, 10);
    21. 	SLPushFront(&s, 20);
    22. 	SLPushFront(&s, 30);
    23. 	//打印观察
    24. 	SLPrint(&s);
    25.  
    26. 	//销毁
    27. 	SLDestory(&s);
    28.  
    29. }
    30.  
    31.  
    32. //尾插、尾删、删多了测试
    33. TestSeqList2()
    34. {
    35. 	//SLInit(NULL);	//测试传空指针 -- 到assert会直接报错
    36. 	SL s;
    37. 	SLInit(&s);
    38. 	SLPushBack(&s, 1);
    39. 	SLPushBack(&s, 2);
    40. 	SLPushBack(&s, 3);
    41. 	SLPushBack(&s, 4);
    42. 	SLPrint(&s);
    43.  
    44. 	//尾删
    45. 	SLPoPBack(&s);
    46. 	SLPoPBack(&s);
    47. 	SLPrint(&s);
    48. 	//再尾删
    49. 	SLPoPBack(&s);
    50. 	SLPoPBack(&s);
    51. 	SLPrint(&s);
    52.  
    53. 	//头删
    54. 	SLPushBack(&s,10);
    55. 	SLPushBack(&s,20);
    56. 	SLPushBack(&s,30);
    57. 	SLPushBack(&s,40);
    58. 	SLPrint(&s);
    59.  
    60. 	SLDestory(&s);
    61. }
    62.  
    63. //插入测试
    64. TestSeqList3()
    65. {
    66. 	SL s;
    67. 	SLInit(&s);
    68. 	SLInsert(&s, 0, 30);
    69. 	SLPushBack(&s, 40);
    70. 	SLPrint(&s);
    71. }
    72.  
    73. //尾插、删除测试
    74. TestSeqList4()
    75. {
    76. 	SL s;
    77. 	SLInit(&s);
    78. 	SLPushBack(&s, 1);
    79. 	SLPushBack(&s, 2);
    80. 	SLPushBack(&s, 3);
    81. 	SLPushBack(&s, 4);
    82. 	SLPushBack(&s, 5);
    83. 	SLPrint(&s);
    84.  
    85. 	SLErase(&s, 0);
    86. 	SLPrint(&s);
    87. 	int x = 0;
    88. 	
    89. 	scanf("%d", &x);
    90. 	int pos = SLFind(&s, x);
    91. 	if (pos != -1)
    92. 	{
    93. 		SLErase(&s, pos);
    94. 	}
    95. 	SLPrint(&s);
    96.  
    97. }
    98.  
    99. void memu()
    100. {
    101. 	printf("****************************\n");
    102. 	printf("1、尾插数据 2、头插数据\n");
    103. 	printf("3、位置插入 7、打印数据 \n");
    104. 	printf("      -1、退出  \n");
    105. 	printf("****************************\n");
    106.  
    107. }
    108.  
    109. int main()
    110. {
    111. 	//TestSeqList1();	//测试的时候尽量单独用一个函数测试
    112. 	//TestSeqList3();
    113. 	//TestSeqList4();
    114.  
    115. 	SL s;
    116. 	SLInit(&s);
    117. 	int option = 0;
    118. 	int x = 0;
    119. 	int pos = 0;
    120. 	do
    121. 	{
    122. 		memu();
    123. 		printf("请输入你的操作:>");
    124. 		scanf("%d", &option);
    125. 		switch (option)
    126. 		{
    127. 			case 1:
    128. 				printf("请连续输入你想要插入的数据，以-1结束\n");
    129. 				scanf("%d", &x);
    130. 				while (x != -1)
    131. 				{
    132. 					SLPushBack(&s,x);
    133. 					scanf("%d", &x);
    134. 				}
    135. 				break;
    136. 			case 2:
    137. 				printf("请连续输入你想要插入的数据，以-1结束\n");
    138. 				scanf("%d", &x);
    139. 				while (x != -1)
    140. 				{
    141. 					SLPushFront(&s, x);
    142. 					scanf("%d", &x);
    143. 				}
    144. 				break;
    145. 			case 3:
    146. 				printf("请输入你想要插入的数据\n");
    147. 				scanf("%d", &x);
    148. 				printf("请输入你想要插入的位置\n");
    149. 				scanf("%d", &pos);
    150. 				SLInsert(&s, pos, x);
    151. 				break;
    152. 			case 7:
    153. 				SLPrint(&s);
    154. 				break;
    155. 		default:
    156. 			break;
    157. 		}
    158.  
    159. 	} while (option != -1);
    160.  
    161. 	SLDestory(&s);
    162.  
    163. 	return 0;
    164. }

    菜单不完善了，很简单

    我写这篇的时候发现这里不允许使用 来二层注释 

    结束语

    别有幽愁暗恨生，此时无声胜有声。
                                            唐·白居易 《琵琶行》

  • 相关阅读:
    重生奇迹MU套装大全中的极品属性
    【word论文排版-公式】如何实现两栏格式公式居中，编号右对齐
    基于单片机设计的家用自来水水质监测装置
    kafka 使用thrift序列化对象
    项目中的奇葩需求你都怎么应对？
    nginx服务器
    130 行代码搞定核酸统计，程序员在抗疫期间的大能量
    【数据结构基础_字符串】Leetcode 409.最长回文串
    数据结构 之 树
    Packet Tracer的使用介绍
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126032028