第二章 线性表

Posted on Edited on In Views:

线性表

线性表的定义

  • 线性表示具有相同数据类型的 n（n >= 0)个数据元素的有限序列，其中 n 为表长，当 n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为 L = (a1, a2, ai, ai+1, an)。每个数据元素所占空间一样大。
    • 有次序。
    • 有限（所有整数按递增次序排列不是一个线性表）。
    • ai 是线性表中的“第 i 个”元素线性表的位序。
    • a1 是表头元素；an 是表尾元素
    • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的基本操作

  • InitList(&L)：初始化表。构造一个空的线性表 L，分配内存空间。
  • Destroy(&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。
  • LinstInsert(&L, i, e)：插入操作。在表L中的第 i 个位置上插入指定元素e。
  • ListDelete(&L, i, &e)：删除操作。删除表 L 中的第 i 个位置的元素，并用 e 返回删除元素的值。
  • LocateElem(L, i)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
  • GetElem(L, i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。
  • Length(L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
  • PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
  • Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。

顺序表

顺序表的定义

  • 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的实现

  • 静态分配

    1
    2
    3
    4
    5
    #define MaxSize 10
    typedef struct {
        ElemType data[MaxSize];
        int length;
    }SqList;

  • 动态分配

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #define InitSize 10
    typedef struct {
        ElemType* data;
        int MaxSize;
        int lengeh;
    }SeqList;

    //增加动态数组的长度
    void IncreaseSize(SeqList& L, int len) {
        int* p = L.data;
        L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
        for(int i = 0; i < L.length; i++) {
            L.data[i] = p[i];
    	}
        L.MaxSize = L.MaxSize + len;
        free(p);
    }

  • 顺序表的特点

    • 随机访问，即可以在 O(1) 时间内找到第i个元素。
    • 存储密度高，每个结点只存储数据元素。
    • 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）。
    • 插入、删除操作不方便，需要移动大量元素。

顺序表的插入和删除

  • 插入操作。在表 L 中的第 i 个位置上插入指定元素e。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool LinstInsert(SqList& L, int i, int e) {
        if(i < 1 || i > L.length + 1)
            return false;
        if(L.length >= MaxSize)
            return false;
        for(int j = L.length; j >= i; j--) {
            L.data[j] = L.data[j - 1];
        }
        L.data[i - 1] = e;
        L.length++;
        return true;
    }

    最好时间复杂度：O(1)

    最坏时间复杂度：O(n)

    平均时间复杂度：O(n)

  • 删除操作。删除表 L 第 i 个位置的元素，并用 e 返回删除元素的值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool ListDelete(SqList& L, int i, int& e) {
        if(i < 1 || i > L.length)
            return false;
        e = L.data[i - 1];
        for(int j = i; j < L.length; j++) {
            L.data[j - 1] = L.data[j];
            L.length--;
            return true;
        }
    }

    最好时间复杂度：O(1)

    最坏时间复杂度：O(n)

    平均时间复杂度：O(n)

顺序表的查找

  • 按位查找操作。获取表 L 中第 i 个位置的元素的值。

    1
    2
    3
    ElemType GetElem(SqList L, int i) {
        return L.data[i - 1];
    }

    时间复杂度：O(1)

  • 按值查找操作。在表 L 中查找具有给定关键字值的元素。

    1
    2
    3
    4
    5
    6
    int LocateElem(SeqList L, ElemType e) {
        for(int i = 0; i < L.length; i++)
            if(L.data[i] == e)
                return i + 1;
        return 0;
    }

    最好时间复杂度：O(1)

    最坏时间复杂度：O(n)

    平均时间复杂度：O(n)

单链表

单链表的定义

  • 顺序表：每个结点中只存放数据元素。

    • 优点：可随机存取，存储密度高。
    • 缺点：要求大片连续空间，改变容量不方便。

  • 单链表：每个结点除了存放数据元素外，还要存储指向下一个结点的指针。

    • 优点：不要求大片连续空间，改变容量方便。
    • 缺点：不可随机存取，要耗费一定空间存放指针。

  • 结构体定义

    1
    2
    3
    4
    typedef struct LNode {
        ElemType data;
        struct LNode* next;
    }LNode, * LinkList;

    强调这是一个单链表：使用LinkList

    强调这是一个结点：使用LNode*

  • 不带头结点的单链表

    1
    2
    3
    4
    bool InitList(LinkList& L) {
        L = NULL;// 空表，暂时还没有任何结点（防止脏数据）
        return true;
    }

  • 带头结点的单链表

    1
    2
    3
    4
    5
    6
    7
    bool InitList(LinkList& L) {
        L = (LNode*)malloc(sizeof(LNode));
        if(L == NULL)
            return false;
        L->next = NULL;
        return true;
    }

    头结点不存储数据。

单链表的插入

  • 插入操作。在表L中的第i个位置上插入指定元素e。

    • 带头结点：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    bool ListInsert(LinkList& L, int i, ElemType e) {
        if(i < 1)
            return false;
        LNode* p;
        int j = 0;
        p = L;
        while(p != NULL && j < i-1) {
            p = p->next;
            j++;
    	}
        if(p == NULL)
            return false;
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;//此句和下一句不能颠倒
        p->next = s;
        return true;
    }

    最好时间复杂度：O(1)

    最坏时间复杂度：O(n)

    平均时间复杂度：O(n)

    • 不带头结点：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    bool ListInsert(LinkList& L, int i, ElemType e) {
        if(i < 1)
            return false;
        if(i == 1) {
            LNode* s = (LNode*)malloc(sizeof(LNode));
            s->data = e;
            s->next = L;
            L = s;
            return true;
        }
        LNode* p;
        int j = 1;
        p = L;
        while(p != NULL && j < i-1) {
            p = p->next;
            j++;
    	}
        if(p == NULL)
            return false;
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }

  • 后插操作。在 p 结点之后插入元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    bool InsertNextNode(LNode* p, ElemType e) {
        if(p == NULL)
            return false;
        LNode* s = (LNode*)malloc(sizeof(LNode));
        if(s == NULL)// 某些情况下内存分配失败（如内存不足）
            return false;
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }

  • 前插操作。在 p 结点之前插入元素 e。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool InsertPriorNode(LNode* p, ElemType e) {
        if(p == NULL)
            return false;
        LNode* s = (LNode*)malloc(sizeof(LNode));
        if(s == NULL)
            return false;
        s->next = p->next;
        p->next = s;//新节点s连到p之后
        s->data = p->data;//将p中元素复制到s中
        p->data = e;//p中元素覆盖为e
        return true;
    }

    时间复杂度：O(1)

单链表的删除

  • 删除操作。删除表中第 i 个位置的元素，并用 e 返回删除元素的值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    bool ListDelete(LinkList& L, int i, ElemType& e) {
        if(i < 1)
            return false;
        LNode* p;
        int j = 0;
        p = L;
        while(p != NULL && j < i-1) {
            p = p->next;
            j++;
    	}
        if(p == NULL)
            return false;
        LNode* q = p->next;
        e = q->data;
        p->next = q->next;
        free(q);
        return true;
    }

    最好时间复杂度：O(1)

    最坏时间复杂度：O(n)

    平均时间复杂度：O(n)

  • 删除指定结点p。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool DeleteNode(LNode* p) {
        if(p == NULL)
            return false;
        LNode* q = p->next;
        p->data = p->next->data;
        p->next = q->next;
        free(q);
        return true;
    }

    注意：不满足p是最后一个结点的情况。若需要删除最后一个结点，只能从表头依次寻找p的前驱。

单链表的查找

  • 按位查找，返回第i个元素（带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    LNode* GetElem(LinkList L, int i) {
        if(i < 0)
            return NULL;
        LNode* p;
        int j = 0;
        p = L;
        while(p != NULL && j < i) {
            p = p->next;
            j++;
    	}
        return p;
    }

    平均时间复杂度：O(n)

  • 封装（基本操作）的好处：避免重复代码，简洁、易维护。

  • 按值查找，找到数据域 == e的结点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
      LNode* LocateElem(LinkList L, ElemType e) {
          LNode* p = L->next;
          while(p != NULL && p->data != e)
              p = p->next;
          return p;
      }

    - 求表的长度。

      ```c
      int Length(LinkList L) {
          int len = 0;
          while(p->next != NULL) {
              p = p->next;
              len++;
      	}
      }

    时间复杂度：O(1)

单链表的建立

  • 尾插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    LinkList List_TailInsert(LinkList& L) {
        int x;
        L = (LinkList)malloc(sizeof(LNode));
        LNode* s,* r = L;
        scanf("%d", &x);
        while(x != 9999) {//输入9999表示结束
            s = (LNode*)malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d", &x);
        }
        r->next = NULL;
        return L;
    }

    注意：设置一个指向表尾结点的指针。

  • 头插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
      LinkList List_HeadInsert(LinkList& L) {
          LNode *s;
          int x;
          L = (LinkList)malloc(sizeof(LNode));
          L->next = NULL;
          scanf("%d", &x);
          while(x != 9999) {//输入9999表示结束
              s = (LNode *)malloc(sizeof(LNode));
              s->data = x;
              s->next = L->next;
              L->next = s;
              scanf("%d", &x);
          }
          return L;
      }

    # 双链表

    - 单链表：无法逆向检索，有时候不太方便。

    - 双链表：可双向检索，存储密度略低于单链表。

    - ```c
      typedef struct DNode {
          ElemType data;
          struct DNode* prior, * next;
      }DNode, * DLinkList;

  • 双链表的初始化（带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    bool InitDLinkList(DLinklist& L) {
        L = (DNode*)malloc(sizeof(DNode));
        if(L == NULL)//内存不足，分配失败
            return false;
        L->prior = NULL;
        L->next = NULL;
        return true;
    }

  • 双链表的插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool InsertNextDNode(DNode* p, DNode* s) {
        if(p == NULL || s == NULL)
            return false;
        s->next = p->next;//将s结点插入到p结点之后
        if(p->next != NULL)
        	p->next->prior = s;
        s->prior = p;
        p->next = s;
    }

  • 双链表的删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool DeleteNextDNode(DNode* p) {//删除p结点的后继结点q
        if(p == NULL)
            return false;
        DNode* q = p->next;
        if(q == NULL)
            return false;
        p->next = q->next;
        if(q->next != NULL)
            q->next->prior = p;
        free(q);
        return true;
    }

  • 双链表的遍历

    • 后向遍历
    1
    2
    3
    4
    while(p != NULL) {
        //对结点p做相应处理
        p = p->next;
    }
    • 前向遍历
    1
    2
    3
    4
    while(p != NULL) {
        //对结点p做相应处理
        p = p->prior;
    }
    • 前向遍历（跳过头结点）
    1
    2
    3
    4
    while(p->prior != NULL) {
        //对结点p做相应处理
        p = p->prior;
    }

  • 双链表不可随机存取，按位查找、按值查找操作都只能用遍历方法实现。时间复杂度O(n)

循环链表

  • 单链表：从一个结点出发只能找到后续的各个结点。

  • 循环单链表：从一个结点出发可以找到其他任何一个结点。

  • 初始化循环单链表

    1
    2
    3
    4
    5
    6
    7
    bool InitList(LinkList& L) {
        L = (LNode*)malloc(sizeof(LNode));
        if(L == NULL)//内存不足，分配失败
            return false;
        L->next = L;//头结点next指向头结点
        return true;
    }

  • 在循环单链表中如果需要经常对表头/表尾结点操作，可将表头/表尾设为头结点。

  • 初始化循环双链表

    1
    2
    3
    4
    5
    6
    7
    8
    bool InitDLinkList(DLinklist& L) {
        L = (DNode*)malloc(sizeof(DNode));
        if(L == NULL)
            return false;
        L->prior = L;
        L->next = L;
        return true;
    }

  • 循环双链表的插入

    1
    2
    3
    4
    5
    6
    bool InsertNextDNode(DNode* p, DNode* s) {
        s->next = p->next;//将s结点插入到p结点之后
        p->next->prior = s;
        s->prior = p;
        p->next = s;
    }

  • 循环双链表的删除

    1
    2
    3
    4
    5
    6
    7
    bool DeleteNextDNode(DNode* p) {//删除p结点的后继结点q
        DNode* q = p->next;
        p->next = q->next;
        q->next->prior = p;
        free(q);
        return true;
    }

静态链表

  • 定义：分配一整片连续的内存空间，各个结点集中安置（用数组方式实现的链表）。

    • 与数组不同之处：数组各个元素是按照数据下标0至n依次排序的。而在每个结点包含数据元素和下一个结点的数组下标（游标）两个信息，因而静态链表不一定依次排序。
    • 每个数据元素4B，每个游标4B（每个结点8B），设起始地址为addr（不是e0地址），则e1的存放地址为addr + 8*2。

  • 结构体定义

    1
    2
    3
    4
    5
    #define MaxSize 10
    struct Node {
        ElemType data;
        int next;//下一个数据下标
    }
    1
    2
    3
    4
    5
    #define MaxSize 10
    typedef struct {
        ElemType data;
        int next;
    }SLinkList[MaxSize]
    • SLinkList a可用 SLinkList 定义“一个长度为 MaxSize 的 Node 型数组”

  • 初始化静态链表：

    • 把 a[0] 的 next 设为-1。
    • 把其他结点的 next 设为一个特殊的值来表示空闲，如-2。

  • 查找：从头结点出发依次往后遍历结点。

  • 插入位序为i的结点：

    1. 找到一个空的结点，存入数据元素。
    2. 从头结点出发找到位序为 i-1 的结点。
    3. 修改新结点的 next。
    4. 修改 i-1 号结点的 next。

  • 删除某个结点：

    1. 从头结点出发找到前驱结点。
    2. 修改前驱结点的游标。
    3. 被删除结点的 next 设为-2。

  • 静态链表的优点：增删操作不需要大量移动元素

  • 静态链表的缺点：

    • 不能随机存取，只能从头结点开始依次往后查找。
    • 容量固定不可变。

顺序表和链表的比较

逻辑结构

  • 都属于线性表，都是线性结构。

存储结构

  • 顺序表：
    • 优点：支持随机存取、存储密度高。
    • 缺点：大片连续空间分配不方便，改变容量不方便。
  • 链表：
    • 优点：离散的小空间分配方便，改变容量方便。
    • 缺点：不可随机存取，存储密度低。

基本操作

  • 初始化：
    • 顺序表：需要预分配大片连续空间。若分配内存过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。
      • 静态分配：静态数组：容量不可改变。
      • 动态分配：动态数组（malloc、free）：容量可以改变，但需要移动大量元素，时间代价高。
    • 链表：只需分配一个头结点（也可以不要头结点，只声明一个头指针），以后方便拓展。
  • 销毁：
    • 顺序表：修改length=0。
      • 静态分配（静态数组）：系统自动回收空间。
      • 动态分配（动态数组：malloc、free）：需要手动 free。
    • 链表：依次删除各个结点（free）。
  • 插入删除：
    • 顺序表：需要将后续元素后移/前移。
      • 时间复杂度：O(n)。时间开销主要来自于移动元素。若数据元素很大，则移动的时间代价很高。
    • 链表：只需要修改指针。
      • 时间复杂度：O(n)。时间开销主要来自于查找元素。查找元素的时间代价更低。
  • 查找：
    • 顺序表：
      • 按位查找：O(1)
      • 按值查找：O(n)。若表内元素有序，则可在O(log2n)时间内找到。
    • 链表：
      • 按位查找：O(n)
      • 按值查找：O(n)
  • 表长难以预估、经常要增加/删除元素：链表。
  • 表长可预估、查询（搜索）操作较多：顺序表。