北京邮电大学-数据结构讲义课件.ppt

1、数据结构数据结构题型题型(1)p基本概念基本概念40n选择和判断，20个左右p简答或给定实例执行算法简答或给定实例执行算法30（5-65-6个题目）个题目）n概念或者某些数据结构的性质n例如：p霍夫曼编码霍夫曼编码p直接插入直接插入/冒泡冒泡/快速快速/选择选择/堆排序等算法的执行堆排序等算法的执行p链地址法哈希表装填链地址法哈希表装填p根据二叉树遍历结果画出树根据二叉树遍历结果画出树p关于图的算法执行，等等关于图的算法执行，等等题型题型(2)p算法设计题算法设计题30n常见题型的范围（2-3题目)p简单题目（数组，单层或双层循环，条件判断）简单题目（数组，单层或双层循环，条件判断）p单向链表

2、或双向链表操作（插入单向链表或双向链表操作（插入/删除删除/转置转置/合并）合并）p二分查找，简单排序算法的实现二分查找，简单排序算法的实现p二叉树（复制，相等，相似等，使用简单递归算法）二叉树（复制，相等，相似等，使用简单递归算法）第一章第一章 绪论绪论基本概念基本概念学习数据结构的意义学习数据结构的意义p是为研究和解决如何有效地组织和处理是为研究和解决如何有效地组织和处理非数值数据非数值数据而而产生的理论、技术和方法。产生的理论、技术和方法。p是计算机科学中的一门综合性的专业基础课。是计算机科学中的一门综合性的专业基础课。涉及计算机软件、硬件以及数学等涉及计算机软件、硬件以及数学等基本术语

3、基本术语p数据数据 被计算机加工处理的对象。p数据元素数据元素（记录记录、表目表目）数据的基本单位，是数据集合中的一个有意义的个体。p数据项数据项 一个数据元素可由若干个数据项数据项组成。组合项组合项年 月 日学 号姓 名班 号性别出生日期入学成绩原子项原子项基本基本术语术语2 2p数据对象数据对象 是性质相同的数据元素的集合，是数据的一个子集。学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 p数据结构数据结构 具有结构的数据元素的集合。它包括数据元

4、素的逻辑结构逻辑结构、存储结构存储结构和相适应的运算运算。数据元素 数据元素之间的逻辑关系，与计算机无关。可用一个二元组表示：Data_Structure=(D,R)D：数据元素的有穷集合，R：集合D上关系的有穷集合。例例 设有数据结构 B=(D,R)，其中 D=d1,d2,d3,d4,d5,d6，R=r，r=,，试画出其逻辑结构图。d1d2 d3 d4d5 d6逻辑结构逻辑结构（以班级学生关系为例）(1)集合结构集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构线性结构 数据元素之间存在一对一的关系。(3)树型结构树型结构 数据元素之间存在一对多的关系。(4)图

5、状结构图状结构或网状结构网状结构 数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系四种基本的逻辑结构四种基本的逻辑结构数据的逻辑结构数据的逻辑结构存储结构存储结构：数据的逻辑结构在计算机中如何表示。p数据元素的映象数据元素的映象 用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为每个数据元素的映象称为结点结点 每个数据项的映象称为每个数据项的映象称为数据域数据域p关系的映象关系的映象两种基本方法及其组合使用。两种基本方法及其组合使用。n顺序映象顺序映象：以相对的存储位置表示关系以相对的存储位置表示关系n链式映象链式映象：以附加信息：以附加信息(指针指针)表示关系表示关

6、系p注意：数据的逻辑结构和存储结构的关系n可以用数组等线形存储的方式存储逻辑上的树形结构可以用数组等线形存储的方式存储逻辑上的树形结构n也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达到提高检索速度的目的到提高检索速度的目的数据的存储结构数据的存储结构 数据的逻辑结构+运算的定义-面向用户，需求分析 （抽象数据类型）概念层 数据的存储结构+运算的实现-面向计算机 实现层数据的逻辑结构与存储结构数据的逻辑结构与存储结构抽象数据类型抽象数据类型p抽象数据类型(ADT)n一个数学模型以及定义在该模型上的一组操作一个数学模型以及定义在该模型上

