@[toc]

本篇文章将讲解线性表的顺序实现。

线性表的定义

线性表是由n(n >= 0)个数据元素(结点)a₁，a₂，......，a_n组成的有限序列，其中数据元素的个数n定义为表的长度，当n = 0时称为空表。
比如序列{a₁，a₂，......，a_i-1，，a_i，a_i+1，a_n}，其中元素a₁被称为线性起点或起始结点，元素a_n被称为线性终点或终端结点。对于元素a_i，a_i-1被称为a_i的直接前驱，a_i+1被称为a_i的直接后继。
所以，对于同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。
由此，我们得知线性表的以下特征(非空情况下)：

有且仅有一个开始结点，它没有直接前驱，而仅有一个直接后继
有且仅有一个终端结点，它没有直接后继，而仅有一个直接前驱
其余的内部结点都有且仅有一个直接前驱和一个直接后继

线性表的抽象数据类型定义

抽象数据类型在前面的专栏文章中就说到了，这里我就直接写出抽象数据类型线性表的定义：

ADT List{
   
   
    数据对象：D = {
   
   ai|ai属于Elemset,(i = 1,2,...,n,n >= 0)}
    数据关系：R = {
   
   <ai-1,ai>|ai-1,ai属于D,(i = 2,3,...,n)}
    基本操作：
    void InitList(&L);            //初始化线性表
    void DestroyList(&L);        //销毁线性表
    int ListInsert(&L,i,e);        //向线性表插入元素
    int ListDelete(&L,i,&e);    //从线性表删除元素
    void ClearList(&L);            //清空线性表
    int ListEmpty(&L);            //判断线性表是否为空
    int ListLength(&L);            //求线性表的长度
    int GetElem(&L,i,&e);        //找到线性表指定位置的元素值
    int LocateElem(&L,e);        //找到线性表指定元素值的位置
    ...
}ADT List;

线性表的顺序表示和实现

在计算机内，线性表有两种基本的存储结构：

顺序存储结构
链式存储结构

我们先来说一说顺序存储结构。
比如一个线性表：{a₁，a₂，......，a_i，a_i+1，......，a_n}，顺序存储就是将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，使其在存储时的物理位置仍然相邻。
举个例子：线性表(1，2，3，4，5)的顺序存储结构为：
在这里插入图片描述
该存储结构采用依次存储，地址连续，中间没有空出存储单元。
如果地址不连续，即中间存在空的存储单元，如下图：

那么它就不是一个线性表的顺序存储结构。
连续地址的好处就是，通过某个元素就可以计算出线性表中的其它所有元素的存储位置。

元素存储位置的计算

既然说到元素的存储位置，我们就来看看如何该计算元素的存储位置。
在这里插入图片描述
假设有这样一个线性表，而a的存储位置为1000，那么b的位置应为多少呢？
千万不要想当然地以为b的存储位置是1001，b的存储位置应该由线性表元素所占的字节数决定。倘若线性表每个元素占用4个字节，则b的存储位置为1004；倘若每个元素占用8个字节，则b的存储位置为1008。
结论如下：
假设线性表的每个元素需占x个存储单元，则第i + 1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系：

LOC(a_i+1) = LOC(a_i) + x

由此可得知，所有数据元素的存储位置均可由第一个数据元素的存储位置计算得到：

LOC(a_i) = LOC(a₁) + (i - 1)x

顺序表的实现

我们分析一下顺序表的元素特性：

地址连续
依次存放
随机存取
类型相同

我们很容易发现，这不就是数组的特性吗？所以，我们可以通过数组来实现顺序表。
顺序表是有插入和删除操作的，所以顺序表的长度是变化的，而C语言中的数组是定长的，那么该如何用数组实现顺序表呢？
我们可以定义一个变量来表示顺序表的长度，当顺序表长度变化时，只需相应地更改该变量即可，定义如下：

#define MAX_SIZE 10        //线性表初始长度
#define ElemType int
typedef struct{
   
   
    ElemType data[MAX_SIZE];
    int length;        //线性表长度
}SqList;

当然了，我们还可以使用动态分配内存的方式来实现顺序表。

顺序表的初始化

定义出了顺序表之后，我们来看看关于顺序表的一些操作，首先是初始化。

SqList InitList(){
   
   
    //声明顺序表
    SqList l;
    l.length = 0;    //初始长度为0
    return l;
}

当然也可以动态分配数组：

typedef struct{
   
   
    int *data;        //声明动态数组
    int length;        //线性表长度

}SqList;

