线性表(顺序表)

发表于 分类于 阅读次数： 本文字数： 7.9k

线性表

1
所谓数组，是有序的元素序列。数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按无序的形式组织起来的一种形式。但是我们还希望能够将这些数据按顺序存放，支持在某个位置插入一条数据、删除一条数据、修改一条数据等，这时候，数组就显得有些乏力了。

数组无法做到这么高级的功能，那么我们就需要定义一种更加高级的数据结构来做到，我们可以使用线性表（Linear List）

1
线性表是由同一类型的数据元素构成的有序序列的线性结构。线性表中元素的个数就是线性表的长度，表的起始位置称为表头，表的结束位置称为表尾，当一个线性表中没有元素时，称为空表。

线性表一般需要包含以下功能：

初始化线性表:将一个线性表进行初始化，得到一个全新的线性表。
获取指定位置上的元素：直接获取线性表指定位置i上的元素。
获取元素的位置：获取某个元素在线性表上的位置i。
插入元素：在指定位置i上插入一个元素。
删除元素：删除指定位置i上的一个元素。
获取长度：返回线性表的长度。

也就是说，现在我们需要设计的是一种功能完善的表结构，它不像是数组那么低级，而是真正意义上的表：

image

简单来说它就是列表，比如我们的菜单，我们在点菜时就需要往菜单列表中添加菜品或是删除菜品，这时列表就很有用了，因为数组长度固定、操作简单，而我们添加菜品、删除菜品这些操作又要求长度动态变化、操作多样。

那么，如此高级的数据结构，我们该如何去实现呢？实现线性表的结构一般有两种，一种是顺序存储实现，还有一种是链式存储实现，我们先来看第一种，也是最简单的的一种。

顺序表

前面我们说到，既然数组无法实现这样的高级表结构，那么我就基于数组，对其进行强化，也就是说，我们存放数据还是使用数组，但是我们可以为其编写一些额外的操作来强化为线性表，像这样底层依然采用顺序存储实现的线性表，我们称为顺序表。

image

这里我们可以先定义一个新的结构体类型，将一些需要用到的数据保存在一起，这里我们以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("顺序表初始化失败，无法启动程序！");
    }
}

接着我们来编写一下插入和删除操作，对新手来说也是比较难以理解的操作：

image

我们先设计好对应的函数：

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("顺序表初始化失败，无法启动程序！");
    }
}

运行结果如下：

image

虽然这样看起来没什么问题了，但是如果我们在非法的位置插入元素会出现问题：

1
2
insertList(&list, 666, -1);   //第一个位置就是0，怎么可能插入到-1这个位置呢，这样肯定是不正确的，所以我们需要进行判断
printList(&list);

我们需要检查一下插入的位置是否合法：

image

转换成位序，也就是[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("插入失败！");
}

image

不过我们还是没有考虑到一个情况，那么就是如果我们的表已经装满了，也就是说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("顺序表初始化失败，无法启动程序！");
    }
}

成功得到结果：
image
这样，我们就完成了顺序表的插入操作，接着我们来编写一下删除操作，其实删除操作也比较类似，也需要对元素进行批量移动，但是我们不需要考虑扩容问题，我们先设计好函数：

1
2
3
void deleteList(ArrayList list, int index){
    	//list就是待操作的表，index是要删除的元素位序
}

按照我们上面插入的思路，我们反过来想一想然后实现删除呢？首先是删除的范围：
image
换算成位序就是[1, size]这个闭区间内容，所以我们先来限定一下合法范围：

1
2
3
4
5
_Bool deleteList(ArrayList list, int index){
    if(index < 1 || index > list->size) return 0;

    return 1;  //正常情况返回1
}

接着就是删除元素之后，我们还需要做什么呢？我们应该将删除的这个元素后面的全部元素前移一位：
image
我们按照这个思路，来编写一下删除操作：

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);

成功得到结果：
image
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站大佬 青空の霞光