[数据结构]顺序表

1、顺序表的概念及结构

1.1 线性表

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

2、顺序表分类

2.1顺序表和数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接⼝

2.2顺序表分类

1.静态顺序表:

概念：使用定长数组存储元素

代码示例：

  1. typrdef int SLDataType;
  2. #define N 8
  3. typedef struct SeqList
  4. {
  5.     SLDataType a[N];//定长数组
  6.     int size;       //有效数据个数
  7. }SL;

这就是一个静态顺序表，它又一定的缺陷。

容易出现：空间给少了不够用，给多了造成空间浪费

2.动态顺序表

它的特点是：按需申请

3.动态顺序表的实现

我们首先创建相应的头文件和程序文件

我们现在头文件中，引用头文件，定义所需要的结构体和函数

  1. #include
  2. #include
  3. #include
  4. typedef int SLDataType;
  5.  
  6. typedef struct SeqList
  7. {
  8. 	SLDataType* arr; //存储数据的底层结构
  9. 	int capacity;    //记录顺序表的空间大小
  10. 	int size;        //记录顺序表当前有效的数据个数
  11. }SL;
  12. //初始化：
  13. void SLInit(SL* ps);
  14. //销毁
  15. void SLDestroy(SL* ps);
  16. //顺序表的头部 / 尾部插入
  17. void SLPushFront(SL* ps, SLDataType x);
  18. void SLPushBack(SL* ps, SLDataType x);
  19. //顺序表的头部 / 尾部删除 
  20. void SLPopBack(SL* ps);
  21. void SLPopFront(SL* ps);
  22.  
  23. //打印
  24. void SLPrint(SL* ps);
  25. //删除指定位置的值
  26. void SLInsert(SL* ps, int pos, SLDataType x);
  27. void SLErase(SL* ps, int pos);
  28.

我们先定义一个动态顺序表

注意：这行代码是为了设定我们的数据类型

1.初始化

接下来我们要初始化我们的顺序表。所以我们定义了这个函数

接着我们去源文件写完这个函数，让指针指向NULL大小设定为0完成初始化

  1. void SLInit(SL* ps) 
  2. {
  3. 	ps->arr = NULL;
  4. 	ps->size = ps->capacity = 0;
  5. }

写完了初始化我们可以开始写功能

首先就是头插和尾插

我们接着完善

2.头插

我们先来写头插函数

void SLPushFront(SL* ps, SLDataType x)

首先我们来思考以下问题，一个数组如何头插，以及目前的内存大小能否插入新的数据

假设足够：

数组头插，我们一般将数组的各个元素后移一位然后将数组arr[0]赋值成我们要插入的数据

  1. void SLPushFront(SL* ps, SLDataType x)
  2. {
  3. 	assert(ps);
  4. for (int i = ps->size; i > 0; i--) //i = 1
  5. 	{
  6. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[1] = ps->arr[0]
  7. 	}
  8. 	ps->arr[0] = x;
  9. 	ps->size++;
  10. }

我们不难写出这个函数但是它对吗？

显然存在一定的问题，我们前面的条件是设置在空间充足的情况下，如果空间不足的话，我们该怎么办呢？

当然是扩容啦！！！

所以我们再写一个检查空间是否充足的函数，如果不足顺便扩容。

那么，既然说到扩容，我们应该怎样扩容呢？

我这里有三种扩容方式：

1.一次扩容一个空间

2.一次扩容多个大小的空间

3.成倍的增加空间（1.5倍，2倍）

这里我推荐第三种方法。

理由：

        第一种一次扩容一个空间，好处是不会造成空间的浪费，缺点是如果我们输入大量数据时，它需要多次开辟，导致程序效率低下。

        第二种一次开辟多个空间，有效解决了第一种导致程序小路低下的问题，但是，它也有相应的问题，我们不能确定一次开辟多大的空间合适，如果开辟小了，一样也会和第一种一样多次扩容，影响程序效率，但如果一下周四开辟空间过大，也会导致空间被浪费。

我们先定义函数：

void SLCheckCapacity(SL* ps)

