线性表

0x01：线性表的逻辑结构

一、线性结构的定义

若结构是非空有限集，有且仅有一个开始结点和一个终端结点。并且所有结点都最多只有一个直接前驱和一个直接后继；即线性结构的数据元素之间存在一对一的线性关系。

将 L 记为线性表，则可以表示为：

$$ L=(a_1,a_2,....,a_i,a_{i+1},.....,a_n) $$

二、线性结构的基本特征

线性结构是一个或多个数据元素的有序（次序）集

  1. 集合中必存在唯一的一个“第一元素”
  2. 集合中必存在唯一的一个“最后元素”
  3. 除最后元素在外，均有唯一的后继
  4. 除第一个元素之外，均有唯一前驱

简单来说，线性表就是一种简单的线性结构

线性表结构

当 n=0 时，即表中不包含任何元素，则称为空表；显然，空表的长度为 0

三、线性表抽象数据类型

定义抽象数据类型

从实际编程和应用角度看，线性表是一种组织数据元素的数据结构，现在考虑如何将其定义为一种抽象数据类型。

  • 从实际编程角度上看，对于一种数据结构有俩个问题必须被考虑：

    • 如何将该结构内部的数据组织好（为它设计一种合适的表示）
    • 如何提供一套有用而且必要的操作，并有效实现这些操作
      显然，这俩个问题互相有着密切的关联
  • 从应用角度上看，线性表是一种有用的结构。需要考虑该结构提供了哪些操作，如何有效使用以解决自己的问题

综上所述，我们定义出了描述抽象数据类型的标准格式

ADT List{
    Data
        数据对象：
        D={a[i]|a[i]∈ElemSet,i=1,2,3,...,n,n≥0}
        //称n为线性表的表长；称n=0时的线性表为空表。
        数据关系：
        R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,3,...,n}
        //设线性表为{a[1],a[2],a[3],...,a[n]}，称i为a[i]在线性表中的位序。
    Operation
        基本操作：
            结构初始化操作
            结构销毁操作
            引用型操作
            加工型操作
}ADT List

结构初始化操作

  • initList(&L)

    • 作用：建立一个空的线性表L

结构销毁操作

  • destroyList(&L)

    • 初始条件：线性表 L 已存在
    • 作用：销毁线性表 L

引用型操作

  • listEmpty(L)

    • 初始条件：线性表 L 已存在
    • 作用：判断线性表是否为空表，若线性表为空，则返回True，否则返回False

  • lengthList(L)

    • 初始条件：线性表 L 已存在
    • 作用：返回线性表 L 的长度（元素个数）

  • priorElem(L, cur_e, &pre_e)

    • 初始条件：线性表 L 已存在
    • 作用：若 cur_e 是 L 的元素，但不是第一个元素，则用 pre_e 返回它的前驱，否则操作失败

  • nextElem(L, cur_e, &next_e)

    • 初始条件：线性表 L 已存在
    • 作用：若 cur_e 是 L 的元素，但不是最后一个元素，则用 next_e 返回它的后继，否则操作失败

  • getElem(L, i, &e)

    • 初始条件：线性表 L 已存在；且$ 1 \leq i \leq lengthList(L) $
    • 作用：将线性表 L 中的第 i 个位置的元素值返回给 e

  • locateElem(L, e)

    • 初始条件：线性表 L 已存在
    • 作用：在线性表 L 中查找给定值 e 相等的元素，若查找成功，则返回元素在表中序号；否则返回0

  • listTraverse(L, visit())

    • 初始条件：线性表 L 已存在；visit()为某个访问函数
    • 作用：依次对 L 中的每个元素调用函数 visit() ，一旦 visit() 失败，则操作失败

加工型操作

  • clearList(&L)

    • 初始条件：线性表 L 已存在
    • 作用：将线性表 L 清空

  • getElem(&L, i, &e)

    • 初始条件：线性表 L 已存在；且$ 1 \leq i \leq lengthList(L) $
    • 作用：获取线性表 L 中第 i 个元素的值，并赋值给 e

  • listInsert(&L, i, e)

    • 初始条件：线性表 L 已存在；且$ 1 \leq i \leq lengthList(L) +1 $
    • 作用：在线性表 L 中第 i 个位置插入新元素e

  • listDelete(&L, i, &e)

    • 初始条件：线性表 L 已存在；且$ 1 \leq i \leq lengthList(L) $
    • 作用：删除线性表 L 中第 i 个位置元素，并将该元素的值赋值给e

