查找与排序实验

实 验 报 告

实验原理：

快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）设置两个变量I、J，排序开始的时候I：=1，J：=N

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想：

（1）确定该区间的中点位置：mid=（low+high）/2

min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置 （2）将待查a值与结

对记录序列(查找表)：{55,13,23,72,109,67,2,78,13}分别实现如下操作：1)顺序查找;2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序(暂时人工排序);3)对排好序的纪录序列表进行折半查找;4)利用原纪录序列建立一颗二叉排序树,并在其上实现特定关键字值结点的查找;5)按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表

淮海工学院计算机科学系 实验报告书课 程 名 ：题

《数据结构》

目： 查找、排序综合实验

班 学 姓

级： 号： 名：

评语：

成绩：

指导教师： 批阅时间： 年 月 日

对记录序列(查找表)：{55,13,23,72,109,67,2,78,13}分别实现如下操作：1)顺序查找;2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序(暂时人工排序);3)对排好序的纪录序列表进行折半查找;4)利用原纪录序列建立一颗二叉排序树,并在其上实现特定关键字值结点的查找;5)按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表

《

数据结构

》实验报告

-1-

排序、查找的应用实验报告要求1 目的与要求:1)查找、排序是日常数据处理过程中经常要进

实验七查找与排序

1. 实验目的

? ? ?

掌握常用查找算法的基本实现方式； 掌握各种排序算法的基本实现方式； 熟悉各种查找与排序算法的特点

2. 实验内容与基本要求

现有某地区某学校学生高考成绩数据（请见文本文件）若干，其中每位学生的信息包括考号、语文、数学、英语、理综、总分、全省排名、录取批次。请根据这些数据请建立一个顺序表。用户可通过数字键选择信息查找及排序功能。对程序的具体要求如下： 1） 程序启动后，显示下列选项信息：

1：排序 2：查找 0：退出

2） 输入数字“1”，进入排序区。进一步显示下列信息：

3：直接插入排序 4：简单选择排序 5：冒泡排序 6、高考总排名7 退出排序 ? 输入数字“3”，程序按照数学成绩进行直接插入排序并显示结果。 ? 输入数字“4”，程序按照语文成绩进行简单选择排序并显示结果。 ? 输入数字“5”，程序按照总分进行冒泡排序并显示结果。

? 输入数字“6”，程序进行高考总排名并显示结果，排名规则：总成绩、数学、

语文、英语、理综。即先按总成绩排，总成绩相同，按数学成绩的高低排名；若数学成绩也相同，按照语文成绩的高低排序；以此类推。注意排序方法的综合运用。

? 输入数字“7”，退出排序。

3）

实 验 报 告

课程名称 数据结构 实验名称 查找与排序的实现 系别 专业班级 指导教师11 一、实验目的

(1) (2) (3) (4)

掌握交换排序算法（冒泡排序）的基本思想； 掌握交换排序算法（冒泡排序）的实现方法； 掌握折半查找算法的基本思想； 掌握折半查找算法的实现方法；

学号 姓名 实验日期 实验成绩

二、实验内容

1. 对同一组数据分别进行冒泡排序，输出排序结果。要求： 1) 设计三种输入数据序列：正序、反序、无序

2) 修改程序：

a) 将序列采用手工输入的方式输入

b) 增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂

性

2. 对给定的有序查找集合，通过折半查找与给定值k相等的元素。

3. 在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，

算法如何改进？

三、设计与编码

1.本实验用到的

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 查找、排序的应用实验

班 级：

学 号： ^ ^

姓 名：

排序、查找的应用实验报告要求

1目的与要求:

1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提

高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用

的数据存储结构；

3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制

实现实验程序的交互运行）和实用性；

4）本次与第七次实验已合二为一，实验结果在机房现场验收和评分，希望同学们认真对待，并于2009年12月20日按时提交本次实验报告（含电子和纸质报告），任何同学不得拖延。

5）如果验收时间紧张，不能再正课时间完成者，由老师择机决定另行通知专门验收时间。凡无故不主动或拖延验收者，均按照不及格处理。

