【数据结构】---线性表

目录

• 线性表的定义和特点
• 线性表的顺序表示和实现
  • 线性表的顺序存储表示
  • 顺序表中基本操作的实现
    • 1. 初始化
    • 2. 取值
    • 3. 查找
    • 4. 插入
    • 5. 删除

线性表的定义和特点

线性表属于线性结构。
线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个元素都有一个前驱和后继。

同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。
由 (n (n geq 0)) 个数据特性相同的元素构成的有限序列称为线性表。线性表中元素的个数 (n (n geq 0)) 定义为线性表的长度， (n = 0) 时称为空表。

线性表的顺序表示和实现

线性表的顺序存储表示

线性表的顺序表示是指用一组地址连续的存储单元一次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构，称这种存储结构的线性表为**顺序表 (Sequential List)。逻辑上相邻的元素，物理次序也是相邻的。

线性表的第一个数据元素的存储位置，通常称作线性表的起始位置或基地址。线性表的顺序存储结构是一种随机存取的存储结构。
通常使用数组来描述数据结构中的顺序存储结构，由于线性表的长度可变，在C语言中可用动态分配的一维数组表示线性表，描述如下：

// ----------顺序表的存储结构----------
#define MAXSIZE 100 // 顺序表可能达到的最大长度
typedef struct
{
    ElemType *elem; // 存储空间的基地址
    int length; // 当前长度
}SqList; // 顺序表的结构类型为SqList

顺序表中基本操作的实现

1. 初始化

顺序表的初始化操作就是构造一个空的顺序表。

算法步骤：

• 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
• 将表的当前长度设为0

Status InitList(SqList &L)
{
    // 构造一个空的顺序表L
    L.elem = new ElemType[MAXSIZE]; // 为顺序表分配一个大小为MAXSIZE的数组空间
    if(!L.elem) exit(OVERFLOW); // 存储分配失败退出
    L.length = 0; // 空表长度为0
    return OK;
}

2. 取值

取值操作就是根据指定的位置i，获取顺序表的中的第i个数据元素的值。

算法步骤：

• 判断指定的位置i是否合理 ((1 leq i leq L.length)) ，若不合理，则返回ERROR。
• 若i值合理，则将第i个元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的值。

Status GetElem(SqList L, int i, ElemType &e)
{
    if(i < 1 || i > L.length) return ERROR; // 判断i值是否合理，若不合理，返回ERROR
    e = L.elem[i-1]; // elem[i-1]单元存储第i个数据元素
    return OK;
}

顺序表的取值算法的时间复杂度为 (O(1)) 。

3. 查找

查找操作就是根据指定的元素值e，查找顺序表中的第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

算法步骤：

• 从第1个元素起，依次和e相比较，若找到和e相等的元素L.elem[i]，则查找成功，返回该元素序号i+1。
• 若查遍整个顺序表都没有找到，则查找失败，返回0。

int LocateElem(SqList L, ElemType e)
{   
    // 在顺序表L中查找值为e的数据元素，返回其序号
    for(i = 0; i < L.length; ++i)
        if(L.elem[i] == e) return i+1; // 查找成功，返回序号i+1
    return 0; // 查找失败，返回0
}

算法分析：
当在顺序表查找一个数据元素时，其主要时间花在数据的比较上，而比较的次数取决于被查元素在顺序表中的位置。
在查找时，为了确定数据元素在顺序表中的位置，需和其进行比较的数据元素的个数的期望值称为算法在查找成功时的平均查找长度 (Average Search Length, ASL)。
假设 (p_{i}) 是第i个元素和e相等的概率， (C_{i}) 是找到和e相等的元素之前已经比较过的元素的个数，则在长度为n的线性表中，查找成功时的平均查找长度为 $$ASL = sum_{i = 1}^{n} p_{i}C_{i}$$
顺序表按值查找算法的平均时间复杂度为 (O(n)) 。

4. 插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使 ((a_{1}, ... , a_{i-1}, a{i}, ... , a_{n}) 变为 ((a_{1}, ... , a_{i-1}, e, a{i}, ... , a_{n}) 。
一般情况下，在第 (i (1 leq i leq n)) 个位置插入一个元素时，需要从最后一个元素（第n个元素）开始，依次向后移动一个位置，直至第i个元素（包括第i个元素），共 (n-i+1) 个元素。

算法步骤：

• 判断插入位置i是否合法，（i值的合法范围是 (1 leq i leq n+1) ），若不合法则返回ERROR。
• 判断顺序表的存储空间是否已满，若满则返回ERROR。
• 将第n个至第i个元素依次向后移动一个位置，空出第i个位置（i = n+1）时无需移动）
• 将要插入的新元素e放入第i个位置
• 表长加1

Status ListInsert(SqList &L, int i, ElemType e)
{
    if( (i < 1) || (i > L.length + 1)) return ERROR; // 判断位置i是否合法
    if(L.length == MAXSIZE) return ERROR; // 当前存储空间已满
    for(int j = L.length - 1; j >= i-1; --j)
        L.elem[j+1] = L.elem[j]; // 元素后移
    L.elem[i] = e;
    ++L.length;
    return OK;
}

上述算法没有处理表的动态扩充。
顺序表插入算法的平均时间复杂度为 (O(n)) 。

5. 删除

线性表的删除操作是将表的第i个元素删去。
一般情况下，删除第 (i (1 leq i leq n)) 个元素时，需要将第i+1个元素至第n个元素（共n-i个元素）依次向前移动一个位置（i = n时无需移动）。

算法步骤：

• 判断删除位置i是否合法，（合法值为 (1 leq i leq n) ），若不合法则返回ERROR
• 将第i+1个至第n个元素依次向前移动一个位置（i = n时无需移动）
• 表长减1

Status ListDelete(SqList &L, int i)
{
    if((i < 1) || (i > L.length)) return ERROR; // i的位置不合法
    for(j = i; j <= L.length - 1; j++) //移动元素
        L.elem[j-1] = L.elem[j];
    --L.length; // 表长减1
    return OK;
}

顺序表删除算法的平均时间复杂度为 (O(n)) 。