数据结构（Python Java）（微课版） 课件全套 蒋理 第1-8章 数据结构与算法概论-查找

数据结构与算法设计计算机解决问题的步骤非数值数学模型1.1问题求解计算机求解现实问题计算机解决问题的步骤一个长75cm、宽60cm的长方形纸板，平均切割成大小相等的正方形纸板，使每个正方形纸板的面积最大，共可切割成多少个正方形纸板？人要和计算机进行有效交流，必须通过程序计算机世界机器语言现实世界自然语言程序计算机解决问题的步骤分析问题、设计算法、编写程序、执行程序人：分析问题、确定解决方案、编写程序计算机：执行程序最终获得问题的解数据模型数值问题：数学方程非数值问题：线性表、树、图等数据结构数据模型一个简单的图书信息检索系统包括一张按索书号、条码号和书名的顺序排列的图书信息表。图书信息表中的顺序关系可以被抽象成线性结构图书信息检索系统——线性数据结构书名条码号索书号书架号什么是算法90073160TP393.92/1811-12-3数据库原理与应用70002001TP391.41/3141-12-1软件测试项目实践00777680TP311.52/8371-13-2Linux系统编程50010241TP316.76/4541-10-2Python程序设计90115601TP311.56/1291-14-1对弈问题——树人机对弈问题是一个古老的人工智能问题，对弈过程是在一定规则约束下的随机过程。其解决问题的思路是将对弈策略事先存入计算机，包括对弈过程中所有可能出现的情况和相应的对策。城市道路问题——图假设某人要从地点A骑车到地点G，使用导航系统查询合适的骑行路线。导航系统为解决这个问题，须建设地区交通的数学模型，描述各个地点及其之间的交通情况。对于这类问题，通常采用“图”来描述路况——将地点抽象成一个点，地点之间的路线抽象成一条线，路线的距离用线上的数字描述。这些点、线就组成了一个图。小结1.1问题求解计算机解决问题的步骤非数值数学模型数据结构与算法设计数据结构的相关概念抽象数据类型1.2数据结构概述数据(data)信息的载体，是对客观事物的符号表示，能够被计算机识别、存储和加工处理。图像、声音、视频等都可通过编码由计算机处理，因此也属于数据的范畴数据元素(dataelement)数据的基本单位,也称为元素、结点或记录数据项数据元素可由若干个数据项（字段、域）构成数据项是数据不可分割的最小单位数据结构的相关概念数据对象数据的子集具有相同性质的数据元素的集合姓名班级学号小明3020112小红302027小方3020232姓名课程名成绩小明高数85小红高数90小红英语88数据数据元素数据对象数据项数据结构数据元素的集合中，元素相互之间的关系数据的逻辑结构集合线性结构树型结构图状结构数据的物理(存储)结构数据在存储器中位置的关系数据逻辑结构表示： Data_Structures=(D,S)D是数据元素的有限集S是数据元素关系的有限集GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}D1D2E11E12E13E21E23E22M某公司有1名经理(M)，2个部门经理(D)，每个部门各有3名职员(E)。人员之间的关系是：经理指导部门经理的工作，部门经理指导职员的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}D1D2E11E12E13E21E23E22M某公司有1名经理，2个部门经理，每个部门各有3名职员。人员之间的关系是：按人员年龄从大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}D1D2E11E12E13E21E23E22M某公司有1名经理，2个部门经理，每个部门各有3名职员。人员之间的关系是：人员之间的友好关系。数据的存储结构数据元素的存储用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2‘A’=(101)8=(01000001)2关系的存储顺序存储结构用元素之间存储的相对位置表示关系链式存储结构用存储元素的引用（指针）表示关系抽象数据类型抽象数据类型是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型一般通过数据对象、数据关系以及基本操作来定义。ADT抽象数据类型名{

数据对象D：<数据对象的定义>

数据关系R：<数据关系的定义>

基本操作P：<基本操作的定义>}小结1.2数据结构概述数据结构的相关概念抽象数据类型数据结构与算法设计算法及其特性算法设计的要求算法描述方法1.3算法概述算法评价算法(Algorithm)对特定问题求解步骤的一种描述是指令的有限序列算法的特性有穷性确定性可行性输入输出算法及其特性正确性：算法应当满足具体问题的需求，按算法编码好的计算机程序的执行结果应当符合预先设定的功能和性能要求。可读性：一个算法应当思路清晰、层次分明、易读易懂。可读性好，易于理解。健壮性：指一个算法对不合理数据输入的反应能力和处理能力，也被称为容错性。高效性：一个算法应当有效使用存储空间和有较高的效率。对于同一个问题，通常可以有多个解决算法，其中执行时间短、占用存储空间少的算法即“好的算法”。算法设计的要求自然语言算法描述框图算法描述伪代码算法描述高级程序语言编写的程序或函数算法描述方法事前估算法（定性分析）：对算法所消耗资源的一种估算方法算法的策略问题的规模书写程序的语言编译程序产生的机器代码的质量机器执行指令的速度事后统计法（定量分析）：将算法实现，测算其时间和空间开销评价算法算法评价指标执行程序需要占用多少机器资源时间资源算法运行时花费的时间代价空间资源程序执行中占用的内存空间代价时间复杂性和空间复杂性T(n)：2n3+3n2+2n+1算法的时间复杂性分析算法中所有语句执行时间之和语句的执行时间：该语句的频度(语句重复执行的次数)，与该语句执行一次所需时间的乘积。//求两个n阶方阵的乘积C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求两个n阶方阵的乘积C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1//求两个n阶方阵的乘积C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求两个n阶方阵的乘积C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1算法的时间复杂性分析算法时间取决于控制结构和原操作的综合效果f(n)是算法中频度最大的语句频度，通常是最深层循环内的原操作执行的次数。随着n的增长，算法执行时间的增长率和f(n)的增长率相同。算法时间复杂度记作：T(n)=O(f(n))O(n)：n3常见函数比较通常有如下的函数关系

