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

C语言实现顺序表_顺序表c语言实现

作者：Cpp五条 | 2024-04-21 02:46:25

赞

踩

顺序表c语言实现

前言

数据结构常见的结构有线性结构、树型结构、图形结构。

而线性结构又分为线性表、栈、数组、队列，本文讲的是顺序表，是线性表的一种。

 一、项目

1.1 SeqList.h（头文件)

  1. #pragma once
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5. #define Max_Capacity 10
  6.  
  7.  
  8. typedef int SLDateType;
  9. //顺序表
  10. typedef struct SeqList
  11. {
  12. 	//顺序表地址q
  13. 	SLDateType* a;
  14. 	//顺序表的有效长度
  15. 	int size;
  16. 	//顺序表大小
  17. 	int capacity;
  18. }SeqList;
  19.  
  20. //初始化顺序表
  21. void SeqListInit(SeqList* ps);
  22. //销毁顺序表
  23. void SeqListDestroy(SeqList* ps);
  24.  
  25.  
  26. //打印顺序表
  27. void SeqListPrint(SeqList* ps);
  28. //头插
  29. void SeqListPushFront(SeqList* ps, SLDateType x);
  30. //尾插
  31. void SeqListPushBack(SeqList* ps, SLDateType x);
  32. //头删
  33. void SeqListPopFront(SeqList* ps);
  34. //尾删
  35. void SeqListPopBack(SeqList* ps);
  36. //中间插
  37. void SeqListInsert(SeqList* ps, int pos, int x);
  38. //中间删
  39. void SeqListErase(SeqList* ps, int pos);
  40.  
  41.  
  42. //检查顺序表是否满了
  43. SLDateType SeqListFull(SeqList* ps);
  44. //顺序表扩容
  45. void SeqListAdd(SeqList* ps);
  46.  
  47.  
  48. //顺序表中查数
  49. void SeqListSearch(SeqList* ps, SLDateType x);
  50. //顺序表中改数
  51. void SeqListChange(SeqList* ps, SLDateType x,SLDateType y);

