正文 

当前位置： 首页 > 技术 > java教程

20172308实验三《程序设计与数据结构》查找与排序实验报告(代码片段)

zhouyajie zhouyajie     2023-01-30     373

关键词：

20172308 2018-2019-1 实验3 《查找与排序》报告

课程：《程序设计与数据结构》
班级： 1723
姓名： 周亚杰
学号：20172308
实验教师：王志强
实验日期：2018年10月20日
必修/选修： 必修

1.实验内容

  • 查找与排序-1：定义一个Searching和Sorting类，并在类中实现linearSearch, SelectionSort方法
  • 查找与排序-2：重构代码
  • 查找与排序-3：参考http://www.cnblogs.com/maybe2030/p/4715035.html 在Searching中补充查找算法并测试
  • 查找与排序-4：补充实现课上讲过的排序方法
  • 查找与排序-5：编写Android程序对各种查找与排序算法进行测试

2. 实验过程及结果

  • 查找与排序-1：
  1. 定义一个Searching和Sorting类
  2. 在类中实现linearSearch, SelectionSort方法
  3. 10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位
  4. 测试用例的选取要考虑到方法的形参，设计选取的用例
  5. 完成测试
  6. 结果截图：
    技术分享图片

技术分享图片

  • 查找与排序-2：
  1. 重构代码
  2. 把Sorting.java Searching.java放入 cn.edu.besti.cs1723.（姓名首字母+四位学号）包中
  3. 把测试代码放test包中
  4. 重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）
  5. 结果截图
    技术分享图片
    技术分享图片
  • 查找与排序-3：
  1. 参考http://www.cnblogs.com/maybe2030/p/4715035.html 在Searching中补充查找算法并测试
  2. 根据参考博客给的C++代码，用Java完成方法的编写
  3. 提交运行结果截图
    技术分享图片
    技术分享图片
    技术分享图片
    技术分享图片
    技术分享图片
  • 查找与排序-4：
  1. 补充实现课上讲过的排序方法：希尔排序，堆排序，二叉树排序等(至少3个)
  2. 测试实现的算法（正常，异常，边界）
  3. 提交运行结果截图
    技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

  • 查找与排序-5：
  1. 编写Android程序对各种查找与排序算法进行测试
  2. 将方法类文件复制到Android studio中
  3. 根据需求设计界面，使能够输入数据，返回排序结果；输入查找值，返回true或false
  4. 提交运行结果截图
    技术分享图片

技术分享图片
技术分享图片
技术分享图片

3. 实验过程中遇到的问题和解决过程

  • 问题1：实验3是根据参考博客里的内容完成查找方法的编写，比如没有学过的斐波那契查找方法，但是博客里只给了C++的代码，在理解意思之后用Java写出来。
    在写二分查找代码的时候，查找的结果出现了问题：如图
    技术分享图片

  • 问题1解决过程：
    （图中的运行结果是不对的，但是代码是修改之后的）
    测试运行的结果是输出了0，这个很奇怪，输出的应该是我要查找的数字才对
    然后对比参考博客里给的C++代码：
//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)

    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    
    return -1;


//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)

    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);

我用的是递归方法
二分查找是在有序的基础上进行查找的：
参考博客给的方法需要传进去查找的范围，所以在找中间值的时候需要把下限加上
然后判断中间值与要查的值大小关系
若正好相等，直接返回要查值的索引位置
若不相等，则对中间值加减1，然后到新的折半区域求新的中间值，判断相等关系
......
如此递归下去

debug之后，发现问题所在：参考博客里的代码有点问题
方法是类似于上面所说的，但是每一次递归都缺少一次判断：
即每一次递归，新的索引中间值都会增或减1，即缺少判断中间值到达边界的条件
如果要查找的值并不存在，则查到边界的时候，就会越界

在博客的评论里也有人回复了
技术分享图片

加上条件之后即可

插值算法与二分查找类似，存在一样的问题
代码如下：

