软件技术基础-chapter12

《软件技术基础-chapter12》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011-5-31内容提要一．上节课内容回顾软件技术基础二．选择排序与堆排序三．归并排序与基数排序第12讲排序技术和二叉排序树四．二叉排序树及其查找主讲教师：张帆©ZhangFan,March,2011CollegeofInformationScience&Technology,BeijingUniversityofChemicalTechnology一.上节课内容回顾一.上节课内容回顾1.1线性哈希表1.1线性哈希表•设计思路•分析有冲突时就去寻找下一个空的哈希地址，只要哈希表优点：只要哈希表未被填满

2、，保证能找到一个空地足够大，空的哈希地址总能找到，并将数据元素存入。址单元存放有冲突的元素；。缺点：可能使第i个哈希地址的同义词存入第i+1个•实现思路哈希地址，这样本应存入第i+1个哈希地址的Hi=(Hash(key)+di)modm(1≤i

3、“堆积”问题。含义：一旦冲突，就找附近（下一个）空地址存入。一.上节课内容回顾一.上节课内容回顾1.2随机哈希表1.3溢出哈希表•设计思路•设计思路有冲突时就去寻找下一个空的哈希地址，只要哈希表除设立哈希基本表外，另设立一个溢出向量表。所有足够大，空的哈希地址总能找到，并将数据元素存入。关键字和基本表中关键字为同义词的记录，不管它们由哈。希函数得到的地址是什么，一旦发生冲突，都填入溢出表。•实现思路•实现思路H=(Hash(key)+d)modm(1≤i

4、希表长度d为伪随机序列i含义：一旦冲突，就找随机空地址存入。12011-5-31一.上节课内容回顾一.上节课内容回顾1.4拉链哈希表1.4拉链哈希表•基本思想例：设{47,7,29,11,16,92,22,02211将具有相同哈希地址的记录链成一个单链表，m个哈希8,3,50,37,89}的哈希函数为：189地址就设m个单链表，然后用一个数组将m个单链表的表头Hash(key)=keymod11，2指针存储起来，形成一个动态的结构。用拉链法处理冲突，则建表3347如右图所示。43792•具体实现516拉

5、链哈希表由哈希表及表外结点组成。哈希表中记录的注：有冲突的元素可以插650在表尾,也可以插在表头7297是指针；表外结点记录关键字及链接各结点的指针。8891010一.上节课内容回顾一.上节课内容回顾1.5排序概述1.5排序概述1.什么是排序？4.什么叫内部排序？什么叫外部排序？将一组杂乱无章的数据按一定的规律顺次排列起——若待排序记录都在内存中，称为内部排序；来。——若待排序记录一部分在内存，一部分在外存，则存放在数据表中按关键字排序称为外部排序。2.排序的目的是什么？——便于查找！注：外部排序时，要

6、将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。3.排序算法的好坏如何衡量？5.待排序记录在内存中怎样存储和处理？•时间效率——排序速度（即排序所花费的全部比较次数）①顺序排序——排序时直接移动记录；•空间效率——占内存辅助空间的大小②链表排序——排序时只移动指针；③地址排序——排序时先移动地址，最后再移动记录。一.上节课内容回顾一.上节课内容回顾1.5排序概述1.6交换排序6.内部排序的算法有哪些？•基本思想——按排序的规则不同，可分为5类：两两比较待排序记录的关键码，如果

7、发生逆序（即排列•插入排序(希尔排序)顺序与排序后的次序正好相反），则交换之，直到所有记录•交换排序（冒泡排序、快速排序）都排好序为止。•选择排序(堆排序）•归并排序•基数排序交换排序的主要算法有：——按排序算法的时间复杂度不同，可分为3类：1)冒泡排序•简单的排序算法：时间效率低，O(n2)•先进的排序算法:时间效率高，O(nlog2n)2)快速排序•基数排序算算法：时间效率高，O(d×n)d＝关键字的位数(长度)22011-5-31一.上节课内容回顾一.上节课内容回顾1.7冒泡排序1.7冒泡排序•基

8、本思想•算法分析每趟不断将记录两两比较，并按“前小后大”（或“前时间效率：O（n2)—因为要考虑最坏情况大后小”）规则交换。空间效率：O（1）—只在交换时用到一个缓冲单元•优点详细分析：每趟结束时，不仅能挤出一个最大值到最后面位置，还•最好情况：初始排列已经有序，只执行一趟起泡，做n-1能同时部分理顺其他元素；一旦下趟没有交换发生，还可以次关键码比较，不移动对象。提前结束排序。•最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟•适用范