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

一时失言乱红尘 2022-03-18 02:28 244阅读 0赞

# 题目 #

编写一个方法removeAfter()，接受一个链表结点作为参数并删除该结点的后续结点（如果参数结点或参数结点的后续结点为空则什么也不做）

# 分析 #

参数是node,由于Node类是私有的,那么就要创建个新的node或者写个方法得到Node

# java代码 #

package book1_3;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-16
     * 利用链表来实现Stack
     * 1 内部嵌套类Node:内容Item;指向Node
     * 2 成员变量:栈顶Node first   指针n
     * 3 方法:isEmpty size push pop resize没了 iterator
     **/
    public class LinkedListStack<Item> implements Iterable {
    
        private static class Node<Item>{//改成静态的
            Item item;
            Node next;
        }
        private Node first;//栈顶,最近添加元素,也是个类,有两个属性
        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;
        }
        //1.3.24
        public void removeAfter(Node node){
            Node current=first;
            while(current.next!=null){
                if(current.item.equals(node.item)){
                    break;
                }
                current=current.next;
            }
            current.next=null;
        }
        //1.3.24
        public Node getNode(Item item){
            Node current=first;
            while(current.next!=null){
                if(current.item.equals(item)){
                    break;
                }
                current=current.next;
            }
            return current;
        }
    
        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 fn(String exp) {
            String[] split = exp.split(" ");
            //使用我们自己定义的数据结构.注意:当new对象的时候要定义好泛型
            LinkedListStack<String> linkedListStack = new LinkedListStack<String>();
            for (String s : split) {
                //这里要多判断一下,f函数的成员变量n是否为零.如果为零,则说明数组里面没东西了,不能用pop()去取数据,否则则会报错
                if (s.equals("-") && !linkedListStack.isEmpty()) {
                    String pop = linkedListStack.pop();//取数据的前提是:数组里面还有数据才可以
                    System.out.println(pop);
                } else {
                    linkedListStack.push(s);
                }
            }
            System.out.println("-----------------end-------------------");
            System.out.println(linkedListStack.size() + " left on stack ");
            System.out.println("the date left in linkedListStack are:");
            for (Object s:linkedListStack
            ) {
                System.out.println(s);
            }
        }
        public static void main(String[] args) {
    //        String exp = "to be or not to - be - - that - - - is";
    //        fn(exp);
            LinkedListStack<String> list1=new LinkedListStack<String>();
            list1.push("d");
            list1.push("c");
            list1.push("b");
            list1.push("a");
            LinkedListStack<String> list2=new LinkedListStack<String>();
            list2.push("d");
            list2.push("c");
            list2.push("b");
            list2.push("a");
            for (Object s:list1
            ) {
                System.out.println(s);
            }
            //1通过方法得到Node
            Node b = list1.getNode("b");
            //2通过new构造器得到Node
            Node c=new Node();
            c.item="c";
    
            list1.removeAfter(b);
            list2.removeAfter(c);
            for (Object aa:list1
                 ) {
                System.out.println(aa);
            }
            for (Object bb:list2
                 ) {
                System.out.println(bb);
            }
    
        }
    }

# 运行结果 #

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

# 心得 #

共有类和私有类 静态类 互相调用比较复杂 暂时搞不懂  
其他好像不难

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