程序在Java中反轉鏈接列表

Question

我已經寫了下面的代碼，其中方法rev(list,list)不工作。請幫我確定有什麼問題。

import java.io.*; 
public class list 
{ 
    int d; 
    list l; 
    list() 
    { 
     d=0; 
     l=null; 
    } 

    void create()throws IOException 
    { 
     int n;// store number of nodes 
     BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
     System.out.println("Enter the first data"); 
     this.d=Integer.parseInt(br.readLine()); 
     System.out.println("Enter number of nodes to be made"); 
     n=Integer.parseInt(br.readLine()); 
     list temp; 
     list ptr=this; 
     for(int i=1;i<n;i++) 
     { 
      temp=new list(); 
      System.out.println("Enter the next data"); 
      temp.d=Integer.parseInt(br.readLine()); 
      temp.l=null; 
      ptr.l=temp; 
      temp=null; 
      ptr=ptr.l; 
     } 
    } 

    void delete(list lst, int n) 
    { 
     list ptr=lst; 
     list ptr1=ptr; 
     int c=1; 
     while(c<n) 
     { 
      ptr1=ptr; 
      ptr=ptr.l; 
      c++; 
     } 
     ptr1.l=ptr.l; 
     ptr.l=null; 
     ptr=null; 
     ptr1=null; 
    } 

    void insertmid(list lst,int x, int n) 
    { 
     list temp=new list(); 
     temp.d=x; 
     temp.l=null; 
     list ptr=lst; 
     int c=1; 
     while(c<n) 
     { 
      ptr=ptr.l; 
      c++; 
     } 
     temp.l=ptr.l; 
     ptr.l=temp; 
    } 

    void rev(list lst,list lst1) 
    { 

     lst1=null; 
     list ptr=new list(); 

     while(lst!=null) 
     { 
      ptr =lst; 
      lst=lst.l; 
      ptr.l=lst1; 
      lst1=ptr; 

     } 
    } 


    void display() 
    { 
     list ptr=this; 

     while(ptr!=null) 
     { 
      System.out.print(ptr.d+"\t"); 
      ptr=ptr.l; 
     } 
     System.out.println(); 
    } 

    public static void main(String args[])throws IOException 
    { 
     list l2=new list(); 
     list l3=new list(); 

     l2.create(); 
     l2.display(); 
     l2.insertmid(l2,14,2); 
     l2.display(); 
     l2.delete(l2, 3); 
     l2.display(); 
     l2.rev(l2,l3); 
     l2.display(); 

    } 
} 

Answer 1

你應該做的第一件事情就是讓自己熟悉Java Naming Conventions因爲它會使你的代碼更清潔和更容易理解。您當前的代碼不區分類或方法或變量。

其次，好像你是從C++背景的和不知道的Java總是passes by value

這裏有一件事你是這樣做是沒有意義的：

