MSE数据结构.ppt

《MSE数据结构.ppt》由会员分享，可在线阅读，更多相关《MSE数据结构.ppt（145页珍藏版）》请在课桌文档上搜索。

1、MSE考试辅导数据结构（精简版）,课程安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序小结,试题结构,考试时间90分钟，满分75分。名词解释（20）问答和编程题（55）时间复杂度Hash二叉树二叉查找树队列,课程安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序,数据结构，数据类型,数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合最常见的四种基本数据结构包括集合线性结构线性表（数组、链表），栈，队列树形结构树图状结构图,算法复杂度基本概念,算法复杂度(algorithmic complexity):算法消耗的时间或(内存)空间相应分为时

2、间复杂度和空间复杂度两个部分,常见基本算法的时间复杂度分析,常见的一些增长率：常数增长率O（1）线形增长率O（n）二次增长率/平方增长率O（n2）对数增长率O（logN）指数增长率O（nm）关系：常数 对数 线形 平方 指数O(1)O(logN)O(n)O(NlogN)O(n2),常见题型,已知算法求时间复杂度给出代码求时间（空间）复杂度比较算法的快慢,常见算法的复杂度小结,O（1）：链表判断为空，双头链表的合并出栈、入栈，进出队列哈希(hash)查找（理想情况）O（n）：链表查找、插入、删除，双向链表查找、插入、删除，链表的合并顺序查找法,常见算法的复杂度小结,O（logn）：二分查找法BS

3、T树的查找、插入、删除O（nlogn）：快速排序、归并排序、堆排序O（n2）：插入排序、选择排序、冒泡排序,例题,堆排序的时间复杂度是_A O(1)B O(n)C O(logN)D O(NlogN)答案：D,例题,假设数组已经排好序，则下列代码的复杂度是？int isIn(int a,int n,int k)for(int j=0;j k)j+;else return 0;答案：O(n),例题,给出下列代码的复杂度：void bubble_sort(int a,int size)for(int i=1;iaj+1)ajaj+1;答案：O(n2),例题,对于有序数组而言，顺序查找和两分查找中更快

4、。答案：两分查找,课程安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序小结,线性表基本概念和性质,线性表是n个数据元素的有限序列常见线性表包括数组、链表、栈、队列等,环形链表,环形链表又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点,栈的基本概念和性质,栈：栈是限定仅在表尾进行插入和删除操作的线性表后进先出特性（LIFO）栈顶、栈底、出栈、入栈,栈的基本概念和性质,设计递归问题的非递归算法一般需要用到栈机制三个数a、b、c进栈，不可能出现c、a、b顺序出栈,例题,设有一个栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元

5、素的出栈顺序为S2,S3,S4,S6,S5,S1，则栈的容量至少应为多少？答案：3,例题,若某栈的输入序列为a、b、c，则所有可能的出栈序列有_种，所有不可能的出栈序列有_种。答案：5，1,队列的基本概念和性质,队列：队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表先进先出特性（FIFO）队尾、队头、入队、出队,例题,在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是，队尾元素是。答案：c，d,双向队列,双向队列：亦称双端队列（Deque）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。,课程

6、安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序小结,树,大纲描述：树的基本概念和术语；树的前序、中序、后序、叶子序遍历；二叉树及其性质；普通树与二叉树的转换；完全树的数组形式存储；空树的表示；树的应用，Huffman树。,树的基本概念和术语,树：是n（n0）个结点的有限集在任意一棵非空树中：有且仅有一个特定的称为根的结点当n1时，其余结点可以分为m（m0）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树树属于层次结构数据结构,树的基本概念和术语,树的结点包括一个数据元素及若干指向其子树的分支结点存放数据的部分称之为结点的标签(label),树的基本概念和