有序表

若线性表中的数据元素互相之间可以被比较，并且数据元素在表中依次非递减或非递增有序排列，即$ a_i \geq a_{i-1} $或者$ a_i \leq a_{i-1} (i=2,3,.....,n) $，则称该表为有序表

  • 将一组无序的记录序列调整为有序的记录序列，这种操作称之为排序

0x02：线性表的顺序存储结构

顺序存储定义

  • 线性表的顺序表示又称为顺序存储结构或顺序映象
  • 顺序存储指的是把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
  • 简而言之，就是元素在逻辑上相邻，在物理上也相邻

顺序存储方法

  • 用一组地址连续的存储单元依次存储线性表的元素，可通过数组v[n]来实现
    即以“存储位置相邻”表示有序对< ai-1,ai >

$$ Loc(a_i) = Loc(a_{a-1}) + M(一个数据元素所占存储量) $$

线性表顺序存储结构

$$ Loc(元素i) = L_0 + （i-1）\times M $$

注意：

  • 存取结构 与 存储结构 是俩个不同的概念
  • 存取结构是在一个数据结构上对查找操作的时间性能的一种描述

  • 通常有俩种存取结构：随机存取结构和顺序存取结构

    • 随机存取结构是指在一个数据结构上进行读取或写入时的时间性能是 O(1)，即查找任意一个数据元素的时间复杂度是相等的，均为常数时间，例如：线性表的顺序存储就是一种随机存取结构
    • 顺序存取结构是指在一个数据结构上进行读取或写入时的时间性能是 O(n) ，即查找一个数据元素的时间复杂度是线性的，与该元素在结构中的位置有关，例如单链表就是一种顺序存取结构

顺序表的类型定义

  • 线性表的静态分配顺序存储结构

    #define MAXSIZE 100    //最大长度
typedef struct{
    ElemType elem[MAXSIZE];
    int length;
}Sqlist;
    • 在线性表的静态分配顺序存储结构中，线性表的最多数据元素为MAXSIZE，元素数量不能随意增加，这是以数组方式描述线性表的缺点

于是为了实现线性表最大存储数据元素可随意变化，可以使用一个动态分配的数组来取代上面的固定长度数组，如下所示：

  • 线性表的动态分配顺序存储结构

    #define MAXSIZE 100 //最大长度
typedef struct{
    ElemType *elem;
    int length;
}SqList;

    例如，以图书表的顺序存储结构类型

    #define MAXSIZE 1000    //图书表可能达到的最大长度
typedef struct{
    char no[20];
    char name[50];
    float price;
}Book;                    //图书信息定义

typedef struct{
    Book *elem;
    int length;
}SqList;

  • 总结
    顺序存储结构封装需要三个属性：

    • 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置
    • 线性表的最大存储容量：数组的长度 MAXSIZE
    • 线性表的当前长度：length
      注意：这里的数组长度与线性表的当前长度需要区分一下：
    • 数组的长度是存放线性表的存储空间的总长度，一般初始化后不再改变
    • 而线性表的当前长度是线性表中的元素个数，是会改变的

顺序表基本操作的实现

  • 顺序表的初始化操作

    • 构建一个空表，由于这是一种加工型操作，因此需要将 L 设为引用参数传入函数中
    • 首先动态分配存储空间
    • 然后将 length 设置为 0，表示表中没有数据元素
    int initList(SqList &L){
    L.elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!L.elem){
        exit(OVERFLOW);         // 内存分配失败
    }
    L.length = 0;
    return OK;
}

  • 顺序表的查找操作

    • 顺序表的按值查找是指在顺序表中查找与给定值x相等的元素
    • 从第一个元素$ a_1 $起，依次与元素 x 进行比较，直到找到一个与 x 相等的数据元素，则返回它在顺序表中的下标
    • 若查遍整个顺序表都没有找到与 x 相等的元素，则返回 0
    int locateElem(SqList L, ElemType x){
    for(i=0; i<L.length; i++){
        if(L.elem[i] == x){
            return i+1;
        }
    }
    return 0;
}
    • 本操作算法的主要运算是比较，显然比较的次数与x在表中的位置有关，也与表长有关
    • 当$ a_1 = x $是，比较1次就成功了，当$ a_n = x$时，比较n次成功，按值查找的平均比较次数为$ \frac{n+1}{2} $，故时间复杂度为 O(n)

  • 顺序表的插入操作

    1. 判断插入位置 i 是否合法
    2. 判断顺序表的存储空间是否已满
    3. 将第n至第 i 位的元素依次向后移动一个位置，空出第 i 个位置
    4. 将要插入的新元素 e 放入第 i 个位置
    5. 表长加1，插入成功返回OK
      顺序表的插入操作
    Status listInsert(SqList &L, int i, ElemType e){
    if((i<1) || (i>L.length+1)){
        return ERROR;            //插入位置不合法
    }
    if(L.length >= MAXSIZE){
        return OVERFLOW;        //当前存储空间已满
    }
    for(j=L.length-1; j>=i-1; j--){
        L.elem[j+1] = L.elem[j];//插入位置及之后的元素后移
    }
    L.elem[i-1] = e;            //将元素e插入第i个位置
    ++L.length;                    //表长+1
    return OK;
}
    • 该算法时间主要耗费在移动元素的操作上
    • 若插入在尾结点之后，则根本无需移动（最优时间）
    • 若插入在首结点之前，则表中元素全部后移（最差时间）
    • 故，该算法的时间复杂度为：O(listLength(L))
    • 假设在第 i 个元素之前插入的概率为$ P_i $，则在长度为n的顺序表汇总插入一个元素所需移动元素次数的期望值为：

