【C语言 数据结构】顺序表的使用

本文借鉴点击跳转
上一篇：线性表的简绍

顺序表

什么是顺序表

顺序表又称顺序存储结构，是线性表的一种，专门存储逻辑关系为“一对一”的数据。

顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。

举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下图所示：

---

顺序表的初始化

使用顺序表存储数据，除了存储数据本身的值以外，通常还会记录以下两样数据：

• 顺序表的最大存储容量：顺序表最多可以存储的数据个数；
• 顺序表的长度：当前顺序表中存储的数据个数。

C 语言中，可以定义一个结构体来表示顺序表：

// TODO 定义结构体
typedef struct {
    ElemType *elem;
    int length;
    int listSize;
} SeqList;
1
2
3
4
5
6

尝试建立一个顺序表，例如：

//TODO 构造空的线性表L
void initList(SeqList *L) {
    L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));
    L->length = 0;
    L->listSize = LISTSIZE;
}
1
2
3
4
5
6

如上所示，整个建立顺序表的过程都封装在一个函数中，建好的顺序表可以存储 5 个逻辑关系为“一对一”的整数。

通常情况下，malloc() 函数都可以成功申请内存空间，当申请失败时，示例程序中进行了“输出失败信息和强制程序退出”的操作，您可以根据实际需要修改代码。

---

顺序表插入元素

向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：

• 插入到顺序表的表头；

• 在表的中间位置插入元素；

• 尾随顺序表中已有元素，作为顺序表中的最后一个元素；

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

• 将要插入位置元素以及后续的元素整体向后移动一个位置；
• 将元素放到腾出来的位置上；

例如，在 {1,2,3,4,5} 的第 3 个位置上插入元素 6，实现过程如下：

• 遍历至顺序表存储第 3 个数据元素的位置，如图1 所示：

• 将元素 3、4 和 5 整体向后移动一个位置，如图 2 所示：

• 将新元素 6 放入腾出的位置，如图 3 所示：

---

因此，顺序表插入数据元素的 C 语言实现代码如下：

// TODO 插入
void insertList(SeqList *L, int loc, char c) {
    //存储空间已满
    if (L->length >= L->listSize) {
        L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));
        L->listSize += LISTINCREMENT;
    }
    for (int k = L->length; k > loc; k--) {
        L->elem[k] = L->elem[k - 1];
    }
    L->length++;
    L->elem[loc] = c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

顺序表删除元素

从顺序表中删除指定元素，实现起来非常简单，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。

后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的。

例如，从 {1,2,3,4,5} 中删除元素 3 的过程如图 4 所示：

---

因此，顺序表删除元素的 C 语言实现代码为：

// TODO 删除
void delList(SeqList *L, int loc) {
    for (int j = loc; j < L->length; j++) {
        L->elem[j - 1] = L->elem[j];
    }
    L->length--;
}
1
2
3
4
5
6
7

---

完整的代码如下所示

#include "stdio.h"
#include "windows.h"
#include "stdlib.h"

// TODO 定义常量
#define LISTSIZE 10
#define LISTINCREMENT 2

typedef char ElemType;

// TODO 定义结构体
typedef struct {
    ElemType *elem;
    int length;
    int listSize;
} SeqList;

//TODO 构造空的线性表L
void initList(SeqList *L) {
    L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));
    L->length = 0;
    L->listSize = LISTSIZE;
}

// TODO 增加
void appendList(SeqList *L, char c) {
    L->elem[L->length++] = c;
}

// TODO 插入
void insertList(SeqList *L, int loc, char c) {
    //存储空间已满
    if (L->length >= L->listSize) {
        L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));
        L->listSize += LISTINCREMENT;
    }
    for (int k = L->length; k > loc; k--) {
        L->elem[k] = L->elem[k - 1];
    }
    L->length++;
    L->elem[loc] = c;
}

// TODO 删除
void delList(SeqList *L, int loc) {
    for (int j = loc; j < L->length; j++) {
        L->elem[j - 1] = L->elem[j];
    }
    L->length--;
}
// TODO 打印
void printList(SeqList *L){
    for (int i = 0; i < L->length; ++i) {
        printf("%c",L->elem[i]);
    }
    printf("\n");
}
void combine(SeqList *a, SeqList *b, SeqList *c)
{
    int i=0, j=0, k=0;
    //同时扫描两个表
    while(i<a->length && j<b->length)
    {
        if(a->elem[i]<=b->elem[j])
        {
            c->elem[k] = a->elem[i];
            i++;
            k++;
        }
        else
        {
            c->elem[k] = b->elem[j];
            j++;
            k++;
        }
    }
    //A表扫完，B组未扫完
    if(i==a->length)
    {
        for(; j<b->length; j++)
        {
            c->elem[k] = b->elem[j];
            k++;
        }
    }
    if(j==b->length)
    {
        for(; i<a->length; i++)
        {
            c->elem[k] = a->elem[i];
            k++;
        }
    }
    c->length=k;
}

int main() {
    char a[] = "ajcniydu";
    SeqList list;
    // TODO 初始化顺序表
    initList(&list);
    printf("%d\n", list.length);
    for (int i = 0; i < strlen("ajcniydu"); i++) {
        appendList(&list, a[i]);
    }
    printList(&list);
    printf("%d\n", list.length);
    insertList(&list, 3, 'p');
    printList(&list);
    printf("%d\n", list.length);
    delList(&list, 3);
    printList(&list);
    printf("%d\n", list.length);
    SeqList aList;
    SeqList bList;
    SeqList cList;
    initList(&aList);
    initList(&bList);
    initList(&cList);

    char a1[] = {'1','3','5','7'};
    char a2[] = {'2','4','6'};
    for (int i = 0; i < 4; i++) {
        appendList(&aList, a1[i]);
    }
    for (int i = 0; i < 3; i++) {
        appendList(&bList, a2[i]);
    }
    combine(&aList,&bList,&cList);
    printList(&cList);
    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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

运行结果

0
ajcniydu
8
ajcpniydu
9
ajpniydu
8
1234567