7、术语,结点的子树的根称之为该结点的孩子结点(child/children)；该结点称为孩子的双亲结点(parent)。拥有同一个双亲结点的孩子结点之间互称兄弟结点(sibling),树的基本概念和术语,如果存在树中的一个结点序列K1,K2Kj,使得结点Ki是结点Ki+1的父结点(1i j),则称该结点序列是树中从结点K1到结点Kj的一个路径(path)或者道路。该路径的长度为j-1,即该路径所经过的边(edge)的数目(或者说结点数目减1)。树中任一结点有一到其自身的长度为0的路径。,树的基本概念和术语,我们通常把树中的路径称为树枝,把路径长度称为树枝长度。如果树中存在一条从结点K到结点M的路

8、径，则称K为M的祖先结点(ancestor),M是K的子孙结点或者后裔结点(descendent)任一结点都是自身的祖先和后裔结点,树的基本概念和术语,一个结点所拥有的子树个数称为结点的度(degree)或次数度为0的结点称之为叶子(leaf),或者外部结点(external node),或者终端结点(terminal node)度不为0的结点称之为分支结点,或者内部结点(internal node),或者非终端结点(non-terminal node)树的度是树内各结点的度的最大值,如果一棵树的度为k;也称这棵树为k次树(k-ary tree),树的基本概念和术语,结点n的层次(level)

9、从根开始定义，根为第一层，根的孩子为第二层；若某结点在第l层，其孩子在l1层。树的深度或高度树中结点的最大层次称为树的深度（depth）或高度（height）,例题,例题,列出如上图所示树的所有叶子结点答案：K,L,F,G,M,I,J列出如上图所示树的所有分支结点答案：A,B,C,D,E,H树A为几次树？子树B呢？答案：3，2前页图所示树的高度为多少？答案：4,二叉树及其性质,二叉树（Binary Tree）另一种树形结构，特点是每个结点至多只有二棵子树，且子树有左右之分，其次序不能任意颠倒二叉树可能的五种基本形态,二叉树及其性质,在二叉树的第i层上至多有2i1个结点（i1）,例题,一棵二叉树

10、第五层上至多有多少个结点？至少多少？答案：16，1,二叉树及其性质,深度为k的二叉树至多有2k1个结点（k1）,例题,一棵深度为5的二叉树至多有多少个结点？至少多少？答案：31，5,二叉树及其性质,对于任何二叉树,如果叶子节点数为n0,度为2的节点数为n2,则n0=n2+1,例题,若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_。答案：9,例题,若二叉树中度为2的结点有15个，度为1的结点有10个，共有多少个结点？答案：41,二叉树及其性质,满二叉树：一棵深度为k且有2k1个结点的二叉树可以对满二叉树的结点进行连续编号，约定编号从根开始，自上而下，自左而右。完全二叉树：深度为k的

11、，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。,二叉树及其性质,完全二叉树特点：叶子结点只可能出现在层次最大的两层上对任一结点，若其右分支下子孙的最大层次为l，其左下分支的子孙的最大层次必为l或者l1。深度为k的完全二叉树第k层最少1个结点，最多2k-1-1个结点；整棵树最少2k-1个结点，最多2k-2个结点,例题,若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。答案：25-1+334,二叉树及其性质,具有n个结点的完全二叉树的深度为log2n+1,例题,具有2000个结点的二叉树，其深度至少为_。答案：1

12、1,完全树的数组形式存储,完全树的数组形式存储算法将其编号为i的结点元素存储在一维数组下标为i1的分量中,例题,已知数组20,30,19,87,30,40,55表示一棵完全二叉树，请画出该树。,练习答案,树的遍历,树的遍历 按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅且一次二叉树的遍历可分为前序、中序、后序、层次序等,树的遍历,二叉树的遍历前序、中序、后序定义层次序：从上而下，从左至右常见问题已知树写遍历结果已知遍历结果画树依据：二叉树的前序和中序遍历可以唯一确定一棵二叉树思路：前序定根，中序定左右,例题,写出左图所示二叉树的前序、中序、后序、层次序遍历结果,例题答案,前序：ABD

