《武汉纺织大学数据结构实验报告4》由会员分享，可在线阅读，更多相关《武汉纺织大学数据结构实验报告4（7页珍藏版）》请在金锄头文库上搜索。
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
3、,68,20,27,9,10,79。三、操作步骤 ： 1.顺序查找 （1）将顺序查找方法添加入SeqList.java中/顺序表查找关键字为key 元素，返回首次出现的元素，若查找不成功返回-1/key可以只包含关键字数据项，由 T 类的 equals()方法提供比较对象相等的依据publicint indexOf(T key) if(key != null) for( int i=0;i list = new SeqList(10); list.append(2); list.append(3); list.append(4); list.append(5); list.append(6);
4、 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）
5、将折半查找方法添加入SeqList.java中/在按升序排序的数组中，折半查找关键字为key 元素，若找到返回下标，否则返回-1publicint 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.java package search; import java.util.Scanner;
6、 /* * author pang*/publicclass Binarysearch publicstaticvoid 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.to
7、String(); 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中/除留余数法计算哈希值，构造哈希表publicvoid hash(int x,int y) int h = x
8、 % y; if(Integer.parseInt( elementh.toString()=0)/该位置为空， 不冲突this.set(h, x);/此处为 set(int x,int y)的方法，与原set 方法有一定差别else/冲突hash(h+1,y);/开放地址法、线性探测再散列解决冲突 /哈希查找publicint hashSearch(int key,int y) int h = key % y;/计算哈希值作为下标for( int i=1;i list = new SeqList(12); for( int i=0;i12;i+) list.append(0); list.h
9、ash(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 ); while( true) int key = scan.nextInt(); System.out .println(list.hashSearch(key,11); （3）运行结果四、实验收获和建议：