1.2 SeqList.c

  1. #include"SeqList.h"
  2.  
  3. //初始化顺序表
  4. void SeqListInit(SeqList* ps)
  5. {
  6. 	ps->a = NULL;
  7. 	ps->size = 0;
  8. 	ps->capacity = 0;
  9. }
  10.  
  11. //打印顺序表
  12. void SeqListPrint(SeqList* ps)
  13. {
  14. 	assert(ps);
  15. 	if (ps->size == 0)
  16. 	{
  17. 		printf("顺序表无有效数据\n");
  18. 		return;
  19. 	}
  20. 	for (SLDateType i = 0; i < ps->size; i++)
  21. 	{
  22. 		printf("%d ", *(ps->a + i));
  23. 	}
  24. 	printf("\n");
  25. }
  26.  
  27. //销毁顺序表
  28. void SeqListDestroy(SeqList* ps)
  29. {
  30. 	assert(ps);
  31. 	free(ps->a);
  32. 	ps->a = NULL;
  33. 	ps->size = 0;
  34. 	ps->capacity = 0;
  35. }
  36.  
  37. //判断顺序表是否满了
  38. SLDateType SeqListFull(SeqList* ps)
  39. {
  40. 	assert(ps);
  41. 	if (ps->size == ps->capacity)
  42. 	{
  43. 		return 1;
  44. 	}
  45. 	return 0;
  46. }
  47.  
  48. //扩容
  49. void SeqListAdd(SeqList* ps)
  50. {
  51. 	assert(ps);
  52. 	ps->a = (SLDateType*)realloc(ps->a,ps->capacity*2*sizeof(SLDateType));
  53. 	if (ps->a == NULL)
  54. 	{
  55. 		perror("realloc error");
  56. 		exit(-1);
  57. 	}
  58. 	ps->capacity *= 2;
  59. }
  60.  
  61. //头插
  62. void SeqListPushFront(SeqList* ps, SLDateType x)
  63. {
  64. 	assert(ps);
  65. 	if (ps->size < 0)
  66. 	{
  67. 		ps->size = 0;
  68. 	}
  69. 	if (SeqListFull(ps))
  70. 	{
  71. 		SeqListAdd(ps);
  72. 	}
  73. 	for(SLDateType i = ps->size-1; i >=0; i--)
  74. 	{
  75. 		ps->a[i + 1] = ps->a[i];
  76. 	}
  77. 	ps->a[0] = x;
  78. 	ps->size++;
  79. }
  80.  
  81. //尾插
  82. void SeqListPushBack(SeqList* ps, SLDateType x)
  83. {
  84. 	assert(ps);
  85. 	if (ps->size < 0)
  86. 	{
  87. 		ps->size = 0;
  88. 	}
  89. 	if (SeqListFull(ps))
  90. 	{
  91. 		SeqListAdd(ps);
  92. 	}
  93. 	ps->a[ps->size] = x;
  94. 	ps->size++;
  95. }
  96.  
  97. //头删
  98. void SeqListPopFront(SeqList* ps)
  99. {
  100. 	assert(ps);
  101. 	if (ps->size <=0)
  102. 	{
  103. 		ps->size = 0;
  104. 		return;
  105. 	}
  106. 	for (SLDateType i = 1; i < ps->size; i++)
  107. 	{
  108. 		ps->a[i - 1] = ps->a[i];
  109. 	}
  110. 	ps->size--;
  111. }
  112.  
  113. //尾删
  114. void SeqListPopBack(SeqList* ps)
  115. {
  116. 	assert(ps);
  117. 	if (ps->size <= 0)
  118. 	{
  119. 		ps->size = 0;
  120. 		return;
  121. 	}
  122. 	ps->size--;
  123. }
  124.  
  125. //中间插
  126. void SeqListInsert(SeqList* ps,int pos,int x)
  127. {
  128. 	assert(ps);
  129. 	if (ps->size <0)
  130. 	{
  131. 		ps->size = 0;
  132. 	}
  133. 	if (SeqListFull(ps))
  134. 	{
  135. 		SeqListAdd(ps);
  136. 	}
  137. 	if (pos - 1 < ps->size)
  138. 	{
  139. 		for(SLDateType i = ps->size - 1; i >= pos - 1; i--)
  140. 			ps->a[i + 1] = ps->a[i];
  141. 		ps->a[pos - 1] = x;
  142. 		ps->size++;
  143. 	}
  144. 	else
  145. 		printf("插入无效\n");
  146. }
  147.  
  148. //中间删
  149. void SeqListErase(SeqList* ps, int pos)
  150. {
  151. 	assert(ps);
  152. 	if (ps->size <= 0)
  153. 	{
  154. 		ps->size = 0;
  155. 		return;
  156. 	}
  157. 	if (pos - 1 < ps->size)
  158. 	{
  159. 		for (SLDateType i = pos; i < ps->size; i++)
  160. 			ps->a[i - 1] = ps->a[i];
  161. 		ps->size--;
  162. 	}
  163. 	else
  164. 		printf("删除无效\n");
  165. }
  166.  
  167. //查
  168. void SeqListSearch(SeqList* ps, int pos)
  169. {
  170. 	assert(ps);
  171. 	if (ps->size <= 0)
  172. 	{
  173. 		ps->size = 0;
  174. 	}
  175. 	if (pos - 1 < ps->size)
  176. 	{
  177. 		printf("%d\n",ps->a[pos - 1]);
  178. 		return;
  179. 	}
  180. 	printf("查找无效\n");
  181. }
  182.  
  183. //改
  184. void SeqListChange(SeqList* ps, int pos, int x)
  185. {
  186. 	assert(ps);
  187. 	if (ps->size <= 0)
  188. 	{
  189. 		ps->size = 0;
  190. 		return;
  191. 	}
  192. 	if (pos - 1 < ps->size)
  193. 	{
  194. 		ps->a[pos - 1] = x;
  195. 	}
  196. 	else
  197. 		printf("修改无效\n");
  198. }

