自考数据结构-串讲笔记复习进程.ppt

《自考数据结构-串讲笔记复习进程.ppt》由会员分享，可在线阅读，更多相关《自考数据结构-串讲笔记复习进程.ppt（210页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自考数据结构-串讲笔记课程说明课程说明知识点：知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。第一章绪论第一章绪论基本概念与术语基本概念与术语数据结构：数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。（一）数据结构概念包括三个方面（一）数据结构概念包括三个方面（三要素三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构）实现数据操作的算法（数据的运算）（二）、相关术语（二）、相关术语1 1、数据：、数据：能输入计算机并能计算机程序处理的符号的总称。2 2、数据元素：、数据元素：数据的基本单位。可以进一步细分为若干数据项

2、，数据项是最小单位，不能再细分。3 3、数据对象：、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。4 4、（1 1）数据的逻辑结构：）数据的逻辑结构：数据之间的关系。数据之间的关系。A.A.集合（无顺序）：集合（无顺序）：B.B.线性结构（一对一）：线性结构（一对一）：C.C.树形结构（一对多）：树形结构（一对多）：D.D.网状、图结构（多对多）：网状、图结构（多对多）：（）数据的存储结构（物理结构）（）数据的存储结构（物理结构）数据结构在计算机中的表示。（种）A.A.顺序表示顺序表示借助数据在连续连续的存储空间中的相对位置表示元素关系。B.B.链式表示链式表示借助数据元素的存储地

3、址的指针指针表示元素关系。2.2.算法和算法分析算法和算法分析一、算法一、算法定义：定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：特点：有穷性确定性可行性零个或多个输入一个或多个输出大大O 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)f(n)时间复杂度时间复杂度T(n)T(n)x=x+11O(1

4、)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&i=n)i=i+1;求时间复杂度的原则求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ n增大增大,T(n)T(n)增加快增加快,算法坏算法坏随问题规模随问题规模n n增大增大,T(n)T(n)趋缓趋缓,算法好算法好T(n)T(n)的增大趋势的增大趋势:O(1)O(log2n)O(n)

5、O(nlog2n)O(n2)O(nk)O(2n)O(en)0时，线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素（a a1 1,a,a2 2,a,ai-1i-1,a,ai i,a,ai+1i+1,a,an n)无前驱无前驱直接前驱直接前驱直接后继直接后继无后继无后继第二章线性表第二章线性表2.2.线性表的顺序存储结构线性表的顺序存储结构一、线性表的顺序存储一、线性表的顺序存储在计算机内开辟一片连续连续空间（存储单元）依次存放表中所有元素。设线性表为A（a1,a2,ai,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地

6、址是Loc(a1)，则第i个元素的起始地址为：Loc(ai)=Loc(a1)+(i-1)*LLoc(ai)=Loc(a1)+(i-1)*La1 a2 ai an连续空间连续空间3.3.线性表的链式存储结构线性表的链式存储结构一、单链表一、单链表定义定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：结点：DataPointer两个概念：两个概念：头指针头指针：指示链表中第一个结点。头结点头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。在链表中第i个结点前插入新结点b（前插）算法分析：算法

7、分析：基本操作：查找第i-1个元素当1in 频度为：i-1当in(最坏，即i不合法)频度为：nT(n)=O(n)二、循环链表二、循环链表特点特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点优点可迅速找到头、尾结点。a1 an HeadHead空表空表三、双向链表和双向循环链表三、双向链表和双向循环链表特点：特点：在结点中增加一个指向前趋的指针域。优点：优点：可迅速找到结点前趋。缺点：缺点：增加存储空间。（每个结点增加了一个指针域）双向链表双向链表a1a2双向循环链表双向循环链表a2a12 2、基本操作、基本操作（1 1）插入）插入：在链表的x结点前插入元素e步骤：步骤：a.在

