学号 2019-2020-20182321 《数据结构与面向对象程序设计》第八周学习总结

教材学习内容总结

• 查找中最简单的查找就是线性查找了，也就是对一列元素一个一个的向下寻找，找到了再返回，线性查找中其实可以利用哨兵法来简化线性查找的过程。
• 简化查找的方法有二分查找，二分查找可以极大的减小算法的时间复杂度，但是缺点是其查找的内容必须是已经排序好的，对于那种不排序的杂乱的线性集合，二分查找法不适用，必须要先排序再查找。
• 除了以上的两种方法，我们其实还另外学了三种，哈希线性查找、哈希链表查找、二叉树查找，他们三个的查找方法我觉得都比以上查找快得多，但是前提是其必须要按照一定的要求将其进行排序，形成一个集合。
• 哈希就是找出每个单个元素与所在节点的关系，利用这层关系，我们对其进行区域性查找
• 二叉树查找就是利用链表形成一个二叉树，比父节点大的在右边，比父节点小的在左边，查找时顺着二叉树向下查找。
• 排序方面，最简单的两个也是我们在c语言里学的选择排序和冒泡排序，选择排序就是找出最大或者最小的元素依次放在数列的最左边，冒泡排序是两两进行比较，找出第一轮比较和后面几轮比较次数之间的关系，其效果就像是水池里的泡泡一样，小的或者大的数字会一点一点的向最上边移动

-插入排序就是将队列里一个又一个的值，插入到已经排序的子序列，如下面序列

20 18 23 21 20 19 11 02 21 14 55

又大到小，先比较前两个，20>18，所以序列不懂，再提取出23，与实现比较的那个两个序列先比较，发现23>20，所以23就在20、18的前面，后面数字以此类推，最后我们就可以得到序列的结果了！个人认为插入排序可以保证算法的稳定性（现对于选择排序来说）

• 在所有的算法里，最牛的就是快速排序了，快速排序类似于一种快速划分，是目前已经知道的最快速的一种排序方式。

• 归并排序有着一种“天下大事分久必合，合久必分”的感觉，是先将一串序列用递归的方法拆成一个又一个的数字，之后再按原来的道路走，将数字一组有一组的比较，最后得出正确的序列

教材中遇到的问题和解决过程

• 问题1：如何计算某算法的大o
• 问题1解决方法：所谓的算法实践复杂度，其实本质山是看一个代码它运行了几次，运行的次数多，则所需要的时间也会多，时间复杂度就会变大。如下代码

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这个代码需要执行n+1+n+1次，即2n+2次运算，那它的大o记数法又是多少？由大一的高数学习我们知道，随着循环次数的增加，常数项对函数的影响并不大，而n的一次项的影响又会若雨n的二次项，所以当函数中只有常数项时，大o计数法就是O(1),如果是有n的一次项，如上图所示的话，大O计数法就是O（n），有n的二次方，大O技术法就是：O(n^2)如下面的代码所示

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循环次数为 n
        for(int j = 0; j < n; j++) {       // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }
}

运算次数为n（n+1）。

当中，对于顺利执行的语句算法，总的时间复杂度，等于其中最大的时间复杂度如下面代码

void aFunc(int n) {
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

• 问题2：什么是快速排序？如何进行快速排序？
• 问题2解决方法：快速排序是目前已知的集中排序中最快速有效的一种排序，其本质上是在开头找到一个基准数据，然后排除这个基准数据在排序中真正属于自己 的位置，如下列的演示图片来源

<快速排序1》

由上图可知，我们设置两个指针，一个指向末尾，一个指向队头，设末尾的low所在的数为基准数，则大于基准数的放右边，小于基准数的放左边，这样就可以找到基准数正确位置

《快速排序2》

3

4

5

low和high相等的时候我们结束循环，这样就是找到了第一个基数的正确位置，照此多运行几轮，我们就会发现快速排序确实会比其他算法的速度快得很多，它先定义一个分界数，将左侧小于它，右侧大于它，再对两侧进行再次划分，如此重复，极大的加快了算法的运行速度。
如下为快速排序代码

private static int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }
}

问题3：什么是归并排序？如何实现归并排序？
问题3解决方法：
归并排序如下图所有演示一般

归并排序1

有了图以后，上面的都很好理解，那么应该如何合并归并排序的数组呢？我们有下面的方法

归并排序2

有了这两张图就很清晰的解释清楚归并排序是如何实现的了，代码如下

public static void mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