c<log2n<n<nlog2n<n2<n3<2n指数时间的关系为

O(2n)<O(n!)<O(nn)算法的时间复杂度不仅是问题规模n的函数，还与所处理的数据集有关 (1)1,2,3,4,5,6,7,8,9,10 (2)10,9,8,7,6,5,4,3,2,1全面分析算法，需考虑它在最坏情况下的代价、最好情况下的代价和平均情况下的代价。算法的空间复杂度算法所需的存储量输入数据所占空间程序本身所占空间辅助变量所占空间 S(n)=O(g(n))随着问题规模n的增大，算法运行所需存储空间的增长率与g(n)的增长率相同小结1.3算法概述算法及其特性算法设计的要求算法描述方法算法评价数据结构与算法设计线性表n(n≥0)个具有相同特性的数据元素的有限序列n表示线性表的长度，即数据元素的个数n=0时表为空表n>0时记为:（a1，a2，…ai-1，ai，ai+1，…an）基本特征有且只有一个第一元素，且只有一个最后元素除第一元素之外，其它元素都有唯一的直接前趋除最后元素之外，其它元素都有唯一的直接后继2.1线性表的概念aebcd数据元素在不同问题中的含义各不相同，可以是一个数、一个符号，一个记录，或其它复杂的信息例中学生成绩表是一个线性表数据元素是每一个学生的信息，包括：学号、姓名、成绩共三个数据项线性表举例学号姓名成绩043801陈实80043802陈信85043803秦俭82043804秦奋90┆┆┆043850钟毅88数据元素基本运算初始化线性表查找线性表中第i个元素查找满足给定条件的数据元素在指定位置插入新的数据元素删除线性表中的第i个数据元素查找表中第i个元素的前驱元素查找表中第i个元素的后继元素表置空 ……线性表的运算数据结构与算法设计顺序存储在内存中开辟连续的存储空间，用连续的存储单元依次存放线性表的数据元素顺序表顺序存储的线性表特点逻辑上相邻的数据元素，其物理位置也相邻利用物理位置上的关系，反映元素的逻辑关系2.2线性表的顺序存储优点静态操作容易实现根据定位公式容易确定表中元素的存储位置缺点动态操作实现效率较低插入和删除结点困难扩展不灵活，容易造成空间浪费建表时，若估计不到表的最大长度，就难以确定分配的空间，影响数据扩展分配的空间过大，则会浪费预留空间顺序存储结构的优缺点数据结构与算法设计链表以链式结构存储的线性表用一组在物理位置上任意的存储单元来存储线性表的节点存储单元可以是相邻的，也可以是不相邻的物理位置上的关系不能反映节点间的逻辑关系2.3线性表的链式存储结构线性表的链式存储０００００５陈小洁０００００４张吉祥０００００２林春英０００００１李小林０００００６李清０００００３张桂林１７１５２０４０５４7155440NULL1用任意位置的存储单元存储线性表的数据元素节点间的逻辑关系借助节点中的指针(引用)

实现每个数据元素，除存储本身信息外，还需存储其直接后继的地址节点

数据域元素本身信息指针域指示直接后继的存储位置链式存储结构的特点

数据域指针域链表中，每个节点只包含一个指针域节点描述如下：#SinNode{

数据域

data;

指针域

next;}单链表每一个节点中有两个指针域一个指向直接后继一个指向直接前趋节点描述如下:#DulNode

{

数据域data

指针域next，prior}双向链表priordatanext数据结构与算法设计均匀性对于同一线性表，其各数据元素必定具有相同的数据类型和长度。有序性各数据元素在线性表中的逻辑位置只取决于它们的序号，数据元素之间的是线性的。线性表的特点顺序表优点：查找速度快缺点：插入和删除比较复杂链表优点：插入和删除操作简单缺点：查找速度慢顺序表与链表的比较单向链表优点：增加或删除节点操作简单缺点：只能从前向后遍历，只能找到后继节点，无法找到前驱节点，操作不够灵活双向链表优点：可以找到前驱节点和后继节点，操作灵活缺点：增加或删除节点时需要操作的指针较多，比较复杂单向链表与双向链表的比较数据结构与算法设计一元多项式求和有序单链表的合并2.5线性表的应用coefexpnext稀疏矩阵的三元组表示法线性表的应用稀疏矩阵的十字链表表示法线性表的应用约瑟夫问题线性表的应用约瑟夫和一个朋友及另外39个人围成一个圆圈，从第一个人开始报数，数到3的那个人退出圈子。然后下一个人从1开始重新报数，最后圈子里只剩下两个人，就是约瑟夫和他朋友。问约瑟夫和朋友站在什么位置？数据结构与算法设计3.1栈栈的定义与基本操作栈的顺序存储结构与实现栈的链式存储结构与实现顺序栈和链栈的比较栈的应用案例栈的定义与基本操作栈的定义栈：限定仅在一端进行插入和删除操作的线性表（a1,…,an-1,an）栈顶（top）：允许插入和删除的一端称为栈顶栈底（bottom）：另一端称为栈底插入位置：1~n+1删除位置：1~n线性表插入位置：n+1删除位置：n栈栈底栈顶栈的定义与基本操作栈的操作插入：入栈、进栈、压栈删除：出栈、弹栈a插入删除bc此时执行出栈操作，哪个元素可以出栈呢？栈的操作特性：后进先出（LastInFirstOut，LIFO）空栈：不含任何数据元素的栈

