考研数据结构复习121130

1、数据结构复习试卷类型及比例试卷类型及比例数据结构（40分）：选择题：10分，简答题：10分，算法题：20分。内容：内容：1、线性表基本概念，顺序存储结构链式存储结构、相应操作。2、栈和队列的特点，栈的应用、递归算法的设计。3、树的基本概念，二叉树的性质、存储结构，树与森林，树的遍历及应用。4、图的基本概念，图的存贮结构，图的遍历和拓扑排序。 5、查找的基本概念、查找性能分析、顺序查找、折半查找和二叉排序树查找。6、直接插入排序、希尔排序、快速排序、简单选择排序和归并排序。数据结构复习数据结构的研究内容：数据结构的研究内容： 研究数据的逻辑结构、存储结构和运算集合。研究数据的逻辑结构、存储结构和

2、运算集合。 逻辑结构是数据结构的抽象，存储结构是数据结构的实现逻辑结构是数据结构的抽象，存储结构是数据结构的实现存储结构的二种类型存储结构的二种类型: 顺序存储结构顺序存储结构通过在存储器中的相对位置，通过在存储器中的相对位置， 表示数据的逻辑结构。表示数据的逻辑结构。 非顺序存储结构（链式存储结构）非顺序存储结构（链式存储结构） -由指针表示数据间的逻辑关系。由指针表示数据间的逻辑关系。常用的数据结构常用的数据结构 (1) 线性结构：结构中的数据元素之间存在着一对一线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组的线性关系。线性表、栈、队、字符串、数组 (2

3、) 树形结构：结构中的数据元素之间存在着一对多树形结构：结构中的数据元素之间存在着一对多的层次关系。的层次关系。-非线性结构非线性结构 (3) 图状结构或网状结构：结构中的数据元素之间存图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。在着多对多的任意关系。- 非线性结构非线性结构一一 线性表线性表 线性表是最简单、最常用的数据结构。线性表是最简单、最常用的数据结构。 栈、队列、串是特殊的线性表，数组和广栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展义表是线性表的扩展-线性结构线性结构 线性表的概念线性表的概念设设 A=（a1, a2, . , ai -1, ai , a

4、i+1, , an ）是一线性表，）是一线性表，1） 同一线性表中的元素必须是同一类型的；同一线性表中的元素必须是同一类型的；2） 在表中在表中 ai-1 领先于领先于ai ，ai 领先于领先于ai+1 ，称，称ai-1 是是ai 的前件，的前件，ai+1 是是ai 的后件；的后件；3） 在线性表中，除第一个元素和最后一个元素之外，其他在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；元素都有且仅有一个前件，有且仅有一个后件；4） 线性表中元素的个数线性表中元素的个数n 称为线性表的长度，称为线性表的长度，n=0 时称为空时称为空表；表；用一组连续的内存

5、单元依次存放一组连续的内存单元依次存放线性表的数据元素。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n 线性表（线性表（a1,a2, a3, . an ） 的顺序存储结构的顺序存储结构用顺序存储结构存储的线性表称为顺序表线性表的顺序存储和实现线性表的顺序存储和实现线性表的顺序存储结构线性表的顺序存储结构 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构是用一组任意的存线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。储单元存储线性表的各个数据元素。 为了表示线性表中元素的先后关系，每个为了表示线性表中元素的先后关系，每个

6、元素除需要存储自身的信息外，还要保存直元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置。接前趋元素或直接后继元素的存储位置。a ai i+1a a1a ai-i-1a a2 2a ai ia an n头指针：头指针：存放线性链表中第一个结点的存储地址存放线性链表中第一个结点的存储地址;头结点：头结点：链表的第一个元素结点前的附加结点；链表的第一个元素结点前的附加结点；带头结点的线性链表带头结点的线性链表：第一个元素结点前增加一个附加：第一个元素结点前增加一个附加结点的线性链表称为结点的线性链表称为 带头结点的线性链表；带头结点的线性链表； headhead是头指针是头指

