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

武汉纺织大学《数据结构》实验报告 班级： 信管 专业 班 姓名： 学号： 实验时间： 年 月 日 指导教师： 实验四：查找操作与应用 一、实验目的： 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;ithis.len;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]; }package search; import java.util.Scanner; /** * * @author pang * */ public class Linearsearch { public static void main(String[] args){ SeqListInteger list = new SeqListInteger(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 = (b