心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

20202304 实验七 《数据结构与面向对象程序设计》实验报告

发布时间：2022-06-30 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了20202304 实验七 《数据结构与面向对象程序设计》实验报告，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

# 20202304 2021-2022-1 《数据结构与面向对象程序设计》实验七报告课程：《程序设计与数据结构》班级： 2023姓名： 何锐学号：20202304实验教师：王志强实验日期：2021年11月4日必修/选修： 必修

 

一、实验内容

1.定义一个SeArching和Sorting类，并在类中实现linearSearch,SelectionSort方法，最后完成测试。要求不少于10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位提交运行结果图。

2.重构你的代码把Sorting.java Searching.java放入 cn.edu.besti.cs2023.（姓名首字母+四位学号） 包中（例如：cn.edu.besti.cs1823.G2301）把测试代码放test包中重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）

3.参考http://www.cnblogs.COM/maybe2030/p/4715035.htML ，学习各种查找算法并在Searching中补充查找算法并测试提交运行结果截图

4.实现排序方法等(至少3个)测试实现的算法（正常，异常，边界）提交运行结果截图（如果编写多个排序算法，即使其中三个排序程序有瑕疵，也可以酌情得满分）

5.编写AndROId程序对实现各种查找与排序算法进行测试提交运行结果截图推送代码到码云（选做，额外加分）

二、实验过程及结果

1.定义一个Searching和Sorting类，并在类中实现linearSearch,SelectionSort方法，最后完成测试。要求不少于10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位提交运行结果图。

Sorting类：

 

public class Sorting {
    public static void SelectionSort1(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }
    public static void SelectionSort2(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            int maxIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] > arr[maxIndex]){
                    maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }
    PRivate static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

Sorting测试类：

public class SortingTest {
    public static void main(String[] args) {
        int a[] = new int[]{20,20,23,04,20,21,11,11,04,03};
        int b[] = a;
        Sorting c = new Sorting();
        c.SelectionSort1(a);//正序
        for(int i=0;i<a.length;i++){
        System.out.printf(String.valueOf(a[i])+" ");}
        System.out.println("");
        c.SelectionSort2(b);//逆序
        for(int i=0;i<a.length;i++){
        System.out.printf(String.valueOf(b[i])+" ");}
    }
}

测试截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 

Searchiing类：

public class Searching{
    //顺序查找
    public void  linSearch(int[] data, int target)
    {
        int count=0;
        for(int i = 0; i < data.length; i++) {
            if(data[i]==target){
                System.out.println("找到目标，在第"+(i+1)+"位");
                count++;
            }
        }
        if (count==0)
            System.out.println("未查找到目标");
        else
            System.out.println("共有"+count+"个");
    }
    //二分查找（需要有序）
    public void binSearch(int[] data,int target)
    {
        int mid = data.length - 1;
        if(target == data.length){
            System.out.println("找到目标，在第"+mid+"位");
        }
        int start = 0;
        int end = data.length-1;
        while(start<=end){
            mid = (end - start) / 2 + start;
            if(target < data[mid]){
                end = mid - 1;
            }else if(target > data[mid]){
                start = mid + 1;
            }else if(target == data[mid]){
                System.out.println("找到目标，在第"+mid+"位");
            }else {
                System.out.println("未查找到目标");
            }
        }
    }
    public    int insSearch(int []data,int  left,int right,int target){

        if(left>right || target<data[0] ||target>data[data.length-1]){
            return -1;
        }

        int mid = left +(right - left) * (target - data[left])/ (data[right] -data[left]);
        int midVal =data[mid];
        if(target > midVal){
            return insSearch(data, mid+1, right, target);

        }else if(target < midVal){
            return insSearch(data, left, mid-1, target);
        }else {
            return mid;
        }
    }

}

Searching测试类：

public class SearchingTest {
    public static void main(String[] args) {
        int a[]=new int[]{20,20,23,04,20,21,11,11,04,03,78,77,56,51};
        Searching b = new Searching();
        b.linSearch(a,23);//正常情况
        b.linSearch(a,21);
        b.linSearch(a,11);
        b.linSearch(a,20);
        b.linSearch(a,78);//边际情况
        b.linSearch(a,03);
        b.linSearch(a,1000);//异常情况
        b.linSearch(a,5000);
    }
}

