1 线性表
线性表是由相同数据类型的n个数据元素a0, a1, ......, an-1 组成的有限序列。一个元素可以由若干个数据项组成。用L命明线性表，则其一般表示如下：
L = （a0, a1, ...... ,an-1）。a0 是表头元素，an-1是表尾元素。
线性表按照存储结构，分为顺序表和链表。
2 顺序表
顺序表是在计算机内存中以数组形式保存的顺序表，是指用一组地址连续的存储单元来存储一维数组数据元素的顺序表。
顺序表主要的特点是可以进行随机访问，通过表头元素的地址和元素的编号（下标），可以在O（1）的时间复杂度内找到指定元素。但是插入和删除需要移动大量的元素，从而保持逻辑上和物理上的连续性。
顺序表的操作分别有构造，插入，扩容，查找，删除，遍历，销毁。
2.1 顺序表的定义和操作
先看一下顺序表的结构体定义
表定义：
1 typedef struct Vector { 2 int size, length; //size表示顺序表的容量，length表示当前顺序表的长度 3 int *data; //data指向顺序表表头地址。 4 } Vector;
定义两个用于当做返回值的宏：
1 #define ERROR 0 2 #define OK 1
2.1.1 顺序表的构造操作：
1 Vector *init(int n) { 2 Vector *v = (Vec *)malloc(sizeof(Vector)); 3 v->data = (int *)malloc(sizeof(int) * n); 4 v->length = 0; 5 v->size = n; 6 return v; 7 }
构造一个顺序表的操作很简单，需要注意的是length和size的初始化，以及用malloc申请一块连续的存储空间来表示顺序表。
2.2.2 顺序表的销毁操作：
1 /* 2 参数： 3 vector -- 表头地址。 4 描述： 5 销毁顺序表和顺序表结构体。 6 返回值： 7 无 8 */ 9 void clear(Vector *vector) { 10 free(vector->data); 11 free(vector); 12 }
销毁一个顺序表的操作也比较简单，只需要释放表头地址所指向的堆内存和顺序表结构体指针所指向的堆内存就可以了。
2.2.3 顺序表的插入操作
1 /* 2 参数： 3 vector -- 顺序表结构体地址； 4 loc -- 要插入顺序表的元素的下标； 5 val -- 要插入顺序表的元素的值。 6 描述： 7 将一个值为val的元素插入到顺序表的第loc个位置上（注意：在这里我们约定顺序表的表头元素下标为0）。 8 返回值： 9 成功返回OK， 否则返回ERROR。 10 */ 11 int insert(Vector *v, int val, int index) { 12 if (v == NULL) return 0; 13 if (index < 0 || index > v->length) return 0; 14 if (v->length == v->size) { 15 if (!expand(v)) { 16 return 0; 17 } 18 printf("Expand vec successful, the size of vec is: %d ", v->size); 19 } 20 for (int i = v->length; i > index; i--) { 21 v->data[i] = v->data[i - 1]; 22 } 23 v->data[index] = val; 24 v->length += 1; 25 return 1; 26 }
插入操作比较难，首先我们得对位置参数loc进行合理性判断，插入位置很好理解，首先我们可以插在第0个元素前面，所以最小的插入下标为0，然后插入位置可以逐渐递增下标，知道最后一个表尾元素的后面，表位元素的下标为length-1，所以最大的插入下标为length，大家可以画一下逻辑图再观察看看，很容易得到上述结论。在上述插入代码的第12和第13行就是loc参数合理性判断的操作。
另外，我们还要注意容量是否能够支持插入元素，如果不够的话，需要对顺序表进行容量扩容，代码14~19行，其中扩容函数expand（）我们这里先不用理它，后面会补充。
接下来就是插入操作的开始了，首先我们必须把插入位置loc的元素以及loc之后的所有元素往后移动一个位置，再插入以val为值的元素，特别注意的是，我们必须是从表尾元素开始往后移动。代码20~23行就是在执行该工作。
最后，我们只需把length参数的值+1就可以了。
对于时间复杂度分析，我们假设顺序表有n个元素，所以我们可以得到能插入的位置有n+1个，故插入某个位置的概率为1/n+1，然后如果我们要插入表头位置，则需要移动n个元素，如果我们要插入的位置是表尾位置，则不需要移动任意元素，所以可得到时间复杂度为1/(n+1)*（0+1+2+...+n）≈n/2，故时间复杂度为O（n）。
2.2.4 顺序表扩容操作
1 /* 2 参数： 3 vector -- 顺序表结构体地址； 4 描述： 5 把顺序表的容量大小扩容为原来的2倍。 6 返回值： 7 无 8 */ 9 int expand(Vector *v) { 10 int extra_size = v->size; 11 int *p; 12 while (extra_size) { 13 p = (int *)realloc(v->data, sizeof(int) * (extra_size + v->size)); 14 if (p) break; 15 extra_size >>= 1; 16 } 17 if (extra_size == 0) return 0; 18 v->data = p; 19 v->size += extra_size; 20 return 1; 21 }
扩容操作很简单，就只是默认把顺序表的容量扩容为原来的2倍。
2.2.5 顺序表的删除
1 /* 2 参数： 3 vector -- 顺序表的结构体地址 4 index -- 要参数的元素下标 5 描述： 6 将下标为index的元素删除。 7 返回值： 8 成功返回OK，失败返回ERROR 9 */ 10 int erase(Vector *v, int index) { 11 if (v == NULL) return 0; 12 if (index < 0 || index >= v->length) return 0; 13 for (int i = index + 1; i < v->length; i++) { 14 v->data[i - 1] = v->data[i]; 15 } 16 v->length -= 1; 17 return 1; 18 }
删除操作同样需要对参数index进行合理性判断，行号11、12就做该工作。对于删除操作，我们只需要从下标index后面的元素逐个往前移就可以了，需要注意的是我们必须从index+1到表尾元素的方向递增下标前移一位。当然，插入完毕记得length减一。
对于时间复杂度分析，我们假设元素总数为n，则可以得知如果删除的是表头元素，那么我们需要把n-1个元素往前移动一个单位， 如果删除的是表尾元素，则不需要移动，删除某个下标的元素的概率为1/n，则移动的次数为1/n * (0+1+...n-1) ≈n/2，则时间复杂度为O（n）。
2.2.6 遍历顺序表
1 /* 2 参数： 3 vector -- 顺序表的结构体地址 4 val -- 要查找的元素值 5 描述： 6 在顺序表中查找值为val的元素的位置。 7 返回值： 8 成功返回该元素下标，失败返回ERROR 9 */ 10 void output(Vector *v) { 11 if (v == NULL) return ; 12 printf("["); 13 for (int i = 0; i < v->length; i++) { 14 i && printf(", "); 15 printf("%d", v->data[i]); 16 } 17 printf("] "); 18 }
遍历顺序表的代码非常简单，时间复杂度也很容易算得为O（n）。
3.测试代码
1 /************************************************************************* 2 > File Name: vector.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Wed 11 Nov 2020 10:19:19 AM CST 6 ************************************************************************/ 7 #include <stdio.h> 8 #include <stdlib.h> 9 #include <time.h> 10 typedef struct Vector { 11 int size, length; 12 int *data; 13 } Vector; 14 15 Vector *init(int n) { 16 Vector *v = (Vector *)malloc(sizeof(Vector)); 17 v->data = (int *)malloc(sizeof(int) * n); 18 v->length = 0; 19 v->size = n; 20 return v; 21 } 22 23 void clear(Vector *v) { 24 free(v->data); 25 free(v); 26 } 27 28 int expand(Vector *v) { 29 int extra_size = v->size; 30 int *p; 31 while (extra_size) { 32 p = (int *)realloc(v->data, sizeof(int) * (extra_size + v->size)); 33 if (p) break; 34 extra_size >>= 1; 35 } 36 if (extra_size == 0) return 0; 37 v->data = p; 38 v->size += extra_size; 39 return 1; 40 } 41 42 int insert(Vector *v, int val, int index) { 43 if (v == NULL) return 0; 44 if (index < 0 || index > v->length) return 0; 45 if (v->length == v->size) { 46 if (!expand(v)) { 47 return 0; 48 } 49 printf("Expand vec successful, the size of vec is: %d ", v->size); 50 } 51 for (int i = v->length; i > index; i--) { 52 v->data[i] = v->data[i - 1]; 53 } 54 v->data[index] = val; 55 v->length += 1; 56 return 1; 57 } 58 59 int erase(Vector *v, int index) { 60 if (v == NULL) return 0; 61 if (index < 0 || index >= v->length) return 0; 62 for (int i = index + 1; i < v->length; i++) { 63 v->data[i - 1] = v->data[i]; 64 } 65 v->length -= 1; 66 return 1; 67 } 68 69 void output(Vector *v) { 70 if (v == NULL) return ; 71 printf("["); 72 for (int i = 0; i < v->length; i++) { 73 i && printf(", "); 74 printf("%d", v->data[i]); 75 } 76 printf("] "); 77 } 78 79 int main(void) { 80 Vector *v = init(8); 81 srand(time(0)); 82 #define max_op 40 83 for (int i = 0; i < max_op; i++) { 84 int index = rand() % (v->length + 2) - 1; 85 int op = rand() % 4; 86 switch (op) { 87 case 2: 88 case 1: 89 case 0: { 90 int val = rand() % 100; 91 printf("insert a item %d at index: %d to Vector %s ", val, index, insert(v, val, index) ? "successful" : "failed"); 92 } break; 93 94 case 3: { 95 printf("delete a item at index: %d from Vector %s ", index, erase(v, index) ? "successful" : "failed"); 96 } break; 97 } 98 output(v); 99 } 100 #undef max_op 101 clear(v); 102 return 0; 103 }
编译并运行测试
ydqun@VM-0-9-ubuntu vector % gcc vector.c [127] ydqun@VM-0-9-ubuntu vector % ./a.out [0] insert a item 93 at index: 0 to Vector successful [93] insert a item 68 at index: -1 to Vector failed [93] insert a item 78 at index: 1 to Vector successful [93, 78] insert a item 49 at index: 1 to Vector successful [93, 49, 78] insert a item 46 at index: -1 to Vector failed [93, 49, 78] insert a item 66 at index: 3 to Vector successful [93, 49, 78, 66] insert a item 63 at index: 4 to Vector successful [93, 49, 78, 66, 63] Expand vec successful, the size of vec is: 10 insert a item 21 at index: 1 to Vector successful [93, 21, 49, 78, 66, 63] insert a item 24 at index: 0 to Vector successful [24, 93, 21, 49, 78, 66, 63] delete a item at index: 0 from Vector successful [93, 21, 49, 78, 66, 63] insert a item 3 at index: 6 to Vector successful [93, 21, 49, 78, 66, 63, 3] delete a item at index: 2 from Vector successful [93, 21, 78, 66, 63, 3] delete a item at index: 4 from Vector successful [93, 21, 78, 66, 3] insert a item 11 at index: 1 to Vector successful [93, 11, 21, 78, 66, 3] insert a item 91 at index: 0 to Vector successful [91, 93, 11, 21, 78, 66, 3] insert a item 59 at index: -1 to Vector failed [91, 93, 11, 21, 78, 66, 3] delete a item at index: 3 from Vector successful [91, 93, 11, 78, 66, 3] insert a item 47 at index: 1 to Vector successful [91, 47, 93, 11, 78, 66, 3] insert a item 34 at index: 0 to Vector successful [34, 91, 47, 93, 11, 78, 66, 3] delete a item at index: 6 from Vector successful
4.总结
线性表的操作和复杂度分析都比较简单,上述都分析过了，其中插入，删除，遍历和值查找都是O（n），但是如果以下标去查找元素，则只需要O（1）的时间复杂度。