第二章 线性表

逻辑特征：

• 若至少含有一个元素，则只有唯一的起始元素；

• 若至少含有一个元素，则只有唯一的尾元素；

• 其他元素有且仅有一个前驱元素和后继元素

线性表的基本运算：

• 初始化链表

• 销毁链表

• 求线性表的长度

• 求线性表的第i个元素

• 按值查找链表中的元素

• 插入元素在链表中的第i个位置

• 删除元素

• 输出线性表中的元素值

线性表抽象数据类型List：

线性链表：

• data：数据域

• next：指针域或链域

• 每个数据元素由节电（Node）构成

• 线性结构：

• 带头节点和不带头节点两种类型
• 带头节点的单链表能够简化运算的实现过程

• 首先定一个链表

• 初始化单链表算法（添加一个头节点）

• 销毁一个链表

• 在带头节点的单链表线性表的第i个元素之前插入元素

• 计算链表的长度

• 寻找链表中元素的位置

• 删除链表中的第k个元素

• main函数就是对上面函数的调用
• ⚠️在函数内部不能InitList，这样会导致程序出错
• 需要在主函数内部创建一个新链表再进行操作

循环链表

• 在循环链表中往往含有头结点 dummy node

• 循环链表的判断是否为空：
• 只要知道循环链表中某一个节点的位置，就可以搜索到所有其他节点的位置
• 搜寻链表的过程中
• 差别之处在于检测到尾节点的指针，其指针指向头节点

• 循环链表的初始化

• 计算循环链表的长度

• 有一个非递减有序的循环单链表L，设计一个算法删除其中所有值为x的结点，并分析算法的时间复杂度
首先由于链表是非递减有序的，因此所有值为x的节点必定相邻
关键点：快慢指针

• 编写一个程序求解约瑟夫（Joseph）问题。有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，数到第m个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，…，如此反复直到所有的小孩全部出列为止，求整个出列序列。(经典的约瑟夫环问题）
• 其中创建初始链表的时候是一个十分容易错的地方
• 在 CreatList 函数中，如果试图通过传递指针 ChildNode L 来修改指针的指向，但是在C语言中，参数传递是按值传递的，所以函数内部的修改不会影响到外部的指针。这会导致在 Jose 函数中使用了一个未初始化的指针，可能导致 segmentation fault。

双向链表和双向循环链表

1. 定义：双向链表是指在前趋和后继方向都能遍历的线性链表。双向链表每个结点的结构为：

2. 使用两个指针来表示节点之间的逻辑关系（prior和next）

3. 节点的固有属性👆
4. 与单链表一样，双向链表也分为非循环双向链表（简称为双向链表）和双向循环链表两种。本章默认会是带有一个头节点的双向链表
• 双向链表的插入
• 双向链表的删除节点
关键点都在于找到第（i-1）个位置