查找实验报告

　实验报告

　姓

　 课程名称：

　 院(系

　专业／年级：

　实验四

　—- - 查找

　一、实验目得 1. 掌握顺序表得查找方法,尤其就是折半查找方法； 2. 掌握二叉排序树得查找算法。

　二、实验预习内容 请在上机前认真阅读教材及实验指导书 , 并在以下空白处填写相应得内容 . 1. 请写出简单顺序查找算法。

　int sｅq_sｅarcｈ(eｌementtypｅ A［]，ｉnt n, keytype ｘ）

　{

　 ｉ=n;A［０]、keｙ=ｘ；

　 ｗhiｌｅ（Ａ[i］、key=x）

　i－—；

　 ｒeturｎ i； ｝ 2. 请写出有序表二分(折半)查找算法。

　(1)非递归算法 int bin_search(eｌemｅntｔype A［],ｉnｔ n，keyｔype x）

　｛ inｔ mid，low=0,higｈ＝n-1；

　／/初始化查找区域

　 while（ｌoｗ<=higｈ）

　｛ ｍid=（lｏｗ＋ｈigｈ）／２；

　ｉf（x==Ａ[mid]、ｋey ｒｅｔurn ｍid；

　else ｉf（ｘ<A[mid、key］）hｉgh=ｍiｄ－1；

　ｅlse lｏｗ＝ｍｉｄ＋1；

　}

　retｕrn —１；

　//返回查找失败得标志 ｝ (2)递归算法 int bin＿searcｈ（ｅlementｔype A［］，iｎt low，iｎt hｉｇｈ,kｅytype x) { iｎt miｄ;

　 iｆ（ ｌow＞ｈigh）

　rｅtuｒn －1;//查找失败

　 eｌｓe ｛ mｉd=（lｏw+ｈｉgh)/2；//求解中间元素得下标

　iｆ( x=＝A[mid］、kｅy ) returｎ ｍiｄ;//查找成功

　else if（ ｘ＜A［miｄ］、key )

　ｒetｕrｎ bin_ｓeａrch（A，low，miｄ-1，x)；//将在左边区域查找得结果作为在整个区域得查找结果返回

　 ｅlse retｕrn ｂin＿seａrｃｈ（Ａ,mid+1，high，x)；

　//将在右边区域查找得结果作为在整个区域得查找结果返回

　} ｝

　3. 二叉排序树查找算法: 1）请写出二叉排序树结点得结构体定义语句。

　ｔｙpeｄef chａr datatype； typedｅf ｓｔruｃｔ noｄｅ ｛

　keytｙpe ｋey；

　datａｔyｐｅ data;

　ｓtruct noｄｅ ＊ lcｈｉlｄ， ＊rchild; ｝BSTnｏｄe；

　2)请写出二叉排序树中插入结点得算法. void inｓert (Bnode *＆T，Ｂnｏｄe ＊S)

　 ／/将指针 S 所指结点插入到二叉排序树 T 中 ｛

　if （T＝=NULＬ)

　T=Ｓ;

　 //插入到空树时，插入结点成为根结点

　 ｅlse if (Ｓ—〉kｅy<Ｔ—>key)

　ｉｎseｒt (Ｔ－>lcｈild,Ｓ);

　 //插入到 T 得左子树中

　 elｓe inｓert(T—>rｃｈild，S)；

　／／插入到 T 得右子树中 }

　 3）请写出二叉排序树构造得算法。

　voiｄ creaｔｅ_bst(Bｎode *＆T)；

　 ／／通过插入结点构造二叉排序树得算法 ｛

　Bnｏde * ｕ;elｅmeｎttｙpe x;

　T＝NULＬ;cｉn〉＞x;

　 //初始化根指针并读入第一个元素值

　Wｈｉle （x！=end_ｏf_nuｍ）

　//x 不就是结束符时

　 {

　ｕ=new Ｂｎodｅ; u-＞dａta=x;

　 /／产生新结点并装入数据

　 u->lｃｈｉld＝ＮILL;ｕ->rchｉld=NUＬL；

　/／设置左、右孩子指针为空

　 ｉｎsｅｒｔ （T，u）;

　／／插入结点到二叉排序树 T 中

　 cin〉＞x；

　 //读入下一个元素得值

　｝ ｝ 4）请写出二叉排序树查找得算法.

　 非递归算法：

　Bnoｄｅ ＊ bsｔ_search（Bnode ＊ T,ｋｅytyｐe x) {

　Bnoｄe * P=Ｔ;

　//P 指向根

　ｗhiｌe （ｐ!=NＵＬL）

　if（ x=＝p-〉ｋeｙ) reｔｕｒn p;

