数据结构(C语言)

《数据结构(C语言)》由会员分享，可在线阅读，更多相关《数据结构(C语言)（395页珍藏版）》请在金锄头文库上搜索。

1、主菜单广东交通职业基数学院计算机系广东交通职业基数学院计算机系课件设计课件设计数据结构（数据结构（C C语言）语言）DATASTRUCTURE第页主菜单教材教材数据结构数据结构（C语言）语言）曲建民曲建民刘元红刘元红郑陶然郑陶然清华大学出版社清华大学出版社参考教材参考教材1数据结构数据结构（C语言版）语言版）严蔚敏吴伟民清华大学出版社 2数据结构题集数据结构题集（C语言版）语言版） 严蔚敏吴伟民清华大学出版社第页主菜单课程特点及课时分配n难度大难度大 综合性强综合性强 必须下苦功学习必须下苦功学习n课程说明课程说明n考试考试n每周每周4节，共节，共20周周n评分标准：平时成绩评分标准：平时成绩

2、20（包括考勤、课堂回（包括考勤、课堂回答问题等）、期中成绩答问题等）、期中成绩30，期末成绩，期末成绩50第页主菜单教学内容教学内容第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 栈和队列栈和队列第四章第四章 数组和串数组和串第五章第五章 树树第六章第六章 图图第七章第七章 内部排序内部排序第八章第八章 查找查找第九章第九章 文件文件第页主菜单第页主菜单 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语 1.3 1.3 运算、算法和算法分析运算、算法和算法分析主要知识点第页主菜单数据处理的种类和能力数据处理的种类和能力数据数据数值数据：

3、数值数据：数数(整数整数,实数实数)非数值数据：非数值数据：字符字符字符串字符串文字文字图形图形图象图象声音声音数据：数据：客观对象的符号表示客观对象的符号表示数学中的整数、实数，数学中的整数、实数，课程名，地名、书名课程名，地名、书名1.1 什么是数据结构数据结构要解决的问题数据结构要解决的问题第页主菜单数值问题与非数值问题数值问题与非数值问题1）数值问题）数值问题例例1已知：游泳池的长已知：游泳池的长len和宽和宽wide，求面积求面积area设计设计求解问题的方法求解问题的方法 编程编程main()intlen,wide,area;scanf(“%d%d%n”,&l,&w);area=l

4、en*wide;printf(“area=%d”,area); 建模型：建模型：问题涉及的对象：游泳池的长问题涉及的对象：游泳池的长len宽宽wide，面积面积area；对象之间的关系：对象之间的关系：area=len wide1.1 什么是数据结构第页主菜单学号学号姓名姓名性别性别出生日期出生日期籍贯籍贯入学成绩入学成绩所在班级所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机100202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机32）非数值问题）非数值问题例例2已知某级

5、学生情况已知某级学生情况,要求分班按入学成绩排列顺序。要求分班按入学成绩排列顺序。在这类文档管理的数学模型中在这类文档管理的数学模型中,计算机处理的对象之间通常存在计算机处理的对象之间通常存在着一种最简单的线性关系着一种最简单的线性关系,这类数学模型称为线性模型。这类数学模型称为线性模型。1.1 什么是数据结构第页主菜单n城市间交通网问题1.1 什么是数据结构第页主菜单数据结构数据结构的研究问题：的研究问题： 非数值数据之间的结构关系，非数值数据之间的结构关系，及如何表示，如何存储，如何处理。及如何表示，如何存储，如何处理。本课程讨论的问题：本课程讨论的问题： 应用中常用的几种数据间的结构关系

6、，应用中常用的几种数据间的结构关系，及如何表示及如何表示, ,如何存储，如何处理。如何存储，如何处理。1.1 什么是数据结构第页主菜单 数据：数据：客观对象的符号表示。客观对象的符号表示。 例如：学号，姓名，班名都是数据。例如：学号，姓名，班名都是数据。 数据元素：数据元素：数据的基本单位。相当于数据的基本单位。相当于“记录记录”, ,在在计计 算机程序中通常作为一个整体考虑和处理算机程序中通常作为一个整体考虑和处理 数据项数据项: : 相当于记录的相当于记录的“域域”, , 是数据的不可分割是数据的不可分割 的最小单位。的最小单位。 如：学号如：学号 数据对象：数据对象：性质相同的数据元素的

7、集合性质相同的数据元素的集合. . 例如例如: : 所有班名相同的记录集合所有班名相同的记录集合 数据结构：数据结构：是相互间存在关系的数据元素集合。是相互间存在关系的数据元素集合。1.2 基本概念和术语第页主菜单对每种数据结构，主要讨论如下两方面的问题：对每种数据结构，主要讨论如下两方面的问题： 1 1） 数据的逻辑结构，数据的逻辑结构，数据结构的数据结构的基本操作；基本操作； 2 2） 数据的存储结构，数据的存储结构，数据结构数据结构基本操作的实现；基本操作的实现；数据的逻辑结构：数据的逻辑结构： 数据之间的结构关系，是数据之间的结构关系，是具体具体关系的抽象。关系的抽象。数据结构的数据结

8、构的基本操作：基本操作： 指对数据结构的加工处理指对数据结构的加工处理数据的存储结构数据的存储结构 ( (物理结构物理结构) )： 数据结构在计算机内存中的表示数据结构在计算机内存中的表示数据结构数据结构基本操作的实现：基本操作的实现： 基本操作在计算机上的实现（方法基本操作在计算机上的实现（方法) )1.2 基本概念和术语第页主菜单n数据的逻辑结构通常有四种基本结构：数据的逻辑结构通常有四种基本结构：n集合集合n线性结构线性结构n树型结构树型结构n图结构图结构1.2 基本概念和术语第页主菜单一、运算一、运算n加工型运算加工型运算n插入运算插入运算n删除运算删除运算n更新运算更新运算n应用型运

9、算应用型运算n查找运算查找运算n读取运算读取运算1.3 运算、算法和算法分析第页主菜单二、算法及其描述二、算法及其描述 算法算法是对求解某个问题的步骤的一种描述方法或操作序列。是对求解某个问题的步骤的一种描述方法或操作序列。 算法的基本特征：算法的基本特征：1 1）输入：）输入：0 0个或多个输入；个或多个输入；2 2）输出：）输出：1 1个或多个输出；个或多个输出；3 3）有穷性：算法必须在有限步内结束；）有穷性：算法必须在有限步内结束；4 4）确定性：组成算法的操作必须清晰无二义性。）确定性：组成算法的操作必须清晰无二义性。5 5）可行性：组成算法的操作必须能够在计算机上实现。）可行性：组

10、成算法的操作必须能够在计算机上实现。 求两个正整数求两个正整数 m m，n n 中的最大数中的最大数MAXMAX的算法的算法 （1 1）若若 m n m n 则则 max=mmax=m （2 2）若若 m = n m = n 则则 max=n max=n 例例1.3 运算、算法和算法分析第页主菜单描述算法的书写规则描述算法的书写规则n所有算法均以函数形式给出,算法的输入数据来自参数表n参数表的参数在算法之前均进行类型说明n有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明1.3 运算、算法和算法分析第页主菜单评价算法标准评价算法标准算法的正确性，易读性，可维护性，健壮性，高效率等

11、。算法的正确性，易读性，可维护性，健壮性，高效率等。算法时间复杂度算法时间复杂度T（n）本课程采用以求解问题的基本操作的执行次数作为算法时间的度量本课程采用以求解问题的基本操作的执行次数作为算法时间的度量算法的空间复杂度算法的空间复杂度S(n)一个算法所需要辅助存储空间的多少为空间复杂度一个算法所需要辅助存储空间的多少为空间复杂度O（n3）称为矩阵相乘算法称为矩阵相乘算法时间复杂度时间复杂度；O（n3）表示矩阵相乘算法执行时间与表示矩阵相乘算法执行时间与n3成正比成正比,即即O（n3）与）与n3同一数量级；同一数量级；n阶矩阶矩阵相乘的算法阵相乘的算法For(i=1;i=n;i+)For(j=

12、1;j=n;j+)cij=0;For(k=1;k=n;k+)cij+=aik*bkj乘法乘法加法加法执行次数均为执行次数均为n3例例1.3 运算、算法和算法分析第页主菜单有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑（1）算法平均时间复杂度算法平均时间复杂度（2）算法在最坏情况下的时间复杂度算法在最坏情况下的时间复杂度算法的时间复杂度算法的时间复杂度一般来说，设算法中基本操作的执行次数是问题规模一般来说，设算法中基本操作的执行次数是问题规模n的某个函数的某个函数f(n)，算法的时间复杂度算法的时间复杂度记作：记作：T(n)=

13、O(f(n)它表示随问题规模它表示随问题规模n的增大，算法执行时间的增长率与的增大，算法执行时间的增长率与f(n)的增长率的增长率相同。相同。1.3 运算、算法和算法分析第页主菜单算法的时间复杂度为算法的时间复杂度为O(N3) 100元买元买100支笔支笔,其中钢笔其中钢笔3元元/支支,圆珠笔圆珠笔2元元/支支,铅铅笔笔0.5元元/支支.写算法输出各种组合方案写算法输出各种组合方案解法解法1#defineN100voidscheme()inti,j,k,count,money;for(i=0;i=N;i+)for(j=0;j=N;j+)for(k=0;k=N;k+)count=i+j+k;mo

14、ney=3*i+2*j+0.5*k;if(count=N&money=N)printf(“%d,%d,%dn%”,i,j,k);例例1.3 运算、算法和算法分析第页主菜单2算法空间复杂度算法空间复杂度在本课程中，用执行算法所需的辅助空间的大小作为算法所在本课程中，用执行算法所需的辅助空间的大小作为算法所需空间的度量。需空间的度量。设执行算法所需的辅助空间是问题规模设执行算法所需的辅助空间是问题规模n的某个函数的某个函数g(n),则算法空间复杂度记作：则算法空间复杂度记作：S（n）=O(g(n)表示算法辅助空间的增长率表示算法辅助空间的增长率与与g(n)的增长率相同的增长率相同1.3 运算、算法

15、和算法分析第页主菜单计算计算解法解法1先计算先计算x的幂的幂,存于存于power中中,再分别乘以相应的系数再分别乘以相应的系数#defineN100floatevaluate(floatcoef,floatx,intn)floatpowerN,f;inti;for(power0=1,i=1;i=n;i+)poweri=x*poweri-1;for(f=0,i=0;i=0;i-)f=f*x+coefi;return(f);时间复杂度为时间复杂度为O(n).空间复杂度为空间复杂度为O(1)1.3 运算、算法和算法分析第页主菜单第页主菜单2.1线性表的定义和基本运算2.2线性表的顺序存储结构2.3线

16、性表的链式存储结构2.3.1单链表2.3.2循环链表2.3.3双向链表2.4线性表的应用举例主要内容第页主菜单第二章线性表线性结构特点：在数据元素的非空有限集中n存在唯一的一个被称作“第一个”的数据元素n存在唯一的一个被称作“最后一个”的数据元素n除第一个外，集合中的每个数据元素均只有一个前驱n除最后一个外，集合中的每个数据元素均只有一个后继第页主菜单n2.1线性表的逻辑结构n定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,.Z)是一个线性表数据元素n特征：n元素个数n表长度，n=0空表n1idata表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生

17、成一个JD型新结点：p=(JD*)malloc(sizeof(JD);系统回收p结点：free(p)2.3.1线性链表n定义：结点中只含一个指针域的链表叫，也叫单链表第页主菜单头结点：在单链表第一个结点前附设一个结点叫头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空头结点指针域为空表示线性表为空ha1a2头结点头结点an.h空表第页主菜单n单链表的基本运算n查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULLn算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为npabxsn算法评价n插入：在线性表两个数据元素a和b间插

18、入x，已知p指向as-link=p-link;p-link=s;n算法描述n算法评价第页主菜单n算法描述pabcn算法评价n删除：单链表中删除b，设p指向ap-link=p-link-link;第页主菜单n动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针n算法描述n算法评价h头结点an0h头结点an-10ana2.h头结点an-10anha1a2头结点an.0Ch2_3.ch头结点0第页主菜单n单链表特点n它是一种动态结构，整个存储空间为多个链表共用n不需预先分配空间n指针占用额外存储空间n不能随机存取，查找速度慢第页主菜单n循环链表(circularlinke

19、dlist)n循环链表是表中最后一个结点的指针指向头结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同n单链表p或p-link=NULLn循环链表p或p-link=Hhh空表第页主菜单n双向链表（doublelinkedlist）单链表具有单向性的缺点n结点定义typedefstructnodedatatypeelement;structnode*prior,*next;JD;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next=p=p-next-proir;第页主菜单bc

20、aPvoiddel_dulist(JD*p)p-prior-next=p-next;p-next-prior=p-prior;free(p);n删除n算法描述n算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;第页主菜单voidins_dulist(JD*p,intx)JD*s;s=(JD*)malloc(sizeof(JD);s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;n算法描述n算法评价：T(n)=O(1)xSbaPn插入第页主菜单1循环链表的概念循环

21、链表的概念循环链表是线性表的另一种链式存储结构，它的特循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一点是将线性链表的最后一个结点的指针指向链表的第一个结点个结点2循环链表图示循环链表图示(a)非空表 （b）空表headheadheadheada1an2.3.2 循环链表第页主菜单单向循环链表说明说明在在解决某些实际问题时循环链表可能要比线性链表方便些。解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；如将一个链表链在另一个链表的后面；循循环链表与线性链表操作的主要差别是算法中循环结束的环链表与线性链表操作的主要差别

22、是算法中循环结束的条件不是条件不是p或或p-link是否为是否为NULL,而是它们是否等于首指针；而是它们是否等于首指针；对对循环链表，有时不给出头指针，而是给出尾指针循环链表，有时不给出头指针，而是给出尾指针a aa1an给出尾指针的循环链表2.3.2 循环链表第页主菜单b ba aa1anb bb1bna aa1anb1bnq qq qp pp pp=a-link;q=b-link;a-link=q-link;b-link=p;free(q);2.3.2 循环链表第页主菜单1双向链表的概念双向链表的概念(a)(a)结点图示结点图示数据域指针域指针域结点结点存储数据元素存储数据元素datad

23、ata存储后继结点存储后继结点 的地址的地址nextnext存储前趋结点存储前趋结点 的地址的地址priorprior双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.3.3 双向链表第页主菜单2双向链表图示双向链表图示headhead (b)空的双向循环链表（c）非空的双向循环链表headheadabtypestructdulnode*pointer;Typestructdulnodedatatypedata;pointerprior,next;dulnode;2.3.3 双向链表第页主菜单在双向链表中删除结点时指针变化情况在双向链表中删除结点时指针

24、变化情况在双向链表中插入一个结在双向链表中插入一个结点时指针的变化情况点时指针的变化情况pai-1xaipaiai+1ai-13、双向链表的基本操作算法2.3.3 双向链表p第页主菜单1）插入操作算法）插入操作算法(在在p所指结点之后插入所指结点之后插入q结点的过程结点的过程)q=(NODE*)malloc(sizeof(NODE);q-data=x;q-rlink=p-rlink;q-llink=p;p-rlink=q;(q-rlink)-llink=q;2.3.3 双向链表第页主菜单2）删除操作算法）删除操作算法(p-llink)-rlink=p-rlink;(p-rlink)-llink

25、=p-llink;free(p);aiai+1pai-12.3.3 双向链表第页主菜单n2.4线性表的应用举例一元多项式的表示及相加n一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表第页主菜单n单链表的结点定义typedefstructnodeintcoef,exp;structnode*next;JD;coefexpnext-1A703198517-1B81227-98-1C70111227517n一元多项式相加第页主菜单设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与

26、q-expp-expexp:p结点是和多项式中的一项p后移,q不动p-expq-exp:q结点是和多项式中的一项将q插在p之前,q后移,p不动p-exp=q-exp:系数相加0：从A表中删去p,释放p,q，p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL若q=NULL，结束若p=NULL，将B中剩余部分连到A上即可n运算规则第页主菜单q-1pa703198517-1pb81227-98ppreq-1pa703198517-1pb81227-98ppreq-1pa7011198517-1pb81227-98ppreq-1pa7011198517-1pb81227-98ppreq

27、=NULL-1pa7011198517-1pb81227-98ppreq=NULL-1pa7011198517-1pb81227-98ppre-1pa70111227517Ch2_算法描述第页主菜单数据结构第页主菜单主要内容n栈的定义n栈的存储结构及其运算的实现第页主菜单栈是限定仅能在表尾一端进行插入、删除操作的线性表栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,.,ai-1,ai,ai+1,an）插入删除一一什么是栈什么是栈3.1.1 栈的定义栈的定义第页主菜单第一个进栈的元素在第一个进栈的元素在栈底栈底，最后一个进栈的元素在最后一个进栈的元素在栈顶栈顶，第一个出栈的元素为第

28、一个出栈的元素为栈顶元素栈顶元素，最后一个出栈的元素为最后一个出栈的元素为栈底元素栈底元素。不含元素的栈称为不含元素的栈称为空栈空栈。出栈出栈 PopPop进栈进栈 PushPush栈顶栈顶栈底栈底二二.栈的逻辑结构栈的逻辑结构toptopbottombottom空栈空栈toptopbottombottoman. . . .a2a1第页主菜单bottombottomtoptopbottombottomtoptopA AA AB BC CD DE EA AB B 栈操作图示栈操作图示 A A进栈进栈 B C D E B C D E 进栈进栈E D C E D C 出栈出栈C CD DE Etop

29、toptoptoptoptop栈的特点栈的特点后进先出后进先出LIFOLIFO入栈与出栈入栈与出栈toptopbottombottomtoptopbottombottomtoptoptoptoptoptop第页主菜单思考：假设有思考：假设有A,B,C三个元素进三个元素进S栈的顺序是栈的顺序是A,B,C，写出所有可能的出栈序列。写出所有可能的出栈序列。CBAACBABCCABBACBCA第页主菜单如果是如果是4个元素，那么它个元素，那么它不可能的出栈序列有哪些？不可能的出栈序列有哪些？可能的出栈序列：可能的出栈序列：1234 1243 1324 1342 1432 2134 2143 23142

30、341 2431 3241 321423423421 4321不可能出现的出栈序列：不可能出现的出栈序列：1423 2413 31243142 3412 41234132 4231 421341334312第页主菜单栈是一种线性表，它的特点是栈是一种线性表，它的特点是 A A 。设用一维数组。设用一维数组 A1A1，nn来表示一个栈，令来表示一个栈，令AnAn 为栈底。用整型变量为栈底。用整型变量T T指示当前栈顶位置，指示当前栈顶位置，ATAT为栈顶元素。往栈中推入（为栈顶元素。往栈中推入（PUSHPUSH）一个新元素时，变量）一个新元素时，变量T T的值的值 B B ，从栈中弹出（，从栈中

31、弹出（POPPOP）一个元素时，变量）一个元素时，变量T T的值的值 C C 。设栈空时，。设栈空时，有输入序列有输入序列a,b,ca,b,c，经过，经过PUSHPUSH，POPPOP，PUSHPUSH，PUSHPUSH，POPPOP操作后，操作后，从栈中弹出的元素序列是从栈中弹出的元素序列是 D D ，变量，变量T T的值是的值是 E E 。A A：1 1）先进先出）先进先出 2)2)后进先出后进先出 3 3）进优于出）进优于出 4 4）出优于进）出优于进 5 5）随机进出）随机进出B B、CC：1 1）加）加1 21 2）减）减1 31 3）不变）不变 4 4）清）清0 50 5）加）加2

32、 62 6）减）减2 2D D：1 1）a,ba,b 2 2）b,cb,c 3 3）c,ac,a 4 4）b,ab,a 5 5）c,bc,b 6 6）a,ca,cE E：1 1）n+1n+1 2 2）n+2 3n+2 3）n 4n 4）n-1 5n-1 5）n-2n-2水平考试试题第页主菜单 设有四个数据元素设有四个数据元素a1,a2,a3和和a4，对它们进行栈操作。在，对它们进行栈操作。在进栈操作时，按进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假次序每次进入一个元素。假设栈的初始状态都是空。现要进行栈操作是进栈两次，出栈一设栈的初始状态都是空。现要进行栈操作是进栈两次，出栈一

33、次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是，第二次出栈得到的元素是 B 经操作后，最后在栈中的元经操作后，最后在栈中的元素还有素还有 C 个。个。供选择的答案供选择的答案 A：1）a1 2）a2 3）a34）a4 B：1）a1 2）a2 3）a3 4）a4 C：1）1 2）2 3）34）0水平考试试题第页主菜单1.栈属于加了限制条件的线性结构；栈属于加了限制条件的线性结构；2.栈是后进先出的线性表；栈是后进先出的线性表；3.进栈和出栈只能从栈的一个端点进行；进栈和出栈只能从栈的一个端点进行；4.栈中

34、的元素个数可以是栈中的元素个数可以是0，此时是空栈；，此时是空栈；5.栈的元素的个数是可以变化的，可以是多栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个；个，但不能是无穷多个；6.每个栈中的元素的类型相同每个栈中的元素的类型相同.栈的特性栈的特性第页主菜单栈的应用栈的应用n实现数制转换n实现函数的递归n行编辑：接受用户从终端输入的程序或数据，并存入用户的数据区n表达式求值：一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果Flash演示第页主菜单三三 栈的基本操作栈的基本操作n初始化IniStack(S):n构造一个空栈S，准备存放数据；

35、n进栈操作Push(S,x)：n将数据元素x插入栈S，使x成为S的栈顶元素；n出栈操作Pop(S)：n当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素；n取栈顶元素GetTop(S)：n当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变；n判栈空EmptyStack(S)：n若S为空栈则该函数值为1，否则为0。第页主菜单一、栈的顺序存储结构一、栈的顺序存储结构用一个一维数组和一个整型变量来实现。用一个一维数组和一个整型变量来实现。structstruct stack stack datatypedatatype arraymaxlenarraymaxlen;intint top; top;

36、 栈数组栈数组 arraymaxlen用来存放栈中所有元素；用来存放栈中所有元素； 整型变量整型变量top的整数值表示栈顶元素在数组的整数值表示栈顶元素在数组array中的位置，中的位置，也称为也称为栈顶指针栈顶指针。3.1.2 栈的存储结构及其运算的实现栈的存储结构及其运算的实现第页主菜单约定约定栈顶指针指向向栈顶元素的位置当栈用顺序结构存储时，当栈用顺序结构存储时，栈的基本操作如建空栈、栈的基本操作如建空栈、进栈、出栈等操作进栈、出栈等操作如何实现？如何实现？顺序栈的图示顺序栈的图示toptopMAX-1MAX-1n nn-1n-1n-2n-21 10 0a an na an-1n-1a

37、a2 2a a1 1栈空：栈空：栈满：栈满：Top=-1Top=maxlen-1第页主菜单1)初始化栈初始化栈viodinitstack(structstacks)s.top=-1;MAX-1MAX-1n nn-1n-1n-2n-21 10 0建立空栈建立空栈toptop第页主菜单2 ) 2 ) 进栈操作进栈操作 viodviod Push ( Push ( structstruct stack s, stack s, datatypedatatype x ) x ) s.tops.top=s.top+1;=s.top+1;s.arraytops.arraytop=x=x； MAX-1MAX-

