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

武汉纺织大学《数据结构》实验报告

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

实验四：查找操作与应用

一、实验目的：

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

二、实验内容：

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

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

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

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

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

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

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

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

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

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

（1）将顺序查找方法添加入SeqList.java中

//顺序表查找关键字为key元素，返回首次出现的元素，若查找不成功返回-1 //key可以只包含关键字数据项，由 T 类的equals()方法提供比较对象相等的依据 public int indexOf(T key){

if(key != null)

for(int i=0;i

if(this.element[i].equals(key))//对象采用equals()方法比较

return i;

是否相等

return -1;//空表，key为空对象或者未找到时 }

public T search(T key) {//查找，返回首次出现的关键字为key的元素 int find = this.indexOf(key); }

return find == -1?null:(T)this.element[find];

（2）Linearsearch.java

package 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.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(\输入要查找的数：\); Scanner scan = new Scanner(System.in); while(true){

int key = scan.nextInt();

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

（3）运行结果

2.折半查找

（1）将折半查找方法添加入SeqList.java中

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

int begin = 0;

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

while(begin<=end){//边界有效

int mid = (begin+end)/2;//中间位置，当前比较元素位置 System.out.print(element[mid]+\);

if(Integer.parseInt(element[mid].toString())==(Integer)

key)//对象比较大小

return mid;//查找成功

if(Integer.parseInt(element[mid].toString())-(Integer) end = mid-1;//查找范围缩小到前半段 else

begin = mid+1;//查找范围缩小到后半段

key>0)//给定对象小

}

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

（2）Binarysearch.java

package search;

import java.util.Scanner; /** *

* @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()); System.out.println(\输入要查找的数：\); Scanner scan = new Scanner(System.in); while(true){ }

int key = scan.nextInt();

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

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

}

}

（3）运行结果

3.哈希查找

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

//除留余数法计算哈希值，构造哈希表 public void hash(int x,int y){

int h = x % y;

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

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

差别

else//冲突

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

}

//哈希查找

public int hashSearch(int key,int y){

int h = key % y;//计算哈希值作为下标

for(int i=1;i<=y;i++)

if(Integer.parseInt(element[h].toString())==0)//（0代表该位置为

空）若查找位置为空，查找失败 return -1;

else if(Integer.parseInt(element[h].toString())==key)//若查找位

置正好为key，查找成功 return h;

}

else//若查找位置有值，但不等于key，解决冲突，继续查找 h=h+i;

return hashSearch(h,y);

（2）Hashsearch.java

package 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;i<12;i++){ }

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());

System.out.println(\输入要查找的数：（0表示该位置为空）\); Scanner scan = new Scanner(System.in);

list.append(0);

}

}

while(true){ }

int key = scan.nextInt();

System.out.println(list.hashSearch(key,11));

（3）运行结果

四、实验收获和建议：

本文来源：https://www.bwwdw.com/article/c8ur.html