2023年查找实验报告

姓院（系实验报告课程名称:专业/年级：1ow=mid+1;®return-1;}intmain(void)(seqlist*L;L=(seq1ist*)malloc(sizeof(seqlist));inta,b,c；Anitial_list(L)；oprintf(“你想创建有序的查找表(以・1结束oscanf("%dM,&x)；whi1e(x!=-l)(olist_creat(L);scanf(M%d%&x)；o}printf("请输入你想查找的数厂);oscanf("％d”,&x);printf("顺序查找一一-你所要找数的下标号a=first_search(L);oif(a==-1)oprintf("没有你所要查的数!)1se-printf("％d'a)；printfCXn1')；printf("倒序查找---你所要找数的下标号:")；b=last_search(L);if(b==0)。printf("没有你所要查的数!)吒1se。printf(n%dM,b);printf(u\nH)；printf("折半查找---你所要找数的下标号:")；c=bin_search(L);if(c==-l)。printf(“没有你所要查的数!”)；else。printf(n%dH,c)；printf("\nn);return0;))inc1ude<stdio.h>include<string.h>inc1ude<std1ib.h>typedefstructBTnode(intdata;structBTnode*lchiId,*rchi1d;}BTnode,*Bnode；voidinsert(Bnode&T,BnodeS)oif(T==NULL)T=S;elseif(S->data<T->data)dinsert(T->1child,S);e1seinsert(T->rchi1d,S);)voidcreate_bat(Bnode&T)(oBnodeu;intx；oT=NULL；叩rintf("putanumber:");seanf(n%d”，&x)；whi1e(x!=—1)。u=(BTnode*)malloc(sizeof(BTnode));ou->data=x;u->1child=NULL;。u->rchild=NULL；ginsert(T,u)；叩rintf("putanumber:");oscanf(”％d”,&x);0)}Bnodebst_search(BnodeT,intx)(oif(T==NULL||T->data==x)ooreturnT;oe1seif((T->data)>x)oreturnbst_search(T->1child,x);elseoreturnbst_search(T->rchild,x);intmain（）intx;aBnodeT,p；叩rintf（"请先建立一棵二叉排序树：”）；printf（n\n"）；create_bat（T）;Printf（”请输入你要查找的数字：”）；scanf（n%d”成x）;p=bst_search（T,x）;oif（p!二NULL）。printf（”已找到你要查找的数!）else叩rintf（”对不起！没有你要查找的数!）叩rimf八nn）；return0；

实验结果。■'C:\Users\stu\Desktop\Debug\shunxubiao.exe你想创建有序的查找表＜以T结束）式2536-1倒序查戊yh.

挤辛查莪—r?数的下标号;3遨的下标号：3

之数的下标号：3Pressanykeytocontinue'C:\Users\stu\Desktop\Debug\shunxubiao.exe"你想创建有序的查找表〈以T结束〉入查查查：48数的下我-一你所要找数的下

anykeytocontinue有有有没没没:::号号号数数数

查查查

要要要"C:\Users\stu\De5ktop\Debug\erchashij.exe"请先建立一棵二叉排序树:putanumber：45putanumber：1putanurnber：66…皿施要拿整的婺字:45已找到祢要查莪的黝请输putanumber…皿施要拿整的婺字:45已找到祢要查莪的黝请输Pressanykeytocontinue♦"C:\Users\stu\Desktop\Debug\erchashu.exe"co叵）博先建立一棵二叉排序树：k)utanumber：45putanunber：1putanumber：66k)utanunber：-lPressanykeytocontinue实验四——查找一、实验目的.掌握顺序表的查找方法，特别是折半查找方法；.掌握二叉排序树的查找算法。二、实验预习内容请在上机前认真阅读教材及实验指导书,并在以下空白处填写相应的内容。.请写出简朴顺序查找算法。intseqsearch(e1ementtypeA[],intn,keytypex)(i=n;A[0].key=x;whi1e(A[i].key=x)i--；returni;}.请写出有序表二分(折半)查找算法。(1)非递归算法intbin_search(elementtypeA[],intn,keytypex){intmid,1ow=0,high=n一1;〃初始化查找区域while(low<=high){mid=(low+high)/2;if(x==A[mid].keyreturnmid;elseif(x<A[mid.key])high=mid-l;else1id+1;returnT;returnT;returnT;〃返回查找失败的标志returnT;四、实验总结（实验过程中出现的问题、解决方法、结果或其它）问题：1.输入程序时的手误.粗心漏写程序.程序格式错误解决方法:编译后根据错误提醒改正结果：程序对的运营，截图并完毕实验报告⑵递归算法intbinsearch(elementtypeA[],intlow,inthigh,keytypex){intmid;if(low>high)return-1;//查找失败else{mid=(low+high)/2;//求解中间元素的下标if(x==A[mid].key)returnmid；//查找成功elseif(x<A[mid],key)returnbin_search(A,low,midT,x);〃将在左边区域查找的结果作为在整个区域的查找结果返回elsereturnbinsearch(A,mid+1,high,x)；//将在右边区域查找的结果作为在整个区域的查找结果返回一))2)请写出二叉排序树中插入结点的算法。voidinsert(Bnode*&T,Bnode2)请写出二叉排序树中插入结点的算法。voidinsert(Bnode*&T,Bnode(if(T==NULL)T=S;elseif(S->key<T->key)insert(T->1child,S);elseinsert(T->rchild,S);}3)请写出二叉排序树构造的算法。voidcreate_bst(Bnode*&T);{Bnode*u；elementtypex;T=NULL;cin»x；1)请写出二叉排序树结点的结构体定义语句。typedefchardatatype;typedefstructnode{keytypekey;datatypedata;structnode*Ichild,*rchild；}BSTnode;*S)//将指针S所指结点插入到二叉排序树T中〃插入到空树时,插入结点成为根结点//插入到T的左子树中〃插入到T的右子树中〃通过插入结点构造二叉排序树的算法〃初始化根指针并读入第一个元素值While(x!=end_of_num)//x不是结束符时{u=newBnode;u->data=x;〃产生新结点并装入数据u->lchi1d=NILL;u->rchiId=NULL;//设立左、右孩子指针为空insert(T,u);〃插入结点到二叉排序树T中cin»x;//读入下一个元素的值))4)请写出二叉排序树查找的算法。非递归算法：Bnode*bst_search(Bnode*T,keytypex)(Bnode*P=T;//P指向根whi1e(p!=NULL)if(x==p->key)returnp;//查找成功elseif(x<p->key=p—>1child);〃到左子树中继续查找elsep=p->rchild;//到右子树中继续查找returnp;//返回结果也许为空，也也许非空递归算法：Bnode*bst_search(Bnode*T,keytypex)(if(T==NULLIIt->key=x)returnT；〃子树为空或已经找届时均可结束elseif(x<T->key)returnbst_search(T->lchiId,x);//左子树中查找的结果就是函数的结果elsereturnbst_search(T—>rchild,x);〃右子树中查找的结果就是函数的结果}三、上机实验1.实验内容。1)建立一个顺序表,用顺序查找的方法对其实行查找；2)建立一个有序表,用折半查找的方法对其实行查找；3)建立一个二叉排序树，根据给定值对其实行查找；4)对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2.实验源程序。#include<stdio.h>#include<stdlib.h>#definemax100intx;typedefstruct(“ntdata[max];ntlistlen;}seq1ist;voidinitial_list(seqlist*L)(eL->listlen=0;)void1ist_creat(seq1ist*L)(inti;®L->1ist1en++；i=L->1ist1en;oL—>data[i]=x；}intlast_search(seqlist*L)(nti;L->list1en；®L—>data[0]=x；whi1e(L—>data[i]!=x)i--；returni;}intfirst_search(seq1ist*L)(inti,n；®n=L->list1en;