当前位置:首页 >> 工学 >>

实验三:折半查找算法设计


课程名称 姓 名 实验日期 数据结构 何虹江 2012.05.19







实验名称 折半查找算法设计 学 号 201007040227 专业班级 软件 1002 成 绩 指导教师

(①实验目的 ②实验原理 ③主要仪器设备 ④实验内容与步骤 ⑤实验数据记录与处理 ⑥实验结果与分析⑦问题与建议)

一、 实验目的 习题 6-16(P149) 二、 实验原理 排序:直接选择排序 第一次从 R[0]~R[n-1]中选取最小值,与 R[0]交换,第二次从 R{1}~R[n-1]中选取最小值,与 R[1]交 换, ...., 第 i 次从 R[i-1]~R[n-1]中选取最小值, R[i-1]交换, 与 ....., n-1 次从 R[n-2]~R[n-1] 第 中选取最小值,与 R[n-2]交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列. 折半查找算法:递归查找和循环查找 假设有已经按照从小到大的顺序排列好的五个整数 a0~a4,要查找的数是 X,其基本思想是: 设查找数据 的范围下限为 l=1,上限为 h=5,求中点 m=(l+h)/2,用 X 与中点元素 am 比较,若 X 等于 am,即找到, 停止查找;否则,若 X 大于 am,替换下限 l=m+1,到下半段继续查找;若 X 小于 am,换上限 h=m-1,到上 半段继续查找;如此重复前面的过程直到找到或者 l>h 为止。如果 l>h,说明没有此数,打印找不到信息, 程序结束。 三、 主要仪器设备 Win7 64-bit;Vs2010 32-bit 四、 实验内容与步骤
#include <stdio.h> #include <stdlib.h> void sort(int array[],int n) { int i,j,small,temp; for(i=0;i<n-1;i++) { small=i; for(j=i+1;j<n;j++) //寻找关键字最小的数据元素 if(array[j]<array[small]) small=j; //记住最小元素的下标 if(small!=i) } } int BSearch1(int a[],int x,int low,int high) { //递归查找 //最小下标不为i时交换元素 temp=array[i];array[i]=array[small];array[small]=temp; //选择排序

int mid; if(low>high) return -1; mid=(low+high)/2; if(x==a[mid]) return mid; else if(x<a[mid]) return BSearch1(a,x,low,mid-1); else return BSearch1(a,x,mid+1,high); } int BSearch2(int a[],int x,int l,int h) { int m; while(l <= h) { m = (l + h) / 2; if(a[m] == x) return m; if(a[m] < x) l= m + 1; else h= m - 1; } return -1; } void main() { int i,x,y,m,n; int a[10000]; for(i=0;i<10000;i++) a[i]= rand()%10000; sort(a,10000); printf("请输入要查找数据(递归查找):"); scanf("%d",&m); x=BSearch1(a,m,0,9999); if(x==-1) printf("查找失败,该数据不存在!\n"); else printf("查找成功,下标为%d\n",x); printf("请输入要查找数据(循环查找):"); scanf("%d",&n); y=BSearch2(a,n,0,9999); //循环查找

if(y==-1) printf("查找失败,该数据不存在!\n"); else printf("查找成功,下标为%d\n",y); }

五、

实验数据记录与处理 查找成功

查找失败

六、 实验结果与分析 假设对 n 个元素的折半查找需要消耗的时间为 t(n)。容易知道:

如果 n = 1,则 t(n) = c1 如果 n > 1,则 t(n) = t(n/2) + c2 其中 n/2 需要取整,c1、c2 都是常数 对于正整数 n,可以有: t(n) = t(n/2) + c2 = t(n/4) + 2*c2 = t(n/8) + 4*c2 = ... = t(n/(2 的 k 次方)) + k*c2 一直推演下去,直到 n/(2 的 k 次方)等于 1,也就是 k = log2(n),此时等式变为: t(n) = t(1) + k*c2 = c1 + log2(n)*c2 于是时间复杂度为 log2(n)。log2(n)和 log(n)其实是同样的复杂度,因为它们之间仅仅差了一个常量系 数而已。 七、 问题与建议


