《自考数据结构串讲笔记课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构串讲笔记课件.ppt（210页珍藏版）》请在三一办公上搜索。
1、自考数据结构 串讲笔记自考乐园版 课程代号：02331,课程说明,串讲目的参考教材：数据结构黄刘生主编经济科学出版社,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,课程说明,知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。,第一章绪论,基本概念与术语数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。,（一）数据结构概念包括三个方面（三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构）实现数据操作的算法（数据的运算）,（二）、相关术语,1、数据：能输入计算机并能计算机程序处理的符
2、号的总称。2、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。,4、（1）数据的逻辑结构：数据之间的关系。A.集合（无顺序）：B.线性结构（一对一）：C.树形结构（一对多）：D.网状、图结构（多对多）：,（）数据的存储结构（物理结构）数据结构在计算机中的表示。（种）A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。,2.算法和算法分析,一、算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：有穷性确定性可行性零个或多个
3、输入一个或多个输出,大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+11O(1)for(j=1;j=3n+5;j+)3n+5O(n)x=x+1;for(i=1;i=3n;i+)3n2O(n2)for(j=1;j=n;j+)x=x+1;i=0;n+1O(n)while(x!=ai,求时间复杂度的原则,当
4、重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,算法时间开销随时间规模变化趋势,n,T(n),随n增大,T(n)增加快,算法坏,随问题规模n增大,T(n)趋缓,算法好,T(n)的增大趋势:O(1)O(log2n)O(n)O(nlog2n)O(n2)O(nk)O(2n)O(en),算法的存储空间需求,算法空间开销与输入形式无关时，仅考虑辅加空间开销。空间量依赖特定输入，讨论最坏情况下的空间开销。,（本章结束）,1.线性表的逻辑结构,一、线性结构线性表是n个数据元素的有限序
5、列当n=0时，称线性表为空表当n0时，线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素（a1,a2,ai-1,ai,ai+1,an),无前驱,直接前驱,直接后继,无后继,第二章线性表,2.线性表的顺序存储结构,一、线性表的顺序存储在计算机内开辟一片连续空间（存储单元）依次存放表中所有元素。设线性表为A（a1,a2,ai,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地址是Loc(a1)，则第i个元素的起始地址为：Loc(ai)=Loc(a1)+(i-1)*L,a1,a2,ai,an,连续空间,3.线性表的链式存储结构
6、一、单链表,定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：,Data,Pointer,两个概念：,头指针：指示链表中第一个结点。头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。,在链表中第i个结点前插入新结点b（前插）算法分析：基本操作：查找第i-1个元素当1in 频度为：i-1当in(最坏，即i不合法)频度为：nT(n)=O(n),二、循环链表,特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点可迅速找到头、尾结点。,a1,an,Head,Head,空表,三、双向
7、链表和双向循环链表,特点：在结点中增加一个指向前趋的指针域。优点：可迅速找到结点前趋。缺点：增加存储空间。（每个结点增加了一个指针域）,双向链表,a1,a2,双向循环链表,a2,a1,2、基本操作,（1）插入：在链表的x结点前插入元素e步骤：a.在链表中查找x结点b.申请结点空间s，s-data=ec.先做s-prior=p-prior;p-prior-next=s;d.后做s-next=p;p-prior=s;,a,x,p,e,s,（本章结束）,（2）删除：删除双向循环链表中的结点x步骤：a.在链表中查找x结点b.删除：p-prior-next=p-next;p-next-prior=p-p
8、rior;c.free(p),a,x,c,p,第3章栈与队列,1.栈一、栈的描述1.栈的定义2.栈的特点：后进先出（LIFO）1,2,3,4顺序进栈，有多少种出栈的情况？Sn=s0sn-1+s1Sn-2+sn-2s1+sn-1s0S0=1,s1=1,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,例：,一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）A.1，3，2，4B.2，3，4，1C.4，3，1，2D.3，4，2，1,二、栈的表示和实现,1、栈的顺序存储结构顺序栈顺序栈：开辟一组地址连续的存储单元，依次存放自栈底到栈顶的
9、数据元素。设top指针指示栈顶元素的当前位置。,基本操作,栈示意图：,C,B,A,base,top,新元素入栈顶时：先入栈,再移指针top=top+1删除元素时：先移指针top=top-1,后删栈顶元素 栈的长度：top-base,2、链栈,定义：采用链式存储结构的栈，并由其栈顶指针惟一确定。设ls为栈顶指针，栈=(a1,a2,an)，a1为栈底元素，an为栈顶元素。,an,a2,a1,ls,最迟入栈元,最早入栈元,2.队列,一、队列描述1、队列定义2、队列特点：先进先出（FIFO）,二、队列的顺序存储表示,1、顺序队列用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front
10、，队尾指针为rear。约定：当front=rear=0，表示空队列；front指向队头元素；rear指向队尾元素的下一个位置。,2、循环队列,假想：将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。,front,rear,Maxsize-1,0,基本操作：,入队操作：Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作：x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;,问题：循环队列的队空、队满条件？,举例说明：矛盾：对空：front=rear队满：front=rear解决方法：
11、少用一个存储空间,矛盾,三、链队列,定义：用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：,a1,an,front,队头元素,队尾元素,rear,头结点,3.递归算法设计,一、递归算法设计递归过程：一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。直接递归调用间接递归调用,1、递归算法的设计思想,分治思想：对一个较大问题可分解成属性相同、规模较小的问题，在小问题求解之后，通过组合，求得原来较大问题的解。递归定义：基本项：描述递归过程的终结状态，即可
12、直接求解状态。归纳项：描述如何实现从当前状态到终结状态的转化，即子问题与原问题之间的转化。,例1：求n!,用分治思想分析,得到递归定义:基本项：当n=1时，f=1。（直接求解状态）归纳项：如果能求得(n-1)!，原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同，只是规模小了。所以，归纳项是设法求(n-1)！。,2、递归算法设计,在程序设计中，什么情况下使用递归算法进行程序设计呢？考虑以下三个方面的因素：当问题的定义是递归的解决问题的数据结构是递归的解决问题的过程是递归的,（本章结束）,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,第四章串,基
13、本概念与基本运算一、串1、串定义：有零个或n个字符构成的有限序列。记为S=a1a2an(n=0);其中S是串名,a1a2.an是串值，ai(i=1)可以是字母、字符、数字，n是串长度，当n=0时为空串。,2串的存储结构,一、顺序存储结构（或称静态存储结构：编译时进行空间分配）定义：用一组地址连续的存储单元存储串的字符序列。两种编址形式：字节编址：一个字节存一个字符。(如早期的pc机)字编址：一个字存一个字符。非紧缩格式：每个字存放一个字符。紧缩格式：每个字节存放一个字符。C语言仅有紧缩格式：char strmax;,概念：存储密度存储密度=,串值所占的存储位,实际分配的存储位,顺序存储结构的特
14、点预先分配串最大长度，有可能造成存储密度低。使串的某些操作受到很大限制。如置换、联接等操作。,二、动态存储结构,（在运行时进行存储空间的分配）定义：用一组任意的存储单元（可以连续，可以不连续）存放串的字符序列。,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串的模式匹配算法,模式
15、匹配：子串的定位操作通常称为串的模式匹配，是各种串处理系统中重要的操作之一。Index(S,T,pos)其中S为主串，T被称为模式串。若T为S子串，则返回T在S中第pos个字符后首次出现的位置。若T不为S子串，则返回0。,模式匹配：子串在主串中的定位操作(mn)。t=t0 t1 t2 tn-1 目标 p=p0 p1 p2 pm-1 模式从目标t中查找与模式p完全相同子串的过程。朴素的模式匹配。,模式匹配,t,a,b,b,b,a,a,p,图3.3朴素的模式匹配过程,a b a,a b a,a b a,a b a,1、朴素的模式匹配,模式匹配的最简单的做法是：用p中的字符依次与t中的字符比较：如果
16、t0=p0，t1=p1，tm-1=pm-1，则匹配成功，调用求子串的操作subStr(t,1,m)即是找到的子串。否则必有某个i（0im-1），使得ti pi，这时可将p右移一个字符，用p中字符从头开始与t中字符依次比较；如此反复执行，直到下面两种情况之一：或者到达某步时，ti=p0，ti+1=p1，ti+m-1=pm-1，匹配成功，subStr(t,i+1,m)即是找到的（第一个）与模式p相同的子串；或者一直将p移到无法与t继续比较为止，则匹配失败。,说明：S串下次比较位置：i-j+2jT0时说明匹配成功。匹配成功的返回值：T中第一个字符在S中的位置。,（本章结束）,第五章数组和广义表,1.
17、数组定义一、数组定义（n维数组）当n=1时，称为一维数组。当n2时，称为多维数组。一个n维数组是由若干个n-1维数组构成的。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,举例：二维数组m*n,a11 a12 a1na21 a22 a2n.am1 am2 amn可以看成由若干个一维数组组成，这些一维数组或按行或按列向量构成,Am*n=,按列向量：,a11 a12 a1na21 a22 a2n.am1 am2 amn,Am*n=,n个一维数组,按行向量：,a11 a12 a1n a21 a22 a2n.am1 am2 amnAm*n=(a11 a12a1
18、n),(a21 a22a2n),(am1 am2 amn),Am*n=,m个一维数组,2.数组的顺序存储表示,问题：存储单元是一维的结构，而数组是多维结构，如何用一组连续存储空间存放数组的数据元素呢？解决方法：存储映射策略；行优先存储；列优先存储。,数组元素满足1=i=m,1=j=n设每个数据元素占L个存储单元，第一个元素a00存储地址是Loc(a00)，问aij在空间上的存储地址是什么？,1、行优先存储,Loc(aij)=Loc(a00)+(i*n+j)*L,a00,a01,a0n-1,am-10,am-1n-1,n,L,假设：行、列的下界为0,Loc(a00),2、列优先存储,Loc(ai
19、j)=Loc(a00)+(j*m+i)*L,a00,a10,am-10,a0n-1,am-1n-1,m,L,假设：行、列的下界为0,Loc(a00),3.矩阵的存储及运算,一、一般矩阵的存储通常用二维数组存储矩阵。特点：矩阵中的每个元素占用二维数组中的相应位置。,二、特殊矩阵的存储,特殊矩阵：矩阵中相当一部分元素取值相同或都为0或元素在矩阵中分布有一定规律。特殊矩阵的存储方式：通常采用压缩存储。压缩存储：为多个值相同的矩阵元只分配一个存储空间；对0元不分配空间。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,1、对称矩阵,定义：对于一个n*n方阵，且a
20、ij=aji（1=i=n,1=j=n）,则称为对称矩阵。特点：矩阵中元素关于对角线元素对称。存储方式：采用三角存放法。即指存储对角线及对角线以下或对角线以下的元素。对于n阶对称矩阵，仅用n(n+1)/2个存储单元。,a11 a12 a1n a21 a22 a2n.an1 an2 ann存储方式：按行优先K=1/2i(i-1)+(j-1)i=j1/2j(j-1)+(i-1)ij,An*n=,a11,a21,a22,a31,aij,an1,ann,k,2、三角矩阵,特征：n阶矩阵，对角线下（或上）的元素均为零或各元素相等于某一个常数C。存储方式：采用三角存放法。即指存储对角线及对角线以下的元素。除
21、此之外，在增加一个存储常数C的存储单元。对于n阶三角矩阵，仅用n(n+1)/2+1个存储单元。,a11 a21 a22 C.an1 an2 ann存储方式：按行优先K=1/2i(i-1)+(j-1)i=j1/2n(n+1)ij,An*n=,a11,a21,a22,a31,aij,an1,ann,k,C,3、对角线阵（对角矩阵）,特征：n*n方阵，若他的全部非0元都集中在以主对角线为中心的带状区域内。存储方式：压缩存储。,三、稀疏矩阵的存储及运算,稀疏矩阵：矩阵中的许多元素为0，并且0元素的个数远远大于非0元的个数。,1、三元组表,三元组表是稀疏矩阵的压缩存储方法之一，是顺序存储结构。稀疏矩阵中
22、的一个非0元用一个三元组(i,j,value)表示；其中：i表示该非0元在矩阵中的行号；j表示该非0元在矩阵中的列号；Value表示该非0元的值。整个矩阵中每个非0元的三元组共同构成该稀疏矩阵的三元组表。,3.广义表,一、广义表定义：设广义表LS=(1,2,n)，n是表长。(1)当n=0时，称广义表LS是空表；(2)当n0时，1,2,n是满足线性有序关系的，且i可以是某一数据对象元素，也可以是一个表结构。前者称为原子，后者称为子表。（在表示习惯上，广义表名称用大写字母表示，原子用小写字母表示）特点：广义表的结构是递归的。,举例：,广义表表长LS1=()n=0(空表)LS2=(a)n=1(只有原
23、子)LS3=(a,(b)n=2LS4=(a,b)n=2LS5=(a,(b,(c)n=2F=(a,F)n=2(递归表),广义表的术语：,当广义表非空时：(1)广义表的表头：表中第一个元素；(2)广义表的表尾：除了表头之外，表中其余元素构成的子表。特点：表头可以是原子或子表，而表尾一定是子表。,举例：,LS=(a,b),c)Head:(a,b)Tail:(c)LS=(a)Head:aTail:()空表LS=(),(e),(a,(b,c,d)Head:()Tail:(e),(a,(b,c,d),广义表运算：设广义表LS=(1,2,n)取广义表表头Head(LS)=1取广义表表尾Tail(LS)=(2
24、,n),二、求广义表深度,1、广义表深度定义：广义表括号重数例：LS=()深度：1LS=()深度：2LS=(a)深度：1LS=(a,(b,c)深度：2,例：求E=(A,B,C)的深度,其中：A=(),B=(e),C=(a,(b,c,d)解：Depth(E)=1+maxDepth(A),Depth(B),Depth(C)Depth(A)=1Depth(B)=1+maxDepth(e)=1Depth(C)=1+max(Depth(a),Depth(b,c,d)Depth(a)=0Depth(b,c,d)=1+maxDepth(b),Depth(C),Depth(d)=1Depth(C)=1+max
25、0,1=2 Depth(E)=1+max1,1,2=3,（本章结束）,第六章树,树的定义和术语一、树的定义二、树的术语结点度、树的度、结点层次、树的深度、家族树、有序树。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,2二叉树,一、二叉树的相关概念1、二叉树定义树中每个结点至多有两棵子树，且子树有序。（根据二叉树的定义，二叉树的结构是递归的）2、二叉树的基本形态二叉树有五种基本形态：,二叉树的基本形态：,左子树,右子树,右子树,左子树,（1）空二叉树,（2）只有一个根结点,（3）有根结点和左子树,（4）有根结点和右子树,（5）有根结点和左，右子树,二、
26、二叉树的性质,1、二叉树性质1：第i层上最多有2i-1个结点。性质2：深度为K的二叉树最多有2K-1个结点。性质3：设叶子（度为0）数为n0，度为2的结点数为n2，则n0=n2+1。,2、满二叉树与完全二叉树,满二叉树：深度为k，且有2k-1个结点。（对满二叉树中的结点约定编号：自根起，从上到下，从左到右）完全二叉树：仅允许最下层右侧分支不满，若按从上到下，从左到右为树中结点编号，则与满二叉树相同。关系：满二叉树是完全二叉树。完全二叉树不一定是满二叉树。,3、完全二叉树性质,性质4：n个结点，深度为K的完全二叉树，其K=log2n+1性质5：对一棵n个结点深度为K的完全二叉树上的结点按层次编码
27、（从第一层到第K层，从左到右），则树中编号为i的结点(11时，i的双亲是 i/2；c:当2in时，i是叶点（无左孩子）；当2in时，i结点无右孩子；当2i+1=n时，2i+1是i的右孩子。,三、二叉树存储结构,1、顺序存储结构用一维数组A作为二叉树的存储结构，Ai表示编号为i的结点。,特点：浪费存储空间,特例：,深度为K，只有K个结点的单支树需要2K-1个存储单元。（由二叉树的性质2知，深度为K的二叉树至多有2K-1个结点）。而真正有用的只有K个空间，其它绝大多数空间是空闲的。造成了存储空间的极大浪费。,顺序存储结构适用于完全二叉树：,特点：即不浪费空间，又可以快速确定其结点的位置；对已知的结
28、点i，其左孩子为2i，右孩子为2i+1，双亲为 i/2。,完全二叉树,结点在存储空间中的相对位置恰好表现出了完全二叉树中结点之间的关系。,2、链式存储结构,二叉链表：链表中每个结点至少含有三个域：数据域、左指针域和右指针域。,lchild,Data,rchild,指向左孩子,指向右孩子,3二叉树的遍历,一、遍历二叉树遍历：按一定次序访问二叉树上每个结点恰一次；访问：访问代表一次操作；访问次序：先左后右。并以访问根的次序不同分为不同的三种方式：先序、中序、后序。,先序：先访问根结点，然后访问左子树，再访问右子树。中序：先访问左子树，然后访问根结点，再访问右子树。后序：先访问左子树，然后访问右子树
29、，再访问根结点。,例1：,先序：ABCDEFGHIJK中序：CEDFBGAIKJH后序：EFDCGBKJIHA,例2：已知先序、中序可以惟一确定一棵二叉树,已知：中序：GDHBAECIF先序：ABDGHCEFI,例3：已知中序、后序可以惟一确定一棵二叉树,已知：中序：DBGEAHFIC后序：DGEBHIFCA,例4：已知先序、后序不能惟一确定一棵二叉树,已知：先序：A B后序：B A,两棵不同的二叉树,以中序为例讨论二叉树的递归遍历算法：,中序遍历二叉树的递归算法分析：中序：访问左子树 访问根 访问右子树基值：bt=NULL(bt为二叉树的根结点指针)。当二叉树为空时。归纳项：即是对子树（子树
30、仍为二叉树）的遍历操作。算法思想：若二叉树为空，则遍历结束；否则,遍历左子树访问根结点遍历右子树,中序递归算法执行过程的简化展开图：,每深入一层代表一次调用；退上一层代表一次返回；从左子树返回仅一层；接着访问根结点；从右子树返回，表明当前层遍历结束，可以连续返回。,二、线索二叉树,1、什么是二叉树的线索化？非线性结构的二叉树经过遍历（先序、中序、后序），结点排成线性有序（前趋、后继惟一）。但二叉树本身不具有这种信息，访问后即消失；为了保持在遍历过程中得到的前趋、后继信息，则需边遍历，边建立线索。线索：即是指向前趋、后继结点的指针。线索二叉树：加上线索的二叉树称为线索二叉树。线索化：对二叉树进行
31、遍历使其成为线索二叉树的过程称为二叉树的线索化。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,2、怎样线索二叉树,(1)增加两个标志位每个标志位仅占1个存储位(bit)结点结构：若LTag=0(Link),则lchild指向左孩子；RTag=0(Link),则rchild指向右孩子；若LTag=1(Thread),则lchild指向线索前趋；RTag=1(Thread),则rchild指向线索后继。,lchild,LTag,data,RTag,rchild,带头结点的中序线索链表：,1,0,A,0,0,B,0,1,F,0,1,C,0,0,E,1,1,
32、D,1,1,G,1,1,二叉树的头指针Head,4树和森林的存储与运算,一、树的存储表示1、双亲表示法（顺序存储结构）开辟一组连续空间存储树的结点，每个结点中附设一个指示双亲结点的双亲域。,C,B,A,D,E,A,B,C,D,E,-1,0,0,0,3,Data:,Parent:,特点：找结点双亲容易，但找孩子不容易,0,1,2,3,4,2、孩子表示法（链式存储结构）,(1)按树的度设结点指针域特点：每个结点的结构一致，操作简单，但浪费存储空间。,C,B,A,D,E,A,B,C,D,E,树的度=3,(2)按结点的度设结点指针域特点：每个结点的结构不一致，操作复杂，但节省存储空间。,C,B,A,D
33、,E,A,B,0,C,0,D,1,3,E,0,(3)按孩子结点排成线性表特点：节省空间，操作也较容易；问题：这种结构不能反映出树的层次性特征。,A,B,C,D,E,C,B,A,D,E,2,3,5,4,每个结点的孩子链表,1,2,3,4,5,3、孩子兄弟表示法（二叉树表示法）,在这种表示法中，树中每个结点有三个域：数据域：存放结点数据左指针域：指向该结点的第一个孩子结点右指针域：指向该结点的右兄弟结点,data,fch,nsib,特点：便于实现树的各种操作，节省空间，并且能够描述树的层次结构。,C,B,A,D,E,A,B,C,D,E,二、森林与二叉树的转换,二叉树和树都可以用二叉链表作为其存储结
34、构。因此，以二叉链表作为中间媒介，可以导出树与二叉树之间存在对应关系。一棵树与惟一的一棵二叉树一一对应。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,举例:,C,B,A,D,E,A,B,C,D,E,A,B,C,D,E,C,B,A,D,E,树,二叉树,二叉树表示法,二叉链表,1、树转换成二叉树,保持双亲和第一个孩子连线，其他连线去掉；兄弟之间连线；使右兄弟结点成为右孩子，使第一个孩子成为左孩子。,2、森林转换为二叉树,将每棵树转化为二叉树；将各棵二叉树的根相连；使二叉树的根成为右孩子。,3、二叉树转换成森林,若某结点是其父结点的左孩子，则把该结点的右孩
35、子、右孩子的右孩子、，都与该结点的父结点用线线连；去掉树中所有父结点到其右孩子的连线，生成森林。,三、树与森林遍历,1、树的遍历遍历规则：(1)先根遍历：先访问树根，再依次先根遍历根的每棵子树。(2)后根遍历：先依次后根遍历根的每棵子树，再访问树根。,例：,A,B,C,D,E,F,先根：ABCEFD后根：BEFCDA,树 二叉树（续上例）,A,B,C,D,E,F,先序：ABCEFD中序：BEFCDA,结论：（续上例）,树的先根遍历相当于其转化的二叉树的先序遍历；树的后根遍历相当于其转化的二叉树的中序遍历；,2、森林的遍历,(1)先序(先根)遍历森林A.访问第一棵树的树根；B.先序遍历第一棵树根
36、的子树森林；C.先序遍历除第一棵树之后,剩余的树构成的森林。,A,B,C,D,E,F,先序：ABCDEF,(2)中序(后根)遍历森林A.中序遍历森林中第一棵树的根结点的子树森林；B.访问第一棵树的根结点；C.中序遍历除第一棵树之后剩余的树构成的森林。,A,B,C,D,E,F,中序：BCDAFE,例:,C,D,E,F,H,J,先根:ABCDEFGHJIK(二叉树的先序)后根:BADEFCJHKIG(二叉树的中序),A,B,I,K,G,森林转化的二叉树:,C,D,E,F,H,J,A,B,I,K,G,5哈夫曼树及其应用,一、概念和术语1、路径2、路径长度3、结点的权4、结点的带权路径长度5、树的带权
37、路径长度6、哈夫曼树,（续三）,例：给定四个叶子结点a、b、c、d，分别带权0.1、0.1、0.4、0.4，由它们构成不同的带权二叉树，分别求WPL。,0.1,0.1,0.4,0.4,WPL=2,0.1,0.1,0.4,0.4,WPL=1.8,0.1,0.1,0.4,0.4,WPL=2.1,二、哈夫曼树的构造,哈夫曼树构造算法:(P91)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树上根结点的权值之
38、和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。例：给定权值7，5，2，4，构造哈夫曼树。,前缀码,给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码。例：000，001，01，10，11 前缀码0，1，10，11 不是前缀码特点：前缀码是码长不等的编码，既可以缩短报文的长度，又容易翻译。,（本章结束）,第七章图,基本概念与术语一、图的定义定义：简单地说，图是由一些结点和连接两个结点之间的边组成。,2图的存储表示和图的生成,一、图的存储表示1、邻接矩阵表示法（数组表示法）用一维数组存储图中顶点的
39、信息；用矩阵（二维数组）表示图中各顶点之间的相邻关系。,图的顺序存储结构,(1)邻接矩阵的定义,图G=(V,E),n个顶点，邻接矩阵用A1.n,1.n存放：Aij=1若或(vi,vj)E,ij 0 否则对带权的图：Aij=wij若或(vi,vj)E,ij,且权为wij 0 否则,(2)对称性,无向图：邻接矩阵对称，只需存入下三角（或上三角）,所用空间为n(n+1)/2有向图：不一定对称，需n2个存储单元。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,2、图的邻接表（图的一种链式存储结构）,(1)无向图的邻接表,vexdata,Firstarc,头结点
40、：,顶点,指向与该顶点邻接的第一个邻接点,adjvex,nextarc,表结点：,邻接点在图中的位置,指向下一个邻接点,构造方法：与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述；各链表设置表头结点，由头结点描述；各表头结点构成一个顺序表。,(2)有向图的邻接表及其逆邻接表,邻接表（出度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧尾的邻接点。顺序表部分定义同无向图的邻接表。逆邻接表（入度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧头的邻接点。顺序表部分定义同无向图的邻接表。,3图的遍历,遍历：按一定次序，由图的某一顶点出发，沿着图的
41、边访问所有顶点恰一次。设置访问标志数组：visitedi 1=i=n(n为图中顶点个数)False表示未被访问True表示已被访问,一、深度优先搜索（DFS）,搜索策略：访问当前顶点vi，寻找与vi相邻且未被访问顶点vj，若存在，将其作为当前点，访问，并重复上述搜寻过程。否则（所有邻接点都被访问过），退回一步，寻找与前一个顶点相邻的未被访问顶点，访问，并重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。深度优先搜索是一种纵向搜索的过程。,二、广度优先搜索（BFS）,搜索策略：访问出发点v0，依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发重复上述过程。若上
42、述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。广度优先搜索是一种横向搜索的过程。使用队列结构。,算法思想从指定顶点出发，每访问一个顶点就把它排在队尾，然后从队头取出一个顶点，访问该顶点所有未被访问的邻接点，如此，直到队空。若图中仍有未被访问的顶点，则另选一个顶点为出发点，重复上述过程。,4生成树&最小生成树,一、生成树1、定义：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。2、算法思想：DFS或BFS生成树。,二、最小生成树,1、定义连通网G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。将生成树的各边的权值总和称为生成树的权，并把权最小的生成树
43、称为G的最小生成树。,例：用Prim算法求最小生成树,连通图如下所示：,例：用克鲁斯卡尔算法求最小生成树,连通图如下所示：,5最短路径一、单源最短路径问题,单源最短路径问题给定带权有向图，求从指定源点到图中其余各点的最短路径。,u0到其余各顶点的最短路径,6拓扑排序,将集合中偏序关系变为全序关系称为拓扑排序。,一、拓扑排序,1、相关概念AOV网：顶点表示活动，弧表示活动间的优先关系的有向图。在无回路的AOV网中，所有的活动可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前边，称此序列为拓扑序列，由AOV网构成拓扑序列的过程称为拓扑排序。,拓扑排序算法思想：,选择有向图中入度为0的
44、顶点输出，并从图中删去该点相邻弧；重复上述操作，直到图中全部顶点均被输出或图中已不存在入度为0的顶点（有回路）。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.,实例：了解算法的执行过程,求精算法时间复杂度：T(n)=O(n+e),（本章结束）,第八章内部排序,排序（Sorting）是将任意顺序的序列重新排成按关键字有序的序列。排序的目的之一是提高查找效率。排序是数据处理领域中的常用运算。,2排序概念,趟（Pass）实现一个元素的有序性所完成的操作。稳定性若在排序前两个记录在序列中的关系为RiRj，且Ri与Rj的关键字相同Keyi=Keyj，排序后若Ri
45、Rj称排序方法稳定，若RjRi称排序方法不稳定。,内部排序的相关概念,排序方法分类插入排序交换排序选择排序归并排序基数排序排序算法的关键操作比较：比较两个关键字的大小。移动：将记录从一个位置移动至另一个位置。,2插入排序,一、直接（简单）插入排序基本思想：每一趟都在已排好序的有序子表中插入一个元素，使有序子表不断扩大。趟：在含有i-1个记录的有序子表中，插入第i个元素成为含有i个元素的有序子表的过程。算法实现：引进监视哨的作用。,算法分析空间：增加一个监视哨时间比较最好情况（正序）：n-1次最坏情况（逆序）：(n+2)(n-1)/2移动最好（正序）：2(n-1)最坏（逆序）：(n+4)(n-1
46、)/4平均时间复杂度：O(n2)稳定性：算法稳定,二、希尔排序（Shell排序）,又称缩小增量排序，是直接插入排序的改进。基本思想将待排记录序列按增量dh值分成若干子表进行直接插入排序；然后缩小增量值，再分割，再排序，直至整个序列“基本有序”时，再对整个序列做一次直接插入排序。,算法分析增量选取方法增量序列不同，时间复杂度不同稳定性：算法不稳定希尔排序的特点,3交换排序一、起泡排序,基本思想相邻元素依次进行比较，小的前移，大的后移，第一趟结束后，最大元素放在了最后；再进行第二趟，使次大元放在最大元素之前；继续，直到在一趟排序中没有交换发生，排序结束。,算法分析最好情况（正序）比较次数：n-1移
47、动次数：0最坏情况（逆序）比较次数：移动次数：n(n-1)时间复杂度：O(n2)稳定性：算法稳定,二、快速排序,基本思想每趟让待排表中的第一元素作支点，排序后入终位k，将原表一分为二，使得r1rk-1中元素小于等于rk，而rk+1rn中元素都大于等于rk，递归进行，直到表长为1时，排序结束。,一趟快速排序算法支点放入x附设两个指针i和j：初始i指向第一元，j指向第n元从右向左，放过x.key元（比x大的元素），j变化，当rj.keyx.key，放入j位置直到i=j，一趟结束，i为x终位,locating the pivot 4938659776132749 ij 273865977613 49
48、ij 273865977613 49ij 2738 9776136549ij 2738139776 6549ij 273813 76976549 ij 2738134976976549 ij,CS&T,BITI,Chapter 8,算法分析时间效率最坏情况：当待排序的记录序列已经有序时，出现恶化趋势，Tworst(n)=O(n2)最好情况：每次划分的两个子表的长度大致相等，支点入“中值”位，Tbest(n)=O(nlog2n)平均情况：数据去无序，T(n)=Tpass(n)+T(k-1)+T(n-k)=O(nlnn)空间效率稳定性：不稳定,4选择排序一、简单选择排序,基本思想每趟通过n-i次关
49、键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1in)个记录交换之。问题简单选择排序与起泡排序在排序过程都须经过比较、交换而实现的，二者的有何区别？,算法分析时间效率比较次数：（无论正序、逆序、其他任意顺序）移动次数：最好情况(正序)：0次最坏情况(非逆序，但每趟排序过程中都有交换发生):3(n-1)平均时间复杂度：O(n2)空间效率：供交换用一个存储单元的辅助空间稳定性：不稳定,二、堆排序,堆排序的算法思想1、建堆将给定的原始待排序列建成一个初始堆。即先建成一棵完全二叉树，再从下往上筛选为堆。首先由序列的第 结点开始与其孩子比，大的上小的下（交换），下去后若有孩子再比较
50、，直到叶子然后再由序列的第 结点起，重复上述过程，直到待排序列中的第一个结点。建成逆堆。得到待排序列中的最大元（根结点），并输出之。2、根结点与最后一片叶子交换。3、若不是堆，则从根开始自上而下恢复成堆。4、重复2、3步，直到剩下一个结点为止，排序结束。,5归并排序,归并排序是另一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表合成一个新的有序表。实现算法即可采用顺序存储结构，也可采用链式存储结构。,1、归并概念,将两个或两个以上的有序表合并成整体有序的大表。归并分类参加归并的有序表个数为2，称为2-路归并参加归并的有序表个数为3，称为3-路归并参加归并的有序表个数3，称为多路归并,