1.3 test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"SeqList.h"
  3. SLDateType main()
  4. {
  5.     //创造顺序表
  6.     SeqList sl;
  7.     //初始化
  8.     SeqListInit(&sl);
  9.     sl.capacity = Max_Capacity;
  10.     sl.a = (SLDateType*)realloc(sl.a,sl.capacity * sizeof(SLDateType));
  11.     if (sl.a == NULL)
  12.     {
  13.         perror("realloc error");
  14.         exit(-1);
  15.     }
  16.     //尾插012345
  17.     for (SLDateType i = 0; i < 5; i++)
  18.         SeqListPushBack(&sl, i);
  19.     //打印顺序表
  20.     SeqListPrint(&sl);
  21.     //头插012345
  22.     for (SLDateType i = 0; i < 5; i++)
  23.         SeqListPushFront(&sl, i);
  24.     //再次打印
  25.     SeqListPrint(&sl);
  26.     //尾删3个数
  27.     for (SLDateType i = 0; i < 3; i++)
  28.         SeqListPopBack(&sl);
  29.     SeqListPrint(&sl);
  30.     //头删2个数
  31.     for(SLDateType i=0;i<2;i++)
  32.        SeqListPopFront(&sl);
  33.     SeqListPrint(&sl);
  34.     //中间第三个数插入2
  35.     SeqListInsert(&sl, 3, 2);
  36.     SeqListPrint(&sl);
  37.     //中间第三个数删除
  38.     SeqListErase(&sl, 3);
  39.     SeqListPrint(&sl);
  40.     //查找第3个数
  41.     SeqListSearch(&sl, 3);
  42.     //修改第3个数为100
  43.     SeqListChange(&sl, 3, 100);
  44.     SeqListPrint(&sl);
  45.     //销毁顺序表
  46.     SeqListDestroy(&sl);
  47.     return 0;
  48. }

二、顺序表的实现

2.1 顺序表

  1. typedef int SLDateType;
  2. //顺序表
  3. typedef struct SeqList
  4. {
  5. 	//顺序表地址q
  6. 	SLDateType* a;
  7. 	//顺序表的有效长度
  8. 	int size;
  9. 	//顺序表大小
  10. 	int capacity;
  11. }SeqList;

创建一个顺序表结构体，成员包含顺序表地址、长度、大小，用于创建顺序表变量。

2.2 初始化顺序表

  1. //初始化顺序表
  2. void SeqListInit(SeqList* ps)
  3. {
  4.     ps->a = NULL;
  5.     ps->size = 0;
  6.     ps->capacity = 0;
  7. }

 将顺序表变量的地址传参，通过指针接收对顺序表的顺序表数组初始化为空，长度为0，大小为0。

2.3 打印顺序表

  1. //打印顺序表
  2. void SeqListPrint(SeqList* ps)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size == 0)
  6. 	{
  7. 		printf("顺序表无有效数据\n");
  8. 		return;
  9. 	}
  10. 	for (SLDateType i = 0; i < ps->size; i++)
  11. 	{
  12. 		printf("%d ", *(ps->a + i));
  13. 	}
  14. 	printf("\n");
  15. }

同样传地址，要先断言指针是否为空，不然会出异常。

然后判断顺序表大小是否为0，为0则代表顺序表中没有有效元素，打印提示，并返回函数，如果大于0，则有元素，从下标0开始，打印size个顺序表元素，并用空格相隔。

2.4 销毁顺序表

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

当我们结束程序时，因为我们是通过动态分配空间给顺序表，所以结束时我们要手动销毁，先断言，防止free空指针，成功释放空间后，将ps->a手动置空，避免产生野指针，并将大小、空间赋0。

三、对顺序表进行操作

