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

数据结构实验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（keykey）

{

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<<"输入插入元素，否则输入＇０＇"<

cin>>ｅ;

while（e!

=0）

{

InsertHash（H,e）;

cout<<"输入插入元素，否则输入＇０＇"<

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;

}