数据结构(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