导图社区 数据结构
- 54
- 1
- 0
- 举报
数据结构
数据结构的思维导图，内容有线性表、栈、队列和数组、串、树与二叉树、图、查找、排序，希望这份脑图会对你有所帮助。
编辑于2023-10-18 22:51:12- 考研 计算机 408 数据结构
- 相似推荐
- 大纲
数据结构
第1章 绪论
术语
算法
对问题求解步骤的描述
数据元素
数据元素包含若干数据项
数据项
数据结构
逻辑结构
线性结构
线性表
受限线性表
队列
栈
串
线性表的推广
数组
非线性结构
集合
树
图
存储结构（物理结构）
特征
5个特性
有穷性
在有穷步内完成，每一步在有穷时间内完成
有穷：可接受范围内
注意：程序可以无穷，但算法必须有穷
确定性
含义明确，确定输入导致确定输出
可行性
可通过有限次基本运算实现
输入
>=0个输入
输出
>=1个输出
好的算法
正确
可读
健壮
速度快，所需存储空间小
复杂度
时间复杂度：T(n)
理论
影响因素
问题规模：n
输入数据的初始值
描述
问题规模：n
基本语句频度：f(n)
时间复杂度：T(n)=O(f(n))
分类
最坏时间复杂度
通常考虑最坏时间复杂度
平均时间复杂度
所有输入实例在等概率出现的情况下，算法的期望运行时间
最好时间复杂度
计算时间复杂度
计算规则
加法规则
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max{f(n),g(n)})
乘法规则
T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))
常用复杂度的比较
渐进上界
若存在正数c和n0，使得对一切n>=n0，都有0<=f(n)<=c*g(n)成立， 则称f(n)的渐进上界是g(n)，记作f(n)=O(g(n))。
大O表示法性质
传递性
f(n)=O(g(n))，g(n)=O(h(n)) ==> f(n)=O(h(n))
O(f(n))+O(f(n))=O(f(n))
即：对数阶与底数无关
数列
求和公式
计算原则
主定理
递归
公式递推法
建立 规模变小的关系
建立T(n)与T(n-1)的关系式
建立T(n)与 T(n-1)和T(n-2) 的关系式
建立T(n)与T(n/2)的关系式
确定最小规模的时间复杂度
T(1)=多少
展开找规律（常设n=2^k），解递推方程，反变换为n的表达式
计算方法
for循环
for( ; ;i++)
列举
∑计算法
for( ; ;i*=2)
列举+解出 循环停止条件对应的变量值
while循环
列举+解出 循环停止条件对应的变量值
∑计算法
参考
https://www.cnblogs.com/chenying99/p/3801293.html
2个重要算法的复杂度
斐波那契数列
递归实现
T(n)=O(2^n) S(n)=O(n)
非递归实现
T(n)=O(n) S(n)=O(1)
阶乘
递归实现
T(n)=O(n) S(n)=O(n)
非递归实现
T(n)=O(n) S(n)=O(1)
空间复杂度：S(n)
影响因素
子主题
概念
只需分析输入和程序本身之外的辅助空间
原地工作
算法所需的辅助空间=常数，即O(1)
计算（算法题必考）
第2章 线性表
分类
顺序存储
顺序表
定义
具有相同数据类型的n(n>=0)个数据元素的有限序列
线性表的顺序表示
结构体
typedef struct { ElemType data[MaxSize]; int length; }SqList;
表示
L=(a1,a2,a3,...an)
基本操作 (未说明即可直接使用)
初始化表
求长
按值查找
按序号查找
插入元素
删除元素
遍历输出
判空
销毁表
区分
线性表是逻辑结构
顺序表和链表是存储结构
特点
创建时需要预估存储空间
逻辑顺序与物理顺序相同
可以随机存取
存储密度高
除在尾部之外，插入和删除操作需要移动元素
除首元素（表头元素）外，其余元素都有一个前驱。 除尾元素（表尾元素）外，其余元素都有一个后继。
顺序表所占的存储空间 = L.length * sizeof(ElemType)
分配
静态分配
运行前指定大小分配
动态分配
运行时再指定大小分配，仍然是定长。不是变长数组，不是链表
注意
位序从1开始，下标从0开始: a1 a2 a3 ... 0 1 2 ...
元素ai的起始地址 = StartLocation(L) + (i - 1) * sizeof(ElemType)
时间复杂度
链式存储
指针实现
单链表
定义
线性表的链式存储
结构
数据域
指针域
结构体
typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList;
表示
用【头指针】来标识一个单链表
头节点
可选
作用
记录表长等数据、或不记录数据
存放第一个数据结点的地址
头节点不是数据结点
优点
方便运算的实现
统一数据结点的操作
统一空表与非空表的操作
区分：头结点≠首结点，首结点：第一个结点。
头指针（头结点指针）
标识链表
注意
通常头指针必须有，因为它标识链表。 但有时题目会取消头指针，仅用尾指针操作链表。
指向
第一个结点
链表有头节点时
头指针指向头结点
链表无头结点时
头指针指向第一个数据结点
尾指针（尾结点指针）
可选
定义
指向最后一个数据结点的指针
需要维护
在表尾插入新结点时，要更新尾指针
优点
功能
一下子定位到尾部
图示
子主题
基本操作
高级操作
双链表
定义
结点有两个指针：前驱指针，后继指针
结构体
typedef strcut DNode { ElemType data; // 数据域 struct DNode *prior或*pre; // 前驱指针 struct DNode *next; // 后继指针 }DNode, *DNodeList;
图示
子主题
循环链表
循环单链表
循环双链表
注意
区分
单链表、双链表、单循环链表、双循环链表
指针流向图
数组实现
静态链表
定义
用数组实现线性表的链式结构
结构体
typedef struct { ElemType data; // 数据域 int next; // 游标/"指针" }SLinkList[MaxSize];
数组的每个元素为结点，每个结点包含{数据域，游标/"指针"(后继元素的索引)}
尾结点的游标next=-1
注意
游标/"指针"：指向的是后继元素在数组的位置/下标/索引，而不是地址
需要预分配存储空间
插入、删除操作
只需修改指针
不需要移动元素
图示
子主题
顺序存储 vs 链式存储
对比
如何选择
链表之间对比
对比
根据某操作最高效选择结构
考虑
复杂度（优先）
同复杂度的，再考虑更新操作的开销
步骤
（1）画出相关结构的指针流向图 （2）标出有无头指针，尾指针，头结点 （3）观察或模拟操作，得到复杂度 （4）不要只看，要手动模拟一遍：明确完整的每一步步骤
注意
题目可能要求两种操作，但通常基于两种操作得出的判断不会矛盾。 如果根据一种操作就能得出最优复杂度的结构，就基本得出了答案。
根据操作写代码
注意，主要操作完成后，某些指针的更新，头结点（长度）的更新
第3章 栈、队列和数组
分类
操作受限
栈
定义
只允许在一端进行插入或删除操作的线性表
概念
栈顶
开放的一端
栈底
封闭的一端
空栈
基本操作 (未说明即可直接使用)
初始化栈
判空
进栈
出栈
出栈同时返回出栈元素的值
获得栈顶元素的值
仅读值，不出栈
销毁栈
特点
n个不同的元素进栈，出栈元素不同排列的个数为卡特兰(Catalan)数
先进后出FILO
不能读取中间的某个元素
难点
根据输入序列==>推断所有可能的输出序列
子主题
根据输出序列==>推断所有可能的输入序列
子主题
第n个输入的数据，可能的输出的位置，不可能的输出位置
子主题
第n个输出的数据，可能的输入的位置，不可能的输入位置
子主题
符合指定条件的所有输出序列
一般穷举法
判断合法出栈序列
判断不合法出栈序列
合法的出入栈操作序列
设初态和终态为空栈
入栈次数=出栈次数
若入栈：+1，出栈：-1，则任意时刻前缀≥0
分类
顺序存储
顺序栈
定义
利用一组地址连续的存储单元存放元素，附设栈顶"指针"：int top；
结构体
#define MaxSize 50 typedef struct { ElemType data[MaxSize]; int top; }SqStack;
栈顶指针
S.top
空栈时：S.top == -1 (规定不一)
基本操作
进栈
进栈前要先判断是否已满
若已满，则溢出
先S.top++，再赋值。
出栈
出栈前要先判空
(先读值，再)S.top--。
共享栈
定义
两个顺序栈共享一个一维数组空间
[--------------------------> <-----------] s1栈底 s1栈顶 s2栈顶 s2栈底
特点
两个栈的进出栈操作恰好相反
栈底不同，栈顶共享存储空间
只有整个存储空间被占满时才发生【上溢】
存取时间：O(1)
目的
更加有效地利用存储空间，两个栈的空间互相调节
判断栈满
top1 - top0 == 1
需要特别留意：判空
链栈（链式存储）
定义
采用链式存储的栈，通常用单链表实现
结构体
typedef struct Linknode { ElemType data; struct Linknode *next; }*LinkStack;
优点
便于多个栈共享存储空间
不会栈满溢出
可以带头节点，也可以不带头节点
【通常】，出入栈操作在【表头】进行
队列（队）
定义
操作受限的线性表，只允许在表的一端进行插入，只允许在表的另一端进行删除。
概念
队头（队首）
队头指针
队尾
队尾指针
空队
基本操作
初始化队列
进队（入队）
出队（离队）
判空
读队头元素的值
读队尾元素的值
不能读取中间的某个元素
特点
先进先出FIFO
分类
顺序存储
(普通)队列
定义
分配一块连续空间存储队列元素
结构体
#define MaxSize 50 typedef struct { ElemType data[MaxSize]; int front, rear; }SqQueue;
特点
不能用Q.rear==MaxSize判断队满
缺点
存在“上溢出”
循环队列
实现
取余运算%
计算
队首指针进1
队尾指针进1
队列长度
判断
队空条件
队满条件
区分队空/队满
牺牲一个单元
此单元称为“空闲结点”
队列的结构体中增设size字段
队列的结构体中增设tag数据成员
基本操作
初始化
判空
入队
出队
链队列（链式存储）
实现
同时有队头指针和队尾指针的单链表
结构体
子主题
头结点
可选
优点
带头结点的链队列的操作更统一
注意
链队列的删除操作
删除前队中有≥2个元素
只需修改头指针
删除前队中仅剩一个元素
头指针与尾指针仅需修改
适用&优点
适合数据变动比较大的情形
不会产生队满溢出
程序中要适用多个队列
不会出现分配不合理与溢出
双端队列 (顺序存储和链式存储均可实现)
定义
允许两端都可以进行入队和出队操作的队列
双端队列的两端分别成为 前端 和 后端
图示
特点
在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。
在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。
变形
输出受限的双端队列
图示
输入受限的双端队列
图示
优先队列
栈、队列的应用
栈 & 括号匹配
栈 & 表达式求值
前缀表达式
中缀表达式
依赖运算符优先级
需要处理括号
后缀表达式
已经考虑了运算符优先级
没有括号
相互转化
参考笔记
栈 & 递归
在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。
递归算法->非递归算法
通常需要借助栈来实现
递归三要素
初值合法
递归体
终止条件
队列 & 层次遍历
队列 & 缓冲区 & 排队
推广
数组
定义
由n（n≥1）个相同类型的数据元素构成的有限队列，占据连续的一段存储空间
特点
一旦被定义，维度和维界就不再改变
基本操作
初始化数组
读元素
写元素
销毁数组
分类
一维数组
多维数组
两种映射方法
行优先
列优先
特殊矩阵的存储压缩
对称矩阵
图
子主题
存到一维数组中
在矩阵中的位置(i, j) <=相互转化=> 在数组中的位置k
公式（因起始不统一，不展示）
注意
矩阵或数组的下标开始是0还是1
三角矩阵
下三角矩阵
上三角矩阵
存到一维数组中
三对角矩阵
对角矩阵
AKA：带状矩阵
稀疏矩阵
定义
相对地，零特别多
没有标准，界限模糊
图
子主题
三元组
非零元素的（行号i，列号j，值v）
如何存储三元组
数组
十字链表
注意
稀疏矩阵压缩后，就失去了随机存取的能力
题型
位置计算，位置转换
第4章 串
定义
字符串，简称串
串是由n(n≥0)个字符组成的有限序列
S='a1 a2 ... an' (n≥0)
长度
n
空串
n=0
Ø
概念
子串
主串中任意多个连续的子序列
主串
包含子串的串
字符在串中的位置
该字符在串中的序号
串中第一个字符的序号为1，即：a1
子串在主串中的位置
=子串首字符在主串中的位置
空格串
由空格组成的串
空格穿≠空串
基本操作
赋值
比较
求长
取子串，[pos,pos+length)
连接
最小操作子集
不能由其他操作实现
复制
判空
定位子串的位置
清空
清空后变为空串
销毁
存储结构
定长顺序存储表示
特点
类似于：定长数组
结构体
#define MAXLEN 255 typedef struct { char ch[MAXLEN]; int length; //【一种串长的表示方法】 }SString;
串长的表示
设置length成员
在串末尾设置'\0'
此时，串长为隐含值
缺点
某些操作使串的长度超过MAXLEN，超出部分只能“截断”
堆分配存储表示
特点
仍然是一组地址连续的存储单元
但是，是在运行过程中分配的
结构体
typedef struct { char *ch; //基址 int length; //串长 }HString;
堆
malloc()
free()
块链存储表示
特点
类似于：单链表
图示
子主题
每个结点
既可以存储单个字符，也可以存放多个字符
每个结点成为“块”
整个链表成为“块链结构”
最后一个结点不满时，通常用“#”补上。
模式匹配（子串定位）
概念
主串S：长度:n
模式串T：长度m
要定位的串
模式串不一定能够找到
失配
正在比较的主串与模式串的对应位不相同
s[i] != t[j]
朴素模式匹配（暴力法）
最坏时间复杂度：O(nm)
指针回溯次数的计算
子主题
比较次数的计算
子主题
特点
匹配失败时，主串的指针i需要回溯
KMP算法
名称由来：三个人名首字母
Knuth，Morris，Pratt
改进后
匹配失败时，主串的指针不会回溯
流程
子主题
next[]与nextval[]的求法
next数组
失配时，模式串要回退到的位置
手算求法
对于模式串
模式串的首位与next[1]对齐
模式串常用p表示，pattern
next数组通常从[1开始存，而next[0]不存
（next[0]=-1），next[1]=0，next[2]=1
next[j]=
模式串aj失配时，最大公共前后缀的长度+1，（最大公共前后缀的长度要<前缀长度；即：最大公共前后缀不能完全重叠）
特点
next[j]的值每次最多增加1
模式串的最后一位不影响next数组的结果
因为最后一位的值与next数组的计算无关
nextval数组
nextval数组仅是对next数组的改进，不影响KMP算法流程
由next数组求nextval数组的求法
nextval[1]=0
nextval[j]，j≥2
模式串[j]!=模式串[next[j]]时
nextval[j]=next[j]
模式串[j]==模式串[next[j]]时
nextval[j]=nextval[next[j]]
最坏时间复杂度O(n+m)
预处理时间复杂度：求next数组/nextval数组
O(m)
匹配过程中最坏时间复杂度
O(n)
注意
在实际的KMP算法中，为了使公式更简洁，计算简单，如果串的位序是从1开始的，则next的数组才需要整体加1；如果串的位序是从0开始的，则next数组不需要整体加1。
主串指针是否会+1
第5章 树与二叉树
树
概念
定义
树是n（n≥0）个结点的有限集。
树的定义是递归的
空树
n=0
树是一种分层结构
图示
术语
称呼
祖先
根节点没有祖先
子孙
叶子结点没有子孙
双亲
双亲也是一种祖先
最近的祖先
双亲是1个结点，而不是2个结点
孩子
孩子也是一种子孙
最近的子孙
兄弟
具有相同双亲的不同结点
堂兄弟
同一层的不同结点
度
结点的度
一个结点拥有的孩子个数
树的度
树中结点的最大度数
分支结点/叶子结点
分支结点（非终端结点）
度>0的结点
根当然也是分支结点
叶子结点（终端结点）
度=0的结点
层/深度/高度
层/层次
↓，根结点：第1层
深度
↓，向下对层计数
高度
↑，向上对层计数
有序树/无序树
有序树
各子树的位置不能换
无序树
各子树可以互换
路径、路径长度
路径
两个结点之间所经过的结点序列（包含两端结点）
树中的路径是从上向下的
同一双亲的孩子之间不存在路径
路径长度
2结点之间
路径上所经过的边数
树
从树根到每个结点（不是每个叶结点）的路径长度的总和
注意与带权路径长度WPL的区别
森林
≥0棵互不交叉的树的集合
表示
ni
度为i的结点的个数
n0
叶子结点的个数
特点
非空树有且仅有一个没有前驱的结点，成为“根”
除根节点外，其余结点都有且只有1个前驱
树中的所有结点都可以有≥0个后继
性质
结点数=所有结点的度+1
度为m的树中第i层上至多有m^(i-1)个结点（i≥1）
高度为h的m叉树至多有(m^h-1)/(m-1)个结点
常用结论
总结点数n=∑ni
总边数=∑（i * ni）
总结点数=总边数+1
二叉树
定义
每个节点的最多有2棵子树的【有序树】
即使树的结点只有1棵子树，也要区分它是左子树还是右子树
区分：二叉树 与 度为2的有序树
特殊的二叉树
满二叉树
图示
完全二叉树
相同高度的满二叉树去掉末尾连续若干结点
图示
性质
完全二叉树中，n1要么=1，要么=0
二叉树中的任意两结点必然存在最近的公共祖先
二叉排序树
左子树上所有结点的关键字均小于根结点的关键字 右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又各是一棵二叉排序树
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1
二叉树的性质
二叉树的存储结构
顺序存储结构
图示
建议从[1开始存储结点。若从[0开始存，则可能不满足前述的某些性质。
完全二叉树 和 满二叉树 都适合顺序存储结构
子主题
一般二叉树
需要添加一些并不存在的空结点
最坏情况
高度为h且只有h个结点的单支树却要占据2^h-1个存储单元
缺点
空间利用率低
链式存储结构（一般采用）
图示
结点结构（基本）
数据域 data 左指针域 lchild 右指针域 rchild
结构体
typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;
在含有n个结点的二叉链表中，含有n+1个空链域
二叉树的遍历
定义
按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
即：以一定的规则将二叉树中的结点排列成一个线性序列，使得该序列中的每个结点（除第一个结点和最后一个结点外）都有一个直接前驱和直接后继
4种遍历
记号
根结点N，（Node）
左子树L
右子树R
“序”是对 根结点N 而言的
先序：先访问N
中序：中间访问N
后序：最后访问N
三种“序”遍历中，L都先于R
4种遍历
3序遍历
层次遍历
【需要借助 队列】
一般不用递归
由遍历序列构造二叉树
中序+其他任何一种序(先序|后序|层次)=>可以唯一确定。 否则，都不能唯一确定。 （先序+后序+层次）也不能唯一确定。
线索二叉树
背景
传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱和后继
引入目的
引入线索二叉树正是为了加快查找结点前驱和后继的速度
规定
若无左子树，令lchild指向其前驱结点。 若无右子树，令rchild指向其后继结点。
需添加 ltag 与 rtag 两个标志域
结点结构
标志域含义
线索二叉树结构体
线索链表
以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表
线索
指向结点前驱和后继的指针成为线索
线索二叉树
加上线索的二叉树成为线索二叉树
线索化
将二叉链表中的空指针改为指向前驱或后继的线索
而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树
分类
中序线索二叉树
添加头节点
头结点的lchild 指向 二叉树的根结点。 头结点的rchild 指向 中序遍历的最后一个结点。
中序遍历的 第1个结点的 lchild 指向 头节点。 中序遍历的最后1个结点的rchild 指向 头节点。
先序线索二叉树
后序线索二叉树
树、森林
存储结构（可以顺序存储，可以链式存储）
双亲表示法
定义
采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
根结点下标为0，其伪指针域为-1。
图示
结构体
#define MAX_TREE_SIZE 100 typedef struct //结点定义 { ElemType data; //结点的值 int parent; //双亲结点的索引 }PTNode; typedef struct //树的双亲表示定义 { PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //节点数 }PTree;
特点
利用了每个结点（根结点除外）只有唯一双亲的性质
可以很快得到每个结点的双亲结点
但求结点的孩子时需要遍历整个结构
区分 （树的顺序存储结构 vs 二叉树的顺序存储结构）
在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系
在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系
二叉树都可以用树的存储结构来存储， 但树却不都能用二叉树的存储结构来存储。
孩子表示法
定义
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空表）
图示
特点
这种存储方式寻找子女的操作非常直接， 而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
孩子兄弟表示法（二叉树表示法） （以二叉链表作为树的存储结构）
定义
每个结点包括
结点值
指向结点第一个孩子结点的指针
指向结点下一个兄弟结点的指针
沿此域可以找到结点的所有兄弟结点
图示
结构体
typedef struct CSNode { ElemType data; //数据域 struct CSNode *firstchild, *nextsibling; //第一个孩子指针、右兄弟指针 struct CSNode *parent; //(可选)指向父结点 }CSNode, *CSTree;
特点
优点
可以方便地实现树转换为二叉树的操作
易于查找孩子的结点等
缺点
从当前结点查找其双亲结点比较麻烦
若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。
树、森林 与 二叉树的转换
基础
由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上看，它们的二叉链表是相同的，只是解释不同而已。
树与二叉树
【注意】在树转成二叉树的过程中，树中的结点只有一个孩子时，要对应左孩子，而不能是右孩子。 如：左图中，G在二叉树中要为左孩子，而不能是右孩子。
森林与二叉树
树和森林的遍历
树的遍历
先根遍历
若树非空，先访问根结点，再依次遍历根结点的每棵子树
后根遍历
若树非空，先依次遍历根结点的每棵子树，再访问根结点
层次遍历
从上到下，从左到右
森林的遍历
先序遍历 （依次对每棵子树先根遍历）
若树非空： ①访问森林中第一棵树的根结点 ②先序遍历第一棵树中根结点的子树森林 ③先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历（AKA：后根遍历） （依次对每棵子树后根遍历）
若树非空： ①中序遍历森林中第一棵树的根结点的子树森林 ②访问第一棵树的根结点 ③中序遍历除去第一棵树之后剩余的树构成的森林
树与二叉树的应用
哈夫曼树 和 哈夫曼的编码
哈夫曼树的定义
结点的权
树中的结点常被赋予一个表示某种意义的值，称为该结点的权
带权路径长度WPL(Weighted Path Length)
从树的根到任意结点的路径长度li（经过的边数）与该结点上权值wi的乘积
哈夫曼树
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树的构造
【注意】
0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。
除非只有1个结点才唯一
构造过程、特点
注意
叶结点的内容写在〇内
叶权值写在〇上
每一步画一幅新图，（每一步多一个空白的〇）
哈夫曼编码
编码分类
固定长度编码
对每个字符用相同长度的二进制位表示
可变长度编码
允许对不同字符用不等长的二进制位表示
比固定长度编码好
可以降低平均编码长度，压缩数据
对高频字符用较少的二进制位表示； 对低频字符用较多的二进制位表示
前缀编码
若没有一个编码是另一个编码的前缀，则称这样的编码为 前缀编码
哈夫曼码
哈夫曼编码是一种前缀编码
哈夫曼编码
哈夫曼解码
并查集 DSU（Disjoint Set Union）
定义
一种简单的集合表示
特点
通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。
所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。
通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。
基本操作
Initial(S)
将集合S中的每个元素都初始化为只有一个单元素的子集合。
Union(S, Root1, Root2)
把集合S中的子集合Root2并入子集合 Root1。要求Root1和Root2互不相交，否则不执行合并。
Find(S, x)
查找集合S中单元素x所在的子集合，并返回该子集合的根结点。
第6章 图
概念
定义
G=（V,E）
顶点集V一定非空
边集E可以为空
图不能为空图
V={v1,v2,v3,...,vn}
|V|：顶点数
|V|＞0
E={(u,v)|u∈V,v∈V}
|E|：边的条数
|E|≥0
(u,v)：无向边（边）
<u,v>：有向边（弧）
图G的顶点集：V(G) 图G的边集：E(G)
术语
有向图
E是有向边的图
有向边（弧）
<v, w>： v --------> w 弧尾 弧头 (箭尾) (箭头)
从v到w的弧
v邻接到w
有序对不可交换：<v,w>≠<w,v>
无向图
E是无向边的图
无向边（边）
(v,w)=(w,v)：可交换
w和v互为邻接点
边(v,w)依附于w,v
边(v,w)和v,w相关联
简单图、多重图
简单图
①不存在重复边 ②不存在顶点到自身的边
考研中仅考虑简单图
完全图（简单完全图）
对于无向图
顶点数为n，有n(n-1)/2条边==>完全图
对于有向图
顶点数为n，有n(n-1)条弧 ==>有向完全图
有向完全图中，任意两顶点之间都存在方向相反的两条弧：v ⇄ u
子图
构造子图
母图==>①删除x个顶点(及其关联的边)②删除y条边==>子图
母图==>不删除顶点（保留所有顶点），仅删除y条边==>生成子图
并非V和E的任何子集都能够构成G的子图
无向图中：连通、连通图、连通分量
连通
两顶点之间存在路径
连通图
任意两顶点都是连通的
对于有n个顶点的连通图，最少有n-1条边
非连通图
不是连通图
对于有n个顶点的图，若边数小于n-1，则必为非连通图
对于有n个顶点的非连通图，最多有C(2,n-1)=(n-1)(n-2)/2条边：{n-1个点的完全图+1个孤立点}
连通分量
极大连通子图
图示
子主题
有向图中：强连通、强连通图、强连通分量
强连通
v可达w，且w可达v
强连通图
任意一对顶点都是强连通的
n个顶点的强连通图最少需要n条边：构成1个环
强连通分量
极大强连通子图
生成树、生成森林
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图的顶点数为n，则它的生成树含有n-1条边。
对生成树而言： 若砍去一条边，则会变成非连通图， 若加上一条边，则会形成一个回路。
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
顶点的度、入度、出度
无向图
度
依附于顶点v的边的条数：TD(v)
对于n个顶点、e条边的无向图
全部顶点的度之和 = 边数*2
有向图
度=出度+入度
TD(v)=OD(v)+ID(v)
出度OD(v)
(v)--->
入度ID(v)
(v)<---
对于n个顶点、e条边的有向图
入度之和 = 出度之和
边的权值、带权图（网）
边的权值
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
带权图（网）
这种边上带有权值的图称为带权图，也称网
稀疏图、稠密图
稀疏图
边少
稠密图
边多
路径、路径长度、回路（环）
路径
顶点vp到顶点vq之间的一条路径是指顶点序列vp,vi1,vi2,vi3,...,vq
路径长度
路径上边的数目称为路径长度
回路（环）
第一个顶点和最后一个顶点相同的路径称为回路或环
若一个图有n个顶点，并且有大于n—1条边，则此图一定有环。
简单路径、简单回路
简单路径
在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
有向树
一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。
存储
邻接矩阵
适用
有向图、无向图均可
唯一性
表示、记号
一维数组存顶点信息
二维数组存边信息
邻接矩阵：An×n
定义
无权图
带权图（网）
结构体
图示
注意
无向图的邻接矩阵是对称矩阵，且唯一。
实际存储中，只需存上三角/下三角矩阵的元素
对规模特大的邻接矩阵可采用压缩存储
空间复杂度=O(n^2)，其中n为图的顶点数|V|
特点
邻接表
适用
有向图、无向图均可
唯一性
特点
对于稀疏图，邻接表可以减少存储空间
邻接表结合了顺序存储和链式存储
结点结构、图示
结构体
存储特点
注意
邻接表的画法不唯一
优缺点
十字链表 （有向图）
适用
有向图专用
唯一性
描述
十字链表是【有向图】的链式存储结构
顶点与顶点之间是顺序存储的
每个弧有一个结点
每个顶点也有一个结点
结点结构
弧结点
顶点结点
特点
容易找到Vi为尾的弧，和Vi为头的弧
容易求出顶点的出度和入度
图的十字链表表示不唯一，但一个十字链表表示确定一个图
画法
邻接多重表 （无向图）
适用
无向图专用
唯一性
描述
每条边用一个结点表示
每个顶点用一个结点表示
画法不唯一
结点结构
边结点
顶点结点
特点
对于无向图，其邻接多重表和邻接表的差别仅在于： 同一条边在邻接表中用2个结点表示，而在邻接多重表表中只用1个结点表示
从顶点出发的线，穿过所有包含该顶点的边结点
画法
步骤
技巧/规范
基本操作
图的遍历
概念
BFS（广度优先搜索，Breadth-First-Search）
描述
Dijkstra 单源最短路径、Prim最小生成树算法也应用了类似的思想
BFS不是递归算法
BFS必须借助一个辅助队列visited[]
特点
图的广度优先搜索的过程 与 二叉树的层序遍历 是完全一致的， 这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。
单源最短路径可以用BFS实现
BFS性能
广度优先生成树
DFS（深度优先搜索，Depth-First-Search）
特点
DFS类似于树的先序遍历
DFS性能 (和BFS一致)
深度优先生成树
图的应用
分类
最小生成树MST（Prim, Kruskal）
最短路径（Dijkstra, Floyd）
有向无环图（DAG）
拓扑排序
AOV网、AOE网
关键路径
最小生成树MST（Minimal-Spanning-Tree）
概念
算法
Prim算法（选顶点）
Kruskal算法（选边）
最短路径
概念
之前的广度优点搜索查找最短路径只是对无权图而言
求解最短路径的算法通常都依赖于一种性质： 两点之间的最短路径也包含路径上其他顶点间的最短路径。
Dijkstra算法 (单源最短路径)
演示（Dijkstra手算）
注意：
与Prim算法区分
Floyd算法 (任意两点最短路径)
演示（Dijkstra与Floyd程序实现）
有向无环图DAG（Directed-Acylic Graph）
用途
有效地描述含有公共子式的表达式
对比
AOV网、拓扑排序、逆拓扑排序
AOV网
Acitivity On Vertex
顶点表示活动
每个AOV网都有1个或多个拓扑排序序列
拓扑排序 (对有向无环图而言)
每个顶点出现且只出现一次
若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径
对AOV网进行拓扑排序的步骤
拓扑排序 唯一性
若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一
但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
时间复杂度
逆拓扑排序 =拓扑排序逆置
AOE网、关键路径
AOE网 (有向无环图)
Activity On Edge
边表示活动
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。
AOE vs AOV
AOE网 特点
前后约束
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
开始 与 结束
仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始
存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束
从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同
关键路径
概念
从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径
关键活动
关键路径上的活动
只要找到了关键活动，就找到了关键路径，也就可以得出最短完工时间
参量
求关键路径的步骤
例子：
注意
关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
第7章 查找
概念
查找
定义
在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找结果
查找成功
查找失败
查找表（查找结构）
定义
用于查找的数据集合称为查找表
操作
①查询某个特定的数据元素是否在查找表中
②检索满足条件的某个特定的数据元素的各种属性
③在查找表中插入一个数据元素
④从查找表中删除某个数据元素
分类
静态查找表
只读不写，即：只涉及①②操作，不涉及③④操作
动态查找表
需要动态地插入或删除
关键字
定义
数据元素中唯一标识该元素的某个数据项的值
特点
基于关键字的查找，查找结果应该是唯一的
平均查找长度ASL (Average Search Length)
定义
一次查找的长度是指需要比较的关键字次数， 而平均查找长度ASL则是所有查找过程中进行关键字的比较次数的平均值
数学定义
意义
ASL是衡量查找算法效率的最主要的指标
分类
顺序查找（线性查找）
适用
顺序表、链表
分类
对一般线性表
思想
从头依次逐个比较
找到-->返回查找成功信息
到末尾还没找到-->返回查找失败信息
代码
哨兵
ST.elem[0]
作用
使得Search_Seq内的循环不必判断数组是否越界
引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率
特点
哨兵最后被比较
“哨兵”并不是这个算法独有的
等概率ASL
ASL成功
(n+1)/2
ASL失败
n+1
优缺点
优点
对数据元素的存储没有要求，顺序存储或链式存储皆可
对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用
缺点
当n较大时，平均查找长度较大，效率低
注意
通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。
对线性的链表只能进行顺序查找
对有序线性表
适用
顺序存储、【链式存储】
判定树
作用
描述有序线性表的查找过程
结点
圆形结点
表示有序线性表中存在的元素
矩形结点（失败结点）
表示不在表中的数据值的集合
若有n个数据结点，则查找树有n＋1个失败结点
若查找到失败结点，则说明查找不成功
图示
等概率ASL
ASL成功
(n+1)/2
ASL失败
n/2+n/(n+1)
折半查找（二分查找）
适用
仅适合 【有序】的 顺序存储 不适合 链式存储
代码（升序） 【要求手撕】
判定树
图示
折半查找的判定树
是一棵平衡二叉树
结论
折半查找法找到给定值的比较次数最多不会超过树的高度
等概率ASL
ASL成功
时间复杂度
O(logn)
平均情况比顺序查找的效率高
分块查找（索引顺序查找）
特点
吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
思想 与 步骤
思想
将查找表分为若干子块。块内的元素可以无序，但块之间是有序的。
再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
过程
第一步：在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。 第二步：在块内顺序查找。
图示
构造查找表
将关键码中<=第i个索引值的元素移入（从给定的关键码集合中删除，加入查找表）查找表
ASL
ASL构成
ASL=Li+Ls
Li：索引查找的平均查找长度
Ls：块内查找的平均查找长度
树形查找
二叉排序树（BST，二叉查找树）
定义
或者是一棵空树
或者是一棵具有以下特性的树
若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。
图示
特点
左子树结点值＜根结点值＜右子树结点值
对二叉排序树进行中序遍历，可以得到一个递增的有序序列
查找
非递归
递归
简单，效率低
实现
插入
构造
相同的一组数据，输入次序不同，导致构造出的二叉排序树也可能不同
重复的数据只会插入第一个
删除
若在二叉排序树中删除并插入某结点，得到的二叉排序树是否和原来的相同？
可能不同
效率分析
平衡二叉树 （Balanced Binary Tree，AVL树）
红黑树
B树、B+树
散列表
概念
散列函数
一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 Hash(key)＝Addr（这里的地址可以是数组下标、索引或内存地址等）。
冲突
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突
同义词
发生碰撞的不同关键字称为同义词
注意
设计得好的散列函数应尽量减少这样的冲突
由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法
散列表
定义
根据关键字而直接进行访问的数据结构
作用
散列表建立了关键字和存储地址之间的一种直接映射关系
复杂度
理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关
散列函数的构造
要求与原则
散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址
方法
直接定址法
散列函数
直接取关键字的某个线性函数值为散列函数
H(key)=key或H(key)=a×key+b
特点
计算最简单，且不会产生冲突
适合关键字的分布基本连续的情况
若关键字分布不连续，空位较多，则会造成存储空间的浪费
除留余数法
最简单、最常用
散列函数
假定散列表表长为m，取一个不大于m但最接近或等于m的质数p
H(key)=key%p
关键
选好p
使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。
数字分析法
平方取中法
效果
在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好
处理冲突
任何设计出来的散列函数都不可能绝对地避免冲突
方法
开放定址法
定义
取法
线性探测法
平方探测法
双散列法
伪随机序列法
拉链法（链接法，chaining）
适用
适用于经常进行插入和删除的情况
图示
查找过程
散列表的查找与构造散列表的过程基本一致
对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同
仍需要以平均查找长度ASL作为衡量散列表的查找效率的度量
性能分析
影响因素
散列函数
处理冲突的方法
装填因子α
定义
一个表的装满程度
散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越满，发生冲突的可能性越大，反之发生冲突的可能性越小。
第8章 排序
概念
定义
重新排列表中的元素，使表中的元素满足按关键字有序的过程
默认顺序
未加说明，默认为(...≤...≤...)非递减
框架
记录
元素
关键字
唯一标识记录的字段
记录≠关键字
稳定性
定义
相同关键字元素之间的相对位置在排序前后不变
【注意】
算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。
如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。
分类
是否在内存中
内部排序
排序期间元素全部都在内存中
外部排序
元素无法全部装入内存，需要借助外存
操作
大多数内部排序都要进行
比较
移动
基数排序不基于比较
内部排序
分类
插入排序
直接插入排序
基本思想
版本
带哨兵
不带哨兵
效率
空间复杂度
O(1)
时间复杂度
适用
直接插入排序算法适用于顺序存储和链式存储的线性表。 为链式存储时，可以从前往后查找指定元素的位置。
特点
边比较，边移动
折半插入排序
特点
将比较与移动分离
①先折半查找出元素待插入的位置
②然后统一地移动待插入位置之后的所有元素
稳定性
稳定
代码
子主题
变化
仅减少了比较元素的次数，约为O(n log2 n)
该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n
而元素的移动次数并未改变，它依赖于待排序表的初始状态
复杂度
时间复杂度
O(n^2)
适用
对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能
希尔排序（缩小增量排序）
由来
直接插入排序更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的
基本思想
过程
先取一个小于n的步长d1，在各组内进行直接插入排序，然后取第二个步长d2<d1，重复上述，直到所取的dt=1。
复杂度
时间复杂度
依赖于增量函数，尚未解决
当n在某个特定范围内，约为O(n^1.3)
最坏
O(n^2)
空间复杂度
O(1)
稳定性
不稳定
适用性
仅适用于线性表的顺序存储
交换排序
冒泡排序
基本思想
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]＞A[i]），则交换它们，直到序列比较完。
每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置······这样最多做n-1趟冒泡就能把所有元素排好序。
复杂度
时间复杂度
最好（初始序列有序时）
O(n)
最坏（初始序列逆序时）
O(n^2)
平均
O( n^2)
空间复杂度
O(1)
稳定性
稳定
注意
冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
快速排序
基本思想
基于分治
过程特征
一趟快速排序的过程是一个交替搜索和交换的过程
效率
空间效率
由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为O(log2n)；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；平均情况下，栈的深度为O(log2n)。
时间效率
影响因素
快速排序的运行时间与划分是否对称有关
最坏情况
两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为O(n^2)。
如何选取枢轴，以提高效率
一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素
随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。
地位
快速排序是所有内部排序算法中平均性能最优的排序算法。
稳定性
不稳定
注意
在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。
选择排序
基本思想
每一趟（如第i趟）在后面 n-i+1 （i=1，2，……，n-1）个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。
分类
简单选择排序
基本思想
假设排序表为L[1...n]，第i趟排序即从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过 n-1趟排序就可使得整个排序表有序。
效率
空间效率
O(1)
时间效率
始终为O(n^2)
稳定性
不稳定
堆排序
概念
堆
大根堆
任意结点≥其孩子结点
小根堆
任意结点≤其孩子结点
基本思想
看书，不整理了
效率
空间效率
O(1)
时间效率
最好、最坏、平均
O(n log2 n)
建堆
O(n)
每次调整
O(h)
稳定性
不稳定
归并排序
基本思想
图示
效率
空间效率
O(n)
时间效率
O(n log2 n)
稳定性
稳定
基数排序
特点
不基于比较和移动
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法
通常采用链式基数排序
方法
最高位优先MSD
最低位优先
LSD
效率
稳定性
稳定
比较 与 应用
归并排序同样基于分治的思想
比较
应用
如何选取排序方法
考虑算法外部因素
考虑算法内部因素
外部排序
概念
方法
多路平衡归并 与 败者树
置换-选择排序（生成初始归并段）
最佳归并树
题型
算法题
规范
算法思想
代码
属性修改不要忘
在顺序表中增删数据，最后要修改L.length
时空复杂度
模板
（1）算法思想： （可以画图） ①... ②... (a)... (b)... ③... 重复①~③，直至...。 （2）C++描述如下： void a(...) { //解释辅助函数功能 ... } int function(...) { ...; //注释 ...; } （3）时间复杂度：O(...)，空间复杂度：O(...)。 理由： ......，因此时间复杂度为O(...)。 仅使用到有限个辅助变量，因此空间复杂度为O(1)。
各种容器的名称
未指明容器的元素类型，怎么表示
如何取函数名，变量名
函数名，变量名拼写规范
子函数功能的描述
大括号规范
修改链表指针
当前元素位置
表头
前驱指针为NULL
表中
表尾
后继指针为NULL
运算符优先级
!L->next <==> L->next != nullptr
常用高级操作
逆置
左右移
判断成环
快慢指针
https://blog.csdn.net/qq_50710984/article/details/125996472
时间复杂度与空间复杂度，谁优先
一般时间复杂度优先
花费大量时间思考最优解法是得不偿失的
使用到排序
说明：使用时间复杂度为O(nlogn)的排序算法将...按从...到...进行排序
步骤重复，套娃=>试图降低时间复杂度
一个符合要求的输出 vs 多个符合题目的输出
追求时间空间都高效 还是 尽可能时间高效(空间换时间)？
【时间复杂度尽可能高效】=【必须用空间换时间】
题目明确了数据的取值范围不超过n，条件圈出来
开僻数组存所有可能的数据
题目没说链表长度，就不能直接用
通过遍历得到长度，T(n)=O(n)
评分标准：按复杂度给分
顺序表与数组的区别
基本相同
区别
函数签名
数组：void f(int A[], int length)
顺序表：void f(SqList &L)
长度
数组：length
顺序表：L.length
访问元素
数组：A[0]
顺序表：L.data[0]
思路
链表逆置
栈
递归