$$ E_{is}=\displaystyle \sum^{n+1}_{i = 1}{P_i(n-i+1)} $$

  • 若假定在顺序表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值（平均移动次数）为：

$$ E_{is}=\frac{1}{n+1}\displaystyle \sum^{n+1}_{i = 1}{(n-i+1)}=\frac{n}{2} $$

  • 顺序表的删除操作

    1. 判断删除位置 i 是否合法
    2. 删除位置 i 的元素
    3. 将位置 i 之后的元素向前移动
      顺序表的删除操作
    Status listDelete(SqList &L, int i, ElemType &e){
    if((i<1) || (i>L.length)){
        return ERROR;            // 删除位置不合法
    }
    for(j=i; j<=L.length-1; j++){
        L.elem[j-1] = L.elem[j];// 被删除元素之后的元素前移
    }
    --L.length;                    // 表长-1
    return OK;
}
    • 与插入算法一样，删除的算法时间主要耗费在移动元素的操作上
    • 若删除尾结点，则根本无需移动元素（最优时间）
    • 若删除首结点，则表中 n-1 个元素都需要向前移动（最坏时间）
    • 故，该算法的时间复杂度为：O(listLength(L))
    • 假设删除第 i 个元素的概率$ Q_i $，则在长度为 n 的顺序表中删除一个元素所需移动元素的次数的期望值为：

$$ E_{dl}=\displaystyle \sum^{n}_{i = 1}{Q_i(n-i)} $$

  • 若假定在顺序表中任何一个位置上进行删除的概率都是相等的，则移动移动元素的期望值（平均移动次数）为：

$$ E_{dl}=\frac{1}{n} \displaystyle \sum^{n}_{i = 1}{(n-i)}=\frac{n-1}{2} $$

顺序表的优缺点

  • 特点

    • 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
    • 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以初略地认为，访问每个元素所花的时间相等

  • 优点

    • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速地存取表中任意位置的元素

  • 缺点

    • 插入和删除操作需要移动大量元素
    • 当线性表长度变化较大时，难以确定存储空间的容量
    • 容易造成存储空间的“碎片”

0x03：线性表的链式存储结构

链式存储定义

在计算机中用一组地址任意的存储单元存储线性表的数据元素，用链接关系显式表示元素之间的顺序关联。基于链接技术实现的线性表称为链接表或链表

  • 什么是链表
    由数据域和指针域俩部分组成，数据元素的存储映像，称为结点

$$ 元素（数据元素的映象） + 指针（指示后继元素存储位置） = 结点（表示数据元素 \& 数据元素的映象） $$

以“结点的序列”表示的线性表，n个结点由指针链组组成的一个线性表，称为链表
它是线性表的链式存储映像，也称为线性表的链式存储结构

单链表、双链表、循环链表

  • 结点只有一个指针域的链表，称为单链表或线性链表
  • 有俩个指针域的链表，称为双链表
  • 首尾相接的链表，称为循环链表

单链表

我们把存储数据元素信息的域称为数据域，把存储直接后继位置地址的域称为指针域；指针域中存储的信息称为指针或链。由这俩部分信息（指针域 + 数据域）组成的数据元素称为存储映像（结点 & Node）

