搜索
武汉纺织大学《数据结构》实验报告班级：信管专业班姓名：学号：实验时间：年月日指导教师：实验四：查找操作与应用一、实验目的：1、掌握顺序查找、折半查找、哈希查找的基本方法和操作过程2、掌握查找效率的分析方法二、实验内容：1、编写程序，实现顺序查找操作，可参考书本P260示例程序。实验步骤：①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（对元素存放的先后顺序没有要求），并按照存储顺序输出所有元素；②、输入带查找关键字，在顺序表中进行顺序查找；③、输出查找结果。2、编写程序，实现有序表折半查找操作，可参考书本P263示例程序。实验步骤：①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（要求所有元素按照递增顺序排列），并按照存储顺序输出所有元素；②、输入带查找关键字，在有序表中进行折半查找；③、输出查找结果。3、编写程序，实现哈希表查找操作。实验步骤：①、在Java语言编辑环境中新建程序，建立一个顺序表（表长12），依次输入10个数据元素，并按照存储顺序输出所有元素；②、输入带查找关键字，在哈希表中进行查找；③、输出查找结果。已知：哈希函数为H(key)=keyMOD11，采用开放地址法、线性探测再散列解决冲突，输入元素为{55,19,31,23,68,20,27,9,10,79}。三、操作步骤：1.顺序查找（1）将顺序查找方法添加入SeqList.java中//顺序表查找关键字为key元素，返回首次出现的元素，若查找不成功返回-1//key可以只包含关键字数据项，由T类的equals()方法提供比较对象相等的依据publicintindexOf(Tkey){if(key!=null)for(inti=0;ithis.len;i++)if(this.element[i].equals(key))//对象采用equals()方法比较是否相等returni;return-1;//空表，key为空对象或者未找到时}publicTsearch(Tkey){//查找，返回首次出现的关键字为key的元素intfind=this.indexOf(key);returnfind==-1?null:(T)this.element[find];}（2）Linearsearch.javapackagesearch;importjava.util.Scanner;/****@authorpang**/publicclassLinearsearch{publicstaticvoidmain(String[]args){SeqListIntegerlist=newSeqListInteger(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(输入要查找的数：);Scannerscan=newScanner(System.in);while(true){intkey=scan.nextInt();System.out.println(顺序查找：+list.search(key));}}}（3）运行结果2.折半查找（1）将折半查找方法添加入SeqList.java中//在按升序排序的数组中，折半查找关键字为key元素，若找到返回下标，否则返回-1publicintbinarySearch(Tkey){intbegin=0;intend=this.len-1;if(key!=null)while(begin=end){//边界有效intmid=(begin+end)/2;//中间位置，当前比较元素位置System.out.print(element[mid]+?);if(Integer.parseInt(element[mid].toString())==(Integer)key)//对象比较大小returnmid;//查找成功if(Integer.parseInt(element[mid].toString())-(Integer)key0)//给定对象小end=mid-1;//查找范围缩小到前半段elsebegin=mid+1;//查找范围缩小到后半段}return-1;//查找不成功}（2）Binarysearch.javapackagesearch;importjava.util.Scanner;/****@authorpang**/publicclassBinarysearch{publicstaticvoidmain(String[]args){SeqListIntegerlist=newSeqListInteger(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(输入要查找的数：);Scannerscan=newScanner(System.in);while(true){intkey=scan.nextInt();System.out.print(折半查找：);System.out.println(list.binarySearch(key));}}}（3）运行结果3.哈希查找（1）将构造哈希表和哈希查找的方法加入SeqList.java中//除留余数法计算哈希值，构造哈希表publicvoidhash(intx,inty){inth=x%y;if(Integer.parseInt(element[h].toString())==0)//该位置为空，不冲突this.set(h,x);//此处为set(intx,inty)的方法，与原set方法有一定差别else//冲突hash(h+1,y);//开放地址法、线性探测再散列解决冲突}//哈希查找publicinthashSearch(intkey,inty){inth=key%y;//计算哈希值作为下标for(inti=1;i=y;i++)if(Integer.parseInt(element[h].toString())==0)//（0代表该位置为空）若查找位置为空，查找失败return-1;elseif(Integer.parseInt(element[h].toString())==key)//若查找位置正好为key，查找成功returnh;else//若查找位置有值，但不等于key，解决冲突，继续查找h=h+i;returnhashSearch(h,y);}（2）Hashsearch.javapackagesearch;importjava.util.Scanner;/****@authorpang**/publicclassHashsearch{publicstaticvoidmain(String[]args){SeqListIntegerlist=newSeqListInteger(12);for(inti=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());System.out.println(输入要查找的数：（0表示该位置为空）);Scannerscan=newScanner(System.in);while(true){intkey=scan.nextInt();System.out.println(list.hashSearch(key,11));}}}（3）运行结果四、实验收获和建议：