如何判空栈

initStack()：初始化操作。设置一个空栈isEmpty()：判栈空函数。若为空，则返回true，否则返回false。getTop()：读栈顶元函数。若栈不空，函数值为栈顶元素，否则为空元素NULLpush(x)：进栈操作。将元素x插入栈中，使x成为栈的栈顶元素pop()：出栈函数。若栈不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULLclearStack()：栈置空操作。不论栈是否为空栈，置为空栈栈的定义与基本操作栈的基本操作栈的定义与基本操作栈的抽象数据类型定义ADTStackDataModelOperationendADT栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系initStack：栈的初始化clearStack：清空栈内元素push：入栈pop：出栈getTop：取栈顶元素isEmpty：判空利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素a1a2……an顺序栈Sai……0n栈底栈顶top栈的顺序存储结构与实现顺序栈用数组的一端作为栈底设变量top存储栈顶元素所在的下标组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶FtopdatanextEDANULL栈顶栈底栈的链式存储结构与实现链栈顺序栈和链栈的比较顺序栈和链栈的基本算法的时间复杂度均为O(1)空间复杂度比较Java中，初始时顺序栈需要确定栈的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链栈没有栈满的问题，只有当内存没有可用存储空间时才会出现栈满，但是每个元素都需要指针域，从而存在结构性开销。把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）十进制数转换成二进制数栈的应用351784210110001余数结果：100011表达式求值栈的应用对算术表达式求值：

1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“运算符优先数法”对每种运算符赋于一个优先数，如：运算符：*/+-#优先数：22110其中

#是表达式结束符表达式求值时，设立两个栈运算符栈(OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数

步骤OPTR栈OPND栈输入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14 # 6# RETURN(TOP(OPND))表达式求值栈的应用小结3.1栈栈的定义与基本操作栈的顺序存储结构与实现栈的链式存储结构与实现顺序栈和链栈的比较栈的应用案例数据结构与算法设计3.2队列队列的定义与基本操作队列的顺序存储结构与实现队列的链式存储结构与实现循环队列与链队列的比较队列的应用案例队列的定义队列的定义与基本操作只能在表的一端进行插入，在表的另一端进行删除的线性表（a1,a2,…,an-1,an）a1

a2

…

an栈a1

a2

…

an队列队头队尾队尾：允许插入的一端，相应地，位于队尾的元素称为队尾元素队头：允许删除的一端，相应地，位于队头的元素称为队头元素队列的操作队列的定义与基本操作队列的操作特性：先进先出（FirstInFirstOut，FIFO）a插入：入队、进队入队bc例：有三个元素按a、b、c的次序依次入队，且每个元素只允许进一次队，则出队序列是什么？答：出队序列只有一种情况：abc出队删除：出队空队列：不含任何数据元素的队列

任何时候执行出队操作，一定是哪个元素呢？队列的基本操作队列的定义与基本操作initQueue()：初始化。设置一个空队列qisEmpty()：判断队列是否为空。若队列q为空，函数值为true，否则为false

size()：求队列长度。函数值为队列q中当前所含元素的个数getHead()：读队头元素。若队列q不为空，函数值为队头元素，否则为空元素enQueue(x)：入队。将元素x插入队列q的尾部，使x成为新的队尾元素delQueue()：出队。若队列q不为空，函数值为队头元素，且从队列q中删除当前队头元素，否则函数值为空元素顺序队列队列的顺序存储结构与实现队列的顺序存储结构队尾：设变量rear存储队尾元素所在的下标队头：用数组的一端作为队头，从下标0处开始存放01234a1a2a3a4rear例：a1a2a3a4

依次入队顺序队列队列的顺序存储结构与实现例：a1

