Linear List

线性表综述

线性表：n个数据元素的有限序列

• 元素个数n定义为线性表长度，n=0时称为空表
• 非空表中每个元素都有确定的位置

顺序存储结构

顺序存储结构/映像：使用一组地址连续的存储单元依次存储数据 元素

• 具体参见algorithm/data_structure_intro

顺序表

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

typedef struct{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

• 以元素在计算机内物理位置相邻表示线性表中数据元素之间 的逻辑关系

• 每个数据元素存储位置和线性表起始位置，相差和其在线性表中 位序成正比常数，所以顺序表时一种随机存取存储结构

  • 高级程序语言中数组类型也有随机存取特点，因此通常 用数组描述

时间效率

• 插入/删除：$O(n)$
  • 主要时间耗费在移动元素上
• 求表长：$O(1)$
• 取第n个元素：$O(1)$

链式存储结构

链式/非顺序存储结构/映像：用一组任意存储单元存储线性表 中数据元素，还需存储一个指示其直接后继的信息

• 具体参见algorithm/data_structure_intro

（线性/单）链表

线性链表：n个节点链接而成

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}LNode, *LinkList;

• 链表中每个节点只包含一个指针域
  • 数据元素之间的逻辑关系由节点中指针指示，即指针为数据 元素之间的逻辑关系映像
• 整个链表存取必须从头指针开始
• 单链表中任何两个元素存储位置之间没有固定联系，是非随机 存取存储结构

• 头指针：指示链表中第一个节点的存储位置
• 头节点：在单链表第一个节点之前附设的节点，其数据域可以 不存储信息，也可以存储线性表长度、尾指针等附加信息

时间效率

• 插入、删除：$O(n)$
  • 已知插入、删除元素确切位置的情况下，仅需修改指针， 而不需要移动元素
• 取第n个元素：$O(n)$
  • 访问时间依赖元素在列表中位置

说明

• 在很多场合下，链表是线性表的首选结构

  • 链表不需要事先分配任何存储空间，空间利用合理
  • 插入、删除效率高，只需要重连相关指针

• 但是存在一些实现问题

  • 求线性表长不如顺序存储结构

• 链表中结点关系使用指针表示，数据元素在线性表中“位序” 概念淡化，被“位置”代替

因此重新定义带头结点的线性链表

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}*Link, * Position;
typedef struct {
	Link head, tail;
	int len;
}

单链表注意事项

• 头结点/头指针：处理链表非常方便的技巧

  • 头指针指向链表首个结点：便于调整首个节点位置时，仍然 记住链表
  • 头指针不包含链表信息，本质不属于链表：有些情况下方便 统一代码，不需要特殊考虑链表首个节点

• 对链表进行可能改变链表的遍历操作：一般使用两个标记 结点/指针

  • 头结点/指针lstart：记住链表
  • 遍历标记指针cur：标记处理结点

• 交换节点：标记指针需要指向当前处理节点的前一个结点

  • 单链表中只有指向下个节点的指针，若标记指针指向当前 节点，则无法方便将链表同当前节点断开、重连
  • 注意待交换两个节点为同一节点的情况：不同于值交换 ，这种情况可能导致链表错误连接成环

• 无指针、纯引用对象语言（python）中：只能使用节点对象 遍历链表

  • 变量为链表中节点引用：使用类似普通指针，需要注意 别修改引用节点数据
  • 变量为额外节点引用：内存类似普通指针，使用时注意 解析引用次数

静态链表

静态链表：使用数组描述的链表

typedef struct{
	ElemType data;
	int cur;
}component, SLinkList[MAXSIZE];

• 数组分量表示节点
• 使用游标cur作为指针域指示节点在链表中的逻辑位置
• 第0个分量表示头节点，其指针域cur指向链表第一个节点

• 方便在无指针高级语言中使用链式结构
• 为确定未使用的数组分量，可以将未被使用的、删除的分量用 游标链成备用边表

Circular Linked List

循环链表：表中最后一个节点指针域指向头节点，整个链表形成环

• 循环链表和线性链表操作基本一致
  • 仅循环条件不再是指针域为空，而是是否等于头指针

Double Linked List

双向链表：链表中有两个指针域，分别指向直接后继、直接前驱

typedef struct DuLNode{
	ElemType data;
	Struct DulNode * prior;
	Struct DulNode * next;
}DuLNode, * DuLinkList;

• 双向链表克服线性链表寻找直接前驱时间$O(n)$的缺点
• 双向链表大部分操作和线性链表相同，指示有些操作需要同时 修改两个指针

• 字符串：数组实现的一种数据结构
  • 字符串常见操作不同于其他数组
    • 计算字符串长度
    • 按照字典序确定字符串排序时位置
    • 连接字符串构