数据结构查找技术验证实验报告.doc

《数据结构查找技术验证实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级：计算机11-2学号：40姓名：朱报龙成绩：_________实验十查找技术验证实验一、折半查找验证1.实验目的⑴掌握折半查找算法的基本思想；⑵掌握折半查找算法的实现方法；⑶掌握折半查找算法的时间性能。2.实验内容对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素.一、设计与编码#includeusingnamespacestd;#defineN15//定义常量N为数组长度voidfind(intarr[],intkey,inti)//折半查找函数{intlow=

2、0,high=N-1,mid,j=0;//j计数查找次数while(low<=high){mid=(low+high)/2;//取中间位++j;printf("第%2d次查找low=%2dhigh=%2dmid=%2d",j,low,high,mid);//显示每次查找低中高位，查找次数if(arr[mid]==key)//查到数据，跳出循环break;if(arr[mid]

3、查前半部}if(low<=high)//查到数据printf("经过总共%2d次查找，找到该数字，该数字位于数组第%d位,",j,mid+1);//显示查到的数据的值，下标值，总查找次数elseprintf("没有找到!");//显示没有找到}voidmain(){intarr[N],key,i;printf("折半查找验证程序，设定被查数据有位，设定为：");for(i=0;i

4、r[i]);}printf("请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:");scanf("%d",&key);//输入KEYwhile(key>0){find(arr,key,N);//调用折半查找函数printf("请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:");scanf("%d",&key);//输入KEY}}a)程序运行的结果如何？二、二叉排序树的建立1.实验目的⑴掌握二叉排序树定义和特性；⑵掌握二叉排序树的建立方法；⑶实现基于二叉排序树的查找技术

5、；⑷掌握二叉排序树的查找性能。2.实验内容⑴对给定的一组无序序列，建立一棵二叉排序树；⑵对建立的二叉排序树实现查找操作。二、设计与编码#includeusingnamespacestd;classBT{public:BT(void)//构造函数{voidInitBiTree(BiTree*t);cout<<"初始化结束！";}//存储结构——二叉链表typedefstructLnode{intkey;structLnode*lchild,*rchild;}BiTnode,*Bi

6、Tree;//创建、初始化voidInitBiTree(BiTree*t){*t=NULL;//置空}//输出中序遍历二叉树voidInorderBiTree(BiTreep){if(p)//p为空，则空操作，否则继续执行{InorderBiTree(p->lchild);cout<key<<"";InorderBiTree(p->rchild);}}//查找数据BiTreeSearchBST(BiTreet,intk){BiTreep;p=t;while((p!=NULL)&&(p->key

7、!=k))if(kkey)p=p->lchild;elsep=p->rchild;return(p);}//插入数据voidInsertBST(BiTree*t,intk){BiTnode*f,*p=*t;while(p){if(p->key==k)return;f=p;p=(kkey)?p->lchild:p->rchild;}p=(BiTree)malloc(sizeof(BiTnode));p->key=k;p->lchild=p->rchild=NULL;if(*t==NULL

8、)*t=p;elseif(kkey)f->lchild=p;elsef->rchild=p;}//在二叉排序树*t中删除关键字为k的结点~BT(){cout<<"调用析构函数释放!"<