7、针ai-1aia2a1ai+1nan 头结点头结点 空指针空指针headhead线性链表的每个结点中只有一个指针域故也称为单链表单链表例1、设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序。（不允许使用数组做辅助存储）例2、将单链表L1拆成二个链表，其中以L1为头的链表保持原来向后的链接，另一个链表的头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的节点，L2包含原链表的偶数序号的节点。例3、线性表合并：二个有序线性表LA、LB合并为一个有序线性表,合并后不另设新表存储。线性表的顺序存储和实现 顺序表是线性

8、表最简单的一种存储结构 小结顺序表的特点：1 通过元素的存储顺序反映 线性表中 数据元素之间的逻辑关系；2 可随机存取顺序表的元素；3 顺序表的插入、删除操作要通过移动元素实现；线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入、删除操作通过修改结点的指针实现； 3 不能随机存取元素；二二 栈与队列栈与队列栈是限定仅能在表尾一端进行插入、删除操栈是限定仅能在表尾一端进行插入、删除操作的线性表作的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除栈的概念栈的概念栈栈栈的

9、示意图栈的示意图出栈出栈进栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底，第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素最后一个出栈的元素为栈底元素栈栈顶顶栈栈底底ana2a1例:一个栈的输入序列为a,b,c,d，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？一个栈的输入序列为1,2,3,4n,? 小小 结结 1 栈是限定仅能在表尾一端进行插入、栈是限定仅能在表尾一端进行插入、 删除操作的线性表；删除操作的线性表； 2 栈的元素具有后进先出的特点；栈的元素具有

10、后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的栈顶元素的位置由一个称为栈顶指针的 变量指示，变量指示， 进栈、出栈操作要修改栈顶指针；进栈、出栈操作要修改栈顶指针； 栈栈队列队列队列的概念队列的概念一一 什么是队列什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入删除删除队列队列 a a1 1 a a2 2 a a3 3 a an n入队列入队列队队头头队队尾尾出队列出队列队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出第

11、一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素循环队列循环队列判分队空、队满有两种方法：判分队空、队满有两种方法：1）另设一个标志位以区分队空、队满。）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件：）少用一个存储单元，队满条件： rear+1=front;队空：队空： front=rear队列中元素的个数队列中元素的个数（rear front+ MAXQSIZE ）% MAXQSIZEfrontfront54 03

12、 12J6J6J7J7J8J8J4J4J5J5rearrear入队时的操作为入队时的操作为 rear=(rear+1) mod MAXQSIZE 小小 结结 1 队列是限定仅能在表尾一端进行插入，表头队列是限定仅能在表尾一端进行插入，表头一端删除一端删除 操作的线性表；操作的线性表； 2 队列中的元素具有先进先出的特点；队列中的元素具有先进先出的特点； 3 队头、队尾元素的位置分别由称为队头指针队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，和队尾指针的变量指示， 4 入队操作要修改队尾指针，出队操作要修改入队操作要修改队尾指针，出队操作要修改队头指针；队头指针； 树的树的 基本术

13、语基本术语结点的层次：根结点的层次定义为结点的层次：根结点的层次定义为1；根的孩子为第；根的孩子为第二层，依此类推；二层，依此类推；树的深度：树的深度：树中所有结点的层次的最大值树中所有结点的层次的最大值结点的度：结点子树的个数结点的度：结点子树的个数树的度：树的度： 树中结点度的最大值。树中结点度的最大值。叶子结点叶子结点：度为：度为 0 的结点；的结点；分枝结点：度不为分枝结点：度不为0的结点；的结点；J JI IA AC CB BD DH HG GF FE EK KL LM M三、树三、树与二叉树与二叉树 二叉树的性质二叉树的性质 性质性质1: 在二叉树的第在二叉树的第i层上至多有层上至

14、多有2i-1个结点个结点(i1)。 因二叉树中每个结点的度最大为因二叉树中每个结点的度最大为2，则第，则第k+1层的结点总数最多层的结点总数最多为第为第k层上结点最大数的层上结点最大数的2倍，即倍，即22k-1=2(k+1)-1，故结论成立，故结论成立。 性质性质2: 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结点（k1）。 证明证明：深度为深度为k的二叉树，其结点总数的最大值是二叉树中的二叉树，其结点总数的最大值是二叉树中每层结点的最大值相加每层结点的最大值相加.深度为深度为k的二叉树的结点总数至多为的二叉树的结点总数至多为 ：kikikii111122层上的最大结点个数第