接着判断是否需要扩容，然后扩容空间，但是由于我们初始化直接是NULL所以这里我再加上一个三目操作符，总体代码如下：

  1. void SLCheckCapacity(SL* ps)
  2. {
  3. 	if (ps->size == ps->capacity)
  4. 	{
  5. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  6. 		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
  7. 		if (tmp == NULL) {
  8. 			perror("realloc fail!");
  9. 			exit(1);
  10. 		}
  11. 		//扩容成功
  12. 		ps->arr = tmp;
  13. 		ps->capacity = newCapacity;
  14. 	}
  15. }

这里我设置了tmp变量是为了防止扩容失败。这里我选择的就是扩容原来的两倍。

接下来我们按照上面的思路把头插完善

  1. void SLPushFront(SL* ps, SLDataType x)
  2. {
  3. 	assert(ps);
  4. 	SLCheckCapacity(ps);
  5. 	for (int i = ps->size; i > 0; i--) //i = 1
  6. 	{
  7. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[1] = ps->arr[0]
  8. 	}
  9. 	ps->arr[0] = x;
  10. 	ps->size++;
  11. }

3.尾插

做完了头插，我们可以来试试尾插，数组中尾插是神简单的，如图：

如果空间充足，我们可以直接再尾部插入我们的数据然后吧size++，不够的话先扩容然后再执行

  1. void SLPushBack(SL * ps, SLDataType x)
  2. {
  3. 		assert(ps);
  4. 		SLCheckCapacity(ps);
  5. 		ps->arr[ps->size++] = x;
  6. }

这样头插和尾插就完成了

4.头删

完成了插入那么我们还需要完成删除，删除相比较插入它有什么不同？删除不需要太在意空间。

现在我们先来完成头删。

在数组中我们怎么完成头删的呢？如图

我们一般是把每个数向前移动一位，数组有效长度-1，及size--;

代码示例：

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

注意：我们要确保ps和ps->size不为NULL

5.尾删

这个操作实现起来其实非常简单，我们可以直接size--;

代码示例：

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

完成这些，那么我要上难度了，删除指定位置的值/插入指定位置的值

6.删除指定位置的值

具体思路，就是遍历去寻找所需数值，然后并将该数值之后的数据的下标前移，siza--如图：

代码示例：

  1. void SLErase(SL* ps, int pos) {
  2. 	assert(ps);
  3. 	assert(pos >= 0 && pos < ps->size);
  4.  
  5. 	//pos以后的数据往前挪动一位
  6. 	for (int i = pos; i < ps->size - 1; i++)
  7. 	{
  8. 		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2] = ps->arr[i-1];
  9. 	}
  10. 	ps->size--;
  11. }

7.在指定位置插入值

思路，找到数值将该数值及其后的向后移动一位。size++

如图：

代码示例：

  1. void SLInsert(SL* ps, int pos, SLDataType x) {
  2. 	assert(ps);
  3. 	assert(pos >= 0 && pos <= ps->size);
  4.  
  5. 	SLCheckCapacity(ps);
  6.  
  7. 	//pos及之后的数据往后挪动一位，pos空出来
  8. 	for (int i = ps->size; i > pos; i--)
  9. 	{
  10. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[pos+1] = ps->arr[pos]
  11. 	}
  12. 	ps->arr[pos] = x;
  13. 	ps->size++;
  14. }

注：这是插入，要检查空间是否足够

8.打印

完成这些我们可以来尝试打印我们的顺序表，类似打印数组。

代码示例：

  1. void SLPrint(SL* ps) 
  2. {
  3. 	for (int i = 0; i < ps->size; i++)
  4. 	{
  5. 		printf("%d ", ps->arr[i]);
  6. 	}
  7. 	printf("\n");
  8. }

9.销毁顺序表

在我们之前讲过动态内存开辟，最后要再释放。

代码示例：

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

