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

[nilosgr]

Σε καθε στοιχειο του πινακα adjacent ειναι μια κεφαλη σε λιστα, σωστα;

Οποτε για να βαλουμε ενα καινουριο στοιχειο στη λιστα, ενας απ τους πολλους τροπους ειναι να το βαλουμε στο τελος. Αυτο κανει το "αδειο" for-loop, ψαχνει για το τελευταιο στοιχειο την λιστας κι οταν το βρει τερματιζει. Δηλαδη στο τελος του loop ο current δειχνει στο τελευταιο στοιχειο

[migf1]

Ξανακοιταώ τώρα αυτό που έγραψα στην αρχική μου απάντηση, και διαπιστώνω αφενός πως στο Node lists[100] = {NULL};

λείπει ένας αστερίσκος, άρα πρέπει να είναι...

 

>Node *lists[ 100 ] = {NULL};

και αφετέρου πως τελικά πρέπει να έχει κι αυτό πολύ house-keeping

 

Πάω να γράψω στα γρήγορα μια απλοποιημένη του υλοποίηση (θα περνάω μόνο id's μέσα στο adjacency αντί για ολόκληρους κόμβους) και επιστρέφω.

 

EDIT:

 

Αν υπήρχε έτοιμη η βιβλιοθήκη για τη διαχείριση linked-lists θα ήταν μια χαρά, τώρα όμως έχει όντως πολύ house-keeping, ακόμα κι απλοποιημένο ... με κάτι τύπου C++ STL κι έναν garbage-collector θα αρκούσε μονάχα η main() και η adjacency_build()...

 

>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node Node;
struct Node {
int id;
/* other data fields go here */
Node *next;
};

#define N  5

/* --------------------------------------------------------------------------------- */
bool list_append( Node **list, int id )
{
Node *head = NULL, *dummy = NULL;
Node *new = calloc(1, sizeof(Node) );
if ( !new )
	return false;

new->id = id;
new->next = NULL;

if ( !*list ) {
	*list = new;
	return true;
}

head = dummy = *list;
while ( head ) {
	dummy = head;
	head = head->next;
}
dummy->next = new; 

return true;
}
/* --------------------------------------------------------------------------------- */
void list_print( Node *list )
{
while ( list ) {
	printf("%d ", list->id );
	list = list->next;
}
puts("\b");

return;
}
/* --------------------------------------------------------------------------------- */
void list_destroy( Node **list )
{
if ( !*list )
	return;

Node *dummy = NULL;
while ( *list ) {
	dummy = (*list)->next;
	free( *list );
	*list = dummy;
}

return;
}
/* --------------------------------------------------------------------------------- */
bool adjacency_build( Node *adjacency[N], int matrix[N][N] )
{
int i,j;

for (i=0; i < N; i++)
	for ( j=0; j < N; j++ )
		if ( 1 == matrix[i][j] )
			if ( !list_append(&adjacency[i], j) )
				return false;

return true;
}
/* --------------------------------------------------------------------------------- */
void adjacency_print( Node *adjacency[N] )
{
for (int i=0; i < N; i++) {
	printf( "adj[%d]: ", i );
	list_print( adjacency[i] );
}

return;
}
/* --------------------------------------------------------------------------------- */
void adjacency_destroy( Node *adjacency[N] )
{
for (int i=0; i < N; i++)
	list_destroy( &adjacency[i] );

return;
}
/* --------------------------------------------------------------------------------- */
int main( void  )
{
Node *adjacency[ N ] = { NULL };

int matrix[N][N] = {				/* sparse matrix */
	{ 0, 1, 1, 1, 0 },
	{ 0, 0,	1, 0, 1 },
	{ 0, 0,	0, 0, 1 },
	{ 0, 0,	1, 0, 1 },
	{ 0, 0,	0, 0, 0 }
};

if ( !adjacency_build( adjacency, matrix) ) {
	puts( "out of memory, aborting..." );
	goto failure;
}

adjacency_print( adjacency );

failure:
adjacency_destroy( adjacency );

system("pause");				/* windows only */
return 0;
}

[V.I.Smirnov]

Φανερά, τo λιγότερο και ευκολότερο house keepping το έχει ο

2D πίνακας με γραμμές μεταβλητού μήκους που έδειξα στο post #11.

Το μήκος κάθε γραμμής δίνεται στο διάνυσμα size_rows[].

To μόνον που απαιτείται ακόμη είναι η ρουτίνα για διαγραφή του πίνακα

(και φυσικά το Τipus να αντικατασταθεί από την δομή του χρήστη διώχνοντας το template) .

 

-

[migf1]

Φανερά, τo λιγότερο και ευκολότερο house keepping το έχει ο

2D πίνακας με γραμμές μεταβλητού μήκους που έδειξα στο post #11....

Ναι!

[bokarinho]

Αυτό που θέλει είναι μια δομή "Α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 και

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

 

-

 

VI, aπό πότε calloc και free αποτελούν C++; Εγώ βλέπω μία μίξη C με C++. Φιλικά και χωρίς καμία δόση εμπαιγμού.

[V.I.Smirnov]

Σωστά βλέπεις.

 

Χρησιμοποιώ στοιχεία από αμφότερες τις C/C++, ανάμικτα, αναλόγως όπως με βολεύει.

Αυστηρά μιλώντας δεν είναι σωστή πρακτική.

Ωστόσο, για τα περισσότερα πράγματα δεν υπάρχει λόγος να περιορίζομαι τυπολατρικά στον

φορμαλισμό της μιας ή της άλλης, αυτό που με ενδιαφέρει είναι να είναι σαφής και κομψός ο κώδικας.

Εδώ η χρήση της C++ αναφέρεται στο template για τον τύπο.

 

-

[bokarinho]

Σωστά βλέπεις.

 

Χρησιμοποιώ στοιχεία από αμφότερες τις C/C++, ανάμικτα, αναλόγως όπως με βολεύει.

Αυστηρά μιλώντας δεν είναι σωστή πρακτική.

Ωστόσο, για τα περισσότερα πράγματα δεν υπάρχει λόγος να περιορίζομαι τυπολατρικά στον

φορμαλισμό της μιας ή της άλλης, αυτό που με ενδιαφέρει είναι να είναι σαφής και κομψός ο κώδικας.

Εδώ η χρήση της C++ αναφέρεται στο template για τον τύπο.

 

-

 

Πιστεύω ότι γνωρίζεις τις συνέπειες αυτού; Εννοώ να δουλεύεις με αντικείμενα και να εφαρμόζεις τέτοιες πολιτικές;

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

Καλή συνέχεια.

 

*Αν και αμφιβάλλω για την ορθότητα της μεθόδου σου, ειδικά κάνοντας template για κάτι, κάνοντας μετά free, νομίζω πως θα έχεις περίεργα αποτελέσματα. Βέβαια αυτό είναι άλλο κεφάλαιο.

[nilosgr]

Εγω στο ποστ #3 εχω κατι λαθος...;

[bokarinho]

Εγω στο ποστ #3 εχω κατι λαθος...;

Στα γρήγορα όπως το είδα κάνε το new -> nodeNew, καθώς το new είναι reserved word για γλώσσα προγραμματισμού.

Κατά τα άλλα δεν έχω διαβάσει όλο το thread, αν θέλεις να γράψεις σε C oder C++.

Γενικά αν γράφεις στην C++, γράφε σε κλάσεις, οι δομές είναι για την C, όχι ότι δεν μπορείς να τις χρησιμοποιήσεις, αλλά έχουμε κλάσεις για την C++.

[V.I.Smirnov]

Eπί προσωπικού, τις ξέρω τις διαφορές (διαδικαστική vs αντικειμενοστρεφής προσέγγιση).

Η τάση μου είναι να γράφω διαδικαστικά - εξάλλου σε μικρά προγράμματα και σε θέματα

αριθμητικής ανάλυσης που έχω τις καταβολές μου η αντικειμενοστρέφεια γενικά δεν προσφέρει

σχεδόν τίποτε. Εξάλλου εδώ πρόκειται μόνον για βασικούς τύπους, όχι αντικείμενα.

 

Στην συγκεκριμένη περίπτωση, ο t.s. γράφει σε C και αναφέρω ότι πρέπει να αφαιρεθεί το

template oπότε ο κώδικας γίνεται αυτούσια C. Δεν υπάρχει περίπτωση να μπερδευτεί.

Αντίθετα, αν χρησιμοποιούσα new/delete, η αφαίρεση του template δεν θα έκανε C τον κώδικα

(αφού τα new/delete αποτελούν ματζούνια της C++) και θα είχες λόγο να διαμαρτύρεσαι...

 

-

[bokarinho]

Eπί προσωπικού, τις ξέρω τις διαφορές (διαδικαστική vs αντικειμενοστρεφής προσέγγιση).

Η τάση μου είναι να γράφω διαδικαστικά - εξάλλου σε μικρά προγράμματα και σε θέματα

αριθμητικής ανάλυσης που έχω τις καταβολές μου η αντικειμενοστρέφεια γενικά δεν προσφέρει

σχεδόν τίποτε. Εξάλλου εδώ πρόκειται μόνον για βασικούς τύπους, όχι αντικείμενα.

 

Στην συγκεκριμένη περίπτωση, ο t.s. γράφει σε C και αναφέρω ότι πρέπει να αφαιρεθεί το

template oπότε ο κώδικας γίνεται αυτούσια C. Δεν υπάρχει περίπτωση να μπερδευτεί.

Αντίθετα, αν χρησιμοποιούσα new/delete, η αφαίρεση του template δεν θα έκανε C τον κώδικα

(αφού τα new/delete αποτελούν ματζούνια της C++) και θα είχες λόγο να διαμαρτύρεσαι...

 

-

 

Τότε μην δίνεις καθόλου κώδικα λοιπόν, δίνεις ένα κώδικα με template και λες να βγάλει το template, αν έχω

καταλάβει σωστά. Αν όχι διόρθωσε με. Δηλαδή τι ακριβώς κάνεις με αυτό; Ο άλλος πχ μπορεί να μην καταλαβαίνει

τι είναι αυτό που βγάζει, πως να το αλλάξει κτλ. Γνώμη μου είναι ή δίνεις κάτι που να είναι αυτό που θέλει

το ζήτημα, ή μην δίνεις καθόλου. Δεν διαφωνώ πως κάποιος που γνωρίζει δεν θα καταφέρει αν θέλει να πάρει

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

Δεν διαμαρτύρομαι, δεν θίγομαι, για να το κάνω αυτό, την γνώμη μου είπα.

[V.I.Smirnov]

Κοντολογής, "καλεσέ τον στο γάμο σου να σου πει και του χρόνου" !!

 

1) αναφέρω καθαρά στο post #11 ότι πρόκειται για απόσπασμα από δικό μου πρόγραμμα και

