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

＜数据结构＞ （C语言实现） 动态顺序表

作者：羊村懒王 | 2024-04-28 06:39:47

赞

踩

＜数据结构＞ （C语言实现） 动态顺序表

 

目录

 

1.线性表

2.顺序表

2.1顺序表的概念及结构

2.2顺序表的优缺点

2.3动态、静态顺序表的区分

3.动态顺序表的实现

3.1 SeqLIst.h

3.2 SeqList.c  Test.c

3.2.1顺序表打印

3.2.2顺序表的初始化

3.2.3顺序表销毁

3.2.4顺序表空间检查扩容

3.2.5顺序表尾插

3.2.6顺序表尾删

3.2.7顺序表头插

3.2.8顺序表头删

3.2.9顺序表在pos位置插入x

3.2.10 删除pos位置元素

3.2.11 修改pos位置数据为x

3.2.12 查找数据x的位置并返回

3.3 SeqList.h  SeqList.c 总览

1.线性表

线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构，相当于连续的一条直线。但在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式进行存储。

2.顺序表

2.1顺序表的概念及结构

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

2.2顺序表的优缺点

优点：

        连续的物理空间，方便下标随机访问。

缺陷：

        不能按需申请和删除空间

        插入数据时，空间不够需要扩容，扩容有性能消耗(realloc空间不够时异地扩容，性能消耗大)

        头部或者中间位置插入删除数据，需要挪动数据，效率较低

        可能存在一定空间占用，浪费空间

2.3动态、静态顺序表的区分

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储元素

 2.动态顺序表：使用动态开辟的数组存储

3.动态顺序表的实现

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

3.1 SeqLIst.h

进行头文件、顺序表结构体的声明、顺序表函数的声明

  1. //防止头文件重复
  2. #pragma once
  3.  
  4. //包含头文件
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <assert.h>
  8.  
  9. //将存储数据类型重定义方便修改存储数据的类型
  10. //SL(动态顺序表SeqList的缩写) DataType(数据类型)
  11. typedef int SLDataType;
  12.  
  13. //动态顺序表
  14. typedef struct SeqList 
  15. {
  16. 	SLDataType* list;//动态开辟数据存储数据元素
  17. 	int size; //存储的数据个数
  18. 	int capacity;//存储空间大小
  19. }SeqList;
  20.  
  21.  
  22. //打印
  23. void SeqListPrint(SeqList* psl);
  24. //初始化
  25. void SeqListInit(SeqList* psl);
  26. //检查空间大小是否已满，若已满则扩容
  27. void SeqListCheckCapacity(SeqList* psl);
  28. //顺序表销毁 
  29. void SeqListDestroy(SeqList* psl);
  30.  
  31.  
  32. //尾插
  33. void SeqListPushBack(SeqList* psl, SLDataType x);
  34. //尾删
  35. void SeqListPopBack(SeqList* psl);
  36. //头插
  37. void SeqListPushFront(SeqList* psl, SLDataType x);
  38. //头删
  39. void SeqListPopFront(SeqList* psl);
  40.  
  41.  
  42. //数据查找 
  43. int SeqListFind(SeqList* psl, SLDataType x);
  44. //数据插入
  45. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
  46. //数据删除
  47. void SeqListErase(SeqList* psl, size_t pos);
  48. //数据修改
  49. void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

3.2 SeqList.c  Test.c

逐个实现顺序表函数并同时进行测试检查

对于函数功能的实现要做到写一个检查一个，千万不要一股脑全部然后写完觉得自己很nb，结果最后进行测试的时候一堆bug，而且难以寻根觅源，折磨的还是你自己。

 

3.2.1顺序表打印

  1. //打印顺序表
  2. void SeqListPrint(SeqList* psl)
  3. {
  4.     //对空指针进行断言，显示出错位置
  5. 	assert(psl);
  6. 	for (int i = 0; i < psl->size; i++)
  7. 	{
  8. 		printf("%d ", psl->list[i]);
  9. 	}
  10. 	printf("\n");
  11. }

3.2.2顺序表的初始化

  1. //动态顺序表的初始化
  2. void SeqListInit(SeqList* psl)
  3. {
  4. 	assert(psl);
  5. 	psl->list = NULL;
  6. 	psl->size = 0;
  7. 	psl->capacity = 0;
  8. }

3.2.3顺序表销毁

  1. //顺序表销毁 
  2. void SeqListDestroy(SeqList* psl)
  3. {
  4. 	assert(psl);
  5. 	free(psl->list);
  6. 	psl->list = NULL;
  7. 	psl->capacity = psl->size = 0;
  8. }

