HASH GAME - Online Skill Game GET 300

　　例：设有一组关键字{ 19, 01, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77 }，采用哈希函数为： H（k）=k mod 13。采用开放地址的线性探测法解决冲突，试在0～18的散列地址空间中，对该关键字序列构造哈希表。 3)折半插入排序性能分析 3. 2-路插入排序 1）基本思想 2-路插入排序是在折半插入排序的基础上改进的，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。 2）具体做法 另设一个和 L.r 同类型的数组d，首先将 L.r[1] 赋值给 d[1] ，并将 d[1] 看成是在排好序的序列中处于中间位置的记录，然后从 L.r 中第 2 个记录起依次插入到d[1] 之前或之后的有序序列中。先将待插入记录的关键字和 d[1] 的关键字进行比较。 若 L.r[i]d[1].key，则将 L.r[i] 插入到 d[1] 之前的有序表中。反之，插入到 d[1] 之后的有序表中。 【初始关键字】 49 38 65 97 76 13 27 49 排序过程中d 的状态如下： i=1: (49) i=2: (49) (38) i=3: (49 65） （38） i=4: (49 65 97） （38） i=5: (49 65 76 97） （38） i=6: (49 65 76 97） （13 38） i=7: (49 65 76 97） （13 27 38） i=8: (49 49 65 76 97） （13 27 38） 3） 2-路插入排序性能分析 二分查找的判定树（中序序列为从小到大排列的有序序列） 由图可得：二分查找的成功平均查找长度为 ASL=(1+2*2+3*4+4)/8=2.625 二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图(b)所示。 由图(a)可得：二叉排序树查找的成功平均查找长度为 ASL=(1+2*2+3*2+4+5*2)/9=3.125 由图(b)可得：平衡二叉树的成功平均查找长度为 ASL=(1+2*2+3*3+4*2)/8=2.75 11 10 1 3 2 4 78 21 3 1 11 2 10 4 78 21 (a) 二叉排序树 (b) 平衡二叉树 线性探查法解决冲突的哈希表如图所示。 由图可得：线性探查法的成功平均查找长度为 ASL=（1+1+2+1+3+2+8+1）/8=2.375 链地址法解决冲突的哈希表如图所示。 由图可得：链地址法的成功平均查找长度为 ASL=(1*6+2*2)/8=1.25 小结 1. 掌握查找的基本概念； 2. 熟练掌握静态查找表的查找算法思想并灵活应用； 3. 熟练掌握动态查找表的特点以及二叉排序树、平衡二叉树的各种操作思想 4. 了解B-、B+树的概念及插入和删除操作； 5. 熟练掌握哈希表的基本概念、哈希函数的构造方法和解决冲突的方法，并能计算平均查找长度。 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 10.1 排序的基本概念 1.排序 设含有n个记录的文件｛R1，R2，…Rn｝，相应的关键字为｛K1，K2，…Kn｝，需确定一种排列P(1),P(2)…P(n)使其相应的关键字满足递增(或递减)关系： KP(1)≤KP(2)≤…KP(n) 或 KP(1)≥KP(2)≥…KP(n) 使上述文件成为一个按其关键字线) ，…RP(n)｝，这种运算就称为排序。 将数据元素的无序序列调整为有序序列的过程。 2.排序算法的稳定性 排序码（Key） 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。 如果待排序的序列中，存在多个具有相同排序码的数据元素，若经过排序这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序发生了改变，则称这种排序算法是不稳定的。 3.内部排序与外部排序 内部排序 指当文件的数据量不太大时，全部信息放内存中处理的排序方法。外部排序 当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序。 4.内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。 内部排序的方法很多，每种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。 排序 简单排序方法，其时间复杂度为O(n2) 先进排序方法，其时间复杂度为O(nlogn) 基数排序，其时间复杂度为O(d·n) 按内部排序过程中所需的工作量来区分： 插入类（直插排序、二分排序、希尔排序） 交换类（冒泡排序、快速排序） 选择类（直选排序、树型排序、堆排序） 归并类（二路归并排序、多路归并排序） 分配类（多关键字排序、基数排序） 按排序过程中依据的原则分 排序 #define MAXSIZE 20 //一个顺序表的最大长度 typedef int KeyType; //定义关键字为整数类型 Typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其他数据项 }RedType; //记录类型 Typedef struct{ RedType r[MAXSIZE+1]; //r[0]用作哨兵单元 int length; //顺序表长度 }SqList; //顺序表类型 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序 1）一趟直接插入排序的基本思想 将记录L.r[i]插入到有序子序列L.r[1..i-1]中，使记录的有序序列从L.r[1..i-1]变为L.r[1..i]。 完成这个“插入”分三步进行： 1．查找L.r[i]在有序子序列L.r [1..i-1]中的插入位置j； 2．将L.r [j..i-1]中的记录后移一个位置； 3．将L.r [i]复制到L.r [j]的位置上。 整个排序过程进行n–1趟插入，即：先将序列中的第1个记录着成一个有序的子序列，然后从第2个记录起逐个插入，直至整个序列变成接关键字非递减有序序列为止。 1.直接插入排序 待排元素序列： [53] 27 36 15 69 42 第一次排序：(27) [27 53] 36 15 69 42 第二次排序：(36) [27 36 53] 15 69 42 第三次排序：(53) [15 27 36 53] 69 42 第四次排序：(69) [15 27 36 53 69] 42 第五次排序: (42) [15 27 36 42 53 69] 直接插入排序示例（插入操作要进行n-1次） 2）直接插入排序算法描述 void InsertionSort ( SqList L ) { // 对记录序列R[1..L.length]作直接插入排序。 for ( i=2; i=L.length; ++i ) { L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } } // InsertSort 3）直接插入排序性能分析 实现排序的基本操作有： （1）“比较” 关键字的大小 （2）“移动”记录 对于直接插入排序： 最好情况“比较”次数：n-1；“移动”次数：2(n-1) 最坏的情况“比较”和“移动”的次数均达到最大值，分别为：(n+2)(n-1)/2；(n+4)(n-1)/2 由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为 O(n2)。 直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。 2.折半插入排序 1）基本思想 考虑到 L.r[1..i-1] 是按关键字有序的有序序列，则可以利用折半查找实现“ L.r[1…i-1]中查找 L.r[i] 的插入位置”如此实现的插入排序为折半插入排序。 (highlow ，查找结束，插入位置为low 或high+1 ) ( 4236 ) ( 4253 ) 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 例：有6个记录，前5个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42 [ 15 27 36 53 69 ] 42 [ 15 27 36 53 69 ] 42 [ 15 27 36 42 53 69 ] ? high ?mid ? low ?low ? high ?mid ?high ?low void BinsertSort(SqList L){ int i,low,high,mid; for(i=2; i= L.length; ++i) { L.r[0]=L.r[i]; low=1; high=i-1; While(low=high) { mid=(low+high)/2; if (L.r[0].key L.r[mid].key) high=mid-1; else low=mid+1; } for( j=i-1; j=low; ? ?j ) L.r[j+1]=L.r[j]; L.r[low]=L.r[0]; } } 2)折半插入排序算法 折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。 折半插入排序是“稳定的” final first 2－路插入排序过程示例： first final final first final first final first final first final first final first 2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。 2-路插入排序中，移动记录的次数约为n2/8 。 当L.r[1]是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 9.3.1 什么是哈希表 哈希表技术的主要目标是提高查找效率。 1. 哈希函数： 根据关键字直接计算出元素所在位置的函数。 例：设哈希函数为：H(K)=K/3+1，则构造关键字序列为 1、2、5、9、11、13、16、21、27 的散列表（哈希表）为： 11 2 27 21 16 13 9 5 1 H(K) 10 9 8 7 6 5 4 3 2 1 序号 2.冲突 两个不同的关键字具有相同的存储位置。 11 2 27 21 16 13 9 5 1 H(K) 10 9 8 7 6 5 4 3 2 1 序号 3.哈希表 根据设定的哈希函数 H(key) 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。 在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。 (1)装填因子α； 装填因子是指哈希表中己存入的元素个数 n 与哈希表的大小 m 的比值，即α=n/m（α=1）。 α越小，发生冲突的可能性越小，反之，发生冲突的可能性就越大。但是，α太小又会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。 (2)所构造的哈希函数; (3)解决冲突的方法。 ① 构造好的哈希函数，使冲突尽可能的少 ② 设计有效的解决冲突的方法 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 9.3.2 哈希函数的构造方法 例：关键码集合为{ 100，300，500，700，800，900 }， 选取哈希函数为 Hash(key)=key/100，则存储结构（哈希表）如下： 1.直接定址法 取关键字或关键字的某个线性函数值为散列地址，即（K）=K 或 H（K）=a * K + b（其中a、b为常数）。 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100 优点：以关键码 key 的某个线性函数值为哈希地址，不会产生冲突。 缺点：要占用连续地址空间，空间效率低。 2.除后余数法 取关键字被不大于散列表表长 m 的数 p 除后所得的余数为哈希函数。即 H（K）=K mod p （p≤m） 经验得知：一般可选p为质数或不包含小于20的质因素的合数。 3.平方取中法 取关键字平方后的中间几位为哈希函数。因为中间几位与数据的每一位都相关。 例：2589的平方值为6702921，可以取中间的029为地址。 选用关键字的某几位组合成哈希地址。 选用原则应当是：各种符号在该位上出现的频率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 7 3 4 8 2 6 9 6 3 4 8 5 2 7 0 3 4 8 6 3 0 5 3 4 9 8 0 5 8 3 4 7 9 6 7 1 3 4 7 3 9 1 9 例：有一组（例如80个）关键码，其样式如下： 讨论： ① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。 位号：① ② ③ ④ ⑤ ⑥ ⑦ ② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。 4.数字分析法 5.折叠法 是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。 适用于：每一位上各符号出现概率大致相同的情况。 移位法：将各部分的最后一位对齐相加。 间界叠加法：从一端向另一端沿分割界来回折叠后，最后一位对齐相加。 例：元 移位法： 427＋518＋96=1041 间界叠加法： 427 518 96— 724+518+69 =1311 6. 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random (key)，其中random为随机函数。 通常，当关键字长度不等时采用此法构造哈希函数较恰当。 实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素： (1)计算哈希函数所需时间(包括硬件指令的因素)； (2)关键字的长度； (3)哈希表的大小； (4)关键字的分布情况； (5)记录的查找频率。 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 9.3.3 处理冲突的方法 1.开放地址法 开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。 （1）线性探测法 设散列函数 H（K）=K mod m （m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为： Hi=(H(K)+di) mod m (di=1,2,…,m-1) 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1 2 3 4 5 6 7 8 9 10 7 47 29 11 16 92 22 8 3 线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素； 线性探测法的缺点：可能使第i 个哈希地址的同义词存入第i+1 个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 可采用二次探测法或伪随机探测法，以改善“堆积”问题。 1.开放地址法 （2）二次探测法 二次探测法对应的探查地址序列的计算公式为： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2)。 0 1 2 3 4 5 6 7 8 9 10 8 29 7 16 92 47 3 22 11 若di＝伪随机序列，就称为伪随机探测法 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2) 2.链地址法 优点：插入、删除方便。 缺点：占用存储空间多。 基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设 m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 例：设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，建表。 0 1 2 3 4 5 6 7 8 9 10 22 11 89 3 47 37 92 29 7 16 50 8 10 ? ? ? ? ? ? ? ? ? ? ? 有冲突的元素可以插在表尾,也可以插在表头。 3.再哈希法 Hi= RHi(key) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。 4.建立一个公共溢出区 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 9.3.4 哈希表的查找及其分析 散列表的目的主要是用于快速查找。 在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。 解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为： di=(H(k)+j) mod 19; j=1,2,……,18 其计算函数如下： H(19)=19 mod 13=6 H(01)=01 mod 13=1 H(23)=23 mod 13=10 H(14)=14 mod 13=1 (冲突) H(14)=(1+1) mod 19=2 H(55)=55 mod 13=3 H(20)=20 mod 13=7 H(84)=84 mod 13=6 (冲突) H(84)=(6+1) mod 19=7 (冲突) H(84)=(6+2) mod 19=8 H(27)=27 mod 13=1（冲突） H(27)=(1+1) mod 19=2 (冲突) H(27)=(1+2) mod 19=3 (冲突) H(27)=(1+3) mod 19=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 {19,01,23,14,55,20,84,27,68,11,10,77} 01 23 14 55 20 84 27 77 10 11 68 … … 哈希查找的性能分析 哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。 1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子α的值和该处理方法有关。 这时的成功的平均查找长度为： ASL= (1+1/(1-α))/2 2.链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。 平均查找长度： ASL=1+α/2 例：给定关键字序列{11，78，10，1，3，2，4，21}，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。设哈希函数为： H(k)=k mod 11，哈希表表长m=11。 顺序查找的顺序表（一维数组） 由图可得：顺序查找的成功平均查找长度为 ASL=(1+2+3+4+5+6+7+8)/8=4.5