数据结构（3）— 线性表之顺序存储详解介绍（含代码）

（1）博客代码在 数据结构代码---GitHub仓库；

线性表介绍

线性表的基础概念

（1） 甲骨文表示：线性表是零个或多个数据元素的有限序列。
（2）线性表，顾名思义，就是说这个数据存储是线性的。而线性的东西具有什么特征呢？
<1> 数据是一对一的排列的，中间的数据都有且仅有一个前面数据 （ 前面的数据叫做前驱 ） 和一个后面的数据 （ 后面的数据叫做后继 ）。而 数据表的最前面的数据叫做表头，最尾端的数据叫做表尾。 表头无前驱，表尾无后继。
<2> 线性表是有限的。因为计算机的存储空间是有限的，所以线性表必然有限。
<3> 线性表中的元素必须是相同类型。这个就像是我们在定义数组，一个数组中的元素，要么都是int型数据，要么都是char型数据，不可能数组中，第一个元素是int型数据，第二个元素变成了char型数据了。
（3）线性表的元素个数n（n>=0）表示线性表的长度， 当n=0时，我们将这个表称之为空表。
（4）在非空表中，每个数据元素都有一个确定的位置，比如a1就是第一个数据元素，a2就是第二个数据元素，ai就是第i个数据元素。所以我们将 i称为数据元素的 位序。

一个数据元素可以拥有多个数据项

（1）我们上面看到，一个数据元素只有一个数据项。在 数据结构（1）前言中我说了，一个数据元素可以有多个数据项，在研究数据结构时，我们都是着眼于数据元素。那有没有一个数据元素拥有多个数据项的线性表呢？有，我们常见的就是花名册。
（2）我们看到如下花名册里面，有姓名，性别，文化程度等等一些元素。 这些元素就是数据项。而人具有这些元素，所以 人这个个体就是数据元素。我们将这些人进行按照顺序排列，最后形成了花名册，这也叫做线性表。

线性表种类

（1）常见的线性表有：顺序存储（说白了就是数组），是链式存储，栈，队列。
（2）链式存储中又分为四种， 单链表， 静态链表， 循环链表， 双向链表。

线性表顺序存储介绍

顺序存储定义

定义

（1）定义： 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
（2）将上面这段话用白话文来说就是，线性表的顺序存储就是一个数组，不过与数组有些许不同，数据结构中的顺序存储定义需要增加一个length用于显示线性表的当前长度。
（3）这个时候可能会有人有疑惑了。为什么需要一个length呢？假设我们在排队买东西，由于空间的限制，只能来20个人（MAXSIZE）。而这个时候，排队的有5个人，如果有第6个人也要来排队，因为人很聪明，知道排到第五个人后面就可以了，但是在写程序的时候，你怎么知道需要将新来的数据放在哪里呢？如果不小心放在了第4个空间中，那么数据会被覆盖，出问题。放在第7位，那么第6位空着，浪费空间。
（4）线性表的顺序存储就是一个排队的过程，MAXSIZE用于定义这个队伍最大多长，而length用于指示当前位置排到哪里了。如果中间一个人突然走了，从这个人开始的后面所有人都要往前面移动，同时length要马上自减一次。如果有一个人因为紧急事件，不得不插队，从插队的位置往后移动，所有人都需要往后移动，length需要马上自增一次。
（5） 因为按照编程习惯，我们的数组首元素下标为0。所以当线性表为空的时候，last为-1，而last=1时候，线性表长度=last+1=1！！！

#define success 0
#define fail  -1
#define MAXSIZE 20          /* 存储空间初始分配量 */

typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */

typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int last;             /* 线性表当前位置，last+1=length */
}SqList,*SqLink;     /*SqList是定义线性表，SqLink是定义线性表的结构体指针*/

顺序存储方式和地址计算

其实如果学了C语言数组了，这部分没有什么可以说的。就是跟数组那样存储，是连续的。不清楚的自行去重新学习数组的知识。