38、1n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1x进栈前进栈前toptopx进栈后进栈后MAX-1MAX-1n nn-1n-1n-2n-21 10 0toptopx xa an na an-1n-1a a2 2a a1 1第页主菜单3 3）出栈操作）出栈操作intint pop( pop( structstruct stack s ) stack s ) return(arrays.topreturn(arrays.top) ; ) ; s.tops.top- ;- ; 出栈操作前出栈操作前MAX-1MAX-1n nn-1n-1n-2n-21

39、10 0a an na an-1n-1a a2 2a a1 1toptop出栈操作后出栈操作后MAX-1MAX-1n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1toptop第页主菜单栈在运算过程中可能发生栈在运算过程中可能发生“溢出溢出”现象：现象：上溢上溢下溢下溢toptopMAX-1MAX-1n nn-1n-1n-2n-21 10 0a an na an-1n-1a a2 2a a1 1MAX-1MAX-1n nn-1n-1n-2n-21 10 0toptop第页主菜单2）进栈操作）进栈操作viodviod Push Push（struct

40、struct stack stack s,datatypes,datatype x x ） s.tops.top=s.top+1;=s.top+1; s.arraytops.arraytop=x=x； if if （s.tops.top=MAXlen-1=MAXlen-1） error(error(“栈满栈满”) ) else else 第页主菜单3）出栈操作）出栈操作intint pop pop （structstruct stack s stack s ） returnreturn（arrays.toparrays.top ） ; ; s.tops.top; ; if if （s.tops

41、.top=-1=-1） ErrorError（“emptystackemptystack”）；）； else else 第页主菜单顺序栈的不足：顺序栈的不足：存在栈满以后就不能再进栈的问题存在栈满以后就不能再进栈的问题（这是因为用了定长的数组存储栈的元素）（这是因为用了定长的数组存储栈的元素）解决方法：解决方法：使用链式存储结构。使用链式存储结构。第页主菜单二二、栈的链式存储和实现、栈的链式存储和实现栈的链式存储结构，也称链栈。其各结点的结构与单栈的链式存储结构，也称链栈。其各结点的结构与单链表中的结点结构完全相同。如图所示：链表中的结点结构完全相同。如图所示：在前面学习了线性链表的插入在前面

42、学习了线性链表的插入删除操作算法，不难写出链式删除操作算法，不难写出链式栈初始化、进栈、出栈等操作栈初始化、进栈、出栈等操作的算法的算法结点结构定义：结点结构定义：TypedefTypedef structstruct node node elemtypeelemtype data; data;structstruct node *next; node *next;node,*pointer;node,*pointer;Data nextData nexts s栈顶（单链栈顶（单链表的表头）表的表头）栈底栈底a an-1n-1a a1 1a an n第页主菜单(1) (1) 初始化栈初始化栈V

43、oid Void initstackinitstack（pointer spointer s） s=null; s=null; s第页主菜单Data nextData nexts s栈顶栈顶栈底栈底a an-1n-1a a1 1a an nData nextData next栈顶栈顶栈底栈底a an-1n-1a a1 1a an n x xp ps s进栈前进栈前 进栈后进栈后(2) 进栈进栈第页主菜单进栈算法进栈算法Void push(pointer Void push(pointer s,datatypes,datatype x) x) p= (pointer *) p= (pointer

44、 *) mallocmalloc ( ( sizeofsizeof (node ); (node ); p-data=x; p-data=x; p-next=s-next; p-next=s-next; s-next=p; s-next=p; 第页主菜单出栈前出栈前 出栈后出栈后Data nextData next栈顶栈顶栈底栈底a an-1n-1a a1 1a an ns sData nextData nextp p栈顶栈顶栈底栈底a an-1n-1a a1 1a an n x xs s(3) 出栈出栈第页主菜单出栈算法出栈算法DatatypeDatatype pop ( pointer s

45、 ) pop ( pointer s ) if (s-next=null) return(null); if (s-next=null) return(null); else else p=s-next; p=s-next; x=p-data; x=p-data; s-next=p-next; s-next=p-next; free(p); free(p); return(xreturn(x); ); 第页主菜单3.2.1队列的定义队列的定义队列是限定仅能在表头进行删除，表尾进行插入的线队列是限定仅能在表头进行删除，表尾进行插入的线性表性表（a1,a2,.,ai-1,ai,ai+1,an）插入

46、插入删除删除3.2 队列第页主菜单 a a1 1 a a2 2 a a3 3 a an n入队列入队列队队头头队队尾尾出队列出队列队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出说明：说明：第一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素3.2 队列第页主菜单rearfrontJ1J2rearfrontJ2（a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4和J5相继入队之后,J2出队rearf

47、ront-101234rearfrontJ5J4J3front,rear均为整数用箭头指示只是为了直观又有又有J6入队入队,怎么办？怎么办？3.2 队列第页主菜单3.2.2队列的基本操作队列的基本操作1）初始化操作）初始化操作initQueue(Q)：建立一个空队列建立一个空队列Q，准备存放数据；准备存放数据；2）入队操作）入队操作enQueue(Q,x)：将数据将数据x插入到队列插入到队列Q的队尾，队列的长度加的队尾，队列的长度加1；3）出队操作）出队操作outQueue(Q)：当队列为空时，返回队当队列为空时，返回队列头元素的值，同时删除队列头元素，队列的长度列头元素的值，同时删除队列头元

48、素，队列的长度减减1；4）取队头元素操作取队头元素操作GetQueue(Q)：当队列为空时，当队列为空时，返回队列头元素的值，但不删除队列头元素；返回队列头元素的值，但不删除队列头元素；5）判空操作：）判空操作：若队列为空，则返回的值为若队列为空，则返回的值为1，否则，否则为为0。3.2 队列第页主菜单3.2.3 队列的存储结构及其基本运算的实现1.链式存储结构3.2 队列frontrear空链队列a1fronta2链队列图示structstruct node node /链队列结点的类型定义链队列结点的类型定义 intint data; data; structstruct node *li

49、nk; node *link;typedeftypedef structstruct node node NODENODE NODE *front, *rear; NODE *front, *rear;第页主菜单1）进队列运算Voidaddqlink(intx)NODE*p;p=(NODE*)malloc(sizeof(NODE);p-data=x;p-link=NULL;rear-link=p;rear=p;3.2 队列第页主菜单2）出队列运算NODE*deleqlink()NODE*p;if(front=rear)return(NULL);p=front-link;front-link=p

50、-link;if(front-link=NULL)rear=front;return(p);3.2 队列第页主菜单3）队列的应用队列的应用1）解决计算机主机与外设不匹配的问题；）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；）解决由于多用户引起的资源竞争问题；3）离散事件的模拟）离散事件的模拟-模拟实际应用中的各种排模拟实际应用中的各种排队现象；队现象；4）用于处理程序中具有先进先出特征的过程；）用于处理程序中具有先进先出特征的过程；在操作系统课程中会讲到3.2 队列第页主菜单2.顺序存储结构将front和rear两个整型变量作为c语言结构体的两个成员，该结构体定义如

51、下：Structsq_queueDatatypedatamaxlen;Intfront,rear;3.2 队列1)1)初始化运算初始化运算initqueueinitqueue（structstruct sq_queuesq_queue sq sq） 得到一个长度为得到一个长度为maxsizemaxsize的空队列的空队列sqsq， 此时此时sq-front=0;sq-rear=0.sq-front=0;sq-rear=0.第页主菜单2)进队列运算enqueue（structsq_queuesq,datatypex)sq-rear=sq-rear+1,sq-rear.data=x3)出队列运算o

52、utqueue（structsq_queuesq）sq-front=sq-front-14)读队列头元素运算gethead(structsq_queuesq）返回的函数值为sq-rear.data,sq队列没有改变5）判断队列是否是空emptyqueue(structsq_queuesq）3.2 队列第页主菜单3 . 循环队列frontrearJ6J4J53 124 05rear54 03 12frontJ6J7J8J9J4J5frontrear54 03 12(b)队空(c)队满队空、队满都有front=rear如何判断循环队列队空、队满？J7rear3.2 队列第页主菜单有两种方法：1）另

53、设一个标志位以区分队空、队满。）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件）少用一个存储单元，队满条件:front=rear+1;front54 03 12J6J7J8J4J5（d）rear3.2 队列第页主菜单1）初始化操作功能：建一个空队列Q；算法：IntqueueMAX;Intfront,rear;intInitQueue_Sq()/构造一个空队列Qfront=0;rear=0;Return(1)循环队列的基本操作算法循环队列的基本操作算法frontrear54 03 12建一个空队列Q3.2 队列第页主菜单2）入队操作）入队操作功能：将功能：将元素元素x插入队尾插入

54、队尾frontrear54 03 12J1J3J2xfrontrear54 03 12J1J3J2元素 x 入队前元素 x 入队后3.2 队列求余运算int insert_queue(int x) /*入队列入队列*/if(rear+1)%MAX=front)return(0); rear=(rear+1)%MAX; queuerear=x;return(1);第页主菜单3）出队操作功能：删除队头元素；frontrear54 03 12J1J3J2出队操作前frontrear54 03 12J1J3J2出队操作后3.2 队列int del_queue() /*出队列出队列*/ if(rear=

55、front) return(0); front=(front+1)%MAX; return(queuefront);第页主菜单小结和作业小结和作业作业作业:课后习题课后习题1、2、3实训题：实训题：参见参见http:/ 1 数组数组4.1.1 数组的概念和运算数组的概念和运算4.1.2 数组的顺序存储和访问数组的顺序存储和访问4.1.3 矩阵的压缩存储矩阵的压缩存储4.2 串串4.2.1 串的基本概念串的基本概念4.2.2 串的基本运算串的基本运算4.2.3 串的存储结构串的存储结构第106页主菜单4.1.1数组的概念运算数组是由一组个数固定，类型相同的数据元素组成阵列。以二维数组为例：二维数

56、组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 Amn=a a0000 a a01 01 a a0 n-10 n-1a a1010 a a11 11 a a1 n-11 n-1a am-1 0m-1 0 a am-1 1 m-1 1 a am-1 n-1m-1 n-1在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j4.1 数组第107页主菜单二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表A=（0 ,1 ,2

57、 ,3 , 4 ,p )其中每一个数据元素 j 是一个列向量的线性表j=（a0j , a1j ,a2j , a3j , ,am-1j )或 i 是一个行向量的线性表 i=（ai0 ,ai1 ,ai2 , ai3 , ,ain-1 )4.1 数组第108页主菜单数组的基本操作1访问：给定一组下标，存取相应的数据元素。2修改：给定一组下标，修改相应数据元素中的某个数据项的值。操作方法根据其存储结构决定4.1 数组第109页主菜单4.1.2数组的顺序存储和访问一维数组在内存中的存放很简单，只要顺序存放在连续的内存单元即可。二维数组，如何用顺序结构表示？内存地址是一维的，而数组是二维的，要将二维数组挤

58、入一维的地址中，有两个策略：以行为主序（C语言使用）以列为主序4.1 数组a a0000 a a01 01 a a0 n-10 n-1a a1010 a a11 11 a a1 n-11 n-1a am-1 0m-1 0 a am-1 1 m-1 1 a am-1 n-1m-1 n-1第110页主菜单设A是一个具有m行n列的元素的二维数组:以行为主序的方式：a00 a01 a0n-1 a10 a11 a1n-1 am-11 am-1n-10 1 n-1 n n+1 2n-1 mn-1a00a10 am-10 a01 a11 am-11 a0n-1 a1n-1 am-1n-10 1 m-1 m

59、m+1 2m-1 nm-1以列为主序的方式：Amn=a a0000 a a01 01 a a0 n-10 n-1a a1010 a a11 11 a a1 n-11 n-1a am-1 0m-1 0 a am-1 1 m-1 1 a am-1 n-1m-1 n-14.1 数组第111页主菜单4.1.3矩阵的压缩存储矩阵的压缩存储 一一 特殊矩阵的压缩存储特殊矩阵的压缩存储二二 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 1 1 三元组表的存储结构三元组表的存储结构 2 2 十字链表的存储结构十字链表的存储结构4.1 数组第112页主菜单数组元素存储地址的计算数组元素存储地址的计算假设二维数组假设二维

60、数组A每个元素占用每个元素占用s个存储单元，个存储单元，Loc(a aijij)为元为元素素a aijij的存储地址，的存储地址，Loc(a a0000)是是a a0000存储位置存储位置,也是二维数组也是二维数组A的的基址。基址。若以行序为主序的方式存储二维数组，则元素若以行序为主序的方式存储二维数组，则元素a aijij的存储的存储位置可由下式确定：位置可由下式确定：Loc(a aijij)=Loc(a a0000)+（n i+j) s若以列序为主序的方式存储二维数组，则元素若以列序为主序的方式存储二维数组，则元素a aijij的存储位的存储位置可由下式确定：置可由下式确定：Loc(a a

61、ijij)=Loc(a a0000)+（m j+i) s一般在程序设计过程中，一维数组和二维数组使用较普遍，一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多维数组使用相对较少，对于高维数组的顺序超过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，可以将二维的情形加以推广便能够得到。存储方法，可以将二维的情形加以推广便能够得到。4.1 数组第113页主菜单矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。一个m行n列的矩阵是一平面阵列，有mn个元素。可以对矩阵作加、减、乘等运算。只有少数程序设计语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。由于这种存储

62、方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。4.1 数组Amn=a a0000 a a01 01 a a0 n-10 n-1a a1010 a a11 11 a a1 n-11 n-1a am-1 0m-1 0 a am-1 1 m-1 1 a am-1 n-1m-1 n-1第114页主菜单应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。例如，设一个10001000的矩阵中有800个非零元素，若用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩

63、存储。本章将讨论两类矩阵的压缩存储：1特殊矩阵的压缩存储2稀疏矩阵的压缩存储4.1 数组Amn=a a0000 a a01 01 a a0 n-10 n-1a a1010 a a11 11 a a1 n-11 n-1a am-1 0m-1 0 a am-1 1 m-1 1 a am-1 n-1m-1 n-1第115页主菜单一特殊矩阵值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例：对称矩阵、上（下）三角矩阵都是特殊矩阵a00 a10 a20 an-10 a10 a11 a21an-10 an-11 an-1 n-1a00 a01 a0n-10 a11 a1n-10 0 0 an-1 n-

64、14.1 数组第116页主菜单特殊矩阵压缩存储特殊矩阵压缩存储(以对称矩阵为例以对称矩阵为例)对称矩阵是满足下面条件的n阶矩阵: aij= aji 0 i,j n-1 a00 a01 a0n-1a10 a11 a1n-1an-10 an-11 an-1n-1对称矩阵元素可以只存储下三角部分，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似）a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1k= 0 1 2 3 4 5 n(n+1)/2-1 4.1 数组第117页主菜

65、单k =i(i+1)/2 +j 当 i jj(j+1)/2 +i 当 i j以一维数组sa作为n阶对称矩阵A的存储结构，A中任意一元素aij与它的存储位置sak之间存在着如下对应关系：a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1k= 0 1 2 3 4 5 n(n+1)/2-1 例如，a a53 53 在sa中的存储位置是：k=5*(5+1)/2+3=18sa18=a a53534.1 数组第118页主菜单压缩存储的对称矩阵的取值算法压缩存储的对称矩阵的取值算法intget_M(inti,intj)if(i=j)return(sai*(i+1)/2+j

66、)elsereturn(saj*(j+1)/2+i);压缩存储的对称矩阵的压缩存储的对称矩阵的赋值算法赋值算法voidassign_M(inti,intj,intvalue)if(i=j)sai*(i+1)/2+j=value;elsesaj*(j+1)/2+i=value;4.1 数组第119页主菜单带状矩阵带状矩阵所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个a a00 00 a a01 01 a a 02 02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a10 10 a a11 11 a a12

67、 12 a a13 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0a a20 20 a a21 21 a a22 22 a a23 23 a a24 24 0 0 00 0 0 0 0 0 0 0 0 0 00 0 a a31 31 a a32 32 a a33 33 a a34 34 a a35 35 0 00 0 0 0 0 0 0 0 0 00 0 0 0 a a42 42 a a43 43 a a44 44 a a45 45 a a46 46 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 a a53 53 a a54 54 a a55 55 a a

68、56 56 a a57 57 0 00 0 0 0 0 0 0 0 0 0 0 00 0 a a64 64 a a65 65 a a66 66 a a67 67 a a68 68 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 a a75 75 a a76 76 a a77 77 a a78 78 a a79 79 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 a a86 86 a a87 87 a a88 88 a a89 89 a a810810 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 a a9797 a a98 98 a a99 99

69、a a910 910 a a9119110 00 0 0 0 0 0 0 0 0 0 0 0 0 0 a a108 108 a a109 109 a a1010 1010 a a1011 1011 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a119 119 a a1110 1110 a a11111111d4.1 数组第120页主菜单a 00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 00 0 a32 a33 a340 0 0 a43 a44K=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 为计算方便

