数据结构：线性表的链式表示与实现

• 算法步骤：生成新结点作头结点，用头指针 L 指向头结点；将头结点的指针域置空。

bool InitList(LinkList &L) {
    L = new Lnode;       // 堆区开辟一个头结点
    L->next = nullptr;   // 空表，也就是说头结点的指针指向为空
    return true;
}
// LinkList &L 等价于 Lnode *&L，是一个指向指针的引用

【2.2】取值

取单链表中第 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 个结点。

bool GetElem(const LinkList &L, const int &i, ElemType &e) {
    if (i < 0) {
        cerr << "out of range" << endl;
        return false;
    }
    Lnode *p = L->next;
    for (int j = 1; j <= i; ++j) {
        if (!p) {
            cerr << "out of range" << endl;
            return false; // 如果此时 p 为空，意味着已经到达链表尾端，停止循环
        }
        p = p->next;
    }
    e = p->data;
    return true;
}

【2.3】查找

按值查找：获取该数据所在位置 (地址) 或序号。

• 算法思路：从第一个元素开始依次比对，直到找到相同元素。
• 算法步骤：
  1. 从第一个结点起，依次和 e 相比较。
  2. 如果找到一个其值与 e 相等的数据元素，则返回其在链表中的地址/序号。
  3. 如果查遍整个链表都没有找到其值和 e 相等的元素，则返回 0 或 "NULL"。

size_t LocateElem(LinkList &L, ElemType &e) {
    Lnode *p = L->next;
    size_t cnt = 1;
    while (p) {
        if (p->data == e) {
            return cnt;
        }
        ++cnt;
        p = p->next;
    }
    cerr << "not found" << endl;
    return 0;
}
// 算法的时间复杂度为 O(n)

【2.4】插入

在第 i 个结点前插入值为 e 的新结点。

• 算法步骤：
  1. 首先找到 ai-1 的存储位置 p。
  2. 生成一个数据域为 e 的新结点 s。
  3. 插入新结点：
     • 新结点的指针域指向结点 ai：s->next = p->next;
     • 结点 ai-1 的指针域指向新结点：p->next = s;
  4. 思考：步骤一和步骤二能互换吗？思路可行，但直接换步骤会丢失 ai 的地址。

bool InsertList(LinkList &L, const int &i, const ElemType &e) {
    Lnode *p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }
    // 异常判断
    if (!p || i < 0) {
        cerr << "out of range" << endl;
        return false;
    }
    Lnode *newNode = new Lnode;
    newNode->data = e;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}
// 算法的时间复杂度为 O(n)

【2.5】删除

删除第 i 个结点。

• 算法步骤：
  1. 首先找到 ai-1 的存储位置 p，保存要删除的 a 的值。
  2. 令 p->next 指向 ai+1：p->next = p->next->next;
  3. 释放结点 a 的空间。

bool EraseList(LinkList &L, const int &i) {
    Lnode *p = L;
    int j = 0;
    while (p->next && j < i - 1) {
        p = p->next;
        ++j;
    }
    // 寻找第 i 个结点，并令 p 指向其前驱
    if (!(p->next) || i < 0) {
        cerr << "out of range" << endl;
        return false;
    }
    Lnode *q = p->next;
    p->next = p->next->next;
    delete q;
    return true;
}
// 算法的时间复杂度为 O(n)

【2.6】单链表的建立

1. 尾插法（元素插入在链表尾部，也叫后插法）

   void CreatListTail(LinkList &L, const size_t n) {
       Lnode *r = L;
       for (int i = 0; i < n; ++i) {
           Lnode *p = new Lnode;
           cin >> p->data;
           p->next = r->next;
           r->next = p;
           r = r->next;
       }
   }
   

2. 头插法（元素插入在链表头部，也叫前插法）

   void CreatListHead(LinkList &L, const size_t n) {
       for (int i = 0; i < n; ++i) {
           Lnode *p = new Lnode;
           cin >> p->data;
           p->next = L->next;
           L->next = p;
       }
   }
   

双向链表

定义

• 为什么要讨论双向链表：
  • 单链表的结点有指示后继的指针域，找后继结点方便 (O(1))。
  • 无指示前驱的指针域，找前驱结点难 (O(n))。
  • 可用双向链表来克服单链表的这种缺点。