void rev(list lst,list lst1) 
{ 

    lst1=null; // this is pointless, essentially, you are using a passed argument as a local variable. 
    // ... 

代碼波紋管實際上是等價的：現在

void rev(list lst) 
{ 

    list lst1=null; //just create lst1 right here, don't need to pass it in as a parameter 
    // ... 

，我不會去清理你的整個代碼，但我會給你的算法來反向鏈接列表，你可以納入你的計劃：

public Node reverseList(Node head) { 
    Node newHead = null;  // New head of the reversed list 
    Node prev, curr, next;  // Tracker pointers to previous, current and next node 
    prev = null; 
    curr = head; 
    next = null; 
    while(curr != null) {  // Iterate through the list 
     next = curr.next;  // Remember the next node 
     curr.next = prev;  // Point the current node to the previous 
     prev = curr;   // Update the previous node tracker to the current node 
     curr = next;   // Update the current node tracker to the next node 
     if(next == null) {  // If we reached list end, store the new head 
      newHead = prev; 
     } 
    } 
    return newHead; 
} 

Answer 2

你可以試試這個使用Java集合類：

import java.util.LinkedList; 
import java.util.List; 
import java.util.Scanner; 

class ReverseList { 
List<Integer>list=new LinkedList<Integer>(); 

public void initializeList(){ 
    Scanner in=new Scanner(System.in); 
    System.out.println("Enter number of nodes:"); 
    int no=Integer.parseInt(in.next()); 

    for(int i=0;i<no;i++){ 
     list.add(Integer.parseInt(in.next())); 
    } 
    in.close(); 
} 

public void displayList(){ 
    System.out.println(list); 
} 

public void reverseList(){ 
    List<Integer>list2=new LinkedList<Integer>(); 

    for(int i=list.size()-1;i>=0;i--){ 
     list2.add(list.get(i)); 
    } 
    this.list=list2; 

} 

public static void main(String[] args) { 
    ReverseList rl1=new ReverseList(); 
    rl1.initializeList(); 
    rl1.displayList(); 
    rl1.reverseList(); 
    rl1.displayList(); 
} 
} 

Answer 3

請請遵循標準的命名約定。這樣做會使您的代碼多更易於閱讀。具體而言，引用類型（類和接口）的名稱應以大寫字母開頭（例如List），而方法和實例變量的名稱應以小寫字母開頭。

這裏是你的非工作方法的一些意見：

void rev(list lst,list lst1) 
{ 

是沒有意義的傳遞LST1如果你馬上要丟棄任何值傳遞，就像你在這裏做的：

lst1=null; 

在這裏初始化變量'ptr'也是毫無意義的，因爲你對它做的第一件事（在循環的開始處）是賦值一個新值。事實上，在循環體內聲明它會更乾淨。

list ptr=new list(); 

下面的循環看起來像它可能是好的，但考慮到其離開最初由lst引用對象的狀態。提示：lst1初始化爲null。

while(lst!=null) 
    { 
     ptr =lst; 
     lst=lst.l; 
     ptr.l=lst1; 
     lst1=ptr; 
    } 

現在考慮Java只有傳遞值，所以傳遞給這個方法的任何引用都不會從調用者的角度改變。

} 

如果你還沒有看到它，那麼考慮這個問題：哪個節點現在在列表的頭部？

從更一般的意義上說，您有一點建模問題，因爲您的list類嘗試執行雙重任務，不僅表示整個列表，還表示該列表中的一個節點。這可以工作，它具有可能有用的屬性，但它也有可能導致麻煩的屬性。例如，你不能用你的類的一個實例來表示一個空列表。您也無法通過具有您的rev()簽名的方法有效地反轉您的班級實例所表示的列表。

Answer 4

使用的Java類命名約定我準備和改寫了您的代碼工作，因爲你問：

import java.io.*; 
public class List 
{ 
    private Integer data; 
    private List next; 

    List(Integer data, List next){ 
     this.data = data; 
     this.next = next; 
    } 

    List(){ 
     this(0); 
    } 

    List(Integer data) { 
     this(data, null); 
    } 

    List(List list) { 
     this(list.getData(), list.getNext()); 
    } 

    public void setData(Integer data) { 
     this.data = data; 
    } 

    public Integer getData() { 
     return this.data; 
    } 

    public void setNext(List next) { 
     this.next = next; 
    } 

    public List getNext() { 
     return this.next; 
    } 

    private List getElementAt(Integer element) { 
     List tmp = this; 
     for(int i = 0; i < element; i++){ 
      if (tmp.getNext() == null) { // preventing NPE 
       return tmp; 
      } 
      tmp = tmp.getNext(); 
     } 
     return tmp; 
    } 

    public void add_nodes()throws IOException { 
     Integer number_of_nodes;// store number of nodes 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     System.out.println("Enter number of nodes to add"); 
     number_of_nodes = Integer.parseInt(br.readLine()); 
     List ptr = this; 
     for(int i = 1 ; i < number_of_nodes ; i++) 
     { 
      List temp = new List(); 
      System.out.println("Enter the next data"); 
      temp.setData(Integer.parseInt(br.readLine())); 
      ptr.setNext(temp); 
      ptr = ptr.getNext(); 
     } 
    } 

    /** 
    * Function used to cut n-th element from list 
    * 
    * @param element - 0 means first element 
    */ 
    public void delete(Integer element){ 
     List tmp = this.getElementAt(element); 
     if (tmp.getNext() == null) { 
      return;    // preventing NPE 
     } 
     tmp.setNext(tmp.getNext().getNext()); //cutting 
    } 

    public void insertmid(Integer position, Integer data){ 
     List tmp = this.getElementAt(position); 
     List element = new List(data, tmp.getNext()); 
     tmp.setNext(element); 

    } 

    public void rewind(){ 
     List tmp = this; 
     List result = new List(this); 
     result.setNext(null); 
     while(tmp.getNext() != null) { 
      tmp = tmp.getNext(); 
      List current = new List(tmp); 
      current.setNext(result); 
      result = current; 
     } 
     this.setData(result.getData()); 
     this.setNext(result.getNext()); 
    } 


    void display() 
    { 
     List tmp = this; 
     while(tmp != null) { 
      System.out.print(tmp.getData() + "\t"); 
      tmp = tmp.getNext(); 
     } 
     System.out.println(); 
    } 

    public static void main(String args[])throws IOException 
    { 
     List list = new List(); 

     list.add_nodes(); 
     list.display(); 
     list.insertmid(4, 2); 
     list.display(); 
     list.delete(3); 
     list.display(); 
     list.rewind(); 
     list.display(); 

    } 
} 

Answer 5

我已經在列表中末尾編寫的代碼僅插入一個節點。 您可以添加一個新的方法（函數）來根據您的要求在開始處添加節點並從列表中刪除節點。

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

class Node{ 
private int data; 
private Node next; 
private Node prev; 

Node(Node n){ 
    this.data=n.data; 
    this.next=n.next; 
    this.prev=n.prev; 
} 

Node(int data){ 
    this.data=data; 
    this.next=null; 
    this.prev=null; 
} 
public int getData() {return data;} 
public void setData(int data) {this.data = data;} 

public Node getNext() {return next;} 
public void setNext(Node next) {this.next = next;} 

public Node getPrev() {return prev;} 
public void setPrev(Node prev) {this.prev = prev;} 
} 

class MyLinkedList{ 
    private Node start; 
    private Node end; 


    public Node getStart() { 
     return start; 
    } 


    public void setStart(Node start) { 
     this.start = start; 
    } 


    public Node getEnd() { 
     return end; 
    } 


    public void setEnd(Node end) { 
     this.end = end; 
    } 


    public boolean isEmpty(){ 
     return start==null; 
    } 

    //data from arguments 
    public void addNode(int data) throws NumberFormatException, IOException{ 

     Node n=new Node(data); 
     if(isEmpty()){ 
      start=end=n; 
     }else 
      if(start==end){ 
       start.setNext(n); 
       n.setPrev(start); 
       end=n; 
      } 
     else{ 
      end.setNext(n); 
      n.setPrev(end); 
      end=n; 
     } 

    } 



    public void reverse() throws NumberFormatException, IOException{ 
     MyLinkedList revList=new MyLinkedList(); 
     Node currNode=this.getEnd(); 

     do{ 

      revList.addNode(currNode.getData()); 
      currNode=currNode.getPrev(); 
     }while(currNode!=null); 

     this.start=revList.getStart(); 
     this.end=revList.getEnd(); 
    } 

    public void traverseFromStart(){ 
     Node n=start; 
     do{ 

      System.out.print(n.getData()+"-->"); 
      n=n.getNext(); 
     }while(n!=null); 
     System.out.println(); 
    } 

    public void traverseFromEnd(){ 
     Node n=end; 
     do{ 

      System.out.print(n.getData()+"-->"); 
      n=n.getPrev(); 
     }while(n!=null); 
     System.out.println(); 
    } 

    public static void main(String[] args) throws NumberFormatException, IOException { 
     MyLinkedList list=new MyLinkedList(); 
     System.out.print("Enter No. of Nodes:"); 
     BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
     int noOfNodes=Integer.parseInt(in.readLine()); 

     for(int i=0;i<noOfNodes;i++){ 
      System.out.print("Enter value of this node:"); 

      list.addNode(Integer.parseInt(in.readLine())); 
     } 


     list.traverseFromStart(); 
     list.traverseFromEnd(); 
     list.reverse(); 
     list.traverseFromStart(); 
     list.traverseFromEnd(); 

    } 
}