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

班级：计算机11-2学号：40姓名：朱报龙成绩：_________实验十查找技术验证实验一、折半查找验证1.实验目的⑴掌握折半查找算法的基本思想；⑵掌握折半查找算法的实现方法；⑶掌握折半查找算法的时间性能。2.实验内容对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素.一、设计与编码#includeiostreamusingnamespacestd;#defineN15//定义常量N为数组长度voidfind(intarr[],intkey,inti)//折半查找函数{intlow=0,high=N-1,mid,j=0;//j计数查找次数while(low=high){mid=(low+high)/2;//取中间位++j;printf(\n第%2d次查找low=%2dhigh=%2dmid=%2d,j,low,high,mid);//显示每次查找低中高位，查找次数if(arr[mid]==key)//查到数据，跳出循环break;if(arr[mid]key)//查找的KEY大于中位值，查后半部low=mid+1;elsehigh=mid-1;//查找的KEY小于中位值，查前半部}if(low=high)//查到数据printf(\n\n经过总共%2d次查找，找到该数字，该数字位于数组第%d位,\n\n,j,mid+1);//显示查到的数据的值，下标值，总查找次数elseprintf(\n\n没有找到!);//显示没有找到}voidmain(){intarr[N],key,i;printf(\n折半查找验证程序，设定被查数据有位，设定为：\n);for(i=0;iN;i++)//输入15个排好序的数据{arr[i]=i+1;printf(%d,arr[i]);}printf(\n请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:);scanf(%d,&key);//输入KEYwhile(key0){find(arr,key,N);//调用折半查找函数printf(\n请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:);scanf(%d,&key);//输入KEY}}a)程序运行的结果如何？二、二叉排序树的建立1.实验目的⑴掌握二叉排序树定义和特性；⑵掌握二叉排序树的建立方法；⑶实现基于二叉排序树的查找技术；⑷掌握二叉排序树的查找性能。2.实验内容⑴对给定的一组无序序列，建立一棵二叉排序树；⑵对建立的二叉排序树实现查找操作。二、设计与编码#includeiostreamusingnamespacestd;classBT{public:BT(void)//构造函数{voidInitBiTree(BiTree*t);cout初始化结束！\n;}//存储结构——二叉链表typedefstructLnode{intkey;structLnode*lchild,*rchild;}BiTnode,*BiTree;//创建、初始化voidInitBiTree(BiTree*t){*t=NULL;//置空}//输出中序遍历二叉树voidInorderBiTree(BiTreep){if(p)//p为空，则空操作，否则继续执行{InorderBiTree(p-lchild);coutp-key;InorderBiTree(p-rchild);}}//查找数据BiTreeSearchBST(BiTreet,intk){BiTreep;p=t;while((p!=NULL)&&(p-key!=k))if(kp-key)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=(kp-key)?p-lchild:p-rchild;}p=(BiTree)malloc(sizeof(BiTnode));p-key=k;p-lchild=p-rchild=NULL;if(*t==NULL)*t=p;elseif(kf-key)f-lchild=p;elsef-rchild=p;}//在二叉排序树*t中删除关键字为k的结点~BT(){cout调用析构函数释放!endl;}//析构private:};//classBTintmain(){BTbt;//classBT创建对象btBT::BiTreet=NULL,p;intkey,q=1;bt.InitBiTree(&t);cout请输入关键字的值,以0结束:endl;cinkey;while(key){bt.InsertBST(&t,key);cinkey;}cout中序遍历建立的二叉排序树的序列为:;bt.InorderBiTree(t);coutendl;cout请输入要插入的结点的关键字的值:endl;cinkey;bt.InsertBST(&t,key);cout插入后的二叉排序树的中序序列为:endl;bt.InorderBiTree(t);coutendl;cout请输入要查找的结点的关键字的值:endl;cinkey;p=bt.SearchBST(t,key);if(p==NULL)cout没有查找到该结点endl;elsecout查找到该结点:;coutp-keyendl;system(pause);return0;}a）程序运行结果如何