实验八 查找及应用实验报告.docx
《实验八 查找及应用实验报告.docx》由会员分享，可在线阅读，更多相关《实验八 查找及应用实验报告.docx（12页珍藏版）》请在冰点文库上搜索。
实验八查找及应用实验报告
实验名称
查找及其应用
实验日期
2019.12.02
实验成绩
1、实验目的：
（1）掌握在数组上进行各种查找的方法和算法
（2）深刻理解各种方法的特点，并能灵活运用
（3）加深对查找的理解，逐步培养解决实际问题的编程能力
2、实验内容：
1、设计一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法查找关键字5的过程。
2、设计一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用二分查找法查找关键字9的过程。
3、设计一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：
（1）由{4,9,0,1,8,6,3,5,2,7}创建一颗二叉排序bt并以括号表示输出。
（2）判断bt是否为一颗二叉排序树。
（3）查找关键字为6的结点，并输出其查找路径。
（4）分别删除bt中关键字为4和5的节点，并输出删除后的二叉排序树。
3、核心算法或代码片段：
代码片段1：
#include
#defineMAXL100//定义表中最多记录个数
typedefintKeyType;
typedefcharInfoType[10];
typedefstruct
{
KeyTypekey;//KeyType为关键字的数据类型
InfoTypedata;//其他数据
}NodeType;
typedefNodeTypeSeqList[MAXL];//顺序表类型
intSeqSearch（SeqListR,intn,KeyTypek）//顺序查找算法
{
inti=0;
while（i=k）
{
printf（"%d",R[i].key）;
i++;//从表头往后找
}
if（i>=n）
return-1;
else
{
printf（"%d",R[i].key）;
returni;
}
}
intmain（）
{
SeqListR;
intn=10,i;
KeyTypek=5;
inta[]={3,6,2,10,1,8,5,7,4,9};
for（i=0;iR[i].key=a[i];
printf（"关键字序列:
"）;
for（i=0;iprintf（"%d",R[i].key）;
printf（"\n"）;
printf（"查找%d所比较的关键字:
\n\t",k）;
if（（i=SeqSearch（R,n,k））!
=-1）
printf（"\n元素%d的位置是%d\n",k,i）;
else
printf（"\n元素%d不在表中\n",k）;
printf（"\n"）;
}
代码片段2：
#include
#defineMAXL100//定义表中最多记录个数
typedefintKeyType;
typedefcharInfoType[10];
typedefstruct
{
KeyTypekey;//KeyType为关键字的数据类型
InfoTypedata;//其他数据
}NodeType;
typedefNodeTypeSeqList[MAXL];//顺序表类型
intBinSearch（SeqListR,intn,KeyTypek）//二分查找算法
{
intlow=0,high=n-1,mid,count=0;
while（low<=high）
{
mid=（low+high）/2;
printf（"第%d次比较:
在[%d,%d]中比较元素R[%d]:
%d\n",++count,low,high,mid,R[mid].key）;
if（R[mid].key==k）//查找成功返回
returnmid;
if（R[mid].key>k）//继续在R[low..mid-1]中查找
high=mid-1;
else
low=mid+1;//继续在R[mid+1..high]中查找
}
return-1;
}
intmain（）
{
SeqListR;
KeyTypek=9;
inta[]={1,2,3,4,5,6,7,8,9,10},i,n=10;
for（i=0;iR[i].key=a[i];
printf（"关键字序列:
"）;
for（i=0;iprintf（"%d",R[i].key）;
printf（"\n"）;
printf（"查找%d的比较过程如下:
\n",k）;
if（（i=BinSearch（R,n,k））!
=-1）
printf（"元素%d的位置是%d\n",k,i）;
else
printf（"元素%d不在表中\n",k）;
return0;
}
代码片段3：
#include
#include
#defineMaxSize100
typedefintKeyType;//定义关键字类型
typedefcharInfoType;
typedefstructnode//记录类型
{
KeyTypekey;//关键字项
InfoTypedata;//其他数据域
structnode*lchild,*rchild;//左右孩子指针
}BSTNode;
intpath[MaxSize];//全局变量,用于存放路径
voidDispBST（BSTNode*b）;//函数说明
intInsertBST（BSTNode*&p,KeyTypek）;
BSTNode*CreatBST（KeyTypeA[],intn）;
voidDispBST（BSTNode*bt）;
intJudgeBST（BSTNode*bt）;
intSearchBST（BSTNode*bt,KeyTypek）;
voidDelete1（BSTNode*p,BSTNode*&r）;
voidDelete（BSTNode*&p）;
intDeleteBST（BSTNode*&bt,KeyTypek）;
intInsertBST（BSTNode*&p,KeyTypek）//在以*p为根节点的BST中插入一个关键字为k的节点
{
if（p==NULL）//原树为空,新插入的记录为根节点
{
p=（BSTNode*）malloc（sizeof（BSTNode））;
p->key=k;p->lchild=p->rchild=NULL;
return1;
}
elseif（k==p->key）
return0;
elseif（kkey）
returnInsertBST（p->lchild,k）;//插入到*p的左子树中
else
returnInsertBST（p->rchild,k）;//插入到*p的右子树中
}
BSTNode*CreatBST（KeyTypeA[],intn）
//由数组A中的关键字建立一棵二叉排序树
{
BSTNode*bt=NULL;//初始时bt为空树
inti=0;
while（iif（InsertBST（bt,A[i]）==1）//将A[i]插入二叉排序树T中
{
printf（"第%d步,插入%d:
",i+1,A[i]）;
DispBST（bt）;printf（"\n"）;
i++;
}
returnbt;//返回建立的二叉排序树的根指针
}
voidDispBST（BSTNode*bt）
//以括号表示法输出二叉排序树bt
{
if（bt!
=NULL）
{
printf（"%d",bt->key）;
if（bt->lchild!
=NULL||bt->rchild!
=NULL）
{
printf（"（"）;
DispBST（bt->lchild）;
if（bt->rchild!
=NULL）printf（","）;
DispBST（bt->rchild）;
printf（"）"）;
}
}
}
KeyTypepredt=-32767;//predt为全局变量,保存当前节点中序前趋的值,初值为-∞
intJudgeBST（BSTNode*bt）//判断bt是否为BST
{
intb1,b2;
if（bt==NULL）//空二叉树是排序二叉树
return1;
else
{
b1=JudgeBST（bt->lchild）;//返回对左子树的判断，不是返回0，否则返回1
if（b1==0||predt>=bt->key）//当左子树不是二叉排序树，或中序前趋（全局变量）大于当前根结点时
return0;//返回“不是二叉排序树”
predt=bt->key;//记录当前根为右子树的中序前趋
b2=JudgeBST（bt->rchild）;//对右子树进行判断
returnb2;
}
}
intSearchBST（BSTNode*bt,KeyTypek）
//以递归方式输出从根节点到查找到的节点的路径
{
if（bt==NULL）
return0;
elseif（k==bt->key）
{
printf（"%3d",bt->key）;
return1;
}
elseif（kkey）
SearchBST（bt->lchild,k）;//在左子树中递归查找
else
SearchBST（bt->rchild,k）;//在右子树中递归查找
printf（"%3d",bt->key）;
}
voidDelete1（BSTNode*p,BSTNode*&r）
//当被删*p节点有左右子树时的删除过程
{
BSTNode*q;
if（r->rchild!
=NULL）
Delete1（p,r->rchild）;//递归找最右下节点
else//找到了最右下节点*r
{
p->key=r->key;//将*r的关键字值赋给*p
q=r;
r=r->lchild;//将*r的双亲节点的右孩子节点改为*r的左孩子节点
free（q）;//释放原*r的空间
}
}
voidDelete（BSTNode*&p）
//从二叉排序树中删除*p节点
{
BSTNode*q;
if（p->rchild==NULL）//*p节点没有右子树的情况
{
q=p;p=p->lchild;free（q）;
}
elseif（p->lchild==NULL）//*p节点没有左子树的情况
{
q=p;p=p->rchild;free（q）;
}
elseDelete1（p,p->lchild）;//*p节点既有左子树又有右子树的情况
}
intDeleteBST（BSTNode*&bt,KeyTypek）
//在bt中删除关键字为k的节点
{
if（bt==NULL）return0;//空树删除失败
else
{
if（kkey）
returnDeleteBST（bt->lchild,k）;//递归在左子树中删除关键字为k的节点
elseif（k>bt->key）
returnDeleteBST（bt->rchild,k）;//递归在右子树中删除关键字为k的节点
else//k=bt->key的情况
{
Delete（bt）;//调用Delete（bt）函数删除*bt节点
return1;
}
}
}
intmain（）
{
BSTNode*bt;
KeyTypek=6;
inta[]={4,9,0,1,8,6,3,5,2,7},n=10;
printf（"创建一棵BST树:
"）;
printf（"\n"）;
bt=CreatBST（a,n）;
printf（"BST:
"）;DispBST（bt）;printf（"\n"）;
printf（"bt%s\n",（JudgeBST（bt）?
"是一棵BST":
"不是一棵BST"））;
printf（"查找%d关键字（递归,逆序）:
",k）;SearchBST（bt,k）;
//SearchBST（bt,k,path,-1）;
printf（"\n删除操作:
\n"）;
printf（"原BST:
"）;DispBST（bt）;printf（"\n"）;
printf（"删除节点4:
"）;
DeleteBST（bt,4）;
DispBST（bt）;printf（"\n"）;
printf（"删除节点5:
"）;
DeleteBST（bt,5）;
DispBST（bt）;
printf（"\n"）;
}
4、实验结果分析及总结体会：
实验结果：
1.
2.
3：
总结体会：
通过本次实验学会了顺序查找和二分查找的区别，认清了两种方法的不同之处，相比之下，二分查找比顺序查找更能节约空间和时间，利用二分查找要优越与顺序查找，也更符合人们的思想，对排序的算法有了更深的认识，体会到了算法的优越。
升级会员 