null自考数据结构 串讲笔记
自考乐园版 课程代号：02331自考数据结构 串讲笔记
自考乐园版 课程代号：02331课程说明课程说明串讲目的
参考
教材
民兵爆破地雷教材pdf初中剪纸校本课程教材衍纸校本课程教材排球校本教材中国舞蹈家协会第四版四级教材
：
《数据结构》黄刘生主编
经济科学出版社更多优质自考
资料
新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单
尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........课程说明课程说明
知识点
高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载
：
线形表、栈、队列、数组、广义表、树、图、查找和排序。第一章 绪论第一章 绪论 §１．基本概念与术语
数据结构：
是一门研究非数值计算的程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
问题中计算机的操作对象及他们之间关系和操作等的学科。null（一）数据结构概念包括三个方面（三要素）
数据之间的逻辑关系（逻辑结构）
数据在计算机中的存储方式（存储结构）
实现数据操作的算法（数据的运算）（二）、相关术语（二）、相关术语 1、数据：
能输入计算机并能计算机程序处理的符号的总称。
2、数据元素：
数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。
3、数据对象：
具有相同性质的数据元素的集合，是数据的一个子集。null4、
（1）数据的逻辑结构：数据之间的关系。
A.集合（无顺序）：
B.线性结构（一对一）：
C.树形结构（一对多）：
D.网状、图结构（多对多）：null（２）数据的存储结构（物理结构）
数据结构在计算机中的表示。（２种）
A.顺序表示
借助数据在连续的存储空间中的相对位置表示元素关系。
B.链式表示
借助数据元素的存储地址的指针表示元素关系。§2.算法和算法分析§2.算法和算法分析一、算法
定义：是对特定问题求解步骤的一种描述，是指令的有限序列。
特点：
有穷性
确定性
可行性
零个或多个输入
一个或多个输出null大O表示法
大O表示同级别
例：f(n)=n2 ,f(n)=1/2(n(n-1)), f(n)=(n-1)(n+2)
均表示为：O(n2)
加法规则：若T1(n)=O(f1(n)), T2(n)=O(f2(n))
则两段程序连在一起的时间代价为:
T(n) =T1(n)+T2(n)
=O(max(f1(n),f2(n))例:例: 语句段 频度f(n) 时间复杂度T(n)
x=x+1 1 O(1)
for(j=1;j<=3n+5;j++) 3n+5 O(n)
x=x+1;
for(i=1;i<=3n;i++) 3n2 O(n2)
for(j=1;j<=n;j++)
x=x+1;
i=0; n+1 O(n)
while(x!=a[i] && i<=n)
i=i+1;求时间复杂度的原则求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。
平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........算法时间开销随时间规模变化趋势算法时间开销随时间规模变化趋势
nT(n)随n增大,T(n)增加快,算法坏随问题规模n增大,T(n)趋缓,算法好T(n)的增大趋势:
O(1)
0时，
线性表中各元素都有确定序号
线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素
（a1,a2,…,ai-1,ai,ai+1,…,an)无前驱直接前驱直接后继无后继第二章 线性表§2.线性表的顺序存储结构§2.线性表的顺序存储结构 一、线性表的顺序存储
在计算机内开辟一片连续空间（存储单元）依次存放表中所有元素。
设线性表为A（a1,a2,…,ai,…,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地址是Loc(a1)，则第i个元素的起始地址为：
Loc(ai)=Loc(a1)+(i-1)*La1a2…ai…an……连续空间§3.线性表的链式存储结构
一、单链表§3.线性表的链式存储结构
一、单链表 定义：
存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。
结点：DataPointer两个概念：两个概念： 头指针：
指示链表中第一个结点。
头结点：
在第一个结点之前附设的结点，其指针域指向链表中第一个结点。null 在链表中第i个结点前插入新结点b（前插）
算法分析：
基本操作：查找第i-1个元素
当1≤i≤n 频度为：i-1
当i>n(最坏，即i不合法) 频度为：n
T(n)=O(n)二、循环链表二、循环链表特点
尾结点的next指针指向头结点，可以设头结点和尾结点指针。
优点
可迅速找到头、尾结点。a1 an …HeadHead空表三、双向链表和双向循环链表三、双向链表和双向循环链表特点：
在结点中增加一个指向前趋的指针域。
优点：
可迅速找到结点前趋。
缺点：
增加存储空间。（每个结点增加了一个指针域）双向链表a1a2双向循环链表a2a12、基本操作2、基本操作（1）插入：在链表的x结点前插入元素e
步骤：
a.在链表中查找x结点
b.申请结点空间s，s->data=e
c.先做s->prior=p->prior;p->prior->next=s;
d.后做s->next=p;p->prior=s;axpes（本章结束）null（2）删除：删除双向循环链表中的结点x
步骤：
a.在链表中查找x结点
b.删除：p->prior->next=p->next;
p->next->prior=p->prior;
c.free(p)axcp第3章 栈与队列第3章 栈与队列§1.栈
一、栈的描述
1.栈的定义
2.栈的特点：后进先出（LIFO）
1,2,3,4顺序进栈，有多少种出栈的情况？
Sn=s0sn-1+s1Sn-2+…+sn-2s1+sn-1s0
S0=1,s1=1更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........例：例： 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ）
A.1，3，2，4
B.2，3，4，1
C.4，3，1，2
D.3，4，2，1 二、栈的表示和实现二、栈的表示和实现 1、栈的顺序存储结构——顺序栈
顺序栈：
开辟一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素。
设top指针指示栈顶元素的当前位置。基本操作基本操作栈示意图：CBAbasetop新元素入栈顶时：先入栈,
再移指针top=top+1
删除元素时：
先移指针top=top-1,
后删栈顶元素
栈的长度：top-base2、链栈2、链栈 定义：
采用链式存储结构的栈，并由其栈顶指针惟一确定。
设ls为栈顶指针，栈=(a1,a2,…,an)，a1为栈底元素，an为栈顶元素。an a2 a1 ……ls最迟入栈元最早入栈元§2.队列§2.队列一、队列描述
1、队列定义
2、队列特点：先进先出（FIFO）二、队列的顺序存储表示二、队列的顺序存储表示1、顺序队列
用一组地址连续的存储单元依次存放从队头到队尾的元素。
设队头指针为front，队尾指针为rear。
约定：当front=rear=0，表示空队列；
front指向队头元素；
rear指向队尾元素的下一个位置。2、循环队列2、循环队列 假想：
将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。frontrearMaxsize-10基本操作：基本操作：入队操作：
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE;
出队操作：
x=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;问题：
循环队列的队空、队满条件？问题：
循环队列的队空、队满条件？举例说明：
矛盾：
对空：front=rear
队满：front=rear
解决方法：
少用一个存储空间矛盾三、链队列三、链队列 定义：
用链表示的队列简称为链队列。
设两个指针front、rear分别指示队头和 队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：a1 an ……front队头元素队尾元素rear头结点§3.递归算法设计§3.递归算法设计 一、递归算法设计
递归过程：
一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。
直接递归调用
间接递归调用1、递归算法的设计思想1、递归算法的设计思想 分治思想：
对一个较大问题可分解成属性相同、规模较小的问题，在小问题求解之后，通过组合，求得原来较大问题的解。
递归定义：
基本项：描述递归过程的终结状态，即可直接求解状态。
归纳项：描述如何实现从当前状态到终结状态的转化，即子问题与原问题之间的转化。例1：求n!例1：求n! 用分治思想分析,得到递归定义:
基本项：当n=1时，f=1。（直接求解状态）
归纳项：如果能求得(n-1)!，原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同，只是规模小了。所以，归纳项是设法求(n-1)！。2、递归算法设计2、递归算法设计 在程序设计中，什么情况下使用递归算法进行程序设计呢？考虑以下三个方面的因素：
当问题的定义是递归的
解决问题的数据结构是递归的
解决问题的过程是递归的（本章结束）更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........第四章 串第四章 串 §１．基本概念与基本运算
一、串
1、串定义：有零个或n个字符构成的有限序列。
记为S=‘a1a2…an’(n>=0);其中S是串名, a1a2..an是串值，ai(i<=n 且 i>=1)可以是字母、字符、数字，n是串长度，当n=0时为空串。§2．串的存储结构§2．串的存储结构一、顺序存储结构
（或称静态存储结构：编译时进行空间分配）
定义：用一组地址连续的存储单元存储串的字符序列。
两种编址形式：
字节编址：一个字节存一个字符。(如早期的pc机)
字编址：一个字存一个字符。
非紧缩格式：每个字存放一个字符。
紧缩格式：每个字节存放一个字符。
C语言仅有紧缩格式：char str[max];null概念：存储密度
存储密度= 串值所占的存储位实际分配的存储位null顺序存储结构的特点
预先分配串最大长度，有可能造成存储密度低。
使串的某些操作受到很大限制。如置换、联接等操作。二、动态存储结构二、动态存储结构 （在运行时进行存储空间的分配）
定义：
用一组任意的存储单元（可以连续，可以不连续）存放串的字符序列。1、链式存储结构1、链式存储结构每个结点存放一个字符。
图示：
存储密度=1/(1+4)=20% (设指针占用4字节)
特点：密度低，存储空间利用率低，操作简单。
每个结点存放多个字符——块链结构。
图示：
存储密度=4/(4+4)=50% (设指针占用4字节)
特点：存储密度大，节省空间，操作复杂。
链式结构的特点：结点的选择非常重要。a b c rear a b c d e f g h i # # # ^ §3．串的模式匹配算法§3．串的模式匹配算法 模式匹配：
子串的定位操作通常称为串的模式匹配，是各种串处理系统中重要的操作之一。
Index(S,T,pos)
其中S为主串，T被称为模式串。
若T为S子串，则返回T在S中第pos个字符后首次出现的位置。
若T不为S子串，则返回0。模式匹配模式匹配：子串在主串中的定位操作(m<T[0]时说明匹配成功。
匹配成功的返回值：T中第一个字符在S中的位置。（本章结束）第五章 数组和广义表第五章 数组和广义表 §1.数组定义
一、数组定义（n维数组）
当n=1时，称为一维数组。
当n>2时，称为多维数组。一个n维数组是由若干个n-1维数组构成的。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........举例：二维数组m*n举例：二维数组m*n
a11 a12 … a1n
a21 a22 … a2n
………………….
am1 am2… amn
可以看成由若干个一维数组组成，这些一维数组或按行或按列向量构成Am*n=按列向量：按列向量：
a11 a12 … a1n
a21 a22 … a2n
………………….
am1 am2… amnAm*n=n个一维数组按行向量：按行向量：
a11 a12 … a1n
a21 a22 … a2n
………………….
am1 am2… amn
Am*n=((a11 a12…a1n),(a21 a22…a2n),…,(am1 am2 … amn))Am*n=m个一维数组§2.数组的顺序存储表示§2.数组的顺序存储表示 问题：
存储单元是一维的结构，而数组是多维结构，如何用一组连续存储空间存放数组的数据元素呢？
解决方法：
存储映射策略；
行优先存储；
列优先存储。null 数组元素满足1<=i<=m,1<=j<=n
设每个数据元素占L个存储单元，第一个元素a00存储地址是Loc(a00)，问aij在空间上的存储地址是什么？1、行优先存储1、行优先存储Loc(aij)=Loc(a00)+(i*n+j)*La00…a01a0n-1…am-10…am-1n-1nL假设：行、列的下界为0Loc(a00)2、列优先存储2、列优先存储Loc(aij)=Loc(a00)+(j*m+i)*L
a00…a10am-10…a0n-1…am-1n-1mL假设：行、列的下界为0Loc(a00)§3.矩阵的存储及运算§3.矩阵的存储及运算一、一般矩阵的存储
通常用二维数组存储矩阵。
特点：
矩阵中的每个元素占用二维数组中的相应位置。二、特殊矩阵的存储二、特殊矩阵的存储 特殊矩阵：
矩阵中相当一部分元素取值相同或都为0或元素在矩阵中分布有一定规律。
特殊矩阵的存储方式：通常采用压缩存储。
压缩存储：
为多个值相同的矩阵元只分配一个存储空间；对0元不分配空间。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........1、对称矩阵1、对称矩阵 定义：
对于一个n*n方阵，且aij=aji（1<=i<=n,1<=j<=n）,则称为对称矩阵。
特点：
矩阵中元素关于对角线元素对称。
存储方式：
采用三角存放法。即指存储对角线及对角线以下或对角线以下的元素。对于n阶对称矩阵，仅用n(n+1)/2个存储单元。null a11 a12 … a1n
a21 a22 … a2n
………………….
an1 an2 … ann
存储方式：按行优先
K= 1/2i(i-1)+(j-1) i>=j
1/2j(j-1)+(i-1) i=j
1/2n(n+1) i0时， 1, 2,…, n是满足线性有序关系的，且i可以是某一数据对象元素，也可以是一个表结构。前者称为原子，后者称为子表。（在表示习惯上，广义表名称用大写字母表示，原子用小写字母表示）
特点：
广义表的结构是递归的。举例：举例： 广义表 表长
LS1=() n=0(空表)
LS2=(a) n=1(只有原子)
LS3=(a,(b)) n=2
LS4=(a,b) n=2
LS5=(a,(b,(c))) n=2
F=(a,F) n=2(递归表)
广义表的术语：广义表的术语：当广义表非空时：
(1)广义表的表头：表中第一个元素；
(2)广义表的表尾：除了表头之外，表中其余元素构成的子表。
特点：
表头可以是原子或子表，而表尾一定是子表。举例：举例：LS=((a,b),c)
Head:(a,b) Tail:(c)
LS=(a)
Head: a Tail: () 空表
LS=((),(e),(a,(b,c,d)))
Head: () Tail: ((e),(a,(b,c,d)))
null广义表运算：设广义表LS= (1, 2,…, n)
取广义表表头 Head(LS)= 1
取广义表表尾 Tail(LS)= (2,…, n)二、求广义表深度二、求广义表深度1、广义表深度定义：广义表括号重数
例： LS=() 深度：1
LS=(()) 深度：2
LS=(a) 深度：1
LS=(a,(b,c)) 深度：2例：求E=(A,B,C)的深度例：求E=(A,B,C)的深度其中：A=(),B=(e),C=(a,(b,c,d))
解： Depth(E)=1+max{Depth(A),Depth(B),Depth(C)}
Depth(A)=1
Depth(B)=1+max{Depth(e)}=1
Depth(C)=1+max(Depth(a),Depth((b,c,d))}
Depth(a)=0
Depth((b,c,d))=1+max{Depth(b),Depth(C),Depth(d)}
=1
Depth(C)=1+max{0,1}=2
Depth(E)=1+max{1,1,2}=3（本章结束）第六章 树第六章 树§１．树的定义和术语
一、树的定义
二、树的术语
结点度、树的度、结点层次、树的深度、家族树、有序树。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........§2．二叉树§2．二叉树一、二叉树的相关概念
1、二叉树定义
树中每个结点至多有两棵子树，且子树有序。
（根据二叉树的定义，二叉树的结构是递归的）
2、二叉树的基本形态
二叉树有五种基本形态：null二叉树的基本形态：左子树右子树右子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点和左子树（4）有根结点和右子树（5）有根结点和左，右子树二、二叉树的性质二、二叉树的性质1、二叉树
性质1：
第i层上最多有2i-1个结点。
性质2：
深度为K的二叉树最多有2K-1个结点。
性质3：
设叶子（度为0）数为n0，度为2的结点数为n2，则n0=n2+1。2、满二叉树与完全二叉树2、满二叉树与完全二叉树 满二叉树：
深度为k，且有2k-1个结点。（对满二叉树中的结点约定编号：自根起，从上到下，从左到右）
完全二叉树：
仅允许最下层右侧分支不满，若按从上到下，从左到右为树中结点编号，则与满二叉树相同。
关系：
满二叉树是完全二叉树。
完全二叉树不一定是满二叉树。3、完全二叉树性质3、完全二叉树性质 性质4：
n个结点，深度为K的完全二叉树，其
K= log2n +1
性质5：
对一棵n个结点深度为K的完全二叉树上的结点按层次编码（从第一层到第K层，从左到右），则树中编号为i的结点(1<=i<=n)有：
a: 当i=1时，此点是根；
b: 当i>1时，i的双亲是 i/2 ；
c: 当2i>n时，i是叶点（无左孩子）；当2i<=n时，2i是i的左孩子；
d: 当2i+1>n时，i结点无右孩子；当2i+1<=n时，2i+1是i的右孩子。三、二叉树存储结构三、二叉树存储结构 1、顺序存储结构
用一维数组A作为二叉树的存储结构，A[i]表示编号为i的结点。特点：浪费存储空间特例：特例：深度为K，只有K个结点的单支树
需要2K-1个存储单元。（由二叉
树的性质2知，深度为K的二叉树
至多有2K-1个结点）。而真正有
用的只有K个空间，其它绝大多
数空间是空闲的。造成了存储空
间的极大浪费。顺序存储结构适用于完全二叉树：顺序存储结构适用于完全二叉树： 特点：
即不浪费空间，又可以快速确定其结点的位置；对已知的结点i，其左孩子为2i，右孩子为2i+1，双亲为 i/2 。完全二叉树结点在存储空间中的相对位置
恰好表现出了完全二叉树中结
点之间的关系。 2、链式存储结构2、链式存储结构 二叉链表：
链表中每个结点至少含有三个域：数据域、左指针域和右指针域。lchildDatarchild指向左孩子指向右孩子§3．二叉树的遍历§3．二叉树的遍历 一、遍历二叉树
遍历：
按一定次序访问二叉树上每个结点恰一次；
访问：
访问代表一次操作；
访问次序：
先左后右。并以访问根的次序不同分为不同的三种方式：先序、中序、后序。null先序：
先访问根结点，然后访问左子树，再访问右子树。
中序：
先访问左子树，然后访问根结点，再访问右子树。
后序：
先访问左子树，然后访问右子树，再访问根结点。例1：例1：先序：ABCDEFGHIJK
中序：CEDFBGAIKJH
后序：EFDCGBKJIHA例2：已知先序、中序可以惟一确定一棵二叉树例2：已知先序、中序可以惟一确定一棵二叉树已知：
中序：GDHBAECIF
先序：ABDGHCEFI例3：已知中序、后序可以惟一确定一棵二叉树例3：已知中序、后序可以惟一确定一棵二叉树已知：
中序：DBGEAHFIC
后序：DGEBHIFCA例4：已知先序、后序不能惟一确定一棵二叉树例4：已知先序、后序不能惟一确定一棵二叉树已知：
先序：A B
后序：B A两棵不同的二叉树以中序为例讨论二叉树的递归遍历算法：以中序为例讨论二叉树的递归遍历算法：中序遍历二叉树的递归算法分析：
中序：访问左子树 访问根 访问右子树
基值：bt=NULL(bt为二叉树的根结点指针)。当二叉树为空时。
归纳项：即是对子树（子树仍为二叉树）的遍历操作。
算法思想：
若二叉树为空，则遍历结束；否则遍历左子树
访问根结点
遍历右子树中序递归算法执行过程的简化展开图：中序递归算法执行过程的简化展开图： 每深入一层代表一次调用；退上一层代表一次返回；从左子树返回仅一层；接着访问根结点；从右子树返回，表明当前层遍历结束，可以连续返回。二、线索二叉树二、线索二叉树 1、什么是二叉树的线索化？
非线性结构的二叉树经过遍历（先序、中序、后序），结点排成线性有序（前趋、后继惟一）。但二叉树本身不具有这种信息，访问后即消失；为了保持在遍历过程中得到的前趋、后继信息，则需边遍历，边建立线索。
线索：即是指向前趋、后继结点的指针。
线索二叉树：加上线索的二叉树称为线索二叉树。
线索化：对二叉树进行遍历使其成为线索二叉树的过程称为二叉树的线索化。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2、怎样线索二叉树2、怎样线索二叉树(1)增加两个标志位
每个标志位仅占1个存储位(bit)
结点结构：
若LTag=0(Link),则lchild指向左孩子；
RTag=0(Link),则rchild指向右孩子；
若LTag=1(Thread),则lchild指向线索——前趋；
RTag=1(Thread),则rchild指向线索——后继。lchildLTagdataRTagrchild带头结点的中序线索链表：带头结点的中序线索链表：10A00B01F01C00E11D11G11二叉树的头指针Head§4．树和森林的存储与运算§4．树和森林的存储与运算 一、树的存储表示
1、双亲表示法（顺序存储结构）
开辟一组连续空间存储树的结点，每个结点中附设一个指示双亲结点的双亲域。CBADEABCDE-10003Data:Parent:特点：找结点双亲容易，但找孩子不容易012342、孩子表示法（链式存储结构）2、孩子表示法（链式存储结构）(1)按树的度设结点指针域
特点：
每个结点的结构一致，操作简单，但浪费存储空间。CBADEAB^^^C^^^D^^E^^^树的度=3null(2)按结点的度设结点指针域
特点：
每个结点的结构不一致，操作复杂，但节省存储空间。CBADEAB0C0D13E0null(3)按孩子结点排成线性表
特点：
节省空间，
操作也较容易；
问题：
这种结构不能
反映出树的层
次性特征。AB^C^DE^CBADE235^4^每个结点的孩子链表123453、孩子兄弟表示法（二叉树表示法）3、孩子兄弟表示法（二叉树表示法）在这种表示法中，树中每个结点有三个域：
数据域：存放结点数据
左指针域：指向该结点的第一个孩子结点
右指针域：指向该结点的右兄弟结点datafchnsibnull 特点：
便于实现树的各种操作，节省空间，并且能够描述树的层次结构。CBADEA^^B^CD^^E^二、森林与二叉树的转换二、森林与二叉树的转换 二叉树和树都可以用二叉链表作为其存储结构。因此，以二叉链表作为中间媒介，可以导出树与二叉树之间存在对应关系。
一棵树与惟一的一棵二叉树一一对应。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........举例:举例:CBADEA^^B^CD^^E^A^^B^CD^^E^CBADE树二叉树二叉树表示法二叉链表1、树转换成二叉树1、树转换成二叉树保持双亲和第一个孩子连线，其他连线去掉；
兄弟之间连线；
使右兄弟结点成为右孩子，使第一个孩子成为左孩子。2、森林转换为二叉树2、森林转换为二叉树将每棵树转化为二叉树；
将各棵二叉树的根相连；
使二叉树的根成为右孩子。3、二叉树转换成森林3、二叉树转换成森林 若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子、……，都与该结点的父结点用线线连；
去掉树中所有父结点到其右孩子的连线，生成森林。三、树与森林遍历三、树与森林遍历1、树的遍历
遍历规则：
(1)先根遍历：
先访问树根，再依次先根遍历根的每棵子树。
(2)后根遍历：
先依次后根遍历根的每棵子树，再访问树根。例：例：ABCDEF先根：ABCEFD
后根：BEFCDA树 二叉树（续上例）树 二叉树（续上例）ABCDEF先序：ABCEFD
中序：BEFCDA结论： （续上例）结论： （续上例）树的先根遍历相当于其转化的二叉树的先序遍历；
树的后根遍历相当于其转化的二叉树的中序遍历；2、森林的遍历2、森林的遍历(1)先序(先根)遍历森林
A.访问第一棵树的树根；
B.先序遍历第一棵树根的子树森林；
C.先序遍历除第一棵树之后,剩余的树构成的森林。ABCDEF先序：ABCDEFnull(2)中序(后根)遍历森林
A.中序遍历森林中第一棵树的根结点的子树森林；
B.访问第一棵树的根结点；
C.中序遍历除第一棵树之后剩余的树构成的森林。ABCDEF中序：BCDAFE例:例:CDEFHJ先根:ABCDEFGHJIK(二叉树的先序)
后根:BADEFCJHKIG(二叉树的中序)ABIKG森林转化的二叉树:森林转化的二叉树:CDEFHJABIKG§5．哈夫曼树及其应用§5．哈夫曼树及其应用一、概念和术语
1、路径
2、路径长度
3、结点的权
4、结点的带权路径长度
5、树的带权路径长度
6、哈夫曼树（续三）（续三） 例：
给定四个叶子结点a、b、c、d，分别带权0.1、0.1、0.4、0.4，由它们构成不同的带权二叉树，分别求WPL。0.10.10.40.4WPL=20.10.10.40.4WPL=1.80.10.10.40.4WPL=2.1二、哈夫曼树的构造二、哈夫曼树的构造 哈夫曼树构造算法: (P91)
根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。
在F中删除这两棵树，同时将新得到的二叉树加入F中。
重复（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。
例：给定权值{7，5，2，4}，构造哈夫曼树。前缀码前缀码 给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码。
例：
{000，001，01，10，11} ——前缀码
{0，1，10，11} ——不是前缀码
特点：
前缀码是码长不等的编码，既可以缩短报文的长度，又容易翻译。（本章结束）第七章 图第七章 图§１．基本概念与术语
一、图的定义
定义：
简单地说，图是由一些结点和连接两个结点之间的边组成。§2．图的存储表示和图的生成§2．图的存储表示和图的生成一、图的存储表示
1、邻接矩阵表示法（数组表示法）
用一维数组存储图中顶点的信息；
用矩阵（二维数组）表示图中各顶点之间的相邻关系。图的顺序存储结构 (1)邻接矩阵的定义(1)邻接矩阵的定义图G=(V,E),n个顶点，邻接矩阵用A[1..n,1..n]存放：
A[i][j]= 1 若或(vi,vj) E,ij
0 否则
对带权的图：
A[i][j]= wij 若或(vi,vj)E,ij,且权为wij
0 否则
(2)对称性(2)对称性无向图：
邻接矩阵对称，只需存入下三角（或上三角）,
所用空间为n(n+1)/2
有向图：
不一定对称，需n2个存储单元。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2、图的邻接表（图的一种链式存储结构）2、图的邻接表（图的一种链式存储结构）(1)无向图的邻接表vexdataFirstarc头结点：顶点指向与该顶点
邻接的第一个
邻接点adjvexnextarc表结点：邻接点在
图中的
位置指向下一个
邻接点null构造方法：
与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述；
各链表设置表头结点，由头结点描述；
各表头结点构成一个顺序表。(2)有向图的邻接表及其逆邻接表(2)有向图的邻接表及其逆邻接表邻接表（出度表）：
结点结构同无向图。
以vi为顶点的邻接点单链表上的结点都是以vi为弧尾的邻接点。
顺序表部分定义同无向图的邻接表。
逆邻接表（入度表）：
结点结构同无向图。
以vi为顶点的邻接点单链表上的结点都是以vi为弧头的邻接点。
顺序表部分定义同无向图的邻接表。§3．图的遍历§3．图的遍历 遍历：
按一定次序，由图的某一顶点出发，沿着图的边访问所有顶点恰一次。
设置访问标志数组：visited[i]
[1<=i<=n(n为图中顶点个数)]
False 表示未被访问
True 表示已被访问一、深度优先搜索（DFS）一、深度优先搜索（DFS） 搜索策略：
访问当前顶点vi，寻找与vi相邻且未被访问顶点vj，若存在，将其作为当前点，访问，并重复上述搜寻过程。
否则（所有邻接点都被访问过），退回一步，寻找与前一个顶点相邻的未被访问顶点，访问，并重复上述过程。
若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。
深度优先搜索是一种纵向搜索的过程。二、广度优先搜索（BFS）二、广度优先搜索（BFS） 搜索策略：
访问出发点v0，依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发重复上述过程。
若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。
广度优先搜索是一种横向搜索的过程。
使用队列结构。null 算法思想
从指定顶点出发，每访问一个顶点就把它排在队尾，然后从队头取出一个顶点，访问该顶点所有未被访问的邻接点，如此，直到队空。
若图中仍有未被访问的顶点，则另选一个顶点为出发点，重复上述过程。§4．生成树&最小生成树§4．生成树&最小生成树 一、生成树
1、定义：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。
2、算法思想：DFS或BFS生成树。二、最小生成树二、最小生成树 1、定义
连通网G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。将生成树的各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树。例：用Prim算法求最小生成树例：用Prim算法求最小生成树连通图如下所示：例：用克鲁斯卡尔算法求最小生成树例：用克鲁斯卡尔算法求最小生成树连通图如下所示：null§5．最短路径
一、单源最短路径问题§5．最短路径
一、单源最短路径问题 单源最短路径问题
给定带权有向图，求从指定源点到图中其余各点的最短路径。u0到其余各顶点的最短路径§6．拓扑排序§6．拓扑排序将集合中偏序关系变为全序关系称为拓扑排序。一、拓扑排序一、拓扑排序 1、相关概念
AOV网：顶点表示活动，弧表示活动间的优先关系的有向图。
在无回路的AOV网中，所有的活动可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前边，称此序列为拓扑序列，由AOV网构成拓扑序列的过程称为拓扑排序。拓扑排序算法思想：拓扑排序算法思想： 选择有向图中入度为0的顶点输出，并从图中删去该点相邻弧；
重复上述操作，直到图中全部顶点均被输出或图中已不存在入度为0的顶点（有回路）。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........实例：了解算法的执行过程实例：了解算法的执行过程求精算法
时间复杂度：T(n)=O(n+e)（本章结束） 第八章 内部排序 第八章 内部排序 排序（Sorting）是将任意顺序的序列重新排成按关键字有序的序列。
排序的目的之一是提高查找效率。
排序是数据处理领域中的常用运算。§2．排序概念§2．排序概念 趟（Pass）
实现一个元素的有序性所完成的操作。
稳定性
若在排序前两个
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
在序列中的关系为…Ri…Rj…，且Ri与Rj的关键字相同Keyi=Keyj，排序后若…Ri…Rj…称排序方法稳定，若…Rj…Ri…称排序方法不稳定。内部排序的相关概念内部排序的相关概念排序方法分类
插入排序
交换排序
选择排序
归并排序
基数排序
排序算法的关键操作
比较：比较两个关键字的大小。
移动：将记录从一个位置移动至另一个位置。§2．插入排序§2．插入排序 一、直接（简单）插入排序
基本思想：
每一趟都在已排好序的有序子表中插入一个元素，使有序子表不断扩大。
趟：
在含有i-1个记录的有序子表中，插入第i个元素成为含有i个元素的有序子表的过程。
算法实现：
引进监视哨的作用。null算法分析
空间：增加一个监视哨
时间
比较
最好情况（正序）：n-1次
最坏情况（逆序）：(n+2)(n-1)/2
移动
最好（正序）：2(n-1)
最坏（逆序）：(n+4)(n-1)/4
平均时间复杂度：O(n2)
稳定性：算法稳定二、希尔排序（Shell排序）二、希尔排序（Shell排序） 又称缩小增量排序，是直接插入排序的改进。
基本思想
将待排记录序列按增量dh值分成若干子表进行直接插入排序；然后缩小增量值，再分割，再排序，直至整个序列“基本有序”时，再对整个序列做一次直接插入排序。null算法分析
增量选取方法
增量序列不同，时间复杂度不同
稳定性：算法不稳定
希尔排序的特点§3．交换排序
一、起泡排序§3．交换排序
一、起泡排序 基本思想
相邻元素依次进行比较，小的前移，大的后移，第一趟结束后，最大元素放在了最后；再进行第二趟，使次大元放在最大元素之前；继续，直到在一趟排序中没有交换发生，排序结束。null算法分析
最好情况（正序）
比较次数：n-1
移动次数：0
最坏情况（逆序）
比较次数：
移动次数： n(n-1)
时间复杂度：O(n2)
稳定性：算法稳定二、快速排序二、快速排序 基本思想
每趟让待排表中的第一元素作支点，排序后入终位k，将原表一分为二，使得r[1]~r[k-1]中元素小于等于r[k]，而r[k+1]~r[n]中元素都大于等于r[k]，递归进行，直到表长为1时，排序结束。null一趟快速排序算法
支点放入x
附设两个指针i和j：初始i指向第一元，j指向第n元
从右向左，放过≥x.key元（比x大的元素），j变化，当r[j].keyx.key，放入j位置
直到i=j，一趟结束，i为x终位
locating the pivot
[49 38 65 97 76 13 27 49’]
i↑ j↑
[27 38 65 97 76 13 49’]
i↑ j↑
[27 38 65 97 76 13 49’]
i↑ j↑
[27 38 97 76 13 65 49’]
i↑ j↑
[27 38 13 97 76 65 49’]
i↑ j↑
[27 38 13 76 97 65 49’]
i↑ j↑
[27 38 13 49 76 97 65 49’]
i↑j↑
locating the pivot
[49 38 65 97 76 13 27 49’]
i↑ j↑
[27 38 65 97 76 13 49’]
i↑ j↑
[27 38 65 97 76 13 49’]
i↑ j↑
[27 38 97 76 13 65 49’]
i↑ j↑
[27 38 13 97 76 65 49’]
i↑ j↑
[27 38 13 76 97 65 49’]
i↑ j↑
[27 38 13 49 76 97 65 49’]
i↑j↑CS&T,BITIChapter 8null算法分析
时间效率
最坏情况：
当待排序的记录序列已经有序时，出现恶化趋势 ，Tworst(n)=O(n2)
最好情况：每次划分的两个子表的长度大致相等，支点入“中值”位，Tbest(n)=O(nlog2n)
平均情况：数据去无序，T(n)=Tpass(n)+T(k-1)+T(n-k)=O(nlnn)
空间效率
稳定性：不稳定§4．选择排序
一、简单选择排序§4．选择排序
一、简单选择排序 基本思想
每趟通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤i≤n)个记录交换之。
问题
简单选择排序与起泡排序在排序过程都须经过比较、交换而实现的，二者的有何区别？null算法分析
时间效率
比较次数： （无论正序、逆序、其他任意顺序）
移动次数：
最好情况(正序)：0次
最坏情况(非逆序，但每趟排序过程中都有交换发生): 3(n-1)
平均时间复杂度：O(n2)
空间效率：供交换用一个存储单元的辅助空间
稳定性：不稳定二、堆排序二、堆排序 堆排序的算法思想
1、建堆
将给定的原始待排序列建成一个初始堆。即先建成一棵完全二叉树，再从下往上筛选为堆。
首先由序列的第 结点开始与其孩子比，大的上小的下（交换），下去后若有孩子再比较，直到叶子
然后再由序列的第 结点起，重复上述过程，直到待排序列中的第一个结点。
建成逆堆。得到待排序列中的最大元（根结点），并输出之。
2、根结点与最后一片叶子交换。
3、若不是堆，则从根开始自上而下恢复成堆。
4、重复2、3步，直到剩下一个结点为止，排序结束。§5．归并排序§5．归并排序 归并排序是另一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表合成一个新的有序表。实现算法即可采用顺序存储结构，也可采用链式存储结构。1、归并概念1、归并概念将两个或两个以上的有序表合并成整体有序的大表。
归并分类
参加归并的有序表个数为2，称为2-路归并
参加归并的有序表个数为3，称为3-路归并
参加归并的有序表个数>3，称为多路归并2、2-路归并的基本思想2、2-路归并的基本思想 基本思想
对于n个元素的待排关键字序列，先分成长度为1的n个有序子表，两两归并，得到 个长度为2或1的有序子表；再对这 个有序子表进行两两归并；如此重复，直至得到一个长度为n的有序表。更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.baidu.com/club/5346389）
欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........3、算法分析3、算法分析时间效率
时间=一趟归并时间*归并趟数
=O(n) * log2n=O(n log2n)
空间效率：使用了一个辅助数组 O(n)
算法稳定性：稳定§6．基数排序§6．基数排序 基数排序借助多关键字排序的思想对单逻辑关键字进行排序，排序中不需要进行比较。一、多关键字排序一、多关键字排序 设n个记录{R1,R2,…,Rn}，Ri的关键字为（K ,K ,…,K ），d个关键字对任意记录Ri和Rj，若他们的关键字满足（ K ,K ,…,K ）<（ K ,K ,…,K ），则称该记录序列有序。null 举例
扑克牌按面值、花色排序。
多关键字排序方法
最高位优先法（MSD）：先按主关键字排序，再按次关键字排序。
最低位优先法（LSD）：先按次关键字排序，再按主关键字排序。
结论
无论MSD和LSD，都是采用若干次的“分配”与“收集”。
基数排序就是对单逻辑关键字采用“分配”与“收集”实现排序的方法。二、基数排序二、基数排序 基数排序是借助 “分配”与“收集”两种操作对单逻辑关键字采用进行排序的一种内部排序方法
单逻辑关键字：可以看成由若干分关键字复合而成
设关键字Keyi= K K K …K …K ，其中
K 称为分关键字；C0≤ K ≤ Crd-1(1≤i≤n,1≤l≤d)
d: 关键字的最大位数
rd: 基（分关键字可取值范围）（本章结束）第九章 查找第九章 查找§１．基本概念
一、对查找表的操作
1
浙公网安备 33021202002483