武汉纺织大学数据结构实验报告(共7页).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;i<this.len;i+)if(this.elementi.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.elementfind;（2）Linearsearch.javapackage search;import java.util.Scanner;/* * * author pang * */public class Linearsearch public static void main(String args)SeqList<Integer> list = new SeqList<Integer>(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元素，若找到返回下标，否则返回-1public 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(elementmid+"? ");if(Integer.parseInt(elementmid.toString()=(Integer) key)/对象比较大小return mid;/查找成功if(Integer.parseInt(elementmid.toString()-(Integer) key>0)/给定对象小end = mid-1;/查找范围缩小到前半段elsebegin = mid+1;/查找范围缩小到后半段return -1;/查找不成功（2）Binarysearch.javapackage search;import java.util.Scanner;/* * * author pang * */public class Binarysearch public static void main(String args)SeqList<Integer> list = new SeqList<Integer>(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(elementh.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.parseInt(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<Integer> list = new SeqList<Integer>(12);for(int i=0;i<12;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();System.out.println("输入要查找的数：（0表示该位置为空）");Scanner scan = new Scanner(System.in);while(true)int key = scan.nextInt();System.out.println(list.hashSearch(key,11);（3）运行结果四、实验收获和建议：专心-专注-专业