public static void sort(int[] arr, int L, int R) {
    if(L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 比较左右两部分的元素，哪个小，把那个元素填入temp中
    while(p1 <= mid && p2 <= R) {
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 上面的循环退出后，把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while(p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while(p2 <= R) {
        temp[i++] = arr[p2++];
    }
    // 把最终的排序的结果复制给原数组
    for(i = 0; i < temp.length; i++) {
        arr[L + i] = temp[i];
    }
}

代码调试中的问题和解决过程

• 问题1：《二叉树排序问题1》使用了二叉树排序，但是结果显示找不到数字
• 问题1解决方法：我们首先来debug一下
  《二叉排序树解决方法》
  源代码如下

Comparebale tree = new Comparebale(b);
     Comparebale head =new Comparebale(-1);
     head.setNext(tree);
     for(int i=1;i<n.length;i++)
     {
         int num =Integer.parseInt(n[i]);
         tree = head.getNext();
         while (tree!= null)
         {
                if(tree.geti()<num)
                    tree = tree.getNext();
                else  if(tree.geti()>num)
                    tree = tree.getSecondnext();
         }
        tree = new Comparebale(num);


     }
     tree = head.getNext();
        boolean i = searching.erchashu(tree,target);
        System.out.println(i);

我们通过dubug发现，树头的树枝被砍断了，所以才会找不到数字1，即head.getnext原本是想让tree这个指针回到树头的，但是谁曾想到，它居然把连起来的tree的树枝给砍断了，导致tree19的下两个节点全部都是null，我们通过与之前写的链表的代码进行了对比研究初步怀疑，此类构建数的是否只能在类里的方法才能实现，于是编写了一下代码来构建二叉树

package newwork;

public class erchashu {
    Comparebale tree = new Comparebale(-1);
    Comparebale head = new Comparebale(-1);
    int[] a = new int[12];
    public erchashu()
    {
        head.setNext(tree);
    }
    public void s(int[] b)
    {
        tree.setI(b[0]);
        for(int i=1;i<b.length;i++)
        {
            Comparebale c = new Comparebale(b[i]);
            tree = head.getNext();
         while (tree.geti()!=b[i])
         {
             if(tree.geti()<b[i]&&(tree.getNext()!=null))
             {
                 tree = tree.getNext();
             }
             else if(tree.geti()<b[i]&&tree.getNext()==null)
             {
                 tree.setNext(c);
                 tree=c;
             }
             else  if(tree.geti()>b[i]&&tree.getSecondnext()!=null)
                 tree = tree.getSecondnext();
             else if(tree.geti()>b[i]&&tree.getSecondnext()==null)
             {
                 tree.setSecondnext(c);
                 tree = c;
             }
         }


        }

    }
    public Comparebale get()
    {
        return head.getNext();
    }
}

由以上的代码看，我们改进了好几个方面，在循环里创建了一个变量c，利用添加元素进链表里的方法，将数给连接起来，然后运行看看

《二叉树运行图》

由图可看出，我们的运行成功了，方法有效，但是具体为什么在类中树枝不会被砍断，这发面还是要再研究研究

• 问题2：关于哈希链表查找的问题
• 问题2解决方法：当我输入23的时候，无法找到我的23数字，但是事实是在序列里我有23这个数字
  《哈希链表问题》

我进过debug查找，发现原因有几个：

1、在链中插入新的节点的时候只能a[i1]就跳到下面的节点去了，然后回不来，而用头指针的时候又再次出现了砍断数枝的问题

2、判定条件设置的不对，应当利用的是我们上面二叉树的判定条件，当当前节点不为空，其下一个节点也不为空的时候才可以跳入到下一个节点中去。
之前的问题都好解决，设计附加条件就好了，但是对于如何处理头被砍掉的问题，盛世难搞，我认为树枝没连上的话，应该是用前面几张中的链表连接的方法连接，但是对于回到头链表就被砍断了的问题，还需要研究研究。
经过改进，此代码目前只能连续插入两到三个数字，无法插入的更多（尽力了。。。。）

package newwork;

import java.util.Scanner;

public class haxilianbiao {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Comparebale[] data = new Comparebale[12];
        Comparebale target ;
        Searching searching = new Searching();
        String s = "19 14 23 1 68 20 84 27 55 11 10 79";
        String[] n = s.split("\\s");
        System.out.println("请输入你想要查找的数（哈希链表查找）");
        int a = scan.nextInt();
        target = new Comparebale(a);
     /*  for(int i =0 ; i<data.length;i++)//哈希链表
        {
            data[i] = new Comparebale(-1);
        }*/
        for(int i = 0;i<n.length;i++)
        {
            int num = Integer.parseInt(n[i]);
            int i1 = num%11;
            if(data[i1]==null)
                data[i1]= new Comparebale(num);
            if (data[i1]!=null)
            {
                Comparebale c = new Comparebale(num);
                data[i1].setNext(c);
            }
            /*if(data[i1]==null)
            data[i1] = new Comparebale(num);*/
        }
        boolean i = searching.lianbiao(data,target);
        if(i)
            System.out.println("数字存在已找到");
        else
            System.out.println("数字不存在找不到");
    }
}

《哈希链表查找运行结果》

• 问题3：《search问题》
  改写教材上的二分法时，发现无论输入数字，最后找到的都是零
• 问题3解决方法：对于循环，我们都是先debug一下
• 《searchdebug》

由图中可以看出，循环根本没有进行，直接就跳出去了。是啥原因呢？

经过仔细的审查，发现，是循环的条件出错了，midpoit的加减搞反了，所以循环根本没有执行
最终运行结果如下图

《search 最终 运行结果》

代码托管

（statistics.sh脚本的运行结果截图）

上周考试错题总结

上周无考试

• 上周博客互评情况
  • 20182334
  • 结对照片

其他（感悟、思考等，可选）

参考：软件工程软件的估计为什么这么难，软件工程 估计方法

• 计划学习时间:10小时

• 实际学习时间:8小时

• 改进情况：

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

• 《Java程序设计与数据结构教程（第二版）》

• 《Java程序设计与数据结构教程（第二版）》学习指导

• ...