7、的一组操作n“抽象抽象”是指数据类型的数学抽象特性，其定义仅仅取是指数据类型的数学抽象特性，其定义仅仅取决于它的一组逻辑特性，而与在计算机内部的表示和决于它的一组逻辑特性，而与在计算机内部的表示和实现无关实现无关算法和算法分析算法和算法分析算法的概念算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下一个算法必须满足以下五五个重要特性个重要特性p有穷性：对任何合法输入执行有穷步后能结束。p确定性：每条指令必须有确切的含义。p可行性：算法的每一条指令均能执行。p输入：有零个或多个输入。p输出：有一个或多个输出。算法的概念算法的概念和特性和特性p正确性（最重要的标准

8、）n算法应满足具体问题的需求算法应满足具体问题的需求n对于典型的、苛刻而带有刁难性的一组对于典型的、苛刻而带有刁难性的一组有效输入有效输入得到正确的得到正确的结果结果p健壮性n算法应具有容错处理。当输入算法应具有容错处理。当输入非法数据非法数据时，算法应对其作出时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果反应，而不是产生莫名其妙或随机的输出结果p可读性n算法应该好读。以有利于阅读者对程序的理解和维护算法应该好读。以有利于阅读者对程序的理解和维护p高效性：时间复杂度n算法执行占用的算法执行占用的CPU时间，随问题规模时间，随问题规模n的变化函数的变化函数p高效性：空间复杂度n算法执

9、行占用的内存总量，随问题规模算法执行占用的内存总量，随问题规模n的变化函数的变化函数评价算法优劣的基本标准评价算法优劣的基本标准算法效率的度量算法效率的度量时间复杂度空间复杂度算法执行的时间算法执行的时间p事后统计的方法n先运行依据算法的程序先运行依据算法的程序n所得时间的统计量依赖于计算机的硬件、软件等环境所得时间的统计量依赖于计算机的硬件、软件等环境因素因素n收集此算法的执行时间和实际占用空间的统计资料。收集此算法的执行时间和实际占用空间的统计资料。p事前分析估算的方法n求出该算法的一个时间界限函数；求出该算法的一个时间界限函数；时间复杂度时间复杂度pnn问题规模，一般为数据的输入量问题规