出队01234a1a2a3a4rear01234a2a3a4rear队头元素出队后，后面的元素都需要前移，时间性能较差如何改进出队操作的时间性能？01234a2a3a4rear设置队头、队尾两个位置变量约定：队头front指向队头元素的前一个位置，队尾rear指向队尾元素fronta1入队、出队时间性能均是O(1)顺序队列队列的顺序存储结构与实现顺序队列队列的顺序存储结构与实现队列的移动有什么特点？01234a2a3a4front整个队列向数组下标较大方向移动单向移动性队列的单向移动性会产生什么问题？a5假溢出：数组空间发生上溢，但数组的低端还有空闲空间rear循环队列队列的顺序存储结构与实现如何解决假溢出呢？01234a3a4rearfront如何使数组下标循环呢？a5a6循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构循环队列队列的顺序存储结构与实现01234a3rearfront如何判断循环队列的队空？队空的判定条件：front==rear循环队列队列的顺序存储结构与实现a6a2a4a5rearfront如何判断循环队列队满？队空的判定条件：front==rear队满的判定条件：front==rearx01234循环队列队列的顺序存储结构与实现如何确定不同的队空、队满的判定条件？队空的判定条件：front==rear队满的判定条件：front==rear数组中有一个空闲单元01234a6a2a4a5rearfront01234a1a2a4a5rearfront(rear+1)%QUEUE_SIZE=front链队列队列的链式存储是单链表，同时带有头指针和尾指针头指针指向队头结点尾指针指向队尾结点队列的链式存储结构头结点^…...head队头队尾tail设队首、队尾指针head和tail,head指向队头，tail指向队尾循环队列与链队列的比较循环队列和链队列基本算法的时间复杂度均为O(1)空间复杂度比较初始时循环队列必须确定一个固定的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链队列没有溢出问题，只有当内存没有可用存储空间时才会出现溢出，但是每个元素都需要指针域，存在结构性开销。队列的应用案例舞伴配对问题在某舞会上，男士和女士进入舞厅时，各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮。在算法中，假设男士和女士的记录存放在一个数组中，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成后，依次使两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮开始时第一个可获得舞伴的人。队列的应用案例时间片轮转调度问题系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止执行该进程，并将它送往就绪队列的末尾；然后，把处理机分配给就绪队列中新的队首进程，同时让它执行一个时间片。小结3.2队列队列的定义与基本操作队列的顺序存储结构与实现队列的链式存储结构与实现循环队列与链队列的比较队列的应用案例数据结构与算法设计4.1递归定义若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。递归定义递归定义构成递归需具备的条件子问题须与原始问题为同样的问题，且更为简单不能无限制地调用本身，须有个出口，化简为非递归状况来处理小结4.1递归定义数据结构与算法设计4.2递归算法设计递归问题，必须符合以下三个条件可以把一个问题转化为一个新的问题，这个新的问题的解决方法与原问题的解法相同，但是所处理的对象（参数）有变化通过对象（参数）的变化使问题得到简化要有明确的结束递归的条件，否则递归将会陷入死循环递归算法设计以下三种情况可以使用递归解决问题定义是递归的数据结构是递归的问题的解法是递归的递归算法设计阶乘函数定义是递归的递归算法设计数据结构是递归的f

ffff

a0a1a2a3a4链表操作递归算法设计问题的解法是递归的汉诺塔(TowerofHanoi)问题的解法如果n=1，则将这一个盘子直接从A柱移到C柱上否则，执行以下三步用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上将A柱上最后一个盘子直接移到C柱上用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上递归算法设计递归的结构递归的结构是由递归出口和递归体两部分组成递归出口确定递归到何时为止递归体确定递归的方式递归是把一个不能或不好直接求解的"大问题"转化为若干个"小问题"来解决再把这些"小问题"进一步分解成更小的"小问题"来解决一直向下分解，直到每一个"小问题"都可以直接解决"直接解决"就是递归出口递归的执行过程求解n!的过程递归的执行过程主程序

fact(4)参数4计算4*fact(3)参数3计算3*fact(2)参数2计算2*fact(1)参数1计算1*fact(0)参数0直接定值=1

参数传递结果返回递归调用回归求值返回1返回1返回2返回6返回