测试截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 

 

2.重构你的代码把Sorting.java Searching.java放入 cn.edu.besti.cs2023.（姓名首字母+四位学号） 包中（例如：cn.edu.besti.cs1823.G2301）把测试代码放test包中重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 测试截图

在Windows中：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 在linux中：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 

 

3.参考http://www.cnbLOGs.com/maybe2030/p/4715035.html ，学习各种查找算法并在Searching中补充查找算法并测试

（一）顺序查找：（适合于存储结构为顺序存储或链接存储的线性表。）

顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

@H_442_512@顺序查找的时间复杂度为O(n)。

代码：

 //顺序查找
    public void  linSearch(int[] data, int target)
    {
        int count=0;
        for(int i = 0; i < data.length; i++) {
            if(data[i]==target){
                System.out.println("找到目标，在第"+(i+1)+"位");
                count++;
            }
        }
        if (count==0)
            System.out.println("未查找到目标");
        else
            System.out.println("共有"+count+"个");
    }

实验截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 （二）二分查找：（元素必须是有序的，如果是无序的则要先进行排序操作。）

也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

期望时间复杂度为O(log2n)。

代码：

 

 //二分查找（需要有序）
    public void binSearch(int[] data,int target)
    {
        int mid = data.length - 1;
        if(target == data.length){
            System.out.println("找到目标，在第"+mid+"位");
        }
        int start = 0;
        int end = data.length-1;
        while(start<end){
            mid = (end - start) / 2 + start;
            if(target < data[mid]){
                end = mid - 1;
            }else if(target > data[mid]){
                start = mid + 1;
            }else if(target == data[mid]){
                int temp = mid + 1;
                System.out.println("找到目标，在第"+temp+"位");
                break;
            }else {
                System.out.println("未查找到目标");
            }
        }
    }

 

测试截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 （三）插值查找：

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

时间复杂度均为O(log2(log2n))。

代码：

public    int insSearch(int []data,int  left,int right,int target){

        if(left>right || target<data[0] ||target>data[data.length-1]){
            return -1;
        }

        int mid = left +(right - left) * (target - data[left])/ (data[right] -data[left]);
        int midVal =data[mid];
        if(target > midVal){
            return insSearch(data, mid+1, right, target);

        }else if(target < midVal){
            return insSearch(data, left, mid-1, target);
        }else {
            return mid+1;
        }
    }

测试截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 （四）斐波那契查找：

是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

