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

班级：计算机11-2 学号：40 姓名：朱报龙 成绩：_实验十 查找技术验证实验一、折半查找验证1. 实验目的 掌握折半查找算法的基本思想； 掌握折半查找算法的实现方法； 掌握折半查找算法的时间性能。2. 实验内容对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素.一、 设计与编码#include using namespace std;#define N 15 /定义常量N 为数组长度void find(int arr,int key,int i) /折半查找函数int low=0,high=N-1,mid,j=0; /j计数查找次数while(low=high)mid=(low+high)/2; /取中间位+j;printf(n 第%2d次查找 low=%2d high=%2d mid=%2d ,j,low,high,mid); /显示每次查找低中高位，查找次数if(arrmid=key) /查到数据，跳出循环break;if(arrmidkey) /查找的KEY大于中位值，查后半部low=mid+1;elsehigh=mid-1; /查找的KEY小于中位值，查前半部if(low=high) /查到数据 printf(nn经过总共%2d次查找，找到该数字，该数字位于数组第%d 位,nn,j,mid+1);/显示查到的数据的值，下标值，总查找次数elseprintf(nn没有找到!); /显示没有找到void main()int arrN,key,i;printf(n折半查找验证程序，设定被查数据有位，设定为：n);for(i=0;i0) find(arr,key,N); /调用折半查找函数printf(n请输入要查询的数字（，输入小于等于零的数字退出验证程序）:);scanf(%d,&key); /输入KEY a) 程序运行的结果如何？二、二叉排序树的建立1. 实验目的 掌握二叉排序树定义和特性； 掌握二叉排序树的建立方法； 实现基于二叉排序树的查找技术； 掌握二叉排序树的查找性能。2. 实验内容 对给定的一组无序序列，建立一棵二叉排序树； 对建立的二叉排序树实现查找操作。二、 设计与编码#includeusing namespace std;class BTpublic :BT(void)/构造函数void InitBiTree(BiTree *t);coutlchild);coutkeyrchild); /查找数据BiTree SearchBST(BiTree t, int k) BiTree p;p=t;while(p!=NULL)&(p-key!=k)if(kkey) p=p-lchild;else p=p-rchild;return(p);/插入数据void InsertBST(BiTree *t,int k)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) *t=p;else if (kkey)f-lchild=p;else f-rchild=p;/在二叉排序树*t中删除关键字为k的结点BT()cout调用析构函数释放!endl;/ 析构private:;/class BTint main()BT bt;/class BT创建对象btBT:BiTree t=NULL,p;int key,q=1;bt.InitBiTree(&t);cout请输入关键字的值,以0结束:key; while(key)bt.InsertBST(&t,key); cinkey; cout中序遍历建立的二叉排序树的序列为:; bt.InorderBiTree(t); coutendl; cout请输入要插入的结点的关键字的值:key; bt.InsertBST(&t,key); cout插入后的二叉排序树的中序序列为:endl; bt.InorderBiTree(t); coutendl; cout请输入要查找的结点的关键字的值:key; p=bt.SearchBST(t,key)