8、链表中查找x结点b.申请结点空间s，s-data=ec.先做s-prior=p-prior;p-prior-next=s;d.后做s-next=p;p-prior=s;axpes（本章结束）（2 2）删除）删除：删除双向循环链表中的结点x步骤：步骤：a.在链表中查找x结点b.删除：p-prior-next=p-next;p-next-prior=p-prior;c.free(p)axcp第第3 3章栈与队列章栈与队列1.1.栈栈一、栈的描述一、栈的描述1.1.栈的定义栈的定义2.2.栈的特点栈的特点：后进先出（后进先出（LIFOLIFO）1,2,3,41,2,3,4顺序进栈，有多少种出栈的情况

9、？顺序进栈，有多少种出栈的情况？S Sn n=s=s0 0s sn-1n-1+s+s1 1S Sn-2n-2+s+sn-2n-2s s1 1+s+sn-1n-1s s0 0S S0 0=1,s=1,s1 1=1=1更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、栈的顺序存储结构、栈的顺序存储结构顺序栈顺序栈顺序栈：顺序栈：开辟一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素。设top指针指示栈顶元素的当前位置。基本操作基本操作栈示意图栈示意图：CBAbasetop新元素入栈顶时：先入栈,再移指针top=top+1删除元素时：先移指针top=top-1,后删栈顶元素 栈的长度

10、：top-base2 2、链栈、链栈定义：定义：采用链式存储结构的栈，并由其栈顶指针惟一确定。设ls为栈顶指针，栈=(a1,a2,an)，a1为栈底元素，an为栈顶元素。an a2 a1 ls最迟入栈元最早入栈元2.2.队列队列一、队列描述一、队列描述1 1、队列定义、队列定义2 2、队列特点：、队列特点：先进先出（先进先出（FIFOFIFO）二、队列的顺序存储表示二、队列的顺序存储表示1 1、顺序队列、顺序队列用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front，队尾指针为rear。约定：当front=rear=0，表示空队列；front指向队头元素；rear指向队尾元

11、素的下一个位置。2 2、循环队列、循环队列假想：假想：将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。frontrearMaxsize-10基本操作：基本操作：入队操作：入队操作：Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作：出队操作：x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;问题：问题：循环队列的队空、队满条件？循环队列的队空、队满条件？举例说明：举例说明：矛盾：矛盾：对空：对空：front=rear队满：队满：front=rear解决方法：解决方法：少用一个存

12、储空间矛盾三、链队列三、链队列定义：定义：用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：a1 an front队头元素队尾元素rear头结点3.3.递归算法设计递归算法设计一、递归算法设计一、递归算法设计递归过程：递归过程：一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。直接递归调用间接递归调用1 1、递归算法的设计思想、递归算法的设计思想分治思想：分治思想：对一个较大问题可分解成属性相同、规模较小的问题，在小问题求解之后，通过组合，求得原来较

13、大问题的解。递归定义：递归定义：基本项：基本项：描述递归过程的终结状态，即可直接求解状态。归纳项：归纳项：描述如何实现从当前状态到终结状态的转化，即子问题与原问题之间的转化。例例1 1：求：求n!n!用分治思想分析,得到递归定义:基本项：基本项：当n=1时，f=1。（直接求解状态）归纳项：归纳项：如果能求得(n-1)!，原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同，只是规模小了。所以，归纳项是设法求(n-1)！。2 2、递归算法设计、递归算法设计在程序设计中，什么情况下使用递归算法进行程序设计呢？在程序设计中，什么情况下使用递归算法进行程序设计呢？考虑考虑以下三个方面的因素：以下

14、三个方面的因素：当问题的定义是递归的解决问题的数据结构是递归的解决问题的过程是递归的（本章结束）更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、串定义、串定义：有零个或：有零个或n n个字符构成的有限序列。个字符构成的有限序列。记为S=a1a2an(n=0);其中S是串名,a1a2.an是串值，ai(i=1)可以是字母、字符、数字，n是串长度，当n=0时为空串。22串的存储结构串的存储结构一、顺序存储结构一、顺序存储结构（或称静态存储结构：编译时进行空间分配）定义：定义：用一组地址连续地址连续的存储单元存储串的字符序列。两种编址形式：两种编址形式：字节编址：字节编址：一个字节字节