24对原问题f(s)进行分析，假设出合理的"较小问题"f(s')；假设f(s')是可解的，确定f(s)的解，即给出f(s)与f(s')的关系；确定特定情况，如f(1)或f(0)的解，由此作为递归出口。递归设计步骤小结4.2递归算法设计数据结构与算法设计4.3消除递归直接转换法间接转换法递归的优点可解决复杂问题可缩短程序代码、提高编程效率递归的缺点不能提高程序的运行效率在递归算法调用的过程中，系统为每一层的返回点、局部变量等开辟了栈来存储，递归次数过多容易造成栈溢出消除递归消除递归两种消除递归的方法直接转换法：对于采用尾递归和单向递归的算法，可用循环结构的算法来代替。间接转换法：用栈来模拟系统运行时的栈，保存有关的信息，而用非递归算法来模拟递归算法。

直接转换法尾递归是指在递归算法的函数中，递归调用语句只有一条，而且是处在函数的最后，如求解阶乘的函数即尾递归。尾递归可以方便地用循环结构来替代间接转换法间接转换法使用栈保存中间结果，一般根据递归函数在执行过程中栈的变化得到小结4.3消除递归直接转换法间接转换法数据结构与算法设计4.4回溯法回溯法是从问题的某一种可能出发，搜索从这种情况出发所能达到的所有可能。当这一条路走到“尽头”的时候，再倒回上一节点，从另一个可能出发，继续搜索。回溯是一种思想，递归是一种解决问题的方法。回溯可以用递归来实现，也可以不用递归实现。回溯法迷宫中设置很多隔壁，对前进方向形成了多处障碍。假设迷宫的每个岔路口只有东南西北四个方向或是这四个方向的子集。回溯法思想：一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若某处可以到达，则到达新起点；否则试探下一方向。若所有的方向均没有通路，则沿原路返回到前一点，换下一个方向再继续试探，直到所有可能的通路都试探到。结果是或找到一条通路，或无路可走又返回到入口点。递归实现：从入口出发，每到一个结点（岔路口），按东南西北的秩序访问相应方向的下一个结点，如果相应方向没有可以访问的结点，则访问下一个方向。如果四个方向全被访问完，则返回到前一个结点。直到找到出口或回到入口。迷宫问题小结4.4回溯法数据结构与算法设计4.5递归的评价可解决适应递归的复杂问题可缩短程序代码、提高编程效率不能提高程序的运行效率递归的评价递归运行效率问题例：计算斐波那契数列的函数Fib(n)的定义:求解斐波那契数列的递归算法的伪代码：

fib(n){ if(n==1或n==2){

return1 }else{ returnfib(n-1)+fib(n-2) }}调用次数

Num(k)=2*Fib(k+1)-1算法复杂度为O(2n),

即指数量级

Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)递归运行效率问题小结4.5递归的评价数据结构与算法设计树的定义树的相关概念树的表示5.1一般树定义树是由n（n≥0）个节点组成的有限集合当n＝0时称为空树否则，在任一非空树中必有一个称为根的节点；当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1,T2,……Tm其中每一个集合本身又是一棵树，称为根的子树特点非空树中至少有一个根节点树中各子树是互不相交的集合5.1树的概念树的结构A只有根节点的树ABCDEFGHIJKLM有子树的树根子树树的相关概念节点(node)节点的度(degree)树的度叶子节点(leaf)分支节点孩子节点(child)双亲节点(parents)兄弟节点(sibling)堂兄弟节点树的层次树的深度有序树与无序树森林路径祖先与子孙终端节点与非终端节点节点树中的元素，包括数据项及若干指向子树的分支节点的度节点拥有的子树数叶子度为0的节点，也叫终端节点分支节点度不为0的节点，也叫非终端节点内部节点除根节点之外，分支节点也称为内部节点树的相关概念孩子节点子树的根称为该节点的孩子双亲孩子节点的上层节点叫该节点的双亲兄弟同一双亲的孩子之间互成为兄弟祖先从根到该节点所经分支上的所有节点子孙子树中的任一节点都是该节点的子孙树的相关概念树的度一棵树中最大的节点度数节点的层次从根节点算起，根为第一层，它的孩子为第二层……堂兄弟其双亲在同一层的节点互称为堂兄弟深度树中节点的最大层次数树的相关概念有序树树中节点的各子树从左至右是有序的最左边的子树的根称为第一个孩子最右边的称为最后一个孩子森林m(m

0)棵互不相交的树的集合树的相关概念树的表示树形结构表示法凹入表示法嵌套集合表示法广义表表示法小结5.1树的概念树的定义树的相关概念树的表示数据结构与算法设计二叉树的概念二叉树的性质二叉树的存储二叉树的遍历5.2二叉树定义二叉树是节点的有限集合或者是空树或者由一个根节点和两棵二叉子树构成左子树，右子树子树不相交特点每个节点至多有二棵子树不存在度大于2的节点子树有左、右之分，次序不能任意颠倒二叉树二叉树的五种形态空二叉树右子树为空的二叉树左子树非空的二叉树仅有根节点的二叉树左右子树均非空的二叉树深度为k的满二叉树，有2k-1个节点2k-1是深度为K的二叉树所具有的最大节点个数满二叉树123114589121367101415特点每层上的节点数都达到最大值只有度为0的节点和度为2的节点每个节点均有两棵高度相同的子树叶子节点都在树的最下面一层上叶子节点只出现在最低两层上对任意节点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次为L或L+1除最低层外，每一层上的节点数均达到最大值；在最低层上只缺少右边的若干节点(也可不缺)。完全二叉树123114589121367101415满二叉树完全二叉树123114589126710性质1：在二叉树第i层上至多有2i-1

个节点(i≥1)证明：当i=1时，只有一个根节点。显然，2i-1

＝20

＝１是对的假设对所有的j(1≤j﹤i)，命题成立即第j层上至多有2j-1

个节点那么可以证明j=i时命题成立归纳假设：第i-1层上至多有2i-2

个节点。由于二叉树的每个节点的度至多为2，故在第i层上的最大节点数为第i-1层上的最大节点数的2倍即2*2i-2＝2i-1。二叉树的性质123114589121367101415性质2：深度为k的二叉树至多有2k-１个节点(k≥1)证明：

由性质１可见，深度为k的二叉树的最大节点数为：二叉树的性质123114589121367101415性质3：对任意二叉树T，如果其终端节点数为n0

，度为2的节点数为n2,则n0=n2+1。证明：二叉树中节点总数为：

n=n0+n1+n2 (5-1)二叉树的分支数为：

n1+2*n2 (5-2)因此，节点总数为：

n=n1+2*n2+1由(5-1)、(5-2)两式可得：

n0=n2+1二叉树的性质1234567性质4：具有n个节点的完全二叉树的深度为

log2

n

+1证明：假设深度为k，则根据性质2和完全二叉树的定义有于是因为k是整数,所以二叉树的性质性质5：对一棵有n个节点的完全二叉树的节点按层序号编号(从第1层到

log2n

+1层，每层从左到右)，则对任一节点i(1≤i≤n)，有：如果i=1，则节点i是根节点，无双亲，否则，其双亲节点为：

i/2