• 双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域 prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。
  • 结构：[prior | data | next]
• 双向链表结构的对称性：
  • 设指针 p 指向某一结点。
  • p->prior->next = p = p->next->prior
  • 在双向链表中有些操作，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。
  • 但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为 O(n)。

typedef struct DuLnode {
    ElemType data;
    DuLnode *prior, *next;
} * DuLinkList;

算法

【3.1】插入

把 x 插入 a 和 b 中：a 的后继指向 x，b 的前驱指向 x，x 的前驱是 a，x 的后继是 b。

bool ListInsert_DuL(DuLinkList &L, const int i, const ElemType &e) {
    // 移动指针到 i 处
    DuLnode *p = L->next;
    int j = 1;
    while (p->next && j < i) {
        ++j;
        p = p->next;
    }
    if (j < i || j < 1) // 如果 i 在链表范围内，上面的 while 循环的终止条件就是 j<i
    {
        cerr << "out of range" << endl;
        return false;
    }
    // 在堆区创建要插入的结点
    DuLnode *s = new DuLnode;
    s->data = e;
    // 重新建立链接关系
    s->prior = p->prior;          // 第一步：s 的前趋等于 p 的前趋
    p->prior->next = s;           // 第二步，用 p 的前趋结点的 next 指向插入元素 s
    s->next = p;                  // 第三步：s 的后继指向 p
    p->prior = s;                 // 第四步：p 的前趋改为指向 s
    return true;
}

【3.2】删除

删掉第 i 个结点。

bool ListErase_DuL(DuLinkList &L, const int i) {
    DuLnode *p = L->next;
    int j = 1;
    while (p->next && j < i) // 移动到第 i 个元素的位置
    {
        ++j;
        p = p->next;
    }
    if (j < i || j < 1) {
        cerr << "out of range" << endl;
        return false;
    }
    // 改变链接关系
    p->prior->next = p->next; // p 的前趋结点的 next 等于 p 的后继
    if (p->next)              // 如果删除的不是最后一个元素
    {
        p->next->prior = p->prior;
    }
    delete p; // 释放空间
    return true;
}

循环链表

定义

• 是一种头尾相接的链表。
• 即：表中最后一个结点的指针域指向头结点，整个链表形成一个环。
• 优点：从表中任一结点出发均可找到表中其他结点。
• 注意：由于循环链表中没有 NULL 指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p 或 p->next 是否为空，而是判断它们是否等于头指针。
• 表示方法：
  • 头指针表示：找 a1 的时间复杂度 O(1)，找 an 的时间复杂度 O(n)。不方便。
  • 尾指针表示：a1 的储存位置 R->next->next，an 的储存位置 R。时间复杂度 O(1)。表的操作常常是在表的首尾位置上进行。
• 双向循环链表：和单链的循环表类似，双向链表也可以有循环表。让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。

// 单循环链表
p != L; 
p->next != L;

// 单链表
p != nullptr; 
p->next != nullptr;

实现

带尾指针循环链表的合并 (将 Tb 合并在 Ta 之后)。

• 分析：
  • p 存表头结点 p = Ta->next;
  • Tb 表头接到 Ta 表尾 Ta->next=Tb->next->next;
  • 释放 Tb 表头结点 delete Tb->next;
  • 修改指针 Tb->next=p;

LinkList Connect(LinkList Ta, LinkList Tb) {
    Lnode *p = Ta->next;
    Ta->next = Tb->next->next;
    delete Tb->next;
    Tb->next = p;
    return Tb;
}

单链表、循环链表和双向链表的时间效率比较

顺序表和链表的比较

• 链式存储结构的优点：
  • 结点空间可以动态申请和释放。
  • 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
• 链式存储结构的缺点：
  • 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
  • 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。

存储密度

存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即：

存储密度 = 结点数据本身占用的空间 / 结点占用的空间总量

例如：|a1|*p|，数据域 8 个字节，指针域 4 个字节，存储密度=8/12=67%。

• 一般地，存储密度越大，存储空间的利用率就越高。
• 显然，顺序表的存储密度为 1 (100%)，而链表的存储密度小于 1。

不同情况的比较