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

线性表的链式表示和实现

链式存储的表示

• 链式存储结构
  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
• 线性表的链式表示又称为非顺序映像或链式映像。
  • 用一组物理位置任意的存储单元来存放线性表的数据元素。
  • 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
  • 链表中元素的逻辑次序和物理次序不一定相同。
• 与链式存储有关的术语
  • 结点：数据元素的存储映像，由数据域和指针域两部分组成 [数据域 | 指针域]。
  • 链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
  • 单链表、双链表、循环链表:
    • 结点只有一个指针域的链表，称为单链表或线性链表。
    • 结点有两个指针域的链表，称为双链表。
    • 首尾相接的链表称为循环链表。
  • 头指针、头结点和首元结点:
    • Head -> Info -> a1 -> a2 -> ... -> an -> null
    • 头指针：是指向链表中第一个结点的指针。
    • 首元结点：是指链表中存储第一个数据元素 a1 的结点。
    • 头结点：是在链表的首元结点之前附设的一个结点。
• 问题讨论
  1. 如何表示空表？
     • 无头结点时，头指针为空时表示空表。
     • 有头结点时，当头结点的指针域为空时表示空表。
  2. 在链表中设置头结点的好处？
     • 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理。
     • 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
  3. 头结点的数据域内装的是什么？
     • 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
• 链表 (链式存储结构) 的特点
  1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
  2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
  3. 这种存取元素的方法被称为顺序存取法。

单链表

定义

每个结点只有一个指针域。

struct Lnode {
    ElemType data; // 结点的数据域
    Lnode *next;   // 结点的指针域
};
typedef Lnode *LinkList; // LinkList 为指向结构体 Lnode 的指针类型

算法

【2.1】基础

• 初始化