数据结构与算法--代码鲁棒性案例分析

╰半夏微凉° 2022-11-15 01:23 196阅读 0赞

#### 代码鲁棒性 ####

*  鲁棒是robust的音译，就是健壮性。指程序能够判断输入是否符合规范，对不合要求的输入能够给出合理的结果。
 *  容错性是鲁棒的一个重要体现。不鲁棒的代码发生异常的时候，会出现不可预测的异常，或者程序奔溃。
 *  由于鲁棒性非常重要，因此我们在写代码的时候，必须进行防御性编程，这个必须成为我们编程的一种习惯，编码过程中应该能够预见可能出现的问题，并适当处理。

#### 最容易出错的双指针操作 ####

*  链表中倒数第K个节点
 *  题目：输入一个链表，输出链表中倒数第k个结点。例如，链表依次是1,2，3,4，5,6，倒数第三个就是4。
 *  我们依然用之前我们在[讲解链表实现][Link 1]时候的链表对象定义

##### 分析 #####

*  此处题目要求的应该是单向链表，因为双向链表没有复杂度可言。为了得到倒数第K个节点，并且不能从尾部遍历，同样的案例从尾部到头打印单向链表，我们在之前的文章（[数据结构与算法–链表实现以及应用][Link 1]）中已经有详细的分析，此处同样也可以利用这种方法。
 *  以上方法中借助其他数据接口，栈实现，时间复杂度是O(N+k)，空间复杂度O(2n)。
 *  应该还有更加高效率的算法，我们还是从头遍历链表，假设有n个节点，那么倒数第k个节点从头开始数是第n-k+1 个节点
 *  如果我们能得到节点个数n大小，那么直接从头遍历n-k+1个就得到倒数第k个了 。
 *  我们用双指针实现，利用两个指针中间步数的差值来得到倒数第k个，比如，我们需要n-k+1的差距，也就是n-（k-1）
 *  当指针A 走到末尾的时候，指针B需要走k-1 的距离，那么此时B指针指向的就是倒数第k个
 *  例如倒数第2 个，那么B就比A 少走了2-1 = 1 步骤，就是指向倒数第二个了。
 *  如下图：

![在这里插入图片描述][20210330200226244.png]  
![在这里插入图片描述][20210330200236139.png]  
![在这里插入图片描述][2021033020024560.png]

![在这里插入图片描述][20210330200250211.png]

*  如上图一中P1走两步，P2 则指向头结点
 *  接着继续两个指针P1， P2，一起向前走，
 *  当P1走到链表尾，则，P2,正好走到倒数第三位置。
 *  如下diam实现：

/** * * 查找单向链表倒数第k个节点 */
        public static ListNode findLastKNode(ListNode head, int k){ 
            if(head == null || k == 0){ 
                return new ListNode(-1);
            }
            ListNode beforeNode = head;
            ListNode afterNode = head;
            for (int i = 0; i < k - 1; i++) { 
                if(beforeNode.getNext() != null){ 
                    beforeNode = beforeNode.getNext();
                }else { 
                    return new ListNode(-1);
                }
            }
            //确保有 k 个节点
            if(beforeNode.getNext() == null){ 
                return new ListNode(-1);
            }
            while (beforeNode.getNext() != null){ 
                beforeNode = beforeNode.getNext();
                afterNode = afterNode.getNext();
            }
            return afterNode;
        }

##### 鲁棒性分析 #####

*  双指针方法中需要注意的点还是挺多的：
    
     *  当我们输入head 结点为null时候回，由于代码会范问空指针内存，次数程序会奔溃
     *  输入head为头肩底的链表节点总数少于k个，此时，我们需要先走k-1 步骤，如果正好k-1个节点，那么之后的步骤会抛出NPL，如果少于k-1个节点，则此时就已经npl
     *  输入参数k为0 的时候，此时 k-1= -1，非法数值，-1 二进制位符号位1 此时会读成数据位，此时数据变为4294967295，此时for循环将会超过执行次数。

###### 相关问题 ######

*  问题一：求单向链表中介节点，奇数个返回中间节点，偶数个返回中间两个任意一个，同样双指针A,B， A每个循环走一步，B每个循环走两步，B到末尾，则A就在中间节点
 *  问题二：求解单向链表是否环形链表，同样双指针A,B，A走一步，B走两步，如果到最后B追上了A 则环形，如果B到最后null，则不是环形

#### 最容易死循环的链表问题 ####

*  题目：定义一个函数，输入链表头结点，反转并输出反转后的链表头结点。

##### 分析 #####

*  我们依然用 之前[链表的实现文章][Link 1]中定义的链表节点如下：

public class ListNode implements Comparable<ListNode> { 
        private Integer value;
        private ListNode next;
    ......
    }

*  链表反转涉及到每个节点的指针操作，非常容易出现死循环问题，为了正确理解整个过程，我们应该首先借助图形来直观的分析。如下：

![在这里插入图片描述][2021033112171642.png]

