数据结构实验2 查找算法的实现和应用.docx

《数据结构实验2 查找算法的实现和应用.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验2查找算法的实现和应用q实验目的1.熟练掌握静态查找表的查找方法；2.熟练掌握动态查找表的查找方法;3.掌握hash表的技术.q实验内容1.用二分查找法对查找表进行查找；2.建立二叉排序树并对该树进行查找；3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。1.二分查找#includeusingnamespacestd;#defineINVALID_INDEX-100intIntCompare(constint&a,constint&b,void*param){returna-b;}template

2、T2>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(the

3、Array+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<<"请输入元素的个数："<>length;int*aArray=newint[length];c

4、out<<"请输入要输入的元素："<>aArray[i];}cout<<"要查找的元素："<>key&&key!='F'){index=BinarySearch(aArray,length,key,IntCompare,NULL);if(index==INVALID_INDEX){cout<<"Theelementisnotexist."<

5、aArray;}return0;}2二叉排序树#include#include#includeusingnamespacestd;typedefintkeyType;typedefstructNode{keyTypekey;structNode*left;structNode*right;structNode*parent;}Node,*PNode;voidinseart(PNode*root,keyTypekey){PNodep=(PNode)malloc(sizeof(Node));p->key=key;p

6、->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)->keyparent=(*root);(*root)->right=p;return;}if((*root)->key>key){inseart(&(*root)->left,key);}

7、elseif((*root)->keyright,key);}elsereturn;}PNodesearch(PNoderoot,keyTypekey){if(root==NULL){returnNULL;}if(key>root->key){returnsearch(root->right,key);}elseif(keykey){returnsearch(root->left,key);}elsereturnroot;}voidcreate(PNode*root,keyType*keyArray,i

8、ntlen