【数据结构】使用C语言 从零编写一个顺序表_写一个表的结构体代码c语言

前言

在学习完C语言的所有语法之后，会发现C语言的数组的功能其实没有那么强大，它仅仅能够存储特定类型、特定数量的元素，不能够扩容，也不能够插入或者删除某一个元素，所以这样的数据结构其实并不够强大，如果能够实现一个能够完成这几个操作的数据结构就好了。本篇博客将会把数组衍生，使用结构体、指针等知识，构建一个顺序表。

顺序表的定义

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

线性表一般具有的功能

• 初始化： 我们可以初始化从而得到一个线性表。
• 获取指定位置上的元素： 直接获取线性表指定位置上的元素。
• 获取元素的位置： 获取某个元素在线性表上的位置。
• 插入元素： 在指定位置上插入一个元素。
• 删除元素： 删除指定位置上的一个元素。
• 获取长度： 返回线性表的长度。

定义一个新的数据结构体

由于我们需要设计一个新的数据结构，所以我们提前定义一个该数据结构的结构体。假设该结构体存储的类型是int，把int型起个别名E，如果以后需要存别的类型，就把这个E修改就可以了。

typedef int E;

struct List
{
    E array[10];
    int capacity;
};
1
2
3
4
5
6
7

这里通过struct声明了一个结构体，其中包括一个E类型的数组，capacity表示该数组的容量。

通过该结构体，我们可以编写一个函数用于初始化数组，当我们声明一个List类型的变量的时候，把变量本身作为参数传入初始化函数就能够对其初始化：

void initList(struct List list)
{
    list.capacity = 10;
}
1
2
3
4

但是我们会发现，这样的函数传进来的变量只是一个局部变量，当函数结束之后内存就会被销毁，所以这样子的初始化函数是有问题的。

最好的方法应该是传入一个List类型变量的指针，然后通过指针初始化变量的值，我们可以把List类型变量的指针改个名：

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->capacity = 10;
}
1
2
3
4
5
6

然后通过指针传参，这样就能成功初始化了。

#include <stdio.h>


typedef int E;

struct List
{
    E array[10];
    int capacity;
};

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->capacity = 10;
}

int main()
{
    struct List list;

    printf("初始化前：%d\n",list.capacity);//初始化前：0

    initList(&list);

    printf("初始化后：%d\n",list.capacity);//初始化后：10

    return 0;
}

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

代码到此，我们定义了一个线性表类型，并让该类型默认拥有10个长度的数组和一个capacity属性，并且编写了一个初始化函数用于初始化该类型中的数据。（好想说属性，学面向对象学的…）

现在想想，把里面数组的长度写死为10不太好，不够自由，我们可以使用malloc函数指定该数组使用多少内存空间，如果要这样写的话，List结构体中就不能直接声明数组了，而是声明一个指向数组的指针。

#include <stdio.h>
#include <stdlib.h>

typedef int E;

struct List
{
    E * array;
    int capacity;
};

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    list->capacity = 10;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

储存线性表的元素个数

我们一般在结构体中定义一个size来储存元素个数，默认初始化为0,同时我们再完善一下初始化函数，如果申请内存空间失败，则返回0（false）。

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;
    
    list->capacity = 10;
    list->size = 0;
    
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

当我们执行初始化操作的时候，可以用if判断是否初始化成功：

	struct List list;
    if (initList(&list)){
        ...
    } else
    {
        printf("初始化线性表失败！");
    }
1
2
3
4
5
6
7

实现插入元素的操作

首先定义一个函数，用于实现对线性表的插入操作。

该函数需要传入表的地址，需要插入的元素，还有插入的位置。

void insertList(ArrayList list,E element,int index)
1

注意：index和索引不一样，index没有0，从1开始

插入操作大概可以分为三部分

• 找到需要插入的位置，从该位置开始，将之后的元素全部往后移动一个单位
• 在需要插入的位置，修改为指定的元素
• 插入完毕后，增加size的值

void insertList(ArrayList list,E element,int index)
{
    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;
}

1
2
3
4
5
6
7
8
9
10
11

可以写一个打印表的函数来测试一下效果：

