查找、排序的应用 实验报告.doc

实验七 查找、排序的应用 实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] [基本要求] [测试数据] 由学生依据软件工程的测试技术自己确定。 五、算法设计 折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=?(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若keyr[mid].key，则high=mid-1 若keyr[mid].key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败 b、顺序查找 从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。 void chaxun(SqList ST) //查询信息 { cout\n************************endl; cout~ (1)根据学号查询 ~endl; cout~ (2)根据姓名查询 ~endl; cout~ (3)根据性别查询 ~endl; cout~ (4)退出 ~endl; cout************************endl; if(m==1) 折半查找算法： for(int i=1;iST.length;i++)//使学号变为有序 for(int j=i;j=1;j--) if(ST.r[j].xuehaoST.r[j-1].xuehao) { LI=ST.r[j]; ST.r[j]=ST.r[j-1]; ST.r[j-1]=LI; } int a=0; cout输入要查找的学号endl; cinn; int low,high,mid; low=0;high=ST.length-1; // 置区间初值 while (low=high) { mid=(low+high)/2; if(n==ST.r[mid].xuehao) { coutST.r[mid].xuehao ST.r[mid].xingming ST.r[mid].xingbei ST.r[mid].chengji1 ST.r[mid].chengji2 ST.r[mid].zongendl; a=1; break; } else if(nST.r[mid].xuehao ) high=mid-1; // 继续在前半区间进行查找 else low=mid+1; // 继续在后半区间进行查找 顺序查找算法: cout输入要查找的姓名endl; cinname; for(int i=0;iST.length;i++) { if(name==ST.r[i].xingming) { coutST.r[i].xuehao ST.r[i].xingming ST.r[i].xingbei ST.r[i].chengji1 ST.r[i].chengji2 ST.r[i].zongendl; a=1; } 插入排序 每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。 //按学号排序，使用插入排序 RecordType LI; //定义存储学号向量 for(int i=1;iST.length;i++) for(int j=i;j=1;j--) if(ST.r[j].xuehaoST.r[j-1].xuehao) { LI=ST.r[j]; ST.r[j]=ST.r[j-1]; ST.r[j-1]=LI;} 2、选择排序 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束。 //按成绩1排序,用选择排序 RecordType LI; for(int i=0; iST.length;i++) for (int j=i+1