代码：

 

 //斐波那契查找
    //先创建斐波那契数列
    public static int[] fib(int []data) {
        int[] f = new int[data.length];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < data.length; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
    //斐波那契查找
    public  int fibSearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;
        int mid = 0;
        int f[] = fib(a);
        while (high > f[k] - 1) {
            k++;
        }
        int[] temp = Arrays.copyOf(a, f[k]);
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (target < temp[mid]) {
                high = mid - 1;
                k--;
            } else if (target > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }

 

测试截图：

20202304 实验七 《数据结构与面向对象程序设计》实验报告

 

 

 完整代码（Searching）码云：https://gITee.com/besti2023javads/hr20202304/blob/master/Searching.java

 

 

4.实现排序方法等(至少3个) 测试实现的算法（正常，异常，边界） 提交运行结果截图（如果编写多个排序算法，即使其中三个排序程序有瑕疵，也可以酌情得满分）

（一）选择排序

首先在未排序数列中找到最小元素，然后将其与数列的首部元素进行交换，然后，在剩余未排序元素中继续找出最小元素，将其与已排序数列的末尾位置元素交换。

//选择排序
    public static void SelectionSort1(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

（二）冒泡排序

将待插元素，依次与已排序好的子数列元素从后到前进行比较，如果当前元素值比待插元素值大，则将移位到与其相邻的后一个位置，否则直接将待插元素插入当前元素相邻的后一位置，因为说明已经找到插入点的最终位置。

//冒泡排序
    public static void MaopaoSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

（三）插入排序

将待插元素，依次与已排序好的子数列元素从后到前进行比较，如果当前元素值比待插元素值大，则将移位到与其相邻的后一个位置，否则直接将待插元素插入当前元素相邻的后一位置，因为说明已经找到插入点的最终位置。

//插入排序
    public static void InsertSort(int[] arr) {
        if (arr.length >= 2) {
            for (int i = 1; i < arr.length; i++) {
                int x = arr[i];
                int j = i - 1;
                while (j >= 0 && arr[j] > x) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = x;
            }
        }
    }

（四）快速排序

简单的说, 就是设置一个标准值, 将大于这个值的放到右边(不管排序), 将小于这个值的放到左边(不管排序), 那么这样只是区分了左小右大, 没有排序, 没关系, 左右两边再重复这个步骤.直到不能分了为止.

//快速排序
    public static void Qucicksort(int[] arr, int begin, int end) {
        int a = begin;
        int b = end;
        if (a >= b) {
            return;
        }
        int x = arr[a];
        while (a < b) {
            while (a < b &amp;& arr[b] >= x) {
                b--;
            }
            if (a < b) {
                arr[a] = arr[b];
                a++;
            }
            while (a < b && arr[a] <= x) {
                a++;
            }
            if (a < b) {
                arr[b] = arr[a];
                b--;
            }
        }
        arr[a] = x;
        QucickSort(arr, begin, a - 1);
        QucickSort(arr, a + 1, end);
    }

（五）归并排序

简单的说把一串数,从中平等分为两份,再把两份再细分,直到不能细分为止,这就是分而治之的分的步骤. 再从最小的单元,两两合并,合并的规则是将其按从小到大的顺序放到一个临时数组中,再把这个临时数组替换原数组相应位置。

//归并排序
    public static void MergeSort(int[] a, int s, int e) {
        int m = (s + e) / 2;
        if (s < e) {
            MergeSort(a, s, m);
            MergeSort(a, m + 1, e);
            merge(a, s, m, e);
        }
    }
    private static void merge(int[] a, int s, int m, int e) {
        int[] temp = new int[(e - s) + 1];
        int l = s;
        int r = m + 1;
        int i = 0;
        while (l <= m && r <= e) {
            if (a[l] < a[r]) {
                temp[i++] = a[l++];
            } else {
                temp[i++] = a[r++];
            }
        }
        while (l <= m) {
            temp[i++] = a[l++];
        }
        while (r <= e) {
            temp[i++] = a[r++];
        }
        for (int n = 0; n < temp.length; n++) {
            a[s + n] = temp[n];
        }
    }

（六）希尔排序

基本上和插入排序的道理是一样的，只不过每次循环的步长都通过减半的方式来实现。

//希尔排序
    public static void XirSorting(int[] arr) {
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k > 0 && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
    }

完整版代码（Sorting）码云：https://gitee.com/besti2023javads/hr20202304/blob/master/Sorting.java

 

 

5.编写Android程序对实现各种查找与排序算法进行测试 提交运行结果截图 推送代码到码云（选做，额外加分）

 

 

 

三、 实验过程中遇到的问题和解决过程 问题1：一开始困顿于使用数组还是链表，后来发现根本没有必要纠结，都一样，重点是数学方法和实现。

 问题2：实现各种数学方法的时候发现十分难以理解，要反复做很多遍才能解决逻辑错误。而且由于数组从零开始，一开始总是让数据从1-.length导致很多问题

 问题3：装成包后windows运行总是出问题，调整了好多次classpath 和 javahome等环境变量才解决。

 

 

脚本宝典总结

以上是脚本宝典为你收集整理的20202304 实验七 《数据结构与面向对象程序设计》实验报告全部内容，希望文章能够帮你解决20202304 实验七 《数据结构与面向对象程序设计》实验报告所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：javalinuxloadloadmasterphppythonsortStringwhilewhile二分查找二分查找快速排序快速排序排序排序查找查找程序员程序员算法算法重构
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程