#include <stdio.h>
#include <stdlib.h>

typedef int E;

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;

    list->capacity = 10;
    list->size = 0;

    return 1;
}

void insertList(ArrayList list,E element,int index)
{
    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int main()
{
    struct List list;

    if (initList(&list)){
        insertList(&list, 111, 1);
        printList(&list);
        insertList(&list, 222, 1);
        printList(&list);
        insertList(&list, 333, 2);
        printList(&list);
    } else
    {
        printf("初始化线性表失败！");
    }
    
    return 0;
}
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

输出结果为：

111
222 111
222 333 111
1
2
3

说明，表的插入操作成功。

但在上述代码中，没有考虑到别的情况，比如说如果插入一个非法的位置 如-1，表中没有这个位置便会插入失败；比如，如果插入的元素过多，多到了超过了先前定义的40个字节的内存大小，程序的内存就会不安全，所以做扩容的操作也是有必要的。

解决插入到非法位置的问题

解决这个问题可以通过size属性判断，如果要插入的位置在[0,size+1]的区间内，就可以插入，如果不在则不能返回，在函数中便返回0；只需要在循环之前加一个判断。

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 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
2
3
4
5
6
7
8
9
10
11
12
13

解决内存扩容的问题

如果要解决这个问题，需要在插入数组之前进行一次判断，如果表中的元素个数等于表的容量，则把该表之前申请的内存空间大小进行增加，生成新的内存，生成新内存之后，还要把历史元素重新添加进新申请的内存中。

在C语言中，可以不用这么麻烦，我们可以使用realloc函数轻松完成这个任务。

realloc函数可以做到控制动态内存开辟的大小，重新申请的内存空间大小就是我们指定的新的大小，并且原有的数据也会放到新申请的空间中，所以非常方便。当然如果因为内存不足之类的原因导致内存空间申请失败，那么会返回NULL，所以别忘了进行判断。

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 0;

    if (list->size == list->capacity)
    {
        int newCapacity = list->capacity *= 2;// 更新新的容量
        E * newArray = realloc(list->array,sizeof (E) * newCapacity);// 内存扩容
        if (newCapacity == 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这样就完善了表的插入操作，我们可以测试一下：

int main()
{
    struct List list;
    if(initList(&list)){
        for (int i = 0; i < 30; ++i)
            insertList(&list, i, i+1);
        printList(&list);
    } else{
        printf("顺序表初始化失败，无法启动程序！");
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果：

0 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

1
2

实现删除元素的操作

实现这个过程，思路和插入差不多，只不过需要删除的位置的区间在[1,size]内。

int deleteList(ArrayList list, int index)
1

删除元素分为两步：

• 找到需要删除元素的位置将该位置往后的所有元素往前移
• 将表的size减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]);
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

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

实现完成

代码写到此，以数组为基底，构建一个线性表就结束了，一下是全部代码：

#include <stdio.h>
#include <stdlib.h>

/*
* 初始化： 我们可以初始化从而得到一个全新的线性表。
* 获取指定位置上的元素： 直接获取线性表指定位置上的元素。
* 获取元素的位置： 获取某个元素在线性表上的位置。
* 插入元素： 在指定位置上插入一个元素。
* 删除元素： 删除指定位置上的一个元素。
* 获取长度： 返回线性表的长度。
 */
typedef int E;

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;

    list->capacity = 10;
    list->size = 0;

    return 1;
}

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 0;

    if (list->size == list->capacity)
    {
        int newCapacity = list->capacity *= 2;// 更新新的容量
        E * newArray = realloc(list->array,sizeof (E) * newCapacity);// 内存扩容
        if (newCapacity == 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;
}

int 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]);
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int findList(ArrayList list,E element) // 查找元素
{
    for (int i = 0;i < list->size;i++)
    {
        if (list->array[i] == element) return i + 1;
    }

    return -1;
}

int main()
{
    struct List list;
    if(initList(&list)){
        for (int i = 0; i < 30; ++i)
            insertList(&list, i, i+1);
        printList(&list);
    } else{
        printf("顺序表初始化失败，无法启动程序！");
    }

    return 0;
}

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110