3.1 在顺序表的头部插入数据

  1. //头插
  2. void SeqListPushFront(SeqList* ps, SLDateType x)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size < 0)
  6. 	{
  7. 		ps->size = 0;
  8. 	}
  9. 	if (SeqListFull(ps))
  10. 	{
  11. 		SeqListAdd(ps);
  12. 	}
  13. 	for(SLDateType i = ps->size-1; i >=0; i--)
  14. 	{
  15. 		ps->a[i + 1] = ps->a[i];
  16. 	}
  17. 	ps->a[0] = x;
  18. 	ps->size++;
  19. }

在头部插入数据，要先判断容量是否已满，如果已满，需要扩容，还有空间，那么就从下标为ps->size-1开始，到0上的值都要将前一个元素给覆盖，而将要插入的数据覆盖给下标为0的空间，长度加1。

3.2 在顺序表末尾插入数据

  1. //尾插
  2. void SeqListPushBack(SeqList* ps, SLDateType x)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size < 0)
  6. 	{
  7. 		ps->size = 0;
  8. 	}
  9. 	if (SeqListFull(ps))
  10. 	{
  11. 		SeqListAdd(ps);
  12. 	}
  13. 	ps->a[ps->size] = x;
  14. 	ps->size++;
  15. }

都是插入数据，所以前面的操作和头插一致，但是尾插要比头插看起来方便，因为只要在顺序表后一个空间内插入要插入的数据，不需要移动数据，并将长度+1。

3.3 删除在顺序表头部的数

  1.  
  2. //头删
  3. void SeqListPopFront(SeqList* ps)
  4. {
  5. 	assert(ps);
  6. 	if (ps->size <=0)
  7. 	{
  8. 		ps->size = 0;
  9.         return;
  10. 	}
  11. 	for (SLDateType i = 1; i < ps->size; i++)
  12. 	{
  13. 		ps->a[i - 1] = ps->a[i];
  14. 	}
  15. 	ps->size--;
  16. }

判断部分不需要判断容量是否够，且长度不能为负数。

和头插相反，我们要从下标为1，到ps->size-1，将前一个数覆盖，长度减1。

3.4 删除在顺序表末尾的数

  1. //尾删
  2. void SeqListPopBack(SeqList* ps)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size <= 0)
  6. 	{
  7. 		ps->size = 0;
  8. 		return;
  9. 	}
  10. 	ps->size--;
  11. }

判断部分一致，尾删只需将长度减一即可。

3.5 在顺序表中间位置插入数据

  1. //中间插
  2. void SeqListInsert(SeqList* ps,int pos,int x)
  3. {
  4.     assert(ps);
  5.     if (ps->size <0)
  6.     {
  7.         ps->size = 0;
  8.     }
  9.     if (SeqListFull(ps))
  10.     {
  11.         SeqListAdd(ps);
  12.     }
  13.     if (pos - 1 < ps->size)
  14.     {
  15.         for(SLDateType i = ps->size - 1; i >= pos - 1; i--)
  16.             ps->a[i + 1] = ps->a[i];
  17.         ps->a[pos - 1] = x;
  18.         ps->size++;
  19.     }
  20.     else
  21.         printf("插入无效\n");
  22. }

中间插比较麻烦，不仅要断言，判断ps->size是否合理，容量是否够，还要判断所给插入数据下标位置是否在0到ps->size之间的合法区域，所以以上同时合法时， 才能实现插入数据，和头插相似，它们都是先从尾部数据开始，先向右整体覆盖过去，但是头插是到0停止，而中间插是到所给下标停止，并将该下标的数插入为想插入的数据，长度加1。

3.6 在顺序表中间位置删除数据

  1. //中间删
  2. void SeqListErase(SeqList* ps, int pos)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size <= 0)
  6. 	{
  7. 		ps->size = 0;
  8. 		return;
  9. 	}
  10. 	if (pos - 1 < ps->size)
  11. 	{
  12. 		for (SLDateType i = pos; i < ps->size; i++)
  13. 			ps->a[i - 1] = ps->a[i];
  14. 		ps->size--;
  15. 	}
  16. 	else
  17. 		printf("删除无效\n");
  18. }

和头删相似，将指定下标左边的元素往左移动一个空间，长度减1。