10、模，一般为数据的输入量pf(n)n算法中算法中基本操作基本操作重复执行的次数重复执行的次数频度频度n是问题规模是问题规模n n的某个函数的某个函数p算法的算法的时间量度、时间量度、时间复杂度时间复杂度n算法中各语句的频度之和算法中各语句的频度之和T(n)nT(n)=O(f(n)n随问题规模的增大，执行时间的增长率和随问题规模的增大，执行时间的增长率和f(n)的增长率相同的增长率相同时间复杂度曲线时间复杂度曲线p常见的时间复杂度：O(1),O(log2n),O(n),O(n log2n),O(n2),O(n3),O(2n)pO(1)data=e;s-next=p-next;p-next=s;带头

11、结点单链表的删除算法带头结点单链表的删除算法p具体操作存储池 p q带头结点单链表的删除算法带头结点单链表的删除算法p删除p节点之后的节点 q=p-next;if(q!=NULL)p-next=q-next;free(q);不带头单链表的转置不带头单链表的转置 pre=NULL;p=head;while(p!=NULL)t=p-next;p-next=pre;pre=p;p=t;head=pre;单链表的缺点单链表的缺点p获取节点P的前驱的算法p删除节点p的算法p替换节点p的算法p在节点p之前插入新节点的算法线性表的双向链式存储线性表的双向链式存储双向链表双向链表双链表的定义：每个节点有两个指

12、针typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;p结点的物理表示带头结点双向循环链表的插入带头结点双向循环链表的插入p将新元素e插入到双向链表中p节点前s=(DuLNode*)malloc(sizeof(DuLNode);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;.LPS带头结点双向循环链表的删除带头结点双向循环链表的删除p删除节点删除节点p p-prior-next=p

13、-next;p-next-prior=p-prior;free(p);第三章第三章 栈和队列栈和队列插入和删除操作受限的线性表插入和删除操作受限的线性表p栈和队列都是线性表，只是在操作上做了限制p栈（stack）n后进先出后进先出(LIFO:Last In First Out)的线性表的线性表n表头端称为栈底（表头端称为栈底（bottom）n表尾端称为栈顶（表尾端称为栈顶（top）n插入和删除都在栈顶进行插入和删除都在栈顶进行p队列（queue）n先进先出先进先出(FIFO:First In First Out)的线性表的线性表n表头端称为队头（表头端称为队头（front）n表尾端称为队尾（表

14、尾端称为队尾（rear）n插入在队尾进行，而删除则在队头进行插入在队尾进行，而删除则在队头进行栈的定义和基本操作栈的定义和基本操作 栈的基本操作栈的基本操作nInitStack(&s)初始化堆栈nStackEmpty(s)判断堆栈是否空npush(s,e)将元素e压入堆栈npop(s,&e)弹出栈顶元素栈的存储结构栈的存储结构p两种方式n顺序表方式（常用）顺序表方式（常用）n链表方式链表方式p顺序表方式的堆栈类型定义#define STACK_SIZE 128ElemType stackSTACK_SIZE;int top;n堆栈容量的设计：根据算法需要，分析算法的空间复杂度堆栈容量的设计：根

15、据算法需要，分析算法的空间复杂度n编号系统编号系统 0(n-1)，top记载下个空位位置，或者说，记载下个空位位置，或者说，元素个数元素个数n栈满和栈空（栈满和栈空（“上溢上溢”与与“下溢下溢”）顺序表方式的堆栈操作顺序表方式的堆栈操作#define InitStack()top=0#define StackEmpty()(top=0)Status push(elemType e)if(top=STACK_SIZE)return ERROR;stacktop+=e;return OK;顺序表方式的堆栈操作顺序表方式的堆栈操作Status pop(elemType&e)if(top=0)retu

16、rn ERROR;e=stack-top;return OK;栈的链式存储结构以及操作栈的链式存储结构以及操作p存储结构设计n不带头的单链表不带头的单链表p类型定义struct NODE ElemType data;struct NODE*next;struct NODE*stack;p操作算法nInitStacknClearStack:释放所有节点释放所有节点n其他操作：其他操作：Push,Pop，StackEmpty队列队列队列的定义队列的定义p 队列是一种特殊的线性表p 限定插入和删除操作分别在表的两端进行p 具有先进先出(FIFOFirst In First Out)的特点。队列的操作

17、队列的操作p 主要操作n 增加（入队）增加（入队）EnQueue(Q,e);n 删除（出队）删除（出队）DeQueue(Q,&e);n 判断队列是否为空判断队列是否为空 QueueEmpty(Q)p 其他操作n 初始化队列初始化队列InitQueue(Q)n 获取队列长度获取队列长度 QueueLength(Q)n 清除队列中的所有元素清除队列中的所有元素 ClearQueue(Q)队列的队列的存储结构和实现存储结构和实现p 链表方式p 顺序表方式链式队列链式队列链式队列的链式队列的其它算法其它算法n存储结构单链表，双向循环链表，带头节点n插入算法，删除算法n求队列长度n遍历队列中现有所有元素

18、使用顺序表方式实现队列使用顺序表方式实现队列循环循环队列队列(1)1)p 存储结构n 使用静态的数组或者动态申请的连续存储空间(顺序表)p 队列描述n 队头队尾p 基本算法n 增加元素:“假溢假溢”现象，解决方法：循环队列现象，解决方法：循环队列n 删除元素01234567rearfront01234567rearfrontACBA01234567rearfrontCG01234567rearfrontG01234567rearfrontHIJ循环队列循环队列(2)2)p“上溢”与“下溢”的条件：队列满和队列空的表示方法n 方法一：浪费一个存储空间，以(rear+1)%N=front判断队列满

19、n 方法二：设置队列中的数据元素计数或者队满标志第五章第五章 数组和广义表数组和广义表数组数组数组的顺序表示和实现数组的顺序表示和实现p二维数组的顺序存储方式n行优先顺序行优先顺序n列优先顺序列优先顺序n根据数组下表根据数组下表(i,j)检索顺序表中元素检索顺序表中元素K的方式的方式数组的顺序存储方式（续）数组的顺序存储方式（续）p多维数组n行优先顺序行优先顺序p规定为先排最右的下标，从右到左，最后排最左下标：n列优先顺序列优先顺序p规定为先排最左下标，从左向右，最后排最右下标。p数组的顺序存储特点n只要已知开始结点的存放地址（即基地址）、数组维数、每维的上、只要已知开始结点的存放地址（即基地

