《数据结构6(4月28日)》由会员分享，可在线阅读，更多相关《数据结构6(4月28日)（39页珍藏版）》请在金锄头文库上搜索。
1、查找：根据给定的关键字值，在一组数据元素中确定一个其关键元素中确定一个其关键字字值等于给定值的数据元素的过程。若存在这样的数据元素， 则称查找成功；若不存在这样的数据元素，则称查找失败。关键字:指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。查找表：指一组待查数据元素的集合。它具有一定存储结构，如顺序表结构、链式结构、树形结构等。2.6 查找1) 查找的方法查找某个数据元素依赖于查找表中数据元素的组织方式。按照 数据元素的组织方式决定采用某种查找方法；反之,为了提高查找 方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在 研究各种查找方法时，
2、必须弄清各种查找方法所适用的组织方式。2) 查找算法的评价衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。 而在查找算法中，基本运算是给定值与关键字值的比较，即算法的 主要时间是花费在“比较”上的，所以，用平均查找长度作为评价 查 找算法好坏的依据。对于含有n个数据元素的查找表，查找成功的平均查找长度为ASL=其中：Pi为查找第i个数据元素的概率；Ci为查找到第i个数 据元素时，需进行的比较次数。*查找方法分类 线性查找法 顺序查找法 对半查找法 分块查找法 基于树的查找法 二叉排序树 B树 计算式查找法哈希法顺序存储的查找方法链式存储的查找方法散列存储的查找方法2.6.1 顺序查找法基
3、本思想是：从数组的第一个元素开始，与查找的关键字逐个比对，直到找到关键字所在的位置或遇到数组的结尾为止，若找到，则返回关键字在数组中的位置，否则返回-1(因为C#的数组下标不可能为-1)。 public int search(int keyValue) int i=0；while( ) i+; if( ) return(i);else return(-1); 假设每个元素等概 率查找,则平均查 找次数为(n+1)/2iamid, 则取表的后半部分作为新表再去查找。（3）若k k);else;return (p); (p != null) for (i = 0; i datai + 1) ; i
4、nt temp = datai;datai = datai + 1;datai + 1 = temp;j-; needChange的作用是当前内循环无交换时，即终止程序的运算 。needChange for(i=1;i=0 i = start;j = end;x = datai; /将第一个值保存在x中while ( ) while (i = x) /自右向左扫描; if (i m) for(; ;j+) k+; bk=aj;else for(; ;i+) k+;bk=ai; j=2*k) twosort(a,i,i+k-1,i+2*k-1,b);i=i+2*k;if(n-ik) twosor
5、t(a,i,i+k-1,n-1,b);else for(;in;i+) bi=ai; 一趟归并后，有序子文件长度为2，二趟归并后，有序子文件长度为4，因归并的结果在b中,故每次归并完将其复制到a中。重复此过程，直到有序子文件为n，具体算法描述如下void mergeSort(int a, int n) int k=1,bN;/N为已定义的符号常量,代表线性表的长度while(kn) merge(a,k,n,b); k=2*k; for(int i=0;iN;i+)ai=bi; 各种排序方法的比较各种排序方法的比较（学号-6-1）将如下一组数据插入到一棵二叉排序树中，并将 该二叉排序树的中序遍历结果输出。45，24，53，12，37，93，30，40，80作业