数组长度与线性表长度区别

（1）我们上面说了，MAXSIZE是数组长度，这个规定了能够放进来多少数据，他的值是固定的。而length是线性表长度，他的长度是会随着线性表的删除，插入等操作发生改变，是动态的。任意时刻length<=MAXSIZE。
（2）至于为什么数组不改成动态分配，是因为这会带来性能上的消耗。我查了一些资料，以及问了bingAI，剥去关于没有及时释放不用的内存以外，更多的是malloc和free会造成资源消耗。

顺序存储实操

这里需要说的是，如果是操作成功了，返回0，操作失败返回-1。

#define success 0
#define fail  -1
#define MAXSIZE 20          /* 存储空间初始分配量 */

typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */

typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int last;             /* 线性表当前位置，last+1=length */
}SqList,*SqLink;     /*SqList是定义线性表，SqLink是定义线性表的结构体指针*/

创建顺序存储线性表

（1）我们先申请一个结构体指针，然后分配一个空间过来，如果没有分配成功，将会打印提示。
（2）如果创建成功之后，因为刚刚申请的空间中存放的值是未知的。所以按照习惯，我们一般都会将其设置为0。
（3）注意：memset函数必须写在 L -> length = -1; 前面，因为memset这一步，会将 L -> length 变成0。 因为按照数组下标的习惯，0表示首元素地址，所以当线性表为空的时候，length==-1。（可能在部分教材里面length=0表示线性表为空，所以下面关于length部分代码会有所差异，需要注意）

/*作用:   创建线性表
 *传入参数：无
 *返回参数：创建失败打印错误报告，创建成功返回创建线性表的结构体指针
 */
SqLink list_create(void)
{
    //建立线性表
    SqLink L;
    L = (SqLink)malloc(sizeof(SqList));
    //确认线性表是否存在
    if(L == NULL)
    {
        printf("list malloc failed!\n");
        return L;
    }
    //线性表存在，将其内容清空
    //注意，这两句别写反了，否则last会变成0。
    memset(L , 0 , sizeof(SqList));
    L -> last = -1;  //last表示线性表的指向位置，因为在C语言中，下标是从0开始，所以当为空表是last=-1
    //返回线性表
    return L;
}

判断线性表是否存在

判断线性表是否存在，我们可以检测他指向的地址是否有问题。

/*作用:   判断线性表是否存在
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：线性表不存在返回fail，线性表存在返回success
 */
int list_if_exist(SqLink L)
{
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    return success;
}

删除线性表

（1）如果线性表为NULL，表示传入线性表不存在，打印提示。
（2）如果线性表存在，将释放内存，同时将指针指向NULL。

/*作用:   删除线性表
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：线性表不存在返回fail，线性表成功删除返回success
 */
int list_delete(SqLink L)
{
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    free(L);
    L=NULL;
    return success;
}

清空线性表

解析看创建顺序存储线性表。

/*作用:   清空线性表
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：成功返回succes,失败返回fail
 */
