大数据结构-实验8查找地算法

1、实用文案8.1实现顺序查找的算法一，实验目的.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程；.学会分析各种查找算法的性能。二，实验内容实现顺序查找的算法编写一个程序，输出在顺序表3,6,2,10,1中,采8用,顺5序,查7找,法4查,找9关键字5的结果。实现折半查找算法编写一个程序，输出在顺序表1,2,3,4,5,中6采,用7折,半8查,找9方,法1查0找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。实现二叉排序树的基本运算编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：（）由，创建一个二叉排序树；（）判断是否为一棵二叉排序树（提示：在遍历过程中检查是

2、否符合二叉排序树定义）；（3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。实现哈希表的相关运算编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：（）建立哈希表，哈希函数为e并采用线性探测法解决冲突。输出哈希表；（哈）在上述哈希表中查找关键字为哈9的记录；（3）在上述哈希表中删除关键字为77的记录，再将其插入，然后输出哈希表。要求：输出格式哈希地址：01哈.1哈关键字值：三，源代码及结果截图实/现顺序查找的算法定/义表中最多记录个数为关键字的数据类型/其他数据顺序表类型顺序查找算法/从表头往后找建立顺序表i.key=a

3、i;查找结果：元素的位置是元素不在表中/实现折半查找算法#include#defineMAXL100/定义表中最多记录个数typedefintKeyType;typedefcharInfoType10;typedefstructKeyTypekey；/KeyType为关键字的数据类型InfoTypedata;/其他数据NodeType；typedefNodeTypeSeqListMAXL；/顺序表类型intBinSearch1(SeqListR,intn,KeyTypek)/非递归二分查找算法intlow=0,high=n-1,mid,count=0；while(lowk)继续在Rlow.mi

4、d-1中查找high=mid-1;elselow=mid+1；继续在Rmid+1.high中查找return-1;intBinSearch2(SeqListR,KeyTypek,intlow,inthigh,intcount)/递归二分查找算法intmid;if(lowk)继续在Rlow.mid-1中查找BinSearch2(R,k,low,mid-1,count);elseBinSearch2(R,k,mid+1,high,count)；/继续在Rmid+1.high中查找elsereturn-1;voidmain()SeqListR;KeyTypek=9;inta=1,2,3,4,5,6,

5、7,8,9,10,i,n=10;for(i=0;in;i+)/建立顺序表Ri.key=ai;printf(用非递归方法：n)；if(i=BinSearch1(R,n,k)!=-1)printf(元素d的位置是dn,k,i)；elseprintf(元素%d不在表中n,k)；printf(用递归方法:n)；if(i=BinSearch2(R,k,0,9,0)!=-1)printf(元素d的位置是dn,k,i)；elseprintf(元素%d不在表中n,k)；8.3nsi元元.元元.兀兀查杳一查鱼?到8查查杳一/实现二叉排序树的基本运算#include/EOF,NULL#include/atoi()

6、#include/cout,cintypedefintStatus;typedefstructBTNodeintkey;structBTNode*lchild;structBTNode*rchild;BTNode;/定义二叉排序树插入结点的算法intBSTInsert(BTNode*&T,intk)if(T=NULL)T=(BTNode*)malloc(sizeof(BTNode);T-lchild=T-rchild=NULL;T-key=k;return1;elseif(k=T-key)return0;elseif(kkey)returnBSTInsert(T-lchild,k);elser

7、eturnBSTInsert(T-rchild,k);/定义二叉排序树的创建算法BTNode*createBST(intk,intn)BTNode*T;T=NULL;for(inti=0;iT-lchild)&(Trchild)Judge(T-lchild);Judge(T-rchild);elsereturn0;/定义二叉排序树的查找算法BTNode*BSTSearch(BTNode*&T,intk)if(T=NULL)returnNULL;elseprintf(%d,T-key);if(T-key=k)returnT;elseif(kkey)returnBSTSearch(T-lchild

8、,k);elsereturnBSTSearch(T-rchild,k);voidmain()inta50=4,9,0,1,8,6,3,5,2,7;BTNode*bt=createBST(a,10);if(Judge(bt)=0)coutbt不是二叉排序树endl；elsecoutbt是二叉排序树endl；cout查找关键字6的查找路径:endl；BTNode*t=BSTSearch(bt,6);coutendl;8.4/实现哈希表的相关运算#include#defineMaxSize100#defineNULLKEY0#defineDELKEY-1typedefintKeyType;/定义最大

9、哈希表长度/定义空关键字值/定义被删关键字值/关键字类型typedefchar*InfoType;/其他数据类型typedefstructKeyTypekey;/关键字域InfoTypedata;/其他数据域intcount;/探查次数域HashTableMaxSize;/哈希表类型voidInsertHT(HashTableha,int*n,KeyTypek,intp)/将关键字k插入到哈希表中inti,adr;adr=k%p;if(haadr.key=NULLKEY|haadr.key=DELKEY)/xj可以直接放在哈希表中haadr.key=k;haadr.count=1;else/发

10、生冲突时采用线性探查法解决冲突i=1；/i记录xj发生冲突的次数doadr=(adr+1)%p;i+;while(haadr.key!=NULLKEY&haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;voidCreateHT(HashTableha,KeyTypex,intn,intm,intp)/创建哈希表inti,n1=0;for(i=0;im;i+)/哈希表置初值hai.key=NULLKEY;hai.count=0;for(i=0;in;i+)InsertHT(ha,&n1,xi,p);intSearchHT(HashTableha,in

11、tp,KeyTypek)在哈希表中查找关键字kinti=0,adr;adr=k%p;while(haadr.key!=NULLKEY&haadr.key!=k)i+;/采用线性探查法找下一个地址adr=(adr+1)%p;if(haadr.key=k)/查找成功returnadr;else/查找失败return-1;intDeleteHT(HashTableha,intp,intk,int*n)删除哈希表中关键字kintadr;adr=SearchHT(ha,p,k);if(adr!=-1)/在哈希表中找到该关键字haadr.key=DELKEY;n-;/哈希表长度减1return1;else

12、/在哈希表中未找到该关键字return0;voidDispHT(HashTableha,intn,intm)/输出哈希表floatavg=0;inti;printf(哈希表地址：t)；for(i=0;im;i+)printf(%3d,i);printf(n);printf(哈希表关键字：t)；for(i=0;im;i+)if(hai.key=NULLKEY|hai.key=DELKEY)printf();/输出3个空格elseprintf(%3d,hai.key);printf(n);printf(搜索次数:t)；for(i=0;im;i+)if(hai.key=NULLKEY|hai.key

13、=DELKEY)printf();/输出3个空格elseprintf(%3d,hai.count);printf(n);for(i=0;im;i+)if(hai.key!=NULLKEY&hai.key!=DELKEY)avg=avg+hai.count;avg=avg/n;printf(平均搜索长度ASL(%d)=%gn,n,avg)；voidmain()intx=16,74,60,43,54,90,46,31,29,88,77;intn=11,m=13,p=13,i,k=29;HashTableha;CreateHT(ha,x,n,m,p);printf(n);DispHT(ha,n,m);printf(查找关键字29：n)；i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=%dn,i,k);elseprintf(未找到dn,k)；k=77;printf(删除关键字%dn,k)；DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=