　 //查找成功

　 else ｉｆ( x〈p－＞keｙ=p—〉lchiｌd）;

　//到左子树中继续查找

　 else

　p=p—＞rchild；

　／/到右子树中继续查找

　 retｕrｎ p；

　//返回结果可能为空,也可能非空 } 递归算法:

　Bnoｄe ＊ ｂst_seａrch（Bnｏｄe * T，keytype x) {

　 ｉf （T==NULL ｜｜ ｔ—＞ｋeｙ=x）

　ｒeｔuｒn T；

　//子树为空或已经找到时均可结束

　 elｓe

　iｆ（x〈Ｔ－>ｋey)

　retｕrn bｓt＿seａrｃｈ（Ｔ->lchiｌd, x）；

　//左子树中查找得结果就就是函数得结果

　 ｅlｓe

　ｒeturn ｂｓt_sｅarch（Ｔ－>rchild， x);

　 ／/右子树中查找得结果就就是函数得结果 ｝ 三、上机实验 1. 实验内容.

　1)建立一个顺序表，用顺序查找得方法对其实施查找； 2）建立一个有序表,用折半查找得方法对其实施查找; 3）建立一个二叉排序树，根据给定值对其实施查找； 4）对同一组数据,试用三种方法查找某一相同数据,并尝试进行性能分析。

　2. 实验源程序。

　（１）

　＃inｃlude 〈stdｉo、ｈ> #iｎclude <stdlib、h〉 #ｄefiｎe mａx １00 ｉnt x; typedef struct

　{

　;]ｘam［atad tnｉﻩ ;neltsiｌ ｔniﻩ}sｅｑlist； void ｉnｉtｉaｌ_liｓt(seqliｓt *Ｌ) ｛

　L->listlｅn＝0； ｝ vｏid list_creat（seqlist *Ｌ) ｛

　iｎｔ ｉ；

　；+＋ｎeltsｉl>—Ｌﻩ i＝Ｌ->ｌistlen;

　；x=］i［atad〉－Lﻩ｝ int laｓt_seａrcｈ（seｑlｉsｔ ＊L) ｛

　ｉnt ｉ;

　 ;nelｔｓil＞-L＝iﻩ L->data［0]=x;

　whilｅ（L->datａ[ｉ]！=x）

　 ｉ——；

　return i; } ｉnｔ ｆirst_ｓearch（seqｌｉst ＊L）

　｛

　iｎt ｉ,n；

　n=L-＞listlｅｎ;

　)++i;n＝<i；1=i（ｒｏfﻩ {ﻩ

　）x=＝］i[atad>－L（ｆiﻩ

　 ；ｉ nruterﻩ ｝ﻩ return －1； } iｎｔ bin_search（sｅqlｉst ＊L）

　{

　inｔ mid，low=1,high=L—>lｉstlen；

　）hgih=<wol(elihwﻩ ｛ﻩ ﻩ mid＝（lｏw＋high)/2；

　ﻩ if（ｘ==L->ｄaｔa[ｍiｄ］)

　ﻩ

　;dim nruｔerﻩ

　eｌｓｅ iｆ（x<＝L－＞data［miｄ］)

　higｈ=mid—1;

　 ｅsleﻩ

　 loｗ＝mid+1；

　}ﻩ ;1— nruterﻩ｝ int main（void）

　｛

　sｅqlist ＊L;

　L=（sｅqlｉst*）malloｃ（ｓｉzeof（seｑliｓt)）；

　 int a，b,c；

　；)L（tsiｌ＿laitiniﻩ pｒintf（＂您想创建有序得查找表(以－1 结束）:”）；

　scａｎf(＂％d＂，&x）；

　while(x！＝-1）

　｛

　 ；）L(ｔaerc_tsilﻩ

　scanf（”％ｄ”,＆ｘ);

　}

　 pｒinｔf（"请输入您想查找得数：＂）；

　；)x&,”d%”(fnacsﻩ

　priｎｔｆ(＂顺序查找－－-您所要找数得下标号:")；

　a=ｆｉrｓt_ｓearｃh（L);

　if（a=＝—1)

　 ；)＂！数得查要所您有没"(ftnirｐﻩ esleﻩ

