定义

顺序表(array-based list)又称为向量(vector)是在计算机内存中以数组的形式保存的线性表.

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。

顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

顺序表的基本操作

顺序表的声明
array_based_list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define ListSize 100      //线性表的最大长度
typedef int DataType;// 顺序表内元素类型

/**
** 顺序表
**/

//定义
typedef struct{
    DataType data[ListSize];   //用数组存储线性表中的元素
    int length;           //顺序表中元素的个数
}SeqList, *PSeqList;

//初始化顺序表
void InitList(PSeqList L);

//按序号查找
int GetData(PSeqList L, int i);

//按值查找
int Locate(PSeqList L, DataType e);

//插入操作
int InsList(PSeqList L, int i, DataType e);
//删除操作
int DelList(PSeqList L, int i);
//打印
void SeqListPrint(PSeqList L);

顺序表的初始化
把顺序表初始化为空的顺序表；只需把顺序表的长度length置为0即可；

这里不需要判断PSeqList L是否为空指针,因为在生成指针时就应该确保指针不为空.如果你用了空指针那么你活该如此.

1
2
3
void InitList(PSeqList L){
    L->length = 0;
}

按序号查找
查找顺序表中第i个元素的值（按序号查找），如果找到，将将该元素值赋给e。查找第i个元素的值时，首先要判断查找的序号是否合法，如果合法，返回第i个元素对应的值。

1
2
3
4
5
6
7
//按序号查找
int GetData(PSeqList L, int i){
    if (i<0 || i>ListSize || L->length < 1 ){
        return -1;
    }
    return L->data[i];
}

按值查找

查找数据元素e在表中的位置，可以从表头开始一直遍历表中元素，如果找到与e相等的元素则返回元素在表中的位置,没有找到则返回-1；

1
2
3
4
5
6
7
8
9
//按值查找
int Locate(PSeqList L, DataType e){
    for (int k = 0; k < L->length; k++){
        if (L->data[k] == e){
            return k;
        }
    }
    return -1;
}

插入操作
在数据表的第i个位置插入元素，首先确保插入位置合法,不能越界(大于顺序表最大长度或者小于零),要按照顺序插入元素(插入元素的位置不能大于顺序表的长度).

要在顺序表的第i个位置插入元素e，先移动最后一个元素，再移动倒数第二个元素，依次类推；在插入元素之后要将表长加一;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//插入操作
int InsList(PSeqList L, int i, DataType e){

    //判断插入位置是否合法,只能按顺序插入
    //判断顺序表是否已满,最后一位保留防止溢出
    if (i < 0 || i > L->length || L->length >= (ListSize - 1)){
        printf("插入位置不合法!\n");
        return -1;
    }
    for (int k = L->length; i <= k; k--){
        L->data[k + 1] = L->data[k];
    }
    L->data[i] = e;
    L->length++;   //数据表的长度加1
    return 1;
}

删除操作
删除数据表中的第i个元素，需要将表中第i个元素之后的元素依次向前移动一位.

进行删除操作之前要判断位置合法性,凡是超出或小于顺序表长度的位置均非法.

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除操作
int DelList(PSeqList L, int i){
    if (i<0 || i>L->length || L->length<1){
        printf("error！\n");
        return  -1;
    }
    while(i < L->length){
        L->data[i] = L->data[i+1];
        i++;
    }
    L->length--;
    return 1;
}