计算机编程查找和排序教案.docVIP

查找和排序 学习目标： 1.掌握查找的相关概念。 2.掌握顺序查找、二分查找和分块查找算法。 3.掌握哈希存储。 4.掌握插入、交换和选择排序算法。 重点、难点: 1. 顺序查找、二分查找和分块查找算法。 2. 哈希存储。 3. 插入、交换和选择排序算法。 课程内容： 6.1 查找的相关概念 查找的定义 查找其关键字等于给定值的操作。 关键字的概念 关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，若能唯一标识，则称为主关键字，否则，称为次关键字。 查找的结果 若查到其关键字等于给定值的记录，则称“查找成功”，否则，称“查找失败”。 查找算法效率的度量 （1）平均查找长度ASL：在查找其关键字等于给定值的过程中，需要和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度。 （2）所需的辅助存储空间 本章假定关键字为整数，其类型定义如下： #define n 待查表中记录个数 typedef struct { . keytype key; datatype orther; }table; table R[n+1]; 6.2 静态查找表 6.2.1顺序查找 顺序查找的定义 用待查关键字和线性表中各结点的关键字逐个比较，直到找到关键字值相等的结点，即查找成功；或查完全表，而未找到关键字相等的结点，即为查找失败。 顺序查找的算法 int seqsearch(R,k) /*在具有n个元素的顺序表R中查找关键字为k的结点， */ /*若查找成功，返回该结点的位置；否则，返回-1 */ table R[]; { int i=0; R[n].key=k; / *R[n]为监视哨，监视哨也可设在低端 */ while (R[i].key !=k) i++; if (i==n) return(-1); /* 返回查找结果 */ else return(i); } 顺序查找算法的时间复杂度 平均查找长度ASL: 查找成功 == 查找失败 n+1 设查找成功的概率为p,查找成功的概率为q=(1-p),则平均比较次数为： E(n)=p. +q.(n+1)= p. +(1-p).(n+1)=(n+1).(1-); 若成功和失败的概率各占50%,平均性能。 若查找各结点的概率不等，应将查找概率高的结点放在前边，以提高查找效率。 6.2.2 二分查找 二分法查找的基本概念 若顺序表中元素已按关键字有序排列，查找时不必顺序查找，而是用待查关键字与中间位置的元素的关键字比较，若相等，则查找成功；若待查关键字小，则在由中间位置分开的左子表中查找，否则，在右子表中进行。如此下去，直至查找成功或查找失败。 二分法查找的算法 int binsearch(R,k) /*在具有n个元素的有序表R中查找关键字为k的结点， */ /*若查找成功，返回该结点的位置；否则，返回-1 */ table R[]; { int l=0; h=n-1; while (l=h) { i=(l+h)/2 /* 取中间位置 */ if (R[i].key=k) return(i); /* 算法结束 */ else if (R[i].keyk) h=i-1); /* 在左子表查找 */ else l=i+1; /* 在右子表查找 */ } return(0) } 二分法查找的时间复杂度 二分法查找的过程可用二叉树来描述，中间结点是二叉树的根，左子表相当于左子树，右子表相当于右子树，由此得到的二叉树便为描述二分法查找的判定树。二分法查找的过程是走了一条从根结点到叶子结点的过程，不论查找成功与失败，查找长度均不超过树的高度，其平均性能为h= (log2(n+1) (。 二分法查找的优缺点 优点：查找速度快； 但表必须有序。 缺点：频繁插入和删除不方便。 二分法查找适于表中元素很少变化而查找频繁的情况；顺序表查找适于查找少而表中元素频繁变化的情况。 6.2.3 分块查找 分块查找综合了顺序查找和二分法查找的优点，既有动态结构，又适于快速查找。 分块查找的基本思想 将待查找文件等长的分为若干个子文件（最后一个子文件长度可能小）。子文件内的元素无序，但子文件之间有序，即第一个子文件的最高关键字小于第二个子文件的最高关键字，第二个子文件的最高关键字小于第三个子文件的最高关键字，依次类推。再建立一个索引表（文件），文件中的每个元素含有各子文件的最高关键字和各子文件中第一个元素的地址（下标），索引文件按关键字有序。 查找时，对索引表可以顺序查找或二分法查找，在块内只能顺序查找。 分块查找的平均长度 设待查找文件有n个记录，平均分成b块，每块