數(shù)據(jù)結(jié)構(gòu)查找

本文格式為Word版下載后可任意編輯和復(fù)制第第頁數(shù)據(jù)結(jié)構(gòu)查找

南京信息工程高校試驗（實習(xí)）報告

一、試驗?zāi)康?/p>

查找（挨次查找、折半查找）

二、試驗內(nèi)容

解和把握靜態(tài)查找表的查找過程；

把握挨次查找算法；

把握折半查找算法

要求完成靜態(tài)查找表的挨次查找和折半查找算法的實現(xiàn)。

三、試驗步驟

#includestdio.h

#includestdlib.h

#includemath.h

#includetime.h

#defineN10

typedefintDataType;//定義比較的元素類型

//靜態(tài)查找表的挨次存儲結(jié)構(gòu)

typedefstruct{

DataType*data;//數(shù)據(jù)元素存儲空間基址，按實際長度安排，0號單元留空

//建表時按實際長度安排，0號單元留空intlength;//表長度

}SSTable;

//創(chuàng)建一個靜態(tài)表，內(nèi)容為20以內(nèi)的隨機數(shù)

voidcreateST(SSTable*ST,intn){

inti;

time_tt;

if(ST!=NULL){

ST-data=(DataType*)calloc(n+1,sizeof(DataType));if(ST-data!=NULL){

srand((unsigned)time(t));

for(i=1;i=n;i++){

ST-data[i]=rand();//產(chǎn)生20以內(nèi)的隨機數(shù)}

ST-length=n;

}

}

}

//創(chuàng)建一個靜態(tài)表，內(nèi)容按從小到大排列，以便折半查找voidcreateST_binary(SSTable*ST,intn){

inti,j=0;

time_tt;

if(ST!=NULL){

ST-data=(DataType*)calloc(n+1,sizeof(DataType));

if(ST-data!=NULL){

for(i=1;i=n;i++){

ST-data[i]=j;

j+=4;

}

ST-length=n;

}

}

}

//打印出靜態(tài)表的內(nèi)容

voidprint_SSTable(SSTable*ST){

inti,n=ST-length;

if(ST!=NULL){

for(i=1;i=n;i++){

printf(%d,ST-data[i]);

}

printf(\n);

}

}intsearch_seq(SSTableST,DataTypekey){

inti;

if(ST.data==NULL)return0;

ST.data[0]=key;//設(shè)置監(jiān)視哨。目的在于免去查找過程中每一步都要檢測整

//個表是否查找完畢，是一個很有效的程序設(shè)計技巧。監(jiān)視

//哨也可以設(shè)在高下標(biāo)處。

for(i=ST.length;ST.data[i]!=key;i--);

returni;

}

intsearch_binary(SSTableST,DataTypekey){

intlow,high,mid;

low=1;

high=ST.length;

while(low=high){//當(dāng)表空間存在時

mid=(low+high)/2;

if(ST.data[mid]==key){

returnmid;//查找勝利，返回mid

}

if(keyST.data[mid]){

high=mid-1;//連續(xù)在前半?yún)^(qū)間查找

}else{

low=mid+1;//連續(xù)在后半?yún)^(qū)間查找

}

}

return0;//查找失敗

}

intmain(){

intn=20;//在20個數(shù)中查找,便利看結(jié)果，不要設(shè)置得太大

SSTableST,ST_binary;//分別用于挨次查找和折半查找的靜態(tài)表indexindtb[n+1];//索引表，用于分塊查找

createST(ST,n);//創(chuàng)建一個隨機靜態(tài)表

createST_binary(ST_binary,n);//創(chuàng)建一個從小到大挨次排列的靜態(tài)表

//采納挨次查找

printf(原始數(shù)據(jù):);

print_SSTable(ST);

printf(挨次查找5的結(jié)果:%d\n,search_seq(ST,5));

printf(挨次查找10的結(jié)果:%d\n,search_seq(ST,10));

printf(挨次查找12的結(jié)果:%d\n,search_seq(ST,12));

printf(挨次查找15的結(jié)果:%d\n,search_seq(ST,15));

printf(挨次查找20的結(jié)果:%d\n,search_seq(ST,20));

printf(\n);//采納折半查找

printf(原始數(shù)據(jù):);

print_SSTable(ST_binary);

printf(折半查找5的結(jié)果:%d\n,search_binary(ST_binary,5));printf(折半查找10的結(jié)果:%d\n,search_binary(ST_binary,10));printf(折半查找12的結(jié)果:%d\n,search_binary(ST_binary,12));printf(折半查找15的結(jié)果:%d\n,search_binary(ST_binary,15));printf(折半查找20的結(jié)果:%d\n,search_binary(ST_binary,20));system(pause);//暫停一下，看看結(jié)果

free(ST.data);//不要忘了釋放堆空間

return0;

}

四、試驗結(jié)果

五、試驗小結(jié)

挨次查找

思路:從表中最終一個記錄開頭，逐個進行記錄的關(guān)鍵字和

給定值的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則

返回返回記錄所在的