數(shù)據(jù)結(jié)構(gòu)實驗2 查找算法的實現(xiàn)和應(yīng)用.docx

《數(shù)據(jù)結(jié)構(gòu)實驗2 查找算法的實現(xiàn)和應(yīng)用.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實驗2查找算法的實現(xiàn)和應(yīng)用q實驗?zāi)康?.熟練掌握靜態(tài)查找表的查找方法；2.熟練掌握動態(tài)查找表的查找方法;3.掌握hash表的技術(shù).q實驗內(nèi)容1.用二分查找法對查找表進(jìn)行查找；2.建立二叉排序樹并對該樹進(jìn)行查找；3.確定hash函數(shù)及沖突處理方法，建立一個hash表并實現(xiàn)查找。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<<"請輸入元素的個數(shù)："<>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