SqList InitList(){
   
   
    //声明顺序表
    SqList l;
    l.data = (int*) malloc(sizeof(int) * MAX_SIZE);
    if(l.data == NULL){
   
   
        exit(-1);
    }
    l.length = 0;    //初始长度为0
    return l;
}

顺序表的销毁

有初始化操作肯定就会有销毁，销毁无用的资源是一个好习惯。
如果使用静态数组实现的顺序表，我们无需手动释放资源，因为程序结束后系统会自动释放内存；而如果使用动态内存分配实现的顺序表，就需要我们手动释放内存，实现如下：

void DestroyList(SqList l){
   
   
    if(l.data){
   
   
        free(l.data);    //释放动态数组内存
    }
    l.data = NULL;
}

非常简单，没有什么需要说明的地方。

清空顺序表

void ClearList(SqList l){
   
   
    l.length = 0;    //将顺序表的长度置为0
}

要注意，清空顺序表并不是释放顺序表的内存，而是表示清空顺序表中的所有元素，所以只需将顺序表长度赋值为0即可。

求顺序表长度

求长度非常简单，将length返回就可以了：

int GetLength(SqList l){
   
   
    return l.length;
}

判断顺序表是否为空

这个也很简单，如果顺序表长度为0，说明顺序表为空；如果不为0，则说明不为空。