如果2i>n，则节点i无左孩子(节点i为叶子节点);否则其左孩子是节点2i如果2i+1>n，则节点i无右孩子;否则其右孩子是节点2i+1二叉树的性质123114589126710顺序存储将任意二叉树“修补”成完全二叉树利用顺序表对数据元素进行存储原二叉树中空缺的节点在数组中相应单元置空二叉树的存储123φ5φ7φφ10链式存储:二叉链表节点包含3个域：数据域和指向左、右子树的指针域二叉树的存储LChildDataRChild遍历（taversal）按一定的规则和次序走遍二叉树的所有节点使每个节点都被访问一次，且只被访问一次访问对节点进行各种操作遍历二叉树的目的遍历是对数据进行操作的基础得到二叉树中各节点的一种线性顺序使非线性的二叉树线性化，简化有关的运算和处理二叉树的遍历若二叉树为空，则返回；否则依次执行以下操作：访问根节点；按先序遍历左子树；按先序遍历右子树；返回。先序遍历先序遍历序列：ABDECACBDEACBDE若二叉树为空，则返回；否则依次执行以下操作：按中序遍历左子树；访问根节点；按中序遍历右子树；返回。中序遍历中序遍历序列：DBEACACBDEACBDE若二叉树为空，则返回；否则依次执行以下操作：按后序遍历左子树；按后序遍历右子树；访问根节点；返回。后序遍历后序遍历序列：DEBCAACBDEACBDE二叉树的概念二叉树的性质二叉树的存储二叉树的遍历小结5.2二叉树数据结构与算法设计树的存储树与二叉树的转换森林与二叉树的转换树的遍历5.3树、森林与二叉树树的存储结构特点寻找父结点只需要O(1)时间可以从一个结点出发，到其父亲，再到其祖父等，从而求出根查询孩子和兄弟的信息困难双亲表示法树的存储结构155特点孩子结点的数据域存放它们在数组中的序号便于实现有关孩子及其子孙的运算不便于实现与双亲有关的运算孩子链表表示法树的存储结构双亲孩子链表示法树的存储结构孩子兄弟表示法树与二叉树的转换abcdefhgiba^c^d^e^f^^g^h^i^^abcdefghi^^^^^^^^^^二叉树与树的相互转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^树转二叉树①加线：在兄弟之间加一连线。②抹线：对每个节点，除了其第一孩子外，去除其与其余孩子之间的关系。③调整：将节点按层次排列，形成二叉树。树转换成的二叉树其右子树一定为空！二叉树转树①加线：若p节点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来②抹线：抹掉原二叉树中双亲与右孩子之间的连线③调整：将节点按层次排列，形成树结构森林转二叉树①将各棵树分别转换成二叉树。②将每棵树的根节点用线相连。③以第一棵树根节点为二叉树的根，调整层次，构成二叉树形结构。二叉树转森林①抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。②还原：将孤立的二叉树分别还原成树。先序遍历(与对应的二叉树先序遍历序列一致)若树非空，则：访问根结点依次先序遍历根的各个子树后序遍历(与对应的二叉树后序遍历序列一致)若树非空，则：依次后序遍历根的各个子树访问根结点层次遍历若树非空，访问根结点。若第1，…i(i≥1)层结点已被访问，且第i+1层结点尚未访问，则从左到右依次访问第i+1层。树的遍历树的遍历先序遍历

A，B，E，F，C，D后序遍历

E，F，B，C，D，A层次遍历

A，B，C，D，E，F树的存储树与二叉树转换森林与二叉树转换树的遍历小结5.3树与二叉树数据结构与算法设计哈夫曼树的相关概念哈夫曼算法哈夫曼编码5.4哈夫曼树路径若树中存在某个节点序列k1,k2,…,kj满足Ki是ki+1的双亲则该节点序列是树上的一条路径路径长度路径经过的边数，称为路径长度树的路径长度从树根到树中每一个节点的路径长度之和哈夫曼树的相关概念节点的权给树的节点赋以一定意义的数值，称为节点的权节点的带权路径长度从树根到某节点的路径长度与该节点的权的积树的带权路径长度（WPL）

树中所有叶子节点的带权路径长度之和哈夫曼树相关概念2357例：4个节点的权值分别为2，3，5，7。以下是以它们为叶子节点构造二叉树，计算各二叉树的带权路径长度WPL。WPL=2*3+3*3+5*2+7*1=32WPL=2*2+3*2+5*2+7*2=34WPL=2*1+3*2+5*3+7*3=44由n个带权叶子节点构成的二叉树具有不同形态其中带权路径长度（WPL）最小的二叉树又叫最优二叉树，或最佳判定树哈夫曼树的概念最佳判定树以各分数段人数的比例为权值构造最佳判定树使得大部分数据经过较少次数的比较得到结果最佳判定树构造哈夫曼树的方法——哈夫曼算法根据给定的n个权值{w1,w2,……wn}，构造n棵只有根节点的二叉树，令其权值为分别wj在森林中选取两棵根节点权值最小的树作左右子树，构造一棵新的二叉树置新二叉树根节点权值为其左右子树根节点权值之和在森林中删除这两棵树，并将新得到的二叉树加入森林中重复上述步骤，直到只含一棵树为止这棵树即哈夫曼树哈夫曼算法例：已知权值集合{2，4，6，7，8}，构造哈夫曼树。哈夫曼编码电报通讯中，电文以二进制的0,1序列传送发送端将电文中的字符转换成0,1的二进制序列接收端将收到的0,1序列转换成对应的字符序列(译码)假定电文是英文，电文字符串由26个英文字母组成，需要编码的字符集是{A,B,C,D,…,Z}方法一：等长的二进制编码方法二：不等长的二进制编码

A:010B:0101C:01011前缀码任一字符的编码，不能是其他字符的前缀哈夫曼编码假设字符集D={d1,d2,d3,…,dn}每个字符di的编码长度为li每个字符di在电文中出现的次数是ci

则电文的总长度为:∑ci*li每个字符di在电文中出现频度的概率是wi

每个字符di的编码长度为li则电文的平均总长度为:∑wi*li

