顺序表属于线性表，是一种具有相同数据结构的有序序列。序列中的元素存放在连续的地址空间中。

顺序表的存储结构有两种

  1. 静态分配

    1
    2
    3
    4
    5
    /*静态分配的顺序表*/
    typedef struct{
        ElemType elem[MAXSIZE];
        int length;
    }Sqlist;

    静态分配中，定义了Sqlist结构体，含有两个成员，分别是MAXSIZE大小的数组elem,用于记录顺序表长度的length

  2. 动态分配

    在动态分配的顺序表中，我们会使用malloc函数申请一块连续的内存，成员elem指针指向大小为MAXSIZE的数组第一个元素的首地址，length用于记录元素个数

    1
    2
    3
    4
    5
    6
    typedef int ElemType;   /*线性表元素类型*/
    /*线性表*/
    typedef struct{
        ElemType *elem; /*元素基地址*/
        int length;     /*元素个数*/
    }SqList;

上面的ElemType是一种抽象的数据类型，而不是固定的数据类型，使用者可以根据实际需要使用typedef定义ElemType的类型，可以是结构体类型，也可以是int,float,char类型。

静态分配和动态分配的区别

  1. 静态分配的数据存储在局部区域，自动释放。动态分配的数据存储在堆区，由使用者管理释放
  2. 静态分配会预先分配一大块内存，而动态分配可以根据需要分配合理的大小，节约空间

对于某些大小固定的数据，推荐使用静态分配的方式方便管理。对于大小不固定，在运行时可能需要动态改变其大小的数据推荐使用动态分配的方式进行管理。

顺序表的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
/*构建一个空的线性表*/
Status InitList(SqList &L);
/*销毁线性表*/
void DestoryList(SqList &L);
/*按位寻找第i个元素,将值放入e中*/
Status GetElem(SqList L,int i,ElemType &e);
/*按值寻找元素,返回序列号*/
int LocateElem(SqList L,ElemType e);
/*在第i个位置之前插入元素*/
Status ListInsert(SqList &L,int i,ElemType e);
/*删除第i个元素*/
Status ListDelete(SqList &L,int i);

顺序表的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
    name:   InitList
    @descrption:    构建一个空的线性表
    @detail:    malloc申请内存，length长度为0
*/
Status InitList(SqList &L)
{
    L.elem=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    if(L.elem==NULL){   /*内存分配失败*/
        return ERROR;
    }
    L.length=0;
    return OK;
}

在初始化操作中，创建一个空的线性表。具体步骤为：预先分配预定大小的空间，使elem指向这段空间的首地址，将length置为0，表示当前表为空。

顺序表的插入与删除

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
    @name:      ListInsert
    @descrption:    在第i个位置插入元素
*/
Status ListInsert(SqList &L,int i,ElemType e)
{
    /*链表长度为length,可以在length+1位置插入元素，即表尾插入*/
    if(i<1||i>L.length+1){//校验i值是否合理 
        return ERROR;
    }
    // i i+1 ... length-1元素向后移动一位
    for(int j=L.length-1;j>=i-1;j--){//最后一个元素的下标为length-1，第i个元素的下标为i-1
        L.elem[j+1]=L.elem[j];//将第j个元素的值赋给第j+1个元素
    }
    L.elem[i-1]=e;//将e赋给第i个元素
    L.length++;
    return OK;
}

插入操作是在第i个位置指向插入元素X，使X成为第i个元素。i的合法值为[i,length+1]，当i=length+1时表示在表尾插入元素。

插入具体实现步骤为将i和i后面所有的元素集体向后移动一个单位。那么是从第i个元素开始移动还是第length个元素开始移动？

如果从第i个元素开始移动，将elem[i]的值覆盖elem[i+1]的值，则elem[i+1]原始的值将会丢失，无法向后移动。所以应该从第length个元素开始依次向后移动。

QQ20240521-225632.png

QQ20240521-225808.png

所以在第i个位置插入元素时应该从表尾开始到第i个元素结束逐个向后移动。最后一个元素的下标索引为length，第i个元素对应的下标索引为i-1

1
2
3
for(int j=L.length-1;j>=i-1;j--){//最后一个元素的下标为length-1，第i个元素的下标为i-1
        L.elem[j+1]=L.elem[j];//将第j个元素的值赋给第j+1个元素
    }

QQ20240521-231235.png

当后移结束后，将第i个元素(下标为i-1)赋值为x，赋值操作结束，更新length的长度，函数返回。

删除操作

1
2
3
4
5
6
7
8
9
10
11
12
/*删除第i个元素*/
Status ListDelete(SqList &L,int i)
{
    if(i<1||i>L.length){//校验i值是否合理
        return ERROR;
    }
    for(int j=i;j<=L.length-1;j++){
        L.elem[j-1]=L.elem[j];
    }
    L.length--;
    return OK;
}

在删除第i个元素前需要校验i的值是否合法，i的有效值为[1,length]。

删除的具体操作为从第i+1个元素(下标为i)开始到第length元素(下标为length-1)结束，依次向前移动。移动完成后需要将length值减1

QQ20240521-232038.png

顺序表的查找

顺序表的查找包括按值查找和按位查找

按值查找
按值查找对顺序表进行遍历，当前元素与目标值相同时结束循环，返回当前索引i。如果查找失败，则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
    @name:          LocateElem
    @descrption:    按值寻找元素
    @return:        成功    返回序号
                    失败    返回-1
*/
int LocateElem(SqList L,ElemType e)
{
    for(int i=0;i<L.length;i++){
        if(L.elem[i]==e)
            return i+1;/*i为索引，返回序号i+1*/
    }
    return -1;/*查找失败,返回-1*/
}

按位查找

按位查找第i个元素操作，先对i值进行校验，后利用数组可以按位访问值的特性，返回elem[i-1]的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
    @name: GetElem
    @descrption:    按位寻找第i元素,将值放入e中
    @detail:        第i个元素从1开始记数，对于数组下表
*/
Status GetElem(SqList L,int i,ElemType &e)
{

    if(i<1||i>L.length)/*判断i值是否合理*/   
        return ERROR;
    e=L.elem[i-1];/*第i个元素对应数组下标i-1*/
    return OK;
}