《算法》第四版 答案（二）习题1.3

本章节为习题1.3.18-1.3.28的答案

• 1.3.18
  答案

删除x的后续结点。

• 1.3.19
  答案

public class ex1_3_18 {

    
    /*public*/public static class Node{
        //否则所写的内部类为动态的，而主程序是public static class main 
        //在java中，类中的静态方法不能直接调用动态方法，只有将某个内部类修饰为静态类，然后才能够在静态类中调用该类的成员变量和成员方法
        String item;
        Node next;
    }
    
    public static void delete(Node first){//static 总是忘记啊 
        //java中静态类不能调用动态的方法
        
        if(first == null){
            System.out.println("wrong!");
        }
        else{
            while(first.next.next != null){
                first = first.next;
            }
            first.next.item = null;
            first.next = null;
        }
        
    }
    
    public static void exhibition(Node first){
        
        if(first == null){
            System.out.println("zero");
        }
        else{
            do{
                System.out.print(first.item);
                first = first.next;
            }while(first != null);//竟然不是first.next
            
            
        }
    }
    
    
    public static void main(String[] args) {
        
        Node first = new Node();
        Node second = new Node();
        Node third = new Node();
        
        //first.item = 'to';无效的字符常数  invalid character constant
        //双引号不要写成单引号了
        first.item = "i";
        second.item = "am";
        third.item = "poor";
        
        first.next = second;
        second.next = third;
        
        
        exhibition(first);
        System.out.println("  ");
        delete(first);
        exhibition(first);
            
    }   
}

• 1.3.20
  答案

import edu.princeton.cs.algs4.StdOut;

public class ex1_3_19 {
    
    public static class Node{
        
        String item;
        Node next;
    }
    
    
    
    public static void exhibition(Node first){
        Node current = first;
        if(current == null){
            StdOut.print("zero!");
        }
        else{
            do{
                StdOut.print(current.item);
                current = current.next;
            }while(current != null);
        }
        
    }
    
    public static void delete(Node first,int k)  
    {  
        // deal with k <= 0, list is empty  
        if (k <= 0 || first == null) return;  
        // deal with first node  
        if (k == 1)   
        {  
            first = first.next;  
            return;  
        }  
          
        // make current equals k-1 node  
        k--;  
        Node current = first;  
        while (current != null && --k != 0)  
        {  
            current = current.next;  
        }  
        // list length less than k  
        if (k != 0 || current == null || current.next == null)  
        {  
            return;  
        }  
        else  
        {  
            current.next = current.next.next;  
        }  
    }  
    
    
    
    public static void main(String[] args) {
        
        Node first = new Node();
        Node second = new Node();
        Node third = new Node();
        Node forth = new Node();
        
        first.item = "to";
        second.item = "or";
        third.item = "not";
        forth.item = "is";
        
        first.next = second;
        second.next = third;
        third.next = forth;
        
        exhibition(first);
        System.out.println(" ");
        delete(first,2);
        exhibition(first);
    }

}

• 1.3.21
  答案

import edu.princeton.cs.algs4.StdOut;


    public class ex1_3_20 {
        
        public static class Node{
            
            String item;
            Node next;
        }

        
        public static void exhibition(Node first){
            Node current = first;
            if(current == null){
                StdOut.print("zero!");
            }
            else{
                do{
                    StdOut.print(current.item);
                    current = current.next;
                }while(current != null);
            }
            
        }
        
        
        
        public static  boolean delete(Node first,String key)  
        {  
            for(Node current = first;current.next != null;current = current.next){
                
                if(current.item.equals(key))
                    return true;//小写且拼写不要错
            }
            
                return false;//不要写到for循环里面，会导致函数没有返回值
            
        }
        
        
        
        public static void main(String[] args) {
            
            Node first = new Node();
            Node second = new Node();
            Node third = new Node();
            Node forth = new Node();
            
            first.item = "to";
            second.item = "or";
            third.item = "not";
            forth.item = "is";
            
            first.next = second;
            second.next = third;
            third.next = forth;
            
            exhibition(first);
            System.out.println(" ");
            delete(first,"not");
            exhibition(first);
        }

    }

• 1.3.22
  答案

插入结点t，并使它成为x的后续结点

• 1.3.23
  答案

在更新t.next时，x.next已经不再指向x的后续结点，而是指向t本身！

明日继续补~