一、理论知识：

1.你需要知道的知识：

结构体
动态分配内存（malloc）
指针
typedef
宏定义

2.什么是顺序表？

顺序表是线性表的一种，但它里面元素的存储时连续的，也就是说在内存中顺序表中的元素的地址是挨在一起的，这有点类似于一维数组，但是两者是有区别的。在C语言中，数组的大小不能动态改变，而顺序表的大小是可以”改变“的。

顺序表的创建代码如下：

typedef struct {
    ElementType *array; //存放数据元素的数组.
    int length;  //顺序表的实际大小.
    int capacity;  //顺序表的最大容量.
}SeqList;

其中，ElementType是一个新的数据类型，它可以是int,float,char等等，还可以是自定义类型。下面是创建一个自定义类型（结构类型）的实例,为了后续的操作，我这里只在结构体里面只弄了一个整型变量，实际情况可以弄多个，而且还是不同类型的。也可以直接把基本数据类型的名字改成ElementType（typedef int ElementType;)。至于为什么弄成ElementType，这是为了规范，统一，方便交流。

typedef struct {
    int a;
    /*
    ...
    */
}ElementType;

定义好之后，我们就可以使用代码：

SeqList *L;

来定义一个顺序表，因为我们的顺序表是一个SeqList类型的指针，所以我们可以用 -> 来访问顺序表（结构体）中的元素：

L->array[i];
L->length;

我们也可以使用：

SeqList L;

来定义。如果是这样定义的话，就要用 . 运算符来访问顺序表中的数据（元素）。

L.array[i];
L.length;

在这里，还是建议使用第一种方法来定义，因为本文采取的是第一种方式，第二种方式，读者可以阅读本文后自行尝试。

3.顺序表的API设计

工作的时候，做一个项目前，都是先商量定义好API，再进行其它操作的，这里我们定义一些基本的顺序表的操作。

SeqList *cleateList(int capacity): 创建线性表。
    
int get(SeqList *L, int i, ElementType *x): 获取线性表中第i个数据元素的值。
    
int find(SeqList *L, ElementType x): 查找线性表中与给定值 x 相等的数据元素。
    
int insertList(SeqList *L, int i, ElementType x): 在第i个位置插入数据元素x。
    
int addList(SeqList *L, ElementType x): 在顺序表的最后增加一个数据元素。
    
int deleteList(SeqList *L, int i, ElementType x): 删除第i个位置的数据元素，并将它保存在x中。
    
int DestoryList(SeqList *L): 销毁一个线性表。
    
int ClearList(SeqList *L): 清空一个线性表。
    
void mergeList(SeqList *LA, SeqList *LB, SeqList *LC): 合并连个顺序表到第三个顺序表中。
    
void outPutList(SeqList *L): 输出线性表中的内容。

二.顺序表基本操作的实现

1.创建顺序表

顺序表的创建，其实就是创建一个空的顺序表，我们在给顺序表分配内存空间后，需要把length的值置为。声明如下：

SeqList *cleateList(int capacity);

其中，capacity是这个顺序表的最大容量。我们可以使用语句：

SeqList *L = cleateList(5);

来创建一个最大容量为5的顺序表。它的示意图，如图所示：

空的顺序表示意图

完整代码如下：

SeqList *cleateList(int capacity)
{
    SeqList *L;
    L = (SeqList *)malloc(sizeof(SeqList));
    
    L->length = 0;
    L->capacity = capacity;
    L->array = (ElementType *)malloc(capacity * sizeof(ElementType));
    
    return L;
}

这样，我们就可以得到一个空的顺序表了，下面我们来讲如何在这个空的顺序表中增添数据元素。

2.增加（插入）数据元素

我们增加数据元素的方式有两种，一种是直接在当前顺序表的最后增加一个数据元素，另一种则是在指定位置增加数据元素。

对于第一种增加数据元素，我们只需要判断当前的顺序表是否满了就可以了，而另一种还需要找到第i个位置，移动后面的数据元素。具体算法如下：

（1) 判断顺序表的存储空间是否为满，若满，返回0；

（2）判断要增加（插入）的第i个位置是否是合法的（1≤ i ≤ n+1),若不合法，返回0；

（3）因为顺序表内数据元素的存储空间在内存中是挨在一起的，因此要将i以后的元素全部往后移一下，即腾出第i个位置。

（4）将带添加的数据元素x存储到第i个位置中；

（5）修改顺序表中length的值，让其+1。

int insertList(SeqList *L, int i, ElementType x)
{
    int k;
    
    if (L->length == L->capacity) return 0; //判断顺序表是否为满。
    
    if (i < 1 || i > L->length+1) return 0; //判断顺序表带插入的数据元素的位置是否合法。
    
    for (k = L->length-1; k >= i-1; k--) { //将第i个元素以后的所有元素都往后挪一个位置。
        L->array[k+1] = L->array[k];
    }
    L->array[i-1] = x; //注意第i个元素它的下标其实是i-1。
    L->length++; //顺序表的长度增加1。
}

