数据结构第16讲.ppt

《数据结构第16讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构第十六讲复习第十五讲散列查找通过直接对关键字进行函数运算得到元素存储地址散列查找的关键让所有数据元素计算得到的地址均匀分布在存储空间冲突的处理线型探测二次探测再哈希链地址哈希函数直接定址平方取中除留余数折叠等等要求掌握构造哈希表的方法掌握哈希表查找的方法排序稳定性问题掌握直接插入排序的算法掌握起泡排序的算法掌握快速排序的算法以上三种排序算法的效率16.1简单选择排序基本思想：首先，在R[1]~R[n]中选出关键字最小的元素，将它与R[1]交换；然后，在R[2]~R[n]中选出关键字最小的元素，将它与R[2]交换；依次做下去，在进行了n-1

2、次选择后排序结束算法实现的要点1、获取选取关键字最小元素的序号用k来存放序号，k首先赋值i-1，在R[i]~R[n]中，逐个比较R[j].key与R[k].key的大小，如果前者小的话，将k更新为j，最后得到的k是关键字最小的元素序号2、交换两个数组元素用R[0]作为交换的暂存空间代码：voidselectsort(){inti,j,k;for(i=1;i<=n-1;i++){k=i;for(j=i+1;j<=n;j++)if(R[j].key

3、;}}}交换找到关键字最小元素序号放在k效率分析比较次数与原排列顺序无关总的比较次数为移动次数如果原序列是有序的，那么不需要移动如果是逆向有序，那么要进行n-1次交换，每次交换移动3次，共3(n-1)次16.2堆排序堆排序是在树型选择排序的基础上发展来的树型选择排序的基本思想首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间继续两两比较，直至选出最小关键字的记录为止这个过程可以用一棵有n个叶子结点的完全二叉树模拟得到这棵完全二叉树后，可以根据下面的步骤输出排序好的序列首先输出根结点，这就是最小的关键字然后将叶子结点中最小的关键字修改

4、为无穷大，对这个叶子结点到根的路径进行再次比较，如果路径上的结点由变化，则修改之时间复杂度是O(nlog2n),需要比较多的辅助空间堆排序的基本思想首先，初始建堆：按堆的定义将R[1]~R[n]调整为堆交换R[1]和R[n]然后，将R[1]~R[n-1]调整为堆，交换R[1]和R[n-1]反复进行，直到交换了R[1]和R[2]为止堆的概念堆是一棵顺序存储的完全二叉树，其中每个结点的关键字都不小于其孩子结点的关键字9785387649132776序列7638859776132749的初始建堆过程7685137697492738原始序列的完全二叉树形

5、态筛选的基本思路：对于任意结点R[i]，如果它的两棵子树都是堆的话，那么取i节点的两个孩子中较大的一个与R[i]比较（假设较大的那个是R[2*i]）如果R[i]较大，说明以R[i]为根的子树是堆否则，交换R[i]与R[2*i]这个交换可能会导致以R[2*i]为根的子树不再是堆（不过它的两棵子树仍然是堆），继续做筛法，直到树叶为止如此可以将一个以R[i]为根的子树调整为堆初始建堆：从原始形态的完全二叉树的最后一个分支结点R[i]（i=n/2）开始，应用上述的筛法，逐步将以R[i]、R[i-1]、...R[1]为根的子树调整为堆筛法的代码voidsi

6、ft(inti,intm){intk;R[0]=R[i];k=2*i;while(k<=m){if((k=1;j--)sift(j,n);for(j=n;j>=2;j--){R[0]=R[1]

7、;R[1]=R[j];R[j]=R[0];sift(1,j-1);}}初始建堆堆排序堆排序的时间复杂度为O(nlog2n)堆排序是不稳定排序16.3归并排序基本思想首先，将R[1]~R[n]看成是n个长度为1的有序表，将相邻的有序表成对归并，得到n/2个长度为2的有序表；然后，再讲这些有序表成对归并，得到n/4个长度为4的有序表如此反复，最后得到一个长度为n的有序表这个叫做2路归并如果归并是在相邻的多个有序表中进行，则叫多路归并算法实现分三个算法两个相邻有序表的归并函数一趟归并：对序列中所有相邻有序表归并对序列进行归并排序两个相邻有序表的归并算法

8、voidmerge(listR,listS,inta,intb,intc){inti,j,k;i=a;j=b+1;k=a;while((