int ListEmpty(SqList l){
   
   
    if(l.length == 0){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

顺序表的插入

前面都是一些比较简单的操作，从这里开始讲解一些顺序表中较为复杂的操作。
比如如下的一个顺序表：
在这里插入图片描述
长度为10的顺序表中存放了5个元素，如何实现往顺序表中插入一个元素呢？分两种情况讨论：

表尾插入
非表尾插入

为什么要有这两种情况呢？
如果插入位置是表尾，那么直接插入即可：
在这里插入图片描述
如果插入位置不为表尾，为了让元素顺利插入，需将插入位置后面的所有元素都往后移动一位，然后插入元素：

当然了，我们还得考虑插入的异常情况：
长度为n的顺序表中，有效元素个数没有满，此时顺序表中还有空余，那么插入位置的有效范围：[1，有效元素个数 + 1]。比如下面的顺序表中，表尾元素5的位置为5，则插入位置最大值为6，因为顺序表中还有空余，所以插入到表尾元素5的后面是没有问题的；插入位置的最小值为1，这个应该很好理解。
在这里插入图片描述
而如果长度为n的顺序表中，有效元素个数已满，即顺序表中没有空余，那么该顺序表就无法插入。

综上所述，顺序表的插入算法思想如下：

判断插入位置pos是否合法
判断顺序表的存储空间是否已满，若已满，返回-1
将pos位置之后的所有元素向后移动一位
将新元素插入到pos位置
顺序表长度length加1，此时插入成功，返回1

分析过后，我们通过代码来实现一下：

int InsertList(SqList *l,int pos,int val){
   
   
    int i;
    //判断插入位置pos是否合法
    if(pos < 1 || pos > l->length + 1){
   
   
        return -1;
    }
    //判断顺序表是否已满
    if(l->length == MAX_SIZE){
   
   
        return -1;
    }
    //将pos位置后面的元素向后移动一位
    for(i = l->length - 1;i >= pos - 1;i--){
   
   
        l->data[i + 1] = l->data[i];
    }
    //将新元素插入到pos位置
    l->data[pos - 1] = val;
    //顺序表长度加1
    l->length++;
    return 1;//插入成功
}

这里需要注意一个问题，就是我们所说的位置和下标是不同的，比如插入位置1，它的下标就为0，要记住下标永远比逻辑位置小1。

我们来分析一下插入算法，既然是插入，算法时间肯定消耗在移动元素上。
最优情况：若插入的位置是表尾，则无需移动元素
最坏情况：若插入的位置是表头，则需移动表中所有元素
对于长度为length的顺序表，若有效元素个数为n，且顺序表未满，此时对于每个元素位置，插入所需要的移动的元素个数如下：

n + 1：这是表尾元素的后一个位置，我们知道这个位置在表未满的情况下是可以插入的，此时插入所需要移动的元素个数为0
n：这是表尾元素，此时插入所需要移动的元素个数为1，仅移动表尾元素即可
n - 1：这是倒数第二个元素，此时插入所需要移动的元素个数为2
1：依次类推，直到表头元素，此时插入所需要移动的元素个数为n

要考虑每个元素位置(n + 1种情况)的插入次数，计算如下：
$$\frac{1}{n + 1}(0 + 1 + ... + n - 1 + n) = \frac{1}{n + 1}\frac{n(n + 1)}{2} = \frac{n}{2}$$
所以对于顺序表插入算法的平均时间复杂度为O(n)。

顺序表的删除

学习完插入操作后，我们来看看删除。
看下面一个顺序表：
在这里插入图片描述
删除操作同样分为两种情况：

表尾删除
非表尾删除

当删除的元素位置为表尾元素，那么直接删除即可：
在这里插入图片描述
而如果删除的元素位置不为表尾元素，那么在删除元素之后还需将删除位置后面的元素都向前移动：

当然还得考虑删除的异常情况：
删除元素不需要考虑顺序表是否满的情况，删除位置的最大值即为顺序表的表尾元素位置，所以有效范围：[1，有效元素个数]。
当顺序表为空，即没有元素时，就不能进行删除操作了，所以要对顺序表是否为空进行校验。

综上所述，顺序表的删除算法思想如下：

判断删除位置pos是否合法
判断顺序表是否为空，若已空，返回-1
将删除位置的元素值进行保存(这里一定要先进行报错，否则移动之后元素值就找不到了)
将pos位置之后的所有元素向前移动一位
顺序表长度length减1，此时删除成功，返回1

分析过后，通过代码实现一下：

int DeleteList(SqList *l,int pos,int *val){
   
   
    int i;
    //判断删除位置是否合法
    if(pos < 1 || pos > l->length){
   
   
        return -1;
    }
    //判断顺序表是否为空
    if(l->length == 0){
   
   
        return -1;
    }
    //保存待删除位置的元素值
    *val = l->data[pos - 1];
    //将pos位置后面的元素向前移动一位
    for(i = pos - 1;i <= l->length;i++){
   
   
        l->data[i] = l->data[i + 1];
    }
    //顺序表长度减1
    l->length--;
    return 1;//删除成功
}

我们同样地来分析一下删除算法。
最优情况：删除位置为表尾元素，不需要移动元素
最坏情况：删除位置为表头元素，需要移动表中除表头元素的所有元素
对于长度为length的顺序表，若有效元素个数为n，此时对于每个元素位置，插入所需要的移动的元素个数如下：
1：若删除第一个元素，则需移动n - 1个元素
2：若删除第二个元素，则需移动n - 2个元素
n：依次类推，若删除最后一个元素，则无需移动元素
要考虑每个元素位置(n + 1种情况)的插入次数，计算如下：
$$\frac{1}{n}[(n - 1)+ (n - 2) + ... + 1 + 0] = \frac{1}{n}\frac{n(n - 1)}{2} = \frac{n - 1}{2}$$
所以对于顺序表删除算法的平均时间复杂度为O(n)。

顺序表的查找

顺序表中的查找分为两种：

查找指定元素值的位置
查找指定位置的元素值

查找算法有很多，这个我将在后续的专栏文章中着重讲解，这里只采用顺序查找的方式，即：从第一个元素开始比较，直到最后一个元素，这也是效率最低的查找算法。

查找指定元素值的位置

如何通过指定元素值查找其在顺序表中的位置呢？
比如下面的顺序表中元素值为2的位置是多少？
在这里插入图片描述
这个想必很简单吧，循环比较顺序表中的所有元素，如果找到与查找元素值相同的元素，则返回该元素值在顺序表中的位置；如果没有找到，则返回-1，表示查找失败。
代码实现如下：

int LocateElem(SqList l,int val){
   
   
    int i;
    //若顺序表为空，直接查找失败
    if(l.length == 0){
   
   
        return -1;
    }
    //循环查找
    for(i = 0;i < l.length;i++){
   
   
        if(l.data[i] == val){
   
   
            return i + 1;    //返回逻辑位置(下标 + 1)
        }
    }
    return -1;//查找失败
}

同样来分析一下该算法的时间复杂度，该算法的重点在于比较次数，所以，我们来分析一下比较次数：

对于第一个元素1，比较次数为1次
对于第二个元素2，比较次数为2次
对于第三个元素3，比较次数为3次
以此类推，对于第n个元素x，比较次数为n次

计算如下：
$$\frac{1}{n}(1 + 2 + 3 + ... + n - 1 + n) = \frac{1}{n}\frac{n(n + 1)}{2} = \frac{n + 1}{2}$$
该算法的平均时间复杂度为O(n)。

查找指定位置的元素值

查找指定位置的元素值那就太简单了，直接返回就可以了。

int GetElem(SqList l,int pos){
   
   
    //判断pos值的合法性
    if(pos < 1 || pos > l.length){
   
   
        return -1;
    }
    //判断顺序表是否为空
    if(l.length == 0){
   
   
        return -1;
    }
    //返回元素值
    return l.data[pos - 1];
}

该算法过于简单，没有什么需要特别说明的地方。

最后

本篇文章是数据结构专栏的最后一篇试读文章，开始我考虑了很久，虽然专栏价格并不贵，但是谁的钱都不是大风刮来的，谁都想花最少的钱买到最好的东西。
付费专栏的门槛其实是比较低的，所以如何能够让读者放心地购买，最好的办法就是试读，专栏的前三篇都是一些废话和概念性的东西，显然体现不出专栏的水平。所以，我决定让大家试读一篇技术性的文章，后面的文章风格也都是如此，可能文章内容会有点啰嗦，但也是为了照顾基础差的同学。如果觉得本专栏会对你有所帮助，还请大家多多支持。

源代码

文章中的所有代码：

#include <stdio.h>
#include <malloc.h>

#define MAX_SIZE 10        //线性表初始长度
#define ElemType int
typedef struct{
   
   
    int data[MAX_SIZE];
    int length;        //线性表长度

}SqList;

int GetElem(SqList l,int pos){
   
   
    //判断pos值的合法性
    if(pos < 1 || pos > l.length){
   
   
        return -1;
    }
    //判断顺序表是否为空
    if(l.length == 0){
   
   
        return -1;
    }
    //返回元素值
    return l.data[pos - 1];
}

int LocateElem(SqList l,int val){
   
   
    int i;
    //若顺序表为空，直接查找失败
    if(l.length == 0){
   
   
        return -1;
    }
    //循环查找
    for(i = 0;i < l.length;i++){
   
   
        if(l.data[i] == val){
   
   
            return i + 1;    //返回逻辑位置(下标 + 1)
        }
    }
    return -1;//查找失败
}

int DeleteList(SqList *l,int pos,int *val){
   
   
    int i;
    //判断删除位置是否合法
    if(pos < 1 || pos > l->length){
   
   
        return -1;
    }
    //判断顺序表是否为空
    if(l->length == 0){
   
   
        return -1;
    }
    //保存待删除位置的元素值
    *val = l->data[pos - 1];
    //将pos位置后面的元素向前移动一位
    for(i = pos - 1;i <= l->length;i++){
   
   
        l->data[i] = l->data[i + 1];
    }
    //顺序表长度减1
    l->length--;
    return 1;//删除成功
}

int InsertList(SqList *l,int pos,int val){
   
   
    int i;
    //判断插入位置pos是否合法
    if(pos < 1 || pos > l->length + 1){
   
   
        return -1;
    }
    //判断顺序表是否已满
    if(l->length == MAX_SIZE){
   
   
        return -1;
    }
    //将pos位置后面的元素向后移动一位
    for(i = l->length - 1;i >= pos - 1;i--){
   
   
        l->data[i + 1] = l->data[i];
    }
    //将新元素插入到pos位置
    l->data[pos - 1] = val;
    //顺序表长度加1
    l->length++;
    return 1;//插入成功
}

SqList InitList(){
   
   
    //声明顺序表
    SqList l;
    l.length = 0;
    return l;
}

//输出顺序表中元素的函数
void displayTable(SqList l){
   
   
    int i;
    for (i = 0;i < l.length;i++) {
   
   
        printf("%d\t",l.data[i]);
    }
    printf("\n");
}

线性表的顺序实现

线性表的定义

线性表的抽象数据类型定义

线性表的顺序表示和实现

元素存储位置的计算

顺序表的实现

顺序表的初始化

顺序表的销毁

清空顺序表

求顺序表长度

判断顺序表是否为空

顺序表的插入

顺序表的删除

顺序表的查找

查找指定元素值的位置

查找指定位置的元素值

最后

源代码

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

线性表的顺序实现

线性表的定义

线性表的抽象数据类型定义

线性表的顺序表示和实现

元素存储位置的计算

顺序表的实现

顺序表的初始化

顺序表的销毁

清空顺序表

求顺序表长度

判断顺序表是否为空

顺序表的插入

顺序表的删除

顺序表的查找

查找指定元素值的位置

查找指定位置的元素值

最后

源代码

热门文章

最新文章

相关电子书