70、，认为每一行都有2d+1个非0元素，若少则用0补足，所以，存放矩阵的数组sa有n(2d+1)个元素数组元素sak与矩阵元素aij之间有关系k=i*(2d+1)+d+(j-i)a00前为何放一个0？你会放d=2,n=6的带状矩阵吗？4.1 数组0 a a0000 a a0101 a a1010 a a11 11 a a12 12 a a21 21 a a22 22 a a23 23 a a32 32 a a33 33 a a34 34 a a43 43 a a44 44 0 0第121页主菜单压缩存储的带状矩阵的取值算法压缩存储的带状矩阵的取值算法intget_Md(inti,intj)if(a

71、bs(i-j)=d）return(sai*(2*d+1)+d+(j-i)；elsereturn(0);压缩存储的带状矩阵的赋值算法压缩存储的带状矩阵的赋值算法voidassign_Md(inti,intj,intvalue)if(abs(i-j)=d）sai*(i+1)/2+j=value;4.1 数组第122页主菜单二稀疏矩阵1什么是稀疏矩阵有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。例A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0

72、0 -7 0 0 0A有42（67）个元素有8个非零元素如何进行稀疏矩阵的压缩存储？4.1 数组第123页主菜单2稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）1）三元组表（i,j,aij)A=(0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7)加上行、列数6，7A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0表示非零元的三元组4.1 数组第124页主菜单2）三元组

73、顺序表假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式我们称之为三元组顺序表。稀疏矩阵的三元组顺序表的类型定义structnodeintrow,col;/非零元的行下标和列下标intvalue;/非零元值;typedefstructnodeNODE;NODEmaMAX；ma0用于存储矩阵行数、列数、非零元个数用于存储非零元三元组的结构4.1 数组第125页主菜单A的三元组顺序表图示 A= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0row col

74、 value0123456782 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8例如ma1.row=0,ma1.col=1,ma1.value=124.1 数组第126页主菜单3)转置运算算法转置运算是一种最常用的矩阵运算。对于一个m行n列的矩阵A，它的转置矩阵B是一个n行m列的矩阵。例如，下图中的矩阵A和B互为转置矩阵。 A= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0

75、0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 B= 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 4.1 数组第127页主菜单 A第第0 0 列列第一列第一列 第二列第二列第三列第三列 第四列第四列第五列第五列 第六列第六列 . B B第第0 0 行行第一行第一行 第二行第二行第三行第三行 第四行第四行第五行第五行 第六行第六行 .转置运算算法4.1 数组第128页主菜单矩阵 B矩阵 Arow col value0123456782 0 -

76、32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue 0123456781 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8分析：分析：（1 1）将矩阵的行列）将矩阵的行列数的值交换数的值交换（2 2）将每一个三元将每一个三元组的组的i i 和和 j j相互调相互调换换（

77、3 3）重排三元组之）重排三元组之间的次序间的次序4.1 数组第129页主菜单转置运算算法按照A的列序来进行转换的基本思想 对 ma 从头至尾扫描： 第一次扫描时，将 ma 中列号为0的所有元组交换行列值后，依次赋值到 mb 中 第二次扫描时，将 ma 中列号为1的所有元组交换行列值后，依次赋值到 mb 中 依此类推，直至将 ma 的所有三元组赋值到 mb 中4.1 数组第130页主菜单i j v0 1 120 2 92 0 -32 5 143 2 244 1 185 0 155 3 -7i j v2 0 -31 4 180 2 -35 0 150 5 150 1 121 0 124 1 18

78、0 2 92 0 93 2 242 3 245 3 -73 5 -72 5 145 2 14A矩阵B矩阵对A六次扫描完成转置运算第一次扫描查第一次扫描查找第找第0 0列元素列元素第一次扫第一次扫描结束描结束第二次扫第二次扫描结束描结束第二次扫描查第二次扫描查找第找第1 1列元素列元素第三次扫描查第三次扫描查找第找第2 2列元素列元素第四次扫描查第四次扫描查找第找第3 3列元素列元素第五次扫描查第五次扫描查找第找第4 4列元素列元素第六次扫描查第六次扫描查找第找第5 5列元素列元素转置运算算法图示0123456786 7 87 6 84.1 数组第131页主菜单转置算法:采用三元组表存储表示，求

79、稀疏矩阵A的转置矩阵Binttranspose(NODEma,NODEmb)inti,j,k;if(ma0.value=0)return(0);mb0.row=ma0.col;mb0.col=ma0.row;mb0.value=ma0.value;k=1;/k为当前三元组在mb存储位置(下标)for(i=0;ima0.col;i+)/找ma中第i列所有非0元素for(j=1;j=ma0.value;j+)/j为扫描ma的“指示器”/j“指向”三元组称为当前三元组if(maj.col=i)mbk.row=maj.col;mbk.col=maj.row;mbk.value=maj.value;k+

80、;return(1);4.1 数组第132页主菜单时间复杂度分析算法的基本操作为将ma中的三元组赋值到 mb ，是在两个循环中完成的，故算法的时间复杂度为O(n t) ), 其中n为A矩阵的列数,t为非0元素个数。当非零元的个数t和矩阵元素个数mn同数量级时，即tm n，转置运算算法的时间复杂度为O（n n m m n）。由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于trow,&head-row,&head-col,&headcol,&head-valval););rowcolvaldownright445head4.1 数组第137

81、页主菜单for(pre=head,i=0;irow;i+)for(pre=head,i=0;irow;i+) p=(NODE *) p=(NODE *)malloc(sizeof(NODEmalloc(sizeof(NODE);); p- p-valval=p-row=p-=p-row=p-colcol=0;=0; p-right=p;pre-down=p;pre=p; p-right=p;pre-down=p;pre=p; p-down=head; p-down=head;4 4 54 4 5head0 0 00 0 00 0 00 0 0for(pre=head,i=0;icol;i+)p

82、=(NODE*)malloc(sizeof(NODE);p-val=p-row=p-col=0;p-down=p;pre-right=p;pre=p;p-right=head;4.1 数组第138页主菜单4 4 54 4 5head0 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 01 1 -1 1 -1 1newrow_pcol_p4.1 数组第139页主菜单count=0;while(countval)count+;new=(NODE*)malloc(sizeof(NODE);scanf(%d,%d,%dn,&new-row,&new-col,&new-val)

83、;for(row_p=head,i=0;irow;i+)row_p=row_p-down;p=row_p;while(p-right!=row_p&p-right-colcol)p=p-right;new-right=p-right;p-right=new;4.1 数组第140页主菜单for(col_p=head,i=0;icol;i+)col_p=col_p-right;p=col_p;while(p-down!=col_p&p-down-rowrow)p=p-down;new-down=p-down;p-down=new;return(head);4.1 数组第141页主菜单A A= =

84、3 2 0 53 2 0 5 0 -1 0 0 0 -1 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 04 4 54 4 50 0 00 0 00 0 00 0 00 3 50 3 50 1 20 1 20 0 30 0 30 0 00 0 00 0 00 0 02 0 22 0 21 1 -11 1 -1head4.1 数组第142页主菜单 小 结1矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间；2特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系；3稀疏矩阵的压缩存储除了要保存非零元素的值外，还要保存

85、非零元素在矩阵中的位置；4.1 数组第143页主菜单学习要点学习要点1了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法；2掌握在串的堆分配存储结构下，串的基本操作算法；串也叫字符串，它是由零个或多个字符组成的的字符序列。基本内容基本内容1串的有关概念串的基本操作2串的顺序存储结构，堆分配存储结构,链式存储结构；3串的基本操作算法；4.2 串第144页主菜单4.1 4.1 串的基本概念串的基本概念4.2 4.2 串的基本运算串的基本运算4.3串的存储结构串的存储结构1串的顺序存储串的顺序存储2串的块链存储串的块链存储4.2 串第145页主菜单4.2.1串的基本概念串的基本概念1什么是

86、串什么是串串是一种特殊的线性表，它是由零个或多个字符组成串是一种特殊的线性表，它是由零个或多个字符组成的有限序列，的有限序列，一般记作一般记作s=“a1,a2,a3,.an”其中其中s-串名，串名，a1,a2,a3,.an-串值串值串的应用非常广泛，许多高级语言中都把串的作为基串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。行字符等也可作为字符串处理。4.2 串第146页主菜单下

87、面是一些串的例子：下面是一些串的例子：（1）a=“Thisisastring”（2）b=“string”（3）c=“（4）d=“”（5）e=“你好你好”说明：说明：1)串中包含的字符个数，称为串的长度。串中包含的字符个数，称为串的长度。长度为长度为0的串称为空的串称为空串，它不包括任何字符串，它不包括任何字符;2)串中所包含的字符可以是字母、数字或其他字符，这依赖于串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。具体计算机所允许的字符集。4.2 串第147页主菜单2串的有关术语串的有关术语1）子串）子串串中任意连续的字符组成的子序列称为该串的子串串中任意连续的字符

88、组成的子序列称为该串的子串;例：例：c=“DATASTRUCTURE”，f=“DATA”f是是c的子串的子串2）子串的位置）子串的位置子串子串t在主串在主串S中的位置是指主串中的位置是指主串s中第一个与中第一个与T相同的子相同的子串的首字母在主串中的位置串的首字母在主串中的位置;例：例：s=“ababcabcac”,t=“abc”子串子串T在主串在主串S中的位置为中的位置为33）串相等）串相等两个串相等，当且仅当两个串长度相同，并且各个对应两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同；位置的字符都相同；4.2 串第148页主菜单4.2.2串的基本操作串的基本操作串的逻辑结构

89、与线性表一样，都是线性结构。但由于串的应用与串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。线性表不同，串的基本操作与线性表有很大差别。1）串赋值操作）串赋值操作assign(s,t)功能：将串功能：将串t的值赋给串变量的值赋给串变量s；2）串相等判断串相等判断equal(s,t)函数函数3)串的联接操作串的联接操作concat(s,t)把串把串t接在串接在串s后面后面4)求串长操作求串长操作lenght(s)5)求子串操作求子串操作sub(s,start,len,t)若若0=startlength(s)0=len=length(s)-sta

90、rt则则t中值为从串中值为从串s的第的第start个字符个字符,起长度为起长度为len的字符序列的字符序列,并且函数返并且函数返回值为回值为1,否则为否则为0；6）求子串位置操作）求子串位置操作index(s,t)功能：如果功能：如果s中存在与中存在与t相同的子串相同的子串,则返回则返回s中第中第1个这样的子串的位个这样的子串的位置，若不存在返回置，若不存在返回04.2 串第149页主菜单7）替换操作替换操作replace(s,t,v)功能：由串功能：由串v替换串替换串s中出现的所有和中出现的所有和t相同的不重叠子相同的不重叠子串；串；8）复制串操作复制串操作strcopy(s,t)功能：由串

91、变量功能：由串变量s复制得到串变量复制得到串变量t；9）判空操作判空操作empty(s)功能：若为空串，则返回功能：若为空串，则返回1，否则返回否则返回010）串置空操作）串置空操作ClearString(s)功能：将功能：将s清为空串清为空串11)串插入操作串插入操作StrInsert(s,start,t)功能：将串功能：将串t插入到串插入到串s的第的第start字符之前字符之前1212）串删除）串删除操作操作StrDelete(s,start,len)功能：从串功能：从串s中删除第中删除第start个字符起长度个字符起长度len为的子串为的子串4.2 串第150页主菜单4.2.3 4.2.

92、3 串的存储结构串的存储结构1 1 顺序存储结构顺序存储结构顺序存储结构类似于顺序存储结构类似于C语言的字符数组，以一组地址连续的存储语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：单元存放串值字符序列，其类型说明如下：#defineMAX255charchMAX 0 1 2 3 4 5 6 7 8 9 10 11 14 MAX-1ch d a t a s t r u ct u r e 0 在数组在数组chch中以字符中以字符00表示字符串的结束表示字符串的结束. . 特点是访问容易特点是访问容易, , 但删除或插入麻烦但删除或插入麻烦4.2 串第151页主菜单2 2

93、 链式链式存储结构存储结构链式存储结构类似线性链表，由于串结构的特殊性链式存储结构类似线性链表，由于串结构的特殊性,要考虑要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但存储效率低。删除、求长度非常方便，但存储效率低。多个字符的，改善了效率，在处理不定长的大字符串时很有多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。结点。d a t a s t r u c t u r e headdate

94、head4.2 串第152页主菜单charstoreMAX;intfree;*/整型域：存放串长整型域：存放串长*/3、堆分配存储、堆分配存储堆分配存储类似于线性表的顺序存储结构，以一组地址连续的堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间是在程序执行过程中动存储单元存放串值字符序列，其存储空间是在程序执行过程中动态分配的。态分配的。一个串值的确定是通过串在堆中的起始位置和串的长度实现的。一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名与串值之间要建立一个对照表。为此，串名与串值之间要建立一个对照表。串名 起址 串长a 0 4b

95、4 9c 13 4.d a t a s t r u c tu r e b o o kfree=17 0 1 2 3 4 5 6 7 8 9 4.2 串第153页主菜单（1）求长度求长度length(s)intlength(chars)inti;for(i=0,si!=0;i+);return(i);4.2 串 (2) 求子串算法求子串算法intsub(chars,intstart,intlen,chart)intn,i;n=length(s);if(start=n)return(0);if(lenn)return(0);/参数不参数不合法合法for(i=0;i=MAX)return(0);fo

96、r(i=0;in;i+)sm+i=ti;ti=0;return(1);4.2 串(4)判断串相等算法判断串相等算法intequal(chars,chart)intm,n,i;m=length(s);n=length(t);if(m!=n)return(0);for(i=0;im;i+)if(si!=ti)return(0);return(1);第155页主菜单第156页主菜单主要内容5.1 树5.1.1 树的有关概念5.1.2 树的表示5.1.3 树的基本运算5.2 二叉树5.2.1 二叉树的概念5.2.2 二叉树的性质5.2.3 二叉树的存储结构5.2.4 二叉树的遍历5.2.5 哈夫曼树和

97、哈夫曼编码5.3 树和森林5.3.1 树的存储结构5.3.2 树、森林与二叉树的转换5.3.3 树和森林的遍历第157页主菜单1树的概念树的概念 树形结构是一种重要的非线性结构，讨论的是层次和分支关树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是系。树是n个结点的有限集合，在任一棵非空树中：个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在

98、树的定义中又用到了树的概念J JI IA AC CB BD DH HG GF FE EK KL LM M5.1 树第158页主菜单例：右边的图是一棵树例：右边的图是一棵树T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J，K K，L L，MMA A是根，其余结点可以划分为是根，其余结点可以划分为3 3个个互不相交的集合：互不相交的集合：T1=B, E, FT1=B, E, F，K K，L , T2=C, G , T3=D, H, I, JL , T2=C, G , T3=D, H, I, J，MM这些集合中的每一集合都本身又

99、是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。 例如：对于例如：对于 T11T11，B B是根，其余结点可以划分为是根，其余结点可以划分为2 2个个互不相交的集合：互不相交的集合：T11=E，K，L，T12=F，T11,T12是是B的子树。的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M5.1 树第159页主菜单从逻辑结构看：从逻辑结构看：1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或

100、多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构）树是一种分枝结构 （除了一个称为根的结点外）每个元素（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。都有且仅有一个直接前趋，有且仅有零个或多个直接后继。J JI IA AC CB BD DH HG GF FE EK KL LM M5.1 树第160页主菜单树的基本术语树的结点：树的结点：包含一个数据元素及若干指包含一个数据元素及若干指向子树的分支；向子树的分支；孩子结点孩子结点：结点的子树的根称为该结点：结点的子树的根称

101、为该结点的孩子；的孩子；双亲结点：双亲结点：B结点是结点是A结点的孩子，则结点的孩子，则A结点是结点是B结点的双亲；结点的双亲；兄弟结点：兄弟结点：同一双亲的孩子结点；同一双亲的孩子结点；堂兄结点：堂兄结点：同一层上结点；同一层上结点；祖先结点祖先结点:从根到该结点的所经分支上的所有结点从根到该结点的所经分支上的所有结点子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙以某结点为根的子树中任一结点都称为该结点的子孙5.1 树J JI IA AC CB BD DH HG GF FE EK KL LM M第161页主菜单树的树的基本术语基本术语结点层结点层：根结点的层定义为：根结点

102、的层定义为1；根的孩子为第二层结；根的孩子为第二层结点，依此类推；点，依此类推；树的深度树的深度：树中最大的结点层：树中最大的结点层结点的度结点的度：结点子树的个数：结点子树的个数树的度树的度：树中最大的结点度。树中最大的结点度。叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为0的结点；的结点；分枝结点分枝结点：度不为：度不为0的结点；的结点；有序树有序树：子树有序的树，如：家族树；：子树有序的树，如：家族树；无序树无序树：不考虑子树的顺序；：不考虑子树的顺序；森林森林；互不相交的树集合；森林和树之间的联系是：；互不相交的树集合；森林和树之间的联系是：一棵树去掉根一棵树去掉根，其子

103、树构成一个森林；一个森林增其子树构成一个森林；一个森林增加一个根结点成为树。加一个根结点成为树。J JI IA AC CB BD DH HG GF FE EK KL LM M5.1 树第162页主菜单2树的表示1）树形表示2）文式图表示3）嵌套括号表示4）凹入表示法（类似书的目录）AEDHJIKLMDGCABEKLFCGDHMJI（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）5.1 树第163页主菜单3树的基本运算树的基本运算树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：作：1 1）initiat

104、e(T);T树的初始化，包括建树。树的初始化，包括建树。2）root(T);求求T树的根。树的根。3）parent(T,x):求求T树中树中x结点的双亲结点。结点的双亲结点。4）Child(T,x,i)：求求T树中树中x结点的第结点的第i个孩子结点。个孩子结点。5）right_sibling(T,x):求求T树中树中x结点的右兄弟结点的右兄弟6）insert_Child(y,i,x):将根为将根为x的子树置为的子树置为y结点的第结点的第i个孩子个孩子7）del_child(x,i);删除删除x结点的第结点的第i个孩子个孩子8）traverse(T);遍历遍历T树。按某个次序依次访问树中每一个结

105、点，并使树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。每个结点都被访问且只被访问一次。9）clear(T);置空置空T树树5.1 树第164页主菜单树是一种分枝结构的对象，在树的概念树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨因此树的形态多种多样，本章我们主要讨论一种最简单的树论一种最简单的树二叉树。二叉树。5.2 二叉树第165页主菜单一一 二叉树的概念二叉树的概念1 1 二叉树的定义二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树

106、本身也是二叉树。说明说明1 1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2;2 2）左、右子树不能颠倒）左、右子树不能颠倒有序树有序树; ;3 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; ; A A F F G G E E D D C C B B5.2.1 二叉树的概念第166页主菜单 A A F F G G E E D D C C B B (a)、(b)是不同的二叉树， (a)的左子树有四个结点，(b)的左子树有两个结点，(a) A A G

107、G E E D D B B C C F F(b)5.2.1 二叉树的概念第167页主菜单2二叉树的基本形态二叉树的基本形态(a)空树(b)仅有根(c) 右子树空(e) 左子树空(d) 左、右子树均在5.2.1 二叉树的概念第168页主菜单5.2.1 二叉树的概念3 二叉树的抽象数据类型的定义：二叉树的抽象数据类型的定义：ADT binarutree数据对象数据对象D:是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R： 若若D= ,则则R= ,称称bitree为空树。为空树。 若若D= , R= H,H是如下关系：是如下关系：在在D中存在唯一的称为根的中存在唯一

108、的称为根的root，它在关系，它在关系H下无前驱；下无前驱；若若Droot ,则存在则存在DrootD1,Dr，且，且D1Dr = 若若D1 ，则，则D1中存在唯一的元素中存在唯一的元素x1， H，且存在，且存在D1上的一个关系，上的一个关系，H1 H；第169页主菜单两种特殊的二叉树两种特殊的二叉树1)1)满二叉树满二叉树：如果深度为：如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉个结点则称为满二叉树；树； A A G G F F E E D D C C B B A A C C B BK=3的满二叉树K=2的满二叉树5.2.1 二叉树的概念第170页主菜单2)

109、完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树； A A E E D D C C B B G G A A E E D D C C B B(a)(a)(c)(c)(b)(b)(a)(a)、(b)(b)完全二叉树(c) (c) 不是完全二叉树 A A G G F F E E D D C C B B5.2.1 二叉树的概念第171页主菜单二 二叉树性质性质1 在二叉树的第i 层上最多有2i-1个结点性质2 深度为k的二叉树最多有 2k-1 个结点性质3 设二叉树叶子结点数为n0，度为2的结点n2，则n0 = n2 +1 A A F F

110、 G G E E D D C C B B5.2.2 二叉树的性质第172页主菜单下面是两个关于完全二叉树的性质下面是两个关于完全二叉树的性质性质性质4 4 具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：trunc(logtrunc(log2 2 n)+1. n)+1. trunc(xtrunc(x) )为取整函数。为取整函数。对完全二叉树的结点编号：对完全二叉树的结点编号：从上到下，每一层从左从上到下，每一层从左到右到右 A A F F E E D D C C B B1 12 23 34 45 56 6性质性质5 5：在完全二叉树中编号为：在完全二叉树中编号为i i的结