//插值查找
int InsertionSearch(int a[], int value, int low, int high)

    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);

插值查找不再是一半一半的查找，而是根据所给查找的长度大小来分割查找的区域

修改后的代码如下：

public static boolean InsertionSearch(Integer[] data, int min, int max, int target)
        boolean flag= false;
        int mid = min+(target-data[min])/(data[max]-data[min])*(max-min);

        if (mid <= max || mid >= min) 
            if (data[mid] == (target)) 
                flag = true;
             else if (data[mid] > (target)) //中间大于目标
                if (min <= mid - 1) 
                    flag = InsertionSearch(data, min, mid - 1, target);
                
             else if (data[mid] < target) 
                if (mid + 1 <= max) 
                    flag = InsertionSearch(data, mid + 1, max, target);
                
            
        
        return flag;

即也加入一行判断，保证mid不会越界
这个也有人评论了
技术分享图片

  • 问题2：实验2的代码重构，要求用命令行运行程序，很久没有用Linux，已经忘得差不多了

  • 问题2解决过程：
    这个问题在实践截止前也没能解决，因为虚拟机的问题没有在Ubuntu上测试运行
    于是在IDEA的命令行上试了很久，百度了很多参考博客，结果都没能成功
    后来试了一下基本命令，如新建文件，ls等结果是——找不到命令（手动脸黑）
    这真是一个悲伤的故事
    百度了一下，应该跟IDEA的命令行相关配置有关

  • 问题3：在Android studio里实现前四个实验的功能，其间遇到了小问题

  • 问题3解决过程：
    第一个是将文件复制到Android studio里面时，原先文件里的import引用到这里不能用了，因为AS里已经有一些包结构了
    但是手动改的话会累死人的，因为这些查找用到了许多本书前几章的代码，懒得找，，，索性将所有文件都拷过去，所以说一个一个文件的改不现实
    所以根据包名，将这几个实验的代码放进相应的包里即可

4.感悟

本次实验让我意识到学过的只是应当多用多回顾，比如说Linux，Android studio，而不能学过就算了

201723272018-2019-1《程序设计与数据结构》实验三：查找与排序

201723272018-2019-1《程序设计与数据结构》实验三：查找与排序课程：《Java软件结构与数据结构》班级：201723姓名：马瑞蕃学号：20172327实验教师：王志强实验日期：2018年11月19日必修/选修：必修一、实验内容：实验二查找与排序-1... 查看详情

20172328《程序设计与数据结构》实验三：查找与排序

20172328《程序设计与数据结构》实验三：查找与排序课程：《软件结构与数据结构》班级：1723姓名：李馨雨学号：20172328实验教师：王志强老师实验日期：2018年11月19日-2018年11月25日必修选修：必修一、实验要求内容实验1：定义... 查看详情

20172308《程序设计与数据结构》第七周学习总结(代码片段)

教材学习内容总结第十一章二叉查找树一、概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，父结点小于或等于右孩子（二叉查找树的定义是二叉树定义的扩展）二、用链表实现二叉查找树addElement操作：ad... 查看详情

201723132017-2018-2《程序设计与数据结构》实验三报告

201723132017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：李楠学号：20172330实验教师：王志强实验日期：2018年11月19日必修/选修：必修1.实验内容实验三-查找与排序-1定义一个Searching和Sor... 查看详情

201723252017-2018-2《程序设计与数据结构》实验三报告(代码片段)

201723252017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：邓煜坤学号：20172325实验教师：王志强实验日期：2018年11月19日必修/选修：必修1.实验内容实验三-查找与排序-1定义一个Searching和... 查看详情

20172308《程序设计与数据结构》第十一周学习总结

201723082017-2018-2《Java程序设计》第十周学习总结教材学习内容总结第24章初识Android1.应用程序结构：两个节点app：-manifests（包含AndroidManifest.xml文件，描述应用程序）-java（包含所有的Java应用程序和测试类）-res（包含资源文件）Gr... 查看详情