ΟΧΙ τελεσίδικη απάντηση στον t.s. Eίναι απλώς ένα παράδειγμα για τον συγκεκριμένο τρόπο

στα πλαίσια της συζήτησης, όχι άμεση λύση.

Γι' αυτό δεν δίνω τη ρουτίνα διαγραφής ή δεν αντικατέστησα το template εγώ.

 

2) ακόμα κι' αν κάποιος δεν ξέρει τι είναι το template, το απόσπασμα είναι self-explained και

σχεδόν αυτονόητο για το πώς πρέπει να τροποποιηθεί σε C - και πανεύκολο αν θελήσει να το κάνει έτσι.

Εν προκειμένω λοιπόν τα σχόλια "μπορεί να μην καταλαβαίνει τι είναι αυτό που βγάζει,

πως να το αλλάξει κλπ" απλώς υποτιμούν το IQ αυτού που θα το διαβάσει.

Εξάλλου μπορεί να ρωτήσει περαιτέρω.

 

3) ο κώδικας του migf1 είναι επίσης ημιτελής, πολύ εκτενέστερος, και σαφώς πιο δύσκολο να

τον παρακολουθήσει κάποιος. Λοιπόν "ο άλλος πχ μπορεί να μην καταλαβαίνει

τι είναι αυτό που βγάζει, πως να το αλλάξει κτλ".