13、CEFG中序：DBAECFG后序：DBEGFCA层次序：ABCDEFG,例题,假设一棵二叉树的前序遍历为EBADCHGFIKJ，中序遍历为ABCDEFGHIJK，请画出该树。,例题答案,Huffman树,Huffman树：又称最优树，是一类带权路径长度最短的树基本概念：树的路径长度：从根到每一结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做WPL。,Huffman树,基本概念：假设有n个权值wi，试构造一棵有n个叶子结点的二叉树，每个叶子的结点带权为wi，则其中WPL最小的二叉树称为最优二叉树或

14、赫夫曼树,Huffman树的构造,一、对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。,Huffman编码,从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1。,课程安排,课程介绍算法分析

15、与抽象数据类型 数组、链表、栈和队列 树查找排序小结,查找,大纲描述：查找的基本概念；Hash查找法，常见的Hash函数；解决冲突的方法；范围查询。,查找的基本概念,查找表(search table)：具有同一类型数据元素(经常称为记录)的集合查找表的基本操作有：查找某个“特定”记录是否在表中查找到后取出某个“特定”记录的各个数据项向表中插入记录从表中删除记录,查找的基本概念,静态查找表(static search table)：仅用于查询的查找表。动态查找表(dynamic search table):若在查找过程中需同时插入表中不存在的记录;或者需要删除记录,则称之为动态查找表。关键字/键

16、值(key)：记录某个数据项的值,用其可以标示该记录当记录只有一个数据项时,其关键字即为该记录的值如果一个key可以唯一标示一个就,则称之为主关键字(primary key),否则称之为次关键字(secondary key),查找的基本概念,查找(search)：在一个查找表中找出具有“特定”键值的那些记录所谓查找成功是指在查找表中找到了满足条件的记录,此时一般会返回找到的记录,或者返回记录的位置信息,或者仅仅返回找到(true)否则称为查找失败,此时一般返回空指针,或特殊值,或者仅仅返回没有找到(false),有时也会就此插入这个元素,Hash查找法，常见的Hash函数,哈希（Hash）函数

17、：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。这个对应关系f为哈希函数。按这个思想建立的表为哈希表。哈希函数的设定可以很灵活，只要使得任何关键字的哈希函数值都落在表长允许范围之内即可。,Hash查找法，常见的Hash函数,除留余数法选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即：H(key)=key%P方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。缺点:整数相除速度较慢,Hash查找法，常见的Hash函数,如:m=8，16，32，64，1

18、28，256，512，1024P=7，13，31，61，127，251，503，1019,解决冲突的方法,对不同的关键字可能得到同一哈希地址，这种现象称冲突。具有相同函数值的关键字对该哈希函数来说称作同义词。在一般情况下，冲突只能尽可能的少，而不能完全避免。,解决冲突的方法,基本思想当冲突发生时，使用某种方法在散列表中形成一个探查序列(也称之为链)，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。Hj=(H(key)+dj)MOD m 1 j m-1;m为hash表长度dj为增量数列,各种方法的不同就区别在取不同的增量数列上,解决冲突的方法,常用的增量数列

19、:线性探测法二次探测法伪随机法再哈希法/二次哈希法桶式散列法,解决冲突的方法,线性探测法取dj=1,2,m-1将散列表看成是一个环形表。若地址为d（即H(key)=d）的单元发生冲突，则依次探查下述地址单元：d+1，d+2，.，m-1，0，1，.，d-1,直到找到一个空单元或查找到关键字为key的结点为止。若沿着该探查序列查找一遍之后，又回到了地址d，则无论是做插入操作还是做查找操作，都意味着失败。,例题,若待散列的序列为(18,25,63,50,42,32,9)，哈希函数为H(key)=key MOD 9，哈希表长度为9，与18发生冲突的元素有_个答案：2,例题,已知一组关键字为（26，36