哈夫曼编码寻找最优前缀码的方法用d1,d2,d3,…,dn作为叶子节点用w1,w2,w3,…,wn作为叶子节点的权构造最优二叉树将树中每个节点的左分支置为0，右分支置为1从根到叶子节点的一个标号序列，就是该叶子节点的编码例：设某语言有ABCDEF六种字母，出现的概率分别为0.11，0.12，0.13，0.15，0.22，0.27。A：000B：001C：110D：111E：01F：10小结5.4哈夫曼树哈夫曼树的相关概念哈夫曼算法哈夫曼编码数据结构与算法设计堆的概念堆的操作堆的算法分析5.5堆堆的概念n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值大根堆小根堆建堆（大根堆）找到最后一个分支节点（非叶子节点）。对这个节点进行向下调整，即与孩子节点相比较，把比自己大并且是最大的孩子节点与当前节点交换位置，如果发生交换，到达新位置的节点将继续向下调整，直到不发生交换位置或到达叶子节点。从后向前对所有分支节点进行向下调整。直到对根节点完成向下调整。堆的操作例：设节点分别为3、7、5、13、2、17、11，建立大根堆。添加节点把这个节点加到顺序表的末尾从下向上调整至合适位置删除节点把待删除的节点与最后一个节点交换位置删除最后一个节点把与删除节点交换位置的节点向下调整至合适位置堆的操作在堆中，向上调整和向下调整的操作次数不会大于二叉树的层数，所以单个节点的调整，其算法复杂度为log2n。建堆时，需要对所有分支节点做向下调整，在完全二叉树中分支节点的个数为n/2，所以建堆的算法复杂度为O(nlog2n)。增加节点和删除节点时，只需要对单个节点进行向上调整或向下调整，所以其算法复杂度为O(log2n)。堆的算法分析堆的插入和删除操作只需要进行O(log2n)次的交换操作，明显优于顺序表的O(n)次操作。相较于链表，堆在逻辑上存在一定的顺序，并且兼具二叉树的特点，可以在算法的优化上起到明显的作用。堆的算法分析小结5.5堆堆的概念堆的操作堆的算法分析数据结构与算法设计图的相关术语图的存储结构6.1图的概念图(Graph)G=(V，E)V是非空有限集合，其元素称为顶点E是边的集合,顶点偶对称为边图的相关术语有向图G1(b)无向图G2有向图G1=(V1，E1)V1={v1，v2，v3，v4}E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}弧有序的顶点偶对：<x，y>

有向图G1XY弧尾弧头无向图G2=(V2，E2)V2={v1，v2，v3，v4，v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}边无序的顶点偶对(x，y)(b)无向图G2完全图(completedgraph)无向图，边的取值范围是0到n(n-1)/2有n(n-1)/2条边的无向图有向图，边的取值范围是0到n(n-1)有n(n-1)条弧的有向图邻接点(adjacent)无向图G=(V，E)，若边(v，v’)∈E顶点v和v’互为邻接点，即v和v’相邻接边(v,v’)与顶点v,v’相关联有向图G=(V,E)，如果边<v,v’>∈E顶点v邻接到v’,或v’邻接于v弧<v,v’>与顶点v,v’相关联无向图度与顶点v相关联的边数有向图入度出度顶点v的度为：TD(v)=ID(v)+OD(v)有n个顶点，e条边或弧的图，满足关系:子图

假设有两个图G=(V，E)G'=(V'，E')如果V'包含于V，E'包含于E，则称G'是G的子图(b)G2的子图(a)G1的子图G1(b)