Eπομένως θα πρέπει να κάνεις τις ίδιες υποδείξεις και στον migf1...

 

 

Για μένα το θέμα έκλεισε.

 

-

[bokarinho]

Κοντολογής, "καλεσέ τον στο γάμο σου να σου πει και του χρόνου" !!

 

1) αναφέρω καθαρά στο post #11 ότι πρόκειται για απόσπασμα από δικό μου πρόγραμμα και

ΟΧΙ τελεσίδικη απάντηση στον t.s. Eίναι απλώς ένα παράδειγμα για τον συγκεκριμένο τρόπο

στα πλαίσια της συζήτησης, όχι άμεση λύση.

Γι' αυτό δεν δίνω τη ρουτίνα διαγραφής ή δεν αντικατέστησα το template εγώ.

 

2) ακόμα κι' αν κάποιος δεν ξέρει τι είναι το template, το απόσπασμα είναι self-explained και

σχεδόν αυτονόητο για το πώς πρέπει να τροποποιηθεί σε C - και πανεύκολο αν θελήσει να το κάνει έτσι.

Εν προκειμένω λοιπόν τα σχόλια "μπορεί να μην καταλαβαίνει τι είναι αυτό που βγάζει,

πως να το αλλάξει κλπ" απλώς υποτιμούν το IQ αυτού που θα το διαβάσει.

Εξάλλου μπορεί να ρωτήσει περαιτέρω.

 

3) ο κώδικας του migf1 είναι επίσης ημιτελής, πολύ εκτενέστερος, και σαφώς πιο δύσκολο να

τον παρακολουθήσει κάποιος. Λοιπόν "ο άλλος πχ μπορεί να μην καταλαβαίνει

τι είναι αυτό που βγάζει, πως να το αλλάξει κτλ".

Eπομένως θα πρέπει να κάνεις τις ίδιες υποδείξεις και στον migf1...

 

 

Για μένα το θέμα έκλεισε.

 

-

 

 

Κοντολογής, "καλεσέ τον στο γάμο σου να σου πει και του χρόνου" !!

 

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

μαζί σου δημόσια τελειώνει εδώ.

 

Για μένα, αφήνω τα λεγόμενα σου, να σε εκθέτουν.

[Star_Light]

Eιρηνη υμίν κύριοι.

 

παρτε το χαλαρα και τελειωσε.

Μην ζοριζεστε και πολυ ;p

 

Αλλωστε ειναι και στην κριτικη του καθενος να ελεγχει αυτο που του δινει ο αλλος.

Ειτε ειναι ειτε δεν ειναι λάθος.

[nilosgr]

Στα γρήγορα όπως το είδα κάνε το new -> nodeNew, καθώς το new είναι reserved word για γλώσσα προγραμματισμού.

Το new δεν ειναι reserved στη C...

 

Οποτε μην μαλλωνετε αν ο Ι.V. ή ο migf1 εδςσε καλυτερη λυση!! χαχα (like a boss )