查找、排序的应用

1查找、排序的应用一、问题描述对学生的基本信息进行管理。设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。二、问题分析1.定义储存学生信息的储存结构2.对学生信息进行查询和排序。3.查询用到两种查询方式：折半查找和顺序查找.4.排序用到两种方式：插入排序和选择排序。三、算法设计(1)定义学生信息存储结构typedefstruct//定义每个记录（数据元素）的结构{stringname;//姓名stringsex;//性别intnumber;//学号floatgrade1,grade2;//成绩1，成绩2floatscore;//总分}RecordType,RT[MAXSIZE];(2)查找方法a、折半查找设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令2low=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的作为哨兵。(3)排序a、插入排序每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。b、选择排序首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束。四、测试数据3五、源代码----------------------------------------Findsort.h-------------------------------------------#includestringusingnamespacestd;#defineMAXSIZE100typedefstruct//定义每个记录（数据元素）的结构{stringname;//姓名stringsex;//性别intnumber;//学号floatgrade1,grade2;//成绩1，成绩2floatscore;//总分}RecordType,RT[MAXSIZE];classstudent{private:RTrt;inttotal;//学生总数4public:voidGreatRT(int);//构建信息库voidBinarySearch();//折半查找voidSequentialSearch();//顺序查找voidInsertsort();//插入排序voidSelectSort();//选择排序};--------------------------------------Findsort.cpp------------------------------------------#includeiostream#includeFindsort.husingnamespacestd;voidstudent::GreatRT(intn){//信息构建total=n;inti=1;do{cout请输入第i个学生的信息：endl;cout姓名：;cinrt[i].name;cout性别：;cinrt[i].sex;cout学号：;cinrt[i].number;cout成绩1：;cinrt[i].grade1;cout成绩2：;cinrt[i].grade2;rt[i].score=rt[i].grade1+rt[i].grade2;i++;coutendl;}while(i=total);cout输入完毕！endlendl;}voidstudent::BinarySearch(){//折半查找算法:RecordTypeLI;for(inti=2;i=total;i++){//使学号变为有序5for(intj=i;j1;j--){if(rt[j].numberrt[j-1].number){LI=rt[j];rt[j]=rt[j-1];rt[j-1]=LI;}}}intn,m=0;cout输入要查找的学号：;cinn;intlow,high,mid;low=1;high=total;//置区间初值while(low=high){mid=(low+high)/2;if(n==rt[mid].number){m=1;break;}elseif(nrt[mid].number)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}if(m!=0)coutrt[mid].namert[mid].sexrt[mid].numberrt[mid].grade1rt[mid].grade2rt[mid].scoreendlendl;elsecout没有你要查找的学号！endlendl;}voidstudent::SequentialSearch(){//顺序查找算法:stringname;intm=0;cout输入要查找的姓名：;cinname;6for(inti=1;i=total;i++){m=1;if(name==rt[i].name)coutrt[i].namert[i].sexrt[i].numberrt[i].grade1rt[i].grade2rt[i].scoreendl;}if(m==0)cout没有你要查找的姓名！endlendl;elsecoutendl;}voidstudent::Insertsort(){//插入排序学号RecordTypeLI;for(inti=2;i=total;i++){for(intj=i;j1;j--){if(rt[j].numberrt[j-1].number){LI=rt[j];rt[j]=rt[j-1];rt[j-1]=LI;}}}for(intk=1;k=total;k++)coutrt[k].namert[k].sexrt[k].numberrt[k].grade1rt[k].grade2rt[k].scoreendl;coutendl;}voidstudent::SelectSort(){//选择排序总分RecordTypeLI;7for(inti=1;i=total;i++){for(intj=i+1;j=total;j++){if(rt[i].scorert[j].score){LI=rt[j];rt[j]=rt[i];rt[i]=LI;}}}for(intk=1;k=total;k++)coutrt[k].namert[k].sexrt[k].numberrt[k].grade1rt[k].grade2rt[k].scoreendl;coutendl;}-----------------------------------------main.cpp-------------------------------------------#includeiostream#includeFindsort.husingnamespacestd;voidmain(){studentst;intn;cout请输入学生总数：;cinn;st.GreatRT(n);cout学号（插入排序）：endl;st.Insertsort();//插入排序cout总分（选择排序）：endl;st.SelectSort();//选择排序st.BinarySearch();//折半查找st.SequentialSearch();//顺序查找}8六、总结本实验综合性非常强，它包含顺序表的存储、查找、排序，而且多处用到调用的方法，调用贯穿于整个程序之中，用到折半查找和顺序查找，用到插入排序和选择排序。通过本实验我对查找和排序这两个章节的内容更加了解，虽然这两个章节内容学习的时候时间非常紧，有很多不懂和疑问，但是通过这次实验，有了很好的补充，同时对调用做了一次很好的复习。