最后来展示程序代码：

  1. #include"SeqList.h"
  2. void SLInit(SL* ps) 
  3. {
  4. 	ps->arr = NULL;
  5. 	ps->size = ps->capacity = 0;
  6. }
  7. void SLDestroy(SL* ps)
  8. {
  9. 	assert(ps);
  10.  
  11. 	if (ps->arr) {
  12. 		free(ps->arr);
  13. 	}
  14. 	ps->arr = NULL;
  15. 	ps->size = ps->capacity = 0;
  16. }
  17. void SLCheckCapacity(SL* ps)
  18. {
  19. 	if (ps->size == ps->capacity)
  20. 	{
  21. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  22. 		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
  23. 		if (tmp == NULL) {
  24. 			perror("realloc fail!");
  25. 			exit(1);
  26. 		}
  27. 		//扩容成功
  28. 		ps->arr = tmp;
  29. 		ps->capacity = newCapacity;
  30. 	}
  31. }
  32. void SLPushBack(SL * ps, SLDataType x)
  33. {
  34. 		assert(ps);
  35. 		SLCheckCapacity(ps);
  36. 		ps->arr[ps->size++] = x;
  37. }
  38. void SLPushFront(SL* ps, SLDataType x)
  39. {
  40. 	assert(ps);
  41. 	SLCheckCapacity(ps);
  42. 	for (int i = ps->size; i > 0; i--) //i = 1
  43. 	{
  44. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[1] = ps->arr[0]
  45. 	}
  46. 	ps->arr[0] = x;
  47. 	ps->size++;
  48. }
  49. void SLPopBack(SL* ps)
  50. {
  51. 	
  52. 	assert(ps);
  53. 	assert(ps->size);   
  54. 	ps->size--;
  55. 	
  56. }
  57. void SLPopFront(SL* ps)
  58. {
  59. 	assert(ps);
  60. 	assert(ps->size);
  61. 	for (int i = 0; i < ps->size - 1; i++)
  62. 	{
  63. 		ps->arr[i] = ps->arr[i + 1];
  64. 	}
  65. 	ps->size--;
  66. }
  67. void SLInsert(SL* ps, int pos, SLDataType x) {
  68. 	assert(ps);
  69. 	assert(pos >= 0 && pos <= ps->size);
  70. 	SLCheckCapacity(ps);
  71. 	for (int i = ps->size; i > pos; i--)
  72. 	{
  73. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[pos+1] = ps->arr[pos]
  74. 	}
  75. 	ps->arr[pos] = x;
  76. 	ps->size++;
  77. }
  78. void SLErase(SL* ps, int pos) 
  79. {
  80. 	assert(ps);
  81. 	assert(pos >= 0 && pos < ps->size);
  82. 	for (int i = pos; i < ps->size - 1; i++)
  83. 	{
  84. 		ps->arr[i] = ps->arr[i + 1];
  85. 	}
  86. 	ps->size--;
  87. }
  88. void SLPrint(SL* ps) 
  89. {
  90. 	for (int i = 0; i < ps->size; i++)
  91. 	{
  92. 		printf("%d ", ps->arr[i]);
  93. 	}
  94. 	printf("\n");
  95. } 
  96. void SLDestroy(SL* ps) 
  97. {
  98. 	assert(ps);
  99.  
  100. 	if (ps->arr) {
  101. 		free(ps->arr);
  102. 	}
  103. 	ps->arr = NULL;
  104. 	ps->size = ps->capacity = 0;
  105. }
  106. //指定位置之前插入数据
  107. void SLInsert(SL* ps, int pos, SLDataType x) {
  108. 	assert(ps);
  109. 	assert(pos >= 0 && pos <= ps->size);
  110.  
  111. 	SLCheckCapacity(ps);
  112.  
  113. 	//pos及之后的数据往后挪动一位，pos空出来
  114. 	for (int i = ps->size; i > pos; i--)
  115. 	{
  116. 		ps->arr[i] = ps->arr[i - 1]; //ps->arr[pos+1] = ps->arr[pos]
  117. 	}
  118. 	ps->arr[pos] = x;
  119. 	ps->size++;
  120. }
  121. //删除指定位置数据
  122. void SLErase(SL* ps, int pos) {
  123. 	assert(ps);
  124. 	assert(pos >= 0 && pos < ps->size);
  125.  
  126. 	//pos以后的数据往前挪动一位
  127. 	for (int i = pos; i < ps->size - 1; i++)
  128. 	{
  129. 		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2] = ps->arr[i-1];
  130. 	}
  131. 	ps->size--;
  132. }

这样一个循序表完成了，你可以用设计的函数来进行操作。

注：本文转载自blog.csdn.net的Dream_Snowar的文章"https://blog.csdn.net/2301_80017277/article/details/135748260"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！