查找排序实验报告

查找、排序实验班级学号姓名一、实验目的1掌握不同的查找和排序方法，并能用高级语言实现相应算法。2熟练掌握顺序查找和二分查找方法。3熟练掌握直接插入排序、选择排序、冒泡排序、快速排序。二、实验内容1创建给定的静态查找表。表中共包含十条学生信息，信息如下：学号姓名班级C++数据结构1王立0351185762张秋0351178883刘丽0351190794王通0351175865赵阳0351160716李艳0351158687钱娜0351195898孙胜0351145602使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。3使用快速排序方法，对学生信息中的学号进行排序，然后使用二分查找方法，从查找表中查找学号为7和12的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。4使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。5使用选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。6使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。7编写一个主函数，将上面函数连在一起，构成一个完整程序。8调试实验源程序并运行。三、实验结果源程序代码：#include<iostream>usingnamespacestd;#include<string>#include<iomanip>#defineM100typedefstringKeytype;typedefstruct{KeytypeclassNum;Keytypename;intstudentNum;intC;intstructure;}Student;typedefstruct{ Students[M]; intlength;}s_t;intcreat(s_t*t,intNum){ inti; t->length=Num; for(i=1;i<=t->length;i++) { cout<<"请输入第"<<i<<"个学生的信息(学号，姓名，班级，C++，数据结构):"<<endl; cin>>t->s[i].studentNum>>t->s[i].name>>t->s[i].classNum>>t->s[i].C>>t->s[i].structure; } return0;}intprint(s_t*t){ inti; cout<<""<<"学号"<<""<<"姓名"<<""<<"班级"<<""<<"C++成绩"<<""<<"数据结构"<<""<<endl; for(i=1;i<=t->length;i++) {cout<<""<<t->s[i].studentNum<<""<<t->s[i].name<<""<<t->s[i].classNum<<""<<t->s[i].C<<""<<t->s[i].structure<<""<<endl; }return0;}intS_Search(s_t*t,Keytypekx){inti; t->s[0].name=kx; for(i=t->length;i>=0;i--) if(t->s[i].name==kx) returni;}voidInserSort(s_t*t){inti; for(i=2;i<=t->length;i++) if(t->s[i].name<t->s[i-1].name) {t->s[0]=t->s[i]; for(intj=i-1;t->s[0].name<t->s[j].name;j--)t->s[j+1]=t->s[j];t->s[j+1]=t->s[0]; }}intSelect_Sort(s_t*t){ inti,j,k; for(i=0;i<t->length;i++) { k=i;for(j=i+1;j<=t->length;j++) if(t->s[k].C>t->s[j].C) k=j; if(i!=k) {t->s[0]=t->s[k]; t->s[k]=t->s[i]; t->s[i]=t->s[0]; } } return0;}intHalf_Sort(s_t*t,intnum){ intflag=0; intlow,high,mid; low=1;high=t->length;while(low<=high) { mid=(low+high)/2; if(t->s[mid].studentNum>num) high=mid-1;elseif(t->s[mid].studentNum<num) low=mid+1; else {flag=mid;break; }} returnflag;}intBu_Sort(s_t*t){ inti,j,swap;for(i=1;i<t->length;i++) { swap=0;for(j=1;j<=t->length-i;j++) if(t->s[j].structure>t->s[j+1].structure) { t->s[0]=t->s[j]; t->s[j]=t->s[j+1]; t->s[j+1]=t->s[0]; swap=1; } if(swap==0) break; } return0;}intPartition(s_t*t,inti,intj){t->s[0]=t->s[i];while(i<j){while(i<j&&t->s[j].studentNum>=t->s[0].studentNum) j--; if(i<j) { t->s[i]=t->s[j]; i++; } while(i<j&&t->s[i].studentNum<t->s[0].studentNum) i++; if(i<j) { t->s[j]=t->s[i]; j--; }}t->s[i]=t->s[0];returni;}voidQuick_sort(s_t*t,ints,intp){ inti;if(s<p){i=Partition(t,s,p); Quick_sort(t,s,i-1); Quick_sort(t,i+1,p);}}voidQuick(s_t*t,intn){Quick_sort(t,1,n);}intmain(){ s_t*t; inti,n,n1,Num; intflag=1; Keytypekx; t=news_t; cout<<"*********欢迎进入学生管理系统**************"<<endl; cout<<"1按姓名顺序查找2输出所有学生信息3直接插入排序"<<endl; cout<<"4按C++选择排序5按学号二分查找6按数据结构冒泡排序"<<endl; cout<<"7按学号快速排序8建立学生的信息0退出程序"<<endl; cout<<"********************************************"<<endl; while(flag) { cout<<"请选择要进行的操作:"; cin>>n; switch(n) { case1: cout<<"请输入要查找的学生的姓名:"<<endl; cin>>kx; i=S_Search(t,kx);if(i) { cout<<""<<"学号"<<""<<"姓名"<<""<<"班级"<<""<<"C++成绩"<<""<<"数据结构"<<""<<endl;cout<<""<<t->s[i].studentNum<<""<<t->s[i].name<<""<<t->s[i].classNum<<""<<t->s[i].C<<""<<t->s[i].structure<<""<<endl; cout<<endl; } elsecout<<"没有此人！"<<endl; break; case2: cout<<"输出现在学生的全部信息:"<<endl; print(t); break; case3:cout<<"直接插入排序:"<<endl;cout<<"排序前的学生信息"<<endl; print(t); cout<<"排序后的学生信息"<<endl; InserSort(t); print(t); break; case4:cout<<"选择排序:"<<endl;cout<<"排序前的学生信息"<<endl; print(t); Select_Sort(t); cout<<"排序后的学生信息"<<endl;print(t); break; case5:Select_Sort(t); cout<<"输入要查找的学号"<<endl; cin>>n1; i=Half_Sort(t,n1); if(i) { cout<<""<<"学号"<<""<<"姓名"<<""<<"班级"<<""<<"C++成绩"<<""<<"数据结构"<<""<<endl;cout<<""<<t->s[i].studentNum<<""<<t->s[i].name<<""<<t->s[i].classNum<<""<<t->s[i].C<<""<<t->s[i].structure<<""<<endl; cout<<endl; } elsecout<<"不存在此学号!"<<endl; break; case6:cout<<"冒泡排序"<<endl; cout<<"排序前的学生信息"<<endl; print(t); Bu_Sort(t); cout<<"排序后的学生信息"<<endl; print(t); break; case7: cout<<""<<endl; print(t); cout<<""<<endl; Quick(t,Num);print(t); break;case8: cout<<"请输入学生的个数："; cin>>Num; creat(t,Num); break; case0:return0; default:cout<<"没有此功能，请选择正确的操作！"<<endl;break;} } return0;}运行结果：表1输入学生信息表2顺序查找方法表3按姓名直接插入表4按C成绩选择排序 表5按学号进行二分法查找表6按数据结构成绩进行冒泡法排序四、实验总结（1）直接插入排序时，要明确后移的结束条件，以便进行正确插入。（2）选择排序时，选择最小或是最大的数据，放到最后。进行N-1趟排序，排序完成。（3）二分法排序时，正确返回查找的下标。返回值flag要进行赋初