20、址）、数组维数、每维的上、下界，和每个数组元素所占用的单元数，就可以将数组元素的存放地下界，和每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数；址表示为其下标的线性函数；n数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个个。p例：数组：ElemType Amn;addr(Aij)=Base(A)+(i*n)+j)*sizeof(ElemType);addr(Aij)=Base(A)+(j*m)+i)*sizeof(ElemType);稀疏矩阵稀疏矩阵p稀疏矩阵n非零元素很少，分布没有规律；非零

21、元素很少，分布没有规律；n设矩阵设矩阵A中有中有s个非零元素，若个非零元素，若s远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即smn），），则称则称A为稀疏矩阵；为稀疏矩阵；n令令e=s/(m*n)，称，称e为矩阵的稀疏因子。通常认为为矩阵的稀疏因子。通常认为e0.05时时称之为稀疏矩阵；称之为稀疏矩阵；n在压缩存储时需要同时存储非零元素的下标和值；在压缩存储时需要同时存储非零元素的下标和值；n可用三元组存储（行号，列号，值）。可用三元组存储（行号，列号，值）。0 12 0 0 0 0 1 0 0 0 3 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 6i j

22、v1 2 122 1 12 5 33 4 55 2 25 6 6A广义表广义表 广义表的定义广义表的定义p广义表n又称列表，其每一个元素的结构都可能是不同的；又称列表，其每一个元素的结构都可能是不同的；n是是n(n0)个元素个元素a1,a2,a3,an的有限序列，其中的有限序列，其中ai或者是原子项，或者是一个广义表；或者是原子项，或者是一个广义表；n通常记作通常记作LS=(a1,a2,a3,an)pLS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。p第一个元素a1称为表LS的表头（head），由余下元素组成的表(a2,a3,.,an)称为LS的表尾（tail）。广义表中括

