【数据结构】线性表的顺序表示

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

1. 顺序表的定义

顺序表：用顺序存储的方式实现线性表。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2. 优缺点比较

3. 顺序表的实现——静态分配

#define MaxSize 50  // 定义线性表的长度
typedef struct{
    ElemType data[MaxSize]; // 用静态的“数组”存放数据元素
    int len;   // 顺序表的当前长度
}SqList;  // 顺序表的类型定义

说明：

1. 对于图中的第2步，如果不初始化，则有可能出现脏数据的情况。
2. 静态分配的方式，顺序表从一开始就确定了长度，无法改变。
3. 如果一开始分配的内存较大，则有可能出现浪费内存的情况。

4. 顺序表的实现——动态分配

#define InitSize 100  // 表长度的初始定义
typedef struct{
    ElemType *data;  // 指示动态分配数组的指针
    int MaxSize,length;  // 数组的最大容量和当前长度
}SeqList;  // 动态分配数组顺序表的类型定义

C的初始动态分配语句为：

L.data=(ElemType*)malloc(sizeof(ElemType)\*InitSize);

说明：

• malloc函数返回一个指针类型，需要强制转换为你定义的数据元素类型指针。
• malloc函数的参数，InitSize表示要分配多大的连续内存空间。
• 对于malloc函数申请的空间，如果要释放需要使用free函数。

C++的初始动态分配语句为：

L.data=new ElemType[InitSize];

5. 顺序表的基本操作

1)插入操作

插入操作需要将要插入的位置的所有元素向后移动1位。

时间复杂度分析：

最好情况：在表尾插入元素，不需要移动元素，时间复杂度为O(1)。

最坏情况：在表头插入元素，所有元素依次后移，时间复杂度为O(n)。

平均情况：在插入位置概率均等的情况下，平均移动元素的次数为n/2，时间复杂度为O(n)。

代码片段：

// 判断插入位置i是否合法（满足1<=i<=len+1）
// 判断存储空间是否已满（即插入x后是否会超出数组长度）
for(int j=L.len;j>=i;j--){
    L.data[j]=L.data[j-1]; // 将最后一个元素到第i个元素依次后移一位
}
L.data[i-1]=x;  // 空出的位置i处放入x
L.len++;  // 线性表长度加1

说明：数组的下标是从0开始的，但是这里说的第几个元素是表示顺序表的位序，是从1开始的。第i个元素，下标实际为i-1。

2)删除操作

删除操作需要将要删除位置之后的所有元素向前移动1位。

时间复杂度分析：

最好情况：删除表尾元素，不需要移动任何元素，时间复杂度为O(1)。

最坏情况：删除表头元素，之后的所有元素依次前移，时间复杂度为O(n)。

平均情况：在删除位置概率均等的情况下，平均移动元素的次数为(n-1)/2，时间复杂度为O(n)。

代码片段：

// 判断删除位置i是否合法（满足1<=i<=len）
e=L.data[i-1];  // 将被删除的元素赋值给e
for(int j=i;j<L.len;j++){
    L.data[j-1]=L.data[j];  // 将删除位置后的元素依次前移
}
L.len--;  // 线性表长度减1

说明：数组的下标是从0开始的，但是这里说的第几个元素是表示顺序表的位序，是从1开始的。第i个元素，下标实际为i-1。

3)按值查找

// 查找成功，返回位置，位置从1开始，查找失败，返回0。e表示要查找的元素，这里不考虑重复元素
for(int i=0;i<L.len;i++){
    if(L.data[i]==e){
        return i+1;  // 加1就是元素在顺序表中的位置
    }
}

时间复杂度分析：

最好情况：查找元素在第一个位置，时间复杂度为O(1)。

最坏情况：查找元素在最后一个位置，时间复杂度为O(n)。

平均情况：在查找位置概率均等的情况下，平均查找次数为(n-1)/2，时间复杂度为O(n)。

4)按位查找

// 判断查找位置是否合法
// 查找成功，返回位置，位置从1开始，查找失败，返回0。e表示要查找的元素，这里不考虑重复元素
int ListFind(SqList L,ElemType e){
    for(int i=0;i<L.len;i++){
        if(L.data[i]==e){
            return i+1;  // 加1就是元素在顺序表中的位置
        }
    }
    return 0;
}

时间复杂度分析：

按位查找时，由于顺序表的各个数据元素在内存中连续存放，具有“随机存取”特性。因此时间复杂度为O(1)。

6. 小结

如想获取完整代码，微信公众号后台回复“顺序表”即可。