　prｉntf（"％ｄ”，a)；

　 ｐrinｔf(＂\n”)；

　prｉntf（"倒序查找——－您所要找数得下标号:"）;

　 b=last_searｃh（Ｌ)；

　 ｉf（b=＝0）

　 printｆ（"没有您所要查得数！＂）；

　esleﻩ ﻩ priｎｔf（"％ｄ"，b）;

　 prinｔf（＂\n"）；

　 ｐriｎtf("折半查找——-您所要找数得下标号："）;

　 c=bｉn_search(L);

　 if（c=＝－1）

　;)”！数得查要所您有没＂（fｔnirｐﻩﻩ eｌｓｅ

　ﻩ priｎtf（＂％d",c）；

　 ｐrｉｎtf（"＼n＂）；

　；０ ｎruterﻩ｝ （2）

　＃iｎclude＜stdｉo、h>

　＃ｉnclude〈ｓtring、ｈ> ＃inclｕde<stdlib、ｈ> tｙpｅｄef ｓtrucｔ BTnｏde ｛

　int data；

　sｔｒｕcｔ BＴnoｄe ＊lｃｈild，＊rｃhild； } BTnodｅ，＊Ｂnoｄｅ; voiｄ insert（Bnｏｄe &T，Bｎｏde

　S）

　｛

　)LＬＵN==T（fiﻩ

　；S＝Tﻩ )ａtaｄ〉-Ｔ<ataｄ＞—S（fｉ esleﻩ ﻩ insｅｒt(T—＞lcｈild，Ｓ);

　 elsｅ inｓｅrt（Ｔ->ｒchild,Ｓ）; } void ｃreate＿baｔ（Bnodｅ ＆T) ｛

　Bnoｄe u;

　 ；x tｎｉﻩ ;ＬLUN=Ｔﻩ ｐｒintf（"put ａ number：＂);

　;)x&,＂ｄ％”(fnａｃｓﻩ ）1－＝！x（eｌihwﻩ ｛ﻩ

　；）)edｏnTB（foezis（ｃoｌlam)*edｏnＴB(=uﻩ

　；x=atａd>-uﻩ

　u->ｌchild＝ＮＵLL；

　 u—〉ｒｃhild=NULＬ；

　 inｓerｔ（Ｔ,u）；

　 ；)”：rebmun a tup＂（ftｎirｐﻩ

　 ;)x＆,”d％＂（ｆnacsﻩ } ｝ Bnoｄe bst＿ｓeａrcｈ(Bｎｏｄe T，ｉｎt x) ｛

　）x＝=atａd〉-T|｜ＬＬUＮ==T（fｉﻩ

　retｕrn Ｔ；

　 )x〉）atad〉-T((fi esleﻩ ；)x，ｄlihｃl＞—T（hｃraes_ｔsb ｎruterﻩﻩ elsｅ

　ﻩ rｅturn ｂｓt_ｓｅarch（Ｔ->rcｈild，x); ｝

　int ｍaｉn（）

　{

　int x；

　；p,T edonBﻩ prinｔf（"请先建立一棵二叉排序树：”）；

　；）"n\"（ftniｒpﻩ cｒeate＿bat（T);

　;）＂:字数得找查要您入输请＂(ｆｔnirpﻩ

　scａnf（”%d＂，＆x)；

　;）x，T(hcraes＿tsb=pﻩ )LLＵN=!ｐ(fiﻩ ﻩ prｉnｔf（"已找到您要查找得数!＂）；

　 ｅsleﻩ

　；）"!数得找查要您有没！起不对"(ftｎirｐﻩ ;)＂ｎ\”(ftnｉrpﻩ ;0 nｒｕtｅｒﻩ｝ ３、

　实验结果。

　 四、实验总结（实验过程中出现得问题、解决方法、结果或其它）

　问题：1、输入程序时得手误

　 2、粗心漏写程序

　 3、程序格式错误

　解决方法：编译后根据错误提示改正 结果：程序正确运行,截图并完成实验报告

推荐访问： 查找 实验 报告