对于直接在顺序表后面增加元素就相对简单了，只要先判断顺序表是否满了，再把这个数据元素加到顺序表的最后，然后length+1即可实现。

int addList(SeqList *L, ElementType x)
{
    if (L->length == L->capacity) return 0; //判断顺序表是否满了。
    
    L->array[L->length] = x; //把这个数据元素添加到顺序表的末尾。
    L->length++; //顺序表长度+1。
    
    return 1;
}

现在，我们学会了如何增加数据元素，那么当我们想输出这些数据元素，要怎么做呢？

3.输出顺序表中的数据元素

具体代码：

void outPutList(SeqList *L)
{
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d\n", L->array[i].a);
    }
}

注意，这里把它当成输出数组元素，我前面定义的结构变量里面是一个整型的a，使用这里我用了 array[i].a 来访问数据元素的内容。

4.测试1！

我们在前面学习了在顺序表中增加数据元素和输出数据元素的函数，但是我们不知道自己写的函数是否是正确的，所以，现在就让肖肖来带着你来测试一把吧！下面是含增加数据元素、输出顺序表内容、主函数的完整程序：

#include <stdio.h>

typedef struct
{
    int a;
}ElementType;

typedef struct
{
    ElementType *array;
    int length;
    int capacity;
}SeqList;

SeqList *cleateList(int capacity);
int addList(SeqList *L, ElementType x);
int insertList(SeqList *L, int i, ElementType x);
void outPutList(SeqList *L);

int main(void)
{
    SeqList *L;
    ElementType x;
    int i;
    
    L = cleateList(5);
    scanf("%d", &x.a);
    insertList(L, 1, x);
    scanf("%d", &x.a);
    addList(L, x);
    outPutList(L);
    
    return 0;
}

SeqList *cleateList(int capacity)
{
    SeqList *L;
    L = (SeqList *)malloc(sizeof(SeqList));
    
    L->length = 0;
    L->capacity = capacity;
    L->array = (ElementType *)malloc(capacity * sizeof(ElementType));
    
    return L;
}

int addList(SeqList *L, ElementType x)
{
    int i;
    if (L->length == L->capacity) return 0;
    
    L->array[L->length] = x;
    L->length++;
    
    return 1;
}

int insertList(SeqList *L, int i, ElementType x)
{
    int k;
    if (L->length == L->capacity) return 0;
    
    if (i < 1 || i > L->length+1) return 0;
    
    for (k = L->length-1; k >= i-1; k--) {
        L->array[k+1] = L->array[k];
    }
    L->array[i-1] = x;
    L->length++;
    
    return 1;
}

void outPutList(SeqList *L)
{
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d\n", L->array[i].a);
    }
}

控制台输入: 1 2

输出： 1 2

由此可见，函数正确！然而，如果我们只是往这个表中添加数据元素，而无法得到里面的数据元素，我们就无法对这个表中数据进行一系列的操作，那么我们该如何得到（查找）顺序表中的数据元素呢？

5.得到、查找数据元素

既然我们学会了如何添加元素到顺序表，我们理所当然的要知道如何得到顺序表中的数据元素。顺序表的查找，获取数据元素其实和简单，基本上与一维数组的类似，获得数据元素的代码如下：

int get(SeqList *L, int i, ElementTypr *x)
{
    if (i < 1 || i > L->length) {
        return 0;
    }
    
    *x = L->array[i-1];
    
    return 1;
}

值得注意的是，顺序表中的第i个元素，它的下标其实是i-1。我们最先判断要取的位置的是否合理，如果是不合理的，我们为什么还要去返回数据呢？查找的操作是查找我们给定的数据是否在顺序表中，然后返回它的位置，如果没有找到，那么返回-1，代码如下：

int find(SeqList *L, ElementType x)
{
    int i = L->length - 1;
    
    while (i >= 0 && L->array[i] != x) {
        i--;
    }
    
    return i;
}

因为顺序表是一个带有数组的结构，如果我们把它当成函数的参数传入会浪费空间，所以我们这里传入的是指向这个顺序表的指针。

若是我不想要一些数据元素要怎么办，或者，我干脆不要这个顺序表了，我们该如何实现呢？别急，带我慢慢述说。

6.删除，清空，销毁！

1> 删除第i个数据元素。

首先要说一下，删除的原理：

（1）判断删除位置i是否合法（1≤ i ≤ n），若不合法，则返回0。

（2）将i-1到n位置的数据元素依次往前移动一位。当 i == n 时，无需移动。

（3）修改length，使得表长减1。

具体代码：

int deleteList(SeqList *L, int i, ElementType x)
{
    int k;
    if (i < 1 || i > L->length) return 0;
    
    *x = L->array[i-1];
    for (k = i; k < L->length; k++) {
        L->array[k-1] = L->array[k];
    }
    L->length--;
    
    return 1;
}