15、故结论成立故结论成立。 性质性质3: 对任意一棵二叉树对任意一棵二叉树T，若叶结点数为，若叶结点数为n0，而其度为，而其度为2的的结点数为结点数为n2，则，则n0=n2+1。证明：设证明：设二叉树中结点总数为二叉树中结点总数为n， n1为度为为度为1的结点总数的结点总数。二叉树中所有结点的度小于等于二叉树中所有结点的度小于等于2，所以有：，所以有：n=n0+n1+n2设二叉树中分支数目为设二叉树中分支数目为B， 因除根结点外，因除根结点外， 每个结点均对应一个每个结点均对应一个进入它的分支，所以有：进入它的分支，所以有：n=B+1又因二叉树中的分支都是由度为又因二叉树中的分支都是由度为1和度为

16、和度为2的结点发出，的结点发出， 所以分支所以分支数目为数目为 B=n1+2n2整理后得整理后得n0=n2+1，故结论成立，故结论成立 二叉树顺序二叉树顺序存储结构，二叉链表存储结构存储结构，二叉链表存储结构 二叉链表中每个结点包含三个域：数据域、左指针域、右二叉链表中每个结点包含三个域：数据域、左指针域、右指针域指针域 A A F F E E D D C C B B二叉链表图示二叉链表图示 D D A A B B C C E E F F 先序遍历（T L L R R） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 先序遍历序列：A, ,B,D,B,D,E

17、E,G,G,C C, ,F F例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L L R R 的顺序遍历左子树 （3）先序遍历右子树：即按 T L L R R 的顺序遍历右子树 A A F F G G E E D D C C B B中序遍历（L L T R R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树 中序遍历序列： D,B,G,D,B,G,E E, ,A, ,C,FC,F例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 L L T R R 的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 L L T R R

18、 的顺序遍历右子树 A A F F G G E E D D C C B B后序遍历（L L R R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点 后序遍历序列： D,G,D,G,E E,B,B,F,CF,C, ,A例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按 L L R R T 的顺序遍历左子树 （2）后序遍历右子树：即按 L L R R T 的顺序遍历右子树 （3）访问根结点A A A F F G G E E D D C C B B例1 、 求二叉树的叶子结点个数。 D A B C E F root例3、将二叉树bt中每一个结点的左右子树互换。例2、试

19、写出一递归函数，判别两棵树是否相等。例4、求二叉树的高度。int PostTreeDepth(struct bitnode *root) /求二叉树的高度求二叉树的高度 int hl, hr, max; if(bt! =NULL) hl=PostTreeDepth(bt-LChild); /求左子树的深度 hr=PostTreeDepth(bt-RChild); /求右子树的深度 max=hlhr?hl: hr; /得到左、 右子树深度较大者 return(max+1); / 返回树的深度 else return(0); /如果是空树， 则返回0 二叉树1 1 二叉树：二叉树： 或为空树，或由

20、根及两颗互不相交或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身的左子树、右子树构成，并且左、右子树本身也是二叉树；也是二叉树； 2 2 二叉树可以用链式结构存储；二叉树可以用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。，每个结点仅被访问一次。 4 4二叉树的遍历可以分解为：访问根，遍历二叉树的遍历可以分解为：访问根，遍历左子左子树和树和遍历遍历右子树，常用的三种遍历算法：右子树，常用的三种遍历算法：先序先序遍历、中序遍历、后序遍历；遍历、中序遍历、后序遍历；树根结点 X 的第一个孩子结点 X 紧