20、，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的散列表，假设利用除余法构造散列函数。,例题答案,为了减少冲突，通常令装填因子1，在此我们取=0.75。因为n=11，所以散列表长度m=high(n/)=15；对于除余法，选P=13（小于15的最大素数），即散列函数为：H(key)=key%13。按顺序插入各个结点：26:H(26)=26/13=0 36:.=10，41:.=2，38:.=12，44:.=5插入15时，其散列地址为2，由于2已被关键字为41的元素占用，故需进行探查。按顺序探查法，显然3为开放地址，故可将其放在3单元。类似的，68和12可

21、分别放在4和1单元中,25x1,25,25x9,25x8,25x7,25x6,25x5,25x4,25x3,25x2,11,38,36,25,6,44,51,68,15,41,12,26,Final,51x1,51,51x6,51x5,51x4,51x3,51x2,10,6,6x1,9,12x1,12,12x2,8,68,68x1,7,15,15x1,6,44,5,38,4,41,3,36,2,26,1,12,11,10,9,8,7,6,5,4,3,2,1,0,pos,BST树定义，性质，实现,二叉排序树(Binary Sorted Tree)定义又称二叉查找树；或者是一棵空树；或者是具有下列

22、性质的二叉树：如果左子树非空,则左子树中所有节点的键值均小于它的根结点的值；如果右子树非空,则右子树中所有节点的键值均大于它的根结点的值；它的左右子树也都是二叉排序树。,BST树定义，性质，实现,二叉排序树性质 如果对二叉排序树进行中序遍历,则得到一个从小到大排好序的列表,所以可以得到一种简单的排序方法叫做“树排序”(treesort)。我们也可以根据这个性质定义二叉排序树为:如果一棵树按中序遍历为排好序的,则这棵树是二叉排序树。,BST树查找，插入，删除算法,BST树查找，插入，删除算法画图算法,例题,已知BST树如左，请画出插入16，再删除36之后的BST树,例题答案,例题,试求按关键字序

23、列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树,例题答案,练习,假设结点序列F（60，30，90，50，120，70，40，80），试用BST的插入算法，用F中的结点依次进行插入，画出由F中结点所构成的BST树T1；再用删除算法，依次删除40，70，60，画出删除后的BST树T2。,练习答案,课程安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序小结,排序,大纲描述：排序基本概念；插入排序，希尔排序，选择排序，快速排序，归并排序，基数排序等排序算法基本思想；算法代码及基本的时间复杂度分析；堆的定义，堆的生成。,排序基本概念,排序(Sorting)：重排一个记录

24、序列,使之成为按关键字有序常见排序可分为以下五类：插入排序（简单插入排序）交换排序（冒泡排序、快速排序）选择排序（简单选择排序、堆排序）归并排序计数排序（多关键字排序）,插入排序,基本算法：void insert_sort(int array)for(int j=1;j0),插入排序,46 26 22 68 48 42 36 84 66 22*26 46 22 68 48 42 36 84 66 22*22 26 46 68 48 42 36 84 66 22*22 26 46 68 48 42 36 84 66 22*22 26 46 48 68 42 36 84 66 22*22 26 4

25、2 46 48 68 36 84 66 22*22 26 36 42 46 48 68 84 66 22*22 26 36 42 46 48 68 84 66 22*22 26 36 42 46 48 66 68 84 22*22 22*26 36 42 46 48 66 68 84,冒泡排序,冒泡排序,也称起泡排序,是最简单的基于交换的排序方法基本思想:从上往下对相邻节点进行比较,使键值较大的节点向下沉,键值较小节点往上浮.对于n个记录做n-1次循环(如果其中某次循环没有发生节点交换,算法结束),冒泡排序,void bubble_sort(int array)boolean change=t