链表

对于线性表来说，总嘚有个头有个尾，链表也不例外

一般情况下，我们把线性表中第一个数据$ a_1 $的存储地址作为线性表的地址，称作链表的头结点，最后一个结点指针为空（Null）

但是，有时为了操作方便，会在第一个结点之前虚加一个“头结点”，以指向头结点的指针作为链表的头指针

虚加头结点

当头指针指向的头结点的指针域为空时，表示该链表为空表

空链表

头指针与头结点的异同

  • 头指针

    • 头指针是指链表指向第一个结点的指针。若链表有头结点，则指向头结点的指针
    • 头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）
    • 无论链表是否为空，头指针均不为空
    • 头指针是链表的必要元素

  • 头结点

    • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无实际意义（也可存放链表的长度）
    • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作就与其他结点的操作统一了
    • 头结点不一定是链表的必要元素

  • 在链表中设置头结点的好处

    1. 便于首元结点的处理
      首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理
    2. 便于空表和非空表的统一处理
      无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了

循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环链表

  • 特点：

    1. 从循环链表中的任何一个结点位置都可以找到其他所有其他结点，而单链表做不到

    2. 循环链表中没有明显的尾端，故为了避免死循环，我们对以下循环判断语句进行了修改

      p != NULL;    ---->    p != L;
p->next != NULL;    --->    p->next != L;
    3. 对循环链表，有时不给出头指针，而给出尾指针，这样可以更方便的找到第一个和最后一个结点

    循环链表尾指针

    1. 所以循环链表的开始结点为：rear->next->next，结束结点为：rear

详解见文章：循环链表

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有俩个指针分别指向直接后继和直接前驱；
双链表
所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

详解见文章：双向链表

双向循环链表

双向循环链表就是在双向链表的基础上，将链表尾结点的后继指向头结点
双向循环列表

详解见文章：双向循环链表

链表的类型定义

单链表的存储结构定义

typedef struct LNode{
    ElemType data;        //数据域
    struct LNode *next;    //指针域
}LNode, *LinkList;        //*LinkList为LNode类型的指针

// 定义一个单链表
LinkList p;        // L为单链表的头指针
LNode *p;

注意区分指针变量和结点变量俩个不同的概念

  • p结点的地址
  • *p表示一个结点

