武漢紡織大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告4

本文格式為Word版，下載可任意編輯——武漢紡織大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告4武漢紡織大學(xué)《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)報(bào)告

班級(jí)：信管專(zhuān)業(yè)班姓名：學(xué)號(hào)：試驗(yàn)時(shí)間：年月日指導(dǎo)教師：

試驗(yàn)四：查找操作與應(yīng)用

一、試驗(yàn)?zāi)康模?/p>

1、把握順序查找、折半查找、哈希查找的基本方法和操作過(guò)程2、把握查找效率的分析方法

二、試驗(yàn)內(nèi)容：

1、編寫(xiě)程序，實(shí)現(xiàn)順序查找操作，可參考書(shū)本P260例如程序。試驗(yàn)步驟：

①、在Java語(yǔ)言編輯環(huán)境中新建程序，建立一個(gè)順序表（表長(zhǎng)10），依次輸入10個(gè)數(shù)據(jù)元素（對(duì)元素存放的先后順序沒(méi)有要求），并依照存儲(chǔ)順序輸出所有元素；

②、輸入帶查找關(guān)鍵字，在順序表中進(jìn)行順序查找；③、輸出查找結(jié)果。

2、編寫(xiě)程序，實(shí)現(xiàn)有序表折半查找操作，可參考書(shū)本P263例如程序。試驗(yàn)步驟：

①、在Java語(yǔ)言編輯環(huán)境中新建程序，建立一個(gè)順序表（表長(zhǎng)10），依次輸入10個(gè)數(shù)據(jù)元素（要求所有元素依照遞增順序排列），并依照存儲(chǔ)順序輸出所有元素；

②、輸入帶查找關(guān)鍵字，在有序表中進(jìn)行折半查找；③、輸出查找結(jié)果。

3、編寫(xiě)程序，實(shí)現(xiàn)哈希表查找操作。試驗(yàn)步驟：

①、在Java語(yǔ)言編輯環(huán)境中新建程序，建立一個(gè)順序表（表長(zhǎng)12），依次輸入10個(gè)數(shù)據(jù)元素，并依照存儲(chǔ)順序輸出所有元素；②、輸入帶查找關(guān)鍵字，在哈希表中進(jìn)行查找；③、輸出查找結(jié)果。

已知：哈希函數(shù)為H(key)=keyMOD11，采用開(kāi)放地址法、線(xiàn)性探測(cè)再散列解決沖突，輸入元素為{55,19,31,23,68,20,27,9,10,79}。

三、操作步驟：1.順序查找

（1）將順序查找方法添參與SeqList.java中

//順序表查找關(guān)鍵字為key元素，返回首次出現(xiàn)的元素，若查找不成功返回-1//key可以只包含關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)，由T類(lèi)的equals()方法提供比較對(duì)象相等的依據(jù)publicintindexOf(Tkey){

if(key!=null)

for(inti=0;ilist=newSeqList(10);list.append(2);list.append(3);list.append(4);list.append(5);list.append(6);list.append(7);list.append(8);list.append(9);list.append(10);list.append(11);

}

}

System.out.println(list.toString());System.out.println(\輸入要查找的數(shù)：\);Scannerscan=newScanner(System.in);while(true){

intkey=scan.nextInt();

System.out.println(\順序查找：\+list.search(key));}

（3）運(yùn)行結(jié)果

2.折半查找

（1）將折半查找方法添參與SeqList.java中

//在按升序排序的數(shù)組中，折半查找關(guān)鍵字為key元素，若找到返回下標(biāo)，否則返回-1publicintbinarySearch(Tkey){

intbegin=0;

intend=this.len-1;if(key!=null)

while(begin0)//給定對(duì)象小

}

return-1;//查找不成功}

（2）Binarysearch.java

packagesearch;

importjava.util.Scanner;/***

*@authorpang**/

publicclassBinarysearch{

publicstaticvoidmain(String[]args){

SeqListlist=newSeqList(10);list.append(2);list.append(3);list.append(4);list.append(5);list.append(6);list.append(7);list.append(8);list.append(9);list.append(10);list.append(11);

System.out.println(list.toString());System.out.println(\輸入要查找的數(shù)：\);Scannerscan=newScanner(System.in);while(true){}

intkey=scan.nextInt();

System.out.print(\折半查找：\);

System.out.println(list.binarySearch(key));

}

}

（3）運(yùn)行結(jié)果

3.哈希查找

（1）將構(gòu)造哈希表和哈希查找的方法參與SeqList.java中

//除留余數(shù)法計(jì)算哈希值，構(gòu)造哈希表publicvoidhash(intx,inty){

inth=x%y;

if(Integer.parseInt(element[h].toString())==0)//該位置為空，不沖突

this.set(h,x);//此處為set(intx,inty)的方法，與原set方法有一定

區(qū)別

else//沖突

hash(h+1,y);//開(kāi)放地址法、線(xiàn)性探測(cè)再散列解決沖突

}

//哈希查找

publicint