我们怎么操作，是把前面的数据元素被后面的覆盖掉，其实之前的 L->length 位置的那个数据元素还是存在的，我们可能通过找到它的地址，通过它的地址来访问它里面的数据，不过我们的查找，得到数据元素的函数中，有如下判断：

if (i < 1 || i > L->length) return 0;

我们的查找、获取函数都只能去找这个范围内的，其他地方呢，我们是访问不到的，所以可以“认为”那个数据元素不见了。

2> 清空顺序表

我们要理解清空顺序表，我们应该先明白，计算机删除数据的原理，我们想想，当我们创建了一个包含“123”的txt文件，然后右键把它删除后，计算机是如何删除的，是像现实生活中的那样，扔掉？不不不，如果计算机是这样，那么你的硬盘和软盘岂不是要年年更换？计算机删除数据的原理就是把另外一些数据覆盖掉你写的数据上面，或者干脆不是它自己覆盖的，而是做上标记，让你不能读取数据，但是可以修改数据，待你下一次写入数据时，再把原来的数据覆盖掉。~~（非专业解释，想了解清楚，请自行百度）~~

我们的清空顺序表的操作也是如此，只是对访问做出限制，然后等待被新的数据元素覆盖掉。代码实现：

int ClearList(SeqList *L)
{
    if (L->array) {
        L->length = 0;
        
        return 1;
    }
    else {
        return 0;
    }
}

L->array 用来判断顺序表中是否有数据元素，如果没有，我们就没有必要对它进行清空操作了。随后我们只需要把顺序表的实际长度length置为0，就可以认为这个顺序表已经被我们清空了。

3> 销毁顺序表

销毁？清空？听起来相同的两个词汇，其实差距挺大的。销毁顺序表，就是说，我不要这个顺序表了，这个顺序表从内存中消失了，就算通过指针来访问，访问到的也是无意义的数据。而清空顺序表呢？仅仅把顺序表里面的旧数据元素不要了，这个顺序表还是存在的，我们可以对这个顺序表进行增加数据元素的操作。

所以，当我们进行销毁顺序表的操作时，我们要注意释放内存（因为我们之前给顺序表、存放数据元素的数组分配了内存），同时把顺序表的实际大小，最大容量都改为0。具体代码如下：

int DestoryList(SeqList *L)
{
    if (L->array) {
        free(L->array);
        L->length = 0;
        L->capacity = 0;
        
        printf("顺序表销毁成功！\n");
        
        return 1;
    }
    else {
        printf("顺序表销毁失败！\n");
        
        return 0;
    }
}

7.合并顺序表

前面我们把顺序表的基础操作学完了，现在我们来学习一个难一点的，合并两个有序顺序表，要求合并后的顺序表还是有序的。这个还是挺简单的，我们先设置三个指针分别指向每一个顺序表的元素，然后比较需要合并的两个顺序表中指针指向的数据元素的大小，然后把其插入到新表即可，具体算法：

（1）设表LC是一个空表，为使LC也是一个有序的顺序表，设置三个指针i，j，k分别指向三个顺序表中的数据元素。

（2）若LA->array[i] <= LB->array[j]，则将LA->array[i] 插入到表LC中。

（3）重复操作步骤（2），直到一个表被扫描完毕为止。

（4）再将为扫描完的表中的剩余的所有元素放到表LC中。

具体代码：

void mergeList(SeqList *LA, SeqList *LB, SeqList *LC)
{
    int i, j, k;
    i = j = k = 0;
    
    if (LC->capacity < LA->length + LB->length) {
        printf("表LC容量不够！\n");
        
        return;
    }
    
    while (i < LA->length && j < LB->length) {
        if (LA->array[i] <= LB->array[j]) {
            LC->array[k++] = LA->array[i++];
        }
        else {
            LC->array[k++] = LB->array[j++];
        }
    }
    
    while (i < LA->length) {
        LC->array[k++] = LA->array[i++];
    }
    
    while (j < LB->length) {
        LC->array[k++] = LB->array[j++];
    }
    
    LC->length = k;
}

三、作者的话

到这里，我们的顺序表已经学完了。可以看到，顺序表并不是很难，只要原理记清楚，多敲几次就可以记住。下一节的链表，难度大一点，因为指针用得多，容易乱吧！

XiaoXiao

http://cn-xiaoxiao.github.io/2021/01/25/%E9%A1%BA%E5%BA%8F%E8%A1%A8/

All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source XiaoXiao !

C语言

Java常用类之 Object类

2021-02-08 Java学习笔记

Java 常用类

新的一年，新的梦想

2021-01-01 文学

Autobiography

顺序表

一、理论知识：

1.你需要知道的知识：

2.什么是顺序表？

3.顺序表的API设计

二.顺序表基本操作的实现

1.创建顺序表

2.增加（插入）数据元素

3.输出顺序表中的数据元素

4.测试1！

5.得到、查找数据元素

6.删除，清空，销毁！

1> 删除第i个数据元素。

2> 清空顺序表

3> 销毁顺序表

7.合并顺序表

三、作者的话

你的赏识是我前进的动力