G2路径在无向图中,若存在一个顶点序列 vi,vp1,vp2,…,vpm，vj使得(vi,vp1)、(vp1,vp2),...,(vpm,vj)∈E则称顶点vi到vj存在一条路径如果G是有向图，则路径也是有向的顶点序列应满足<vi,vp1>,<vp1,vp2>,...,<vpm,vj>∈E路径的长度路径上的边的或弧的数目简单路径顶点不重复出现的路径称为简单路径回路第一个顶点和最后一个顶点相同的路径称为回路或环简单回路除了第一顶点和最后一个顶点之外，其余顶点不重复出现的回路权(weight)在图的每条边上加上一个数字作权网(network)带权的图称为网邻接矩阵邻接矩阵是表示顶点间相邻关系的矩阵若G是一个具有n顶点的图则G的邻接矩阵是如下定义的n×n矩阵：图的存储结构无向图的邻接矩阵对称，可压缩存储有n个顶点的无向图需存储空间为n(n+1)/2有向图的邻接矩阵不一定对称有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和邻接矩阵的特点网的邻接矩阵定义：网的邻接矩阵顶点表顶点表的每个结点中指针域指向边表的第一个结点数据域存储顶点的名称或其它信息顶点表的每个结点，相当于边表头结点边表把同一个顶点发出的边链接在同一个链表中，链表的每一个结点代表一条边边表结点中保存着与某顶点相关联的另一顶点，和指向下一个表结点的指针图的邻接表表示法邻接表边表结点vexdatafirstarcadjvexnext顶点表结点图的邻接表表示法图的邻接表表示法有向图的邻接表邻接表V1V2V4V5V3V7V6V8在弧结点中有四个域：尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的编号。链域(hlink)：指向弧头相同的下一条弧。链域(tlink)：指向指向弧尾相同的下一条弧。十字链表tailvexheadvexhlinktlink弧头相同的弧在同一链表上，弧尾相同的弧也是在同一链表上。它们的头结点即为顶点结点，它由三个域组成data域存储和顶点相关的信息firstin域和firstout域分别指向以该顶点为弧头或弧尾的第一个弧结点。十字链表datafirstinfirstout十字链表tailvexheadvexhlinktlinkdatafirstinfirstout用一维数组存储图中所有的边每个元素用于存储一条边的起点、终点和权(对于无向图，可选定边的任一端点为起点或终点)各边在数组中的顺序可任意安排，也可根据具体要求而定边集数组只是存储图中所有边的信息，若需要存储顶点信息，同样需要一个具有n个元素的一维数组边集数组边集数组小结6.1图的概念图的相关术语图的存储结构数据结构与算法设计深度优先遍历广度优先遍历6.2图的遍历从图中某顶点出发，沿一些边访问图中顶点，使每个顶点都被访问到，且仅被访问一次无重复，无遗漏关键点图中可能存在回路图的顶点可能与其它顶点相通,在访问完某顶点后,可能沿着某些边回到曾经访问过的顶点为避免重复访问,可设辅助数组visited[]将其初始化为0遍历时,如果某顶点i被访问,将visited[i]置为1以此防止顶点i被多次访问图的遍历图的深度优先搜（DFS）索类似树的深度遍历设初始状态：图中所有顶点都没被访问过从图中某一顶点v0出发，访问v0，然后访问与v0邻接,但未被访问过的任一顶点v1接着访问与v1邻接，但未被访问过的任意顶点V2当达到某顶点时，发现其所有邻接顶点均被访问过，则退回到最近被访问过的前一顶点若它还有邻接点未被访问过，从未被访问过的顶点中，任取一顶点,重复这一过程若所有邻接顶点被访问过，则再回退如此重复，直到所有顶点均被访问过为止深度优先遍历深度优先遍历广度优先遍历（BFS）类似于树的层次遍历假设初始状态是图中所有顶点都没被访问过从图中某一顶点v0出发，访问v0然后访问v0的全部邻接点v1，v2，...，vt再从这些被访问的顶点出发，逐次访问它们的邻接点(已被访问的顶点除外)依此类推，直到所有顶点都被访问为止广度优先遍历广度优先遍历小结6.2图的遍历深度优先遍历广度优先遍历数据结构与算法设计拓扑排序问题关键路径问题最短路径问题6.3图的应用最小生成树连通无向图中，如果从顶点v到顶点v'有路径，则称v和v'是连通的连通图如果图中任意两个顶点都是连通的，则是连通图连通分量无向图的极大连通子图连通图只有一个连通分量，即其自身非连通的无向图有多个连通分量最小生成树15732461573246强连通图有向图中，如果每一对顶点vi,vj∈V(vi!=vj)，从vi到vj和从vj到vi都存在路径，则称G是强连通图强连通分量有向图的极大强连通子图称作强连通分量强连通图的强连通分量是其自身非强连通的有向图可能有多个强连通分量最小生成树123245136生成树连通最小生成树是一个极小连通子图它含有图中全部顶点，但只有足以构成一棵树的n-1条边最小生成树生成树一个图可以有许多棵不同的生成树生成树具有以下共同特点：顶点个数与图的顶点个数相同是图的极小连通子图一个有n个顶点的连通最小生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树最小生成树设G=(V，E)是一个连通图则从图中任一顶点出发，遍历图G时，得到一个边集T(G)，T(G)与图中所有顶点一起构成图G的极小连通子图，它是连通图的一棵生成树。由DFS得到的是深度优先生成树由BFS得到的为广度优先生成树连通无向最小生成树V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树这些连通分量的生成树组成非连通图的生成森林非连通最小生成树ABLMCFDEGHKIJABLMCFJDEGHKI最小生成树不是唯一的从不同的顶点出发，能得到不同的生成树连通网络G=(V,E)各边带权生成树各边带权生成树的权生成树各边权值的和最小生成树权值最小的生成树最小生成树1654327131791812752410最小生成树问题提出在n个城市间建立通信网络顶点—表示城市权—城市间建立通信线路所需花费代价希望找到一条路径，使建立该通信网所需花费的总代价最小路径上各边权值的和最小问题分析n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路如何在可能的线路中选择n-1条边，把所有城市连起来，且总耗费(各边权值之和)最小找图中的最小生成树贪心（Prim）在对问题求解时，总是做出在当前看来是最好的选择算法得到的是在某种意义上的局部最优解贪心算法不是对所有问题都能得到整体最优解，但是在求最小生成树问题上适用贪心算法克鲁斯卡尔（Kruskal）算法寻找每一步当前情况下的最小路径不能形成回路无环图（DAG）一个无环（回路）的有向图叫做有向无环图AOV网顶点表示活动的网顶点表示活动弧表示活动间的先后关系AOV网中不允许有回路拓扑排序问题拓扑排序问题提出问题提出如果现在只有一名工人做整个工程，每次只能做一项活动，他应怎样安排所做事情的前后顺序，才能顺利完成此项工程。拓扑排序拓扑排序的方法从有向图中任选一个入度为0的顶点，并访问对所有以它为尾的弧，弧头顶点的入度减1删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已访问，或当图中不存在度为0的顶点为止不存在度为0的顶点:存在环拓扑排序举例V1：材料进场 V2：阀门试压 V3：预埋预留 V4：设备安装V5：管道预制 V6：支吊架安装 V7：单机试运转 V8：管道安装V9：试压、闭水 V10：卫生器具安装 V11：油漆防腐V12：冲洗消毒 V13：验收拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序拓扑序列：V1→V2→V3→V4→V5→V6→V7→V8→V9→V10→V11→V12→V13或：V1→V2→V5→V3→V6→V8→V9→V11→V10→V12→V4→V7→V13AOV网的拓扑序列不是唯一的关键路径问题987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4用有向图表示工程计划，顶点表示事件，弧表示活动每个顶点表示在它之前的活动已完成，在它之后的活动可以开始问题描述一个工程有11项活动，9个事件V1表示工程开始，V9表示