linked list σε κάθε στοιχείο ενός array -- C

[jimbakl]

Καλησπέρα σας, δεν είμαι κανένας από σχολή προγραμματισμού και προσπαθώ να μάθω συνδεδεμένες λίστες και δομές για να εφαρμόσω μερικά πράγματα σχετικά με την σχολή μου. Τεσπά.

 

Έχω έναν πίνακα αποστάσεων, n * n ,

>
99999	1		1		1	        99999
99999	99999	1	        99999	1
99999	99999	99999	99999	1
99999     99999        1             99999       1
99999	99999	99999	99999	99999

 

 

όπου dis[j] !=99999 υπάρχει σύνδεση. Θέλω λοιπόν να κάνω ένα διάνυσμα, adjacent[n] το οποίο θα ναι κάπως έτσι

 

adjacent[n]

||

0 --> 1 --> 2 --> 3

1 --> 2 --> 4

2 --> 4

3 --> 2 --> 4

4 -->

 

όπου 0,1,2,3,4, τα Node.id

 

 

δηλαδή να δείχνω κάθε φορά ο κάθε κόμβος (i) με ποιους γειτνιάζει, αλλά όχι μόνο το όνομα, θέλω κάθε φορά να επεξεργάζομαι αυτούς τους κόμβους, οπότε θέλω να φτιάξω λίστες που να ξεκινάνε από το array αυτό με τα struct node moy. Λογικά θα γίνεται αυτό που θέλω να κάνω, στην C

>struct Node{
int id;
double cost;
double distance;
struct Node *next_node;
}Node;

 

