数据结构实验2 查找算法的实现和应用.docx
- 文档编号:3484208
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:14
- 大小:40.95KB
数据结构实验2 查找算法的实现和应用.docx
《数据结构实验2 查找算法的实现和应用.docx》由会员分享,可在线阅读,更多相关《数据结构实验2 查找算法的实现和应用.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构实验2查找算法的实现和应用
实验2查找算法的实现和应用
❑实验目的
1.熟练掌握静态查找表的查找方法;
2.熟练掌握动态查找表的查找方法;
3.掌握hash表的技术.
❑实验内容
1.用二分查找法对查找表进行查找;
2.建立二叉排序树并对该树进行查找;
3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。
1.二分查找
#include
usingnamespacestd;
#defineINVALID_INDEX-100
intIntCompare(constint&a,constint&b,void*param)
{
returna-b;
}
template
intBinarySearch(constT1*theArray,intlength,constT2&key,int(*compare)(constT1&,constT2&,void*param),void*param)
{
intindexRet=INVALID_INDEX;
intmid=length/2;
intcmp=compare(theArray[mid],key,param);
if(cmp==0)
{
indexRet=mid;
}
elseif(length!
=1)
{
if(cmp<0&&length!
=1)
{
indexRet=BinarySearch(theArray+mid,length-mid,key,compare,param);
if(indexRet!
=INVALID_INDEX)
{
indexRet+=mid;
}
}
else
{
indexRet=BinarySearch(theArray,mid,key,compare,param);
}
}
returnindexRet;
}
intmain()
{
intlength=0;
inti=0;
intkey=0;
intindex=INVALID_INDEX;
cout<<"请输入元素的个数:
"< cin>>length; int*aArray=newint[length]; cout<<"请输入要输入的元素: "< for(i=0;i { cin>>aArray[i]; } cout<<"要查找的元素: "< while(cin>>key&&key! ='F'){ index=BinarySearch(aArray,length,key,IntCompare,NULL); if(index==INVALID_INDEX) { cout<<"Theelementisnotexist."< } else { cout<<"Theelementpositionis"< deleteaArray;} return0; } 2二叉排序树 #include #include #include usingnamespacestd; typedefintkeyType; typedefstructNode { keyTypekey; structNode*left; structNode*right; structNode*parent; }Node,*PNode; voidinseart(PNode*root,keyTypekey) { PNodep=(PNode)malloc(sizeof(Node)); p->key=key; p->left=p->right=p->parent=NULL; if((*root)==NULL) { *root=p; return; } if((*root)->left==NULL&&(*root)->key>key) { p->parent=(*root); (*root)->left=p; return; } if((*root)->right==NULL&&(*root)->key { p->parent=(*root); (*root)->right=p; return; } if((*root)->key>key) { inseart(&(*root)->left,key); } elseif((*root)->key { inseart(&(*root)->right,key); } else return; } PNodesearch(PNoderoot,keyTypekey) { if(root==NULL) { returnNULL; } if(key>root->key) { returnsearch(root->right,key); } elseif(key { returnsearch(root->left,key); } else returnroot; } voidcreate(PNode*root,keyType*keyArray,intlength) { inti; for(i=0;i { inseart(root,keyArray[i]); } } intmain() { inti; PNoderoot=NULL; inta[100]; intn; scanf("%d",&n); for(i=0;i { scanf("%d",&a[i]); } create(&root,a,n); intm; while(~scanf("%d",&m)){ if(search(root,m)->key){ printf("YES\n"); } } return0; } 3hash #include //#include #include usingnamespacestd; enumResult{ ok=2, success=1, unsuccess=0, duplicate=-1, fail=-2, }; typedefintelemtype; typedefstruct{ elemtype*elem; intcount; intsizeindex; }hashTable; voidInithash(hashTable&H,intn){ H.elem=newelemtype[n]; H.count=0; H.sizeindex=n; for(inti=0;i { H.elem[i]=0; } } inthash(elemtypeK,intsizeindex) { intcount=H.count; inthaAddr=K%sizeindex; returnhaAddr; } intSearchHash(hashTable&H,elemtypeK,int&haAddr,int&c) { intd=1; intsizeindex=H.sizeindex; haAddr=hash(K,sizeindex); while(H.elem[haAddr]! =NULL&&H.elem[haAddr]! =K) { haAddr=(K%sizeindex+d)%sizeindex; d++; c++; cout<<"产生冲突,解决中…………"< if(c>H.sizeindex-2) { cout<<"冲突次数过多,重新建立哈希表"< break; } } if(K==H.elem[haAddr]) { cout<<"chenggong"< returnsuccess; } else { cout<<"fail"< returnunsuccess; } } intInsertHash(hashTable&H,elemtypee) { intcollision=0; inthaAddr=-1; if(SearchHash(H,e,haAddr,collision)==success) { cout<<"存在该元素! ! ! "< returnduplicate; } elseif(collision { H.elem[haAddr]=e; H.count++; cout<<"插入成功! ! ! "< returnok; } else { cout<<"冲突次数过多,重新建立哈希表"< returnfail; } } inthashsearch(hashTable&H,elemtypee) { intp=0; for(inti=0;i { if(H.elem[i]==e) { //H.elem[i]==0; p=1; cout<<"hashaddress="< if(p==0) returnunsuccess; else returnsuccess; } } } voidPrintHash(hashTableH) { intnum=1; cout<<"哈希表为……! "< for(inti=0;i { if(num%10==0) cout< if(H.elem[i]! =NULL) { cout< num++; } elsecontinue; } cout< } voidPerformance(hashTable&H){ //hashTableH; intsizeindex; cout<<哈希表容量为……! < cin>>sizeindex; Inithash(H,sizeindex); inte=1; cout<<"输入插入元素,否则输入'0'"< cin>>e; while(e! =0) { InsertHash(H,e); cout<<"输入插入元素,否则输入'0'"< cin>>e; } PrintHash(H); intk=1; cout<<"输入要查找元素: "; //intk; cin>>k; hashsearch(H,k); intstatus=hashsearch(H,K); if(! status) cout<<"该元素不存在"< } intmain() { hashTableH; Performance(H); cin.get(); cin.get(); return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实验2 查找算法的实现和应用 数据结构 实验 查找 算法 实现 应用
![提示](https://static.bingdoc.com/images/bang_tan.gif)