20172308《程序设计与数据结构》第八周学习总结

201723082017-2018-2《Java程序设计》第八周学习总结教材学习内容总结1.多态a.体现：父类引用指向了自己的子类对象；父类的引用接受自己的子类对象。（eg:父类f=new子类();）b.好处：大大提高了程序的扩展性。c.前提：类与类之间有... 查看详情

20172308《程序设计与数据结构》第五周学习总结

201723082017-2018-2《Java程序设计》第五周学习总结教材学习内容总结1.条件判断a.if语句:如果条件表达式的运算结果是true，则执行if中的语句，然后执行if后面的语句b.if-else语句：如果条件成立执行第一条语句，不成立则执行else语句... 查看详情

实验三-查找与排序-5（选做，加分）补做

题目编写Android程序对各种查找与排序算法进行测试提交运行结果截图推送代码到码云解答importandroid.content.Intent;importandroid.support.v7.app.AppCompatActivity;importandroid.os.Bundle;importandroid.view.View;importandroid.widget.Button;impo 查看详情

201723182017-2018-2《程序设计与数据结构》实验3报告

201723182017-2018-2《程序设计与数据结构》实验3报告课程：《程序设计与数据结构》班级：1723姓名：陆大岳学号：20172318实验教师：王志强实验日期：2018年11月19日必修/选修：必修1.实验内容实验三-查找与排序-1定义一个Searching和So... 查看详情

201723012017-2018-2《程序设计与数据结构》实验三报告

201723012017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：郭恺学号：20172301实验教师：王志强老师助教：张旭升/刘伟康实验日期：2018年5月16日必修/选修：必修1.实验内容实验1：代码规... 查看详情

#学号2017-2018-20172309《程序设计与数据结构》实验三报告(代码片段)

学号2017-2018-20172309《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：王志伟学号：20172309实验教师：王志强老师实验日期：2018年4月18日必修/选修：必修1.实验内容实验三敏捷开发与XP实践（1）... 查看详情

20172308《程序设计与数据结构》第八周学习总结(代码片段)

教材学习内容总结第十二章优先队列与堆一、堆：具有两个附加属性的一颗二叉树它是一颗完全树对每一结点，它小于或等于其左右孩子（或大于等于其左右孩子）最小堆：对每一结点，它小于或等于其左右孩子最大堆：对每一... 查看详情

1723222018-2019-1《程序设计与数据结构》实验三报告(代码片段)

1723222018-2019-1《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：张昊然学号：20172322实验教师：王志强助教：张之睿/张师瑜实验日期：2018年11月19日必修/选修：必修1.实验内容此处填写实验的具... 查看详情

201723112017-2018-2《程序设计与数据结构》实验三报告(代码片段)

201723112017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：赵晓海学号：20172311实验教师：王志强实验日期：2018年5月27日必修/选修：必修1.实验内容（1）代码规范http://www.cnblogs.com/rocedu/p/4... 查看详情

201723132017-2018-2《程序设计与数据结构》实验三报告

201723132017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：余坤澎学号：20172313实验教师：王志强实验日期：2018年5月10日必修/选修：必修1.实验内容编程标准能够使代码更容易阅读和理解... 查看详情

2017-2018-2《程序设计与数据结构》实验三报告(代码片段)

学号2017-2018-2《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：康皓越学号：20172326实验教师：王志强实验日期：2018年5月16日必修/选修：必修1.实验内容代码规范协同测试重构密码学应用2.实验... 查看详情

201723032018-2019-1《程序设计与数据结构》实验三报告(代码片段)

201723032018-2019-1《程序设计与数据结构》实验三报告课程：《程序设计与数据结构》班级：1723姓名：范雯琪学号：20172303实验教师：王志强助教：张师瑜/张之睿实验日期：2018年11月19日必修/选修：必修实验内容节点一定义一个Sear... 查看详情