数据结构(C 版)各种排序和查找的应用

---------------------------------------------------------------最新资料推荐------------------------------------------------------

数据结构（C++版）各种排序和查找的应用

数学与计算机学院 实 验 报 告 （ 2019 /2019 学年 第 1 学期）

课程名称 数据结构 课程代码 任课教师 指导教

师 学生姓名 学 号 年 级 专 业 综合成绩 实验名称 查找和排序 指导教师 实验类型 □验证 综合 实验学时 2+10 实验日 期实验时间 实验编号 1 分组号 1 实验地点 实验报告 一、 实验目的和要求 1． 掌握静态表查找存储结构和算法； 2． 掌握动态表查找存储结构和算法 3． 掌握折半查找算法和二叉排序树查找算法。

4． 掌握常用的排序方法及实现； 5． 深刻理解排序的定义和各种排序方法的特点， 并能加以灵活应用 实验要求：

了解掌握查找算法的基本思想和算法的实现； 了解各种方法的排序过程及依据的原则， 并掌握各种排序方法的时间复杂度的分析方法。

二、 实验环境(实验设备) 硬件: 微型计算机 P5 软件: Windows XP+Microsoft Visual C++ 6. 0 三、 实验原理及内容 实验题目: 给出 n 个学生的考试成绩表， 每条信息由姓名和分数组成， 试完成下列操作：

1. 输入 n 个学生的姓名和成绩， 保存于考试成绩表中； 2. 排序：

使用直接插入排序算法对学生的分数按升序排列， 结果保存在

1 / 6

原考试成绩表中。 3. 输出：

按一行一个学生信息的方式输出 n 个这生考试成绩表。 4. 查找：

对于经步骤 2 排序好的考试成绩表， 请使用二分查找算法查找分数为 x 的学生， 若存在则输出学生的姓名和分数， 否则输出查无此人 信息。

5． 根据 1 中输入的成绩表 1） 建立二叉排序树； 2） 使用中序遍历算法输出中序遍历序列； 3） 查找成绩为 x 的学生， 若存在输出该学生信息， 否则输出未找到信息。 实验中完成 1-5 题； 实验后完成：

将考试成绩表分别使用希尔排序、 堆排序对分数进行升序和降序排列并输出。

2 实验报告 实验解答：

1. 学生考试成绩表的结构体定义 struct student{ char name[15]; float score; } ; 2. 学生考试成绩表的定义（数组） #define MAX 2 Student s[MAX]; 3. n 个学生录入的算法代码 void table: : create() { char n[15]; for(int i=0; iMAX; i++) { cout输入姓名：

; cinn; strcpy(s[i]. name, n) ; cout输入成绩： ; cins[i]. score; } } 4． 按分数进行直接插入排序算法的代码 void table: : sort() { float temp; int i, j;

---------------------------------------------------------------最新资料推荐------------------------------------------------------

for(i=1; iMAX; i++) { temp=s[i]. score; for(j=i; jMAX temps[j-1]. score; j--) { s[j]. score=s[j-1]. score; } s[j]. score=temp; } } 5. n 个学生考试成绩表的输出算法 void table::display(){ for(int i=0;iMAX;i++){ cout姓名： s[i].nameendl; cout成绩：

s[i].scoreendl; 3 实验报告 } } 6． n 个学生按分数进行二分查找算法。

void table: : search() { float f; int mid, min=0, max=MAX, i, flog=0; cout输入成绩：

; cinf; while(min=max) { mid=(min+max) /2; if(f==s[mid]. score) { cout姓名： s[mid]. nameendl; cout成绩：

s[mid]. scoreendl; for(i=mid-1; i=0s[i]. score==f; i--) { //查找左边成绩相同的学生 cout姓名： s[i]. nameendl; cout成绩：

s[i]. scoreendl; } for(i=mid+1; iMAXs[i]. score==f; i++) { //查找右边成绩相同的学生 cout姓名：

s[i]. nameendl; cout成绩：

s[i]. scoreendl; } max=min-1; flog=1; //跳出 while 循环 } else if(fs[mid]. score)

3 / 6

{ max=mid-1; } else{ min=mid+1; } } if(flog==0) cout查找失败！ endl; } 7． 按成绩建立二叉排序树算法 student * table: : insert(student * t, student * s1) { if(t==NULL) 4 实验报告 t=s1; else if(s1-scoret-score) t-left=insert(t-left, s1) ; else t-right=insert(t-right, s1) ; return t; } void table: : creatBIN() { student * s1; for(int i=0; iMAX; i++) { s1=new student; cout插入第i+1个节点endl; s1-left=NULL; s1-right=NULL; strcpy(s1-name, s[i]. name) ; s1-score=s[i]. score; root=insert(root, s1) ; } } 8． 按成绩进行二叉排序树查找算法 void table: : search1() { float f; int flog=0; cout输入要查找的成绩：

; cinf; student * t=root; while(t!=NULL) { if(t-score==f) { cout姓名： t-nameendl; cout成绩：

t-scoreendl; while(t-right!=NULLt-right-score==f) {//查找其他成绩相同的学生 cout姓名： t-nameendl; cout成绩：

t-scoreendl; t-right=t-right-right; } t==NULL; flog=1; } else if(t-scoref) { t=t-right; } else t=t-left; } if(flog==0) cout查找失败！ endl; 5 实验报告 } 9． 你准备用于测试的数