《数据结构》 查找排序 实验报告.docx

北 华 航 天 工 业 学 院?数据结构?课程实验报告实 验 题 目 ： 作者所在系部： 作者所在专业： 作者所在班级： 作 者 学 号 ： 作 者 姓 名 ： 任课教师姓名： 完 成 时 间 ： 北华航天工业学院教务处制实验五：查找和排序班级 学号 姓名 一、实验目的 1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法，并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。二、实验内容1 创立给定的静态查找表。表中共包含十条学生信息，信息如下： 学号 姓名 班级 C+ 数据结构 1 王立 03511 85 76 2 张秋 03511 78 88 3 刘丽 03511 90 79 4 王通 03511 75 86 5 赵阳 03511 60 71 6 李艳 03511 58 68 7 钱娜 03511 95 89 8 孙胜 03511 45 602 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，那么显示该生的相关信息；如果查找不成功，那么给出相应的提示信息。3 使用直接插入排序方法，按姓名对学生信息进行排序。输出排序前和排序后的学生信息表，验证排序结果。4 使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。5使用二分查找方法，从查找表中查找C成绩为78和80的学生。如果查找成功，那么显示该生的相关信息；如果查找不成功，那么给出相应的提示信息。6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。7 编写一个主函数，将上面函数连在一起，构成一个完整程序。8 将实验源程序调试并运行。注意：每完成一个操作必须进行输出，以验证操作的正确性。三、实验结果1、程序源代码：shiyanwu.cpp/包含主函数及各功能函数/*通过主函数调用各功能函数，进行初始化信息，并能通过菜单实现多种查找、排序方法。根据题目要求，简化了程序后，顺序查找方法实现按学生姓名查找学生相关信息，二分查找方法实现按学生CPP成绩查找学生相关信息，直接插入排序方法实现按学生姓名排序学生相关信息，直接选择排序方法实现按学生CPP成绩排序学生相关信息，冒泡排序方法实现按学生数据结构成绩排序学生相关信息*/#include"shiyanwu.h"#include<iostream>using namespace std;int main()int x,choice;ST *t;t=Init_ST();while(1)cout<<"1：顺序查找 2：二分查找 3:直接插入排序 4：直接选择排序 5：冒泡排序 6:退出"<<endl;cout<<"请输入操作编号："cin>>choice;switch(choice)case 1:S_Search(t);/顺序查找法，查找姓名break;case 2:Binary_Search(t,x);/二分查找法，查找CPP成绩break;case 3:cout<<"直接插入排序法，排序前的信息："<<endl;show(t);D_Insertsort(t);/直接插入排序法，排序姓名cout<<"直接插入排序法，排序后的信息："<<endl;show(t);break;case 4:cout<<"直接选择排序法，排序前的信息："<<endl;show(t);Select_Sort(t);/直接选择排序法，排序CPP成绩cout<<"直接选择排序发，排序后的信息："<<endl;show(t);break;case 5:cout<<"冒泡排序法，排序前的信息："<<endl;show(t);Bubble_Sort(t);/冒泡排序法，排序数据结构成绩cout<<"冒泡排序法，排序后的信息："<<endl;show(t);break; case 6: exit(1);default:cout<<"输入错误，请重新输入"<<endl;break;return 0;ST *Init_ST()ST *t;t=new ST;t->length=8;t->data1.number=1;strcpy(t->data1.classa,"03511");strcpy(t->data1.name,"王立");t->data1.cpppoint=85;t->data1.datastructpoint=76;t->data2.number=2;strcpy(t->data2.classa,"03511");strcpy(t->data2.name,"张秋");t->data2.cpppoint=78;t->data2.datastructpoint=88;t->data3.number=3;strcpy(t->data3.classa,"03511");strcpy(t->data3.name,"刘丽");t->data3.cpppoint=90;t->data3.datastructpoint=79;t->data4.number=4;strcpy(t->data4.classa,"03511");strcpy(t->data4.name,"王通");t->data4.cpppoint=75;t->data4.datastructpoint=86;t->data5.number=5;strcpy(t->data5.classa,"03511");strcpy(t->data5.name,"赵阳");t->data5.cpppoint=60;t->data5.datastructpoint=71;t->data6.number=6;strcpy(t->data6.classa,"03511");strcpy(t->data6.name,"李艳");t->data6.cpppoint=58;t->data6.datastructpoint=68;t->data7.number=7;strcpy(t->data7.classa,"03511");strcpy(t->data7.name,"钱娜");t->data7.cpppoint=95;t->data7.datastructpoint=89;t->data8.number=8;strcpy(t->data8.classa,"03511");strcpy(t->data8.name,"孙胜");t->data8.cpppoint=45;t->data8.datastructpoint=60; return t;/初始化学生信息ST *Init_ST2(ST *t)int i;cout<<"学生人数："cin>>t->length;for(i=1;i<=t->length;i+)cout<<"学号："cin>>t->datai.number;cout<<"姓名："cin>>t->datai.name;cout<<"班级："cin>>t->datai.classa;cout<<"C+成绩："cin>>t->datai.cpppoint;cout<<"数据结构成绩："cin>>t->datai.datastructpoint;return t;/初始化查找表中学生信息void show(ST *t)int i; cout<<"学号 姓名 班级 C+ 数据结构"<<endl;for(i=1;i<=t->length;i+)cout<<t->datai.number<<" "cout<<t->datai.name<<"t"cout<<t->datai.classa<<" "cout<<t->datai.cpppoint<<" "cout<<t->datai.datastructpoint<<endl;/输出学生信息void S_Search(ST *t)int i;char x20;cout<<"输入需查找的学生姓名："cin>>x;strcpy(t->data0.name,x);for(i=t->length;strcmp(t->datai.name,x);i-);if(i=0)cout<<"没有该学生的相关信息"<<endl;elsecout<<"学号 姓名 班级 C+ 数据结构"<<endl;cout<<t->datai.number<<" "cout<<t->datai.name<<" "cout<<t->datai.classa<<" "cout<<t->datai.cpppoint<<" "cout<<t->datai.datastructpoint<<endl;/查找到学生信息名字相同后，输出学生信息/顺序查找void D_Insertsort(ST *t)int i,j;for(i=2;i<=t->length;i+)if(strcmp(t->datai.name,t->datai-1.name)<0)/通过比拟学生姓名进行插入排序t->data0=t->datai;for(j=i-1;strcmp(t->data0.name,t->dataj.name)<0;j-)t->dataj+1=t->dataj;t->dataj+1=t->data0;/直接插入排序void Select_Sort(ST *t)int i,j,k,n;n=t->length;for(i=1;i<n;i+)for(k=i,j=i+1;j<=n;j+)if(t->dataj.cpppoint<t->datak.cpppoint)k=j;if(i!=k)t->data0=t->datak;t->datak=t->datai; t->datai=t->data0;/查找到CPP成绩最小的学生信息元素，将其排序/直接选择法排序void Binary_Search(ST *t,int x)cout<<"输入需查找的C+成绩："cin>>x;int low,high,mid;int flag;low=1;high=t->length;/初始化查找范围flag=0;while(low<=high)mid=(low+high)/2;/取支点if(x < t->datamid.cpppoint)high=mid-1;else if(x > t->datamid.cpppoint)low=mid+1;elseflag=mid;break;if(flag=0)cout<<"没有该学生的相关信息"<<endl;elsecout<<"学号 姓名 班级 C+ 数据结构"<<endl;cout<<t->dataflag.number<<" "cout<<t->dataflag.name<<" "cout<<t->dataflag.classa<<" "cout<<t->dataflag.cpppoint<<" "cout<<t->dataflag.datastructpoint<<endl;/查找成功，输出该学生相关信息/二分查找void Bubble_Sort(ST *t)int i,j,mark,n;n=t->length;for(i=1;i<n;j+)mark=0;for(j=1;j<=n-i;j+)if(t->dataj.datastructpoint>t->dataj+1.datastructpoint)t->data0=t->dataj;t->dataj=t->dataj+1;t->dataj+1=t->data0;mark=1;/将数据结果成绩值最大的学生信息元素排在最后if(mark=0)break;/已排好序列，结束排序/冒泡排序shiyanwu.h/包含数据结构的定义，及功能函数的声明typedef structint number;char name20;char classa10; int cpppoint;int datastructpoint;Datatype;/学生信息存储结点的定义typedef structDatatype data20;int length;ST;/查找表的定义ST *Init_ST(); /初始化所有学生信息ST *Init_ST2(ST *t);/初始化查找表中的学生信息void show(ST *t);/输出查找表中的学生信息void Select_Sort(ST *t);/直接选择排序法，排序CPP成绩void Binary_Search(ST *t,int x);/二分查找，查找CPP成绩void Bubble_Sort(ST *t);/冒泡排序，排序数据结构成绩void S_Search(ST *t);/顺序查找，查找姓名void D_Insertsort(ST *t);/直接插入排序，排序姓名按拼音字母顺序2、程序运行截图：图1顺序查找，按学生姓名查找学生信息图2 直接插入排序，按学生姓名排序学生信息图3 直接选择排序，按学生CPP成绩排序学生信息图4 二分查找，按学生CPP成绩查找学生信息图5 冒泡排序，按学生数据结构成绩排序学生信息四、实验总结1、掌握了根本的查找、排序算法。2、在程序的编写过程中，遇到很多不明白的地方，在得到同学的大力帮助下，根本掌握了。