21、邻的右兄弟二叉树根结点 X 的左孩子结点 X 的右孩子IACBDHGFEFIABDHGCE树树森林转换为二叉树的过程 ABCDEFGHIJ(a) 森林ABCDEFGHIJ(b) 森林中每棵树对应的二叉树ABEFGHIHCD(c) 森林对应的二叉树森林森林哈夫曼树及应用1 哈夫曼树哈夫曼树-带权带权路径长度最短的二叉树路径长度最短的二叉树(最优树）。最优树）。路径：路径：从一个结点到另一个结点之间的若干个分支序列；从一个结点到另一个结点之间的若干个分支序列；路径长度：路径长度：从一个结点到另一个结点路径上的分支数目；从一个结点到另一个结点路径上的分支数目；结点的路径长度：结点的路径长度：从根到该

22、结点的路径长度；从根到该结点的路径长度；树的路径长度：树的路径长度：树中所有叶子结点的路径长度之和；记为树中所有叶子结点的路径长度之和；记为PL.在结点数相同的条件下，完全二叉树是路径最短的二叉树在结点数相同的条件下，完全二叉树是路径最短的二叉树7 71 13 32 25 56 64 48 88 81 13 32 25 57 74 46 6非完全二叉树非完全二叉树 PL=10完全二叉树完全二叉树PL=9（路径最短的二叉树不唯一，不是完全二叉树，也可能路径长度最短）（路径最短的二叉树不唯一，不是完全二叉树，也可能路径长度最短）1 哈夫曼树哈夫曼树的概念（续）的概念（续）结点的权结点的权：根据应用

23、的需要给树的结点赋的权值；：根据应用的需要给树的结点赋的权值；结点的带权路径长度结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度树的带权路径长度=树中所有叶结点的带权路径长度之和；树中所有叶结点的带权路径长度之和；记作记作 ： WPL= wi Li 哈夫曼树：设有哈夫曼树：设有n个权值个权值(w1 , w2 , , wn )，构造有，构造有n个叶结点的二个叶结点的二叉树，每个叶结点以叉树，每个叶结点以 wi 为它的权值。则带权路径长度最小的二叉为它的权值。则带权路径长度最小的二叉树为哈夫曼树。树为哈夫曼树。B BD DA A

24、C CA AC C D DB B7 5 2 47 5 2 44 47 75 52 2WPL?WPL?WPL?WPL?哈夫曼树哈夫曼树? ?哈夫曼树哈夫曼树? ?构造哈夫曼树的算法：构造哈夫曼树的算法：1根据给定的n个权值 ，构造n棵带权只有一个根结点的二叉树 F=T1、T2Tn2在F中选取两棵根结点权值最小的树作为左、右子二叉树，构造一颗新的二叉树， 且新二叉树根的权值=左、右子树根结点权值之和；3从F中删除这两棵二叉树，并将新二叉树加入F；4重复 2、3，直到F中只含一棵二叉树为止；403060155 101530例：构造以W=（5，15，40，30，10）为权的哈夫曼树。305 10154

25、04030155 1015403030155 1015哈夫曼树中权值小的离根远，权值大的离根近401003060155 1015301234WPL=5*4+10*4+15*3+30*2+40*1=205 四、四、 图图 图的定义： 图G由两个集合V,E构成，记作G= 其中V是顶点的非空有限集合，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)

26、,(v2 2,v,v3 3)(v)(v2 2,v,v4 4)G1G1图示图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；例例 V0V0 V4V4 V3V3 V1V1 V2V2G2 G2 图示图示有序对 ：用以vi为起点、vj为终点的有向线段表示，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图； V0V0 V1V1 V2V2 V3V3G2=G2=V2=vV2=v0 0 v v1 1,v,v2 2,v,v3 3 E2=vE2= , v, , , ,图的存储结构图的存储结构-邻接矩阵邻接矩阵 若图若图G是一

27、个具有是一个具有n个顶点的无权图，个顶点的无权图，G的邻接矩阵是的邻接矩阵是nn矩阵矩阵A： 01, jiA若若或或(vi, vj) E E 反之 邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵： Ai，j=1 若(vi,vi+1)E 或 E0 否则0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 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邻接矩阵表示用邻接矩阵表示顶点间的关系 5.2 5.2 图的存储