3.2.4顺序表空间检查扩容

 当size与capacity相等时，顺序表已满需要扩容

  1. //顺序表空间扩容
  2. void SeqListCheckCapacity(SeqList* psl)
  3. {
  4. 	assert(psl);
  5. 	//当数据个数与存储空间相等时，数组已满
  6. 	//如果数组满了，使用realloc进行扩容
  7. 	if (psl->size == psl->capacity)
  8. 	{
  9. 		//当capacity为0时为其赋值为4，若不为0则进行倍增
  10. 		size_t NewCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  11. 		//将当前的空间翻倍扩容
  12. 		SLDataType* tmp = realloc(psl->list, sizeof(SLDataType) * NewCapacity);
  13. 		//realloc扩容可能失败，需要对其进行检查
  14. 		if (tmp == NULL)
  15. 		{
  16. 			printf("realloc fail\n");
  17. 			exit(-1);//终止程序
  18. 		}
  19. 		else
  20. 		{
  21. 			psl->list = tmp;
  22. 			psl->capacity = NewCapacity;
  23. 		}
  24. 	}
  25. }

3.2.5顺序表尾插

                  

  1. //顺序表尾插
  2. void SeqListPushBack(SeqList* psl, SLDataType x)
  3. {
  4. 	assert(psl);
  5.     
  6.     //检查顺序表是否已满，若满则扩容
  7.     SeqListCheckCapacity(psl);
  8.  
  9. 	//在表尾部插入数据
  10. 	psl->list[psl->size] = x;
  11. 	psl->size++;
  12. }

Tset.c 中进行测试

  1. #include "SeqList.h"
  2.  
  3. int main()
  4. {
  5. 	SeqList s;
  6. 	SeqListInit(&s);
  7. 	SeqListPushBack(&s, 1);
  8. 	SeqListPushBack(&s, 2);
  9. 	SeqListPushBack(&s, 3);
  10. 	SeqListPushBack(&s, 4);
  11. 	SeqListPushBack(&s, 5);
  12. 	SeqListPrint(&s);
  13.  
  14. 	return 0;
  15. }

测试结果

 (之后的bug测试自己进行，不再赘述)

3.2.6顺序表尾删

                          

                   

 当size小于0时，会越界访问导致头插失败。所以要有判断条件size > 0.

  1. //顺序表尾删
  2. void SeqListPopBack(SeqList* psl)
  3. {
  4. 	assert(psl);
  5. 	//if判断 限制size大于0
  6. 	if (psl->size > 0)
  7. 	{
  8. 		psl->size--;
  9. 	}
  10. }

3.2.7顺序表头插

 

  1. //顺序表头插
  2. void SeqListPushFront(SeqList* psl, SLDataType x)
  3. {
  4. 	assert(psl);
  5.     
  6.     //检查顺序表是否已满，若满则扩容
  7. 	SeqListCheckCapacity(psl);
  8.  
  9. 	//将所有位置的数据从后往前，往后移动一位
  10. 	int end = psl->size - 1;
  11. 	while (end >= 0)
  12. 	{
  13. 		psl->list[end + 1] = psl->list[end];
  14. 		end--;
  15. 	}
  16.  
  17. 	//在表头位置插入数据
  18. 	psl->list[0] = x;
  19. 	psl->size++;
  20. }

3.2.8顺序表头删

 当表中无数据时，头删会使数组越界。导致后续操作出错。

  1. //顺序表头删
  2. void SeqListPopFront(SeqList* psl)
  3. {
  4. 	assert(psl);
  5.  
  6. 	//判断表中是否有数据
  7. 	if (psl->size > 0)
  8. 	{
  9. 		//将表头后的数据从前往后，往前移动一位
  10. 		int pos = 1;
  11. 		while (pos < psl->size)
  12. 		{
  13. 			psl->list[pos - 1] = psl->list[pos];
  14. 			++pos;
  15. 		}
  16.  
  17. 		--psl->size;
  18. 	}
  19. }

3.2.9顺序表在pos位置插入x

 

  1. //在pos位置插入x
  2. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
  3. {
  4. 	assert(psl);
  5.  
  6. 	//检查输入的pos是否越界
  7. 	assert(pos <= psl->size);
  8.  
  9. 	int end = psl->size - 1;
  10. 	//将pos之后的数据从后往前，往后移动一位
  11. 	while (end >= pos)
  12. 	{
  13. 		psl->list[end + 1] = psl->list[end];
  14. 		--end;
  15. 	}
  16.  
  17. 	//在pos位置插入x
  18. 	psl->list[pos] = x;
  19. 	psl->size++;
  20. }