*  我一开始还是想到双指正方法，第一步骤分别指向钱两个节点，并且改变本节点的指针指向，我们此时需要知道的是，本节点信息，上一个节点信息，这里都符合，得到下一图步骤。

![在这里插入图片描述][20210331122010468.png]

*  但是此时我们无法循环到下一个节点3， 因此逻辑无法成立，我们需要借助第三个指针，P3，如下图

![在这里插入图片描述][20210331122245367.png]

*  如上，我们可以得到本节点信息，上一个节点信息，下一个节点信息，在经过p2 指针的转向后，我们无法通过P2.next得到下一个节点，因此我们循环时候，需要做如下调整 P2 = P1， P1 = P3， P3=P3.next，然后接着操作P1 节点指针，继续循环到最后p3.Next为null为止，如下图最终状态

![在这里插入图片描述][20210331122728453.png]

*  如上最终状态，因为我们每次只修改了P1 节点的指针指向，所以循环结束后，还有最后节点没有处理，我们需要在循环结束后处理。
 *  如上分析，我有如下实现：

/** * 反转单向链表 * */
        public static ListNode reverOverListNode(ListNode head){ 
            if(head == null){ 
                return head;
            }
            ListNode before = head;
            ListNode middle = head;
            ListNode after = head;
            if(middle.getNext() == null){ 
                return head;
            }
            middle = middle.getNext();
            if(middle.getNext() == null){ 
                middle.setNext(before);
                head.setNext(null);
                return middle;
            }
            after = middle.getNext();
            while (after.getNext() != null){ 
                middle.setNext(before);
                before = middle;
                middle = after;
                after = after.getNext();
            }
            //处理最后两个节点的指针
            head.setNext(null);
            middle.setNext(before);
            after.setNext(middle);
            return after;
        }

###### 鲁棒性分析 ######

*  在指针操作时候，最容易出现的三个问题：
    
     *  输入的链表头指针是努力，或者整个链表只有一个节点，必须在前三个步骤中判断
     *  反转后出现环形链表，在如上处理过程中，最容易忽略的头节点指针指向null，导致环形链表
     *  链表断裂， 最后一个步骤没有对最后的节点进行指针指向操作，导致最后一个节点处断裂。

#### 合并两个排序的链表 ####

*  题目：输入两个递增的链表，合并这两个链表并使得新的链表中节点任然按原有顺序有序。如下图：
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]
 *  链表一，链表而是两个递增链表，合并两个链表得到链表三
 *  这个问题我们需要注意的和上一个问题类似，还是链表断裂问题，还有环形链表问题，因为需要同时操作两个链表的指针。
 *  我们有如下分析：
    
     *  将一二个链表看出需要处理的一个组，比较第一个元素，得到小的一个，剔除当成新链表的head节点：  
        ![在这里插入图片描述][20210331145610638.png]

![在这里插入图片描述][20210331145614799.png]

*  将1 节点剔除后，将剩下的链表1 ，链表2 看成是一个整体，仍然比较第一个节点的大小，继续如上步骤

![在这里插入图片描述][2021033114584871.png]

*  继续同样的逻辑合并剩余的节点，这是典型的递归流程，我们可以定义递归函数完成合并过程。.
 *  如上分析有如下代码

/** * 递归合并两个顺序链表 * */
        public static ListNode mixTwoSortList(ListNode sortOne, ListNode sortTwo){ 
            if(sortOne == null && sortTwo == null){ 
                return new ListNode();
            }
            if(sortOne == null){ 
                return sortTwo;
            }
            if(sortTwo == null){ 
                return sortOne;
            }
            ListNode mergeHead = null;
            if(sortOne.getValue() < sortTwo.getValue()){ 
                mergeHead = sortOne;
                mergeHead.setNext(mixTwoSortList(sortOne.getNext(), sortTwo));
            }else { 
                mergeHead = sortTwo;
                mergeHead.setNext(mixTwoSortList(sortTwo.getNext(), sortOne));
            }
            return mergeHead;
        }

###### 鲁棒性分析 ######

*  首先还是空指针问题，一旦输入空链表立刻npl，因此我们应该对空链表单独处理

#### 更加复杂的指针操作案例树的子结构 ####

*  题目：输入两颗二叉树A，B，判断B是不是A树的子结构。二叉树的定义我们用之前章节中讲解的[二叉树实现原理][Link 2]中定义的树节点来实现。

/** * 二叉树节点对象定义 * * @author liaojiamin * @Date:Created in 15:24 2020/12/11 */
    public class BinaryNode { 
        private Object element;
        private BinaryNode left;
        private BinaryNode right;
    ......
    }