链表基本操作的实现

  • 初始化操作

    1. 生成新结点作为头结点
    2. 用头指针 L 指向头结点
    3. 头结点指针域置空
    Status initList(LinkList &L){
    L = new LNode;
    L->next = NULL;
    return OK;
}

  • 销毁操作

    Status destroyList(LinkList &L){
    LinkList p;
    while(L){
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}

  • 清空操作

    Status clearList(LinkList &L){
    LinkList p,q;
    p = L->next;        // p指向第一个结点
    while(p){
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;        // 头结点指针域置空
    return OK;
}

  • 求表长操作

    • “数”结点；指针 p 依次指向各个结点，从第一个元素开始“数”，一直“数”到最后一个结点
    int lengthList(LinkList L){
    LinkList p;
    p = L->next;
    i = 0;
    while(p){
        i++;
        p = p->next;
    }
    return i;    // 返回L中数据元素的个数
}

  • 判断表是否为空

    int listEmpty(LinkList L){
    // 若L为空表，则返回1，否则返回0
    if(L->next){
        return 0;
    }else{
        return 1;
    }
}

  • 取值操作（根据给定位置 i 获取对应位置数据元素的内容）
    链表的查找要从链表的头指针出发，顺着链表指针域 next 逐个结点往下搜索，直至搜索到第 i 个结点位置；因此，链表不是随机存取结构，而是顺序存取结构

    1. 从第1个结点(L->next)顺链扫描，用指针 p 指向当前扫描的结点，p 初值 p=L->next
    2. j 做计数器，累计当前扫描过的结点数，j 初值为 1
    3. 当 p 指向扫描到下一结点时，计数器 j 加 1
    4. 当 j = i 成立时，p 所指向的结点就是要找的第 i 个结点
    Status getElem(LinkList L, int i, ElemType &e){
    p = L->next;
    j = 1;                // 初始化计数器
    while(p && j < i){    // 向后扫描，直到p指向第i个元素或p为空
        p = p->next;
        ++j;
    }
    if(!p || j > i){
        return ERROR;    // 第i个元素不存在
    }
    e = p->data;        // 将第i个元素取出
    return OK;
}

  • 查找操作

    1. 从第一个结点开始，依次和 e 进行比较
    2. 如果在链表中找到一个值与 e 相等的数据元素，则返回其在表中的“位置"或地址
    3. 如果查遍整个链表都没有找到与 e 相等的元素，则返回 0 或 NULL
    // 姿势1：当找到值与e相等的数据元素时，返回数据元素的地址，查找失败返回NULL
LNode *locateElem(LinkList L, ElemType e){
    p = L->next;
    while(p && p->data!=e){
        p = p->next;
    }
    return p;
}

// 姿势2：当找到值与e相等的数据元素时，返回元素的位置，查找失败则返回0
int locateElem(LinkList L, ElemType e){
    p = L->next;
    j = 1;
    while(p && p->data!=e){
        p = p->next;
        j++;
    }
    if(p){
        return j;
    }else{
        return 0;
    }
}

  • 插入操作

    1. 找到$ a_{i-1} $结点将其暂存于 p
    2. 生成一个新结点 s ，并将其数据域置为 e
    3. 新结点 s 的指针域指向结点$ a_i $
    4. 修改结点 p 的指针域指向新结点 s
      链表的插入操作
    Status listInsert(LinkList &L, int i, ElemType e){
    p = L;
    j = 0;
    while(p && j < i-1){
        p = p->next;
        ++j;
    }
    if(!p || j > i-1){
        return ERROR;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

  • 删除操作

    1. 找到$ a_{i-1} $结点并将其暂存给 p
    2. 将$ a_i $结点暂存给 q
    3. 令 p->next 指向 $ a_i $结点的直接后继结点
    4. 将$ a_i $的值赋值给 e
    5. 释放$ a_i $结点
      链表的删除操作
    Status listDelete(LinkList &L, int i, ElemType &e){
    p = L;
    j = 0;
    while(p->next && j < i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next) || j > i-1){
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return OK;
}

链表的运算效率分析

  • 查找：因线性链表只能顺序存取，即在查找时需要从头指针找起，查找的时间复杂度为$ O(n) $
  • 插入和删除：因线性链表不需要移动元素，只需要修改结点指针，所以一般情况下时间复杂度为$ O(1) $
  • 但是，如果要在单链表中进行前插或者删除操作，由于要从头查找前驱结点，所以所耗时间复杂度为$ O(n) $

补充算法：

  • 单链表的建立（前插法）——栈式
    建立一个空表，重复读入数据

    1. 生成新的结点，并将数据存入其数据域中
    2. 将该结点插入到链表的前端
      链表前插法
    void createList(LinkList &L, int n){
    L = new LNode;
    L->next = NULL;            // 建立一个带头结点的单链表
    for(i=n; i>0; --i){
        p = new LNode;        // 生成新结点
        cin >> p->data;        // 输入元素值
        p->next = L->next;
        L->next = p;
    }
}

  • 单链表的建立（尾插法）——队式
    建立一个空表，重复读入数据

    1. 将尾指针 r 指向头结点
    2. 生成新的结点，并将数据存入其数据域中
    3. 将新结点插入到链表尾部（尾指针所指向结点之后）
    4. 尾指针指向新的尾部结点
      链表尾插法
    void createList(LinkList &L, int n){
    L = new LNode;
    L->next = NULL;
    r = L;                // 尾指针r指向头结点
    for(i=0; i<n; ++i){
        p = new LNode;    // 生成新结点
        cin >> p->data;    // 获取元素值
        p->next = NULL;
        r->next = p;    // 插入到表尾
        r = p;            // 尾指针r指向新的尾结点
    }
}

链表的优缺点

  • 特点

    • 线性表的链式存储结构的特点是用一组地址任意的存储单元来存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置
    • 在链式存储结构中，除了要存储数据元素信息以外，还要存储它的后继元素的存储地址（指针）；也就是说，除了存储其本身的信息外，还需存储一个指示其直接后继存储位置的信息
    • 链式存储结构在访问时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间是不相等的；这种存取元素的方法也被称为顺序存取法

  • 优点

    • 数据元素的个数可以自由扩充
    • 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

  • 缺点

    • 存储密度小
    • 存取效率不高，必须采用顺序存取法进行操作，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

0x04：顺序存储和链式存储的比较

顺序存储和链式存储的比较

Last modification：November 9th, 2020 at 11:53 am
© 允许规范转载
给狐宝打点钱⑧