• 【数据结构初阶】顺序表SeqList

    描述

    顺序表我们可以把它想象成在一个表格里面填数据，并对数据做调整；

    那我们的第一个问题是：怎么样在创建出足够的空间呢？

    我们可以去堆上申请，用一个指针指向一块空间，如果申请的空间不够，我们可以再realloc申请出来。

    我们的第二个问题是：怎么样标记我们用了多少空间呢？

    这时我们就需要一个变量来记录我们当前的用到第几个“格子”（即用了多少空间），我们这里用size来表示：

    我们的第三个问题是：怎么样知道我们有空间呢？

    这时我们就需要一个变量来记录我们“格子”总数（即拥有多少空间），我们这里用capacity来表示：

    所以（在.h文件中）我们线性表的结构体描述为：

    1. typedef int SLDataType;
    2.  
    3. typedef struct SeList
    4. {
    5. 	SLDataType* a;
    6. 	int size;
    7. 	int capacity;
    8. }SL;

    组织

    1. 初始化
    2. 释放
    3. 尾插
    4. 尾删
    5. 头插
    6. 头删
    7. 指定位置删除
    8. 指定位置插入
    9. 查找指定元素

    1.初始化

    把我们描述出来的顺序表结构体里的变量初始化

    在.h文件中：

    因为要对创建出来的结构体里的内容进行修改，所以函数要进行传址调用；

    在.c文件中:

    我们用malloc来开辟空间,同时注意检查malloc；

    因为我们刚刚开辟空间，并没有往顺序表里增删查改 所以此时size为0；

    而我们的capacity就是在malloc开辟的空间大小。

    1. void SLInit(SL* ps)
    2. {
    3. 	assert(ps->a);
    4.  
    5. 	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    6. 	if (ps->a == NULL)
    7. 	{
    8. 		perror("malloc fail");
    9. 		return;
    10. 	}
    11.  
    12. 	ps->size = 0;
    13. 	ps->capacity = INIT_CAPACITY;
    14. }

    2.释放

    将描述出来的顺序表结构体里的变量逐个进行释放；

    在.h 文件中：

    在.c文件中：

    首先是指针a，需要使用free函数将其释放，还需要注意的是free后，需要将a置空，避免出现野指针；

    因为size和capacity是临时变量储存在栈上，函数调用结束后会自动释放，我们这里把它改为0就可以了。

    1. void SLDestroy(SL* ps)
    2. {
    3. 	assert(ps->a);
    4.  
    5. 	free(ps->a);
    6. 	ps->a = NULL;
    7. 	ps->capacity = 0;
    8. 	ps->size = 0;
    9. }

    3.尾插

    向顺序表的尾部插入数据；

    在.h 文件中：

    在.c文件中：

    尾插数据时，首先，需要判断capacity（空间）是否足够，如果不够需要扩容，这里我们写个扩容函数：

    扩容我们用realloc函数，最后要返回ps至尾插函数判断是否为空；

    接着，才能将数据尾插；

    最后别忘了调整size的位置；

    1. SL* SLExpand(SL* ps)
    2. {
    3. 	assert(ps->a);
    4. 	if (ps->size == ps->capacity)
    5. 	{
    6. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);
    7. 		if (tmp == NULL)
    8. 		{
    9. 			perror("realloc fail");
    10. 			return NULL;
    11. 		}
    12. 		ps->capacity *=2;
    13. 		ps->a = tmp;
    14. 	}
    15. 	return ps;
    16. }
    17.  
    18. void SLPushBack(SL* ps,SLDataType x)
    19. {
    20. 	assert(ps->a);
    21. 	//扩容
    22. 	if (ps->size == ps->capacity)
    23. 	{
    24. 		SL* ret = SLExpand(ps);
    25. 		if (ret == NULL)
    26. 		{
    27. 			return;
    28. 		}
    29. 	}
    30. 	ps->a[ps->size] = x;
    31. 	ps->size++;
    32.  
    33. }

    4.尾删

    将顺序表的尾部删除；

    在.h 文件中：

    在.c 文件中：

    因为顺序表是从开始连续存储size个数据，不能单独释放那一块区域，所以我们直接将size--就可以了，如果往后插入的话，就直接把数据覆盖；

    assert（）如果当capacity为空的时候还尾删时会报错,并且终止程序；

    1. void SLPopBack(SL* ps)
    2. {
    3. 	assert(ps->a);
    4. 	ps->size--;
    5. }

    5.头插

    向顺序表的头部插入数据；

    在.h 文件中：

    在.c 文件中：

    首先，我们得先判断空间是否足够，如果不够就扩容；

    第二步：把数据往后移一位，数据从最后一位开始向后移动；

    第三步：进行数据头插，别忘了把size的大小改改；

    1. void SLPushFront(SL* ps, SLDataType x)
    2. {
    3. 	assert(ps->a);
    4.  
    5. 	//扩容
    6. 	if (ps->size == ps->capacity)
    7. 	{
    8. 		SL* ret = SLExpand(ps);
    9. 		if (ret == NULL)
    10. 		{
    11. 			return;
    12. 		}
    13. 	}
    14.  
    15. 	//移动数据
    16. 	for (int i = ps->size; i >0 ; i--)
    17. 	{
    18. 		ps->a[i] = ps->a[i - 1];
    19. 	}
    20.  
    21. 	//头插
    22. 	ps->a[0] = x;
    23. 	ps->size++;
    24.  
    25. }

    6.头删

    将顺序表的头部数据删除；

    在.h 文件中：

    在.c 文件中：

    我们只需要将从第二位数据开始往前移动，把前一位的数据覆盖就可以达到头删的效果；

    1. void SLPopFront(SL* ps)
    2. {
    3. 	assert(ps->a);
    4. 	assert(ps->size > 0);
    5. 	for (int i = 0; i < ps->size; i++)
    6. 	{
    7. 		ps->a[i] = ps->a[i + 1];
    8. 	}
    9.  
    10. 	ps->size--;
    11. }

    7.指定位置删除

    将顺序表的指定位置数据删除；

    在.h 文件中：

    在.c 文件中：

    首先，要先用assert检查一下空间和pos的值是否合理；

    如果删除的数据是最后一个就直接尾删；

    如果如果删除的数据不是最后一个就需要移动数据覆盖，类似于头删；

    1. void SLErase(SL* ps, int pos)
    2. {
    3. 	assert(ps->a);
    4. 	assert(pos >= 0&&possize);
    5.  
    6. 	//如果pos是最后一个数据，尾删
    7. 	if (pos == ps->size - 1)
    8. 	{
    9. 		SLPopBack(ps);
    10. 	}
    11.  
    12. 	else
    13. 	{
    14. 		for (int i = pos; i < ps->size; i++)
    15. 		{
    16. 			ps->a[i] = ps->a[i + 1];
    17. 		}
    18. 		ps->size--;
    19. 	}
    20.  
    21. 	
    22. }

    8.指定位置插入

    将顺序表的指定位置数据插入；

    在.h 文件中：

    在.c 文件中：

    首先，要先用assert检查一下空间和pos的值是否合理；

    如果插入的数据是最后一个就直接尾插；

    如果如果插入的数据不是最后一个就需要移动数据，再插入数据，类似于头插；

    1. void SLInsert(SL* ps, int pos, SLDataType x)
    2. {
    3. 	assert(ps->a);
    4. 	assert(pos >= 0 && pos <= ps->size);
    5.  
    6. 	//判断容量
    7. 	if (ps->size == ps->capacity)
    8. 	{
    9. 		SL* ret = SLExpand(ps);
    10. 		if (ret == NULL)
    11. 		{
    12. 			return;
    13. 		}
    14. 	}
    15.  
    16. 	//尾插
    17. 	if (pos == ps->size - 1)
    18. 	{
    19. 		SLPushBack(ps,x);
    20. 	}
    21. 	else
    22. 	{
    23. 		for (int i = ps->size; i > pos; i--)
    24. 		{
    25. 			ps->a[i] = ps->a[i - 1];
    26. 		}
    27. 		ps->size++;
    28. 		ps->a[pos] = x;
    29. 	}
    30. }

    9.查找指定元素

    在顺序表中查找指定数据，并输出其下表，和在该表中的个数；

    在.h 文件中：

    在.c 文件中：

    for循环遍历一下顺序表，如果遍历过程中找到了直接打印其下标，并用一个变量记录它出现的此数。

    出循环后打印其和在该表中出现的个数。

    1. void SLFindPoint(SL* ps, SLDataType x)
    2. {
    3. 	assert(ps->a);
    4. 	
    5. 	int cnt = 0;
    6. 	for (int i = 0; i < ps->size; i++)
    7. 	{
    8. 		if (ps->a[i] == x)
    9. 		{
    10. 			cnt++;
    11. 			printf("找到了第%d个，下标为:%d\n",cnt, i);
    12. 		}
    13. 	}
    14. 	if (cnt == 0)
    15. 	{
    16. 		printf("抱歉，无该数据\n");
    17. 	}
    18. 	else
    19. 	{
    20. 		printf("共找到%d个数据\n", cnt);
    21. 	}
    22. }

    整个程序

    .h文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. typedef int SLDataType;
    8. #define INIT_CAPACITY 4
    9.  
    10. typedef struct SeList
    11. {
    12. 	SLDataType* a;
    13. 	int size;
    14. 	int capacity;
    15. }SL;
    16.  
    17. void SLPrint(SL* ps);
    18.  
    19. void SLInit(SL* ps);
    20. void SLDestroy(SL* ps);
    21. void SLPushBack(SL* ps,SLDataType x);
    22. void SLPopBack(SL* ps);
    23. void SLPushFront(SL* ps, SLDataType x);
    24. void SLPopFront(SL* ps);
    25. void SLErase(SL* ps,int pos);
    26. void SLInsert(SL* ps, int pos, SLDataType x);
    27. void SLFindPoint(SL* ps, SLDataType x);

    .c文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Seqlist.h"
    3.  
    4.  
    5. void SLPrint(SL* ps)
    6. {
    7. 	assert(ps->a);
    8.  
    9. 	for (int i = 0; i < ps->size; i++)
    10. 	{
    11. 		printf("%d ", ps->a[i]);
    12. 	}
    13. 	printf("\n");
    14. }
    15.  
    16.  
    17. void SLInit(SL* ps)
    18. {
    19. 	assert(ps->a);
    20.  
    21. 	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    22. 	if (ps->a == NULL)
    23. 	{
    24. 		perror("malloc fail");
    25. 		return;
    26. 	}
    27.  
    28. 	ps->size = 0;
    29. 	ps->capacity = INIT_CAPACITY;
    30. }
    31.  
    32. void SLDestroy(SL* ps)
    33. {
    34. 	assert(ps->a);
    35.  
    36. 	free(ps->a);
    37. 	ps->a = NULL;
    38. 	ps->capacity = 0;
    39. 	ps->size = 0;
    40. }
    41.  
    42. SL* SLExpand(SL* ps)
    43. {
    44. 	assert(ps->a);
    45. 	if (ps->size == ps->capacity)
    46. 	{
    47. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);
    48. 		if (tmp == NULL)
    49. 		{
    50. 			perror("realloc fail");
    51. 			return NULL;
    52. 		}
    53. 		ps->capacity *=2;
    54. 		ps->a = tmp;
    55. 	}
    56. 	return ps;
    57. }
    58.  
    59. void SLPushBack(SL* ps,SLDataType x)
    60. {
    61. 	assert(ps->a);
    62. 	//扩容
    63. 	if (ps->size == ps->capacity)
    64. 	{
    65. 		SL* ret = SLExpand(ps);
    66. 		if (ret == NULL)
    67. 		{
    68. 			return;
    69. 		}
    70. 	}
    71. 	ps->a[ps->size] = x;
    72. 	ps->size++;
    73.  
    74. }
    75.  
    76. void SLPopBack(SL* ps)
    77. {
    78. 	assert(ps->a);
    79. 	ps->size--;
    80. }
    81.  
    82. void SLPushFront(SL* ps, SLDataType x)
    83. {
    84. 	assert(ps->a);
    85.  
    86. 	//扩容
    87. 	if (ps->size == ps->capacity)
    88. 	{
    89. 		SL* ret = SLExpand(ps);
    90. 		if (ret == NULL)
    91. 		{
    92. 			return;
    93. 		}
    94. 	}
    95.  
    96. 	//移动数据
    97. 	for (int i = ps->size; i >0 ; i--)
    98. 	{
    99. 		ps->a[i] = ps->a[i - 1];
    100. 	}
    101.  
    102. 	//头插
    103. 	ps->a[0] = x;
    104. 	ps->size++;
    105.  
    106. }
    107.  
    108. void SLPopFront(SL* ps)
    109. {
    110. 	assert(ps->a);
    111. 	assert(ps->size > 0);
    112. 	for (int i = 0; i < ps->size; i++)
    113. 	{
    114. 		ps->a[i] = ps->a[i + 1];
    115. 	}
    116.  
    117. 	ps->size--;
    118. }
    119.  
    120. void SLErase(SL* ps, int pos)
    121. {
    122. 	assert(ps->a);
    123. 	assert(pos >= 0&&possize);
    124.  
    125. 	//如果pos是最后一个数据，尾删
    126. 	if (pos == ps->size - 1)
    127. 	{
    128. 		SLPopBack(ps);
    129. 	}
    130.  
    131. 	else
    132. 	{
    133. 		for (int i = pos; i < ps->size; i++)
    134. 		{
    135. 			ps->a[i] = ps->a[i + 1];
    136. 		}
    137. 		ps->size--;
    138. 	}
    139.  
    140. 	
    141. }
    142.  
    143. void SLInsert(SL* ps, int pos, SLDataType x)
    144. {
    145. 	assert(ps->a);
    146. 	assert(pos >= 0 && pos <= ps->size);
    147.  
    148. 	//判断容量
    149. 	if (ps->size == ps->capacity)
    150. 	{
    151. 		SL* ret = SLExpand(ps);
    152. 		if (ret == NULL)
    153. 		{
    154. 			return;
    155. 		}
    156. 	}
    157.  
    158. 	//尾插
    159. 	if (pos == ps->size - 1)
    160. 	{
    161. 		SLPushBack(ps,x);
    162. 	}
    163. 	else
    164. 	{
    165. 		for (int i = ps->size; i > pos; i--)
    166. 		{
    167. 			ps->a[i] = ps->a[i - 1];
    168. 		}
    169. 		ps->size++;
    170. 		ps->a[pos] = x;
    171. 	}
    172. }
    173.  
    174. void SLFindPoint(SL* ps, SLDataType x)
    175. {
    176. 	assert(ps->a);
    177. 	
    178. 	int cnt = 0;
    179. 	for (int i = 0; i < ps->size; i++)
    180. 	{
    181. 		if (ps->a[i] == x)
    182. 		{
    183. 			cnt++;
    184. 			printf("找到了第%d个，下标为:%d\n",cnt, i);
    185. 		}
    186. 	}
    187. 	if (cnt == 0)
    188. 	{
    189. 		printf("抱歉，无该数据\n");
    190. 	}
    191. 	else
    192. 	{
    193. 		printf("共找到%d个数据\n", cnt);
    194. 	}
    195. }

  • 相关阅读:
    ACM笔记
    PostgreSQL的学习心得和知识总结（一百三十九）|深入理解PostgreSQL数据库GUC参数 allow_alter_system 的使用和原理
    抖音小店需要办理营业执照吗？怎么办理？这个流程你一定要收好！
    java基础之内部类[31]
    操作系统——网络通信——多路复用——select 、poll 、epoll的函数的相关使用
    生命在于学习——Stable Diffution（Mac端）
    [Linux] 基于阻塞队列的生产者消费者模型
    全国职业技能大赛云计算--高职组赛题卷④（容器云）
    网安周报｜Chaes恶意软件的新Python变种针对银行和物流行业
    水厂除砷项目，砷出水未检出
  • 原文地址：https://blog.csdn.net/lsj1345714539566/article/details/134347485