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

1、班级：计算机11-2 学号：40 姓名：朱报龙 成绩：_实验十 查找技术验证实验一、折半查找验证1. 实验目的 掌握折半查找算法的基本思想； 掌握折半查找算法的实现方法； 掌握折半查找算法的时间性能。2. 实验内容对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素.一、 设计与编码#include <iostream>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(

2、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(arrmid<key) /查找的KEY大于中位值，查后半部low=mid+1;elsehigh=mid-1; /查找的KEY小于中位值，查前半部if(low<=high) /查到数据 printf("nn经过总共%2d次查找，找到该数字，该数字位于数组第%

3、d 位,nn",j,mid+1);/显示查到的数据的值，下标值，总查找次数elseprintf("nn没有找到!"); /显示没有找到void main()int arrN,key,i;printf("n折半查找验证程序，设定被查数据有位，设定为：n");for(i=0;i<N;i+) /输入15个排好序的数据arri=i+1;printf("%d ",arri);printf("n请输入要查询的数字（，输入小于等于零的数字退出验证程序）:");scanf("%d",&k

4、ey); /输入KEYwhile(key>0) find(arr,key,N); /调用折半查找函数printf("n请输入要查询的数字（，输入小于等于零的数字退出验证程序）:");scanf("%d",&key); /输入KEY a) 程序运行的结果如何？二、二叉排序树的建立1. 实验目的 掌握二叉排序树定义和特性； 掌握二叉排序树的建立方法； 实现基于二叉排序树的查找技术； 掌握二叉排序树的查找性能。2. 实验内容 对给定的一组无序序列，建立一棵二叉排序树； 对建立的二叉排序树实现查找操作。二、 设计与编码#include<ios

5、tream>using namespace std;class BTpublic :BT(void)/构造函数void InitBiTree(BiTree *t);cout<<"初始化结束！n"/存储结构二叉链表typedef struct Lnodeint key;struct Lnode *lchild,*rchild;BiTnode,*BiTree;/创建、初始化void InitBiTree(BiTree *t)*t=NULL;/置空/输出中序遍历二叉树void InorderBiTree(BiTree p)if(p)/p为空，则空操作，否则继续执

6、行InorderBiTree(p->lchild);cout<<p->key<<" "InorderBiTree(p->rchild); /查找数据BiTree SearchBST(BiTree t, int k) BiTree p;p=t;while(p!=NULL)&&(p->key!=k)if(k<p->key) p=p->lchild;else p=p->rchild;return(p);/插入数据void InsertBST(BiTree *t,int k)BiTnode *f

7、,*p=*t;while(p)if(p->key=k) return;f=p;p=(k<p->key)?p->lchild:p->rchild; p=(BiTree)malloc(sizeof(BiTnode);p->key=k;p->lchild=p->rchild=NULL;if(*t=NULL) *t=p;else if (k<f->key)f->lchild=p;else f->rchild=p;/在二叉排序树*t中删除关键字为k的结点BT()cout<<"调用析构函数释放!"<

8、;<endl;/ 析构private:;/class BTint main()BT bt;/class BT创建对象btBT:BiTree t=NULL,p;int key,q=1;bt.InitBiTree(&t);cout<<"请输入关键字的值,以0结束:"<<endl; cin>>key; while(key)bt.InsertBST(&t,key); cin>>key; cout<<"中序遍历建立的二叉排序树的序列为:" bt.InorderBiTree(t); c

9、out<<endl; cout<<"请输入要插入的结点的关键字的值:"<<endl; cin>>key; bt.InsertBST(&t,key); cout<<"插入后的二叉排序树的中序序列为:"<<endl; bt.InorderBiTree(t); cout<<endl; cout<<"请输入要查找的结点的关键字的值:"<<endl; cin>>key; p=bt.SearchBST(t,key); if(p=NULL) cout<<"没