3.2.10 删除pos位置元素

 

  1. //删除pos位置数据
  2. void SeqListErase(SeqList* psl, size_t pos)
  3. {
  4. 	assert(psl);
  5. 	assert(pos < psl->size);
  6.  
  7. 	size_t begin = pos + 1;
  8.     //将pos位置后的元素从前往后，往前移动一位
  9. 	while (begin < psl->size)
  10. 	{
  11. 		psl->list[begin - 1] = psl->list[begin];
  12. 		++begin;
  13. 	}
  14.  
  15. 	psl->size--;
  16. }

3.2.11 修改pos位置数据为x

  1. //数据修改
  2. void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
  3. {
  4. 	assert(psl);
  5. 	assert(pos < psl->size);
  6.  
  7. 	psl->list[pos] = x;
  8. }

3.2.12 查找数据x的位置并返回

  1. //数据查找 
  2. int SeqListFind(SeqList* psl, SLDataType x)
  3. {
  4. 	assert(psl);
  5.  
  6. 	for (int i = 0; i < psl->size; i++)
  7. 	{
  8. 		if (psl->list[i] == x)
  9. 		{
  10. 			return i;
  11. 		}
  12.  
  13. 		return -1;
  14. 	}
  15. }

3.3 SeqList.h  SeqList.c 总览

  1. //防止头文件重复
  2. #pragma once
  3.  
  4. //包含头文件
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <assert.h>
  8.  
  9. //将存储数据类型重定义方便修改存储数据的类型
  10. //SL(动态顺序表SeqList的缩写) DataType(数据类型)
  11. typedef int SLDataType;
  12.  
  13. //动态顺序表
  14. typedef struct SeqList 
  15. {
  16. 	SLDataType* list;//动态开辟数据存储数据元素
  17. 	int size; //存储的数据个数
  18. 	int capacity;//存储空间大小
  19. }SeqList;
  20.  
  21. //打印
  22. void SeqListPrint(SeqList* psl);
  23. //初始化
  24. void SeqListInit(SeqList* psl);
  25. //检查空间扩容
  26. void SeqListCheckCapacity(SeqList* psl);
  27. //顺序表销毁 
  28. void SeqListDestroy(SeqList* psl);
  29. //尾插
  30. void SeqListPushBack(SeqList* psl, SLDataType x);
  31. //尾删
  32. void SeqListPopBack(SeqList* psl);
  33. //头插
  34. void SeqListPushFront(SeqList* psl, SLDataType x);
  35. //头删
  36. void SeqListPopFront(SeqList* psl);
  37. //数据查找 
  38. int SeqListFind(SeqList* psl, SLDataType x);
  39. //数据插入
  40. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
  41. //数据删除
  42. void SeqListErase(SeqList* psl, size_t pos);
  43. //数据修改
  44. void SeqListModify(SeqList* psl, size_t pos, SLDataType x);
  1. #include "SeqList.h"
  2.  
  3.  
  4. //打印顺序表
  5. void SeqListPrint(SeqList* psl)
  6. {
  7. 	//对空指针进行断言，显示出错位置
  8. 	assert(psl);
  9. 	for (int i = 0; i < psl->size; i++)
  10. 	{
  11. 		printf("%d ", psl->list[i]);
  12. 	}
  13. 	printf("\n");
  14. }
  15.  
  16. //动态顺序表的初始化
  17. void SeqListInit(SeqList* psl)
  18. {
  19. 	//对空指针进行断言，显示出错位置
  20. 	assert(psl);
  21. 	psl->list = NULL;
  22. 	psl->size = 0;
  23. 	psl->capacity = 0;
  24. }
  25.  
  26. //顺序表销毁  
  27. void SeqListDestroy(SeqList* psl)
  28. {
  29. 	assert(psl);
  30. 	free(psl->list);
  31. 	psl->list = NULL;
  32. 	psl->capacity = psl->size = 0;
  33. }
  34.  
  35. //顺序表空间扩容
  36. void SeqListCheckCapacity(SeqList* psl)
  37. {
  38. 	assert(psl);
  39. 	//当数据个数与存储空间相等时，数组已满
  40. 	//如果数组满了，使用realloc进行扩容
  41. 	if (psl->size == psl->capacity)
  42. 	{
  43. 		//当capacity为0时为其赋值为4，若不为0则进行倍增
  44. 		size_t NewCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  45. 		//将当前的空间翻倍扩容
  46. 		SLDataType* tmp = realloc(psl->list, sizeof(SLDataType) * NewCapacity);
  47. 		//realloc扩容可能失败，需要对其进行检查
  48. 		if (tmp == NULL)
  49. 		{
  50. 			printf("realloc fail\n");
  51. 			exit(-1);//终止程序
  52. 		}
  53. 		else
  54. 		{
  55. 			psl->list = tmp;
  56. 			psl->capacity = NewCapacity;
  57. 		}
  58. 	}
  59. }
  60.  
  61. //顺序表尾插
  62. void SeqListPushBack(SeqList* psl, SLDataType x)
  63. {
  64. 	//对空指针进行断言，显示出错位置
  65. 	assert(psl);
  66. 	//插入数据
  67.  
  68. 	SeqListCheckCapacity(psl);
  69.  
  70. 	psl->list[psl->size] = x;
  71. 	psl->size++;
  72. }
  73.  
  74. //顺序表尾删
  75. void SeqListPopBack(SeqList* psl)
  76. {
  77. 	//对空指针进行断言，显示出错位置
  78. 	assert(psl);
  79. 	//if判断 限制size大于0
  80. 	if (psl->size > 0)
  81. 	{
  82. 		psl->size--;
  83. 	}
  84. }
  85.  
  86. //顺序表头插
  87. void SeqListPushFront(SeqList* psl, SLDataType x)
  88. {
  89. 	assert(psl);
  90.  
  91. 	SeqListCheckCapacity(psl);
  92.  
  93. 	//将所有位置的数据从后往前，往后移动一位
  94. 	int end = psl->size - 1;
  95. 	while (end >= 0)
  96. 	{
  97. 		psl->list[end + 1] = psl->list[end];
  98. 		end--;
  99. 	}
  100.  
  101. 	//在表头位置插入数据
  102. 	psl->list[0] = x;
  103. 	psl->size++;
  104. }
  105.  
  106. //顺序表头删
  107. void SeqListPopFront(SeqList* psl)
  108. {
  109. 	assert(psl);
  110.  
  111. 	//判断表中是否有数据
  112. 	if (psl->size > 0)
  113. 	{
  114. 		//将表头后的数据从前往后，往前移动一位
  115. 		int pos = 1;
  116. 		while (pos < psl->size)
  117. 		{
  118. 			psl->list[pos - 1] = psl->list[pos];
  119. 			++pos;
  120. 		}
  121.  
  122. 		--psl->size;
  123. 	}
  124. }
  125.  
  126. //数据查找 
  127. int SeqListFind(SeqList* psl, SLDataType x)
  128. {
  129. 	assert(psl);
  130.  
  131.  
  132. 	for (int i = 0; i < psl->size; i++)
  133. 	{
  134. 		if (psl->list[i] == x)
  135. 		{
  136. 			return i;
  137. 		}
  138.  
  139.  
  140. 		return -1;
  141. 	}
  142. }
  143.  
  144. //在pos位置插入x
  145. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
  146. {
  147. 	assert(psl);
  148.  
  149. 	//检查输入的pos是否越界
  150. 	assert(pos <= psl->size);
  151.  
  152. 	int end = psl->size - 1;
  153. 	//将pos之后的数据从后往前，往后移动一位
  154. 	while (end >= pos)
  155. 	{
  156. 		psl->list[end + 1] = psl->list[end];
  157. 		--end;
  158. 	}
  159.  
  160. 	//在pos位置插入x
  161. 	psl->list[pos] = x;
  162. 	psl->size++;
  163. }
  164.  
  165. //删除pos位置数据
  166. void SeqListErase(SeqList* psl, size_t pos)
  167. {
  168. 	assert(psl);
  169. 	assert(pos < psl->size);
  170. 	size_t begin = pos + 1;
  171. 	while (begin < psl->size)
  172. 	{
  173. 		psl->list[begin - 1] = psl->list[begin];
  174. 		++begin;
  175. 	}
  176.  
  177. 	psl->size--;
  178. }
  179.  
  180. //数据修改
  181. void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
  182. {
  183. 	assert(psl);
  184. 	assert(pos < psl->size);
  185.  
  186. 	psl->list[pos] = x;
  187. }

          顺序表到这里也就实现完成了，现在可以通过Test.c程序对顺序表进行调试和使用了。

          看到这里祝你考试科科满昏~~  ouo

 

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

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

  

闽ICP备14008679号