第三章 线性表之顺序表

• 第三章 线性表之顺序表
  • 一、什么是线性表？
    • 1> 概念
    • 2> 线性表的基本操作
  • 二、线性表的顺序存储
    • 1. 存储结构
      • 顺序存储图示
    • 2. 核心操作
      • 1> 初始化
        • 顺序表初始化图示
        • C 语言实现
      • 2> 清空
        • 顺序表清空图示
        • C 语言实现
      • 3> 销毁
        • 顺序表销毁图示
        • C 语言实现
      • 4> 插入
        • 顺序表插入图示
        • C 语言实现
      • 5> 删除
        • 顺序表删除图示
        • C 语言实现
      • 6> 随机访问
        • C 语言实现
    • 3. 总结

一、什么是线性表？

1> 概念

线性表： n 个元素的有序序列。n 可为 0，表示空表；n > 0 时，除了头元素，每个元素都有后继元素，除了尾元素，每个元素都有前驱元素。换句俗话，就是说线性表中有 n 个元素，它们按顺序串成一串儿。

线性表的特点：

1. 同一性：线性表的元素都属于同一类型；
2. 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数；
3. 有序性：线性表中元素有序。

2> 线性表的基本操作

线性表的抽象数据型规定了线性表的基本操作，它们相当于线性表的接口。基本操作只考虑功能，不考虑实现；不同的存储方式下，实现相同的功能算法也不同；后续我们将采用不同的存储方式实现这些基本操作。

1. InitList(&L)
   • 结果：构造一个空的线性表 L
2. DestroyList(&L)
   • 前提：线性表 L 已存在
   • 结果：将 L 销毁
3. ClearList(&L)
   • 前提：线性表 L 已存在
   • 结果：将 L 置为空表
4. EmptyList(&L)
   • 前提：线性表 L 已存在
   • 结果：如果 L 为空表，则返回 TRUE，否则，返回 FALSE
5. ListLength(L)
   • 前提：线性表 L 已存在
   • 结果：返回表中的元素个数
6. GetElem(L, i, &e)
   • 前提：表 L 存在，且 0 <= i <= ListLength(L) - 1
   • 结果：用 e 返回 L 中第 i 个数据元素
7. LocateElem(L, e, compare())
   • 前提：表 L 存在，compare 是数据元素的判定函数
   • 结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序，如果 e 不存在，在返回 0
8. PriorElem(L, cur_e, &pre_e)
   • 前提：线性表已存在
   • 结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
9. NextElem(L, cur_e, &next_e)
   • 前提：线性表已存在
   • 结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的前驱，否则操作失败，next_e 无定义
10. ListInsert(&L, i, e)
    • 前提：表 L 已存在，e 为合法元素值且 0 <= i <= ListLength(L)
    • 结果：在 L 中第 i 个位置之前插入新的数据 e，L 的长度加 1
11. ListDelete(&L, i, &e)
    • 前提：表 L 存在且非空，0 <= i <= ListLength(L) - 1
    • 结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1
12. ListTranverse(L, visit())
    • 前提：表 L 存在
    • 结果：依次对 L 的每个数据元素调用 visit()，一旦 visit() 失败则操作失败

二、线性表的顺序存储

线性表的顺序存储 是指用一组地址连续的存储单元存储数据，使得逻辑上相邻的元素在物理上也是相邻的。

1. 存储结构

我们可以使用一维数组来存储一个线性表的元素，具体如下：

// 缓冲区初始大小
#define LIST_INIT_SIZE  100
// 缓冲区增量
#define LIST_INCREMENT  10
// 顺序表结构
typedef struct
{
    char    *elem;     // 线性表存储空间基址，为简便起见，我们让线性表存储单个字符
    int     length;    // 线性表中元素个数
    int     listsize;  // 当前分配的存储容量
} SeqList;

顺序存储图示

顺序表

2. 核心操作

我们详细说明顺序表的核心操作，其他操作见项目代码。

1> 初始化

申请顺序表空间，初始化变量。

顺序表初始化图示

顺序表初始化

C 语言实现

// 前提：L 为未初始化的线性表
// 结果：将 L 初始化为空表
Status    InitList(SeqList& L)
{   // 开辟顺序表的初始存储空间，即：缓冲区空间
    L.elem = (char*) malloc(LIST_INIT_SIZE * sizeof(char));
    if(!L.elem)
    { // 如果申请失败，返回错误代码
        printf("存储分配失败\n");
        return OVERFLOW;
    }
    L.length = 0;                 // 设置元素个数为 0
    L.listsize = LIST_INIT_SIZE;  // 设置初始缓冲区大小
    return OK;                    // 初始化成功
}

