实 验 报 告
课程名称 数据结构 实验名称 查找与排序的实现
系别 专业班级 指导教师11
学号 姓名 实验日期 实验成绩
一、实验目的
(1) 掌握交换排序算法（冒泡排序）的基本思想；
(2) 掌握交换排序算法（冒泡排序）的实现方法；
(3) 掌握折半查找算法的基本思想；
(4) 掌握折半查找算法的实现方法；
二、实验内容
1. 对同一组数据分别进行冒泡排序，输出排序结果。要求：
1) 设计三种输入数据序列：正序、反序、无序
2) 修改程序：
a) 将序列采用手工输入的方式输入
b) 增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂性
2. 对给定的有序查找集合，通过折半查找与给定值k相等的元素。
3. 在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，算法如何改进
三、设计与编码
1.本实验用到的理论知识
2.算法设计
3.编码
package sort_search;
import class Sort_Search {
序输入：
II.正序输入：
III.反序输入：
五、总结与心得
六、思考题
已知奇偶转换排序如下：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。
a)试问排序结束的条件是什么
b)实现上述排序过程的算法如何(请用自然语言、代码、伪代码写出该算法)
5_数据结构―查找和排序
软件技术基础
数据结构查找和排序
沙河校区主楼西301 沙河校区主楼西301 主楼西
颜红梅
hmyan@ __
软件技术基础
上节课复习线性表顺序表 结构体定义和表达 操作:初始化,赋值,插入, 操作:初始化,赋值,插入,删除 优缺点 链表 结构体表达 指针 操作:查找,插入, 操作:查找,插入,删除 优缺点
栈 队列
软件技术基础
数据结构1,基本概念 2,线性结构 3,非线性结构 4,查找与排序
软件技术基础
本节主要内容
查找算法顺序查找 二分查找
排序算法简单插入排序 简单选择排序 冒泡排序
软件技术基础
一,基本概念1,算法的概念 算法是对某一特定问题的解题步骤的描 是计算机指令的有限序列. 述,是计算机指令的有限序列.
数据结构的选择对算法的选择起决定作 用.
程序=算法+ 程序=算法+数据结构+。(运行环境相关) 运行环境相关)
软件技术基础
2,算法的特征可行性 确定性 有穷性 输入 输出:算法必须有确定的执行结果( 输出:算法必须有确定的执行结果(一个 或多个输出) 或多个输出)
软件技术基础
3,算法的评价: 算法的评价:正确性: 正确性:对于一切合法输入都能产生满足规格 要求的结果. 要求的结果. 易读性:算法要便于阅读,有助于人们对算法 易读性:算法要便于阅读, 的理解.
的理解. 健壮性:当输入非法数据时, 健壮性:当输入非法数据时,也能正常作出反 应和处理.要考虑出错的情况. 应和处理.要考虑出错的情况. 运行时间及占用空间:对相同规模的问题, 运行时间及占用空间:对相同规模的问题,运 行时间短,占用空间少. 行时间短,占用空间少.
软件技术基础
二,查找算法查找的效率将直接影响到数据处理的效率. 查找的效率将直接影响到数据处理的效率. 查找――就是在给定的数据集合中找出 就是在给定的数据集合中找出满足 查找――就是在给定的数据集合中找出满足 的结点/ 某种条件的结点 元素. 某种条件的结点/元素. 一般是依据结点/元素的关键字进行查找; 关键字进行查找 一般是依据结点/元素的关键字进行查找;关键字:元素的标志,检索的依据; 关键字:元素的标志,检索的依据; 一般情况下, 一般情况下,关键字是一个元素的唯一标识
淮海工学院计算机科学系
实验报告书
课程名： 《数据结构》
题 目： 查找、排序的应用实验
班 级： ^ ^
学 号： ^ ^
姓 名： ^ ^
评语：
成绩： 指导教师：
批阅时间： 年 月 日 《 数据结构 》实验报告
- 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) 分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序；
注：下面所有算法顺序结构都为
typedef struct{
KeyType key;
OthorType otherdata;
}
typedef struct{
RecordType r[maxsize+1];
int length;
}SqeList;
二分查找：
int BInSrch(RecordList *L,KeyType k){
int low=0,i=0;
int high=L->lengh-1;
while(low<=high){
int mid=(low+high)/2;
if(k==r[mid].key){
i=mid;break;
}
else if(kr[mid].key)
high=mid-1;
else low=mid+1;}
return(i);
}
}
直接插入排序法：
void InsertSort(SqeList *L){
for(i=1;ilength;i++){
L->r[0]=L->r[i];j=i-1;
while(L->r[0].keyr[j].key){
L->r[j+1]=L->r[j];
j=j-1;
}
L->r[j+1]=L->r[0];
}
}
希尔排序
void ShellInsert(SqeList *L,int di){