3.7 在顺序表中查找指定下标的值

  1. //查
  2. void SeqListSearch(SeqList* ps, int pos)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size <= 0)
  6. 	{
  7. 		ps->size = 0;
  8. 	}
  9. 	if (pos - 1 < ps->size)
  10. 	{
  11. 		printf("%d\n",ps->a[pos - 1]);
  12. 		return;
  13. 	}
  14. 	printf("查找无效\n");
  15. }

返回指定下标下的值，比较容易实现。

3.8 将顺序表指定下标的值修改

  1. //改
  2. void SeqListChange(SeqList* ps, int pos, int x)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size <= 0)
  6. 	{
  7. 		ps->size = 0;
  8. 		return;
  9. 	}
  10. 	if (pos - 1 < ps->size)
  11. 	{
  12. 		ps->a[pos - 1] = x;
  13. 	}
  14. 	else
  15. 		printf("修改无效\n");
  16. }

找到指定下标的位置，直接赋给修改的值即可，也很容易实现。

3.9 顺序表的扩容

  1. /判断顺序表是否满了
  2. SLDateType SeqListFull(SeqList* ps)
  3. {
  4. 	assert(ps);
  5. 	if (ps->size == ps->capacity)
  6. 	{
  7. 		return 1;
  8. 	}
  9. 	return 0;
  10. }
  11.  
  12. //扩容
  13. void SeqListAdd(SeqList* ps)
  14. {
  15. 	assert(ps);
  16. 	ps->a = (SLDateType*)realloc(ps->a,ps->capacity*2*sizeof(SLDateType));
  17. 	if (ps->a == NULL)
  18. 	{
  19. 		perror("realloc error");
  20. 		exit(-1);
  21. 	}
  22. 	ps->capacity *= 2;
  23. }

如果ps->size等于容量，代表容量已满，则将容量扩大为原来的两倍，但是可能会出现内存泄漏的情况，严谨一点应该在realloc完后将地址赋给一个新指针，由新指针判断不为空，再赋给顺序表指针，如果扩容失败，程序将会终止。

四、实现程序

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"SeqList.h"
  3. SLDateType main()
  4. {
  5.     //创造顺序表
  6.     SeqList sl;
  7.     //初始化
  8.     SeqListInit(&sl);
  9.     sl.capacity = Max_Capacity;
  10.     sl.a = (SLDateType*)realloc(sl.a,sl.capacity * sizeof(SLDateType));
  11.     if (sl.a == NULL)
  12.     {
  13.         perror("realloc error");
  14.         exit(-1);
  15.     }
  16.     //尾插01234
  17.     for (SLDateType i = 0; i < 5; i++)
  18.         SeqListPushBack(&sl, i);
  19.     //打印顺序表
  20.     SeqListPrint(&sl);
  21.     //头插01234
  22.     for (SLDateType i = 0; i < 5; i++)
  23.         SeqListPushFront(&sl, i);
  24.     //再次打印
  25.     SeqListPrint(&sl);
  26.     //尾删3个数
  27.     for (SLDateType i = 0; i < 3; i++)
  28.         SeqListPopBack(&sl);
  29.     SeqListPrint(&sl);
  30.     //头删2个数
  31.     for(SLDateType i=0;i<2;i++)
  32.        SeqListPopFront(&sl);
  33.     SeqListPrint(&sl);
  34.     //中间第三个数插入2
  35.     SeqListInsert(&sl, 3, 2);
  36.     SeqListPrint(&sl);
  37.     //中间第三个数删除
  38.     SeqListErase(&sl, 3);
  39.     SeqListPrint(&sl);
  40.     //查找第3个数
  41.     SeqListSearch(&sl, 3);
  42.     //修改第3个数为100
  43.     SeqListChange(&sl, 3, 100);
  44.     SeqListPrint(&sl);
  45.     //销毁顺序表
  46.     SeqListDestroy(&sl);
  47.     return 0;
  48. }

用SeqList.c的函数实现我们对顺序表sl的一系列操作，结束时销毁顺序表。

打印结果如下

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号