数据结构-查找排序实验

实验五：查找和排序班级B09513学号200940姓名一、实验目的1掌握查找的不同方法，并能用高级语言实现查找算法。2熟练掌握顺序表和有序表的顺序查找和二分查找方法。3掌握排序的不同方法，并能用高级语言实现排序算法。4熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。二、实验内容1创建给定的静态查找表。表中共包含十条学生信息，信息如下：学号姓名班级C++数据结构1王立0351185762张秋0351178883刘丽0351190794王通0351175865赵阳0351160716李艳0351158687钱娜0351195898孙胜0351145602使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。3使用直接插入排序方法，按姓名对学生信息进行排序。输出排序前和排序后的学生信息表，验证排序结果。4使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。5使用二分查找方法，从查找表中查找C成绩为79和80的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。6使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。7编写一个主函数，将上面函数连在一起，构成一个完整程序。8将实验源程序调试并运行。注意：每完成一个操作必须进行输出，以验证操作的正确性。三、实验结果#include<iostream>#include<string>#include<iomanip>usingnamespacestd;constintMAX=100;typedefstruct{ intnum;stringname; intclassnum; intcs; intss;}DataType;typedefstruct{ DataTypedata[MAX]; intlength;}SNode;voidInit(SNode*t){ t->length=0;}voidCreate(SNode*t,inta[],stringb[],intc[],intd[],inte[],intn) //创建{ for(inti=0;i<n;i++) { t->data[i+1].num=a[i]; t->data[i+1].name=b[i]; t->data[i+1].classnum=c[i]; t->data[i+1].cs=d[i]; t->data[i+1].ss=e[i]; t->length++; }}voidDisplay(SNode*t,inti) //输出学生的相关信息{cout.setf(ios::right);cout<<setw(8)<<"学号"<<setw(10)<<"姓名"<<setw(10)<<"班级"<<setw(10)<<"C++成绩"<<setw(15)<<"数据结构成绩"<<endl;cout.setf(ios::right); cout<<setw(8)<<t->data[i].num<<setw(10)<<t->data[i].name<<setw(10)<<t->data[i].classnum<<setw(10)<<t->data[i].cs<<setw(15)<<t->data[i].ss<<endl;}voidN_Search(SNode*t,stringkn) //按姓名查找{ inti; i=t->length; t->data[0].name=kn;while(t->data[i].name!=kn) i--; if(i==0) cout<<"······对不起，没有该姓名的学生！········"<<endl; else { cout<<"····找到了！······"<<endl;Display(t,i); } }voidC_Search(SNode*t,intcs1) //二分查找C成绩{inti=1;intflag,flag1;intlow,high,mid,low1,high1,mid1;low=1;low1=1;high=t->length;high1=t->length;flag1=0;flag=0;while(low<=high){ mid=(low+high)/2; if(cs1<t->data[mid].cs) high=mid-1; else { if(cs1>t->data[mid].cs) low=mid+1; else { flag=mid; break; } }}if(flag==0) cout<<"没有该成绩的学生！"<<endl;else{ cout<<"---------该学生的信息：-----------"<<endl;Display(t,flag);}}voidN_Sort(SNode*t,intn) //直接插入法对学生的姓名进行排序{ inti; intj; DataTypep; for(i=2;i<=n;i++) { if(t->data[i].name<t->data[i-1].name) { t->data[0].name=t->data[i].name; for(j=i-1;t->data[0].name<t->data[j].name;j--) { p=t->data[j]; t->data[j]=t->data[j+1]; t->data[j+1]=p; } } }}voidC_Sort(SNode*t,intn){ inti,j,k; for(i=1;i<n;i++) { for(k=i,j=i+1;j<=n;j++) if(t->data[j].cs<t->data[k].cs) k=j; if(i!=k) { t->data[0]=t->data[k]; t->data[k]=t->data[i]; t->data[i]=t->data[0]; } }}voidS_Sort(SNode*t,intn) //冒泡法对数据结构排序{ inti,j; intswap; for(i=1;i<n;i++) { swap=0; for(j=1;j<=n-i;j++) if(t->data[j].ss>t->data[j+1].ss) { t->data[0]=t->data[j]; t->data[j]=t->data[j+1]; t->data[j+1]=t->data[0]; swap=1; } if(swap==0) break; }}intmain(){ SNodes; Init(&s); inti; inta[8]={1,2,3,4,5,6,7,8};stringb[8]={"王立","张秋","刘丽","王通","赵阳","李艳","钱娜","孙胜"};intc[8]={03511,03511,03511,03511,03511,03511,03511,03511};intd[8]={85,78,90,75,60,58,95,45};int e[8]={76,88,79,86,71,68,89,60}; Create(&s,a,b,c,d,e,8); stringnames;intscore; cout<<"请输入您要查找的学生的姓名：";cin>>names;N_Search(&s,names); cout<<"请输入您要查找的学生的姓名："; cin>>names;N_Search(&s,names); cout<<"--------姓名排序--------"<<endl; cout<<"********排序前的输出结果：********"<<endl;for(i=1;i<9;i++) Display(&s,i); N_Sort(&s,8); cout<<"********排序后的输出结果：********"<<endl; for(i=1;i<9;i++) Display(&s,i); cout<<"------C++成绩排序--------"<<endl; cout<<"********排序前的输出结果：********"<<endl; for(i=1;i<9;i++) Display(&s,i); C_Sort(&s,8); cout<<"********排序后的输出结果：********"<<endl; for(i=1;i<9;i++) Display(&s,i); cout<<"---------二分查找法对C++成绩的查找----------"<<endl; cout<<"请输入您要查找的学生的C++成绩：";cin>>score; C_Search(&s,score); cout<<"请输入您要查找的学生的C++成绩：";cin>>score; C_Search(&s,score); cout<<"-------数据结构排序-------"<<endl; cout<<"********排序前的输出结果：********"<<endl; for(i=1;i<9;i++) Display(&s,i); cout<<"********排序后的输出结果：********"<<endl;S_Sort(&s,8); for(i=1;i<9;i++) Display(&s,i);}试验结果：直接插入法按姓名对学生的信息排序：排序前：排序后：直接选择法对C++成绩进行排序：排序前：排序后：二分法队学生的成绩进行查找：冒泡法对学生的数据结构成绩进行排序：排序前：排序后：四、实验总结1、关键码是数据元素中某个数据项的值，它