int list_clear(SqLink L)
{
    //确认线性表是否存在
    if(L == NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //线性表存在，将其内容清空
    //注意，这两句别写反了，否则last会变成0。
    memset(L , 0 , sizeof(SqList));
    L -> last = -1;  //last表示线性表的指向位置，因为在C语言中，下标是从0开始，所以当为空表是last=-1
    return success;
}

判断线性表是否为空

（1）先判断线性表是否存在
（2）我们只需要判断length即可。如果对于length是什么依旧不清楚的，看下图。

/*作用:   判读线性表是否为空(因为使用者并不知道函数实现具体细节，所以需要加上这个)
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：线性表为空返回succes,否则返回fail
 */
int list_if_empty(SqLink L)
{
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    if(L -> last ==-1)
    {
        printf("list is empty!\n");
        return success;
    }
    return fail;
}

获取当前线性表长度

获取线性表长度就看length+1即可。

/*作用:   查看当前线性表长度
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：返回当前线性表的长度
 */
int list_get_length(SqLink L)
{
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    return (L->last+1);
}

判断指定数值是否在线性表中

（1）先判断线性表是否存在
（2）我们只需要将线性表中的值一个一个的与value对比即可。

/*作用:   判断value是否在线性表中
 *传入参数：
 *  @L:线性表的结构体指针
 *  @value:需要查看线性表中是否存在的值
 *        @可输入值范围受到ElemType决定
 *返回参数：value在线性表中存在返回succes,value不在线性表中或线性表不存在返回fail
 */
int list_value_if_locate(SqLink L,ElemType value)
{
    int i;
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //逐个判断线性表中的值
    for(i = 0;i<=L->last;i++)
    {
        if(L->data[i]==value)
        {
            return success;
        }
    }

    return fail;
}

在线性表指定位置插入数据

（1）判断线性表是否存在
（2）先判断线性表是否已经满了
（3）判断插入位置是否合理
（4）将要插入的位置元素都向后移动，腾出空间，让新数据插入
（5）插入新数据，last自增

/*作用:   插入数据，在线性表L的pos处插入数据value
 *传入参数：
 *  @L: 线性表的结构体指针
 *  @value: 需要插入线性表的值
 *        @可输入值范围受到ElemType决定
 *  @pos：需要插入的位置
 *        @插入位置范围受到MAXSIZE限制
 *返回参数：返回当前线性表的长度
 */
int list_insert(SqLink L,ElemType value,int pos)
{
    int i; 
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //如果线性表满了
    if(L->last == MAXSIZE-1)
    {
        printf("list is full\n");
        return fail;
    }
    //判断插入的位置是否合法
    if(pos<0 || pos > L->last+1)
    {
        printf("pos is invaild\n");
    }
    //向后移动
    for(i = L -> last;i >= pos;i--)
    {
        L->data[i+1]=L->data[i];
    }
    //更新last和插入部分数值
    L->data[pos]=value;
    L->last++;
    
    return success;
}

删除指定位置元素

（1）检查线性表是否存在
（2）是否为空表
（4）删除位置是否合理
（5）将所有数据向前移动（此时原来pos位置的数据会被pos+1处覆盖）
（6）last自减

/*作用:   删除指定位置的元素
 *传入参数：
 *  @L: 线性表的结构体指针
 *  @pos： 需要删除的数据的位置
 *        @插入位置范围受到MAXSIZE限制
 *返回参数：删除失败返回fail，成功删除返回success
 */
int list_delete_pos_value(SqLink L,int pos)
{
    int i;
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //检测是否为空表
    if(L->last==-1)
    {
        printf("list is empty!\n");
        return fail;
    }
    //检测删除位置是否合理
    if(pos < 0 || pos > L->last)
    {
        printf("pos is invalid！\n");
        return fail;
    }
    //向前移动
    for(i=pos+1;i<=L->last;i++)
    {
        L->data[i-1]=L->data[i];
    }
    //更改last
    L->last--;
    
    return success;
}

获取两个线性表的并集

（1）判断三个线性表是否存在
（2）判断他们是否为空
（3）先将L1的值存入L3中
（4）然后将L2中拥有，但是L1中没有的值存入L3中

/*作用: L1和L2并集，将并集值给到L3
 *传入参数：
 *  @L1，L2: 两个不同的线性表
 *  @L3： L1和L2并集
 *返回参数：失败返回fail，成功返回success
 */
int list_merge(SqLink L1,SqLink L2,SqLink L3)
{
    int i;
    //判断L1，L2，L3是否存在
    list_if_exist(L1);
    list_if_exist(L2);
    list_if_exist(L3);
    //判断L1，L2,是否为空
    list_if_empty(L1);
    list_if_empty(L2);
    //将L1中的所有元素存放到L3中
    for(i = 0; i <= L1->last;i++)
    {
        list_insert(L3, L1->data[i],L3->last+1);
    }
    
    for(i = 0; i <= L2->last;i++)
    {
        //判读L2中的每一个元素是否在L1中,如果不在，就存入到L3中
        if(list_value_if_locate(L1,L2->data[i])==-1)
        {
            //如果L3满了，提前结束
            if(list_insert(L3,L2->data[i],L3->last+1)==fail)
            {
                return fail;
            }
        }
    }
    return success;
}

删除线性表中重复元素

（1）判断线性表是否存在
（2）如果只有一个元素就不需要判断
（3）我们选择从第二个元素开始（建立变量i），判断i位置的元素是否与i前面元素有重复，如果重复了，那么就删除i位置的元素。此时可以跳出循环。
（4）因为删除位置i的元素之后，原来位置i+1的元素会替补到位置i处。所以我们需要先将位置i自减一次，然后在for语句中自增一次，为了保持位置i不变，所以我们需要i自减一次抵消。
（5）如果没有重复元素，那么i就自增。

/*作用:删除线性表中重复元素
 *传入参数：
 *    @L1 : 线性表的结构体指针
 *返回参数：删除成功返回success
 */
int list_purge(SqLink L)
{
    int i,j;
    //确认线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //如果当前线性表只有一个元素，就没有必要判断了
    if(L->last==0)
    {
        return success;
    }
    //让i不断向后移动
    for(i=1;i<=L->last;i++)
    {
        //将位置i之前的元素与i处元素进行判断，相同就删除
        for(j=i-1;j>=0;j--)
        {
            //如果发现前面有与位置i相同的元素，删除，保持i不动
            if(L->data[i]==L->data[j])
            {
                //位置i与前面有重复，就删除位置i的值
                list_delete_pos_value(L,i);
                //因为需要保持位置i不动，而for语句中有i++，所以这里用i--抵消
                i--;
                break;
            }
        }
    }
    return success;
}

获取指定位置元素

（1）判断线性表是否存在
（2）判断是否为空表
（3）判断获取数据的位置是否合理
（4）返回指定位置值

/*作用: 返回指定位置的值
 *传入参数：
 *  @L: 线性表的结构体指针
 *  @pos：指定位置
 *        @插入位置范围受到MAXSIZE限制
 *返回参数：线性表为空，返回fail。成功打印返回success
 */
int list_pos_value(SqLink L,int pos)
{
    //判断线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //判断是否为空表
    if(L->last==-1)
    {
        printf("list is empty!\n");
    }
    //判断获取数据的位置是否合法
    if(pos<0 || pos > L->last+1)
    {
        printf("pos is invaild\n");
    }
    //返回指定位置值
    return (L->data[pos]);
}

显示线性表中的值

（1）线性表是否存在
（2）是否为空表
（3）逐个打印线性表中的元素

/*作用: 显示线性表中的值
 *传入参数：
 *    @L: 线性表的结构体指针
 *返回参数：线性表为空，返回fail。成功打印返回success
 */
int list_show(SqLink L)
{
    int i;
    //判断线性表是否存在
    if(L==NULL)
    {
        printf("list is not exist!\n");
        return fail;
    }
    //判断是否为空表
    if(L->last==-1)
    {
        printf("list is empty!\n");
    }
    //将线性表中的值打印出来
    for(i=0;i<=L->last;i++)
    {
        printf("%d ",L->data[i]);
    }
    printf("\n");
    return success;
}

线性表顺序结构优缺点

优点

（1）存储密度高
（2）查找线性表中元素也方便

缺点

（1）需要提供一大片较大的连续存储空间。
（2）插入，删除等运算耗时，存在元素在存储空间成片移动的现象

总结

如果我们需要插入删除操作比较多，比如游戏开发中的装备经常会更换，这个用线性存储就非常不合适，链式存储就比较好。但是如果我们需要频繁查找元素，比如查找游戏ID，查看用户性别等等用顺序存储就很方便。