5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于按时提交。 2 实验内容或题目

题目：对数据序列（查找表）：{55，13，23，72，109，67，2，78,13}分别实现如下操作：

1) 顺序查找；

2) 分别使用直

xxx大学实验报告

课程名称 数据结构 实验项目 实验三 查找和排序(一)——查找 院 系 信息学院计类系 专业班级 计类1501 姓 名 学 号 指导老师 日 期

批改日期 成 绩

一 实验目的

1．掌握哈希函数——除留余数法的应用； 2. 掌握哈希表的建立； 3. 掌握冲突的解决方法； 4. 掌握哈希查找算法的实现。

二 实验内容及要求

实验内容：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并计算平均查找长度（设每个记录的查找概率相等

查找、排序的应用

《数据结构》

实 验 报 告 书

实验内容：查找、排序的应用 学院班级：计算机学院计算机科学与技术 姓 名：*****

学 号：20110********** 指导老师：高****

1

查找、排序的应用

前言

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

实验七查找、排序的应用

一、实验

实验二 信息的查找与排序

【实验目的】

熟练掌握基本的排序算法，掌握数组的基本查找方法：顺序法和折半查找法。 【实验内容】

以6_2.c命名本程序并上交。

数据文件studentlist.txt中存放有21名学生的学号与成绩，数据已按学号升序排序。studentlist.txt的内容如下图：

从数据文件studentlist.txt中读出21名学生的学号与成绩到学号数组与成绩数组中，显示这21名学生的成绩到屏幕。

输入一个要查找的学生学号，找到了，输出该学生的成绩，找不到，显示No find。 要求使用折半查找算法按学号查找。

最后按成绩降序排序输出所有数据

【实验提示】

对信息排序时，通常只使用信息的一个子项作为排序键值（Key Value）,如开始的学号就是排序键。当待查找的信息有序排列时，折半查找比顺序查找效率要高非常多。本题最后是用成绩做为排序键对信息进行排序。

查找是计算机中经常要遇到的一种操作，其含义是在一组数据中查找到所查数据的位置。比较简单的是顺序查找法，效率较高的是折半查找法。 1．顺序查找法

顺序查找也叫线性查找，当一组数据无序时，一般采用顺序查找。其基本思想是：从数据集的第一个元素开始，依次将关键字x与数据集中的每一个

实验二 信息的查找与排序

【实验目的】

熟练掌握基本的排序算法，掌握数组的基本查找方法：顺序法和折半查找法。 【实验内容】

以6_2.c命名本程序并上交。

数据文件studentlist.txt中存放有21名学生的学号与成绩，数据已按学号升序排序。studentlist.txt的内容如下图：

从数据文件studentlist.txt中读出21名学生的学号与成绩到学号数组与成绩数组中，显示这21名学生的成绩到屏幕。

输入一个要查找的学生学号，找到了，输出该学生的成绩，找不到，显示No find。 要求使用折半查找算法按学号查找。

最后按成绩降序排序输出所有数据

【实验提示】

对信息排序时，通常只使用信息的一个子项作为排序键值（Key Value）,如开始的学号就是排序键。当待查找的信息有序排列时，折半查找比顺序查找效率要高非常多。本题最后是用成绩做为排序键对信息进行排序。

查找是计算机中经常要遇到的一种操作，其含义是在一组数据中查找到所查数据的位置。比较简单的是顺序查找法，效率较高的是折半查找法。 1．顺序查找法

顺序查找也叫线性查找，当一组数据无序时，一般采用顺序查找。其基本思想是：从数据集的第一个元素开始，依次将关键字x与数据集中的每一个

深 圳 大 学 实 验 报 告

课程名称： 数据结构实验与课程设计

实验项目名称： 顺序查找、折半查找实验

学院： 计算机与软件学院

专业：

指导教师： 杨芳

报告人： 学号： 班级：

实验时间：

实验报告提交时间：

教务处制

一、实验目的

1、掌握顺序查找、折半查找算法的基本思想 2、掌握顺序查找、折半查找算法的实现方法 3、掌握顺序查找、折半查找的时间