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

1、武汉纺织大学数据结构实验报告班级： 信管 专业 班 姓名： 学号： 实验时间： 年 月 日 指导教师： 实验四：查找操作与应用一、实验目的： 1、掌握顺序查找、折半查找、哈希查找的基本方法和操作过程2、掌握查找效率的分析方法二、实验内容：1、编写程序，实现顺序查找操作，可参考书本P260示例程序。 实验步骤： 、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（对元素存放的先后顺序没有要求），并按照存储顺序输出所有元素； 、输入带查找关键字，在顺序表中进行顺序查找； 、输出查找结果。2、编写程序，实现有序表折半查找操作，可参考书本P263示例程序。 实验步骤

2、： 、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（要求所有元素按照递增顺序排列），并按照存储顺序输出所有元素； 、输入带查找关键字，在有序表中进行折半查找； 、输出查找结果。3、编写程序，实现哈希表查找操作。 实验步骤： 、在Java语言编辑环境中新建程序，建立一个顺序表（表长12），依次输入10个数据元素，并按照存储顺序输出所有元素； 、输入带查找关键字，在哈希表中进行查找； 、输出查找结果。 已知：哈希函数为H(key)=key MOD 11，采用开放地址法、线性探测再散列解决冲突，输入元素为 55,19,31,23,68,20,27,9,10,7

3、9。三、操作步骤：1.顺序查找（1）将顺序查找方法添加入SeqList.java中/顺序表查找关键字为key元素，返回首次出现的元素，若查找不成功返回-1/key可以只包含关键字数据项，由 T 类的equals()方法提供比较对象相等的依据public int indexOf(T key)if(key != null)for(int i=0;ithis.len;i+)if(this.elementi.equals(key)/对象采用equals()方法比较是否相等return i;return -1;/空表，key为空对象或者未找到时public T search(T key) /查找，返回首

4、次出现的关键字为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(输入要查找的数：);Scanner scan = new Scanner(System.in);while(true)int key = scan.nextInt();System.out.println(顺序查找： +list.search(key);（3）运行结

6、果2.折半查找（1）将折半查找方法添加入SeqList.java中/在按升序排序的数组中，折半查找关键字为key元素，若找到返回下标，否则返回-1public int binarySearch(T key)int begin = 0;int end = this.len-1;if(key != null)while(begin0)/给定对象小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(输入要查找的数：);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(el

9、ementh.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(elementh.toString()=0)/（0代表该位置为空）若查找位置为空，查找失败return -1;else if(Integer.parse

10、Int(elementh.toString()=key)/若查找位置正好为key，查找成功return h;else/若查找位置有值，但不等于key，解决冲突，继续查找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