111、点的结点1 1）若有左孩子，则左孩编号为）若有左孩子，则左孩编号为2i2i2 2）若有右孩子，则右孩子结点编号为若有右孩子，则右孩子结点编号为2i+12i+13 3）若有双亲，则双亲结点编号为若有双亲，则双亲结点编号为trunc(i/2)trunc(i/2)5.2.2 二叉树的性质第173页主菜单1 1 二叉树的顺序结构二叉树的顺序结构满二叉树或完全二叉树的顺序结构满二叉树或完全二叉树的顺序结构用一组用一组连续的连续的内存单元，按内存单元，按编号编号顺序依顺序依次存储完全二叉树的元素次存储完全二叉树的元素. .例如，用一维例如，用一维数组数组btbt 存放一棵完全二叉树，将标号存放一棵完全二叉

112、树，将标号为为 i i 的结点的数据元素存放在分量的结点的数据元素存放在分量 bti-1bti-1中。存储位置隐中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，的。例如，bt5bt5（i=6)i=6)的双亲结点标号是的双亲结点标号是k=trunc(i/2)=3,k=trunc(i/2)=3,双亲结点所对应的数组分量双亲结点所对应的数组分量btk-1=bt2btk-1=bt2顺序结构图示 0 1 2 3 4 5 6 7 m-10 1 2 3 4 5 6 7 m-1A B C D E FA B C D E F A A

113、F F E E D D C C B B1 12 23 34 45 56 65.2.3 二叉树的存储结构第174页主菜单 A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 81010 A A F F G G E E D D C C B B9 90 1 2 3 4 5 6 7 8 9 10 m-10 1 2 3 4 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 GA B C D E 0 F 0 0 G5.2.3 二叉树的存储结构第175页主菜单2 二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 A A F

114、F E E D D C C B BStructStruct node node intint data; data; structstruct node * node *lchlch,*,*rchrch; ;二叉链表图示 D D A A B B C C EE FF 5.2.3 二叉树的存储结构第176页主菜单 A A F F E E D D C C B B 3 三叉链表 三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域StructStruct node node intint data; data; structstruct node node * *lchlch,*,*r

115、chrch,*parent;,*parent;ABDFEC5.2.3 二叉树的存储结构第177页主菜单5.2.4 遍历（Traversal）本节内容：1.遍历的基本概念2.各种遍历方法的思想3.各种遍历方法的递归算法和非递归算法4.以先序输入方式建立二叉树的算法。重点、难点1.各种遍历方法的思想2.各种遍历方法的非递归算法第178页主菜单一. 遍历的基本概念遍历是各种数据结构最基本的操作，许多其他的遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。操作可以在遍历基础上实现。二叉树的二叉树的遍历：沿某条路径周游二叉树，对树中遍历：沿某条路径周游二叉树，对树中的每个结点访问一次且

116、仅访问一次。的每个结点访问一次且仅访问一次。“访问访问”的含义很广，可以是对结点的各种处理，的含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。如修改结点数据、输出结点数据。第179页主菜单两种基本策略：广度遍历深度遍历如何访问二叉树的每个结点，而且每个结点仅被访问一次？ A A F F E E D D C C B B第180页主菜单广度遍历策略层次遍历方法：从上到下、从左到右访问各结点适用于顺序存储结构 A A F F E E D D C C B B存储结构012345678ABCDEF遍历结果：A B C D E F第181页主菜单深度遍历策略二叉树由根、左子树、右子树三部分

117、组成二叉树的遍历可以分解为： 访问根（D）遍历左子树（L）遍历右子树（R）有六种遍历方法：D L RD L R，L D RL D R，L R DL R D，D R LD R L，R D LR D L，R L DR L D约定先左后右,有三种遍历方法，分别称为先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B第182页主菜单二、各种遍历的思想1 . 先序遍历（DLR）2 . 中序遍历（LDR）3. 后序遍历（RDL）第183页主菜单 例：先序遍历右图所示的二叉树，所得先序遍历序列： A A, B, C, D, E, F, G, H, K, B, C, D, E,

118、 F, G, H, K1 . 先序遍历（DLR）先序遍历（DLR）思想若二叉树非空，则依次进行以下操作 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； A A F F H H E E D D C C B BFlash演示 G G K K第184页主菜单例：中序遍历右图所示的二叉树，所得中序遍历序列： B, D, C, A, E, H, G, K, F2. 中序遍历（LDR）中序遍历（LDR）思想若二叉树非空，则依次进行以下操作 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；Flash演示 A A F F H H E E D D C C B B G G K

119、 K第185页主菜单3. 后序遍历（LRD）例：后序遍历右图所示的二叉树，所得后序遍历序列： D, C, B, H, K, G, F, E,D, C, B, H, K, G, F, E, A A后序遍历（LRD）思想若二叉树非空，则依次进行以下操作 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点；Flash演示 A A F F H H E E D D C C B B G G K K第186页主菜单软件水平考试有关试题2004年试题2002年试题1999年试题第187页主菜单2002年 试题假设一棵二叉树的后序遍历序列为假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍

120、历序列为中序遍历序列为DBGEHJACIF，则其前序遍历序列则其前序遍历序列为为。A）ABCDEFGHIJB）ABDEGHJCFIC）ABDEGHJFICD）ABDEGJHCFIABDEGHJCFI第188页主菜单1999试题2二叉树的查找有深度优先和广度优先二类，深度优先包括_C_。当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和和EGBDHFAC时，其后序序列必是_D_,层次序列为_E_.C: (1)前序遍历 后序遍历 中序遍历 (2)前序遍历 后序遍历 层次遍历 (3)前序遍历 中序遍历 层次遍历 (4)中序遍历 后序遍历 层次遍历D:(1)BDEAGFHC(2)EBDGACFH

121、(3)HGFEDCBA(4)HFGDEABCHGEDBFCAE: (1) B D E A C G F H (2) E B D G A C F H (3) H G F E D C B A (4) H F G C D E A B第189页主菜单软件设计师 2004上半年设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是_(10)_。Ax是y的左兄弟 Bx是y的右兄弟Cx是y的祖先 Dx是y的后裔 第190页主菜单三、遍历的递归算法前序遍历（DLR）void preorder（btree *t）若二叉树t非空，则：访问根结点t

122、前序遍历t的左子树前序遍历t的右子树if (t) putchar(t-data); preorder(t-lchild);preorder(t-rchild); 第191页主菜单中序遍历、后序遍历的递归算法中序遍历void inorder（bitree *t） if ( t ) inorder(t-lchild); putchar(t-data); inorder(t-rchild); 后序遍历void postorder（bitree *t） if ( t ) postorder(t-lchild); postorder(t-rchild); putchar(t-data); 你能写出后序遍

123、历递归算法了吧第192页主菜单1哈夫曼树哈夫曼树的概念的概念路径：路径：从一个结点到另一个结点之间的若干个分支从一个结点到另一个结点之间的若干个分支路径长度：路径长度：路径上的分支数目称为路径长度；路径上的分支数目称为路径长度；结点的路径长度：结点的路径长度：从根到该结点的路径长度从根到该结点的路径长度树的路径长度：树的路径长度：树中所有叶子结点的路径长度之和；一般记为树中所有叶子结点的路径长度之和；一般记为PL。在结点数相同的条件下，完全二叉树是路径最短的二叉树。在结点数相同的条件下，完全二叉树是路径最短的二叉树。7 71 13 32 25 56 64 48 88 81 13 32 25 5

124、7 74 46 6非完全二叉树完全二叉树5.2.5 哈夫曼树和哈夫曼编码第193页主菜单结点的权：结点的权：根据应用的需要可以给树的结点赋权值；根据应用的需要可以给树的结点赋权值；结点的带权路径长度：结点的带权路径长度：从根到该结点的路径长度与该结点权的乘从根到该结点的路径长度与该结点权的乘积；积；树的带权路径长度树的带权路径长度=树中所有叶子结点的带权路径之和；通常记树中所有叶子结点的带权路径之和；通常记作作WPL= wi Li哈夫曼树：哈夫曼树：假设有假设有n个权值个权值(w1,w2,wn)，构造有构造有n个叶子结个叶子结点的严格二叉树，每个叶子结点有一个点的严格二叉树，每个叶子结点有一个

125、wi作为它的权值。则带作为它的权值。则带权路径长度最小的严格二叉树称为权路径长度最小的严格二叉树称为哈夫曼树。哈夫曼树。B BD DA AC CA AC C D DB B7 5 2 47 5 2 44 47 75 52 25.2.5 哈夫曼树和哈夫曼编码第194页主菜单B BD DA AC CC C A AD D7 5 2 47 5 2 44 47 75 52 2A AC C D DB B4 47 75 52 2C CA A B BD D4 47 75 52 2B BWPL=7*2+5*2+2*2+4*2=36WPL=7*2+5*2+2*2+4*2=36WPL=7*1+5*2+2*3+4*3=

126、35WPL=7*1+5*2+2*3+4*3=35WPL=7*3+5*3+2*1+4*2=46WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35WPL=7*1+5*2+2*3+4*3=35要使二叉树要使二叉树WPL小小,就须在构造就须在构造树时树时,将权值大的将权值大的结点靠近根结点靠近根.5.2.5 哈夫曼树和哈夫曼编码第195页主菜单2应用举例应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例例编制一个将百分制转换成五分制的程序。编制一个将百分制转换成五分制的程序。最直观的方法是利用最直观的

127、方法是利用if语句来的实现。可用二叉树描述判定过语句来的实现。可用二叉树描述判定过程。程。a a 80 80a a 90 90不及格良好中等及格优秀a a 60 60a a 70 705.2.5 哈夫曼树和哈夫曼编码第196页主菜单按图的判定过程按图的判定过程:转换一个分数所需的比较次数转换一个分数所需的比较次数=从根到对应结点的路径长度从根到对应结点的路径长度转换转换10000个分数所需的个分数所需的总比较次数总比较次数=10000 (0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）二叉树的带权路径长度a a 80 80a a 90 90不及格良好中等及格优秀a a 60 6

128、0a a 70 70分数 0-59 60-69 70-79 80-89 90-100比例数0.05 0.15 0.40 0.30 0.10设有设有10000个百分制分数要转换，设学生成绩在个百分制分数要转换，设学生成绩在5个等个等级以上的分布如下级以上的分布如下：构造以分数的分布比例为权值构造以分数的分布比例为权值的哈夫曼树的哈夫曼树5.2.5 哈夫曼树和哈夫曼编码第197页主菜单3哈夫曼树的构造哈夫曼树的构造构造哈夫曼树的步骤：构造哈夫曼树的步骤：1根据给定的根据给定的n个权值个权值，构造，构造n棵只有一个根结点的棵只有一个根结点的二叉树，二叉树，n个权值分别是这些二叉树根结点的权。个权值分

129、别是这些二叉树根结点的权。设设F是由这是由这n棵二叉树构成的集合棵二叉树构成的集合2在在F中选取两棵根结点树值最小的树作为左、右子中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；左、右子树根结点权值之和；3从从F中删除这两颗树，并将新树加入中删除这两颗树，并将新树加入F；4重复重复2、3，直到，直到F中只含一颗树为止；中只含一颗树为止；5.2.5 哈夫曼树和哈夫曼编码第198页主菜单40403030606015155 5101015153030例：构造以例：构造以W=（5，15，40，30，

130、10）为权的哈夫曼为权的哈夫曼树树。30305 51010151540404040303015155 51010151540403030303015155 510101515哈夫曼树中权值小的结点离根远权值大的结点离根近40401001003030606015155 51010151530305.2.5 哈夫曼树和哈夫曼编码第199页主菜单哈夫曼编码哈夫曼编码在进行数据通讯时，涉及数据编码问题。所谓数据编在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。码就是数据与二进制字符串的转换。例如：邮局发电报：例如：邮局发电报：例例要传输的原文为要传输的原文为ABACCDA

131、等长编码等长编码A：00B：01C：10D：11发送方：发送方：将将ABACCDA转换成转换成00010010101100接收方：接收方：将将00010010101100还原为还原为ABACCDA不等长编码不等长编码A：0B：00C：1D：01发送方：发送方：将将ABACCDA转换成转换成000011010接收方：接收方：000011010转换成转换成原文电文（二进制字符串）原文发送方发送方接收方接收方AAAACCDAAAAACCDABBCCDABBCCDAA的编码是B的前缀5.2.5 哈夫曼树和哈夫曼编码第200页主菜单设设A：0B：110C：10D：111发送方：发送方：将将ABACCDA

132、转换成转换成0110010101110总长度是总长度是13所得的译码是唯一的所得的译码是唯一的前缀编码：任何字符编码不是其它字符编码的前缀任何字符编码不是其它字符编码的前缀5.2.5 哈夫曼树和哈夫曼编码第201页主菜单可利用二叉树设计前缀编码：例例某通讯系统只使用某通讯系统只使用8种字符种字符a、b、c、d、e、f、g、h，其使用其使用频率分别为频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用二叉，利用二叉树设计一种不等长编码：树设计一种不等长编码：1）构造以）构造以a、b、c、d、e、f、g、h为为叶子结点的二叉树；叶子结点的二叉树；2）将该二

133、叉树所有左分枝标记）将该二叉树所有左分枝标记1，所有右分枝标记，所有右分枝标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；码；5.2.5 哈夫曼树和哈夫曼编码第202页主菜单a: 0110a: 0110b: 10b: 10c: 1110c: 1110d: 1111d: 1111e: 110e: 110f: 00f: 00g: 0111g: 0111h: 010h: 010292919195858424210010015158 87 73 35 58 81111232314142929构造以字符使用频率构造以字符使用频率作为权

134、值的哈夫曼树作为权值的哈夫曼树如何得到使二进如何得到使二进制串总长最短编制串总长最短编码码5.2.5 哈夫曼树和哈夫曼编码第203页主菜单小小结结1 1 二叉树：二叉树： 或为空树，或由根及两颗不相交的左子树、右子或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；树构成，并且左、右子树本身也是二叉树；2 2 二叉树即可以用顺序结构存储，也可用链式结构存储；二叉树即可以用顺序结构存储，也可用链式结构存储；3 3遍历：按某种搜索路径访问二叉树的每个结点，每个结点遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。仅被访问一次。 二叉树的遍历可以分解为：访问

135、根，遍历二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历遍历、中序遍历、后序遍历. .4 4哈夫曼树：哈夫曼树又称为最优二叉树，是一种带权路径哈夫曼树：哈夫曼树又称为最优二叉树，是一种带权路径长度最短的树。本课程主要介绍了哈夫曼树的概念和哈夫长度最短的树。本课程主要介绍了哈夫曼树的概念和哈夫曼编码。曼编码。5.2 二叉树第204页主菜单5.3 树和森林5.3 树和森林 一. 树的存储结构 二. 树、森林与二叉树的转换 三. 树和森林的遍历第205页主菜单1 双亲表示法 采用一组连续空

136、间存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 5.3.1 树的存储结构DataParent数据双亲位置结点结构图示第206页主菜单5.3.1 树的存储结构 A -A -1 1 B 0 B 0 C 0 C 0 D 1 D 1 E 1 E 1 F 2 F 2 G 4 G 4 H 4 H 4 I 4 I 4 j 5 j 50 01 12 23 34 45 56 67 78 89 9data parent 双亲表示的存储结构类型定义：#defineMAX100typedefstructPTNodetelemtypedata;intparent;/双亲位置域PTNode

137、;typedefstructPTNodenodesMAX;Intn;/结点数PTree数组下标I IA AC CB BH HG GF FE ED Dj j树的双亲表示法的存储结构第207页主菜单5.3.1 树的存储结构 2 2、孩子表示法、孩子表示法 通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。孩子链表：对树的每个结点用线性链表存贮它的孩子结点。TypedefTypedef structstruct ctnodectnode /*/*孩子结点孩子结点* */ / intint child; child;StructStruct ctnodectnode *next; *nex

138、t;*childptrchildptr; ;TypedefTypedef structstruct /*/*孩子链表头指针孩子链表头指针* */ / telemtypetelemtype data; data;ChildptrChildptr firstchildfirstchild; ; ctboxctbox; ;TypedefTypedef structstruct /*/*结点数和根的位置结点数和根的位置* */ / ctboxctbox nodesmaxnodesmax;IntInt n,*r; n,*r; ctreectree; ;孩子链表存储结构类型定义如下：第208页主菜单 1

139、2 树的孩子链表图示结点的孩子结点链表注：找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构5.3.1 树的存储结构 A A B B C C D D E E F F G G H H I I j j 0 01 12 23 34 45 56 67 78 89 9I IA AC CB BH HG GF FE ED Dj j4 39 68 75 第209页主菜单带双亲孩子链表双亲孩子表示法：结合双亲表示法和孩子表示法dataparentlink -1 A -1 A 0 B 0 B 0 C 0 C 1 D 1 D 1 E 1 E 2 F 2 F 4 G 4 G 4 H 4 H 4 I 4 I

140、 5 j 5 j 0 01 12 23 34 45 56 67 78 89 9I IA AC CB BH HG GF FE ED Dj j 1 2 4 39 68 75 5.3.1 树的存储结构第210页主菜单5.3.1 树的存储结构TypedefTypedef structstruct ctnodectnode /*/*孩子结点孩子结点* */ / intint child; child;StructStruct ctnodectnode *next; *next;*childptrchildptr; ;TypedefTypedef structstruct /*/*孩子链表头指针孩子链表头

141、指针* */ / intint parent; parent; /*/*双亲位置双亲位置* */ /telemtypetelemtype data; data;ChildptrChildptr firstchildfirstchild; ; ctboxctbox; ;TypedefTypedef structstruct /*/*结点数和根的位置结点数和根的位置* */ / ctboxctbox nodesmaxnodesmax;IntInt n,*r; n,*r; ctreectree; ;带双亲孩子链表存储结构类型定义如下：第211页主菜单 3 3 孩子兄弟表示法孩子兄弟表示法 用二叉链表

142、作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点。structnodechardata;structnode*son,*brother;A AI IH HG GF FE EC CD DB B树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点 5.3.1 树的存储结构第212页主菜单5.3.2 树、森林和二叉树的转换I IA AC CB BD DH HG GF FE E此二叉链表既是树(a)(a)的孩子兄弟表示又是二叉树(b)(b)的二叉链表(a)(a)(b)(b)由此可将树与二叉树对应起来A AI IH HD DG GF FC CE EB BF FI I

143、A AB BD DH HG GC CE E第213页主菜单一、树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点 X X 的第一个孩子结点 X X 紧邻的右兄弟二叉树根结点 X X 的左孩子结点 X X 的右孩子5.3.2 树、森林和二叉树的转换第214页主菜单I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E树根结点 X X 的第一个孩子结点 X X 紧邻的右兄弟二叉树根结点 X X 的左孩子结点 X X 的右孩子5.3.2 树、森林和二叉树的转换第215页主菜单二

144、、森林：树的集合二、森林：树的集合将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；从树的二叉链表示的定义可知,任何一棵和树对应的二叉树,其右子树必为空。所以只要将森林中所有树的根结点视为兄弟，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标树的根，就可以将森林转换为二叉树。森林转换为二叉树转换规则：若 F = T1，T2，T3，Tn 是森林，则 B（F）=root,LB,RB（1）若 F 为空，即 n=0，则 B(F)为空树。（2）若 F 非空，则 B（F）的根是T1的根，其左子树为LB

145、，是从T1根结点的子树森林F1=T11，T12，T1m转换而成的二叉树；其右子树为RB，是从除T1外的森林F=T2，T3，Tn转换而成的二叉树；5.3.2 树、森林和二叉树的转换第216页主菜单 J J A A L L K KI IH HG GF FE EA AC CB BD D包含3棵树的森林 B B C C D D E E F F G G H H I I J J K K L L F F D D C C A A B B E E G G H H I I J J K K L L每棵树对应的二叉树森林对应的二叉树5.3.2 树、森林和二叉树的转换第217页主菜单二叉树还原为森林二叉树还原为森林转换

146、规则：若 B（F）=root,LB,RB是一棵二叉树，则转换为森林F = T1，T2，Tn 的规则为（1）若 B 为空，则 F 为空树。（2）若 B 非空，则 F 第一棵树T1的根是二叉树的根，T1中根结点的子森林F1是由B的左子树LB转换而成的森林，F中除T1外其余树组成的森林F=T2，T3，Tn是由B（F）的右子树RB转换转换而成的；5.3.2 树、森林和二叉树的转换第218页主菜单第219页主菜单主要内容6.1 图的定义和术语图的定义和术语 6.2 图的基本操作图的基本操作 6.3 图的存储结构图的存储结构 6.4 图的遍历图的遍历 6.5 生成树和最小生成树生成树和最小生成树第220页

147、主菜单6.1 6.1 图的定义和术语图的定义和术语一一 图的定义图的定义 图图G G由两个集合构成，记作由两个集合构成，记作G=G= 其中其中V V是顶点的非空有限集合，是顶点的非空有限集合，E E是是边的有限集合，其中边是顶点的无序对或有序对集合。边的有限集合，其中边是顶点的无序对或有序对集合。G1=G1=V1=vV1=v0 0 ,v ,v1 1,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v

148、,v4 4)无序对无序对(v(vi i,v,vj j) )：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为表示，称为无向边无向边； V0V0 V4V4 V3V3 V1V1 V2V2例例G1 G1 图示图示第221页主菜单6.1 图的定义和术语图的定义和术语G2 G2 图示图示有序对有序对v ：用以为用以为v vi i起点、以起点、以v vj j为终点为终点的有向线段表示，称为的有向线段表示，称为有向有向边或弧边或弧； V0V0 V1V1 V2V2 V3V3G2=G2=V2=vV2=v0 0 v v1 1,v,v2 2,v,v3 3 E2=vE2= , v, , , ,第2

