数据结构实验五-查找与排序的实现

实 验 报 告

课程名称 数据结构 实验名称 查找与排序的实现 系别 专业班级 指导教师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

for(int j=0;jr[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.println();

System.out.println(\比较次数为：\ System.out.println(\移动次数为：\ }

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

System.out.println(\排序前的数组为： \ for(int i=0;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.无序输入：