在二叉排序树中查找关键字为key的记录.docx
《在二叉排序树中查找关键字为key的记录.docx》由会员分享，可在线阅读，更多相关《在二叉排序树中查找关键字为key的记录.docx（10页珍藏版）》请在冰点文库上搜索。
在二叉排序树中查找关键字为key的记录
学院名称
专业班级
实验成绩
学生姓名
学号
实验日期
课程名称
数据结构
实验题目
4查找
一、实验目的与要求
通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。
二、主要仪器设备
Cfree
三、实验内容和原理
2.实习题1
[问题描述]
编写程序实现下面运算:
在二叉排序树中查找关键字为key的记录。
[输入]
排序二叉树，以及要查找的数字（节点）。
[输出]
显示该节点是否存在。
[存储结构]
有序表采用顺序方式存储。
[算法的基本思想]
若二叉排序树为空树，查找失败，返回null或0；
否则，将key与根节点的关键字比较：
若key=根节点的关键字，查找成功；
若key<根节点的关键字，继续在左子树中查找；
若key>根节点的关键字，继续在右子树中查找。
[参考源程序]
#include
#include
#defineNULL0
typedefintKeyType;
typedefstruct{
KeyTypekey;
}ElemType;//元素类型
typedefstructBiTNode{
ElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
BiTreesearchBST（BiTreebt,KeyTypekey）{
/*在二叉排序树bt中查找其关键字等于给定值的结点是否存在，并输出相应信息*/
if（bt==NULL）returnNULL;//在排序二叉树中进行递归查找
elseif（bt->data.key==key）returnbt;
elseif（keydata.key）returnsearchBST（bt->lchild,key）;
elsereturnsearchBST（bt->rchild,key）;
}
voidinsertBST（BiTree*bt,BiTrees）{
/*在二叉排序树中插入一个新结点,即依次插入输入的数*/
if（*bt==NULL）*bt=s;
elseif（s->data.key<（*bt）->data.key）insertBST（&（（*bt）->lchild）,s）;
elseif（s->data.key>（*bt）->data.key）insertBST（&（（*bt）->rchild）,s）;
}
main（）{
charch;
KeyTypekey;
BiTreebt,s;
inti=0;
/*建立一棵二叉排序树，元素从键盘按先序输入，直到输入关键字等于-1为止*/
printf（"\n请输入元素（-1:
结束）：
\n"）;//以-1为结束
scanf（"%d",&key）;
bt=NULL;
while（key!
=-1）{
s=（BiTree）malloc（sizeof（BiTNode））;
（s->data）.key=key;s->lchild=s->rchild=NULL;
insertBST（&bt,s）;
scanf（"%d",&key）;
}//while
/*二叉排序树的查找，可多次查找，并输出查找的结果*/
do{
printf（"\n输入你想要查找的元素：
"）;
scanf（"%d",&key）;
s=searchBST（bt,key）;
if（s!
=NULL）printf（"\n成功!
这个等价元素是%d.\n",s->data.key）;
elseprintf（"\n没有找到!
\n"）;
printf（"\n是否继续?
（y/n）：
"）;
scanf（"%c",&ch）;
ch=getchar（）;
}
while（ch=='y'||ch=='Y'）;
getchar（）;
}//main
实验结果：
五、实验结果与分析
（2）习题1：
采用先序遍历的方式生成二叉树，程序中多次使用的递归的算法。
使程序看起来很简洁。
如果把头结点的生成也放到生成树的函数中，会使程序看起来更加调理。
六、实验心得及体会
查找是很多程序的基础，很多程序中都会用到查找。
比如在线性表的插入和删除时要查找合适的位置。
所以学好查找是很必要的。
本次实验只要是采取了这般查找的方法。
其实还有很多查找的方法。
如顺序查找，索引顺序表查找。
每种查找方法各有优劣。
如折半查找的平均查找长度小于顺序查找，但它要求查找的表为有序的。
所以需将无序表排序成有序表。
这又会浪费运行时间。
编写程序时遇到了很多的困难，如先序生成树更好还是中序生成更好。
太原理工大学学生实验报告
学院名称
计算机科学与技术
专业班级
计Z1002班
实验成绩
学生姓名
郑海兵
学号
2010001420
实验日期
1月2日
课程名称
数据结构
实验题目
5内排序
一、实验目的与要求
通过本次实验，掌握线性表的排序方法，并分析时间复杂度。
二、主要仪器设备
Cfree
三、实验内容和原理
[问题描述]
设计一个用链表表示的直接选择排序算法，并用程序实现。
[输入]
n个数据。
[输出]
n个数据由小到大排列的结果。
[存储结构]
待排序记录顺序存储。
[算法的基本思想]
已知待排序初始序列用单链表存储，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。
r以前为已排序序列，r以后为未排序序列。
再从未排序序列中找出最小结点插入r的后面，让r指向这个结点。
反复执行这个过程，直到排好序。
[参考源程序]
#include
#include
intn;
structNumber{
intdata;
structNumber*next;
};
structNumber*Creat_H（intk）{//创建单链表
structNumber*L;
structNumber*p;
p=（structNumber*）malloc（sizeof（structNumber））;
L=p;
inttemp;
inti;
printf（"\n请输入元素：
"）;
for（i=1;i<=k;i++）{
scanf（"%d",&temp）;
p->data=temp;
if（i==k）{
p->next=NULL;
break;
}
p->next=（structNumber*）malloc（sizeof（structNumber））;
p=p->next;
}//for
returnL;
}//structNumber*Creat_H
structNumber*Sort（structNumber*p）{//直接选择排序
structNumber*max;
structNumber*min;
structNumber*temp;
structNumber*r;
r=p;
intflag=0;
do{
if（flag==0）{//第一次找最小数时的初始化
temp=min=max=r;
}
else{
temp=min=max=r->next;
}//do
while
（1）{//找出最小数
if（min->data<=max->next->data）{
if（max->next->next!
=NULL）{
max=max->next;
}
else{
break;
}
}//if
else{
temp=max;//相当于temp->next=min
min=max->next;
if（max->next->next!
=NULL）{
max=max->next;
}
else{
break;
}
}//else
}//while
（1）
if（temp!
=min）{
if（min->next==NULL）{
temp->next=NULL;
}
else{
temp->next=min->next;
}
if（flag==0）{
r=min;
r->next=p;
p=r;
}
else{
min->next=r->next;
r->next=min;
r=min;
}
}//if
else{//初始化时min就已经指向了最小数
if（flag==0）{//第一次找到最小数
r=min;
p=r;
}
else{
r=min;
}
}//else
flag++;//又排好一个数
if（flag==n-1）{
returnp;
}
}while
（1）;
}
intmain（）{
structNumber*H;
printf（"\n请输入元素个数n（n>=2）：
"）;//输入数据（不得少于2个）
scanf（"%d",&n）;
while（n<2）{
printf（"\nError!
请重新输入元素个数n：
"）;
scanf（"%d",&n）;
}
H=Creat_H（n）;
H=Sort（H）;
printf（"\n排序后的数为：
"）;//数据排序后的序列
while（H!
=NULL）{
printf（"%-4d",H->data）;
H=H->next;
}
printf（"\n"）;
system（"pause"）;
return0;
getchar（）;
}
五、实验结果与分析
习题1：
这题要从前面和后面同时进行处理，只有这样才能保证时间复杂度为O（N）。
六、实验心得及体会
排序有很多种方法，如冒泡排序、直接插入排序、希尔排序、归并排序、选择排序等等。
各个排序的方法各有优劣，时间复杂度各不相同。
习题二中使用的快速排序方法是冒泡排序的改进方法，时间复杂度比较小。
但若初始纪录序列按关键字有序或基本有序时，快速排序退化为冒泡排序。
在实验中学习到很多，每次调试程序都进步不少，以后会多思考，多读程序，使思维更加缜密，调理和清晰，同时也提高自己的提高动手能力。
升级会员 