查找实验报告

查找实验报告实验报告姓课程名称：院(系专业年级：实验四- - 查找一、实验目得 1.掌握顺序表得查找方法,尤其就是折半查找方法； 2.掌握二叉排序树得查找算法。二、实验预习内容 请在上机前认真阅读教材及实验指导书 , 并在以下空白处填写相应得内容 .1.请写出简单顺序查找算法。int sq_sarc(eementtyp A，nt n, keytype =n;A、ke=； hii、key=_i-； etur i； 2.请写出有序表二分(折半)查找算法。(1)非递归算法 int bin_search(eemntype A,n n，keyype _ in mid，low=0,hign-1；/初始化查找区域whileo=hig id=lig；f_=mid、ey urn id；else fAmid、keyhgh=i1；lse l1；retrn -；/返回查找失败得标志 (2)递归算法 int binsearclementype A，it low，it h,kytype _) it mi;i owighrtun 1;/查找失败ee md=lw+gh)/2；/求解中间元素得下标i( _=Amid、ky ) retur i;/查找成功else if Ami、key )etr bin_erchA，low，mi-1，_)；/将在左边区域查找得结果作为在整个区域得查找结果返回lse retrn inser,mid+1，high，_)；/将在右边区域查找得结果作为在整个区域得查找结果返回 3.二叉排序树查找算法: 1请写出二叉排序树结点得构造体定义语句。peef chr datatype； typedf ru no keytpe ey；daty data;truct no lcl， rchild; BSTne；2)请写出二叉排序树中插入结点得算法.void inert (Bnode _T，ne S)/将指针 S 所指结点插入到二叉排序树 T 中 if T=NUL)T=;/插入到空树时，插入结点成为根结点lse if (-kykey)set (lcild,);/插入到 T 得左子树中ele inert(T-rild，S)；插入到 T 得右子树中 3请写出二叉排序树构造得算法。voi crea_bst(Bode _T)； 通过插入结点构造二叉排序树得算法 Bnde _;elmettpe _;TNUL;cn_;/初始化根指针并读入第一个元素值Wle _！=end_f_nu/_ 不就是完毕符时 =new od; u-dta=_;/产生新结点并装入数据u-lldILL;-rchld=NUL；/设置左、右孩子指针为空s T，u;插入结点到二叉排序树 T 中cin_； /读入下一个元素得值 4请写出二叉排序树查找得算法. 非递归算法：Bno bs_searchBnode T,ytye _) Bnoe _P=;/P 指向根hie !=NLif _=p-e) ren p;/查找成功else ( _pke=p-lchid;/到左子树中继续查找elsep=p-rchild；/到右子树中继续查找retr p；/返回结果可能为空,也可能非空 递归算法: Bnoe st_serchBne _T，keytype _) f T=NULL -e=_eun T；/子树为空或已经找到时均可完毕elei_ey)retrn btser-lchid, _；/左子树中查找得结果就就是函数得结果leeturn t_sarchrchild， _);/右子树中查找得结果就就是函数得结果 三、上机实验 1.实验内容.1)建立一个顺序表，用顺序查找得方法对其施行查找； 2建立一个有序表,用折半查找得方法对其施行查找; 3建立一个二叉排序树，根据给定值对其施行查找； 4对同一组数据,试用三种方法查找某一一样数据,并尝试进展性能分析p 。2.实验程序。inlude stdo、 #iclude listln0； vid list_creatseqlist _) i ；+eltsl- i-istlen;；_=iatadL int lat_sercsels L) nt ; ;nelil-Li L-data0=_;whilL-dat！=_-；return i; n irst_earchseqst Lit ,n；n=L-listl;)+i;nLi； nruter return 1； i bin_searchsqlst Lin mid，low=1,high=L-lstlen；hgih=aai);dim nruere i_ ncludetring、 inclde tpef truc BTnde int data；sc Bnoe lild，rhild； BTnod，no; voi insertBne &;T，BdeS)LN=Tfi；ST )ta-child,; void reatebaBnod T) Bnoe u; ；_ t ;LUN= intf“put number：);)_&;,”(fn 1！_eihw ；)ednTBfoezisolam)_ednB(=u；_=atd-uu-childLL； u-hild=NUL； iner,u； ；)”：rebmun a tupftir;)_,”dnacs Bnoe bsterc(Be T，t _) _=atd-T|U=Tfretrn ； )_atad-T(fi esle ；)_，lihl-Thraes_sb ruter els rturn t_arch-rcild，_); int anint _；p,T edonB prinf”请先建立一棵二叉排序树：”；“n”ftnip ceatebatT);:字数得找查要您入输请(nirpscnf”%d，_)；;_，T(hcraestsb=p )LLN=!(fi prnf“已找到您要查找得数!； sle；”!数得找查要您有没！起不对&;(ftir ;)”(ftnrp ;0 nt 、实验结果。四、实验总结实验过程中出现得问题、解决方法、结果或其它问题：1、输入程序时得手误2、粗心漏写程序3、程序格式错误 解决方法：编译后根据错误提示改正 结果：程序正确运行,截图并完成实验报告第 11 页 共 11 页