相关文章:
实验三:折半查找算法设计.doc
实验三:折半查找算法设计 - 实 课程名称 姓名 实验日期 数据结构 何虹江 2
验证试验-折半查找.doc
数据结构协同上机实验 第三组 验证实验-折半查找一、折半查找-实验目的 对给定...五、算法设计概要- -直方图 ? data 自定义结构,用于存放关键码及关键码出现的...
折半查找算法及程序实现教案.doc
折半查找算法及程序实现教案 - 折半查找算法及程序实现 一、教材分析 教学重点:以图示法方式,演示折半查找算法的基本思想。 教学难点:由折半查找算法的思想到程序...
实验五:查找算法的设计.doc
学校代码: 学 10128 号: 201220905048 《数据结构》实验报告( 题学系专班目:...实验二 折半查找算法设计... 4页 5下载券 实验三:折半查找算法设... ...
数据结构实验---折半查找实验报告.doc
三.实验过程及内容:(对程序代码进行说明和分析,越详细越好,代码排版要整齐,可读性要高) 1、详细阅读折半查找算法的实现过程 2、详细阅读老师提供的程序框架 3、...
数据结构实验三.doc
实验三 排序、查找算法的实现与应用一、实验目的 掌握排序、查找算法的实现和...折半查找算法既可以设计成递归结构的算法,也可以设计成虚幻结构的算法。 九、...
西安石油大学数据结构实验2-折半查找算法设计.doc
西安石油大学数据结构实验2-折半查找算法设计 - 实验报告 课程名称: 上机实验名称: 专业班级: 指导教师: 学生姓名: 学号: 数据结构 折半查找算法设计...
折半查找及其改进(算法与数据结构课程设计).doc
折半查找算法设计; 3、完成基于区间约束对折半查找算法的改进算法的设计; ...在实验编写程序的过程中,遇到了很多的问题,这些在我以前的实验中都是没遇到的,...
实验三 单元测试.doc
实验三 单元测试一、 实验目的 1、 掌握 UNnit 的安装、基本使用方法; 2、 ...(1)、补充完折半插入排序算法 BInsertSort (2)、针对折半查找算法,设计相应...
选择排序算法实验报告.doc
实验三折半查找算法一、实验性质设计 二、实验学时 14 学时 三、实验目的 1、掌握折半查找算法的方法和原理。 2、掌握 java 语言实现该算法的一般流程。 四、...
算法实验报告.doc
08 页实验三 0-1 背包问题的动态规划算法设计???.11 页 实验四 背包问题的...五、算法描述及实验步骤 算法描述: 折半查找法也称为二分查找法,它充分利用了...
实验一 二分搜索算法.pdf
理解分治算法的概念和基本要素; 2、理解递归的概念; 3、掌握设计有效算法的分治...二.实验原理: 二分搜索算法也称为折半查找法,它充分利用了元素间的次序关系,...
线性表的折半查找法.doc
查找算法(设计性) 查找算法(设计性) 实验目的 1、掌握查找的特点。 2、掌握折半查找的基本思想及其算法。 3、熟悉二叉排序树的特点,掌握二叉排序树的插入、删除...
折半查找冒泡排序堆排序.doc
折半查找冒泡排序堆排序 - 数据与结构实验报告 折半查找法、冒泡法与堆排序 一 实验设计: (1)用折半查找法找到需要查找目标的位置 (2)用冒泡法把输入数据从小...
山东科技大学算法设计报告.doc
15 山东科技大学算法设计 指导教师对实验报告的评语成绩: 指导教师签字: 年月日...三、 实验原理 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,...
查找.doc
掌握静态查找表的顺序存储结构; 2. 通过实验,掌握静态查找的算法; 3. 实现折半查找算法。 二、实验内容 1. 存储结构的设计 2. 折半查找算法的实现 3. 折半...
二分搜索算法实验报告.doc
3、 掌握设计有效算法的分治策略; 4、通过二分搜索技术学习分治策略设计技巧; ...三.实验原理二分搜索算法也称为折半查找法,它充分利用了元素间的次序关系,采用...
软件学院数据结构上机实验题目2013.doc
3)删除操作; 4)存取操作;5)查找操作;6)其他相关扩展操作; 3、设计输出函数,...排序算法 必作实验实验项目名称 折半查找算法实现及二叉查找树类实现 实验目的...
西安交大数据结构与算法分析课内实验报告.doc
西安交大数据结构与算法分析课内实验报告_工学_高等教育_教育专区。这是西安交大...三、算法设计(1) 折半查找算法 BinarySearch(max,min,des) mid-<(max+min)...
算法实验报告.doc
算法实验报告 - 实验一 二分查找程序实现,实验二 棋盘覆盖问题(分治法),实验三 0-1背包问题的动态规划算法设计,实验四 背包问题的贪心算法,实验五 最小重量机器...
更多相关文章: