算法－第四版－练习1.3.28解答

以你之姓@ 2022-03-18 03:44 190阅读 0赞

# 题目 #

编写一个方法max()，接受一个链表的首结点作为参数，返回链表中键最大的节点的值。假设所有键均为正整数，如果链表为空则返回0。

# 分析 #

1.条件:必须采用递归的办法  
2.刚开始不会做.看了别人的答案以后  
思路:  
1.递归必须有2个基本条件,递归到最后的时候,返回一个确定的值  
2.在递归的时候可以返回下一次的计算比如返回f(n-1)或者f(n.next)

# java代码 #

package hk13;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-19
     **/
    public class W_1_3_28<Item> implements Iterable {
        private static class Node<Item> {//改成静态的
            Item item;
            Node next;
        }
    
        private Node first;//栈顶,最近添加元素,也是个类,有两个属性
        private Node last;
        private int n;//元素数量,类似指针
    
        public void push(Item item) {
            Node old = first;
            first = new Node();
            first.item = item;
            first.next = old;
            n++;
        }
    
        public Item pop() {
            n--;
            Item item = (Item) first.item;//多了个强转 为什么呢???
            first = first.next;
            return item;
        }
        //采用递归的方法啊
        public static int max(Node<Integer> node){
            //当递归到最后一次的时候,返回Node的值
            if(node.next==null){
                return node.item;
            }
            //当每次递归的时候比较max(x.next)和x.item的值,返回大的那个
            else {
                int result=max(node.next);//如果放在第一行,当最后一次循环的时候,就会报出空指针异常
                return result>node.item?result:node.item;//三元运算符,当比较结果是true取前面,是false取后面
            }
            
        }
    
        public static void printList(W_1_3_26 a) {
            for (Object o : a
            ) {
                System.out.print(o+" ");
            }
            System.out.println();
        }
    
        public int size() {
            return n;
        }
    
        public boolean isEmpty() {
            return n == 0;
        }
    
        @Override
        public Iterator iterator() {
            return new ListIterator();
        }
    
        private class ListIterator implements Iterator<Item> {
            private Node current = first;
    
            @Override
            public boolean hasNext() {
                return current != null;
            }
    
            @Override
            public Item next() {
                Item item = (Item) current.item;
                current = current.next;
                return item;
            }
    
            @Override
            public void remove() {
                //blank
            }
    
        }
    
        public static void main(String[] args) {
            Node<Integer> a1=new Node<Integer>();
            a1.item=1;
            Node<Integer> a2=new Node<Integer>();
            a2.item=2;
            Node<Integer> a3=new Node<Integer>();
            a3.item=3;
            Node<Integer> a4=new Node<Integer>();
            a4.item=5;
            Node<Integer> a5=new Node<Integer>();
            a5.item=4;
            a1.next=a2;
            a2.next=a3;
            a3.next=a4;
            a4.next=a5;
            int max = max(a1);
            System.out.println(max);
        }
    }

# 运行结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 心得 #

链表结构为4- 5- 3- 2- 1  
链表引用为a5-a4-a3-a2-a1  
进入递归函数以后.  
第一次返回4和max(a4)中大的值  
第二次返回5和max(a3)中大的值  
第三次返回3和max(a2)中大的值  
第四次返回2和max(a1)中大的值  
第五次max(a1)返回1  
然后在倒着往上计算出最大值  
递归还是相对抽象的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220318/c9ed659d9f12447698c1f852fa7d8db4.png