2> 清空

将当前顺序表中数据清除，保持原有存储结构；此时缓冲区大小 L.listsize 不做改变，也就是说，缓冲区大小是可以大于初始大小 LIST_INIT_SIZE 的。

顺序表清空图示

顺序表清空

C 语言实现

// 前提：线性表 L 已存在
// 结果：将 L 置为空表
void    ClearList(SeqList &L)
{
    // 将顺序表缓冲区中的数据清零
    if(L.elem)
        memset(L.elem, 0, sizeof(char) * L.listsize);
    // 将顺序表长度置 0
    L.length = 0;
}

3> 销毁

将顺序表销毁，释放所有占用的内存。

顺序表销毁图示

顺序表销毁

C 语言实现

// 前提：线性表 L 已存在
// 结果：将 L 销毁
void    DestroyList(SeqList &L)
{
    if(L.elem)
    {
        free(L.elem);
        L.elem = NULL;
    }
    L.length = 0;
    L.listsize = 0;
}

4> 插入

在顺序表中的指定位置 i (0 <= i <= L.length) 插入元素 e。

顺序表插入图示

顺序表插入

C 语言实现

// 前提：表 L 已存在，e 为合法元素值且 0 <= i <= ListLength(L)
// 结果：在 L 中第 i 个位置之前插入新的数据 e，L 的长度加 1，
//       插入成功返回 TRUE，否则，返回 FALSE
int ListInsert(SeqList &L, int i, char e)
{   // 判断插入位置是否合法
    if(i < 0 || i > L.length)
        return ERROR; // 地址错误
    // 判断缓冲区是否充足
    if(L.length >= L.listsize)
    {   // 缓存区长度不够，扩大容量，让缓冲区增加 LIST_INCREMENT
        char *buf = (char*) realloc(L.elem, (L.listsize + LIST_INCREMENT) * sizeof(char));
        if(!buf) return OVERFLOW;
        // 重置缓冲区指针
        L.elem = buf;
        // 重置缓冲区大小
        L.listsize += LIST_INCREMENT;
    }
    // pos 指向下标为 i 的元素
    char *pos = &(L.elem[i]);
    // p 从最后一个数据元素 L.elem[L.length - 1] 开始，依次递减，直到下标为 i 的元素
    for(char *p = &(L.elem[L.length - 1]); p >= pos; p--)
        *(p + 1) = *p;  // 将当前元素向后移动一个位置
    *pos = e;     // 将新增元素放在 pos 所指位置
    L.length++;   // 元素个数加 1
    return OK;
}

5> 删除

将顺序表中指定位置的元素删除。

顺序表删除图示

顺序表删除

C 语言实现

// 删除表中元素
// 前提：表 L 存在且非空，0 <= i <= ListLength(L) - 1
// 结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1
int ListDelete(SeqList &L, int i, char &e)
{
    // 判断删除位置是否合法
    if(i < 0 || i >= L.length)  return ERROR;
    // p 指向下标为 i 的元素
    char *p = &L.elem[i];
    // 将下标为 i 的元素放入 e 以便返回
    e = *p;
    // 从 p + 1 开始，到 L.elem[L.length - 1]，将每个元素向前移动一个位置
    for(p++; p < L.elem + L.length; p++)
        *(p - 1) = *p;
    L.length--; // 元素个数减 1

    return OK;
}

6> 随机访问

获取线性表中指定位置 i (0 <= i <= L.length - 1) 的元素值。

C 语言实现

// 前提：表 L 存在，且 0 <= i <= ListLength(L) - 1
// 结果：用 e 返回 L 中第 i 个数据元素，
// 如果失败，返回 ERROR；否则，返回 OK
int GetElem(SeqList &L, int i, char *e)
{   // 判断位置是否合法
    if(i < 0 || i >= L.length)
        return ERROR;
    // 将下标为 i 的元素放入 e 以便返回
    *e = L.elem[i];
    return OK;
}

3. 总结

1. 顺序表随机访问时，效率比较高，直接就可以访问到，时间为：O(1)
2. 顺序表插入和删除时，为了保持顺序结构，需要移动大量的元素，因此效率很差，时间复杂度为：O(n)