23、号的重数称为广义表的深度。广义表广义表的长度和深度的长度和深度n(),(e),(a,(b,c,d),(f,g)n长度4，深度3 广义表广义表操作操作p广义表的长度和深度(P108,p113)n(),(e),(a,(b,c,d),(f,g)n长度4，深度3phead与与tail操作操作(p108)nA=(a,(b,c)nHead(A)anB=Tail(A)(b,c)nC=Head(B)(b,c)nTail(B)()nHead(C)bnD=Tail(C)(c)nHead(D)cnTail(D)()nL=(a,b,c),(e,f,g)取出元素fpHead(Tail(Head(Tail(L)nL=(a

24、,b,c),x,(u,t,w)取出元素tpHead(Tail(Head(Tail(Tail(L)第六章第六章 树和二叉树树和二叉树树的定义和基本术语树的定义和基本术语树的定义树的定义p树是一类重要的非线性数据结构，是以分支关系定义的层次结构；p树是n(n0)个结点的有限集，非空树满足：n有且仅有一个特定的称之为有且仅有一个特定的称之为(root)的结点；的结点；n除根以外的其余结点可分为除根以外的其余结点可分为m(0 m1，则i的双亲是i/2。p若2in，则i无左孩子;否则，i的左孩子是2i。p若2i+1n，则i无右孩子;否则，i的右孩子是2i+1。12 34 5 6 712 34 5 6 7

25、8 9 10二叉树的存储二叉树的存储结构结构(1)(1)p顺序存储结构n按完全二叉树存储按完全二叉树存储（可以用数组这样线性的存储结构（可以用数组这样线性的存储结构存储一个非线性的数据结构）存储一个非线性的数据结构）#define MaxTreeSize 128typedef TElemType SqBiTreeMaxTreeSize;SqBiTree bt;A B C DE F1 2 3 4 5 6 7ABDEFC二叉树的存储二叉树的存储结构结构(2)(2)p顺序存储结构n用父母指针存储用父母指针存储p存储结点数据和其父结点的序号ABC DEF0112331 2 3 4 5 6ABDEFC#

26、define MaxTreeSize 100typedef struct Node Telemtype data;int parent;Node;typedef Node bTreeMaxTreeSize;二叉树的存储二叉树的存储结构结构(3)(3)p链式存储结构n用二叉链表存储用二叉链表存储p链式存储结构n用三叉链表存储用三叉链表存储 A B C D E bt A B C D E bt二叉树的存储二叉树的存储结构结构(4)(4)p二叉链表的类型定义typedef struct BiTNode TElemType data；struct BiTNode*lchild；struct BiTNod

27、e*rchild；BiTNode,*BiTree；性质：有N个节点的二叉树共有N+1个空指针，N-1个非空指针。p三叉链表的类型定义typedef struct TriTNode TElemType data；struct BiTNode*lchild；struct BiTNode*rchild；struct BiTNode*parent；TriTNode,*TriTree；遍历二叉树遍历二叉树遍历二叉树遍历二叉树p遍历二叉树n指按某条搜索路线走遍二叉树的每个结点，使得树中指按某条搜索路线走遍二叉树的每个结点，使得树中每个结点都被访问一次，且仅被访问一次。每个结点都被访问一次，且仅被访问一次。

28、根据搜索路径的不同，二叉树的遍历分为八种：1、前序遍历（、前序遍历（preorder traversal）DLR2、中序遍历（、中序遍历（inorder traversal）LDR3、后序遍历（、后序遍历（postorder traversal）LRD4、逆前序遍历（、逆前序遍历（inverse preorder traversal）DRL5、逆中序遍历（、逆中序遍历（inverse inorder traversal）RDL6、逆后序遍历（、逆后序遍历（inverse postorder traversal）RLD7、按层次遍历（、按层次遍历（level-by-level traversal

29、）8、按层次逆遍历（、按层次逆遍历（inverse level-by-level traversal）p遍历方法n先序遍历：先序遍历：ABDECn中序遍历：中序遍历：DBEACn后序遍历：后序遍历：DEBCAAB CD E遍历二叉树示例遍历二叉树示例ABDEFC1.ABDCEF1.ABDCEF2.DBAECF2.DBAECF3.3.DBEFCADBEFCA4.ACFEBD4.ACFEBD5.FCEABD5.FCEABD6.FECDBA6.FECDBA7.ABCDEF7.ABCDEF8.ACBFED8.ACBFED1-前序前序 2-中序中序 3-后序后序 4-逆前序逆前序 5-逆中序逆中序 6-

30、逆后序逆后序 7-层次层次 8-层次逆层次逆p利用遍历结果确定二叉树问题n先序序列先序序列+中序序列中序序列n中序序列中序序列+后序序列后序序列n先序序列先序序列+后序序列后序序列(x，为什么？，为什么？)先序序列:ABCDEFGH 中序序列:BDCEAFHGABFCGDEH思考：层序+先序/中序/后序，能否确定？如何做？利用遍历结果确定二叉树问题利用遍历结果确定二叉树问题(1)1)例如：层序ABCDEFGHIJ,中序DBGEHJACIF 例如：中序ABCDEFGHIJ,后序ACDBHJIGFE利用遍历结果确定二叉树问题利用遍历结果确定二叉树问题(2)2)p一棵二叉树的先序、中序和后序序列分别

31、如下，其中有一部分未显示出来，求出空格处的内容，并画出该二叉树先序：_ H _ A _ D I K C _ B中序：J _ F A D G _ K E I _ 后序：_ F _ A H C E _ B _ G先序：_ H _ A _ D I K C _ B中序：J _ F A D G _ K E I _ 后序：_ F _ A H C E _ B _ GGHAFDJCEKBIvoid Preorder(BiTree t)if(t)visit(t);Preorder(t-lchild);Preorder(t-rchild);void Inorder(BiTree t)if (t)Inorder(t

32、-lchild);visit(t);Inorder(t-rchild);void Postorder(BiTree t)if(t)Postorder(t-lchild);Postorder(t-rchild);visit(t);遍历二叉树的递归算法遍历二叉树的递归算法判断两个二叉树是否相等(相似）类似的其他递归式二叉树算法类似的其他递归式二叉树算法(1)int check(BiTree a,BiTree b)if(a=NULL)return b=NULL;if(b=NULL)return 0;if(a-data!=b-data)return 0;return check(a-lchild,b-

33、lchild)&check(a-rchild,b-rchild);交换二叉树的左右子树）void swap(BiTree t)if(t=NULL)return;tmp=t-lchild;t-lchild=t-rchild;t-rchild=tmp;swap(t-lchild);swap(t-rchild);类似的其他递归式二叉树算法类似的其他递归式二叉树算法(2)拷贝二叉树BiTree btcopy(BiTree t)if(t=NULL)return NULL;p=malloc(sizeof(*BiTree);p-data=t-data;p-lchild=btcopy(t-lchild);p-

34、rchild=btcopy(t-rchild);return p;树和森林树和森林树的存储结构：双亲表示法树的存储结构：双亲表示法A B C D E F G 0 01033 1 2 3 4 5 6ABCEFGD 存储方法：使用顺序结构存储方法：使用顺序结构#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data;int parent;PTNode;/*节点的存储结构节点的存储结构*/typedef struct/*顺序存储结构顺序存储结构*/PTNode nodesMAX_TREE_SIZE;int r,n;/*根位置和节点数根

35、位置和节点数*/PTree;优点：简单，紧凑，易于寻找双亲节点优点：简单，紧凑，易于寻找双亲节点缺点：查询某节点的孩子效率低缺点：查询某节点的孩子效率低树的存储结构树的存储结构:孩子兄弟表示法孩子兄弟表示法p孩子兄弟表示法ABCDEFGABCEFGD森林与二叉树的转换森林与二叉树的转换p转换原则n按孩子兄弟表示法进行转换。按孩子兄弟表示法进行转换。p树与二叉树的转换DE森林与二叉树的转换森林与二叉树的转换赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用p赫夫曼树n最优树；最优树；n是一类带权路径长度最短的树；是一类带权路径长度最短的树；n路径长度路径长度p指树中两个结点间路径上

36、所含有的分支数目。n树的路径长度树的路径长度p指从树根到每一结点的路径长度之和。n带权路径长度带权路径长度p指结点的路径长度与该结点的权之积。赫夫曼树赫夫曼树树的带权路径长度n树中所有叶子结点的带权路径长度；树中所有叶子结点的带权路径长度；p最优二叉树或赫夫曼树。nWPL 最小的二叉树。最小的二叉树。结点到根的路径长度权值其中：记作：kknkkklwlwwpl1赫夫曼树的构造赫夫曼树的构造p根据给定的n个权值w1,w2,.wn构成n棵二叉树的集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空；p在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的

37、二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。p在F中删除这两棵树，同时将新得到的二叉树加入F中；p重复2和3，直到F中只含一棵树为止；p这棵树就是赫夫曼树；p性质：所有节点的度要么为0，要么为2；不一定是完全二叉树；子树也是赫夫曼树例例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 2314871529291487152911358192342113581923422914871529581135819234229148715295

38、8100赫夫曼树构造赫夫曼树构造举例举例1 1例：例：已知字符 A、B、C、D、E、F、G，使用频度分别为：0.25、0.1、0.15、0.06、0.3、0.05、0.09，试以此构造霍夫曼树。GB0.19A0.44FD0.11C0.26E0.5611、0.25 0.1 0.15 0.06 0.3 0.05 0.092、0.25 0.1 0.15 0.3 0.09 0.11 3、0.25 0.15 0.3 0.11 0.19 4、0.25 0.3 0.19 0.265、0.3 0.26 0.446、0.44 0.567、1.00赫夫曼树构造赫夫曼树构造举例举例2 2GBAFDCE0000001

39、11111A:01B:001C:101D:1001E:11F:1000G:000E:100A:000B:001C:010D:011F:101G:110000000111111GBAFDCE0WPL霍夫曼编码=2.56WPL等长编码=3 利用赫夫曼编码可提高效率：(3-2.56)/3 15%赫夫曼编码赫夫曼编码赫夫曼编码的特点赫夫曼编码的特点n不等长编码不等长编码 赫夫曼编码是不等长编码n前缀编码前缀编码 赫夫曼编码是赫夫曼编码是前缀编码前缀编码，即任一编码，即任一编码另一字符编另一字符编码的前缀码的前缀n发送过程（编码）发送过程（编码）根据由赫夫曼树得到的编码表根据由赫夫曼树得到的编码表 送出

40、字符数据送出字符数据n接收过程（解码）接收过程（解码）按左按左0、右、右1的规定，从根结点走到一个叶结点，完成一的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束个字符的译码。反复此过程，直到接收数据结束第七章第七章 图图本章内容本章内容p定义和术语p存储结构：邻接矩阵、邻接表，十字链表，邻接多重表p两种遍历策略：深度优先搜索和广度优先搜索p连通性和最小生成树p拓扑排序和关键路径(AOV,AOE)p求最短路径问题的解法图的基本概念图的基本概念图的定义图的定义和术语和术语(1)(1)p图Gn由两个集合由两个集合V(G)和和E(G)组成，记作组成，记作G=(V,E)n

41、其中其中V(G)是顶点的非空有穷集合，是顶点的非空有穷集合，E(G)是边的有穷是边的有穷集合，而边是顶点的无序对或有序对。集合，而边是顶点的无序对或有序对。112323423图的基本术语图的基本术语(2)(2)p顶点(vertex)n数据元素所构成的结点通常称为顶点。数据元素所构成的结点通常称为顶点。p弧(arc)n若两个顶点间有关系若两个顶点间有关系E，则称，则称为一条弧。为一条弧。p弧头(又称终端点)n若若为一条弧，则顶点为一条弧，则顶点 y 称为弧头。称为弧头。p弧尾(又称初始点)n若若为一条弧，则顶点为一条弧，则顶点 x 称为弧尾。称为弧尾。p边(Edge)n无向图中两条弧无向图中两条

42、弧和和可用一条边可用一条边(x,y)来表示来表示。图的基本图的基本术语术语(3)(3)p顶点的度（degree）n无向图：与顶点相关联的无向图：与顶点相关联的边边数称为该顶点的度数称为该顶点的度n有向图：分为入度和出度有向图：分为入度和出度 p顶点的入度（indegree）n以顶点为头的弧数称为该顶点的入度以顶点为头的弧数称为该顶点的入度。p顶点的出度（outdegree）n以顶点为尾的弧数称为该顶点的出度以顶点为尾的弧数称为该顶点的出度。p路径（path）n由顶点由顶点vi经过一系列边和顶点到达顶点经过一系列边和顶点到达顶点vj所得到的顶点序列。所得到的顶点序列。p回路（loop-又称环 c

43、ycle）n起点和终点为同一顶点的路径称为回路。起点和终点为同一顶点的路径称为回路。ABCEFD图的基本图的基本术语术语(4)(4)p简单路径n(路径的顶点路径的顶点)序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。p简单回路(简单环)n除路径起点和终点相同外，其余顶点均不相同的回路。除路径起点和终点相同外，其余顶点均不相同的回路。p稀疏图n边数很少的图边数很少的图(如如enlogn)。p稠密图n边数很多的图。边数很多的图。p权(weight)n有些图的边或弧具有一定的大小，称之为权。有些图的边或弧具有一定的大小，称之为权。p网n带权值的图又称为网或网络。带权值的图又称为网或网络。AB

44、CEFD图的基本图的基本术语术语(5)(5)p子图n由图的部分顶点和边组成的新图称为原图的子图。由图的部分顶点和边组成的新图称为原图的子图。p生成子图n由图的全部顶点和部分边组成的子图称为原图的生成子图。由图的全部顶点和部分边组成的子图称为原图的生成子图。p邻接点n若边若边(vi,vj)E，则，则 vi与与vj互为邻接点。互为邻接点。图的基本图的基本术语术语(6)(6)p有向图n若若E，并不总有，并不总有E，则称此图为有，则称此图为有向图向图p无向图n若若E，总有，总有E，则称此图为无向图，则称此图为无向图p完全图n具有具有 n*(n-1)/2条边的无向图称为完全图。条边的无向图称为完全图。p

45、有向完全图n具有具有 n*(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。图的基本术语图的基本术语(7)(7)p生成树n连通图的极小连通生成子图称为原图的生成树。连通图的极小连通生成子图称为原图的生成树。p生成森林n由多棵有向树构成的有向图的生成子图称为生成森林。由多棵有向树构成的有向图的生成子图称为生成森林。p最小代价生成树n连通网中由最小权值的边构成的生成树。连通网中由最小权值的边构成的生成树。图的存储图的存储图的存储结构：邻接矩阵图的存储结构：邻接矩阵p数组表示法n邻接矩阵邻接矩阵ABCEFDAij=0 (vi,vj)E1 (vi,vj)EA B C D E F0 0

46、0 0 0 11 0 1 0 0 00 0 0 1 0 00 0 0 0 1 00 1 0 0 0 00 0 0 0 1 0ABCDEF#define Infinity INT_MAXtypedef enumDG,DN,AG,AN GraphKind;typedef struct ArcCell VRType adj;InfoType*info;ArcCell,AdjMatrix2020;typedef struct Gragh VertexType vexs20;int vtxnum,arcnum;AdjMatrix arcs;GraghKind kind;Gragh;带权图的存储带权图的存

47、储结构结构:邻接邻接矩阵矩阵 邻接矩阵 3 2 4 5 2 32 5 42Aij=(vi,vj)E权值权值 (vi,vj)EA B C D图的遍历图的遍历图的遍历图的遍历图的遍历n按某种搜索顺序对图中每个结点访问且仅访问一次。按某种搜索顺序对图中每个结点访问且仅访问一次。n遍历图的两种方式n深度优先搜索深度优先搜索 DFSn广度优先搜索广度优先搜索 BFS深度优先搜索深度优先搜索n类似树的先根边历n从某顶点 v0 出发，访问该顶点n依次从v0的未被访问过的邻接点中选取一个顶点作为新出发点;用同样的方法访问其它所有未被访问过邻接顶点n若此时仍有顶点未被访问，则从未被访问过的顶点中任意选取一个顶点

48、作为新的出发点；n反复此过程，直至图中所有顶点均被访问过一遍为止。ABCEFGDHA BFEH C D G广度优先搜索广度优先搜索p类似树的按层次遍历p从某顶点v0出发，访问该顶点p依次访问v0的所有未被访问过的邻接点p然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0 连通的顶点均被访问到为止；p若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点；p反复此过程，直至图中所有顶点均被访问过一遍为止。ABCEFGDHA BC FH D G E最小生成树最小生成树无向图的连通分量和生成树无向图的连通分量和生成树p无向图的连通分量n从图中任一

49、顶点出发，一次调用深度或广度优先搜从图中任一顶点出发，一次调用深度或广度优先搜索所得到的顶点集即为连通分量中的顶点集。索所得到的顶点集即为连通分量中的顶点集。p生成树n连通分量中的节点，连同遍历时走过的边，连通分量中的节点，连同遍历时走过的边，构成图的生成树构成图的生成树n非连通图，多个生成树，形成生成森林非连通图，多个生成树，形成生成森林最小生成树最小生成树p定义n由一个网络生成的各边的权数总和最小的生成树；由一个网络生成的各边的权数总和最小的生成树；p构造算法nPrim算法算法nKruskal算法算法PrimPrim算法算法p将图中顶点分为两个集合，其中集合 X 包含图的一个顶点 v0，集

50、合 Y 包含除 v0 外的其它所有顶点；p将跨接这两个集合的权值最小的边加入图中，并将其依附在该边的集合 Y 中的顶点 v1 从 Y 中移入集合 X 中；p反复过程 2，直到集合 Y 为空，所得生成子图即为最小生成树。p算法复杂性O(n2)ABCEFD2313221ABCEFD21321拓扑排序与关键路径拓扑排序与关键路径拓扑排序拓扑排序p拓扑排序n由某集合上的一个由某集合上的一个偏序偏序得到该集合上的一个得到该集合上的一个全序全序pAOV 网(Activity On Vertex)n有向边表示两个活动间的有向边表示两个活动间的次序关系次序关系n顶点表示活动顶点表示活动n这类图又称为顶点活动图