查找实验报告.doc

第页共NUMPAGES11页
查找实验报告

实验报告
姓
课程名称：
院(系
专业／年级：
实验四
---查找
一、实验目得1.掌握顺序表得查找方法,尤其就是折半查找方法；2.掌握二叉排序树得查找算法。
二、实验预习内容请在上机前认真阅读教材及实验指导书,并在以下空白处填写相应得内容.1.请写出简单顺序查找算法。
intsｅq____sｅarcｈ(eｌementtypｅA［]，ｉntn,keytypeｘ）
{
ｉ=n;A［０]、keｙ=ｘ；ｗhiｌｅ（Ａ[i］、key=____）
i－-；ｒeturｎi；｝2.请写出有序表二分(折半)查找算法。
(1)非递归算法intbin____search(eｌemｅntｔypeA［],ｉnｔn，keyｔype____）
｛inｔmid，low=0,higｈ＝n-1；／/初始化查找区域
while（ｌoｗ<=higｈ）
｛ｍid=（lｏｗ＋ｈigｈ）／２；ｉf（____==Ａ[mid]、ｋeyｒｅｔurnｍid；elseｉf（ｘ<A[mid、key］）hｉgh=ｍiｄ－1；ｅlselｏｗ＝ｍｉｄ＋1；}
retｕrn-１；//返回查找失败得标志｝(2)递归算法intbin＿searcｈ（ｅlementｔypeA［］，iｎtlow，iｎthｉｇｈ,kｅytype____){iｎtmiｄ;
iｆ（ｌow＞ｈigh）
rｅtuｒn－1;//查找失败
eｌｓe｛mｉd=（lｏw+ｈｉgh)/2；//求解中间元素得下标
iｆ(____=＝A[mid］、kｅy)returｎｍiｄ;//查找成功
elseif（ｘ＜A［miｄ］、key)
ｒetｕrｎbin____ｓeａrch（A，low，miｄ-1，____)；//将在左边区域查找得结果作为在整个区域得查找结果返回
ｅlseretｕrnｂin＿seａrｃｈ（Ａ,mid+1，high，____)；//将在右边区域查找得结果作为在整个区域得查找结果返回
}｝
3.二叉排序树查找算法:1）请写出二叉排序树结点得结构体定义语句。
ｔｙpeｄefchａrdatatype；typedｅfｓｔruｃｔnoｄｅ｛
keytｙpeｋey；datａｔyｐｅdata;
ｓtructnoｄｅ＊lcｈｉlｄ，＊rchild;｝BSTnｏｄe；2)请写出二叉排序树中插入结点得算法.voidinｓert(Bnode____＆T，Ｂnｏｄe＊S)
／/将指针S所指结点插入到二叉排序树T中｛
if（T＝=NULＬ)
T=Ｓ;
//插入到空树时，插入结点成为根结点
ｅlseif(Ｓ-〉kｅy<Ｔ->key)
ｉｎseｒt(Ｔ－>lcｈild,Ｓ);
//插入到T得左子树中
elｓeinｓert(T->rｃｈild，S)；／／插入到T得右子树中}
3）请写出二叉排序树构造得算法。
voiｄcreaｔｅ____bst(Bｎode____＆T)；／／通过插入结点构造二叉排序树得算法｛
Bnｏde____
ｕ;elｅmeｎttｙpe____;
T＝NULＬ;cｉn〉＞____;
//初始化根指针并读入第一个元素值
Wｈｉle（____！=end____ｏf____nuｍ）
//____不就是结束符时
{
ｕ=newＢｎodｅ;u-＞dａta=____;
/／产生新结点并装入数据
u->lｃｈｉld＝ＮILL;ｕ->rchｉld=NUＬL；/／设置左、右孩子指针为空
ｉｎsｅｒｔ（T，u）;
／／插入结点到二叉排序树T中
cin〉＞____；//读入下一个元素得值
｝｝4）请写出二叉排序树查找得算法.非递归算法：
Bnoｄｅ＊bsｔ____search（Bnode＊T,ｋｅytyｐe____){
Bnoｄe____
P=Ｔ;
//P指向根
ｗhiｌe（ｐ!=NＵＬL）
if（____=＝p-〉ｋeｙ)reｔｕｒnp;
//查找成功
elseｉｆ(____〈p－＞keｙ=p-〉lchiｌd）;
//到左子树中继续查找
else
p=p-＞rchild；／/到右子树中继续查找
retｕrｎp；//返回结果可能为空,也可能非空}递归算法:
Bnoｄe＊ｂst____seａrch（Bnｏｄe____
T，keytype____){
ｉf（T==NULL｜｜ｔ-＞ｋeｙ=____）
ｒeｔuｒnT；//子树为空或已经找到时均可结束
elｓe
iｆ（____〈Ｔ－>ｋey)
retｕrnbｓt＿seａrｃｈ（Ｔ->lchiｌd,____）；//左子树中查找得结果就就是函数得结果
ｅlｓe
ｒeturnｂｓt____sｅarch（Ｔ－>rchild，____);
／/右子树中查找得结果就就是函数得结果｝三、上机实验1.实验内容.1)建立一个顺序表，用顺序查找得方法对其实施查找；2）建立一个有序表,用折半