线性表
线性表是n个具有相同特性的数据元素的有限序列，是一种实际中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串。
线性表在逻辑上是线性结构，即连续的一条直线，但在物理上不一定连续，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表及其特点
数组缺陷：定义数组时必须指定数组大小，但是如果指定的大小不能满足使用空间需求时，就会有问题。
顺序表含义及特点：顺序表本质是数组，是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改，顺序表要从左往右连续存储数据。顺序表的逻辑结构和物理结构都是连续的。
2.顺序表分类：顺序表有两种，包括静态顺序表和动态顺序表
（1） 静态顺序表：使用定长数组存储元素。
1. //顺序表的静态存储 2. #define N 7 3. typedef int SLDataType; 4. 5. typedef struct SeqList 6. { 7. SLDataType array[N];//定长数组 8. size_t size;//有效数据的个数 9. }SeqList;
（2）动态顺序表：使用动态开辟的数组存储。
1. typedef struct SeqList 2. { 3. SLDataType* array;//指向动态开辟的数组 4. size_t size;//有效数据的个数 5. size_t capacity;//容量 6. }SeqList;
3. 顺序表缺陷：
（1）动态增容有性能消耗。
（2）当头部插入数据时，需要挪动数据
顺序表的实现
静态顺序表容量是固定的，因此静态顺序表不实用。那么如何实现动态顺序表呢？
18-dynamicSequenceTable.h（结构体定义和方法声明）
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. 4. //为int类型重新定义新名称 5. //如果后续想把SeqList中成员*a的类型改为float或char,不需要把每个使用*a的地方都修改一遍，直接修改typdef定义类型即可 6. typedef int SeqDataType; 7. 8. typedef struct SeqList 9. { 10. SeqDataType* a; 11. int size;//有效数据的个数 12. int capacity;//容量 13. }SeqList,SEQ; 14. 15. //内存中管理数据的结构增删改查的接口 16. 17. //初始化 18. void SeqListInit(SeqList* seq); 19. 20. //销毁 21. void SeqListDestroy(SeqList* seq); 22. 23. //打印 24. void SeqListPrint(SeqList* seq); 25. 26. //扩容 27. void SeqCheckCapacity(SeqList* seq); 28. 29. //尾插 30. void SeqListPushBack(SeqList* seq, SeqDataType x); 31. 32. //头插 33. void SeqListPushFront(SeqList* seq, SeqDataType x); 34. 35. //尾删 36. void SeqListPopBack(SeqList* seq); 37. 38. //头删 39. void SeqListPopFront(SeqList* seq); 40. 41. //查找 42. int SeqListFind(SeqList* seq, SeqDataType x); 43. 44. //某一位置插入数据 45. void SeqListInsert(SeqList* seq, int pos, SeqDataType x); 46. 47. //某一位置删除数据 48. void SeqListErase(SeqList* seq, int pos); 49. 50. //某一位置删除数据 51. void SeqListModify(SeqList* seq, int pos,SeqDataType x);
18-dynamicSequenceTable.c（方法实现）
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<stdio.h> 3. #include<assert.h> 4. #include<stdlib.h> 5. 6. #include "18-dynamicSequenceTable.h" 7. 8. //初始化 9. void SeqListInit(SeqList* pq) 10. { 11. assert(pq); 12. 13. //初始化每个成员变量的值 14. pq->a = NULL; 15. pq->size = 0; 16. pq->capacity = 0; 17. } 18. 19. //销毁 20. void SeqListDestroy(SeqList* pq) 21. { 22. assert(pq); 23. free(pq->a); 24. pq->a = NULL; 25. pq->size = 0; 26. pq->capacity = 0; 27. } 28. 29. //扩容 30. void SeqCheckCapacity(SeqList* pq) 31. { 32. //判断是否需要扩容 33. if (pq->size == pq->capacity) 34. { 35. //如果capacity=0，就申请4个a的空间，如果不为0，就申请2倍大的capacity的空间 36. //一般扩容都扩容成原来2倍，太小则需要频繁扩容，太大则有可能浪费较多空间 37. int newCapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; 38. SeqDataType* newA = (SeqDataType*)realloc(pq->a, sizeof(SeqDataType) * newCapacity); 39. if (newA == NULL) 40. { 41. printf("realloc fail\n"); 42. return; 43. } 44. pq->a = newA; 45. pq->capacity = newCapacity; 46. } 47. } 48. 49. //尾插 50. void SeqListPushBack(SeqList* pq, SeqDataType x) 51. { 52. assert(pq); 53. 54. //判断是否需要扩容 55. SeqCheckCapacity(pq); 56. 57. //把第size个元素值置为x 58. pq->a[pq->size] = x; 59. 60. //size++ 61. pq->size++; 62. } 63. 64. //头插 65. void SeqListPushFront(SeqList* pq, SeqDataType x) 66. { 67. assert(pq); 68. 69. //判断是否需要扩容 70. SeqCheckCapacity(pq); 71. 72. //在第一个位置插入数据需要把所有元素向后挪动一个位置，要从最后一个元素开始依次把所有数据拷贝到下一个位置 73. int end = pq->size-1; 74. while (end>=0) 75. { 76. //将元素拷贝到该元素下一个位置 77. pq->a[end + 1] = pq->a[end]; 78. end--; 79. } 80. 81. //将x放在第一个位置 82. pq->a[0] = x; 83. 84. //size++ 85. pq->size++; 86. } 87. 88. //打印 89. void SeqListPrint(SeqList* pq) 90. { 91. assert(pq); 92. int i = 0; 93. for (i = 0; i < pq->size; i++) 94. { 95. printf("%d ", pq->a[i]); 96. } 97. printf("\n"); 98. } 99. 100. //尾删 101. void SeqListPopBack(SeqList* pq) 102. { 103. assert(pq); 104. assert(pq->size>0); 105. 106. //直接将元素个数-1即可，数据删除不删除无所谓 107. pq->size--; 108. } 109. 110. //头删 111. void SeqListPopFront(SeqList* pq) 112. { 113. assert(pq); 114. assert(pq->size > 0); 115. int begin = 0; 116. while (begin < pq->size) 117. { 118. //删除第一个元素，需要从前往后将其余元素依次拷贝到数组中，如果从后往前拷贝，那么所有元素值都为最后一个元素值 119. pq->a[begin] = pq->a[begin + 1]; 120. begin++; 121. } 122. 123. //size-1 124. pq->size--; 125. } 126. 127. //查找 128. int SeqListFind(SeqList* pq, SeqDataType x) 129. { 130. assert(pq); 131. int i = 0; 132. for (i = 0; i < pq->size; i++) 133. { 134. if (pq->a[i] = x) 135. { 136. return i; 137. } 138. } 139. 140. return -1; 141. } 142. 143. //某一位置插入数据 144. void SeqListInsert(SeqList* pq, int pos, SeqDataType x) 145. { 146. assert(pq); 147. assert(pos>0 && pos < pq->size); 148. 149. //判断是否需要扩容 150. SeqCheckCapacity(pq); 151. 152. //从后往前拷贝数据 153. int i = pq->size-1; 154. while (i >= pos) 155. { 156. pq->a[i + 1] = pq->a[i]; 157. i--; 158. } 159. 160. pq->a[pos] = x; 161. pq->size++; 162. } 163. 164. //某一位置删除数据 165. void SeqListErase(SeqList* pq, int pos) 166. { 167. assert(pq); 168. assert(pos > 0 && pos < pq->size); 169. 170. int i = pos; 171. while (i < pq->size) 172. { 173. pq->a[i] = pq->a[i + 1]; 174. i++; 175. } 176. pq->size--; 177. } 178. 179. //修改某一位置数据 180. void SeqListModify(SeqList* pq, int pos, SeqDataType x) 181. { 182. assert(pq); 183. assert(pos >= 0 && pos < pq->size); 184. 185. pq->a[pos] = x; 186. }
头插需要从后向前拷贝的原因：如果从前向后对数组依次拷贝，先拷贝1，最后拷贝5，就会把所有数据都变成小标为0的元素，因此要从后向前拷贝，先拷贝5，最后拷贝1。
18-test.c（测试、方法调用）
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<stdio.h> 3. #include "18-dynamicSequenceTable.h" 4. 5. TestSEQList1() 6. { 7. SeqList s = {NULL,0,0}; 8. 9. //想要修改结构体变量，必须传结构体的地址 10. //因此SeqListInit的实参是结构体地址，形参应该是指针，用来接收结构体地址，其他方法同理 11. SeqListInit(&s); 12. 13. //尾插 1 2 3 4 5 14. SeqListPushBack(&s, 1); 15. SeqListPushBack(&s, 2); 16. SeqListPushBack(&s, 3); 17. SeqListPushBack(&s, 4); 18. SeqListPushBack(&s, 5); 19. 20. //头插 0 0 0 0 0 21. SeqListPushFront(&s, 0); 22. SeqListPushFront(&s, 0); 23. SeqListPushFront(&s, 0); 24. SeqListPushFront(&s, 0); 25. SeqListPushFront(&s, 0); 26. SeqListPrint(&s); 27. 28. //头删一个元素 29. SeqListPopFront(&s); 30. SeqListPrint(&s); 31. 32. //尾删一个元素 33. SeqListPopBack(&s); 34. SeqListPrint(&s); 35. 36. //指定位置插入一个元素 37. SeqListInsert(&s,2,6); 38. SeqListPrint(&s); 39. 40. //指定位置删除一个元素 41. SeqListErase(&s, 2); 42. SeqListPrint(&s); 43. 44. //修改指定位置元素 45. SeqListModify(&s, 0, -1); 46. SeqListPrint(&s); 47. 48. //销毁顺序表 49. SeqListDestroy(&s); 50. 51. } 52. 53. int main() 54. { 55. TestSEQList1(); 56. return 0; 57. }
执行结果：
