数据结构考试
一.复习重点
https://www.123pan.com/s/WiS5Vv-aMJeh.html
二.头歌实训
https://www.educoder.net/classrooms/MWBEUPRN/shixun_homework
三.数据结构知识点
一.第一章 概述
1.1数据结构的作用和意义
数据结构是一门融合数学，计算机硬件和计算机软件的核心课程。
数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序，操作系统，数据库管理系统及其他系统程序和大型
应用程序的重要基础。
1.2 基本概述和术语
1.数据即信息的载体，是客观事物的符号表示，反能输入计算机并能被计算机程序执行处理的符号都可称为数据。
2.数据元素是数据的基本单位，它在计算机处理和程序设计中通常作为独立整体。
3.关键字是数据元素中某数据项的值，若用该值可以唯一的标识一个数据元素，称该值为主关键字。
4.数据对象是具有相同特征的数据元素的集合，是数据的子集。
5.数据结构是数据及数据元素的组织形式。
数据结构分为：数据的逻辑结构，数据的存储结构和数据的运算。
数据的逻辑结构描述了一个数据对象中个数据元素之间的内在逻辑关系。
数据的存储结构又称为物理结构，表示一个数据对象中的各数据元素被保存到物理存储器之中呈现的关系。
数据结构通常有4类基本形式：集合结构，线性结构，树形结构或层次结构，图形结构或网状结构。
集合结构：数据元素除了同属于一个集合，它们之间没有其他关系。
线性结构：数据元素之间的关系是一对一的关系。
树形结构：数据元素之间存在一对多的关系。
图形结构：数据元素之间存在多对多的关系。
6.数据类型是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
java语言中，数据类型分为值类型和引用型两种。
值类型：int，double，long，float，short，byte，character，boolean等，是简单数据类型。
引用型：Arrays，String，StringBuilder，Math，ArraysList，Calendar，Date，File等
直接使用一个对象的名字或者别名来代表存储位置。
C++通过指针来表示对象在内存中的起始地址。
数据类型强调数据元素的相同性质及其运算，数据结构强调数据元素之间的相互关系，数据类型可以看做
简单的数据结构。
数据的逻辑结构是从具体问题抽象出来的数学模型，与数据在计算机中的具体存储没有关系。
数据结构分为线性结构和非线性结构。
线性结构有链表，堆栈，队列，串等。非线性结构有集合，矩阵，树和图等。
数据元素的集合D，数据元素D上的关系集R，一个数据结构可以形式化地描述成二元组B=（D，R）
数据结构在计算机中的表示称为数据的物理结构，又称数据的存储结构。
数据的存储结构有顺序和链式两种不同的方式。
顺序存储结构的特点是借助数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系。
顺序结构又分为索引存储和散列存储。
索引存储是在存储对象的基础上增加了一个索引表，索引表通过指定一个特定排序关键字来建立索引机制。
散列存储时通过数据元素与存储地址建立起某种映射关系，是每个数据元素与每一个存储地址尽量产生一一对应
的关系，这样，查找时同样可以大大提高效率。
链式存储结构通过一组任意的存储单元来存储数据元素。存储单元可以连续也可不连续。数据项+地址项
（后继元素的存储位置）
1.3 面向对象的数据结构表示
1.类的声明与实例化
2.类的成员的定义与使用
3.抽象类
4.泛型类
数据结构研究的是数据对象内部各数据元素之间逻辑关系问题，它不关心数据的具体类型，因此数据结构本身
就是一种抽象概念。因此，我们可以使用java语言的抽象类，泛型类或接口来表示数据结构中的抽象数据类型
，从而实现面向对象的抽象数据类型表示。
使用java语言描述数据结构的优势：1.使用java语言描述数据结构更加简单 2. java的泛型机制更加适合数据结构的抽象
表示3.java.util包提供多种数据结构，可以加速应用系统开发。
1.4 算法和算法分析
数据结构+算法=程序
算法是指在有限的时间内，为解决某一问题而采取的方法和步骤的准确，完整的描述，它是有穷的规则序列，这些规则
决定了解决某一特定问题的一系列运算或者操作。
一个算法应具备五个特征：1有穷性 2 确定性 3 可行性 4 输入 5 输出
算法效率的量度：1 正确性 2 可读性 3 健壮性 4 运行时间 5 占用空间
算法效率分析（算法优劣的评价）：1 时间复杂度 2 空间复杂度
一个算法的运行时间，成为算法的时间复杂度
某一算法的基本操作重复执行的次数（频次）是问题规模n的某个函数f(n)，这算法的时间复杂度T(n)=f(n)
比较不同算法的优劣主要以他们“增长的趋势”为准则，并重点考察当n逐渐增大时T(n)的极限情况。
这种“渐进时间复杂度”常常使用数量级的形式来表示，简称时间复杂度，记为T(n)=O(f(n))
x=x+1; O(1)
for(i=1;i<=n;j++){
x=x+1; O(n)
}
for(i=1;i<n;i++){
for(j=1;j<=m;j++){
x=x+1; O(nxm)
}
}
i=1;
while(i<=n){
i=5*i; O(log5 n)
}
O(1)常数阶，基本操作执行次数为常数
O(logn)对数阶
O(n)线性阶
O(nlogn)线性对数阶
O(n^2)平方阶
O(n^k)k方阶
O(x^n)指数阶
对于足够大的n
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<...<O(3^n)<O(n!)算法在整个运行过程中所占用的存储空间称为算法的空间复杂度。
算法在计算机存储器内占用的存储空间主要分为3部分：算法本身占用的存储空间，算法输入/输出数据所占用的
存储空间，算法运行过程中临时占用的存储空间。
算法的空间复杂度通常只讨论算法运行过程中临时占用的存储空间
算法运行过程中临时占用的存储空间分为两部分，一是为所有形参变量分配的存储空间，二是在为函数体中定义的内部临时
变量分配的存储空间
空间复杂度S(n)=f(n)=O(f(n)) n为问题的规模
long factorical(long n){
if(n<=1){
return 1;
}else{
return n*factorial(n-1);
}
}
递归算法的空间复杂度为递归计算过程中所消耗的堆栈空间的大小，它等于一次调用所分配的临时存储空间的
大小乘以被调用的次数。该算法的空间复杂度为S(n)=O(n)二.第二章 线性表的逻辑结构
2.1 线性表的概念
线性表是n个数据元素的有限序列，其元素可以是数值，字符也可以是有多个数据项的组合。
线性表中的元素可以是多种类型的，但是对于同一线性表，其中的数据元素必须要有相同特性
线性表可逻辑地表示为（a1,a2,a3,ai-1,...an)其中a1为表中的第一个数据元素，an为最后一个数据元素，ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱，ai+1是ai的直接后继
线性表还可以使用以下形式化的描述进行定义 LinearList=(D,R) D为数据元素的集合，R为序偶的集合
线性表中数据元素的个数n为线性表的长度
当数据元素的位置与它的值相关时，称为有序线性表，否则称为无序线性表。
2.2 线性表的顺序实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的这种连续存储表示称为
顺序存储结构或顺序映像，通常，把这种具有顺序存储结构的线性表简称为顺序表。
以数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。可以根据顺序表中数据元素的位序，随机
访问表中的任一元素，也就是说，顺序表一种可随机存取的存储结构。
顺序表的实现：
初始化 插入O(n) 删除O(n) 查找 获取第pos位置的元素 修改第pos位置的元素 求顺序表的长度 遍历 清空顺序表
2.3 顺序表的链式表示
线性表的链式存储结构是指用一组任意的存储单元来存放线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
节点=数据域+指针域
存储数据元素信息的域称为数据域，存储直接后继存放位置的域称为指针域。
这两部分信息组成数据元素ai的存储映像，称为节点
有n个元素的线性表通过每个节点的指针域链接成一个链表，由于链表的每个节点只有一个指向后继的指针
，所以称其为单链表或线性链表
在单链表中，头结点只表示链式存储结构的开始，其数据域可以不存储任何数据信息，其指针域指向链表的第一个节点
由于最后一个数据元素没有直接后继，故最后一个节点的指针为空（null）常用^表示
2.3.1 单链表的实现
初始化 获取头结点地址 插入O(n) 删除O(n)查找O(n) 获取单链表第pos个节点的值 更新单链表第pos个节点的值 判断单链表是否为空
求单链表的长度 遍历操作 清空单链表
2.3.2 循环链表的实现
操作基本一致，区别在于算法中判断到达链表尾节点的条件不是p.next是否为空，而是它们是否等于头指针
在循环链表中插入一个节点时必须要考虑在链表末尾追加节点的情况，即要把头结点修改为它的后继节点。
同样，删除某个节点，如果该节点是链表中的最后一个节点，此时应该注意要把该节点的前驱节点的后继设置为头结点
2.3.3 双向链表的实现
包含前驱节点和后继节点地址的链表称为双向链表
prior data next
双向链表的插入 双向链表的删除
2.3.4 双向循环链表
三.第三章 栈
3.1 栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。允许插入，删除的一端为栈顶，另一端为栈底，不含
任何数据元素的栈称为空栈。栈的修改原则是后进先出。
栈顶指针来表示栈顶的位置，栈底指针来表示栈的底部位置。
栈的基本操作
初始化 入栈 出栈 获取(取栈顶元素) 判空 求长度 正向遍历 销毁
3.1.1 顺序栈
用一组地址连续的存储单元(数组)依次存放自栈底到栈顶的数据元素，把数组中索引为0的一端称为栈底，用top来指示
栈顶元素在顺序栈中的变化。
top为栈顶指针，top指向栈顶元素的位置
top的初始值为-1，指向栈底，每当插入一个新的栈顶元素，先把栈顶指针top加1，在把入栈的元素放在栈顶指针top指向的位置。
删除栈顶元素时，先删除栈顶元素，在把栈顶指针top-1
顺序栈的基本操作
初始化 入栈 出栈 读栈顶元素 判断栈空操作 遍历栈 清空栈操作
3.1.2 链栈
采用链式存储结构的栈称为链栈
节点=数据域+指针域
插入一个新元素p，只能链接到栈顶，数据域为data，指针域指向原栈顶元素，栈顶指针top在指向这个新元素，
操作语句为p.next=top;top=p;删除一个元素，只能删除栈顶元素，删除时，栈顶指针指向原栈顶元素的指针域，
操作语句为p=top;top=top.next;
链栈的操作
入栈 出栈 读取栈顶元素 求栈中数据元素个数 判断当前栈是否为空 销毁一个已存在的栈
3.2 队列
3.2.1 队列的定义
队列是一种运算受限制的线性表，元素的添加操作在表的一端进行，而元素的删除操作在表的另一端进行，
允许插入的一端为队尾，允许删除的一端为队头。
先进先出
向队列添加元素称为入队，从队列中删除元素称为出队，新入队的元素只能添加在队尾，出队的元素只能是
对头的元素。
队列的基本操作
初始化 入队 出队 获取对头 求长度 判空 正序遍历 销毁
3.2.2 顺序队列
队列用一维数组表示，索引下界为0，上界为n-1，还需设置两个指针front和rear分别指向队头元素和队尾元素的
位置，元素的数目为0的队列为空队列，初始化是front=rear=0；入队时将队尾指针rear加1，即rear=rear+1，
在将新元素按rear指向位置插入。出队时将队头指针+1，即front=front+1，在将 front所指的元素取出，
在非空队列中，队头指针始终指向队头元素的前一个位置，队尾指针始终指向队尾元素的位置。
3.2.3 循环队列
物理上队尾在队头之前，但逻辑上队头仍在前，入队和出队仍按照先进先出的原则进行。通常把这种特殊结构的
队列成为循环队列。
加入元素e
rear=(rear+1)%queueArray.length;删除元素e
front=(front+1)%queueArray.length;队列元素个数
(rear-front+queueArray.length)%queueArray.length;少用一个元素的存储空间，此时队列最多存放 queueArray.length-1 个元素
(rear+1)%queueArrays.length==front;判断循环队列是否为满rear==front;判空3.2.2 链队列
用链表结构表述的队列称为链队列
有队头和队尾两个指针，在链队列中添加一个头结点，并令队头指针指向头结点
front==rear; 判空 rear.next=p; 入队
front.next=front.next.next;出队四.第四章 串,矩阵,广义表
4.1串的概念
字符串(简称串)，是由0个或多个字符组成的有限序列。记为 s="a1a2a3...an"
s为串的名字，用单引号括注的字符序列是该串的值，串中的字符的个数n称为串的长度。0个字符的串称为空串，长度为0
串中由任意连续的字符组成的子序列称为该串的子串，包含子串的串相应称为主串，字符在序列中的序号为字符位置，
子串在主串中的位置则以子串的第一个字符在主串中的位置来表示，称为子串位置。
4.2串的基本操作
复制 判空 串比较 求串长 串连接 求子串 子串定位 串替换 插入子串 删除子串 大写转小写 小写转大写 串压缩
4.3 串的顺序存储与实现
可以用字符数组来存储字符数据
串初始化 串比较 串连接 求子串 复制串
4.4 模式匹配
在当前串中寻找某个子串的过程称为模式匹配,其中该子串称为模式串,如果匹配成功,返回子串在当前串中首次出现的存储位置
否则匹配失败。
模式匹配算法 BF
基本思想：首先将当前串的第一个字符与子串的第一个字符进行比较，若不同，就将当前串的第二个字符以子串的第一个字符进行比较
......直到当前串的第i个字符和子串的第一个字符相同，在将它们之后的字符进行比较，若也相同，继续向后比较，若当前串的第i+j个字符
与子串的第j个字符不同，则返回到本趟开始字符的下一个字符，重复上述过程，若子串中的字符全部比较完毕，则说明本趟匹配成功
本趟的起始位置为i，否则，匹配失败。
在好的情况下，时间复杂度为O(n+m)
在最坏的情况下，时间复杂度为O(n*m)
public int index (String t){
if(this.length<t.getLength()){
return -1;
}
int a = -1;
for(int i=0;i<this.length;i++){
int j=0;
while(j<t.getLength()&&this.chars[i+j]==t.chars[j]){
if(this.chars[i+j]!=t.chars[j]){
break;
}
j++;
}
if(j==t.getLength()){
a=i;
break;
}
}
return a;
}4.5 矩阵
4.5.1 矩阵的定义
一般用二维数组来存储矩阵 ,有些程序设计语言还提供了矩阵运算方法
4.5.2 特殊矩阵 对称矩阵
若n阶矩阵A中的元素满足：aij=aji ,1<=j, j<=n,则称其为n阶对称矩阵。
3 6 4 7 8
6 2 8 4 2
A= 4 8 1 6 9
7 8 6 0 5
8 2 9 5 7
对于对称矩阵，可以将n^2个元素压缩存储到有n*(n+1)/2个元素的空间里
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
SA= 3 6 2 4 8 1 7 4 6 0 8 2 9 5 7
对称矩阵的压缩存储
此时，a11存入SA0，a21存入SA2... aij存入SAk k与i，j的对应关系为：
(i*(i-1))/2 + j-1 i>=j
k= (j*(j-1))/2 + i-1 i<j4.5.3特殊矩阵 三角矩阵
分为上三角矩阵和下三角矩阵
3 c c c c
6 2 c c c
A= 4 8 1 c c 下三角矩阵
7 8 6 0 c
8 2 9 5 7
3 6 4 7 8
c 2 8 4 2
A= c c 1 6 9 上三角矩阵
c c c 0 5
c c c c 7
对于三角矩阵，可以将n^2个元素压缩存储到有n*(n+1)/2+1个元素的空间里 多一个c 可节省n*(n-1)/2个存储单元
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
SA= 3 6 2 4 8 1 7 4 6 0 8 2 9 5 7 c
三角矩阵的压缩存储
此时，a11存入SA0，a21存入SA2... aij存入SAk k与i，j的对应关系为：
(i*(i+1))/2 +j i>=j i，j从0开始
k= (n*(n+1))/2 i<j
下三角行列式
((2*n-i+1)*i)/2 +j-1 i<=j i，j从0开始
k= (n*(n+1))/2 i>j
上三角行列式 4.5.4 特殊矩阵 稀疏矩阵
假设m行n列的矩阵含t个非0元素，则非0元素的比例δ=t/mxn称为稀疏因子，通常认为δ<=0.05的矩阵为稀疏矩阵
每个非零元素可以表示为一个三元组(i,j,aij) 将三元组按行优先或列优先的顺序排列，如按行优先，将同一行中
列号以从大到小的规律排列为一个线性表，称为三元组表，每一个稀疏矩阵可用一个三元组表来表示，称为稀疏矩阵
的顺序存储结构。
0 12 9 0 0 0
0 0 0 0 0 0
A= -3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
稀疏矩阵
i j vaule
0 6 6 8
1 1 2 12
2 1 3 9
3 3 1 -3
4 3 5 14
5 4 3 24
6 5 2 18
7 6 1 15
8 6 4 -7
三元组表4.6 广义表
广义表是一种特殊的有限序列，其数据元素可以是单个数据(单元素，又称原子)，也可以是一个广义表(子表)。
当广义表非空时，第一个元素通常称为表头，其余元素的组成的子表称为表尾。
广义表最外层包含的元素的个数称为广义表的长度。
广义表所含括号的重数称为广义表的深度。
“原子”的深度为0，“空表”的深度为1，广义表的名称用大写字母表述，数据元素用小写字母表示。
D=((),(e),(a,(b,c,d)))
长度为3，深度为3，Head(D)=a,Tail(D)=((e),(a,(b,c,d)))4.6.1 广义表的存储结构及实现
通常为链式存储结构 ，每个数据元素可用一个节点表示。
节点结构有两种 ：原子节点 表节点
一个表节点有3个域组成：标志域，指示表头的指针域，指示表尾的指针域
一个原子节点有2个域组成：标志域和值域
五.第五章 树的定义和基本术语
5.1.1 树的定义
树是有若干个节点组成的有限集合，其中必须有一个节点是根节点，其余节点分为若干个互不相交的集合，每一个集合还是一棵树
，但被称为根的子树。当树的节点个数为0时，这棵树为空树，记为Φ
树具有以下特点：
1.树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点
2.树中所有节点可以有0个或多个后继节点
5.1.2 树的表示方法
1.直观表示法 2.嵌套集合表示法 3.广义表表示法4.凹入表示法
5.1.3 树的术语
树的节点：表示树中的数据元素，包括数据项及若干指向其子树的分支。
节点的度：节点所拥有的子树的个数称为该节点的度。
叶子节点：度为0的节点称为叶子节点，又称为终端节点。
分支节点：度不为0的节点称为分支节点，又称非终端节点。除了根节点，分支节点也称内部节点。
孩子，双亲，兄弟：若树中一个节点A的子树的根节点是B，则称B是A的孩子(也称之节点)，称A为B的双亲(也称父节点)
具有相同双亲的子节点互称兄弟。
路径，路径长度：如果一颗树的一串节点n1，n2，n3...nk有如下关系，即节点ni是ni+1的父节点(1<=i<k),就把n1，n2...nk
称为一条由n1至nk的路径。这条路径的长度是k-1。
祖先，子孙：在树中，如果有一条路径从节点M到节点N，那么M称为N的祖先，N称为M的子孙。
节点的层数：规定树的根节点的层数为1，其余节点的层数等于它的双亲节点的层数加1。
树的深度：树中所有节点的最大层数称为树的深度。/任意一个节点到根节点的距离，根节点从一开始
树的高度：任意一个节点到叶子节点的距离，叶子节点从一开始
树的度：树中各节点的度的最大值称为该树的度。
有序数和无序树：一颗树中的节点的各子树从左到右是有次序的，若交换了某节点各子树的相对位置，则构成不同的树，
称这棵树为有序数；反之则称为无序树。
森林：0棵或有限棵不相交的树的集合称为森林。任意一棵树，删去根节点就变成了森林。
5.2 二叉树
5.2.1 二叉树的概念
二叉树是一种每个节点最多拥有2个字树的树，其中第一个字树被称为左子树，第二个子树被称为右子树，当二叉树的节点
个数为零时，我们称这个二叉树为空二叉树，记为Φ
满二叉树：在二叉树中，如果所有分支节点都存在左子树和右子树，而且所有叶子节点都在同一层上，这样的一颗二叉树称为
满二叉树。深度为k ，且有2^(k-1)个节点
完全二叉树：是一种叶子节点只能出现最下层和次下层，且最下层的叶子节点集中在树的左边的特殊二叉树。一棵深度为
k的二叉树，其中除k层外，其他个节点数均达到最大值。
5.2.2 二叉树的性质
性质1 一棵非空二叉树的第i层上最多有2^(i-1)个节点(i>=1)
性质2 一棵深度为k的二叉树中，最多具有2^k -1个节点
性质3 对于一颗非空二叉树，如果叶子节点数为n0，度为2的节点数为n2，则有：n0=n2+1
边数(总度数之和)=总结点数之和-1
性质4 具有n个节点的完全二叉树的深度k为[log2 n]+1
性质5 对于具有n个节点的完全二叉树如果按照从上至下和从左右的顺序对二叉树中的所有节点从1开始按顺序编号，则
对于任意的序号为i节点，有如下关系：
1.如果i>1,则序号为i的节点的父节点的序号为[n/2],如果i=1，则该节点是根节点，无父节点。
2.如果2i<=n,则序号为i的节点的左子节点的序号为2i，如果2i>n,则序号为i的节点无左子节点。
3.如果2i+1<=n,则 序号为i的节点的右子节点为2i+1；如果2i+1>n,则序号为i的节点无右子节点。
5.2.3 二叉树的存储结构
1.顺序存储结构
用一组连续的存储单元存放二叉树的节点，从上至下，从左到右 适合于完全二叉树和满二叉树，序号可以唯一的
反映节点之间的逻辑关系，又不会浪费空间 ，对于一般二叉树，深度为k最多需要分配2^k -1个存储单元
2.链式存储结构
二叉树的链式存储结构是指用链表来表示一颗二叉树。
lchild data rchild
二叉树存储中节点的存储结构
其中，data域用来存放某节点的数据信息；lchild，rchild分别存放指向左孩子和右孩子的指针
当左孩子或右孩子不存在时，相应指针域值为空（用符号^或null表示）3.三叉链表存储
lchild data rchild parent
三叉链表存储中节点的存储结构
其中，data域用来存放某节点的数据信息；lchild，rchild分别存放指向左孩子和右孩子的指针
当左孩子或右孩子不存在时，相应指针域值为空（用符号^或null表示），parent域为指向该节点双亲节点的指针
即便于查找孩子节点，又便于查找双亲节点5.2.4 二叉树的基本操作
建立二叉树 生成一颗二叉树 向二叉树中插入一个左右孩子节点 删除二叉树的左子树
5.2.5 二叉树的遍历
二叉树的遍历是指按照某种顺序访问二叉树的每个节点，使每个节点被访问一次且仅访问一次
1.前序遍历
访问根节点 前序遍历根节点的左子树 前序遍历根节点的 右子树
2.中序遍历
中序遍历根节点的左子树 访问根节点 中序遍历根节点的 右子树
3.后序遍历
后序遍历根节点的左子树 后序遍历根节点的右子树 访问根节点
4.层次遍历
从上到下，从左到右
在进行层次遍历时，可设置一个队列结构，从根节点遍历，首先将根节点入队，然后从队头取出一个元素，每取
一个元素执行以下操作：
若该元素所指节点的左右孩子非空，则将该元素所指节点的左孩子节点和右孩子节点按顺序入队，直到层次遍历结束
5.求二叉树的深度
使用后序遍历求二叉树的深度
5.2.6 线索二叉树
为了保留节点在某种遍历序列中采用直接前驱和直接后驱的位置关系，可以利用二叉树的二叉链表存储结构中的空指针域
来指示。这些指向直接前驱节点和指向直接后继节点的指针被称为线索，加了线索的二叉树被称为线索二叉树
一个具有n个节点的二叉树若采用二叉链表存储结构，在2n个指针域中只有n-1个指针域用来存储孩子节点的引用，而另外
n+1个指针域存放的都是null。
线索树有前序，中序，后序线索二叉树三种，把二叉树改造为线索二叉树的过程称为二叉树的线索化
通过为每个节点增设两个标志域Itag和rtag来实现区分指针域存放的是指针还是线索
0 lchild指向节点的左孩子
ltag= 1 lchild指向节点的直接前驱节点
0 rchild指向节点的右孩子
rtag= 1 rchild指向节点的直接后继节点
ltag lchild data rchild rtag
线性二叉树中节点的结构前序，中序，后序线索二叉树的构建
1求遍历 2看空域 3 连线
1.启动二叉树线索化
2.通过中序遍历完成二叉树的线索化
3.在中序线索二叉树上查找任意节点的中序前驱节点
4.在中序线索二叉树上查找任意节点的中序后序节点
3.如果该节点的左标志为1，那么其左指针域指向的节点便是它的前驱节点，如果该节点的左标志为0，
表明该节点有左孩子，它的前驱节点是以该节点的左孩子为根节点的子树的最右节点。
4.如果该节点的右标志为1，那么其右指针域指向的节点便是它的后继节点，如果该节点的右标志为0，
表明该节点有右孩子，它的后继节点是以该节点的右孩子为根节点的子树的最左节点。
5.2.7 二叉树的查找
二叉查找树有称为二叉排序树
若它的左子树不为空，则左子树上的所有节点的值均小于根节点的值
若它的右子树不为空，则右子树上的所有节点的值均大于根节点的值
它的左右子树也分别是二叉查找树5.3 树和森林
5.3.1 树的存储方式
1.双亲表示法 2.孩子链表表示法3.双亲孩子表示法4.孩子兄弟表示法
5.4.2 树和森林与二叉树之间的转换
1.将树转换为二叉树
树中的所有兄弟之间加连线
对树中的每个节点，只保留它与第一个孩子节点之间的连线，删去它与其他孩子节点之间的连线
以树的根节点为轴心，旋转，使之结构分明2.将森林转换为二叉树
将森林中的每颗树转换成相应的二叉树
第一棵二叉树不动,从第二棵开始,依次把一棵二叉树的根节点作为前一棵二叉树根节点的右孩子,当所有二叉树连起来后,
此时得到的二叉树是由森林转换得到的二叉树3.将二叉树转换为树和森林
根据二叉树的根节点有无右分支,将一棵二叉树还原为树或森林
若某节点是其双亲的左孩子,则把该节点的右孩子,右孩子的右孩子...都与该节点的双亲结点用线连起来
删去原二叉树中所有的双亲结点与右孩子结点的连线
整理,使结构分明5.4.3 树的遍历
1.先根遍历
访问根节点
按照从左到右的顺序先根遍历根节点的每一棵子树2.后根遍历
按照从左到右的顺序后根遍历根节点的每一棵子树
访问根节点5.4.4 森林的遍历
1.前序遍历
2.中序遍历
5.5 哈夫曼树
哈夫曼树也称最有二叉树，是指对一组带有确定权值的叶子节点，构造的具有最小带权路径长度的二叉树。
从根节点到各个叶子节点的路径长度与相应节点权值的乘积之和叫做二叉树的带权路径长度。
WPL= 求和符号 wk x Lk k从1到n
哈夫曼算法 126页
哈夫曼树的构造算法 127页
哈夫曼编码 128页
6.图
6.1 图的定义及其常用术语
6.1.1 图的定义
图是由顶点集合及顶点之间的边集合组成的一种数据结构，记为G=(V,E)
6.1.2 图的常用术语及含义
1有向图和无相图
根据顶点之间的关系是否有方向性区分,对于无向图,顶点的边用圆括号表示(x,y)
对于有向图,顶点间的边称为有向边,用尖括号表示<x,y>
2完全图 稀疏图 稠密图 网
n表示顶点数目 边数为e 则
当为0<=e<=n(n-1)/2，该图称为完全图
当为0<=e<=n(n-1)，该图称为有向完全图
一个图的边数或弧数接近完全图的时，为稠密图；反之，为稀疏图
如果图的边有数据，则称该数据为边的权，带权的图为网
3 子图
若有两个图G1和G2，其中G1=(V1,E1),G2=(V2,E2),且满足如下条件：
V2属于V1,E2属于E1,则称图G2为图G1的子图
4 邻接点和度
对于无向图，顶点v和顶点w之间存在一条边，则称顶点v和顶点w互为邻接点，顶点v关联的边
的数目定义为v的度，记为TD(V)
顶点的出度是以顶点v为弧尾的弧的数目，记为OD(V),顶点的入度是以顶点V为弧头的弧的数目，记为ID(V)
5 路径 简单路径 简单回路
两个顶点之间的路径为两个顶点之间的顶点序列
路径上所含边的数目为路径的长度
序列中顶点不重复出现的路径称为简单路径,序列中除第一个顶点和最后一个顶点相同外,其余顶点不重复的回路
称为简单回路
6 连通图 连通分量 强连通图 强连通分支
在无向图中,若从顶点x到顶点有路径,则称顶点x和顶点y是连通的,若图中任意两个顶点都是连通的,则称改无向图为连通图
否则为非连通图
在无向图中,极大的连通子图(满足连通的条件下,尽可能多包含原图的顶点和边)被称为该图的连通分量
任意连通图的连通分量只有一个,及它本身 非连通图可能有多个连通分量
在有向图中,若从顶点x到顶点有路径,则称顶点x和顶点y是连通的,若图中任意两个顶点之间都存在一条有向路径,则称改有向图为强连通图
否则为非强连通图
在有向图中,极大的强连通子图被称为改图的强连通分量
任意强连通图的强连通分量只有一个,及它本身 非强连通图可能有多个强连通分量
6.2 图的存储结构
6.2.1 邻接矩阵
用两个数组来表示图,第一个数组是一维数组用来存储顶点信息,第二个数组是二维数组,存储顶点之间的信息
邻接矩阵的性质
144-147 页
6.2.2 邻接表
是图的一种顺序存储与链式存储结合的存储方法
有向图与无向图邻接表的性质
逆邻接表
147-151 页
6.3 图的遍历
6.3.1 深度优先(dfs)
152-154页
6.3.2 广度优先(bfs)
155-157页
6.4 生成树和最小生成树
6.4.1 生成树
157页
6.4.2 最小生成树
1.普利姆算法
2.克鲁斯卡尔算法(回路)
158-165页
6.5 图的应用
6.5.1 最短路径
迪杰斯特拉算法(单源最短路径)按路径长度递增产生各顶点的最短路径算法
6.5.2 拓扑排序
AOV网
拓扑排序 判断有向图中是否存在回路
169-171页
6.5.3 关键路径
AOE网
事件（顶点）的最早发生时间，事件（顶点）的最迟发生时间，活动（边）的最早发生时间，活动的最迟发生时间——关键路径
求Ve Vl e(i,j) l(i,j)
对比e和l，相同的边为关键活动
171-174 页
7.查找
7.1基本概念
数据项是数据不可分割的最小单位
数据元素是由若干数据项构成的最小数据单位
根据给定的某个值，在查找表中寻找一个其关键字等于给定值的数据元素
查找表是由同一类型的数据元素构成的集合
查找表的四种基本操作
1.判定数据元素是否存在2.查找数据元素各属性值3.插入一个元素4.删除一个元素
把查找过程中对关键字的最多比较次数和平均比较次数称为最大查找长度，后者称为平均查找长度
7.2 静态查找表
7.2.1 顺序查找
顺序查找又叫线性查找，既使用于线性表的顺序存储结构，也适用于线性表的链式存储结构
顺序查找的平均查找长度
时间复杂度为O(n)
7.2.2 折半查找
折半查找又称为二分查找，它是一种效率较高的查找算法
要求线性表必须采用顺序存取结构，且表中元素必须有序
用二叉树来描述折半查找过程，把当前查找区间的中间节点mid作为根节点，左半区间和右半区间分别作为根的左子树
和右子树，左半区间和右半区间再按类似的方法推导
平均查找长度ASL=(n+1/n) (log2 (n+1) ) -1
n较大时ASL=(log2 (n+1) ) -1
则时间复杂度为O(log2 (n+1))
7.3 动态查找表
在动态查找表中，经常需要对表中记录进行插入和删除
二叉查找树的查找属于典型的动态查找表
当查找树接近于满二叉树时，最坏情况下查找时间为log2 (n+1)，与折半查找同量级
当为单支树时，最坏情况下查找时间为O(n),与顺序查找同一数量级
满二叉树具有较高的查找速度
7.3.1 平衡二叉树
形态均匀的二叉查找树称为平衡二叉树
平衡因子是用来衡量二叉树节点的左子树和右子树的高度差的。如果一个节点没有右子树，那么它的平衡因子就是它的左子树的高度减去0（右子树的高度为0）。
假设我们有一个节点N，它只有左子树，没有右子树。设L为节点N的左子树的高度，则N的平衡因子为L-0，即平衡因子为L。
所以，如果一个节点没有右子树，它的平衡因子就是它的左子树的高度最小不平衡子树是指离插入节点最近求平衡因子绝对值大于1的节点做根节点的子树
调整最小不平衡子树各节点之间的连接关系，以达到新的平衡，这样的平衡二叉树简称AVL树
二叉平衡树的构建：构建二叉排序树过程中，调整最小不平衡字树有四种情况（LL，RR，LR，RL）
187-192 页
7.3.2 B-树
192-194 页
7.3.3 B+树
195 页
7.3.4 二叉查找树(二叉排序树)
又叫二叉搜索树（Binary Sreach Tree）或二叉排序树,简称BST。 二叉排序树的性质：如果任一结点的左子树非空，则左子树的所有结点的值都小于根结点的值；如果任一结点的右子树非空，则右子树的所有结点的值都大于根结点的值。
二叉查找树的构建
https://blog.csdn.net/yohe12/article/details/103646598
ASL(平均查找长度的计算
https://blog.csdn.net/Ang_go/article/details/117302523
7.4 哈希表
7.4.1 哈希表的概念
在记录的存储位置和它的关键字之间建立一个确定的对应关系H，以H作为关键字为key的记录在表中的位置
称这个对应关系H为哈希函数，按这个思想建立的表称为哈希表
哈希表也称为散列表
7.4.2 哈希函数的构建
1.直接定址法 2.数字分析法 3.平方去中法 4 折叠法 5 除留余数法
7.4.3 处理冲突
1.开放定址法
对增量di有三种取法
线性探测法 平方探测法 随机探测法
2.链地址法
3.在哈希法
4.公共溢出区法
7.4.4 哈希表的查找及分析
装填因子 a=n/m n为记录数 m为表的长度
线性探测在哈希处理冲突：ASL=1/2(1+1/(1-a))
平方探测在哈希处理冲突：ASL=-(1/a)ln(1-a)
链地址法处理冲突：ASL=1+a/2
哈希表的平均查找长度是a的函数，可以选择一个合适的a，使平均查找长度限定在某个范围内
8.排序
8.1基本概念
排序就是将一组任意数据序列的数据按一定的规律进行排序，使之成为有序序列
作为排序依据的数据项被称为排序项，也被称为记录的主关键字
关键字分为主关键字和次关键字
主关键字排序结果唯一
次关键字排序结果不唯一
排序分类
根据排序过程中涉及的存储器，排序分为内部排序和外部排序
按排序的稳定性，分为稳定排序和不稳定排序
按排序的策略，分为插入排序，交换排序，选择排序，归并排序，基数排序、
8.2 插入排序
8.2.1直接插入排序
8.2.2 希尔排序
8.3 交换排序
8.3.1 冒泡排序
8.3.2 快速排序
8.4 选择排序
8.4.1简单选择排序
8.4.2 堆排序
8.5 归并排序
8.5.1 二路归并排序
8.6 各种排序算法比较
希 快 选 堆
220页
数据结构习题
1.计算机执行下面语句时,语句s的执行效率为 (n-2)(n+3)/2
for(i=l；i<n-l；i++)
for(j=n;j>=i;j--)
s=s+1;
i=1 n
i=2 n-1
...
i=n-2 3
s=(n-2)(n+3)/2试比较线性表的两种存储结构各自的优缺点。
顺序存储：
优点：存储密度大，存储空间利用率高，可随机存取。
缺点：插入或删除元素时不方便。
链式存储：
优点：插入或删除元素时很方便，使用灵活。
结点空间可以动态申请和释放；
缺点：存储密度小，存储空间利用率低，非随机存取。3.空串是 0个字符的串 ，其长度等于 0 ，空格串是 由一个或多个空格字符组成的串 ，其长度等于 空格字符个数 。
4.二叉树是特殊的树(x)
5.任意一棵二叉树的叶子结点在前序，中序后序遍历序列中的相对次序不变
6.在n个顶点的无向图中，若边数大于(n-1)(n-2)/2,则该图必是连通图。