*  例如有如下两棵二叉树，A中有一部分子树结构和B是一直的，因此B是A的子结构：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]
 *  依据之前二叉树实现原理 的分析，树操作中指针比值链表更加复杂，与树相关的问题我们通常都会用递归去解决。
 *  如上题中查找A中包含B，可分为两步：
    
     *  第一步在A树中查找B的根节点一样的节点R，如果找到，执行下一步
     *  第二步，判断A中以R为根节点的子树与B树的结构是否一致，
 *  用如上图来分析：
    
     *  首先在A中找 8 这个节点，发现A的根节点就是8 ，我们将A以8节点为根节点的树，与B节点比较
     *  将8 的左子树看成完整的树，与B中左子树 比较，还是按第一步骤逻辑 发现不同则不需第三部
     *  如果相同则需要，将8 的右子树看出完整的树，与B中右子树比较，还是按第一步骤逻辑。
     *  如果以上都不同，则回到第一步，将A的左子树看出是一个完整的树与B的根节点比较，
     *  依次逻辑遍历整个A树，直到找到B一样结构或者遍历到叶子节点为止。
 *  依据如上分析，我们有如下递归实现，其中某些函数是用之前文章 [二叉树实现原理][Link 2]的某些功能：

/** * 判断 A树中是否包含B树 * @author liaojiamin * @Date:Created in 16:43 2021/3/30 */
    public class BinaryNodeComparable { 
    
        /** * 递归方式遍历树 * */
        public static boolean isComparable(BinaryNode tree1, BinaryNode tree2){ 
            if(tree1 == null || tree2 == null){ 
                return false;
            }
            boolean result = false;
            if(tree1.compareTo(tree2.getElement()) == 0){ 
                result = tree1HaveTree2(tree1, tree2);
            }
            if(!result){ 
                result = isComparable(tree1.getLeft(), tree2);
            }
            if(!result){ 
                result = isComparable(tree1.getRight(), tree2);
            }
            return result;
        }
    	 /** * 依次比较跟，左，右节点 * */
        public static boolean tree1HaveTree2(BinaryNode tree1, BinaryNode tree2){ 
            //t2 遍历完了并且都一致，则存在包含
            if(tree2 == null){ 
                return true;
            }
            //t2 不为空，t1 为空 ，则不存在包含
            if(tree1 == null){ 
                return false;
            }
            if(tree1.compareTo(tree2.getElement()) != 0){ 
                return false;
            }
            return tree1HaveTree2(tree1.getLeft(), tree2.getLeft())
                    && tree1HaveTree2(tree1.getRight(), tree2.getRight());
        }
    
        public static void main(String[] args) { 
            BinaryNode node1 = new BinaryNode(null, null, null);
            BinarySearchTree tree1 = new BinarySearchTree();
            Random random = new Random();
            for (int i = 0; i < 20; i++) { 
                node1 = tree1.insert(Integer.valueOf(i), node1);
            }
            tree1.printTree(node1);
    
            System.out.println("-------------");
            BinaryNode node2 = new BinaryNode(null, null, null);
            BinarySearchTree tree2 = new BinarySearchTree();
            for (int i = 0; i < 3; i++) { 
                node2 = tree2.insert(Integer.valueOf(i), node2);
            }
            tree2.printTree(node2);
            System.out.println(isComparable(node1, node2));
    
        }
    }

*  以上考察二叉树遍历算法的理解 以及递归的能力
 *  考察代码的鲁棒性，每个题型都有大量的指针操作，稍不注意就会有npl奔溃。我们应该在程序开始的时候采用防御性编程的方式
 *  每次范问指针地址之前都需要考虑这个指针是否有可能是null

[上一篇：数据结构与算法–代码完整性案例分析][Link 3]  
[下一篇：数据结构与算法–解决问题的方法- 二叉树的的镜像][-]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114397878
[20210330200226244.png]: /images/20221022/cd0fb68ec3204eb191e97f2e3daa3f1a.png
[20210330200236139.png]: /images/20221022/25725257ee6c4ec89cd07353c4645616.png
[2021033020024560.png]: /images/20221022/297a8f721eca483f9cd942ead08aefae.png
[20210330200250211.png]: /images/20221022/49fa4c021f11431c850d13825f9a130b.png
[2021033112171642.png]: /images/20221022/5452def50bef4c00853bf5d5c70a093c.png
[20210331122010468.png]: /images/20221022/a8e4218039f244fdade1b8739e490ec7.png
[20210331122245367.png]: /images/20221022/177cacaa25ca4015ac01b92d67fc8a11.png
[20210331122728453.png]: /images/20221022/48b07685db8d4ff0823b68cc1fb1e5a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221022/7f3df3882230423c9a6ecfecc9924753.png
[20210331145610638.png]: /images/20221022/611c77d3d4e744d9a28ff564641288a5.png
[20210331145614799.png]: /images/20221022/ef75f13431b446b4b2af262178fd6dab.png
[2021033114584871.png]: /images/20221022/1fde391e831a48d1b59b8a3b12e40ad1.png
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/111043418
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]: /images/20221022/78bab116b9664c1e9046cdf47b9ce83c.png
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/115199996
[-]: https://blog.csdn.net/liaojiamin0102/article/details/115456324