线性表的顺序储存 – 予安的博客

线性表的顺序存储是通过一个连续的内存空间来存放表中的元素，通常用数组来实现。顺序存储的特点是每个元素在内存中的地址是连续的，因此可以通过索引直接访问元素，效率较高。

顺序存储的特点：

内存连续：元素在内存中占据连续的空间，这使得可以通过数组下标快速访问每个元素，时间复杂度为O(1)。
固定大小：如果是静态数组（如C语言中的数组），存储空间在创建时就已经确定，不易修改。如果需要增加或删除元素，可能需要重新分配内存。
随机访问：可以直接通过下标访问任意元素，效率高。
操作简单：如插入、删除等操作需要移动元素，效率较低。对于数组中的插入或删除，可能需要将后续的元素一一移动，时间复杂度为O(n)。
存储空间浪费：在存储空间不足或超出预期时，可能需要重新分配较大空间，从而浪费空间。

顺序存储常见操作：

访问操作：直接通过索引访问元素，时间复杂度O(1)。
插入操作：通常需要将插入位置后的所有元素向后移动一位，时间复杂度O(n)。
删除操作：删除元素后，需要将删除位置后的所有元素向前移动，时间复杂度O(n)。
查找操作：查找某个元素的时间复杂度为O(n)，如果是顺序查找。

举例说明：

假设我们有一个顺序存储的线性表，存储整数数组arr = [1, 3, 5, 7, 9]，若要插入元素6到位置2（即元素5和7之间），我们需要移动元素5及其后的元素，新的顺序表变为[1, 3, 5, 6, 7, 9]。

适用场景：

顺序存储适合元素数量固定或插入、删除操作较少的场景，如需要频繁随机访问元素的情况。

优点：

访问速度快，直接通过索引定位元素。
内存连续，占用空间较小。

缺点：

插入、删除效率低，需要移动元素。
空间不易调整，可能会浪费存储空间。

总结来说，顺序存储结构适合在需要快速访问、元素数量不经常变动的场景中使用，但对于频繁插入和删除操作的场景，可能需要考虑其他数据结构（如链表）。

C语言中顺序表的实现

#include <stdio.h>
#define Maxsize 50

typedef int ElemType;//便于更改顺序表中的数据类型
typedef struct {//定义顺序表
    ElemType data[Maxsize];
    int length;
}SeqList;//定义顺序表别名为SeqList

bool SeqInsert(SeqList &L,int pos,ElemType element) {
    //插入操作
    if(pos<1 || pos>L.length+1) {//判断合法插入范围
        return false;
    }
    if(L.length==Maxsize) {//链表已满，无法插入
        return false;
    }
    for (int i = L.length-1; i >= pos-1; i--) {//从表尾元素开始，向后移动一个位置，直到插入位置为止
        L.data[i+1] = L.data[i];
    }
    L.data[pos-1] = element;//赋值
    L.length++;//增加表长
    return true;
}


void PrintList(SeqList L) {//遍历打印表中元素
    for (int i = 0; i < L.length; i++) {
        printf("
    }
}

bool SeqDelete(SeqList &L,int pos) {
    //删除指定位置的元素
    if(pos<1 || pos>L.length) {//检查删除位置是否合法
        return false;
    }
    for (int i = pos-1; i < L.length; i++) {//从删除位置开始，直到最后一位，均向前移动一个位置
        L.data[i] = L.data[i+1];
    }
    L.length--;
    return true;
}


int main() {
    SeqList L;//创建名为L的顺序表
    //初始化元素
    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.length=3;//记录表长

    int pos=2;
    int element;
    scanf("
    bool ret=SeqInsert(L,pos,element);//使用的三个参数:表名称、插入位置、插入值
    if(ret==true) {
        PrintList(L);
        printf("\n");
    }
    else {
        printf("插入失败！\n");
    }

    scanf("
    ret=SeqDelete(L,pos);
    if(ret==true) {
        PrintList(L);
    }
    else {
        printf("false\n");
    }
    return 0;
}