武汉纺织大学数据结构试验报告4

本文格式为Word版，下载可任意编辑——武汉纺织大学数据结构试验报告4武汉纺织大学《数据结构》试验报告

班级：信管专业班姓名：学号：试验时间：年月日指导教师：

试验四：查找操作与应用

一、试验目的：

1、把握顺序查找、折半查找、哈希查找的基本方法和操作过程2、把握查找效率的分析方法

二、试验内容：

1、编写程序，实现顺序查找操作，可参考书本P260例如程序。试验步骤：

①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（对元素存放的先后顺序没有要求），并依照存储顺序输出所有元素；

②、输入带查找关键字，在顺序表中进行顺序查找；③、输出查找结果。

2、编写程序，实现有序表折半查找操作，可参考书本P263例如程序。试验步骤：

①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（要求所有元素依照递增顺序排列），并依照存储顺序输出所有元素；

②、输入带查找关键字，在有序表中进行折半查找；③、输出查找结果。

3、编写程序，实现哈希表查找操作。试验步骤：

①、在Java语言编辑环境中新建程序，建立一个顺序表（表长12），依次输入10个数据元素，并依照存储顺序输出所有元素；②、输入带查找关键字，在哈希表中进行查找；③、输出查找结果。

已知：哈希函数为H(key)=keyMOD11，采用开放地址法、线性探测再散列解决冲突，输入元素为{55,19,31,23,68,20,27,9,10,79}。

三、操作步骤：1.顺序查找

（1）将顺序查找方法添参与SeqList.java中

//顺序表查找关键字为key元素，返回首次出现的元素，若查找不成功返回-1//key可以只包含关键字数据项，由T类的equals()方法提供比较对象相等的依据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(\输入要查找的数：\);Scannerscan=newScanner(System.in);while(true){

intkey=scan.nextInt();

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

（3）运行结果

2.折半查找

（1）将折半查找方法添参与SeqList.java中

//在按升序排序的数组中，折半查找关键字为key元素，若找到返回下标，否则返回-1publicintbinarySearch(Tkey){

intbegin=0;

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

while(begin0)//给定对象小

}

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(\输入要查找的数：\);Scannerscan=newScanner(System.in);while(true){}

intkey=scan.nextInt();

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

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

}

}

（3）运行结果

3.哈希查找

（1）将构造哈希表和哈希查找的方法参与SeqList.java中

//除留余数法计算哈希值，构造哈希表publicvoidhash(intx,inty){

inth=x%y;

if(Integer.parseInt(element[h].toString())==0)//该位置为空，不冲突

this.set(h,x);//此处为set(intx,inty)的方法，与原set方法有一定

区别

else//冲突

hash(h+1,y);//开放地址法、线性探测再散列解决冲突

}

//哈希查找

publicint