28、结构图的存储结构 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 若图若图G是一个有是一个有n个顶点的网，则它的邻接矩个顶点的网，则它的邻接矩阵是具有如下性质的阵是具有如下性质的nn矩阵矩阵A： ijwjiA, 若若或或(vi, vj)E 反之反之 例如：一个有向网例如：一个有向网N,其邻接矩阵其邻接矩阵?图7.7v1v2v6v5v4v35485579612 5 7 5 7 4 4 8 98 9 5 6 5 6 5 5 2 1 2 1 图的遍历：图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。 为保证每一个顶点只被访问一次，必须对

29、顶点进行标记，当顶点vi未被访问，值为0；当vi已被访问，则值为1。 图的遍历有两种遍历方法图的遍历有两种遍历方法（对无向图，有向图都适用）对无向图，有向图都适用） 深度优先遍历 广度优先遍历 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1从图中某顶点v出发： 1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； （1 1） V0,V1,V3,V7,V4,V2,V5,V6,V0,V1,V3,V7,V4,V2,V5,V6, 由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的这是序列（这

30、是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径例例 深度优先遍历深度优先遍历求图G以V0为起点的的深度优先遍历序列： V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4 （2）V0,V1,V4,V7,V3,V2,V5,V6 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1从图中某个未被访问过的顶点从图中某个未被访问过的顶点vivi出发：出发：1 1）访问顶点）访问顶点vi vi ；2 2）访问）访问 vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , , w wk k ；3 3）

31、依次从这些邻接点出发，访问它们的所有未被访问的邻接点）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; ; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；依此类推，直到图中所有访问过的顶点的邻接点都被访问； 广度优先遍历广度优先遍历（类似于树的按层遍历）（类似于树的按层遍历）V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，广度优先序列不是唯一的广度优先序列不是唯一的例例求图求图G G的以的以V0V0起点的的广度优先序列

32、起点的的广度优先序列 V0,V1,V2,V3,V4,V5,V6,V7V0,V1,V2,V3,V4,V5,V6,V7拓扑序列：有向图拓扑序列：有向图D的一个顶点序列称作一个拓扑序列的一个顶点序列称作一个拓扑序列-如果该序列中任两顶点如果该序列中任两顶点v 、u ，若在，若在D中中v是是u前趋，则在序列中前趋，则在序列中v也是也是u前趋。前趋。拓扑排序：拓扑排序： 将有向图中顶点排成拓扑序列。将有向图中顶点排成拓扑序列。拓扑排序的应用拓扑排序的应用 安排施工计划（如上）安排施工计划（如上） 判断工程流程的是否合理判断工程流程的是否合理 AOV网（有向图）网（有向图）不存在有向回路不存在有向回路当且

33、仅当能对当且仅当能对AOV网网进行拓扑排序进行拓扑排序 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V62 拓扑排序方法：拓扑排序方法：1）在有向图选一无前趋的顶点）在有向图选一无前趋的顶点v，输出；，输出；2）从有向图中删除）从有向图中删除v及以及以v为尾的孤；为尾的孤；3）重复）重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶点；例：、直接全部输出全部顶点或有向图中不存在无前趋顶点；例：V0,V1,V2,V3,V4,V5,V6 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6 五五 查找查找平均查找长度平均查找长度ASL：为确定数据元素在列表

34、中的位置，：为确定数据元素在列表中的位置， 需需和给和给定值进行比较的平均次数定值进行比较的平均次数，称为查找算法在查找成功时的平均，称为查找算法在查找成功时的平均查找长度。对于长度为查找长度。对于长度为n的列表，的列表， 查找成功时的平均查找长度查找成功时的平均查找长度为：为： niiinnCPCPCPCPASL12211Pi为查找第为查找第i个元素的概率，个元素的概率，Ci为找到列表中第为找到列表中第i个数据个数据元素时，已经进行过的关键字比较次数。元素时，已经进行过的关键字比较次数。查找算法的基本运算是关键字之间的比较操作，所以可用平均查找算法的基本运算是关键字之间的比较操作，所以可用平

