数据结构复习ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第9章 查找,基本概念,查找 内部查找外部查找,关键字次关键字,稳定查找不稳定查找,静态查找表,动态查找表,查找成功查找失败,第9章 查找基本概念,1,一.静态查找表,顺序表的查找,算法实现，时间复杂度分析（成功、包括失败情况）,2.有序表的查找,折半查找的适用条件，算法实现，时间复杂度分析,3.索引顺序表的查找,分块有序的概念，时间复杂度分析,一.静态查找表,2,二.动态查找表,二叉排序树,算法思想，时间复杂度分析,二叉排序树的蜕化为单支树,2.平衡二叉树（AVL树）,平衡因子，平衡二叉树的构造过程,3.B_树,m阶B_树的概念，结点结构，插入删除的算法思想,二.动态查找表,3,三.哈希查找,哈希函数,2.处理冲突的方法,3.哈希查找的算法思想,三.哈希查找,4,Exercise9-1,已知一个长度为 15 的线性表，其关键字序列为 190，381，12，40，410，394，540，760，35，476，800，146，9，445，600,按各元素的顺序构造一棵二叉排序树,若各元素的查找概率相等，给出该二叉排序树的平均查找长度,Exercise9-1,5,Exercise9-2,已知关键字序列为 45，24，70，7，30，53，90，3，12，26，37，50，61，85，100,试按关键字顺序构造一棵 平衡二叉树，要求画出每个具体步骤,Exercise9-2,6,Exercise9-4,设哈希表的地址范围为 017，哈希函数为：,H(k)=k MOD 16,k 为关键字，用线性探测再散列法处理冲突，输入关键字序列为：,10，24，32，17，31，30，46，47，40，63，49,画出哈希表的示意图,若查找关键字 63，需要依次与哪些关键字比较,Exercise9-4,7,第10章 内部排序,时间复杂度比较,Insertion,O(n,2,),Bubble,O(n,2,),Quick,O(n,log,n),Most of the time!,Heap,O(n,log,n),Guaranteed,Merging,O(n log n),Guaranteed,Radix,O(d(n+rd),平均时间性能而言，快速排序最佳。,第10章 内部排序,8,空间复杂度比较,Insertion,O(1),Bubble,O(1),Quick,O(,log,n),Heap,O(1),Merging,O(n),Radix,O(rd),数据结构复习ppt课件,9,稳定性比较,Insertion,简单稳定，希尔不稳定,Bubble,稳定,Quick,不稳定,Heap,不稳定,Merging,稳定,Radix,稳定,数据结构复习ppt课件,10,1.插入排序：,直接插入排序法应掌握算法(包括算法的实现),希尔排序的算法思想，要能写出每趟排序的结果。,希尔排序中增量序列定义的要求,希尔排序是不稳定的(希尔：排得希里糊涂尔：),1.插入排序：,11,2.交换排序,交换排序的基本思想(两两比较反即换)。,包括冒泡排序和快速排序。,冒泡排序的算法应掌握。冒泡排序是稳定的。,快速排序法应掌握算法思想(分治)，针对给定的实例，写出快速排序的排序过程。,快速排序的平均时间复杂度为O(nlgn)。,它是不稳定的(一快就不稳),2.交换排序,12,3.选择排序,基本思想就是“每趟选一排在后”。,直接选择排序的算法思想和实现，能写出其各趟排序的过程。,直接选择排序是不稳定的(直接“选举”也是“不稳定”的，所以我们要进行间接选举),堆排序。堆的定义(大根堆就是双亲比孩子大，小根堆就是双亲比孩子小)。请判断一个序列是不是堆(大顶堆或小顶堆)。,建堆和堆排序的图示过程。堆排序是不稳定的(你想，一堆鸡蛋能稳定吗),3.选择排序,13,4.归并排序,算法思想和归并排序过程的表示,顺序表和链表上一趟归并排序的实现,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,7,链式存储指针如何变化？,4.归并排序0 1,14,5.基数排序,将,最低位优先法,用于,单关键字,的情况。,基数排序的分配和收集方法(图示)。,基数排序中，是稳定的。,排序算法的选择策略,各种内部排序方法的比较和选择比如在几种排序法中选择稳定的排序法、选择速度快的排序法、选择稳定且速度快的排序法，对于给定的关键字序列，选择最好的排序法等。,5.基数排序,15,Exercise10-1,若待排序的关键字序列为,25，73，12，80，116，,25,1.请按如下两种增量值分别给出希尔排序的过程示意图,3，2，1,5，2，1,2.给出快速排序的过程示意图,3.给出堆排序的过程示意图,4.给出2路归并排序的过程示意图,5.给出基数排序的过程示意图,Exercise10-1,16,