数据结构 第二章 线性表 · 速览

数据结构目录阅读详版下载 Markdown

一元多项式

• 一元多项式 $f(x)=a_0x^0+\cdots+a_nx^n$；三种存储：数组存全部项 / 数组存非零项 / 链表存非零项。
• 数组存全部项：下标即指数，加法 = 对应位置系数相加；缺点：须预定义大小，高次稀疏项（如 $x+3x^{2000}$）极度浪费空间。
• 数组存非零项：用类 PolyTerm 存 (系数, 指数)，按指数有序存放（便于加法）；加法用归并：比较两表当前首项指数，大者直接取、相等则系数相加、一表取完拼接另一表剩余项；缺点仍须按最大可能（m+n 项）预分配。
• 链表存非零项：PolyNode{coefficient, exponent, next}，不需预定义空间。

线性表定义

• 线性表：同类型元素构成的有序序列；长度 = 元素个数；无元素为空表；除表尾每元素有唯一直接后继，除表头每元素有唯一直接前驱。
• ADT 操作：MakeEmpty、FindKth(按位置)、Find(按值)、Insert、Delete、Length。

数组存储（顺序存储）

• 连续空间顺序存放；LinearList{ T* data; int size; }，new 分配在堆。构造/析构 O(1)。
• 用 new T[n] 而非 T data[n]：① 变量不能作数组大小；② new 在堆、栈数组在栈。栈：自动管理、大小受限（溢出 Stack Overflow）；堆：手动 new/delete、灵活大。
• 按位置查找 O(1)（随机访问，越界返 NULL）；按值查找 O(N)（未找到返 -1）。
• 插入 O(N)：先挪后放——先把该位及其后元素向后挪一格再写入（先放会覆盖，错）；越界/满则报错。
• 删除 O(N)：把待删位之后元素依次前移一格覆盖，长度 -1。

链表存储（链式存储）

• 逻辑相邻不要求物理相邻，靠指针建立关系；Node{int data; Node* next;}、LinkedList{Node* head;}。
• 按值查找、按位置查找均 O(N)；插入、删除均 O(N)（须先定位前驱，走 pos-1 步）。
• 删除三步（易错）：temp=current->next; current->next=temp->next; delete temp;——必须先用 temp 保存待删结点，否则先改前驱指针会使待删结点失去引用、无法删除（内存泄漏）。

数组 vs 链表 复杂度（必背）

操作	数组	链表
创建	O(1)	O(1)
删除结构	O(1)	O(N)
指定位置 插入/删除	O(N)/O(N)	O(N)/O(N)
头部插入	O(N)	O(1)
尾部插入	O(1)	O(N)
按位置查找/访问元素	O(1)	O(N)
访问	随机访问	顺序访问

• 数组顺序存储（连续）→ 随机访问；链表链式存储（指针）→ 顺序访问。
• 反转链表（头插法）：begin、end 辅助指针，反复把 begin 之后结点摘下插到头结点后；就地反转。

链表变体

• 单循环链表：末结点 next 指向头结点；从任一结点出发可遍历全部。
• 不带头结点单循环链表：head 直接指首结点；典型应用约瑟夫环。
• 双向链表：每结点有 prev、next；可按元素在前/后半段决定从 head 向后或从 tail 向前查（需 length 辅助）。插入到 p 之后须先设 tmp 的 prev/next，再改相邻结点指针；插在首结点位置操作不同。
• 双向循环链表：不带头尾结点。

方法论小结

• 研究任何数据结构的四方面：逻辑结构、物理结构、基本操作实现、典型应用；操作分结构构造/属性/数据操纵/遍历/典型应用类。
• 设计完整程序的五步法：参数分析、空间检查、核心操作、对其他属性的影响、正确返回。