35、均查找长度来衡量查找算法的性能。查找长度来衡量查找算法的性能。 线性表的查找线性表的查找顺序查找顺序查找-最简单的查找方法顺序查找的基本思想顺序查找的基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，

36、但若采用单链表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。序的。niniiniiininnCnCPASL111) 1(21) 1(11二分二分查找（折半查找）查找（折半查找）1.二分查找的基本思想二分查找的基本思想高效率的查找方法。要求表中元素按关键字有序高效率的查找方法。要求表中元素按关键字有序(升序或降序升序或降序)。假设表中元素为升序排列。假设表中元素为升序排列。二分查找的基本思想是：二分查找的基本思想是：首先将表中间位置记录的关键字与查找关键字比较，首先将表中间位置

37、记录的关键字与查找关键字比较，如果两者相等，则查找成功；如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。成功，或直到子表不存在为止，此时查找不成功。例如，假设给定有序表中关键字为：例如，假设给定有序表中关键字为：05,13,19

38、,21,37,56,64,74,80,88,92，查找，查找K=21的情况：的情况： 05 13 19 21 37 56 64 74 80 88 92 low hig (a) 初初始始情情形形 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 low hig mid (b) 经过一次比较后的情形经过一次比较后的情形 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 (c ) 经过二次比较后的情形经过二次比较后的情形 (arra

39、ymid.key=19) low mid hig 图图 6-1 查找查找 K=21 的示意图的示意图 05 13 19 21 37 56 64 74 80 88 92 (d ) 经过三次比较后的情形经过三次比较后的情形 (arraymid.key=21) mid low hig 图图 6-1 查找查找 K=21 的示意图的示意图 (查找成功查找成功) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 103.二分查找的性能分析 二分查找的过程可以用二叉树来描述。把当前查找区间的二分查找的过程可以用二叉树来描述。把当前查找区间的中点作为根结点，左子区间和右子区

40、间分别作为根的左子中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。得到的二叉树称为二分查找的判定树。例如，给定的关键字序列例如，给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树。的判定树。 0 1 2 3 4 5 6 7 8 9 10 4 0 3 2 7 6 5 8 9 1 0 图图6 -3 具具 有有11 个个 关关 键键 字字 序序 列列 的的 二二 分分 查查 找找 判判 定定 树树 1 查找查找21的过程是从根

41、到结点的过程是从根到结点3的路径，查找的路径，查找85,应在结点应在结点9的左的左子树上子树上,但其左子树为空但其左子树为空,故失败。故失败。所做比较的次数恰为该结点在判定树上的层次数。因此，折所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。半查找成功时，关键字比较次数最多不超过判定树的深度。ASL=(1+2*2+3*4+4*4)/11=3 4 0 3 2 7 6 5 8 9 10 图图 6-3 具具有有 11 个个关关键键字字序序列列的的二二分分查查找找判判定定树树 1 树表的查找树表的查找 二叉排序树查找二叉排序树查找1什么是二叉排序

42、树什么是二叉排序树二叉排序树，它或者是一棵空树，或者是一棵具有如下二叉排序树，它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：特征的非空二叉树：(1)若它的左子树非空，则左子树上所有结点的关键字均若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字；大于等于根结点的关键字； (3)左、右子树本身又都是一棵二叉排序树。左、右子树本身又都是一棵二叉排序树。二叉排序树二叉排序树 526148973CAOZHAODINGCHENWANG(a)

43、二叉排序树示例1(b) 二叉排序树示例2(根据字符 ASC 码的大小 ) 4二叉排序二叉排序 树上的查找树上的查找 （1）二叉排序）二叉排序 树的查找思想树的查找思想若二叉排树为空，则查找若二叉排树为空，则查找 失败，否则，先拿根结点值与失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。结点时

44、，还没有找到待找结点，则查找不成功。（2）二叉排序树查找的算法实现）二叉排序树查找的算法实现NODE * search(int k, NODE *root) /在以root为根的二叉排序树中查找关键值为x的结点 p=root; while(p!= =NULL) if (p-key= =k) return(p); /查找成功 else if (p-keyk) p=p-lch ; /进入左子树查找 else p=p-rch ; /进入右子树查找 return(NULL); 5二叉排序树查找的性能分析二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深在二叉排序树查找中，成

45、功的查找次数不会超过二叉树的深度，而具有度，而具有n个结点的二叉排序树的深度，最好为个结点的二叉排序树的深度，最好为log2n，最坏，最坏为为n。因此，二叉排序树查找的最好时间复杂度为。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可，一般情形下，其时间复杂度大致可看成看成O(log2n)，比顺序查找效率要好，但比二分查找要差。，比顺序查找效率要好，但比二分查找要差。 1. 二叉排序树的插入和生成二叉排序树的插入和生成 已知一个关键字值为已知一个关键字值为key的结点的结点s， 若将其插入到二叉排序若将其插入到

46、二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。树中，只要保证插入后仍符合二叉排序树的定义即可。插入方法：插入方法： 若二叉排序树是空树，则若二叉排序树是空树，则key成为二叉排序树的成为二叉排序树的根；根； 若二叉排序树非空，若二叉排序树非空， 则将则将key与二叉排序树的根进行比与二叉排序树的根进行比较，如果较，如果key的值等于根结点的值，则停止插入；如果的值等于根结点的值，则停止插入；如果key的值的值小于根结点的值，则将小于根结点的值，则将key插入左子树；如果插入左子树；如果key的值大于根结的值大于根结点的值，则将点的值，则将key插入右子树。插入右子树。二叉排序树的建立

47、过程二叉排序树的建立过程 902812245345( g ) 插入902812245345( f ) 插入2812245345( e ) 插入12245345( d) 插入532445( c) 插入2445( b) 插入45( a) 空树顺序输入:45、24、53、12、28、90输入顺序不同所建立的不同二叉排序树 902845125324顺序输入:24、53、12、28、 45、 90排序排序将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。 排序排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序） 归并

48、排序（二路归并排序） 插入排序1直接插入排序基本思想：把基本思想：把n个待排序的元素看成一个有序表和一个无序表，个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有开始时有序表中只包含一个元素，无序表中包含有n-1个元素，个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。的适当位置，使之成为新的有序表。2.折半插入排序例如，n=6，数组R的六个排序码分别为：17，3

49、，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。 0 1 2 3 4 5 初始状态 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14 20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9 第五次插入 (3 9 14 17 20 25) 图 7-1 直接插入排序示例 3. 希尔排序希尔排序希尔排序希尔排序(缩小增量排序缩小增量排序):1959年由年由D.L.Shell提出来的。提出来的。基本思想：先将整个待排元素序列分割成若干个子序列（由基本思想

50、：先将整个待排元素序列分割成若干个子序列（由 “增量增量”确定）分别进行直接插入排序，待整个序列中的元素确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。情况），效率是很高的。例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。 91 67 35 62 29 72 46 57 初

51、始状态， setp=4 29 57 35 62 46 67 91 72 第二趟结果，step=1 29 35 46 57 62 67 72 91 第三趟结果 29 67 35 57 91 72 46 62 第一趟结果,step=2 图 7-2 希尔排序算法的执行过程 交换排序交换排序冒泡排序冒泡排序基本思想:对待排序序列从后向前（从下标较大的元素开始），对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐较小的元素逐渐从后部移向前部，就象水底下的

52、气泡一样逐渐向上冒。渐向上冒。例如，例如，n=6，数组，数组R的六个排序码分别为：的六个排序码分别为：17，3，25，14，20，9。下面用图。下面用图7-3给出冒泡排序算法的执行过程。给出冒泡排序算法的执行过程。 图 7-3 冒泡排序示例 0 1 2 3 4 5 第一趟排序 3 (17 9 25 14 20) 第二趟排序 3 9 (17 14 25 20) 第三趟排序 3 9 14 (17 20 25) 第四趟排序 3 9 14 17 20 25 初始状态 （17 3 25 14 20 9) 快速排序快速排序基本思想是：取待排序序列中的某个元素（一般第一个元素）基本思想是：取待排序序列中的某个元