《数据结构》查找排序.docx

《《数据结构》查找排序.docx》由会员分享，可在线阅读，更多相关《《数据结构》查找排序.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北 华 航 天 工 业 学 院数据结构课程实验报告实 验 题 目 ： 作者所在系部： 作者所在专业： 作者所在班级： 作 者 学 号 ： 作 者 姓 名 ： 任课教师姓名： 完 成 时 间 ： 北华航天工业学院教务处制实验五：查找和排序班级 学号 姓名 一、实验目的 1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法，并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。二、实验内容1 创建给定的静态查找表。表中共包含十条学生信息，信息如下： 学号 姓名 班级 C+ 数据结构

2、 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成绩进行排序。输出排序前和排序后的学生信息表，验证排序

3、结果。5使用二分查找方法，从查找表中查找C成绩为78和80的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。7 编写一个主函数，将上面函数连在一起，构成一个完整程序。8 将实验源程序调试并运行。注意：每完成一个操作必须进行输出，以验证操作的正确性。三、实验结果1、程序源代码：shiyanwu.cpp/包含主函数及各功能函数/*通过主函数调用各功能函数，进行初始化信息，并能通过菜单实现多种查找、排序方法。根据题目要求，简化了程序后，顺序查找方法实现按学生姓名查找

4、学生相关信息，二分查找方法实现按学生CPP成绩查找学生相关信息，直接插入排序方法实现按学生姓名排序学生相关信息，直接选择排序方法实现按学生CPP成绩排序学生相关信息，冒泡排序方法实现按学生数据结构成绩排序学生相关信息*/#includeshiyanwu.h#includeusing namespace std;int main()int x,choice;ST *t;t=Init_ST();while(1)cout1：顺序查找 2：二分查找 3:直接插入排序 4：直接选择排序 5：冒泡排序 6:退出endl;coutchoice;switch(choice)case 1:S_Search(t)

5、;/顺序查找法，查找姓名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冒泡排序法，排序前的信

6、息：endl;show(t);Bubble_Sort(t);/冒泡排序法，排序数据结构成绩cout冒泡排序法，排序后的信息：endl;show(t);break; case 6: exit(1);default:cout输入错误，请重新输入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

7、-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-d

8、ata5.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,钱娜)

9、;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;coutt-length;for(i=1;ilength;i+)coutt-datai.number;coutt-datai.name;coutt-datai.classa;coutt

10、-datai.cpppoint;coutt-datai.datastructpoint;return t;/初始化查找表中学生信息void show(ST *t)int i; cout学号 姓名 班级 C+ 数据结构endl;for(i=1;ilength;i+)coutdatai.number ;coutdatai.namet;coutdatai.classa ;coutdatai.cpppoint ;coutdatai.datastructpointendl;/输出学生信息void S_Search(ST *t)int i;char x20;coutx;strcpy(t-data0.nam

11、e,x);for(i=t-length;strcmp(t-datai.name,x);i-);if(i=0)cout没有该学生的相关信息endl;elsecout学号 姓名 班级 C+ 数据结构endl;coutdatai.number ;coutdatai.name ;coutdatai.classa ;coutdatai.cpppoint ;coutdatai.datastructpointendl;/查找到学生信息（名字相同）后，输出学生信息/顺序查找void D_Insertsort(ST *t)int i,j;for(i=2;ilength;i+)if(strcmp(t-datai.

12、name,t-datai-1.name)data0=t-datai;for(j=i-1;strcmp(t-data0.name,t-dataj.name)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;in;i+)for(k=i,j=i+1;jdataj.cpppointdatak.cpppoint)k=j;if(i!=k)t-data0=t-datak;t-datak=t-datai; t-datai=t-data0;/查找到CPP成绩最小的学生信息元

13、素，将其排序/直接选择法排序void Binary_Search(ST *t,int x)coutx;int low,high,mid;int flag;low=1;high=t-length;/初始化查找范围flag=0;while(low=high)mid=(low+high)/2;/取支点if(x 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;cou

14、tdataflag.number ;coutdataflag.name ;coutdataflag.classa ;coutdataflag.cpppoint ;coutdataflag.datastructpointlength;for(i=1;in;j+)mark=0;for(j=1;jdataj.datastructpointt-dataj+1.datastructpoint)t-data0=t-dataj;t-dataj=t-dataj+1;t-dataj+1=t-data0;mark=1;/将数据结果成绩值最大的学生信息元素排在最后if(mark=0)break;/已排好序列，结束排

15、序/冒泡排序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 *

16、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、在程序的编写过程中，遇到很多不明白的地方，在得到同学的大力帮助下，基本掌握了。