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

1、武漢紡織大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級(jí)： 信管 專業(yè) 班 姓名： 學(xué)號(hào)： 實(shí)驗(yàn)時(shí)間： 年 月 日 指導(dǎo)教師： 實(shí)驗(yàn)四：查找操作與應(yīng)用一、實(shí)驗(yàn)?zāi)康模?1、掌握順序查找、折半查找、哈希查找的基本方法和操作過(guò)程2、掌握查找效率的分析方法二、實(shí)驗(yàn)內(nèi)容：1、編寫(xiě)程序，實(shí)現(xiàn)順序查找操作，可參考書(shū)本P260示例程序。 實(shí)驗(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示例程序。 實(shí)驗(yàn)步驟

2、： 、在Java語(yǔ)言編輯環(huán)境中新建程序，建立一個(gè)順序表（表長(zhǎng)10），依次輸入10個(gè)數(shù)據(jù)元素（要求所有元素按照遞增順序排列），并按照存儲(chǔ)順序輸出所有元素； 、輸入帶查找關(guān)鍵字，在有序表中進(jìn)行折半查找； 、輸出查找結(jié)果。3、編寫(xiě)程序，實(shí)現(xiàn)哈希表查找操作。 實(shí)驗(yàn)步驟： 、在Java語(yǔ)言編輯環(huán)境中新建程序，建立一個(gè)順序表（表長(zhǎng)12），依次輸入10個(gè)數(shù)據(jù)元素，并按照存儲(chǔ)順序輸出所有元素； 、輸入帶查找關(guān)鍵字，在哈希表中進(jìn)行查找； 、輸出查找結(jié)果。 已知：哈希函數(shù)為H(key)=key MOD 11，采用開(kāi)放地址法、線性探測(cè)再散列解決沖突，輸入元素為 55,19,31,23,68,20,27,9,10,7

3、9。三、操作步驟：1.順序查找（1）將順序查找方法添加入SeqList.java中/順序表查找關(guān)鍵字為key元素，返回首次出現(xiàn)的元素，若查找不成功返回-1/key可以只包含關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)，由 T 類的equals()方法提供比較對(duì)象相等的依據(jù)public int indexOf(T key)if(key != null)for(int i=0;ithis.len;i+)if(this.elementi.equals(key)/對(duì)象采用equals()方法比較是否相等return i;return -1;/空表，key為空對(duì)象或者未找到時(shí)public T search(T key) /查找，返回首

4、次出現(xiàn)的關(guān)鍵字為key的元素int find = this.indexOf(key);return find = -1?null:(T)this.elementfind;（2）Linearsearch.javapackage search;import java.util.Scanner;/* * * author pang * */public class Linearsearch public static void main(String args)SeqList list = new SeqList(10);list.append(2);list.append(3);list.appe

5、nd(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ù)：);Scanner scan = new Scanner(System.in);while(true)int key = scan.nextInt();System.out.println(順序查找： +list.search(key);（3）運(yùn)行結(jié)

6、果2.折半查找（1）將折半查找方法添加入SeqList.java中/在按升序排序的數(shù)組中，折半查找關(guān)鍵字為key元素，若找到返回下標(biāo)，否則返回-1public int binarySearch(T key)int begin = 0;int end = this.len-1;if(key != null)while(begin0)/給定對(duì)象小end = mid-1;/查找范圍縮小到前半段elsebegin = mid+1;/查找范圍縮小到后半段return -1;/查找不成功（2）Binarysearch.javapackage search;import java.util.Scanner;

7、/* * * author pang * */public class Binarysearch public static void main(String args)SeqList list = new SeqList(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

8、();System.out.println(輸入要查找的數(shù)：);Scanner scan = new Scanner(System.in);while(true)int key = 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)造哈希表public void hash(int x,int y)int h = x % y;if(Integer.parseInt(el

9、ementh.toString()=0)/該位置為空，不沖突this.set(h, x);/此處為set(int x,int y)的方法，與原set方法有一定差別else/沖突hash(h+1,y);/開(kāi)放地址法、線性探測(cè)再散列解決沖突/哈希查找public int hashSearch(int key,int y)int h = key % y;/計(jì)算哈希值作為下標(biāo)for(int i=1;i=y;i+)if(Integer.parseInt(elementh.toString()=0)/（0代表該位置為空）若查找位置為空，查找失敗return -1;else if(Integer.parse

10、Int(elementh.toString()=key)/若查找位置正好為key，查找成功return h;else/若查找位置有值，但不等于key，解決沖突，繼續(xù)查找h=h+i;return hashSearch(h,y);（2）Hashsearch.javapackage search;import java.util.Scanner;/* * * author pang * */public class Hashsearch public static void main(String args)SeqList list = new SeqList(12);for(int i=0;i12;i+)list.append(0);list.hash(55,11);list.hash(19,11);list.hash(31,11);list.hash(23,11);list.hash(68,11);list.hash(20,11);list.hash(27,11);list.hash(9,11);list.hash(10,11);list.hash(79,11);System.out.println(list.toString();Syst