> 
main(){

struct Node *head, *current, *adjacent;

int i,j,n, **dis;
head=(struct Node *)calloc(1,sizeof(struct Node));
current=head;
FILE*fp=fopen("data.txt","r");
fscanf(fp,"%d",&n);   // n is the number of nodes
dis=callocInt2d(n,n);  //dynamically declaration of matrix dis[n][n]
adjacent=(struct Node *)calloc(n,sizeof(struct Node));		//adjacent is a matrix (1)x(n)  of structs, which will include all the adjacent nodes
for(i=0;i<n;i++){
	for(j=0;j<n;j++){
		fscanf(fp,"%d",&dis[i][j]);    //read from file the dis matrix
	}
}
//INITIALIZATION FOR ALL STRUCTS 
//===============================================
for(i=0;i<n;i++){
	Node.id=i;
	Node.distance=0;
	adjacent[i].id=i;			//adjacent is a matrix of structs, which will include all the adjacent nodes
	adjacent[i].cost=0;
	adjacent[i].distance=0;
}

//===============================================
//CREATE A LIST, ONE FOR EACH NODE TO ITS ADJACENT'S NODES
//===============================================
for(i=0;i<n;i++){
	for(j=0;j<n;j++){
		if(dis[i][j]!=99999){	//CHECK IF THERE IS CONNECTION   if !=99999 there is connection.
			adjacent[i].next_node=(struct Node *)calloc(1,sizeof(struct Node));
			
		}
	}
}

 

 

στο τελευταίο for loop, όπως το έχω στο μυαλό μου πρέπει να γίνει η δημιουργία της λίστας με τα struct nodes, το θέμα είναι πως δεν έχω βρει κάτι που να με βοηθάει, και ούτε και ένα εγχειρίδιο με απλά παραδείγματα, για newbies στις λίστες , δομές και pointers.

 

όποιος μπορεί ας με βοηθήσει λίγο να καταλάβω κυρίως τα βασικά με αυτό το θέμα, ....

Σας ευχαριστώ.

[migf1]

Αν ο πίνακας με τις λίστες έχει προβλέψιμο μέγιστο μήκος (και συνάμα δεν είναι memory-critical η εφαρμογή σου) τότε για να μην ταλαιπωρείσαι με πολύ house-keeping, δοκίμασε κάτι σαν το παρακάτω...

 

>
...
typedef struct Node {
/* node's data fileds here */
Node *next;
} Node;
...
#define MAXLISTS   100 

int main( void )
{
Node lists[ 100 ] = {NULL};
...
}

οπότε κάθε lists[ i ] θα είναι μια linked-list.

[nilosgr]

Τι διαφορα εχει το cost απο το distance;

Επισης το Node.id = i; και το Node.distance = 0; που εχει στο πρωτο loop, τι κανουν;

 

Λοιπον, το λαθος το εχεις στο δευτερο loop. πρεπει να εινα καπως ετσι:

>for(i=0;i<n;i++){
   for(j=0;j<n;j++){
       if(dis[i][j]!=99999){
           struct Node *new;   
           new = (struct Node *)calloc(1,sizeof(struct Node));
           new->id = j;
           new->cost = new->distance = dis[i][j];
           new->next_node = NULL;

           for(current = adjacent[i]; current->next_node != NULL; current = current->next_node);
           
           current->next_node = new;                                
       }
   }
}

[V.I.Smirnov]

Για να μην ταλαιπωρείται, το καλύτερο είναι να χρησιμοποιήσει την vector της STL (C++) :

 

vector<vector<my_type>>

 

Δεν βρίσκω προφανή λόγο (ει μη μόνον για εκπαίδευση) να παιδεύεται κάποιος να

ξαναφτιάξει πράγματα όταν υπάρχουν έτοιμα...

 

-

[jimbakl]

Τι διαφορα εχει το cost απο το distance;

Επισης το Node.id = i; και το Node.distance = 0; που εχει στο πρωτο loop, τι κανουν;

 

Λοιπον, το λαθος το εχεις στο δευτερο loop. πρεπει να εινα καπως ετσι:

for(i=0;i<n;i++){

for(j=0;j<n;j++){

if(dis[j]!=99999){

struct Node *new;

new = (struct Node *)calloc(1,sizeof(struct Node));

new->id = j;

new->cost = new->distance = dis[j];

new->next_node = NULL;

 

for(current = adjacent; current->next_node != NULL; current = current->next_node);

 

current->next_node = new;

}

}

}

TO node.id =i, kai to Node.distance=0 είναι μια αρχικοποίηση που κάνω, βάζω αποστάσεις αρχικές 0, και σαν ιδ ισο με το ονομα του κομβου.

distance είναι η απόσταση που καλύπτω, και cost είναι μια άλλη παράμετρο που θα βάλω στην συνέχεια, κάτι σαν budget constraint....

 

Για να καταλάβω..

struct Node *new; // ορίζεις έναν δείκτη τύπου Νοδε

new = (struct Node *)calloc(1,sizeof(struct Node)); //

new->id = j;

new->cost = new->distance = dis[j]; // για μένα cost ≠ distance άρα θα χω, new->cost =xxxxxx () και new->distance= dis[][] ......

new->next_node = NULL; // ???? γιατί =NULL ???

 

for(current = adjacent; current->next_node != NULL; current = current->next_node);

 

current->next_node = new;

 

Δεν εξηγείς λίγο αυτό το for() loop??? Γιατί σκοπός του θέματος που ανάρτησα δεν είναι να το αντιγράψω αλλά να το μάθω...

 

Σε ευχαριστώ πάντως για την βοήθεια...

 

 

Για να μην ταλαιπωρείται, το καλύτερο είναι να χρησιμοποιήσει την vector της STL (C++) :

 

vector<vector<my_type>>

 

Δεν βρίσκω τον λόγο (ει μη μόνον για εκπαίδευση) να παιδεύται κάποιος να ξαναφτιάξει πράγματα όταν υπάρχουν έτοιμα...

Γιατί δυστυχώς είναι για την C όλα αυτά...... Εγώ θα το κανα στο matlab αν ήταν δυνατόν..

[migf1]

Εγώ πάλι δεν έχω καταλάβει την εκφώνηση.

 

Αν θες έναν πίνακα (array) από λίστες, ο πιο απλός τρόπος είναι αυτός που σου έδειξα στο προηγούμενο ποστ. Αν πρέπει υποχρεωτικά ο πίνακας να οριστεί δυναμικά (π.χ. απαίτηση της άσκησης) τότε αποσαφήνισε τι ακριβώς ζητάει η άσκηση, γιατί προσωπικά δεν κατάλαβα τίποτα από αυτά που γράφεις στο αρχικό ποστ, ώστε να μπορέσω να σε βοηθήσω πιο ουσιαστικα.

 

ΥΓ Στην υπογραφή μου έχω ένα link στο οποίο εξηγώ αναλυτικά και στα Ελληνικά τις linked-lists. Ρίξε του μια ματιά, διότι πιθανότατα θα σε βοηθήσει να ξεκαθαρίσεις πολλά πράγματα για τις λίστες

[jimbakl]

Εγώ πάλι δεν έχω καταλάβει την εκφώνηση.

 

Αν θες έναν πίνακα (array) από λίστες, ο πιο απλός τρόπος είναι αυτός που σου έδειξα στο προηγούμενο ποστ. Αν πρέπει υποχρεωτικά ο πίνακας να οριστεί δυναμικά (π.χ. απαίτηση της άσκησης) τότε αποσαφήνισε τι ακριβώς ζητάει η άσκηση, γιατί προσωπικά δεν κατάλαβα τίποτα από αυτά που γράφεις στο αρχικό ποστ, ώστε να μπορέσω να σε βοηθήσω πιο ουσιαστικα.

 

ΥΓ Στην υπογραφή μου έχω ένα link στο οποίο εξηγώ αναλυτικά και στα Ελληνικά τις linked-lists. Ρίξε του μια ματιά, διότι πιθανότατα θα σε βοηθήσει να ξεκαθαρίσεις πολλά πράγματα για τις λίστες

 

 

 

θέλω να κάνω ένα array με (n) στοιχεία, το κάθε ένα από αυτά τα στοιχεία θα περιέχει και τα δεδομένα του κάθε κόμβου, που θα περιέχονται στην δομή Νode. Αυτό είναι το εύκολο κομμάτι. Στην συνέχεια θέλω σε κάθε ένα από τα (n) αυτά στοιχεία, να βάλω τους κόμβους με τους οποίους γειτνιάζει. πχ. to array[1] αντιστοιχεί στον κόμβο με id =1 , και ενώνεται με τους κόμβους 2 και 4. θέλω λοιπόν με κάποιο τρόπο να συνδέσω τον κόμβο 1 με τον 2 και τον 4 . .. κάτι σαν αυτό.. :

 

Πιστεύω να καταλαβαίνεις.. Μακάρι να τα χα τελείως ξεκάθαρα στο μυαλό μου αυτά με τις δομές και τις λίστες για να τα εξηγούσα καλύτερα και να ήξερα ακριβως τι ζητάω.

 

Θα μπορούσα να το κάνω με έναν 2d πίνακα και να γλιτώσω αυτό με τις λίστες, αλλά ο πίνακας των αποστάσεων και κατα συνέπεια οι συνδέσεις είναι σε sparse matrix.

[migf1]

θέλω να κάνω ένα array με (n) στοιχεία, το κάθε ένα από αυτά τα στοιχεία θα περιέχει και τα δεδομένα του κάθε κόμβου, που θα περιέχονται στην δομή Νode. Αυτό είναι το εύκολο κομμάτι. Στην συνέχεια θέλω σε κάθε ένα από τα (n) αυτά στοιχεία, να βάλω τους κόμβους με τους οποίους γειτνιάζει. πχ. to array[1] αντιστοιχεί στον κόμβο με id =1 , και ενώνεται με τους κόμβους 2 και 4. θέλω λοιπόν με κάποιο τρόπο να συνδέσω τον κόμβο 1 με τον 2 και τον 4 . .. κάτι σαν αυτό.. :

...

Πιστεύω να καταλαβαίνεις.

Είναι ακριβώς αυτό που σου έγραψα στο 1ο μου ποστ (όπου έχω lists βάλε array και όπου έχω MAXLISTS βάλε n ).

 

Μακάρι να τα χα τελείως ξεκάθαρα στο μυαλό μου αυτά με τις δομές και τις λίστες για να τα εξηγούσα καλύτερα και να ήξερα ακριβως τι ζητάω.

Διάβασε τις σημειώσεις στο link της υπογραφής μου.

 

Θα μπορούσα να το κάνω με έναν 2d πίνακα και να γλιτώσω αυτό με τις λίστες, αλλά ο πίνακας των αποστάσεων και κατα συνέπεια οι συνδέσεις είναι σε sparse matrix.

Δεν καταλαβαίνω πως ένας 2d πίνακας θα μπορούσε να υλοποιήσει αυτό που περιγράφεις (οι πίνακες έχουν fixed μέγεθος σε όλες τους τις διαστάσεις, ενώ εσύ θέλεις κάθε γραμμή να έχει διαφορετικό μήκος).

[jimbakl]

Είναι ακριβώς αυτό που σου έγραψα στο 1ο μου ποστ (όπου έχω lists βάλε array και όπου έχω MAXLISTS βάλε n ).

 

 

Διάβασε τις σημειώσεις στο link της υπογραφής μου.

 

 

Δεν καταλαβαίνω πως ένας 2d πίνακας θα μπορούσε να υλοποιήσει αυτό που περιγράφεις (οι πίνακες έχουν fixed μέγεθος σε όλες τους τις διαστάσεις, ενώ εσύ θέλεις κάθε γραμμή να έχει διαφορετικό μήκος).

 

 

είναι λάθος το ξέρω αλλά θα μπορούσα να τον κάνω ένα (n)x(n) μηδενικό πίνακα και μόνο όπου υπάρχει σύνδεση να βάλω 1...

απλά δεσμεύω τζάπα μνήμη έτσι...

[migf1]

είναι λάθος το ξέρω αλλά θα μπορούσα να τον κάνω ένα (n)x(n) μηδενικό πίνακα και μόνο όπου υπάρχει σύνδεση να βάλω 1...

απλά δεσμεύω τζάπα μνήμη έτσι...

Θα μπορούσες να το κάνεις και με bit-flags, ανάβοντας μονάχα τα bits που θέλεις για άσσους, μετά να το κάνεις και compress και έτσι θα κατανάλωνες την ελάχιστη δυνατή μνήμη... μερικά μόνο bytes.

 

Το θέμα είναι να κατασταλάξεις πως θέλεις να το υλοποιήσεις, και να το υλοποιήσεις.

[V.I.Smirnov]

Αυτό που θέλει είναι μια δομή "Αdjacency List".

 

Είναι κλασικός τρόπος περιγραφής γράφων που περιγράφει την

συνδεσιμότητα των κόμβων σε ένα γράφο Ν κόμβων.

Ο κοινός, απλοϊκός τρόπος είναι με πίνακες NxN αλλά πολύ πιο σπάταλος σε μνήμη.

Αdjacency lists χρησιμοποιούνται π.χ. σε τοπολογική ταξινόμηση γράφων,

critical path method, εύρεση ελάχιστης διαδρομής (αλγ. Dijkstra ) κλπ.

Έχω ασχοληθεί με τέτοια πράγματα παλιότερα αλλά σε C++.

 

Ωστόσο, και με φορμαλισμό πινάκων γίνεται αυτό που ζητά.

Το παρακάτω απόσπασμα είναι από ένα παλιό δικό μου πρόγραμμα που

δεσμεύει δυναμικά πίνακα με διαφορετικό πλήθος στοιχείων ανά γραμμή.

Eίναι C++ όμως, όχι C.

>  template<class Tipus> Tipus ** Init_Matrix_2D(long  nrows, long  *size_rows)
  {
  //the dimensions of size_rows must be [nrows] 

     Tipus **X;
     long  i;

     X = (Tipus **)calloc(nrows, sizeof(Tipus *));
     if (X == NULL)
        return NULL;

     long  s = 0;; 
     for (i = 0; i < nrows; i++)
        s += size_rows[i];
    
     Tipus* p = (Tipus*)calloc(s, sizeof(Tipus));
     if (p == NULL) 
     {
        free(X);
        return NULL;
     }
     
     for (i = 0; i < nrows; i++)
     {
        X[i] = p;
        p += size_rows[i];
     }
     
     return X;
  };

 

Πάντως κάτι σαν το παραπάνω μπορεί να γραφεί εύκολα και σε C και

να αποφευχθούν οι λίστες που είναι πιο δύσκολες...

 

-

Επεξ/σία 1 Απριλίου 2012 από V.I.Smirnov

[migf1]

Εμένα θα μου επιτρέψετε να επιμείνω πως η απλούστερη υλοποίηση είναι ο πίνακας από λίστες, που έγραψα εξαρχής. Ειδικά τώρα που ξέρουμε πως το n είναι γνωστό εκ των προτέρων.

[V.I.Smirnov]

Ο πίνακας λιστών είναι ο κλασικός, συνήθης τρόπος.

 

Ωστόσο, αν το σκεφτείς λίγο θα συμφωνήσεις ότι το

απλούστερο είναι ο 2D πίνακας με γραμμές διαφορετικού μήκους.

Είναι εννοιολογικά απλούστερη δομή (ενώ ο πίνακας λιστών εμπλέκει δύο : λίστες και πίνακα) και

όλα τα στοιχεία του προσπελαύνονται όπως σε κάθε πίνακα (αρκεί να είσαι μέσα στα όρια των διαστάσεων).

 

-

[migf1]

Έχεις δίκιο φίλε Smirnov, "χρυσή τομή" ήθελα να γράψω κι έγραψα "απλούστερη".

[Timonkaipumpa]

Ο πίνακας λιστών είναι ο κλασικός, συνήθης τρόπος.

 

Ωστόσο, αν το σκεφτείς λίγο θα συμφωνήσεις ότι το

απλούστερο είναι ο 2D πίνακας με γραμμές διαφορετικού μήκους.

Είναι εννοιολογικά απλούστερη δομή (ενώ ο πίνακας λιστών εμπλέκει δύο : λίστες και πίνακα) και

όλα τα στοιχεία του προσπελαύονται όπως σε κάθε πίνακα (αρκεί να είσαι μέσα στα όρια των διαστάσεων).

 

-

 

 

 

edit

 

Λάθος... δεν είχα δει την 2η σελίδα.

 

Τον 2D πίνακα με διαφορετικού μήκους γραμμές θα σου πρότεινα και εγώ.

 

 

Επίσης, με ποιους συνδέεται θα μπορούσες να το βγάζεις παίζοντας με bit masks ή bit arrays και έτσι έχοντας και την τιμή και την σύνδεση (εάν στο επιτρέπει ο τύπος δεδομένων που θα έχεις).