数据结构实验五-查找与排序的实现
- 格式:doc
- 大小:112.09 KB
- 文档页数:7
实验报告
课程名称数据结构实验名称查找与排序的实现
系别专业班级指导教师11
学号姓名实验日期实验成绩
一、实验目的
(1)掌握交换排序算法(冒泡排序)的基本思想;
(2)掌握交换排序算法(冒泡排序)的实现方法;
(3)掌握折半查找算法的基本思想;
(4)掌握折半查找算法的实现方法;
二、实验内容
1.对同一组数据分别进行冒泡排序,输出排序结果。要求:
1)设计三种输入数据序列:正序、反序、无序
2)修改程序:
a)将序列采用手工输入的方式输入
b)增加记录比较次数、移动次数的变量并输出其值,分析三种序列状态的算法时间复杂
性
2.对给定的有序查找集合,通过折半查找与给定值k相等的元素。
3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置,
算法如何改进?
三、设计与编码
1.本实验用到的理论知识
2.算法设计
3.编码
package sort_search;
import java.util.Scanner;
public class Sort_Search {
//冒泡排序算法
public void BubbleSort(int r[]){
int temp;
int count=0,move=0;
boolean flag=true;
for(int i=1;i flag=false; count++; for(int j=0;j if(r[j]>r[j+1]){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; move++; flag=true; } } } System.out.println("排序后的数组为:"); for(int i=0;i System.out.print(r[i]+" "); } System.out.println(); System.out.println("比较次数为:"+count); System.out.println("移动次数为:"+move); } public static int BinarySearch(int r[],int key){ //折半查找算法 int low=0,high=r.length-1; while(low<=high){ int mid=(low+high)/2; if(r[mid]==key){ return mid; } else if(r[mid]>key){ high=mid-1; } else{ low=mid+1; } } return -1; } //测试 public static void main(String[] args) { Sort_Search ss=new Sort_Search(); int t[]=new int[13]; System.out.println("依次输入13个整数为:"); Scanner sc=new Scanner(System.in); for(int i=0;i t[i]=sc.nextInt(); } System.out.println("排序前的数组为: "); for(int i=0;i System.out.print(t[i]+" "); } System.out.println(); ss.BubbleSort(t); //查找 while(true){ System.out.println("请输入要查找的数: "); int k=sc.nextInt(); if(BinarySearch(t,k)>0) System.out.println(k+" 在数组中的位置是第: "+ BinarySearch(t,k)); else System.out.println(k+" 在数组中查找不到!"); } } } 四、运行与调试 1.在调试程序的过程中遇到什么问题,是如何解决的? 问题:在计算比较次数和移动次数时,计算数据明显出错。 原因:在进行移动和比较的过程中,没有更新标志,导致计数出错。 解决办法:在比较和移动的过程中,有进行比较和移动的操作时,更新标志。然后按标志计数。 2.设计了哪些测试数据?预计结果是什么?说明: 测试了int类型数据: 241 17 23 45 37 4 31 43 11 89 33 101 177 预计排序后结果为:4 11 17 23 31 33 37 43 45 89 101 177 241 比较次数:①无序:8次②正序:1次③反序:12次 移动次数:①无序:30次②正序:0次③反序:78次 查找数33的位置为:5 查找数101的位置为:10 查找数100的结果为:查找不到 3.程序运行的结果如何 I.无序输入: