武汉纺织大学《数据结构》实验报告
班级： 信管 专业 班 姓名： 学号： 实验时间： 2016 年 5 月 6 日 指导教师： 宋泽源
实验七：线性查找操作与应用
一、实验目的：
1、掌握顺序查找、折半查找的基本方法和操作过程
2、掌握二叉排序树的基本方法和操作过程
3、掌握查找效率的分析方法
二、实验内容：
1、编写程序，实现顺序查找操作，可参考书本P260/P25示例程序。
实验步骤：
①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（对元素存放的先后顺序没有要求），并按照存储顺序输出所有元素；
②、输入待查找关键字，在顺序表中进行顺序查找；
③、输出查找结果。
2、编写程序，实现有序表折半查找操作，可参考书本P263/P218示例程序。
实验步骤：
①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（要求所有元素按照递增顺序排列），并按照存储顺序输出所有元素；
②、输入待查找关键字，在有序表中进行折半查找；
③、输出查找结果。
3、编写程序，实现二叉排序树查找操作，可参考书本P277/P235示例程序。
实验步骤：
① 在Java语言编辑环境中新建程序，依次输入10个数据元素，建立一个二叉排序树，并按照中序遍历输出所有元素； ②、输入待查找关键字，在二叉排序树中进行查找；
③、输出查找结果。
三、操作步骤： 实验1：package search;
import java.util.Scanner;
public cla Sequence {
public static void main(String[] args) throws java.io.IOException{
SeqList list = new SeqList(10); int value[]=Sequence.readInt(); for(int i=0;i
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)+\"在数组中下标为
list.append(value[i]); \"+list.indexOf(key)+\"的位置\");
}
} System.out.println(\"输入10个数：\"); byte buffer[]=new byte[512]; int count =System.in.read(buffer); if(count
public static int[] readInt() throws java.io.IOException{
} String s=new String(buffer,0,count-2); String str[]=s.split(\" \"); int value[]=new int[str.length]; int i=0,j=0; while(i
try{
}
catch(NumberFormatException e){ System.out.println(str[i]+\"不能转换为数组\"); }
finally{i++;}
if(i==j){ value[j]=Integer.parseInt(str[i]); j++;
return value; }
int keys[]=new int[j]; System.arraycopy(value, 0, keys, 0, j); return keys; } }
实验二
package search;
import java.util.Scanner;
public cla BinarySearch {
public static void main(String[] args)throws java.io.IOException{
SeqList list = new SeqList(10); int value[]=BinarySearch.readInt(); for(int i=0;i
System.out.println(list.toString());
System.out.println(\"使用折半查找方法，输入要查找的数：\"); Scanner scan = new Scanner(System.in); while(true){ int key = scan.nextInt(); list.append(value[i]);
System.out.println(key+\"在数组中的下标为\"+list.binarySearch(value, key));
} public static int[] readInt() throws java.io.IOException{
System.out.println(\"输入10个升序数：\"); byte buffer[]=new byte[512]; int count =System.in.read(buffer); if(count
try{
}
catch(NumberFormatException e){ System.out.println(str[i]+\"不能转换为数组\"); } value[j]=Integer.parseInt(str[i]); j++; return null; }
finally{i++;}
if(i==j){
return value; }
int keys[]=new int[j]; System.arraycopy(value, 0, keys, 0, j); return keys; } }
折半查找方法的实现：
} } } public static int binarySearch(int [] value, int key){
return binarySearch(value,key,0,value.length-1); } public static int binarySearch(int [] value,int key,int min, int
if(min>max){ } else{
int mid=(max+min)/2; if(value[mid]==key){
return mid; return binarySearch(value,key,mid+1,max); return binarySearch(value,key,min,mid-1); }else if(value[mid]
验三
package search;
import java.util.Scanner;
public cla BinarySortTree_ex {
public static void main(String args[]) throws java.io.IOException{
BinarySortTree bstree=new BinarySortTree(); int values[]=BinarySortTree_ex.readInt(); for(int i=0;i
bstree.inOrder(); //中根次序遍历二叉树
//System.out.println(\"中序遍历输出二叉排序树\"+bstree.toString());
System.out.println(\"输入查找的数字：\"); Scanner scan = new Scanner(System.in); while(true){ int key = scan.nextInt(); System.out.println(\"查找\"+key+\",\"+(bstree.search(key)!=null?\"\":\"不\")+\"成功\");
}
} System.out.println(\"输入10个数：\"); byte buffer[]=new byte[512]; int count =System.in.read(buffer); if(count
public static int[] readInt() throws java.io.IOException{
} return null; String s=new String(buffer,0,count-2); String str[]=s.split(\" \"); int value[]=new int[str.length]; int i=0,j=0; while(i
try{
}
catch(NumberFormatException e){ // System.out.println(str[i]+\"不能转换为数组\"); }
finally{i++;}
if(i==j){ value[j]=Integer.parseInt(str[i]); j++;
return value; }
int keys[]=new int[j]; System.arraycopy(value, 0, keys, 0, j); return keys; }
}
四、实验收获和建议：
条条大路通罗马。
