大话数据结构2-顺序存储结构

发表于 更新于 分类于 ， Valine：

线性表是一种元素的有限序列。它的数据对象集合为 ${a_1,a_2,…,a_n}$, 每个元素的类型都相同。其中，除第一个元素$a_1$ 外，每个元素都有且只有一个直接前驱元素，除了最后一个元素 $a_n$ 外，每个元素都有且只有一个直接后继元素。

I 线性表的顺序存储结构简介

顺序存储结构是一种物理上连续的存储线性表数据的存储方案。

对于顺序存储的线性表，需要注意的是区分: “数组的长度” 和 “线性表的长度” ，通常，数组的长度 是存放线性表的存储空间的长度，而 线性表的长度 则是线性表中数据元素的个数。

我们用C代码描述线性表的顺序存储（实际上就是定义对象的属性）：

1
2
3
4
5
6
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList;

它有三个重要的属性：

  • 存储空间的起始位置：数组 data，它的存储位置就是顺序存储空间的存储位置。
  • 最大容量：数组长度 MaxSize。
  • 线性表的当前长度：Length。

II 顺序存储结构的读取和写入

线性表中任一元素的存储位置可以由第一个元素的位置 + 该元素在线性表中的次序推导得出：

$$LOC(a_i) = LOC(a_1) + (i-1)*c$$

其中 LOC 获取元素的位置，c 是指每个元素c个存储单元。因此，读取、存入顺序存储结构的线性表数据非常方便，它们所消耗的计算成本是相同的，时间复杂度都为 $O(1)$, 这种存储结构也叫做随机存储结构。

III 顺序存储结构的插入和删除

插入算法的思路：

  • 如果插入位置不合理，抛出异常；
  • 如果线性表长度大于数组长度，则抛出异常或者动态增加容量；
  • 从最后一个元素开始向前遍历到第 i 个位置，分别将它们向后移动一个位置；
  • 将要插入的元素填入位置 i 处；
  • 表长增加1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status ListInsert(sqList *L, int i, ElemType e){
    int k;
    if (L->length == MAXSIZE) // 顺序线性表已经填满
        return ERROR;

    if (i < 1 || i > L->length + 1)
        return ERROR;

    if (i <= L->length){ //判断元素不在表尾，即插在了有元素存放的地方
        for (k = L->length - 1; k >= i - 1; k--)
            L->data[k+1] = L->data[k]; // 元素向后移动1位
    }

    L->data[i-1] = e;
    L->length++;
    return OK;
}

删除操作：

  • 如果删除的位置不合理，抛出异常；
  • 去除删除元素；
  • 从删除元素的位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置；
  • 表长减1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListDelect(sqList *L, int i, ElemType *e){ //删除掉的元素放在 *e 的位置
    int k;

    if (L->length == 0)     //如果线性表为空
        return ERROR;

    if (i < 1 || i > L->length)     //输入不合法
        return ERROR;

    *e = L->data[i-1]; //将删除的数据存放在e

    if (i < L->length){ //判断元素不在表尾
        for (k = i; k < L->length; k++)
            L->data[k-1] = L->data[k]; // 元素向前移动一位
    }

    L->length--;
    return OK;
}

Note: 一定要考虑周全可能出现的 error 情况，像上面删除元素的代码，我刚开始处理时就忘记了线性表为空的情况。

IV 线性表的优缺点总览

优点：

  1. 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
  2. 可以快速的存取表中任一位置的元素；线性表存、读数据的时间复杂度为$O(1)$。

缺点：

  1. 插入和删除操作需要移动大量元素，插入删除数据的时间复杂度为 $O(n)$；
  2. 当线性表长度变化较大时，难以确定存储空间的容量；
  3. 造成存储空间的“碎片”。