149、22页主菜单图的应用举例：图的应用举例：例例1 1 交通图（公路、铁路）交通图（公路、铁路） 顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示交通图中的有单行道双行道，分别用有向边、无向边表示；例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例例4 4 各种流程图各种流程图 如如产品的生产流程图产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 V0V0 V4V

150、4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V36.1 图的定义和术语图的定义和术语第223页主菜单二二 图的基本术语图的基本术语 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V36.1 图的定义和术语图的定义和术语1)1)无向图（无向图（undigraphundigraph）：）：在图在图G G中，若中，若所有边是无向边，则所有边是无向边，则 称称G G为无向图；为无向图；2)2)有有向图（向图（digraphdigraph）：）：在图在图G G中，若所有边是有向边，则称中，若所有边是有向边，则称G G为有向图；为有向图； 混和

151、图：混和图：在图在图G G中，即有无向边也有有向边，则称中，即有无向边也有有向边，则称G G为混合为混合图；图；3)3)无向完全图：任意两顶点间都有边的图称为无向完全图。无向完全图：任意两顶点间都有边的图称为无向完全图。在一个含有在一个含有n n个个顶点的无向完全图中，有顶点的无向完全图中，有n(n-1)/2n(n-1)/2条边。条边。4 4）有向完全图：任意两顶点之间都有方向互为相反的两条弧）有向完全图：任意两顶点之间都有方向互为相反的两条弧相连接的有向图称为有向完全图。在一个含有相连接的有向图称为有向完全图。在一个含有n n个顶点的有向个顶点的有向完全图中，有完全图中，有n(n-1)n(n

152、-1)条条弧。弧。5 5）稠密图）稠密图/ /稀疏图：若边数为稀疏图：若边数为e e，顶点数为顶点数为n n，边数稀少到边数稀少到eenlognnlogn，则称该图为稀疏图，否则该图为稠密图。则称该图为稀疏图，否则该图为稠密图。第224页主菜单6 6）顶点的度、入度、出度顶点的度、入度、出度 邻接点：边的两个顶点邻接点：边的两个顶点 关联边：若边关联边：若边e= (v, u), e= (v, u), 则称顶点则称顶点v v、u u 关联边关联边 在无向图中：在无向图中： 顶点顶点V V的度的度 = = 与与V V相关联的边的数目，记作相关联的边的数目，记作TD(V)TD(V) 在有向图中：在有

153、向图中： 顶点顶点V V的出度的出度= =以以V V为起点有向边数，记作为起点有向边数，记作OD(V)OD(V) 顶点顶点V V的入度的入度= =以以V V为终点有向边数，记作为终点有向边数，记作ID(V)ID(V) 顶点顶点V V的度的度= V= V的出度的出度+V+V的入度的入度 设图设图G G的顶点数为的顶点数为n n，边数为边数为e e 图的所有顶点的度数和图的所有顶点的度数和 = 2*e= 2*e （每条边对图的所有顶点的度数和每条边对图的所有顶点的度数和“贡献贡献”2 2度）度） 6.1 图的定义和术语图的定义和术语 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1

154、V1 V2V2 V3V3TD(V0)=2TD(V1)=3TD(V2)=3TD(V3)=2TD(V4)=2ID(V0)=1OD(V0)=2TD(V0)=3ID(V1)=1OD(V1)=0TD(V1)=1ID(V2)=1OD(V2)=1TD(V2)=2ID(V3)=1OD(V3)=1TD(V3)=2第225页主菜单 7)7)边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权（信息就称该边的权（weightweight）。）。8 8）网（网（networknetwork）：）：边（或弧）上带权的图称为网

155、。边（或弧）上带权的图称为网。9 9）路径、回路）路径、回路 无向图无向图G G=（V，E）中的顶点序列中的顶点序列v1,v2,v1,v2, , ,vkvk, ,若若(vi,vi+1)(vi,vi+1) E( E( i=1,2,i=1,2,k-1), v =v1, u =k-1), v =v1, u =vkvk, , 则称该序列是从顶点则称该序列是从顶点v v到顶点到顶点u u的路径；若的路径；若v=uv=u，则称该序列为回路；则称该序列为回路； 有向图有向图D=（V，E）中的顶点序列中的顶点序列v1,v2,v1,v2, , ,vkvk, , 若若 vi,vi+1 E E (i=1,2,(i=

156、1,2,k-1), v =v1, u =k-1), v =v1, u =vkvk, , 则称该序列是从顶点则称该序列是从顶点v v到顶点到顶点u u的路径；的路径；若若v=uv=u，则称该序列为回路；则称该序列为回路； 在在图图1 1中，中，V0,V1,V2,V3 V0,V1,V2,V3 是是V0V0到到V3V3的路径；的路径； V0,V1,V2,V3,V0V0,V1,V2,V3,V0是回路；是回路；在在图图2 2中，中，V0,V2,V3 V0,V2,V3 是是V0V0到到V3V3的路径；的路径； V0,V2,V3,V0V0,V2,V3,V0是回路；是回路；无向图无向图G1G1有向图有向图G2

157、 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3例例6.1 图的定义和术语图的定义和术语第226页主菜单 10)10)简单路径和简单回路简单路径和简单回路 在一条路径中在一条路径中, ,若除起点和终点外若除起点和终点外, ,所有顶点各不所有顶点各不相同相同, ,则称该路径为简单路径；则称该路径为简单路径； 由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路； 在在图图1 1中，中，V0,V1,V2,V3 V0,V1,V2,V3 是是简单路径；简单路径； V0,V1,V2,V4,V1V0,V1,V2,V4,V1不是简单路径；在不是简单路径

158、；在图图2 2中，中， V0,V2,V3,V0V0,V2,V3,V0是简单回路；是简单回路；6.1 图的定义和术语图的定义和术语无向图无向图G1G1有向图有向图G2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3例例第227页主菜单11）子图）子图设有两个图设有两个图G=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，E1关联的顶点都在关联的顶点都在V1中，则称中，则称G1是是G的子图；的子图；例例(b)、(c)是是(a)的子图的子图(a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4

159、V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V26.1 图的定义和术语图的定义和术语第228页主菜单 1212）连通图（强连通图）连通图（强连通图） 在无（有）向图在无（有）向图G=G= V, E 中，若对任何两个顶点中，若对任何两个顶点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称G G是连通图（强连通图）是连通图（强连通图） 非非连连通通图图 连连通通图图 强强连连通通图图 非非强强连连通通图图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V

160、3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V46.1 图的定义和术语图的定义和术语第229页主菜单13）连通分图（强连通分量）连通分图（强连通分量）无向图无向图G的极大连通子图称为的极大连通子图称为G的连通分量的连通分量极大连通子图意思是：该子图是极大连通子图意思是：该子图是G连通子图，将连通子图，将G的任何不在该子图中的任何不在该子图中的顶点加入，子图不再连通；的顶点加入，子图不再连通；连通分图连通分图非非连连通通图图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4 V0V0 V2V2 V1V1非连通分图非连通分图6.1 图的定义和术语图的定义和术语第230页主菜

161、单有向图有向图D的极大强连通子图称为的极大强连通子图称为D的强连通分量的强连通分量极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是D强连通子图，将强连通子图，将D的任何不在该子图的任何不在该子图中的顶点加入，子图不再是强连通的；中的顶点加入，子图不再是强连通的；强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V16.1 图的定义和术语图的定义和术语第231页主菜单14)生成树生成树包含无向图包含无向图G所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G的的生成树生成树极小连通子图意思是：该子图是极小连通子图意思是：该子图是G的

162、连通子图，在该子图中删除任何一的连通子图，在该子图中删除任何一条边，子图不再连通，条边，子图不再连通，若若T是是G的生成树的生成树当且仅当当且仅当T满足如下条件满足如下条件T是是G的连通子图的连通子图T包含包含G的所有顶点的所有顶点T中无回路中无回路连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V26.1 图的定义和术语图的定义和术语第232页主菜单6.2 6.2 图的基本操作图的基本操作图有图有以下基本操作：以下基本操作：1）CreatGraph（

163、G）：）：输入图输入图G的顶点和边，建立的顶点和边，建立图图G的存储。的存储。2）DFSTraverse（G,V）：）：从图从图G的一个顶点的一个顶点V出发出发深度优先遍历图深度优先遍历图G。3）BFSTraverse（G,V）：）：从图从图G的一个顶点的一个顶点V出发出发广度优先遍历图广度优先遍历图G。第233页主菜单图的存储结构至少要保存两类信息：图的存储结构至少要保存两类信息： 1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定约定: : G= G=是图是图, , V= V=v v0 0,v,v1 1,v,v2 2, v, vn-1n-1 , ,设顶点的设顶点的 角标角标

164、为它的编号为它的编号 如何表示顶点间的关系如何表示顶点间的关系？顶点的编号顶点的编号 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V36.3 6.3 图的存储表示图的存储表示第234页主菜单1 1 邻接矩阵邻接矩阵：G G的邻接矩阵是满足如下条件的的邻接矩阵是满足如下条件的n n阶阶矩阵：矩阵： Aij=Aij=1 1 若若(vi,vi+1)(vi,vi+1) E E 或或 E E0 0 否则否则0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 12 20 1 0 1 0 1 0 1 1 13 30 1 0 00 1 0 04 40 1

165、 1 0 0 1 1 0 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0一一 邻接矩阵表示邻接矩阵表示 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V36.3 6.3 图的存储表示图的存储表示第235页主菜单无向图邻接矩阵表示法特点：无向图邻接矩阵表示法特点：1 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点顶点v的度：等于二维数组对应行（或列）中的度：等于二维数组对应行（或列）中1的个数；的个数；3 3）判断两顶点判断两顶点v

166、 v、u u是否为邻接点：只需判二维数组对应分量是否为是否为邻接点：只需判二维数组对应分量是否为1 1；4 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1 1或清或清0 0；5 5）设图的顶点数为设图的顶点数为 n ,n ,存储图用一维数组存储图用一维数组, , 数组元素有数组元素有 m m 个个 （m=n),m=n),则则 G G占用存储空间：占用存储空间：m+nm+n2 2；G G占用存储空间只与它的顶点数有关，与边数无关；适占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；用于边稠密的图；对有向图的数组表

167、示法可做类似的讨论对有向图的数组表示法可做类似的讨论0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 12 20 1 0 1 0 1 0 1 1 13 30 1 0 00 1 0 04 40 1 1 0 0 1 1 0 0 0邻接矩阵表示法邻接矩阵表示法的空间代价的空间代价只与图的顶点数有关只与图的顶点数有关 V0V0 V4V4 V3V3 V1V1 V2V26.3 6.3 图的存储表示图的存储表示第236页主菜单图的基本操作：图的基本操作：1 1）求）求无向图某顶点无向图某顶点vivi的度的度( (或有向图中或有向图中vivi的出度的出度) )。Ai0Ai0到到Ain-1Ai

168、n-1中的非中的非0 0个数，即数组个数，即数组A A中第中第i i 行的非行的非0 0 元素的个数；元素的个数；2）求有向图某）求有向图某顶点顶点vi的的入度。：入度。：A0iA0i到到A n-1i A n-1i 中的非中的非0 0个数，即数个数，即数组组A A中第中第i i 列的非列的非0 0 元素的个数；元素的个数；3 3）检测图中的总边数。扫描整个数组）检测图中的总边数。扫描整个数组A A，统计出数组中非统计出数组中非0 0元素的个数。无向元素的个数。无向图的总边数为非图的总边数为非0 0元素个数的一半，而有向图的总弧数为非元素个数的一半，而有向图的总弧数为非0 0元素个数元素个数；

169、V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V30 1 0 1 00 1 0 1 01 10 1 0 10 1 0 12 20 1 0 1 0 1 0 1 1 13 30 1 0 00 1 0 04 40 1 1 0 0 1 1 0 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 06.3 图的存储表示图的存储表示第237页主菜单二二邻接表邻接表三 邻接表是图的链式存储结构邻接表是图的链式存储结构四四1 1 无向图的邻接表无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；顶点：

170、通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的关联同一顶点的边：用线性链表存储边：用线性链表存储该结点表示边该结点表示边（Vi Vi VjVj）, ,其中的其中的1 1是是VjVj在一维数组中的位置在一维数组中的位置例例 V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4下标下标 编号编号 linklink6.3 图的存储表示图的存储表示第238页主菜单图的邻接表类型定义图的邻接表类型定义structnode/边（弧）结点的

171、类型定义边（弧）结点的类型定义intvertex;/边（弧）的另一顶点的在数组中的位置边（弧）的另一顶点的在数组中的位置structnode*link;/指向下一条边（弧）结点的指针指向下一条边（弧）结点的指针;typedefstructNODE；NODEadjlistMAX;/邻接点链表的头指针所对应的邻接点链表的头指针所对应的数组数组6.3 图的存储表示图的存储表示第239页主菜单无向图的邻接表的特点无向图的邻接表的特点 1 1）在）在G G邻接表中，同一条边对应两个结点；邻接表中，同一条边对应两个结点； 2）顶点）顶点v的度：等于的度：等于v对应线性链表的长度；对应线性链表的长度；3）判

172、定两顶点）判定两顶点v v ，u u是否邻接：要看是否邻接：要看v v对应线性链表中有无对应的结点对应线性链表中有无对应的结点 4 4）在）在G G中增减边：要在两个单链表插入、删除结点；中增减边：要在两个单链表插入、删除结点； 5 5）设存储顶点的一维数组大小为设存储顶点的一维数组大小为m(mm(m 图的顶点数图的顶点数n), n), 图的边数为图的边数为e e，G G占占用存储空间为：用存储空间为：m+2*em+2*e。G G占用存储空间与占用存储空间与 G G 的顶点数、边数均有关；适用的顶点数、边数均有关；适用于边稀疏的图于边稀疏的图 0 0 1 1 2 2 3 3 4 4m-1m-1

173、V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 04 43 3邻接表的空间代价邻接表的空间代价与图的边及顶点数均有关与图的边及顶点数均有关 V0V0 V4V4 V3V3 V1V1 V2V22 26.3 图的存储表示图的存储表示第240页主菜单2 2 有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表1 1）有向图的邻接表）有向图的邻接表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为以同一顶点为起点起点的弧的弧：用线性链表存储：用线性链表存储类似于无向图的邻接表，类似于无向图的邻接表，所不同的是：所不同的是：以同一顶点为

174、起点的弧以同一顶点为起点的弧：用线性链表存储用线性链表存储下标下标 编号编号 linklink V0V0V1V1V2V2V3V31 12 23 30 00123m-1例例 V0V0 V1V1 V2V2 V3V36.3 图的存储表示图的存储表示第241页主菜单2 2）有向图的逆邻接表）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧以同一顶点为终点的弧：用线性链表存储：用线性链表存储V0V0V1V1V2V2V3V30123m-10 00 02 23 3 类似于有向图的邻接表，类似于有向图的邻接表，所不同的是：所不同的是：以同一顶点为以同一顶