26、ruefor(int k=array.length-1;k0,快速排序,就平均时间而言，快速排序是目前被认为最好的一种内部排序方法,由C.A.R.Hoare发明分治法(divide and conquer)思想的体现Unix系统函数库所提供的标准排序方法C标准函数库中的排序方法直接就命名为qsort(),快速排序,基本思想:是对冒泡排序的一种改进选取一个轴值,然后根据此轴值通过一趟排序对记录集进行一次分割,然后对分割后产生的两个记录子集分别进行快速排序,快速排序,快速排序,49,38,65,97,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,1

27、3,49,27,38,97,76,13,65,49,27,38,13,97,76,65,49,27,38,13,76,97,65,49,27,38,13,49,76,97,65,49,49,temp,例题,写出对于结点序列（46，26，22，68，48，42，36，84，66）进行第一次分割后序列的情况，注意列出步骤的每一步。,例题答案,【】26，22，68，48，42，36，84，6636，26，22，68，48，42，【】，84，6636，26，22，【】，48，42，68，84，6636，26，22，42，48，【】，68，84，6636，26，22，42，【】，48，68，84，663

28、6，26，22，42，46，48，68，84，66,练习,已知序列（2,8,7,1,3,5,6,4），如果选用4作为枢轴，那么进行一次分割后序列表现是怎样的？答案：2，3，1，4，7，5，6，8,练习,对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是_。答案：13，38，27，49，76，97，65，50,简单选择排序示例,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,

29、27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,例题,对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是答案：简单选择排序,练习,若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序列的

30、状态是_。,练习答案,13，38，65，97，76，49，27，5013，27，65，97，76，49，38，5013，27，38，97，76，49，65，50,堆的定义，堆的生成,1964年威洛姆斯(J.willioms)提出堆排序属于树型选择排序，仅需要一个记录大小的辅助空间，每个待排序记录仅占有一个存储空间。,堆的定义，堆的生成,定义：n个元素的序列k1,k2,kn当且仅当满足下列关系时，称之为堆：kik2i且kik2i+1或kik2i且kik2i+1等价的树的定义：如果一棵完全二叉树,其中每个节点的键值不小于(或者不大于)其子树的所有节点的键值,则称这棵二叉树为(最大值/最小值)堆(m

31、ax/min heap),堆的定义，堆的生成,堆的性质:堆中节点的(层次)次序不是很有关系,很容易把不是完全树的堆调整为是完全树的堆若序列是堆，则堆顶元素必为序列中n个元素的最值。一般按层次序采用数组方式存储设节点数为n若2i+1=a2i+1(ai=a2i+2(ai=a2i+2),堆的定义，堆的生成,10,15,56,25,30,70,10,15,56,25,30,70,小根堆示例,堆的定义，堆的生成,70,56,30,25,15,10,70,56,30,25,15,10,大根堆示例,堆的定义，堆的生成,堆排序：若在输出堆顶的最值之后，使得剩余n1个元素的序列重又建成一个堆，则得到n个元素中的

32、次小值，如此反腐执行，便能得到一个有序序列，这个过程称为堆排序。,堆的定义，堆的生成,堆排序基本思想:将记录集调整为堆输出堆顶的最值记录将剩下记录重新调整为一个堆重复2,3直至所有记录被输出堆排序关键问题:如何将一个记录集调整为堆?,堆的定义，堆的生成,堆生成/调整算法:从树的最后一个非叶子节点开始,也就是从数组的第length/2-1个元素开始调整每次比较当前节点和及其左右子节点,取三者中最大者作为根按逆层次序考察,直至根节点,也就是数组的第一个元素,堆的定义，堆的生成,void HeapifyDown(Node node)int x=label(node);Node maxChild;wh

33、ile(true)if(left(node)=LENGTH)break;if(right(node)=LENGTH)maxChild=left(node);else maxChild=label(left(node)label(right(node)?left(node):right(node);if(xlabel(maxChild)break;elseswap(node,maxChild);,堆的定义，堆的生成,void Heapify(Node tree)for(int j=tree.length/2-1;j=0;j-)HeapifyDown(treej);,堆的定义，堆的生成,堆排序算法

34、：先将初始堆调整成一个最大值堆；然后将最值与最后一个元素对调，将去除最后一个元素后剩余的堆重新调整为一个最大值堆；继续以上过程直至最后一个元素。,堆的定义，堆的生成,void heap_sort(Node tree)Heapify(tree);for(int j=tree.length-1;j0;j-)swap(tree0,treej);for(int k=(j+1)/2-1;j=0;j-)HeapifyDown(treek);,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,堆的定义，堆的生成,13,88,42,23,2

35、4,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,堆的定义，堆的生成,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,堆的定义，堆的生成,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后,堆的定义，堆的生成,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,堆的定义，堆的生成,（f）第三趟排序之后,05,24,16,23,13,42,88,9

36、1,05,24,16,23,13,42,88,91,堆的定义，堆的生成,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,堆的定义，堆的生成,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,堆的定义，堆的生成,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,堆的定义，堆的生成,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,

37、88,91,堆的定义，堆的生成,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,堆的定义，堆的生成,（l）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,堆的定义，堆的生成,（m）重建的堆R1到R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,堆的定义，堆的生成,（n）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,堆的定义，堆的生成,堆的定义

38、，堆的生成,性能分析:比较,移动:最优,最差,平均均为O(nlogn)稳定性:不稳定,堆的定义，堆的生成,优点:对于最坏情况,复杂度也是O(nlogn)只占有n个记录的空间,空间复杂度为O(1)合适于外部排序缺点:对于记录数较少时不合适,例题,以下序列中不符合堆定义的是_。A(102，87，100，79，82，62，84，42，22，12，68)B(102，100，87，84，82，79，68，62，42，22，12)C(12，22，42，62，68，79，82，84，87，100，102)D(102，87，42，79，82，62，68，100，84，12，22)答案：D,例题,给定序列100

39、,86,48,73,35,39,42,57,66,21,按堆结构的定义,则它一定是堆。答案：最大值,练习,已知序列88，91，42，23，24，16，5，13，用堆排序方法进行排序，求排序过程中堆的状况。,练习答案,91，88，42，23，24，16，5，1313，88，42，23，24，16，5，9188，24，42，23，13，16，5，915，24，42，23，13，16，88，9142，24，16，23，13，5，88，915，24，16，23，13，42，88，9124，23，16，5，13，42，88，9113，23，16，5，24，42，88，91,练习答案,23，13，16，5

40、，24，42，88，915，13，16，23，24，42，88，9116，13，5，23，24，42，88，915，13，16，23，24，42，88，9113，5，16，23，24，42，88，915，13，16，23，24，42，88，91,练习,序列（4,1,10,14,16,9,3,2,8,7）是否是一个最大值堆？如果不是请将其调整为一个最大值堆，并且使用堆排序算法进行排序，写出过程中每步序列的变化状况。,归并排序,Jon von Neumann于1945年提出彻底的分治法,完全的等分(相对于快速排序而言)适用于巨量数据的排序Java类库所提供的标准排序方法所谓归并是指将两个或两个以上

41、有序表合并为一个有序表的过程,归并排序,(25)(57)(48)(37)(12)(92)(86),(25 57)(37 48)(12 92)(86),(25 37 48 57)(12 86 92),(12 25 37 48 57 86 92),课程安排,课程介绍算法分析与抽象数据类型 数组、链表、栈和队列 树查找排序小结,例题,已知非空二叉树结点的构造为 date|left|right，指向树根结点的指针为root，求统计树所有内部结点个数的算法。,例题答案,int Count(BinaryTree*root)/*使用一个辅助队列，假设进队函数为void in(BinaryTree*Node),出队函数为BinaryTree*out()判断队列空函数为int isempty()*/BinaryTree*node;int count;in(root);while(!isempty()node=out();if(node-left!=null)in(node-left);if(node-right!=null)in(node-right);if(node-left!=null|node-right!=null)count+;return count;,Thank You!Good Luck!,