15、存一个字符。(如早期的pc机)字编址：字编址：一个字字存一个字符。非紧缩格式：非紧缩格式：每个字存放一个字符。紧缩格式：紧缩格式：每个字节存放一个字符。C C语言仅有紧缩格式：语言仅有紧缩格式：char strmax;char strmax;概念：存储密度概念：存储密度 存储密度存储密度=串值所占的存储位实际分配的存储位顺序存储结构的特点顺序存储结构的特点预先分配串最大长度，有可能造成存储密度低。使串的某些操作受到很大限制。如置换、联接等操作。二、动态存储结构二、动态存储结构（在运行时进行存储空间的分配）定义：定义：用一组任意的存储单元（可以连续，可以不连续）存放串的字符序列。1 1、链式存储

16、结构、链式存储结构每个结点存放一个字符。图示：图示：存储密度=1/(1+4)=20%(设指针占用4字节)特点：特点：密度低，存储空间利用率低，操作简单。每个结点存放多个字符块链结构。图示：图示：存储密度=4/(4+4)=50%(设指针占用4字节)特点：特点：存储密度大，节省空间，操作复杂。链式结构的特点：结点的选择非常重要。a b c rear a b c d e f g h i#33串的模式匹配算法串的模式匹配算法模式匹配：模式匹配：子串的定位操作通常称为串的模式匹配，是各种串处理系统中重要的操作之一。Index(S,T,pos)其中S为主串，T被称为模式串。模式串。若T为S子串，则返回T在

