顺序表



​ Hello,大家好,欢迎来到肖肖的数据结构讲堂,今天我们要来学习的是,线性表中的顺序表。


一、理论知识:

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

三、作者的话

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


Author: XiaoXiao
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source XiaoXiao !
评论
  TOC