线性表 1 所谓数组,是有序的元素序列。数组是在程序设计中,为了处理方便,把具有相同类型的若干元素按无序的形式组织起来的一种形式。但是我们还希望能够将这些数据按顺序存放,支持在某个位置插入一条数据、删除一条数据、修改一条数据等,这时候,数组就显得有些乏力了。
数组无法做到这么高级的功能,那么我们就需要定义一种更加高级的数据结构来做到,我们可以使用线性表(Linear List)
1 线性表是由同一类型的数据元素构成的有序序列的线性结构。线性表中元素的个数就是线性表的长度,表的起始位置称为表头,表的结束位置称为表尾,当一个线性表中没有元素时,称为空表。
线性表一般需要包含以下功能:
初始化线性表 :将一个线性表进行初始化,得到一个全新的线性表。获取指定位置上的元素 :直接获取线性表指定位置i上的元素。获取元素的位置 :获取某个元素在线性表上的位置i。插入元素 :在指定位置i上插入一个元素。删除元素 :删除指定位置i上的一个元素。获取长度 :返回线性表的长度。
也就是说,现在我们需要设计的是一种功能完善的表结构,它不像是数组那么低级,而是真正意义上的表:
简单来说它就是列表,比如我们的菜单,我们在点菜时就需要往菜单列表中添加菜品或是删除菜品,这时列表就很有用了,因为数组长度固定、操作简单,而我们添加菜品、删除菜品这些操作又要求长度动态变化、操作多样。
那么,如此高级的数据结构,我们该如何去实现呢?实现线性表的结构一般有两种,一种是顺序存储实现,还有一种是链式存储实现,我们先来看第一种,也是最简单的的一种。
顺序表 前面我们说到,既然数组无法实现这样的高级表结构,那么我就基于数组,对其进行强化,也就是说,我们存放数据还是使用数组,但是我们可以为其编写一些额外的操作来强化为线性表,像这样底层依然采用顺序存储实现的线性表,我们称为顺序表。
这里我们可以先定义一个新的结构体类型,将一些需要用到的数据保存在一起,这里我们以int类型的线性表为例:
1 2 3 4 5 6 typedef int E; //这里我们的元素类型就用int为例吧,先起个别名 struct List { E array[10]; //实现顺序表的底层数组 int capacity; //表示底层数组的容量 };
为了一会使用方便,我们可以给其起一个别名:
1 typedef struct List * ArrayList; //因为是数组实现,所以就叫ArrayList,这里直接将List的指针起别名
然后我们就可以开始编写第一个初始化操作了:
1 2 3 void initList(ArrayList list){ list->capacity = 10; //直接将数组的容量设定为10即可 }
但是我们发现一个问题,这样的话我们的顺序表长度不就是固定为10的了吗?而前面我们线性表要求的是长度是动态增长的,那么这个时候怎么办呢?我们可以直接使用一个指针来指向底层数组的内存区域,当装不下的时候,我们可以创建一个新的更大的内存空间来存放数据,这样就可以实现扩容了,所以我们来修改一下:
1 2 3 4 struct List { E * array; //指向顺序表的底层数组 int capacity; //数组的容量 };
接着我们修改一下初始化函数:
1 2 3 4 void initList(ArrayList list){ //这里就默认所有的顺序表初始大小都为10吧,随意 list->array = malloc(sizeof(E) * 10); //使用malloc函数申请10个int大小的内存空间,作为底层数组使用 list->capacity = 10; //容量同样设定为10 }
但是还没完,因为我们的表里面,默认情况下是没有任何元素的,我们还需要一个变量来表示当前表中的元素数量:
1 2 3 4 5 6 7 8 9 10 11 12 13 struct List { E * array; //指向顺序表的底层数组 int capacity; //数组的容量 int size; //表中的元素数量 }; typedef struct List * ArrayList; void initList(ArrayList list){ //这里就默认所有的顺序表初始大小都为10吧,随意 list->array = malloc(sizeof(int) * 10); //使用malloc函数申请10个int大小的内存空间,作为底层数组使用 list->capacity = 10; //容量同样设定为10 list->size = 0; //元素数量默认为0 }
还有一种情况我们需要考虑,也就是说如果申请内存空间失败,那么需要返回一个结果告诉调用者:
1 2 3 4 5 6 7 _Bool initList(ArrayList list){ list->array = malloc(sizeof(int) * 10); if(list->array == NULL) return 0; //需要判断如果申请的结果为NULL的话表示内存空间申请失败 list->capacity = 10; list->size = 0; return 1; //正常情况下返回true也就是1 }
这样,一个比较简单的顺序表就定义好,我们可以通过initList函数对其进行初始化:
1 2 3 4 5 6 7 8 int main() { struct List list; //创建新的结构体变量 if(initList(&list)){ //对其进行初始化,如果失败就直接结束 ... } else{ printf("顺序表初始化失败,无法启动程序!"); } }
接着我们来编写一下插入和删除操作,对新手来说也是比较难以理解的操作:
我们先设计好对应的函数:
1 2 3 void insertList(ArrayList list, E element, int index){ //list就是待操作的表,element就是需要插入的元素,index就是插入的位置(注意顺序表的index是按位序计算的,从1开始,一般都是第index个元素) }
我们按照上面的思路来编写一下代码:
1 2 3 4 5 6 void insertList(ArrayList list, E element, int index){ for (int i = list->size; i > index - 1; i--) //先使用for循环将待插入位置后续的元素全部丢到后一位 list->array[i] = list->array[i - 1]; list->array[index - 1] = element; //挪完之后,位置就腾出来了,直接设定即可 list->size++; //别忘了插入之后相当于多了一个元素,记得size + 1 }
现在我们可以来测试一下了:
1 2 3 4 5 void printList(ArrayList list){ //编写一个函数用于打印表当前的数据 for (int i = 0; i < list->size; ++i) //表里面每个元素都拿出来打印一次 printf("%d ", list->array[i]); printf("\n"); }
1 2 3 4 5 6 7 8 9 10 11 12 13 int main() { struct List list; if(initList(&list)){ insertList(&list, 666, 1); //每次插入操作后都打印一下表,看看当前的情况 printList(&list); insertList(&list, 777, 1); printList(&list); insertList(&list, 888, 2); printList(&list); } else{ printf("顺序表初始化失败,无法启动程序!"); } }
运行结果如下:
虽然这样看起来没什么问题了,但是如果我们在非法的位置插入元素会出现问题:
1 2 insertList(&list, 666, -1); //第一个位置就是0,怎么可能插入到-1这个位置呢,这样肯定是不正确的,所以我们需要进行判断 printList(&list);
我们需要检查一下插入的位置是否合法:
转换成位序,也就是[1, size + 1]这个闭区间,所以我们在一开始的时候进行判断:
1 2 3 4 5 6 7 8 _Bool insertList(ArrayList list, E element, int index){ if(index < 1 || index > list->size + 1) return 0; //如果在非法位置插入,返回0表示插入操作执行失败 for (int i = list->size; i > index - 1; i--) list->array[i] = list->array[i - 1]; list->array[index - 1] = element; list->size++; return 1; //正常情况返回1 }
我们可以再来测试一下:
1 2 3 4 5 if(insertList(&list, 666, -1)){ printList(&list); } else{ printf("插入失败!"); }
不过我们还是没有考虑到一个情况,那么就是如果我们的表已经装满了,也就是说size已经达到申请的内存空间最大的大小了,那么此时我们就需要考虑进行扩容了,否则就没办法插入新的元素了:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _Bool insertList(ArrayList list, E element, int index){ if(index < 1 || index > list->size + 1) return 0; if(list->size == list->capacity) { //如果size已经到达最大的容量了,肯定是插不进了,那么此时就需要扩容了 int newCapacity = list->capacity + (list->capacity >> 1); //我们先计算一下新的容量大小,这里我取1.5倍原长度,当然你们也可以想扩多少扩多少 E * newArray = realloc(list->array, sizeof(E) * newCapacity); //这里我们使用新的函数realloc重新申请更大的内存空间 if(newArray == NULL) return 0; //如果申请失败,那么就确实没办法插入了,只能返回0表示插入失败了 list->array = newArray; list->capacity = newCapacity; } for (int i = list->size; i > index - 1; i--) list->array[i] = list->array[i - 1]; list->array[index - 1] = element; list->size++; return 1; }
1 realloc函数可以做到控制动态内存开辟的大小,重新申请的内存空间大小就是我们指定的新的大小,并且原有的数据也会放到新申请的空间中,所以非常方便。当然如果因为内存不足之类的原因导致内存空间申请失败,那么会返回NULL,所以别忘了进行判断。
这样,我们的插入操作就编写完善了,我们可以来测试一下:
1 2 3 4 5 6 7 8 9 10 int main() { struct List list; if(initList(&list)){ for (int i = 0; i < 30; ++i) insertList(&list, i, i); printList(&list); } else{ printf("顺序表初始化失败,无法启动程序!"); } }
成功得到结果: 这样,我们就完成了顺序表的插入操作,接着我们来编写一下删除操作,其实删除操作也比较类似,也需要对元素进行批量移动,但是我们不需要考虑扩容问题,我们先设计好函数:
1 2 3 void deleteList(ArrayList list, int index){ //list就是待操作的表,index是要删除的元素位序 }
按照我们上面插入的思路,我们反过来想一想然后实现删除呢?首先是删除的范围: 换算成位序就是[1, size]这个闭区间内容,所以我们先来限定一下合法范围:
1 2 3 4 5 _Bool deleteList(ArrayList list, int index){ if(index < 1 || index > list->size) return 0; return 1; //正常情况返回1 }
接着就是删除元素之后,我们还需要做什么呢?我们应该将删除的这个元素后面的全部元素前移一位: 我们按照这个思路,来编写一下删除操作:
1 2 3 4 5 6 7 _Bool deleteList(ArrayList list, int index){ if(index < 1 || index > list->size) return 0; for (int i = index - 1; i < list->size - 1; ++i) list->array[i] = list->array[i + 1]; //实际上只需要依次把后面的元素覆盖到前一个即可 list->size--; //最后别忘了size - 1 return 1; }
删除相比插入要简单一些,我们来测试一下吧:
1 2 3 4 for (int i = 0; i < 10; ++i) //先插10个 insertList(&list, i, i); deleteList(&list, 5); //这里删除5号元素 printList(&list);
成功得到结果: OK,那么插入和删除操作我们就成功完成了,还有一些比较简单的功能,我们这里也来依次实现一下,首先是获取长度:
1 2 3 int sizeList(ArrayList list){ return list->size; //直接返回size就完事 }
接着是按位置获取元素和查找指定元素的位置:
1 2 3 4 E * getList(ArrayList list, int index){ if(index < 1 || index > list->size) return NULL; //如果超出范围就返回NULL return &list->array[index - 1]; }
1 2 3 4 5 6 int findList(ArrayList list, E element){ for (int i = 0; i < list->size; ++i) { //一直遍历,如果找到那就返回位序 if(list->array[i] == element) return i + 1; } return -1; //如果遍历完了都没找到,那么就返回-1 }
这样,我们的线性表就实现完成了,完整代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include <stdio.h> #include <stdlib.h> typedef int E; struct List { E * array; int capacity; int size; }; typedef struct List * ArrayList; _Bool initList(ArrayList list){ list->array = malloc(sizeof(E) * 10); if(list->array == NULL) return 0; list->capacity = 10; list->size = 0; return 1; } _Bool insertList(ArrayList list, E element, int index){ if(index < 1 || index > list->size + 1) return 0; if(list->size == list->capacity) { int newCapacity = list->capacity + (list->capacity >> 1); E * newArray = realloc(list->array, newCapacity * sizeof(E)); if(newArray == NULL) return 0; list->array = newArray; list->capacity = newCapacity; } for (int i = list->size; i > index - 1; --i) list->array[i] = list->array[i - 1]; list->array[index - 1] = element; list->size++; return 1; } _Bool deleteList(ArrayList list, int index){ if(index < 1 || index > list->size) return 0; for (int i = index - 1; i < list->size - 1; ++i) list->array[i] = list->array[i + 1]; list->size--; return 1; } int sizeList(ArrayList list){ return list->size; } E * getList(ArrayList list, int index){ if(index < 1 || index > list->size) return NULL; return &list->array[index - 1]; } int findList(ArrayList list, E element){ for (int i = 0; i < list->size; ++i) { if(list->array[i] == element) return i + 1; } return -1; }
顺序实现的线性表,插入、删除、获取元素操作的时间复杂度
插入 :因为要将后续所有元素都向后移动,所以平均时间复杂度为O ( n ) O(n)O(n)
删除 :同上,因为要将所有元素向前移动,所以平均时间复杂度为O ( n ) O(n)O(n)
获取元素 :因为可以利用数组特性直接通过
参考b站大佬 青空の霞光