175、点为终点终点弧弧：用线性链表存储用线性链表存储例例 V0V0 V1V1 V2V2 V3V36.3 图的存储表示图的存储表示第242页主菜单建立邻接表的算法建立无向邻接表intcreate(NODE*adjlist)NODE*p;intnum,i,v1,v2;scanf(“%dn”,&num);/读入结点数for(i=0;inum;i+)/初始化空关系图adjlisti.link=NULL;adjlisti.vertex=i;6.3 图的存储表示图的存储表示第243页主菜单for(;)scanf(“%dto%dn”,&v1,&v2);/读入一条边读入一条边if(v10|v2vertex=v2;p

176、-link=adjlistv1.link;adjlistv1.link=p;/插入在链表首部插入在链表首部p=(NODE*)malloc(sizeof(NODE);p-vertex=v1;p-link=adjlistv2.link;adjlistv2.link=p;return(num);/返回图的结点数6.3 图的存储表示图的存储表示第244页主菜单在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。6.3 图的存储表示图的存储表示第245页主菜单图的遍历：从图的某顶点出发，访问图中所有顶点，并且图的遍历：从图的某顶点出发，访

177、问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组必须对顶点进行标记，一般用一个辅助数组 visitMAXvisitMAX作为对作为对顶点的标记，当顶点顶点的标记，当顶点vivi未被访问，未被访问，visitivisiti值为值为0 0；当；当vivi已被访已被访问，则问，则visitivisiti值为值为1 1。 图的遍历与图的遍历与树的遍历有什么不同树的遍历有什

178、么不同 有两种遍历方法有两种遍历方法（它们对无向图，有向图都适用）它们对无向图，有向图都适用） 深度优先遍历深度优先遍历 广度优先遍历广度优先遍历6.4 图的遍历图的遍历第246页主菜单一一、深度优先遍历、深度优先遍历从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）依次从依次从v v的未被访问的邻接点出发，继续对图进行深的未被访问的邻接点出发，继续对图进行深度优先遍历；度优先遍历； V0,V1,V3,V7,V4,V2,V5,V6,V0,V1,V3,V7,V4,V2,V5,V6, 由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯

179、一的深度优先序列不是唯一的这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径例例求图求图G G以以V0V0起点的起点的的的深度优先序列深度优先序列：V0,V1,V4,V7,V3,V2,V5,V6V0,V1,V4,V7,V3,V2,V5,V6 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V46.4 图的遍历图的遍历第247页主菜单如果将图顶点的邻接点如果将图顶点的邻接点看作二叉树结点的左、右孩子看作二叉树结点的左、右孩子深度优先遍历与深度优先遍历与先序遍历先序遍

180、历是不是很类似？是不是很类似？深度优先遍历深度优先遍历从图中某顶点从图中某顶点v v出发：出发： （1 1）访问顶点）访问顶点v v；（2 2）依次从依次从v v的未被访问的邻接点的未被访问的邻接点出发，对图进行深度优先遍历；出发，对图进行深度优先遍历； 先序遍历（先序遍历（DLRDLR） 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树）先序遍历右子树； V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V16.4 图的遍历图的遍历第248页主菜单结点定义结点定义typedefstr

181、uctnodeintvertex;/边（弧）的另一顶点在数组中的位置边（弧）的另一顶点在数组中的位置structnode*link;/指向下一条边（弧）结点的指针指向下一条边（弧）结点的指针;typedefstructNODE；NODEadjlistMAX;/邻接点链表的头指针所对应的数组邻接点链表的头指针所对应的数组辅助数组辅助数组 intint visitMAX visitMAX; /; /顶点标志数组顶点标志数组, ,全局变量全局变量 NODE * NODE * ptrMAXptrMAX; /; /顶点链表指针数组顶点链表指针数组visitvisit0 01 12 23 34 4m-1m

182、-10 00 00 00 00 0深度优先遍历算法深度优先遍历算法6.4 图的遍历图的遍历第249页主菜单调用深度优先遍历算法的主函数调用深度优先遍历算法的主函数main()NODEadjlistMAX;intnum;num=create(adjlist);/*建立图建立图G的邻接表的邻接表*/depthfirst(adjlist,num);/*调用对图调用对图G深度优先搜索算法深度优先搜索算法*/深度优先遍历算法深度优先遍历算法6.4 图的遍历图的遍历第250页主菜单voiddepthfirst(NODEadjlist,intnum)inti;for(i=0;inum;i+)ptri=adj

183、listi.link;/记住每个顶点链表的第一个结点的地址记住每个顶点链表的第一个结点的地址visiti=0;/给每个结点一个未访问标记给每个结点一个未访问标记for(i=0;ivertex;取结点的邻接顶点取结点的邻接顶点wif(visitw=0;)dfs(w);ptrv=ptrv-link;/记住顶点记住顶点v的的邻接顶点位置，邻接顶点位置，该邻接点在该邻接点在w之后之后从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G。6.4 图的遍历图的遍历第252页主菜单 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 0 0 1 1 2 2

184、 3 3 4 4 5 5 6 6 7 7V0V0V1V1V2V2V3V3V4V4V5V5V6V6V7V71 12 20 01 11 15 57 77 73 30 06 64 42 26 65 52 24 43 36.4 图的遍历图的遍历第253页主菜单如果将图顶点的邻接点如果将图顶点的邻接点看作二叉树结点的左、右孩子看作二叉树结点的左、右孩子深度优先遍历算法与深度优先遍历算法与先序遍历算法先序遍历算法的结构是不是很像？的结构是不是很像？深度优先遍历算法深度优先遍历算法voiddfs(intv)intw;printf(“%d,“,v);visitv=1;/访问此结点访问此结点while(ptrv

185、！=NULL）w=ptrv-vertex;取结点的邻接顶点取结点的邻接顶点wif(visitw=0;)dfs(w);ptrv=ptrv-link;/记住顶点记住顶点v的邻接点位置，的邻接点位置，该邻接点在该邻接点在w之后之后先序遍历递归算法先序遍历递归算法voidprev(NODE*root)if(root!=NULL)printf(“%d,”,root-data)；/访问此结点访问此结点prev(root-lch);/访问孩子结点访问孩子结点prev(root-rch);比较比较6.4 图的遍历图的遍历第254页主菜单图中某未访问过的顶点图中某未访问过的顶点vivi出发：出发：1 1）访问顶

186、点访问顶点vi vi ；2 2）访问访问 vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , w, wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点依次从这些邻接点出发，访问它们的所有未被访问的邻接点; ; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；依此类推，直到图中所有访问过的顶点的邻接点都被访问；二、广度优先遍历二、广度优先遍历（类似于树的按层遍历）（类似于树的按层遍历） V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5

187、 V4V4这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，广度优先序列不是唯一的广度优先序列不是唯一的例例求图求图G G 的以的以V0V0起点的起点的的广的广度优先序列度优先序列: :V0,V1,V2,V3,V4,V5,V6,V76.4 图的遍历图的遍历第255页主菜单从图中某顶点从图中某顶点vivi出发：出发：1 1）访问顶点访问顶点vi vi ；（；（容易实现）容易实现）2 2）访问访问vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , w, wk k ； （容易

188、实现）容易实现）3 3）依次从这些邻接点（在步骤依次从这些邻接点（在步骤 2 2）访问的顶点）出发，访问它们的所有）访问的顶点）出发，访问它们的所有未被访问的邻接点未被访问的邻接点; ; 依此类推，直到图中所有访问过的顶点的邻接点都被依此类推，直到图中所有访问过的顶点的邻接点都被访问；访问；为实现为实现 3 3），），需要保存在步骤需要保存在步骤(2(2）中访问的顶点，而且）中访问的顶点，而且访问这些顶点访问这些顶点邻接邻接点点的顺序为：先保存的顶点，其邻接点先被访问。的顺序为：先保存的顶点，其邻接点先被访问。广度优先遍历算法广度优先遍历算法在在广度优先遍历算法中，广度优先遍历算法中，需设置一

189、队列需设置一队列Q Q，保存已访问的顶点，保存已访问的顶点，并控制遍历顶点的顺序。并控制遍历顶点的顺序。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V16.4 图的遍历图的遍历第256页主菜单广度优先遍历广度优先遍历从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点访问顶点v v ；2 2）访问访问v v的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , w, wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接依次从这些邻接点出发，访问它们的所有未被访问的邻接点点; ; 依此类推，直到图中所有访问过的顶点

190、的邻接点都依此类推，直到图中所有访问过的顶点的邻接点都被访问；被访问； V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1QV1V1V2V2V3V3V0V0V4V4V5V5V6V6V7V7V0V0V1V1V2V2V3V3V4V4V5V5V6V6V7V76.4 图的遍历图的遍历第257页主菜单void void breadfirst(intbreadfirst(int num) num) intint; ; for (i=0;inum;i+) visiti=0; for (i=0;inum;i+) visiti=0;/给所有顶点一个未被访问标记给所有顶点一个未被访问标

191、记 for (i=0;inum;i+)for (i=0;ivertex; w = p-vertex; /遍历遍历v v所指的整个链表所指的整个链表 if(visitw= =0) if(visitw= =0) /如果如果w w 未被访问过未被访问过 printf(“%d,”,wprintf(“%d,”,w); ); / / 访问访问 w w visitw=1;enter(w); visitw=1;enter(w); 访问后，访问后，w w 入队入队 p=p-link; p=p-link; 6.4 图的遍历图的遍历第259页主菜单 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4 V0V

192、0 V2V2 V3V3 V1V1 V5V5 V4V4深度优先遍历深度优先遍历广度优先遍历广度优先遍历两种遍历两种遍历的比较的比较6.4 图的遍历图的遍历第260页主菜单6.5.1生成树生成树生成树是一个连通图生成树是一个连通图G的一个极小的连通子图。包含图的一个极小的连通子图。包含图G的所的所有顶点，但只有有顶点，但只有n-1条边，并且是连通的。生成树可由遍历过程中条边，并且是连通的。生成树可由遍历过程中所经过的边组成。所经过的边组成。深度优先遍历得到的深度优先遍历得到的生成树称为生成树称为深度优先深度优先生成生成树树；广；广度优先遍历得到的度优先遍历得到的生成树称为生成树称为广广度优先度优先

193、生成树生成树。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V3V3 V0V0 V7V7 V6V6 V5V5 V4V4 V2V2 V1V1深度优先深度优先生成树生成树广广度优先度优先生成树生成树6.5 6.5 生成树和最小生成树生成树和最小生成树第261页主菜单要要在在n n 个个城城市市间间建建立立交交通通网网，要要考考虑虑的的问问题题如如何何在在保保证证n n 点点连连通通的的前题下最节省经费前题下最节省经费?V2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 6例例求求解解:连连通通6 6个个城城市

194、市且且代代价价最小的交通线路最小的交通线路?如何求连通图的如何求连通图的最小生成树最小生成树?6.5.2 6.5.2 最小生成树（最小支撑树）最小生成树（最小支撑树） 若有一个连通的无向图若有一个连通的无向图 G G ，有有 n n 个顶个顶点，并且它的边是有权值的。在点，并且它的边是有权值的。在 G G 上构造上构造生成树生成树 G G , ,最小生成树最小生成树 n-1 n-1 条边的权值之条边的权值之和最小的和最小的 G G 。6.5 生成树和最小生成树生成树和最小生成树第262页主菜单 普鲁姆算法基本步骤普鲁姆算法基本步骤设设G=（V，E）为为一一个个具具有有n个个顶顶点点的的带带权权

195、的的连连通通网网络络，T=（U，TE）为构造的生成树。为构造的生成树。（1）初始时，）初始时，U=u0，TE= ；（2）在在所所有有u U、v V-U的的边边（u,v）中中选选择择一一条条权权值值最最小小的的边边，不不妨设为（妨设为（u,v)；（3）(u,v)加入加入TE，同时将同时将u加入加入U；（4）重复重复(2)、（、（3），直到），直到U=V为止；为止；(1)普鲁姆算法普鲁姆算法V2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 66.5 生成树和最小生成树生成树和最小生成树第263页主菜单V V2 2V V0 0V V3 3V V

196、5 5V V4 4V V1 13652165546V V2 2V V0 0V V3 3V V5 5V V4 4V V1 112V V2 2V V0 0V V3 3V V5 5V V4 4V V1 114V V2 2V V0 0V V3 3V V5 5V V4 4V V1 1142V V2 2V V0 0V V3 3V V5 5V V4 4V V1 11452V V3 3V V0 0V V3 3V V5 5V V4 4V V1 11453U= U= V0V0 U= U= V0,V2V0,V2 U= U= V0,V2,V5V0,V2,V5U= U= V0,V2,V5,V3V0,V2,V5,V3 U

197、= U= V0,V2,V5,V3,V1V0,V2,V5,V3,V1 U= U= V0,V2,V5,V3,V1,V4V0,V2,V5,V3,V1,V4 第264页主菜单 有关数据的存储结构有关数据的存储结构无向连通网络无向连通网络:G G 为为选择权值最小的边选择权值最小的边:置一个一维数组：置一个一维数组：closestclosest ，对对i i V-U V-U closestclosesti= j (ji= j (j U) U) (j,i)(j,i)是一条边，且是是一条边，且是 i i 到到 U U 中各顶点中各顶点“权权最小边最小边”LowcostiLowcosti ：用来保存连接用来保

198、存连接 i i 到到 U U 中各顶点中各顶点“权最小边权最小边”的权。的权。 普鲁姆算法涉及的数据和操作：普鲁姆算法涉及的数据和操作：数据：无向连通网络数据：无向连通网络操作操作:选择权值最小的边，不妨设为（选择权值最小的边，不妨设为（u,v)(u,v)加入加入TE，u加入加入UV2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 6UV-U viUV-U vivj6.5 生成树和最小生成树生成树和最小生成树第265页主菜单V V2 2V V0 0V V3 3V V5 5V V4 4V V1 13652165546例例 0 0 0 0 0

199、0 0 0 0 0 0 0 0 6 1 5 max max 0 6 1 5 max max iclosestilowcosti012345iclosestilowcosti012345 0 2 0 0 2 20 2 0 0 2 2 0 5 0 5 6 0 5 0 5 6 4 4U=v0U=v0,v2V V2 2V V0 0V V3 3V V5 5V V4 4V V1 13652165546U UU U对对i i V-U V-U closestclosesti= j (ji= j (j U) U) (j,i)(j,i)是一条边，且是是一条边，且是 i i 到到 U U 中各顶点中各顶点“权最小边

200、权最小边”LowcostiLowcosti ：用来保存连接用来保存连接 i i 到到 U U 中各顶点中各顶点“权最小边权最小边”的权。的权。V-U=v1,V2,V3,V4,V5V-U=v1,V3,V4,V56.5 生成树和最小生成树生成树和最小生成树第266页主菜单 0 0 0 0 0 00 0 0 0 0 0 0 60 6 1 1 5 max max5 max max lowcostlowcost00 0 2 0 0 2 20 2 0 0 2 2 0 5 0 5 60 5 0 5 6 4 4 closestclosestlowcostlowcost0,20,2 0 2 0 5 2 20 2

201、 0 5 2 2 0 5 00 5 0 2 2 6 6 0 0 closestclosestlowcostlowcost0,2,50,2,5 0 2 0 5 2 20 2 0 5 2 2 0 0 5 5 0 0 6 0 0 6 0 0 closestclosestlowcostlowcost0,2,5,30,2,5,3 0 2 0 5 1 20 2 0 5 1 2 0 0 0 00 0 0 0 3 3 0 0closestclosestlowcostlowcost0,2,5,3,10,2,5,3,1 0 2 0 5 1 20 2 0 5 1 2 0 0 0 0 0 0 0 0 0 0 0 0

202、closestclosestlowcostlowcost0,2,5,3,1,40,2,5,3,1,4i iclosestclosest 0 0 1 2 3 4 5 1 2 3 4 5 U U6.5 生成树和最小生成树生成树和最小生成树第267页主菜单普里姆算法普里姆算法图采用邻接矩阵表示，邻接矩阵所对应的二维数组是图采用邻接矩阵表示，邻接矩阵所对应的二维数组是costMAXMAX,则则 (1) (1) 初始化初始化(U=0),closesti=0;lowcosti=cost0i; U=0),closesti=0;lowcosti=cost0i; lowcost0=0;lowcost0=0; (

203、i=1,2,3, n-1;) (i=1,2,3, n-1;) (2) (2) 每次扫描数组每次扫描数组lowcostilowcosti ，找出值最小且不为找出值最小且不为0 0的的lowcostklowcostk ，得到得到 最小生成树的一条边（最小生成树的一条边（ closestk,k),closestk,k),将其将其输出。输出。（3 3）令）令lowcostklowcostk=0,=0,将将k k并入并入U U 中中（4 4）修改数组）修改数组closesticlosesti和和 lowcostilowcosti （ lowcostilowcosti ！=0 =0 及及i V-Ui V-

204、U（5 5）重复（重复（2 2）（）（3 3）（）（4 4），直到），直到U=VU=V（或循环或循环 n-1 n-1 次）结束次）结束 6.5 生成树和最小生成树生成树和最小生成树第268页主菜单用普里姆算法用普里姆算法viudviud PRIM( PRIM( intint costN, costN, intint start_v ) start_v ) intint closestN,lowcostN,i,j,k,minclosestN,lowcostN,i,j,k,min; ; for (i=0; jN; i+) for (i=0; jN; i+) lowcostilowcosti=cos

205、tstart_vi;=coststart_vi; closesti=start_v; closesti=start_v; for (i=1; iN; i+) / for (i=1; iN; i+) / 循环循环n-1n-1次，每次求出最小生成树的一条边次，每次求出最小生成树的一条边 min=MAX; min=MAX; for (j=0; jN; j+) for (j=0; jN; j+) if ( if (lowcostjlowcostj!=0 & !=0 & lowcostjlowcostjmin)min) min= min= lowcostj;klowcostj;k=j; / =j; /

206、找出值最小的找出值最小的 lowcostklowcostk printf(“%d,%d:%dn”,closestk,kprintf(“%d,%d:%dn”,closestk,k, , lowcostklowcostk);); lowcostklowcostk=0; / =0; / 将将 k k 并入并入U U 中中 for (j=0; jN; j+) / for (j=0; jN; j+) / 修改修改 lowcostlowcost 和和closest closest if (costkj!=0 & costkj if (costkj!=0 & costkj lowcostjlowcostj)

207、 lowcostjlowcostj=costkj;closestj=k;=costkj;closestj=k; 6.5 生成树和最小生成树生成树和最小生成树第269页主菜单 基本步骤基本步骤设设G=（V，E）为为一一个个具具有有n个个顶顶点点的的带带权权的的连连通通网网络络，最最小小生生成成树树的的初初始始状态为有状态为有n个个顶点但无边的非连通图顶点但无边的非连通图T=（V， ）。）。（1）将将E中中的的边边按按权权值值的的递递增增顺顺序序排排序序，选选择择权权值值最最小小的的边边，若若与与相相关关的的顶点落在顶点落在T中不同的连通分量上，则将其加入中不同的连通分量上，则将其加入T中，否则，

208、将其弃舍。中，否则，将其弃舍。（2）循环至所有顶点在同一的连通分量上。循环至所有顶点在同一的连通分量上。如如何何识识别别一一条条边边所所相相关关的的顶顶点点是是否否落落在在同同一一个个连连通通分分量量上上？可可将将一一个个连连通通分分量量的的所所有有顶顶点点看看成成一一个个集集合合，当当从从E中中取取出出一一条条边边（xi,xj）时时，若若xi,xj在同一集合在同一集合u中，则将该边弃舍；中，则将该边弃舍；否则，则将该边加入到否则，则将该边加入到T中，中，并将并将xj所在的集合所在的集合v并入集合并入集合u中。中。（2）克鲁斯卡尔算法克鲁斯卡尔算法V2V2V0V0V3V3V5V5V4V4V1V

209、13 36 65 52 21 16 65 55 54 46 66.5 生成树和最小生成树生成树和最小生成树第270页主菜单需要引入辅助数组需要引入辅助数组 sets （1）初初始始化化：图图G中中的的n个个顶顶点点，构构成成n个个连连通通分分量量，顶顶点点xi对对应应的的连连通通分分量量用用集集合合i表表示示，所所以以setsi=i,即即表表示示第第i个个顶顶点在集合点在集合i中。中。（2）依依次次取取出出E中中的的边边（按按边边权权值值递递增增顺顺序），设取出的边为（序），设取出的边为（xi,xj）。）。（3）判判断断：若若setsi=setsj,则则表表示示xi和和xj在在同同一一集集合合

210、中中，返返回回（2）；否否则则，转到（转到（4）。）。（4）将将边边（xi,xj）并并入入T，同同时时将将xj所所在在的的集集合合v（与与xj连连通通的的顶顶点点）并并入入xi所所在在的的集集合合u（与与xi连连通通的的顶顶点点），即即：由由v=setsj和和u=setsi，扫扫描描辅辅助助数数组组sets，若若 setsk=v, 则则 令令 setsk=u 。返返回回（2）。）。（5）重重复复（2）、（3）、（4），取取出出n-1条边。条边。012345012345下标下标setsV2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 66.

211、5 生成树和最小生成树生成树和最小生成树第271页主菜单V2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 6012345012345下标下标sets012345012345下标下标sets031001111V2V2V0V0V3V3V5V5V4V4V1V1123456.5 生成树和最小生成树生成树和最小生成树第272页主菜单克鲁斯卡尔算法中，数据结构定义为：克鲁斯卡尔算法中，数据结构定义为：structnodeintbegin,end;/边的相关顶点编号边的相关顶点编号intcost;/边的权值边的权值typedefstructnodeED

212、GE;EDGEedgesMAX;/存放边的数组存放边的数组intnum;/数组中实际存放的边数数组中实际存放的边数intint kruskalkruskal (EDGE edges , (EDGE edges ,intint num) num) intint setsN,t,i,j,k,u,v; setsN,t,i,j,k,u,v; for(i=0; iN; i+) setsi=i; / for(i=0; iN; i+) setsi=i; /初始化初始化 k=0;t=0;k=0;t=0;6.5 生成树和最小生成树生成树和最小生成树第273页主菜单克鲁斯卡尔算法：克鲁斯卡尔算法： while(t

213、N)&(knum)while(tN)&(knum) i=edgesk.begin; j=edgesk.end;k+; i=edgesk.begin; j=edgesk.end;k+; /按顺序取出一条边按顺序取出一条边 u=setsi; v=setsj;u=setsi; v=setsj; /xi在集合在集合u中中,xj在集合在集合v中中 if(u!=v)if(u!=v) /xi,xj不在同一集合中不在同一集合中 printf(“%d,%dprintf(“%d,%d: %dn”,u,v,edgesk.cost);: %dn”,u,v,edgesk.cost); t+; t+; for (i=0;

214、 iN; i+) for (i=0; iN; i+) if(setsi= =v)seti=u;if(setsi= =v)seti=u; /xi在集合的在集合的v并入在集合的并入在集合的u中中 if (t= =N-1)return(1);if (t= =N-1)return(1); else return(0); else return(0); 6.5 生成树和最小生成树生成树和最小生成树第274页主菜单第275页主菜单7.1排序概述排序概述7.1.1排序介绍排序（Sorting）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一

215、组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。表7-1学生档案表学号姓名年龄性别99001王晓佳18男99002林一鹏19男99003谢宁17女99004张丽娟18女99005周涛20男99006李小燕16女第276页主菜单例如，在表7-1中，若以每个记录的学号为关键字，按排序码年龄的递增（由小到大）排序，则所有记录的排序结果可简记为：（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）；也可能为：（99006，16），（99003，17），（99004，18），（9900

216、1，18），（99002，19），（99005，20）；这两个结果都是表7-1按年龄的递增排序结果。若按排序码姓名来进行递增排序，则得到的排序结果为：（99006，李小燕），（99002，林一鹏），（99001，王晓佳），（99003，谢宁），（99004，张丽娟），（99005，周涛）当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。7.1排序概述排序概述第277页主菜单7.1.2 基本概念基本概念1排序码（SortKey）作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一

217、种记录都可找到一个取得它排序码的函数Skey(一个或多个关键字的组合)。2有序表与无序表有序表与无序表一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。3正序表与逆序表正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，我们一般只讨论正序表。7.1排序概述排序概述第278页主菜单4排序定义排序定义若给定一组记录序列r1，r2，rn，其排序码分别为s1，s2，sn，将这些记录排成顺序为rk1，rk2，rkn的一个序列R，满足条件sk1sk2skn，获得这些记录排成顺序为rp1，rp2，rpn的一个序列

218、R”，满足条件sp1sp2spn的过程称为排序。也可以说，将一组记录按某排序码递增或递减排列的过程，称为排序。5稳定与不稳定稳定与不稳定因为排序码可以不是记录的关键字，同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。在上例中（见表9-1，按年龄排序），如果一种排序方法使排序后的结果必为前一个结果，则称此方法是稳定的；若一种排序方法使排序后的结果可能为后一个结果，则称此方法是不稳定的。7.1排序概述排序概述第279页主菜单6内排序与外排序内排序与外排序按照排序过程中使用内外存的不同将排序方法分为

219、内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。本章仅讨论内排序。7排序的时间复杂性排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。7.1排序概述排序概述第280页主菜单为

220、了以后讨论方便，我们直接将排序码写成一个一维为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。序码的值递增排列。插入排序（直插排序、二分排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）排序排序7.1排序概述排序概述第281页主菜单72插入排序插入排序7.2.1 直接插入排序直接插入排序1直接插入排序的基本思想直接插入排序（StraightInsertionSorting）的基

221、本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。2直接插入的算法实现第282页主菜单voidsort(NODEarray,intn)/待排序元素用一个数组待排序元素用一个数组array表示，数组有表示，数组有n个元素个元素inti,j;NODEx;/x为中间结点变量为中间结点变量for(i=1;i=0)&(x.keyarrayj.key)arrayj+1=arrayj;j-;/顺序比较和移动顺

222、序比较和移动arrayj+1=x;72插入排序插入排序例例如如，n=6，数数组组R的的六六个个排排序序码码分分别别为为：17，3，25，14，20，9。它的直接插入排序的执行过程如图。它的直接插入排序的执行过程如图9-1所示。所示。第283页主菜单72插入排序插入排序第284页主菜单3直接插入排序的效率分析直接插入排序的效率分析从上面的叙述可以看出，直接插入排序算法十分简单。那么它的效率如何呢？首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）

223、。因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。72插入排序插入排序第285页主菜单7.2.2希尔排序希尔排序1希尔排序的基本思想希尔排序的基本思想希希尔尔排排序序,又又称称为为“缩缩小小增增量量排排序序”。是是1959年年由由D.L.Shell提提出出来来的的。该该方方法法的的基基本本思思想想是是：先先将将整整个个待待排排元元素素序序列列分分割割成成若若干干个个子子序序列列（由由相相隔隔某某个个“增增量量”的的元元素素组组成成的的）分分别别进进行行直直接接插插入入排排序序，待待整整个个序序列列中中的的元元素素基基本本有有序序（增增量量足足够够小小

224、）时时，再再对对全全体体元元素素进进行行一一次次直直接接插插入入排排序序。因因为为直直接接插插入入排排序序在在元元素素基基本本有有序序的的情情况况下下（接接近近最最好好情情况况），效效率率是是很很高高的的，因因此此希尔排序在时间效率上比前两种方法有较大提高。希尔排序在时间效率上比前两种方法有较大提高。2希尔排序的效率分析虽然我们给出的算法是三层循环，最外层循环为log2n数量级，中间的for循环是n数量级的，内循环远远低于n数量级，因为当分组较多时，组内元素较少；此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。因此，希尔排序的时间复杂性在O（nlog2n）和O（n2）

225、之间，大致为O（n1.3）。由由于于希希尔尔排排序序对对每每个个子子序序列列单单独独比比较较，在在比比较较时时进进行行元元素素移移动动，有有可可能能改改变变相同排序码元素的原始顺序，因此希尔排序是不稳定的。相同排序码元素的原始顺序，因此希尔排序是不稳定的。72插入排序插入排序第286页主菜单73交换排序交换排序7.3.1 冒泡排序1冒泡排序的基本思想通通过过对对待待排排序序序序列列从从后后向向前前（从从下下标标较较大大的的元元素素开开始始），依依次次比比较较相相邻邻元元素素的的排排序序码码，若若发发现现逆逆序序则则交交换换，使使排排序序码码较较小小的的元元素素逐逐渐渐从从后后部部移移向向前前部

226、部（从从下下标标较较大大的的单单元元移移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。向下标较小的单元），就象水底下的气泡一样逐渐向上冒。因因为为排排序序的的过过程程中中，各各元元素素不不断断接接近近自自己己的的位位置置，如如果果一一趟趟比比较较下下来来没没有有进进行行过过交交换换，就就说说明明序序列列有有序序，因因此此要要在在排排序序过过程程中中设设置置一一个个标标志志flag判判断断元元素素是是否否进进行行过过交交换换。从而减少不必要的比较。从而减少不必要的比较。例如，n=8，数组array的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算

227、法的执行过程。第287页主菜单73交换排序交换排序第288页主菜单2冒泡排序的算法实现冒泡排序的算法实现voidBubblesort(NODEarray,intn)inti,j,flag;/当flag为0则停止排序NODEtemp;for(i=1;i=i;j-)if(arrayj.keyarrayj-1.key)/发生逆序temp=arrayj;arrayj=arrayj-1;arrayj-1=temp;flag=1;/交换，并标记发生了交换if(flag=0)break;73交换排序交换排序第289页主菜单例例如如，n=6，数数组组R的的六六个个排排序序码码分分别别为为：17，3，25，14

228、，20，9。下下面面用用图图7-3给出冒泡排序算法的执行过程。给出冒泡排序算法的执行过程。73交换排序交换排序第290页主菜单3冒泡排序的效率分析冒泡排序的效率分析从上面的例子可以看出，当进行完第三趟排序时，数组已经有序，所以第四趟排序的交换标志为0，即没进行交换，所以不必进行第四趟排序。从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。

229、因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。73交换排序交换排序第291页主菜单7.3.2 快速排序快速排序1快速排序的基本思想快速排序（QuickSorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单

230、元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。73交换排序交换排序第292页主菜单快快速速排排序序的的过过程程为为：把把待待排排序序区区间间按按照照第第一一个个元元素素（即即基基准准元元素素）的的排排序序码码分分为为左左右右两两个个子子序序列列的的过过程程叫叫做做一一次次划划分分。设设待待排排序序序序列列为为arraystartarrayend，其其中中start为为下下限限，end为为上上限限，startend，mid=arraystart为为该该序序列列的的基基准准元元素素，为为了了实实现现一一次次划划分分，令令i,j的的初初值值分分别别

231、为为start和和end。在在划划分分过过程程中中，首首先先让让j从从它它的的初初值值开开始始，依依次次向向前前取取值值，并并将将每每一一元元素素arrayj的的排排序序码码同同mid的的排排序序码码进进行行比比较较，直直到到arrayj.key=end)return;i=start;j=end;mid=arrayi;while(ij)while(imid.key)j-;if(ij)arrayi=arrayj;i+;while(ij&arrayi.key=mid.key)i+;if(ij)arrayj=arrayi;j-;/一次划分得到基准值的正确位置arrayi=mid;quicksort(

232、array,start,i-1);/递归调用左子区间quicksort(array,i+1,end);/递归调用右子区间73交换排序交换排序第296页主菜单3快速排序的效率分析快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含

233、有n-i个(i代表二叉树的层数（1in）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。73交换排序交换排序第297页主菜单74选择排序选择排序7.4.1 直接选择排序直接选择排序1直接选择排序的基本思想直接选择排序的基本思想直接选择排序也是一种简单的排序方法。它的基本思想是：第一次从array0arrayn-1中选取最小值，与array0交换，第二次从ar

234、ray1arrayn-1中选取最小值，与array1交换，第三次从array2arrayn-1中选取最小值，与array2交换，第i次从arrayi-1arrayn-1中选取最小值，与arrayi-1交换，, 第n-1次从arrayn-2arrayn-1中选取最小值，与arrayn-2交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。第298页主菜单第299页主菜单3直接选择排序的效率分析直接选择排序的效率分析在直接选择排序中，共需要进行n-1次选择和交换，每次选

235、择需要进行n-i次比较（1in-1），而每次交换最多需3次移动，因此，总的比较次数C=(n2-n)/2，总的移动次数M=3(n-1)。由此可知，直接选择排序的时间复杂度为O(n2)数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。例如，给定排序码为3，7，3，2，1，排序后的结果为1，2，3，3，7。7.4.1 7.4.1 直接选择排序直接选择排序第300页主菜单7.4.2 树形选择排序树形选择排序从直接选择排序可知，在n个排序码中，找出最小值需n-1次比较，找出第二小值需n-2

236、次比较，找出第三小值需n-3次比较，其 余 依 此 类 推 。 所 以 ， 总 的 比 较 次 数 为 ： (n-1)+(n-2)+3+2+1=(n2-n)/2，那么，能否对直接选择排序算法加以改进，使总的比较次数比(n2-n)/2小呢？显然，在n个排序码中选出最小值，至少进行n-1次比较，但是，继续在剩下的n-1个关键字中选第二小的值，就并非一定要进行n-2次比较，若能利用前面n-1次比较所得信息，则可以减少以后各趟选择排序中所用的比较次数，比如8个运动员中决出前三名，不需要7+6+5=18场比赛（前提是，若甲胜乙，而乙胜丙，则认为甲胜丙），最多需要11场比赛即可（通过7场比赛产生冠军后，第

237、二名只能在输给冠军的三个对中产生，需2场比赛，而第三名只能在输给亚军的三个对中产生，也需2场比赛，总共11场比赛）。具体见图7-6所示。第301页主菜单7.4.2 树形选择排序树形选择排序第302页主菜单从图7-6（a）可知，8个队经过4场比赛，获胜的4个队进入半决赛，再经过2场半决赛和1场决赛即可知道冠军属谁（共7场比赛）按照锦标赛的传递关糸，亚军只能产生于分别在决赛，半决赛和第一轮比赛中输给冠军的选取手中，于是亚军只能在b、c、e这3个队中产生（见图7-6（b），即进行2场比赛（e与c一场，e与c的胜队与b一场）后，即可知道亚军属谁。同理，第三名只需在c、f、g这3个队产生（见图7-6（c

238、）即进2场比赛（f与g一场，f与g的胜队与c一场）即可知道第三名属谁。树形选择排序，又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的排序码进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直到选出最小排序码为止。7.4.2 树形选择排序树形选择排序第303页主菜单例如，给定排序码头50，37，66，98，75，12，26，49，树形选择排序过程见图7-7。7.4.2 树形选择排序树形选择排序第304页主菜单7.4.2 树形选择排序树形选择排序第305页主菜单1堆的定义堆的定义若有n个元素的排序码k1，k2，k3，kn，当满足如下条件：kik2ikik

239、2i（1）kik2i+1或(2)kik2i+1其中i=1,2,n/2则称此n个元素的排序码k1，k2，k3，kn为一个堆。若将此排序码按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。7.4.3 堆排序堆排序第306页主菜单若n个元素的排序码k1，k2，k3，kn满足堆，且让结点按1、2、3、n顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i，右孩子为2i+1）可知，堆排序实际与一棵完全二叉树有关。若将排序码初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使排序码变成能

240、符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。2堆排序的基本思想堆排序的基本思想将排序码k1，k2，k3，kn表示成一棵完全二叉树，然后从第n/2个排序码(即树的最后一个非终端结点)开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第n/2-1个排序码重复刚才操作，直到第一个排序码止。这时候，该二叉树符合堆的定义，初始堆已经建立。7.4.3 堆排序堆排序第307页主菜单接着，可以按如下方法进行堆排序：将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1kn-1重新建堆，然后k1和kn-1交换，再将k1kn-2重新建堆，然后k1和kn-2交换，如

241、此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，kn已排成一个有序序列。例如，给定排序码49，38，65，97，76，13，27，49，建立初始堆的过程如图7-8所示。7.4.3 堆排序堆排序第308页主菜单第309页主菜单建成如图7-8(e)所示的堆后，堆排序过程如图7-9所示。7.4.3 堆排序堆排序第310页主菜单7.4.3 堆排序堆排序第311页主菜单4堆排序的效率分析堆排序的效率分析在整个堆排序中，共需要进行n+n/2-1次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全

242、二叉树的深度，所以，每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。堆排序占用的辅助空间为1（供交换元素用），故它的空间复杂度为O（1）。堆排序是一种不稳定的排序方法，例如，给定排序码：2，1，2，它的排序结果为：1，2，2。7.4.3 堆排序堆排序第312页主菜单75归并排序7.5.1 二路归并排序二路归并排序二路归并排序的基本思想二路归并排序的基本思想: : 二二路路归归并并排排序序的的基基本本思思想想是是：将将两两个个有有序序子子区区间间（有有序序表表）合合并并成成一一个个有有序序子子区区间间，一一次次合合并并完完成成后后，有有序序子子区区间

243、间的的数数目目减减少少一一半半，而而区区间间的的长长度度增增加加一一倍倍，当当区区间间长长度度从从1 1增增加加到到n n（元元素素个个数数）时时，整整个个区区间间变变为为一一个个，则则该该区区间中的有序序列即为我们所需的排序结果。间中的有序序列即为我们所需的排序结果。第313页主菜单例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。75归并排序第314页主菜单3二路归并排序的效率分析二路归并排序的效率分析二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。而归并趟数为log2n(当log2n为奇数时，则为log2n+1)。因为每一趟归

244、并就是将两两有序子区间合并成一个有序子区间，而每一对有序子区间归并时，记录的比较次数均小于等于记录的移动次数（即由一个数组复制到另一个数组中的记录个数），而记录的移动次数等于这一对有序表的长度之和，所以，每一趟归并的移动次数均等于数组中记录的个数n，即每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为O(nlog2n)。利用二路归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。75归并排序第315页主菜单由于二路归并排序中，每两个有序表合并成一个有序表时，若分别在两个有序表中出现有相同排序码，则会

245、使前一个有序表中相同排序码先复制，后一有序表中相同排序码后复制，从而保持它们的相对次序不会改变。所以，二路归并排序是一种稳定的排序方法。75归并排序第316页主菜单76各种内排序方法的比较和选择各种内排序方法的比较和选择7.6.1 各种内排序方法的比较各种内排序方法的比较1从时间复杂度比较从时间复杂度比较从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的

246、最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。第317页主菜单2从空间复杂度比较从空间复杂度比较归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。3.从稳定性比较直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。4从算法简单性比较从算法简单性比较直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法

247、简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。76各种内排序方法的比较和选择各种内排序方法的比较和选择第318页主菜单7.6.2 各种内排序方法的选择各种内排序方法的选择1从时间复杂度选择从时间复杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。2从空间复杂度选择从空间复杂度选择尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。3一般选择规则一般选择规则（1）当待排序元素的个数n较大，排

248、序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。76各种内排序方法的比较和选择各种内排序方法的比较和选择第319页主菜单（2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。（3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。（4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。(5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。76各种内排序方法的比较和选

249、择各种内排序方法的比较和选择第320页主菜单第321页主菜单8.1查找的基本概念查找的基本概念查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可

250、以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。第322页主菜单有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方

251、式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。第323页主菜单查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中i为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率

252、相等，i为查找第i个元素所用到的比较次数。第324页主菜单82线性表的查找线性表的查找8.2.1 顺序查找顺序查找1顺序查找的基本思想顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。下面以顺序表的形式来描述算法。第325页主菜单2顺序查找算法实现顺序查找算法实现stru

253、ctnode;intkey;/key为关键字，类型设定为整型;typedefstructnodeNODE;intseq_search(NODEarrry,intn,intk)/在表中查找关键字值inti;为的元素,n是表的长度for(i=0;in&arrayi.key!=k;i+);/从表尾开始向前扫描if(ik，则在array1到arraymid-1中继续查找，若有arraymid.keyk，则在arraymid+1到arrayn-1中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)

254、。第328页主菜单2二分查找算法实现二分查找算法实现intbin_search(NODEarray,intn,intk)intlow=0,hig=n-1,mid;while(lowk)hig=mid-1;/在左子区间中查找在左子区间中查找elselow=mid+1;/在右子区间中查找在右子区间中查找return(-1);/查找失败查找失败第329页主菜单例 如 ， 假 设 给 定 有 序 表 中 关 键 字 为05,13,19,21,37,56,64,74,80,88,92将查找K=21和K=85的情况描述为图8-1及图8-2形式。012345678910012345678910第330页主菜

255、单012345678910012345678910第331页主菜单012345678910012345678910第332页主菜单012345678910012345678910第333页主菜单012345678910图图8-2查找查找K=85的示意图的示意图(查找不成功查找不成功)第334页主菜单3.二分查找的性能分析为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定 树 。 例 如 ， 图 8-1给 定 的 关 键 字 序 列05,13,1

256、9,21,37,56,64,74,80,88,92，的判定树见图8-3。第335页主菜单从图8-3可知，查找21的过程是从根到结点3的路径，查找85,应在结点9的左子树上,但其左子树为空,故失败。二叉树第K层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。则二分查找的时间复杂度为O(log2n)。第336页主菜单8.2.3分块查找分块查找 1.分块查找分块查找的思想的思想分块查找是顺序查找的一种改进方法，又称索引顺序查找，具体实现如下：将一个主表分成n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，用每个子表最大关键字和指示块中第一个记录在表中位

257、置建立索引表。typedefstructintkey;NODE;typedefstructintkey,pos;INDEX;第337页主菜单例如，给定关键字序列如下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3，即将该序列分成3个子表，每个子表有6个元素，则得到的主表和索引表如图所示。22121389203342443824486058744986532248860612分块查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38,则先在索引表中按顺序比较，因为22kkey=k)return(p);/查找成功

258、elseif(p-keyk)p=p-lch;/进入左子树查找elsep=p-rch;/进入右子树查找return(NULL);二叉排序树查找的算法实现二叉排序树查找的算法实现第343页主菜单（3 3）二叉排序树查找实例）二叉排序树查找实例第344页主菜单4二叉排序树查找的性能分析二叉排序树查找的性能分析在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。第3

259、45页主菜单 8.3.2平衡二叉树查找平衡二叉树查找1平衡二叉树的概念平衡二叉树的概念平衡二叉树(balancedbinarytree)是由阿德尔森一维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。第346页主菜单若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。 将结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。 如图8-8所示二叉排序树，是一棵平衡二叉树，而如图8-9所示二叉排序树，就不是一棵平衡二叉树。平衡二叉树概念平衡二叉树概念第347页主菜

260、单 2.2.非平衡二叉树的平衡处理非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。 （1 1）LLLL型型 的处理的处理( (左左型左左型) )如图8-10所示，在A的左孩子B上插入一个左孩子结点C，使A的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。(注：图中结点旁边的数字表示

261、该 结点的平衡因子)第348页主菜单（2 2）LRLR型的处理型的处理( (左右型左右型) )如图8-11所示，在A的左孩子B上插入一个右孩子C，使的A的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将C变到B与A之间，使之成为LL型，然后按第(1)种情形LL型处理。第349页主菜单（3 3）RRRR型的处理型的处理( (右右型右右型) )如图8-12所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点C成为B的右子树。第350页主菜单（4

262、4）RLRL型的处理型的处理( (右左型右左型) )如图8-13所示，在A的右孩子B上插入一个左孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将C变到A与B之间，使之成为RR型，然后按第(3)种情形RR型处理。第351页主菜单例例8-2 8-2 给给定定一一个个关关键键字字序序列列4,5,7,2 4,5,7,2 ,1,3,6,1,3,6，试试生生成成一一棵棵平平衡衡二二叉树。叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图8-14。

263、第352页主菜单第353页主菜单3 3平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。第354页主菜单例例8-3 8-3 对对例例8-28-2给给定定的的关关键键字字序序列列4,5,7,2,1,3,64,5,7,2,1,3,6，试试用用二二叉叉排排序序树树和和平平衡衡二二叉叉树树两两种种方方法法查查找找，给给出出查查找找6 6的的次次数数及及成成功功的的平平均查找长度。均查找

264、长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-14，得到的二叉排序树见图8-15。第355页主菜单从图8-15的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-14的平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。第356页主菜单8.3.3 B- 树树B-树是一种平衡的多路查找树，在文件系统中很有用，定义如下：一棵m阶的B-树，或是空树，或是满足以下条件的m叉树：（1）树

265、中每个结点至多有m棵子树（2）若根结点不是叶子结点，则至少有二棵子树。（3）除根结点外的所有非终端结点至少有int(m/2)棵子树（4）所有结点包含信息（n,A0,K1,A1,Kn,An)其中Ki为关键字且有序。Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+1,An所指子树中所有结点的关键字均大于Kn（5）所有叶子结点都出现在同一层次上，即所有空的指针出现在同一层上。第357页主菜单 n A0 K1A1KnAnn+1个分支135118111127139347536419924378第358页主菜单B-树的操作树的操作（1）查找要查找关键字k的记录，首先从根结点开始，若找

266、到则找所对应的记录，否则沿p所指的子树继续查找，其中A0kKnAiKikKi+1若直到叶子结点还未找到，则查找失败。第359页主菜单B-树的操作树的操作（2）插入设要插入关键值为k的记录，指向k所在记录的指针为p。首先找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是：申请一个新结点，由指针p指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点

267、中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。第360页主菜单452431237505390617095插入303730插入8585618570539070第361页主菜单84哈希表（散列查找哈希表（散列查找）8.4.1 基本概念基本概念散列查找，也称为哈希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为哈希表或散列表。散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造哈希函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。例如，要找关键字为k的元

268、素，则只需求出函数值H（k），H（k）为给定的哈希函数，代表关键字k在存贮区中的地址，而存贮区为一块连续的内存单元，可用一个一维数组(或链表)来表示。第362页主菜单例，假设有一批关键字序列18,75,60,43,54,90,46，给定哈希函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为：H（18）=18%13=5H（75）=75%13=10H（60）=60%13=8H（43）=43%13=4H（54）=54%13=2H（90）=90%13=12H（46）=46%13=7于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT（哈希表或散列表）中，

269、具体表示为：第363页主菜单其中HT就是散列存贮的表，称为散列表或哈希表。从哈希表中查找一个元素相当方便，例如，查找75，只需计算出H（75）=75%13=10，则可以在HT10中找到75。为了保证哈希表查找得以实现，必须使记录的存放规则和查找规则一致，即：使用同样的哈希函数。在存储时，以每个记录的关键字为自变量，通过哈希函数计算出存储地址，将该记录存放在存储地址对应的存储单元中。在查找时，以查找值为自变量，通过哈希函数计算出地址，从该地址所对应的存储单元中取出记录数据。第364页主菜单上面讨论的哈希表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键

270、字有可能对应同一个内存地址，即两个记录的关键值不等，但它们的哈希函数的值相同，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免的，除非构造出的哈希函数为线性函数。哈希函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。使用哈希方法，首先要选择一个好的哈希函数，使一组关键值所得到的哈希地址能均匀分布在整个地址空间中，并且冲突次数尽可能地少。第365页主菜单在哈希存贮中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。第一是

271、与装填因子有关，所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即=n/m。当越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将变得太小，这样将会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。第二是与所构造的哈希函数有关(前面己介绍)。第三是与解决冲突的方法有关，这些内容后面将再作进一步介绍。第366页主菜单8.4.2 哈希函数的构造哈希函数的构造哈希函数的构造目标是使哈希地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单，冲突次数少。具体常用的构造方法有如下几种：1直接定址法直接定址法可表示为H（k）

272、=a.k+b，其中a、b均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。2数字分析法数字分析法对关键字序列进行分析，取那些位上数字变化多的、频率大的作为哈希函数地址。第367页主菜单例如，对如下的关键字序列：993465329937224299387433993013679932281799338967993541579936853799368532通过对上述关键字序列分析，发现前3位相同，第8位只可取2、3、7，因此，这四位不可取。中间的四位的数字变化多些，可看成是随机的，若规定地址取3位，则哈希函数可取它的第4、5、6

273、位。于是有：H（99346532）465H（99372242）722H（99387433）874H（99301367）016H（99322817）228第368页主菜单3平方取中法平方取中法取关键字平方后的中间几位为哈希函数地址。这是一种比较常用的哈希函数构造方法，但在选定哈希函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到哈希函数地址。如图中，随机给出一些关键字，并取平方后的第2到4位为函数地址。第369页主菜单4折叠法折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的

274、叠加和（舍去进位）作为哈希函数地址，称为折叠法。例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有53558101104643014932，舍去高位，则有H（430104681015355）4932为该身份证关键字的哈希函数地址。5除留余数法除留余数法该方法是用关键字序列中的关键字k除以一个整数p所得余数作为哈希函数的地址，即H（k）kp。P=mm为哈希表长度第370页主菜单除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的p值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生

275、冲突的可能性。一般情形下，p取为一个素数较理想，并且要求装填因子最好是在0.60.9之间，所以p最好取1.1n1.7n之间的一个素数较好，其中n为哈希表中待装元素个数。6. 随机随机法法选择一个随机函数，取关键值的随机函数值为它的哈希地址，即H(key)=random(key)random()不能是一般的随机函数，固定的参数必须返回确定的值。第371页主菜单8.4.3 解决冲突的方法解决冲突的方法由于哈希存贮中选取的哈希函数不是线性函数，将大的关键值的取值空间映射到小的地址空间中，故不可避免地会产生冲突，下面给出常见的解决冲突方法。1开放定址法开放定址法开放定址法就是从发生冲突的那个单元开始，

276、按照一定的次序，从哈希表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突的发生。在哈希表未满时，处理冲突需要的“下一个”空地址在哈希表中解决。开放定址法利用下列公式求“下一个”空地址Hi=(H(key)+di)MODmi=1,2,K(K=m-1)其中H（key)为哈希函数，m为哈希表长度，di为增量序列第372页主菜单根据di的取法，解决冲突时具体使用下面一些方法。（1）线性探查法）线性探查法假设哈希表的地址为0m-1，则哈希表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾m-1时，又从0，1，2，.开始探查)等地址，直到

