Δομή Εύρεσης-Ένωσης με Συνδεδεμένες Λίστες Άσκηση

[guitarist2]

Έχω την παρακάτω άσκηση σε java για συνδεδεμένες λίστες ,κάνει compile, και όταν την τρέχω μου βγάζει nullpointerexception στις σειρές : ,πιστεύω ότι το λάθος είναι στην printSet ,προσπάθησα να την κάνω και με διαφορετικούς τρόπους αλλά ανεπιτυχώς. Ο κώδικας μου είναι εκεί που λέει /* enter your code */. Συμπεριλαμβάνω και την εκφώνηση της άσκησης. 

lab2.pdf

import java.io.*;

public class ListUnionFind {

    private class Node {
        int item;   // integer item in {1..N}
        int size;   // set size if this node is representative
        Node next;  // next node in list
        Node rep;   // representative node

        Node(int item) {
            this.item = item;
            this.size = 1;
            this.next = null;
            this.rep = this;
        }
    }
    
    private Node[] ItemNode; // provides access to list nodes
    private int N;           // number of items
    private int setCount;    // number of sets
    
    // make singleton set {v}
    Node makeSet(int v) {
        Node x = new Node(v);
        return x;
    }

    // initialize data structure
    public ListUnionFind(int N) {
        this.N = N;
        this.setCount = N;
        ItemNode =  new Node[N+1];     // array of references to list nodes
        for (int v = 1; v <= N; v++) {
            ItemNode[v] = makeSet(v);  // initialize N singleton sets
        }
    }
    
    int find(int v) {
        /* enter your code */
        int k = v;
        while(k != ItemNode[k].rep.item){
			k = ItemNode[k].rep.item;
		}
        return k; // change appropriately 
    }
	private int count=0;
    void unite(int v, int u) {
        /* enter your code */
        int a = find(v);
        int b = find(u);
        if(a != {
        	if(ItemNode[a].size >= ItemNode[b].size){
        		ItemNode[v].next = ItemNode[b].rep;
        		ItemNode[b].rep = ItemNode[a].rep;
        		ItemNode[a].size = ItemNode[a].size + ItemNode[b].size;
        	}
        	else{
        		ItemNode[u].next = ItemNode[a].rep;
        		ItemNode[a].rep = ItemNode[b].rep;
        		ItemNode[b].size = ItemNode[a].size + ItemNode[b].size;
        	}
        	count++;
        }
    }

    int setCount() {
        /* enter your code */
        return N-count; // change appropriately 
    }
  
    void printSet(int v) {
        /* enter your code */
        int c = find(v);
/*        Node t = ItemNode[c].next;
        while(t != null){
        	System.out.println(t.item);
        	t=t.next;
        }*/
/*        int t = c;
        while(ItemNode[t].next != null){
        	System.out.print(ItemNode[t].item);
        	t=ItemNode[t].next.item;
        }*/
        System.out.print(c+" ");
        int t = c;
        if(ItemNode[c].next != null){
        	for(int i=1;i <= ItemNode[c].size;i++){
        		t=ItemNode[t].next.item;
				System.out.print(t+" ");
			}
		}
		System.out.println("");	
           	
    }
      
    void printSets() {
        /* enter your code */
        for(int i=1;i <= N;i++){
        	if(ItemNode[i] == ItemNode[i].rep){
        		printSet(i);  
        	}
        } 			
    }
    
    public static void main(String[] args) {
        System.out.println("Test ListUnionFind");
        
        int N = 16; 
        ListUnionFind LUF = new ListUnionFind(N);
        
        for (int k=1; k<=3; k++){
            LUF.unite(k+1,k);
            LUF.unite(k+5,k+4);
            LUF.unite(k+9,k+8);
            LUF.unite(k+13,k+12);
        }
        LUF.unite(1,5);
        LUF.unite(9,13);
        LUF.printSets();
        LUF.unite(1,13);
        LUF.printSets();
    }
}

[kostas.xatzigeorgiou]

Αυτά τα λαθάκια τα έκανα και γώ γιατί μου φαίνονταν απλά στο μάτι.. ωστοσο διάβασα 2 μήνες OCA/OCP Advanced Class Design για να τα ξεκαθαρίζω μέσα μου..

 

Οταν λές  

int x; 

η Java κάνει αυτόματα το initialization στον primitive για σένα, δηλαδή

 x=0; 

και μετά αλλάζεις την τιμή πχ.

x=8;

και καταχωρεί στη συγκεκριμένη διεύθυνση μνήμης το 8.

 

Οταν όμως λές

 Integer num;

το num δέν περιέχει καμιά τιμή γιατί είναι reference της κλάση Integer.

 

Είναι pointer και η Java το κάνει αυτόματα null. 

 

Επομένως αν πάς και γράψεις μετα

num = new Integer(8);

δημιουργείς ένα object της κλάσης Integer και ο pointer num "δείχνει" το συγκεκριμένο αντικείμενο.

 

Το Exception που σου πετάει σημαίνει ότι δηλώνεις κάποια μεταβλητή χωρίς να δημιουργήσεις το object και το κάνεις dereference ΠΡΙΝ το δημιουργήσεις.

 

Πράγματι υπάρχουν περιπτώσεις που η Java μπορεί να μην σου λέει κάν που είναι το πρόβλημα.. πχ στη μέθοδο

public void someMethod(Object obj){
// code here 
}

το obj είναι null και επομένως μπορείς να καλέσεις την μέθοδο

someMethod(null);

Οταν όμως πάς να κάνεις κάτι με τη μέθοδο someMethod() και περάσεις κάποιο αντικείμενο σου πετάει το NullPointerException..

[guitarist2]

Αυτά τα λαθάκια τα έκανα και γώ γιατί μου φαίνονταν απλά στο μάτι.. ωστοσο διάβασα 2 μήνες OCA/OCP Advanced Class Design για να τα ξεκαθαρίζω μέσα μου..

 

Οταν λές  

int x; 

η Java κάνει αυτόματα το initialization στον primitive για σένα, δηλαδή

 x=0; 

και μετά αλλάζεις την τιμή πχ.

x=8;

και καταχωρεί στη συγκεκριμένη διεύθυνση μνήμης το 8.

 

Οταν όμως λές

 Integer num;

το num δέν περιέχει καμιά τιμή γιατί είναι reference της κλάση Integer.

 

Είναι pointer και η Java το κάνει αυτόματα null. 

 

Επομένως αν πάς και γράψεις μετα

num = new Integer(8);

δημιουργείς ένα object της κλάσης Integer και ο pointer num "δείχνει" το συγκεκριμένο αντικείμενο.

 

Το Exception που σου πετάει σημαίνει ότι δηλώνεις κάποια μεταβλητή χωρίς να δημιουργήσεις το object και το κάνεις dereference ΠΡΙΝ το δημιουργήσεις.

 

Πράγματι υπάρχουν περιπτώσεις που η Java μπορεί να μην σου λέει κάν που είναι το πρόβλημα.. πχ στη μέθοδο

public void someMethod(Object obj){
// code here 
}

το obj είναι null και επομένως μπορείς να καλέσεις την μέθοδο

someMethod(null);

Οταν όμως πάς να κάνεις κάτι με τη μέθοδο someMethod() και περάσεις κάποιο αντικείμενο σου πετάει το NullPointerException..

Καταλαβαίνω τι εννοείς, ωστόσο δεν καταλαβαίνω εγώ σε ποιο σημείο έχω το λάθος και δεν είμαι σίγουρος αν ο κώδικάς μου είναι σωστός, (πχ το for loop στη μέθοδο printSet).