17、S中第pos个字符后首次出现的位置。若T不为S子串，则返回0。模式匹配模式匹配：子串在主串中的定位操作(mT0时说明匹配成功。匹配成功的返回值：T中第一个字符在S中的位置。（本章结束）第五章数组和广义表第五章数组和广义表1.1.数组定义数组定义一、数组定义（一、数组定义（n n维数组）维数组）当n=1时，称为一维数组。当n2时，称为多维数组。一个n维数组是由若干个n-1维数组构成的。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ a12 a1na21 a22 a2n.am1 am2 amn可以看成由若干个一维数组组成，这些一维数组或按行或按列向量构成可以看成由若干个一维数组组成，这些

18、一维数组或按行或按列向量构成Am*n=按列向量：按列向量：a11 a12 a1na21 a22 a2n.am1 am2 amnAm*n=n n个一维数组个一维数组按行向量：按行向量：a11 a12 a1n a21 a22 a2n .am1 am2 amnAm*n=(a11 a12a1n),(a21 a22a2n),(am1 am2 amn)Am*n=m m个一维数组个一维数组2.2.数组的顺序存储表示数组的顺序存储表示问题：问题：存储单元是一维的结构，而数组是多维结构，如何用一组连续存储空间存放数组的数据元素呢？解决方法：解决方法：存储映射策略；行优先存储；列优先存储。数组元素满足1=i=m,

19、1=j=n设每个数据元素占L个存储单元，第一个元素a00存储地址是Loc(a00)，问aij在空间上的存储地址是什么？1 1、行优先存储、行优先存储Loc(aij)=Loc(a00)+(i*n+j)*La00a01a0n-1am-10am-1n-1nL假设：行、列的下界为假设：行、列的下界为0Loc(a00)2 2、列优先存储、列优先存储Loc(aij)=Loc(a00)+(j*m+i)*La00a10am-10a0n-1am-1n-1mL假设：行、列的下界为假设：行、列的下界为0Loc(a00)3.3.矩阵的存储及运算矩阵的存储及运算一、一般矩阵的存储一、一般矩阵的存储通常用二维数组存储矩阵

20、。特点：特点：矩阵中的每个元素占用二维数组中的相应位置。二、特殊矩阵的存储二、特殊矩阵的存储特殊矩阵：特殊矩阵：矩阵中相当一部分元素取值相同或都为0或元素在矩阵中分布有一定规律。特殊矩阵的存储方式：通常采用压缩存储。压缩存储：压缩存储：为多个值相同的矩阵元只分配一个存储空间；对0元不分配空间。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、对称矩阵、对称矩阵定义：定义：对于一个n*n方阵，且aij=aji（1=i=n,1=j=j1/2j(j-1)+(i-1)i=j1/2n(n+1)i0时，1,2,n是满足线性有序关系的，且i可以是某一数据对象元素，也可以是一个表结构。前者称为原子

21、原子，后者称为子表子表。（在表示习惯上，广义表名称用大写字母表示，原子用小写字母表示）特点：特点：广义表的结构是递归的。举例：举例：广义表广义表表长表长LS1=()n=0(空表)LS2=(a)n=1(只有原子)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

22、)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,n)二、求广义表深度二、求广义表深度1 1、广义表深度定义：、广义表深度定义：广义表括号重数例：LS=()深度：1LS=()深度：2LS=(a)深度：1LS=(a,(b,c)深度：2例：求例：求E=(A,B,C)E=(A,B,C)的深度的深度其中：A=(),B=(e),C=(a,(b,c,d)解：Depth(E)=1+maxDepth(A),Depth(B),Dep

23、th(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+max0,1=2 Depth(E)=1+max1,1,2=3 3（本章结束）第六章树第六章树树的定义和术语树的定义和术语一、树的定义一、树的定义二、树的术语二、树的术语结点度、树的度、结点层次、树的深度、家族树、有序树。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、二叉树定义、二叉树定义树中每个结点

24、至多有两棵子树，且子树有序。（根据二叉树的定义，二叉树的结构是递归的）2 2、二叉树的基本形态、二叉树的基本形态二叉树有五种基本形态：二叉树的基本形态：左子树右子树右子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点和左子树（4）有根结点和右子树（5）有根结点和左，右子树二、二叉树的性质二、二叉树的性质1 1、二叉树、二叉树性质性质1 1：第i层上最多有2i-1个结点。性质性质2 2：深度为K的二叉树最多有2K-1个结点。性质性质3 3：设叶子（度为0）数为n0，度为2的结点数为n2，则n0=n2+1。2 2、满二叉树与完全二叉树、满二叉树与完全二叉树满二叉树：深度为k，且有2k-1个

25、结点。（对满二叉树中的结点约定编号：自根起，从上到下，从左到右）完全二叉树：仅允许最下层右侧分支不满，若按从上到下，从左到右为树中结点编号，则与满二叉树相同。关系：关系：满二叉树是完全二叉树。完全二叉树不一定是满二叉树。3 3、完全二叉树性质、完全二叉树性质性质性质4 4：n个结点，深度为K的完全二叉树，其K=log2n+1性质性质5 5：对一棵n个结点深度为K的完全二叉树上的结点按层次编码（从第一层到第K层，从左到右），则树中编号为i的结点(1=i1时，i的双亲是 i/2；c:当2in时，i是叶点（无左孩子）；当2in时，i结点无右孩子；当2i+1=n时，2i+1是i的右孩子。三、二叉树存储

26、结构三、二叉树存储结构1 1、顺序存储结构、顺序存储结构用一维数组A作为二叉树的存储结构，Ai表示编号为i的结点。ABC125 A B C .01234A特点：浪费存储空间特点：浪费存储空间特例：特例：123K深度为K，只有K个结点的单支树需要2K-1个存储单元。（由二叉树的性质2知，深度为K的二叉树至多有2K-1个结点）。而真正有用的只有K个空间，其它绝大多数空间是空闲的。造成了存储空间的极大浪费。顺序存储结构适用于完全二叉树：顺序存储结构适用于完全二叉树：特点：特点：即不浪费空间，又可以快速确定其结点的位置；对已知的结点i，其左孩子为2i，右孩子为2i+1，双亲为 i/2 。DBACEF1

27、23456 A B C D E F 012346A完全二叉树完全二叉树结点在存储空间中的相对位置恰好表现出了完全二叉树中结点之间的关系。2 2、链式存储结构、链式存储结构二叉链表：二叉链表：链表中每个结点至少含有三个域：数据域、左指针域和右指针域。lchildDatarchild指向左孩子指向左孩子指向右孩子指向右孩子33二叉树的遍历二叉树的遍历一、遍历二叉树一、遍历二叉树遍历：遍历：按一定次序访问二叉树上每个结点恰一次；访问：访问：访问代表一次操作；访问次序：访问次序：先左后右。并以访问根的次序不同分为不同的三种方式：先序、中序、后序。先序：先序：先访问根结点，然后访问左子树，再访问右子树。

28、中序：中序：先访问左子树，然后访问根结点，再访问右子树。后序：后序：先访问左子树，然后访问右子树，再访问根结点。例例1 1：KBDEHCGIJAF先序：先序：A ABCDEFGBCDEFGHIJKHIJK中序：中序：CEDFBGCEDFBGA AIKJHIKJH后序：后序：EFDCGBEFDCGBKJIHKJIHA A例例2 2：已知先序、中序可以惟一确定一棵二叉树：已知先序、中序可以惟一确定一棵二叉树已知：中序：GDHBGDHBA AECIFECIF先序：A ABDGHBDGHCEFICEFIAIFECIFABCEGDHGDHBFABCEDGHI例例3 3：已知中序、后序可以惟一确定一棵二叉

29、树：已知中序、后序可以惟一确定一棵二叉树已知：中序：DBGEDBGEA AHFICHFIC后序：DGEBDGEBHIFCHIFCA AAHIFCDBGEHIFABCDGEFABCIDGEH例例4 4：已知先序、后序：已知先序、后序不能不能惟一确定一棵二叉树惟一确定一棵二叉树已知：先序：A B后序：B AABAB两棵不同的二叉树两棵不同的二叉树以中序为例讨论二叉树的递归遍历算法：以中序为例讨论二叉树的递归遍历算法：中序遍历二叉树的递归算法分析：中序：中序：访问左子树 访问根 访问右子树基值：基值：bt=NULL(bt为二叉树的根结点指针)。当二叉树为空时。归纳项：即是对子树（子树仍为二叉树）的遍

30、历操作。算法思想：算法思想：若二叉树为空，则遍历结束；否则遍历左子树访问根结点遍历右子树中序递归算法执行过程的简化展开图：中序递归算法执行过程的简化展开图：每深入一层代表一次调用；退上一层代表一次返回；从左子树返回仅一层；接着访问根结点；从右子树返回，表明当前层遍历结束，可以连续返回。ABFCDEGH二、线索二叉树二、线索二叉树1 1、什么是二叉树的线索化？、什么是二叉树的线索化？非线性结构的二叉树经过遍历（先序、中序、后序），结点排成线性有序（前趋、后继惟一）。但二叉树本身不具有这种信息，访问后即消失；为了保持在遍历过程中得到的前趋、后继信息，则需边遍历，边建立线索。线索：即是指向前趋、后继

31、结点的指针。线索二叉树：加上线索的二叉树称为线索二叉树。线索化：对二叉树进行遍历使其成为线索二叉树的过程称为二叉树的线索化。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 2、怎样线索二叉树、怎样线索二叉树(1)(1)增加两个标志位增加两个标志位每个标志位仅占1个存储位(bit)结点结构：若LTag=0(Link),则lchild指向左孩子；RTag=0(Link),则rchild指向右孩子；若LTag=1(Thread),则lchild指向线索前趋；RTag=1(Thread),则rchild指向线索后继。lchildLTagdataRTagrchild带头结点的中序线索链表：带头

32、结点的中序线索链表：10A00B01F01C00E11D11G11二叉树的头指针二叉树的头指针Head44树和森林的存储与运算树和森林的存储与运算一、树的存储表示一、树的存储表示1 1、双亲表示法、双亲表示法（顺序存储结构）开辟一组连续空间存储树的结点，每个结点中附设一个指示双亲结点的双亲域。CBADEABCDE-1 0003Data:Parent:特点：找结点双亲容易，但找孩子不容易特点：找结点双亲容易，但找孩子不容易012 342 2、孩子表示法（、孩子表示法（链式存储结构）(1)按树的度设结点指针域特点：特点：每个结点的结构一致，操作简单，但浪费存储空间。CBADEAB C D E 树的

33、度树的度=3=3(2)按结点的度设结点指针域特点：特点：每个结点的结构不一致，操作复杂，但节省存储空间。CBADEAB 0C 0D 13E 0(3)按孩子结点排成线性表特点：特点：节省空间，操作也较容易；问题：问题：这种结构不能反映出树的层次性特征。ABCDECBADE2354每个结点的孩子链表每个结点的孩子链表123453 3、孩子兄弟表示法（二叉树表示法）、孩子兄弟表示法（二叉树表示法）在这种表示法中，树中每个结点有三个域：数据域：存放结点数据左指针域：指向该结点的第一个孩子结点右指针域：指向该结点的右兄弟结点datafchnsib特点：特点：便于实现树的各种操作，节省空间，并且能够描述树

34、的层次结构。CBADEA B CD E 二、森林与二叉树的转换二、森林与二叉树的转换二叉树和树都可以用二叉链表作为其存储结构。因此，以二叉链表作为中间媒介，可以导出树与二叉树之间存在对应关系。一棵树与惟一的一棵二叉树一一对应。一棵树与惟一的一棵二叉树一一对应。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ B CD E A B CD E CBADE树树二叉树二叉树二叉树表示法二叉树表示法二叉链表二叉链表1 1、树转换成二叉树、树转换成二叉树保持双亲和第一个孩子连线，其他连线去掉；兄弟之间连线；使右兄弟结点成为右孩子，使第一个孩子成为左孩子。2 2、森林转换为二叉树、森林转换为二叉树将

35、每棵树转化为二叉树；将各棵二叉树的根相连；使二叉树的根成为右孩子。3 3、二叉树转换成森林、二叉树转换成森林若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子、，都与该结点的父结点用线线连；去掉树中所有父结点到其右孩子的连线，生成森林。三、树与森林遍历三、树与森林遍历1 1、树的遍历、树的遍历遍历规则遍历规则：(1)(1)先根遍历：先根遍历：先访问树根，再依次先根遍历根的每棵子树。(2)(2)后根遍历：后根遍历：先依次后根遍历根的每棵子树，再访问树根。例：例：ABCDEF先根：先根：ABCEFDABCEFD后根：后根：BEFCDABEFCDA树 二叉树（续上例）ABCDEF先序：先

36、序：ABCEFDABCEFD中序：中序：BEFCDABEFCDA结论结论：（续上例）树的先根先根遍历相当于其转化的二叉树的先序先序遍历；树的后根后根遍历相当于其转化的二叉树的中序中序遍历；2 2、森林的遍历、森林的遍历(1)(1)先序先序(先根先根)遍历森林遍历森林A.访问第一棵树的树根；B.先序遍历第一棵树根的子树森林；C.先序遍历除第一棵树之后,剩余的树构成的森林。ABCDEF先序：先序：ABCDEFABCDEF(2)(2)中序中序(后根后根)遍历森林遍历森林A.中序遍历森林中第一棵树的根结点的子树森林；B.访问第一棵树的根结点；C.中序遍历除第一棵树之后剩余的树构成的森林。ABCDEF中

37、序：中序：BCDAFEBCDAFE例例:CDEFHJ先根先根:ABCDEFGHJIK(ABCDEFGHJIK(二叉树的先序二叉树的先序)后根后根:BADEFCJHKIG(BADEFCJHKIG(二叉树的中序二叉树的中序)ABIKG森林转化的二叉树森林转化的二叉树:CDEFHJABIKG55哈夫曼树及其应用哈夫曼树及其应用一、概念和术语一、概念和术语1、路径路径2、路径长度路径长度3、结点的权结点的权4、结点的带权路径长度结点的带权路径长度5、树的带权路径长度树的带权路径长度6、哈夫曼树哈夫曼树（续三）（续三）例：例：给定四个叶子结点a、b、c、d，分别带权0.1、0.1、0.4、0.4，由它们

38、构成不同的带权二叉树，分别求WPL。0.1 0.1 0.4 0.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只含一棵树为止。这棵树便是哈夫曼树。例：给定

39、权值7，5，2，4，构造哈夫曼树。前缀码前缀码给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码前缀码。例：例：000，001，01，10，11 前缀码0，1，10，11 不是前缀码特点：特点：前缀码是码长不等的编码，既可以缩短报文的长度，又容易翻译。（本章结束）第七章图第七章图基本概念与术语基本概念与术语一、图的定义一、图的定义定义：定义：简单地说，图是由一些结点和连接两个结点之间的边组成。22图的存储表示和图的生成图的存储表示和图的生成一、图的存储表示一、图的存储表示1 1、邻接矩阵表示法、邻接矩阵表示法（数组表示法）用一维数组存储图中顶点的信息；用矩阵（二

40、维数组）表示图中各顶点之间的相邻关系。图的顺序存储结构图的顺序存储结构(1)(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)(2)对称性对称性无向图：无向图：邻接矩阵对称，只需存入下三角（或上三角）,所用空间为n(n+1)/2有向图：有向图：不一定对称，需n2个存储单元。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 2、图的邻接表（、图的邻接表（图的一种链式存储结构图的一种链式存储结构）(1)(1)无向图的邻

41、接表无向图的邻接表vexdataFirstarc头结点：头结点：顶点顶点指向与该顶点指向与该顶点邻接的第一个邻接的第一个邻接点邻接点adjvexnextarc表结点：表结点：邻接点在邻接点在图中的图中的位置位置指向下一个指向下一个邻接点邻接点构造方法：构造方法：与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述；各链表设置表头结点，由头结点描述；各表头结点构成一个顺序表。(2)(2)有向图的邻接表及其逆邻接表有向图的邻接表及其逆邻接表邻接表（出度表）：邻接表（出度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧尾弧尾的邻接点。顺序表部分定义同无向图的邻接表。逆邻接表

42、（入度表）：逆邻接表（入度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧头弧头的邻接点。顺序表部分定义同无向图的邻接表。33图的遍历图的遍历遍历遍历：按一定次序，由图的某一顶点出发，沿着图的边访问所有顶点恰恰一次一次。设置访问标志数组设置访问标志数组：visitedi 1=i=n(n为图中顶点个数)False表示未被访问True表示已被访问一、深度优先搜索一、深度优先搜索（DFS）搜索策略：搜索策略：访问当前顶点vi，寻找与vi相邻且未被访问顶点vj，若存在，将其作为当前点，访问，并重复上述搜寻过程。否则（所有邻接点都被访问过），退回一步，寻找与前一个顶点相邻的未被访

43、问顶点，访问，并重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。深度优先搜索是一种纵向搜索纵向搜索的过程。二、广度优先搜索二、广度优先搜索（BFS）搜索策略：搜索策略：访问出发点v0，依次依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。广度优先搜索是一种横向搜索横向搜索的过程。使用队列队列结构。算法思想算法思想从指定顶点出发，每访问一个顶点就把它排在队尾，然后从队头取出一个顶点，访问该顶点所有未被访问的邻接点，如此，直到队空。若图中仍有未被访问的顶点，则另选一个顶点为出发点，重复上

44、述过程。44生成树生成树&最小生成树最小生成树一、生成树一、生成树1 1、定义：、定义：一个连通图连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树生成树。2 2、算法思想：、算法思想：DFS或BFS生成树。二、最小生成树二、最小生成树1 1、定义、定义连通网G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。将生成树的各边的权值总和称为生成树的权，并把权最小权最小的生成树称为G的最小生成树最小生成树。例：例：用用PrimPrim算法求最小生成树算法求最小生成树连通图如下所示：21456361555366422145636155536642例：例：用克鲁斯卡尔算法求最

45、小生成树用克鲁斯卡尔算法求最小生成树连通图如下所示：214563615553664212435612435612435612435612435612435655最短路径最短路径一、单源最短路径问题一、单源最短路径问题单源最短路径问题单源最短路径问题给定带权有向图，求从指定源点到图中其余各点的最短路径。u0到其余各顶点的最短路径到其余各顶点的最短路径源点源点中间顶点中间顶点终点终点路径长度路径长度1 2101 4 30 1 4 3 50 1 4,3 5 60 12534101005030102060u066拓扑排序拓扑排序将集合中偏序关系变为全序关系称为拓扑排序。一、拓扑排序一、拓扑排序1 1、

46、相关概念、相关概念AOV网网：顶点表示活动，弧表示活动间的优先关系的有向图。在无回路的AOV网中，所有的活动可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前边，称此序列为拓扑序列拓扑序列，由AOV网构成拓扑序列的过程称为拓扑排序拓扑排序。拓扑排序算法思想：拓扑排序算法思想：选择有向图中入度为0的顶点输出，并从图中删去该点相邻弧；重复上述操作，直到图中全部顶点均被输出或图中已不存在入度为0的顶点（有回路）。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ locating the pivot 4938659776132749 ij 273865977613 49ij 27

47、3865977613 49ij 2738 9776136549ij 2738139776 6549ij 273813 76976549 ij 2738134976976549 ijCS&T,BITIChapter 8算法分析时间效率最坏情况：当待排序的记录序列已经有序时，出现恶化趋势，Tworst(n)=O(n2)最好情况：每次划分的两个子表的长度大致相等，支点入“中值”位，Tbest(n)=O(nlog2n)平均情况：数据去无序，T(n)=Tpass(n)+T(k-1)+T(n-k)=O(nlnn)空间效率稳定性：不稳定44选择排序选择排序一、简单选择排序一、简单选择排序基本思想基本思想每趟

48、通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1in)个记录交换之。问题问题简单选择排序与起泡排序在排序过程都须经过比较、交换而实现的，二者的有何区别？算法分析算法分析时间效率比较次数：（无论正序、逆序、其他任意顺序）移动次数：最好情况(正序)：0次最坏情况(非逆序，但每趟排序过程中都有交换发生):3(n-1)平均时间复杂度：O(n2)空间效率：供交换用一个存储单元的辅助空间稳定性：不稳定二、堆排序二、堆排序堆排序的算法思想堆排序的算法思想1、建堆将给定的原始待排序列建成一个初始堆。即先建成一棵完全二叉树，再从下往上筛选为堆。首先由序列的第 结点开始与其孩子

49、比，大的上小的下（交换），下去后若有孩子再比较，直到叶子然后再由序列的第 结点起，重复上述过程，直到待排序列中的第一个结点。建成逆堆逆堆。得到待排序列中的最大元（根结点），并输出之。2、根结点与最后一片叶子交换。交换。3、若不是堆，则从根开始自上而下恢复成堆。4、重复2、3步，直到剩下一个结点为止，排序结束。55归并排序归并排序归并排序是另一类不同的排序方法。“归并归并”的含义是将两个或两个以上的有序表合成一个新的有序表。实现算法即可采用顺序存储结构，也可采用链式存储结构。1 1、归并概念、归并概念将两个或两个以上的有序表合并成整体有序的大表。归并分类参加归并的有序表个数为2，称为2-路归并参

50、加归并的有序表个数为3，称为3-路归并参加归并的有序表个数3，称为多路归并a、b、C均有序,且ai 若ai=bjbj 否则 Ck=a1.nb1.m C1.m+n归并归并2 2、2-2-路归并的基本思想路归并的基本思想基本思想基本思想对于n个元素的待排关键字序列，先分成长度为1的n个有序子表，两两归并，得到 个长度为2或1的有序子表；再对这 个有序子表进行两两归并；如此重复，直至得到一个长度为n的有序表。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 3、算法分析、算法分析时间效率时间=一趟归并时间*归并趟数=O(n)*log2n=O(n log2n)空间效率：使用了一个辅助数组 O(