277、找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。假设发生冲突时的地址为d0=H(k)，则探查下一位置的公式为di=(di-1+1)%m(1im-1)，最后将冲突位置的关键字存入di地址中。例8-5给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，哈希函数H（k）=k%13，哈希表空间地址为012，试用线性探查法建立哈希存贮(哈希表)结构。得到的哈希表如图8-17所示第373页主菜单(2)二次方探查法二次方探查法该该方方法法规规定定，若若在在d地地址址发发生生冲冲突突，下下一一次次探探查查位位置置为为d+12，d-12,d+22，d-22，直到

278、找到一个空闲位置为止。直到找到一个空闲位置为止。开开放放地地址址法法充充分分利利用用了了哈哈希希表表的的空空间间，但但在在解解决决一一个个冲冲突突时时，可可能能造造成成下下一一个个冲冲突突。另另外外，用用开开放放地地址址法法解解决决冲冲突突不不能能随随便对结点进行删除。便对结点进行删除。第374页主菜单2.链地址法链地址法链地址法也称拉链法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表例：对给定的关键字序列19,14,23,1,68,20,84,27,55,11,10,79，给定哈希函数为H(k)=k%13，试用拉链法解决冲突建立哈希表。图8-18为用尾插法建

279、立的关于例8-6的拉链法解决冲突的哈希表。第375页主菜单第376页主菜单8.4.5 哈希查找的性能分析哈希查找的性能分析哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。1.线性探查法的性能分析线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子的值和该处理方法有关，这时的成功的平均查找长度为ASL=1/2(1+1/(1-)。2.拉链法查找的性能分析拉链法查找的性能分析由于拉链法查找就是在单链表上查找，

280、查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。它的平均查找长度ASL=1+/2。第377页主菜单例8-7给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。哈希函数H(k)=k%11。顺序查找的顺序表（一维数组）如图8-19所示，从图8-19可以得到顺序查找的成功平均查找长度为：ASL=(1+

281、2+3+4+5+6+7+8)/8=4.5；第378页主菜单二分查找的判定树（中序序列为从小到大排列的有序序二分查找的判定树（中序序列为从小到大排列的有序序列）如图列）如图8-20所示，所示，从图从图8-20可以得到二分查找的成功平均查找长度为：可以得到二分查找的成功平均查找长度为：ASL=(1+2*2+3*4+4)/8=2.625；第379页主菜单二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图8-21(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图8-21(b)所示，从图8-21(a)可以得到二叉排序树查找的成功平均查找长度为：ASL=(1+2*2+3*2+

282、4+5*2)=3.125；从图8-21(b)可以得到平衡二叉树的成功平均查找长度为：ASL=(1+2*2+3*3+4*2)/8=2.75；第380页主菜单线性探查法解决冲突的哈希表如图8-22所示，从图8-22可以得到线性探查法的成功平均查找长度为：ASL=（1+1+2+1+3+2+1+8）/8=2.375；第381页主菜单拉链法解决冲突的哈希表如图8-23所示。从图8-23可以得到拉链法的成功平均查找长度为：ASL=(1*6+2*2)/8=1.25。第382页主菜单第383页主菜单主要内容9.1 文件的基本概念文件的基本概念9.2 顺序文件顺序文件9.3 索引文件索引文件9.4 索引顺序文件

283、索引顺序文件9.5 散列文件散列文件9.6 多关键字文件多关键字文件第384页主菜单9.1 文件的基本概念1.文件的定义和术语文件的定义和术语 文件文件(file)是性质姓通的记录的集合。数据结构中所讨论的文件主要是性质姓通的记录的集合。数据结构中所讨论的文件主要是数据库意义上的文件，数据库中所研究的文件是指带有结构的记录是数据库意义上的文件，数据库中所研究的文件是指带有结构的记录集合，每个记录可由若干个数据项组成。集合，每个记录可由若干个数据项组成。文件可分为定长文件和不定长文件。文件可分为定长文件和不定长文件。2.文件的逻辑结构及操作文件的逻辑结构及操作检索操作检索操作简单查找简单查找范围

284、查找范围查找函数查找函数查找布尔查找布尔查找维护操作维护操作插入插入删除删除修改修改提高文件效率的再组织操作提高文件效率的再组织操作恢复恢复安全保护等安全保护等第385页主菜单3.文件的实时处理和批量处理文件的实时处理和批量处理实时处理是指文件操作响应时间要求严格。实时处理是指文件操作响应时间要求严格。批量处理是指可隔一段时间后处理一批操作。批量处理是指可隔一段时间后处理一批操作。4.文件的存储结构文件的存储结构顺序组织顺序组织索引组织索引组织散列组织散列组织链组织链组织提示：磁带只适用于存储顺序文件。磁盘适用于存提示：磁带只适用于存储顺序文件。磁盘适用于存储顺序、索引、散列和多关键字文件等。

285、储顺序、索引、散列和多关键字文件等。9.1 文件的基本概念第386页主菜单9.2 顺序文件顺序文件的特点：顺序文件的特点：1.在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们进入存储器的顺序一致。进入存储器的顺序一致。2.顺序文件的主要优点是顺序存取速度块，适宜于顺序存取和成顺序文件的主要优点是顺序存取速度块，适宜于顺序存取和成批处理。批处理。3.顺序文件的缺点是不利于修改。顺序文件的缺点是不利于修改。4.顺序文件特别适应于磁带存储器，也适应于磁盘存储。顺序文件特别适应于磁带存储器，也适应于磁盘存储。提示：顺序文件是指按记录写入文件的

286、先后顺序存放、提示：顺序文件是指按记录写入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。顺序文件可分为顺其逻辑顺序和物理顺序一致的文件。顺序文件可分为顺序有序文件和顺序无序文件两种。序有序文件和顺序无序文件两种。第387页主菜单9.3 索引文件索引文件的特点：索引文件的特点：索引文件由索引表和主文件两部分组成。索引文件由索引表和主文件两部分组成。索引文件是指逻辑记录和物理记录之间的对应关系的表。索引文件是指逻辑记录和物理记录之间的对应关系的表。索引文件的检索方式为直接存取或按关键字存取。索引文件的检索方式为直接存取或按关键字存取。索引文件的修改比较容易实现。索引文件的修改比较容易实现。索

287、引文件只能是磁盘文件。索引文件只能是磁盘文件。主文件有序的索引文件称为索引顺序文件，主文件无序的索引文件称为索引主文件有序的索引文件称为索引顺序文件，主文件无序的索引文件称为索引非顺序文件。非顺序文件。索引表都是有序的，查找索引表时可以用折半查找法。索引表都是有序的，查找索引表时可以用折半查找法。索引文件的术语索引文件的术语主文件、索引表和索引项主文件、索引表和索引项索引文件通常是在文件本身之外，另外建立一个索引表。索引指明逻辑索引文件通常是在文件本身之外，另外建立一个索引表。索引指明逻辑记录和物理记录之间的一一对应关系。索引表和主文件一起构成的文件记录和物理记录之间的一一对应关系。索引表和主

288、文件一起构成的文件称作索引文件。称作索引文件。索引表中的每一项称作索引项，索引项都是由主关键字和该关键字所在索引表中的每一项称作索引项，索引项都是由主关键字和该关键字所在记录的物理地址组成的。索引表必须按主关键字有序，而主文件本身可记录的物理地址组成的。索引表必须按主关键字有序，而主文件本身可以按主关键字有序也可以无序。以按主关键字有序也可以无序。索引顺序文件和索引非顺序文件。索引顺序文件和索引非顺序文件。主文件本身按主关键字有序的索引文件称为索引顺序文件，主文件无序主文件本身按主关键字有序的索引文件称为索引顺序文件，主文件无序的索引文件称为索引非顺序文件。的索引文件称为索引非顺序文件。一、索

289、引文件的特点和术语一、索引文件的特点和术语第388页主菜单二、索引文件的存储二、索引文件的存储索引文件在存储器上分为两个区：索引区和索引文件在存储器上分为两个区：索引区和数据区，前者存放索引表，后者存放主文数据区，前者存放索引表，后者存放主文件。件。三、索引文件的检索和修改三、索引文件的检索和修改1.索引文件的检索索引文件的检索2.在索引文件中插入记录在索引文件中插入记录3.删除索引文件中的记录删除索引文件中的记录9.3 索引文件第389页主菜单9.4 索引顺序文件一、一、ISAM文件文件ISAM是索引顺序存取方法。它是一种专为磁盘存取设计的是索引顺序存取方法。它是一种专为磁盘存取设计的文件组

290、织方式，采用静态索引结构。文件组织方式，采用静态索引结构。1.ISAM文件的特点文件的特点ISAM是索引顺序存取方法，该方法专为磁盘存取设计。是索引顺序存取方法，该方法专为磁盘存取设计。ISAM文件是属于索引顺序文件的组织方式。文件是属于索引顺序文件的组织方式。ISAM文件由多级主索引、柱面索引、磁道索引和主文件文件由多级主索引、柱面索引、磁道索引和主文件组成。组成。2.ISAM文件的组织结构文件的组织结构ISAM文件由多级主索引、柱面索引、磁道索引和主文件文件由多级主索引、柱面索引、磁道索引和主文件组成。组成。第390页主菜单3.ISAM文件的检索文件的检索在在ISAM文件上检索记录的步骤如

291、下：文件上检索记录的步骤如下：从主索引出发，找到相应的柱面索引；从主索引出发，找到相应的柱面索引；从柱面索引找到记录所在柱面的磁道索引；从柱面索引找到记录所在柱面的磁道索引；从磁道索引找到记录所在磁道的起始地址，由此出发从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。在该磁道上进行顺序查找，直到找到为止。4.在在ISAM文件中插入记录文件中插入记录5.删除删除ISAM文件中的记录文件中的记录9.3 索引文件第391页主菜单二、二、VSAM文件文件VSAM是虚拟存储存取方法。它是一种索引顺序文件是虚拟存储存取方法。它是一种索引顺序文件的组织方式，采用的组织方式

292、，采用B树作为动态索引结构。树作为动态索引结构。1.VSAM文件的特点文件的特点VSAM是虚拟存储存取方法，该方法为磁盘存取设计。是虚拟存储存取方法，该方法为磁盘存取设计。VSAM文件是属于索引顺序文件的组织方式。文件是属于索引顺序文件的组织方式。VSAM文件采用动态索引结构。文件采用动态索引结构。2.介绍介绍B树树B树是一种常用于文件组织的树是一种常用于文件组织的B树的变型树。树的变型树。3.VSAM文件查找、插入与删除文件查找、插入与删除9.3 索引文件第392页主菜单9.5 散列文件散列文件是利用散列存储方式组织的文件，亦称直接存取散列文件是利用散列存储方式组织的文件，亦称直接存取文件。

293、文件。散列文件的特点：散列文件的特点：散列文件是使用散列技术组织成的文件。散列文件是使用散列技术组织成的文件。散列文件中的记录通常是成组存放的，存放一组的存储单散列文件中的记录通常是成组存放的，存放一组的存储单位称为桶。位称为桶。散列文件是随机存放的，查找、存取和删除方便。散列文件是随机存放的，查找、存取和删除方便。一、散列文件的存储一、散列文件的存储散列文件存储类似于散列表，根据文件中关键字的特点，散列文件存储类似于散列表，根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到外存储设计一个散列函数和处理冲突的方法，将记录散列到外存储设备上。设备上。第393页主菜单二、散列文

294、件的查找二、散列文件的查找当在基桶中没有找到待查记录时，就沿着指针所指溢出当在基桶中没有找到待查记录时，就沿着指针所指溢出桶中进行查找。同一散列地址的溢出桶和基桶，在磁盘上桶中进行查找。同一散列地址的溢出桶和基桶，在磁盘上的物理位置不要相距太远。的物理位置不要相距太远。三、散列文件的删除操作三、散列文件的删除操作对被删记录做删除标记。阶段性的重新组织文件。散列对被删记录做删除标记。阶段性的重新组织文件。散列文件的优点是文件随机存取，记录不需进行排序，插入和文件的优点是文件随机存取，记录不需进行排序，插入和删除操作方便，存取速度快，不需要索引，节省存储空间。删除操作方便，存取速度快，不需要索引，

295、节省存储空间。其缺点是不能进行顺序存取，只能按关键字随机存取，不其缺点是不能进行顺序存取，只能按关键字随机存取，不能进行复合询问，在经过多次插入、删除后，造成文件结能进行复合询问，在经过多次插入、删除后，造成文件结构不合理，需要重新组织文件。构不合理，需要重新组织文件。9.5 散列文件第394页主菜单9.6 多关键字文件除了对主关键字建立索引外，对次关键字也建立相应索除了对主关键字建立索引外，对次关键字也建立相应索引的文件称为多关键字文件。次关键字索引本身可以是顺序引的文件称为多关键字文件。次关键字索引本身可以是顺序表，也可以是树表。表，也可以是树表。多关键字文件的特点：多关键字文件的特点：多

296、关键字文件不仅对主关键字索引，还对其余的次关键多关键字文件不仅对主关键字索引，还对其余的次关键字进行索引；字进行索引；多重表文件是对数据文件中的主关键字和次关键字分别多重表文件是对数据文件中的主关键字和次关键字分别建立索引，索引是用指针构成链表。建立索引，索引是用指针构成链表。倒排文件也是对数据文件中的主关键字和次关键字分别倒排文件也是对数据文件中的主关键字和次关键字分别建立索引，但索引是用倒排表。同一类关键字用一个倒排建立索引，但索引是用倒排表。同一类关键字用一个倒排表，一个倒排表中按关键字标出有序的记录号。表，一个倒排表中按关键字标出有序的记录号。第395页主菜单9.6 多关键字文件一、多

297、重表文件的概念一、多重表文件的概念多重表文件的主文件是一个顺序文件，每个需要查询的次多重表文件的主文件是一个顺序文件，每个需要查询的次关键字建立一个索引，并将具有相同次关键字的记录链接成关键字建立一个索引，并将具有相同次关键字的记录链接成一个链表，将次链表的头指针、链表长度以及次关键字作为一个链表，将次链表的头指针、链表长度以及次关键字作为索引表的一个索引项。索引表的一个索引项。二、倒排文件二、倒排文件倒排文件是多关键字文件的一种，它和多重表文件的次关倒排文件是多关键字文件的一种，它和多重表文件的次关键字索引的结构不同。键字索引的结构不同。1.倒排文件的概念倒排文件的概念倒排文件中的次关键字索引称作倒排表。相同次关键字的倒排文件中的次关键字索引称作倒排表。相同次关键字的不同记录之间不进行链接，而是在倒排表中列出具有该相不同记录之间不进行链接，而是在倒排表中列出具有该相同次关键字记录的各存储地址。主文件和倒排表就一起构同次关键字记录的各存储地址。主文件和倒排表就一起构成了倒排文件。成了倒排文件。2.倒排表的查找倒排表的查找