Ubuntu-gr Forum

migf1 έγραψε:Απλά Συνδεδεμένες Λίστες - Μέρος 2ο

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

Ας ξεκινήσουμε με 3 βατές:

1. void list_print( Node *list ) : που τυπώνει τα πεδία value όλων των κόμβων
2. int list_len( Node *list ) : που μετράει το πλήθος των κόμβων της λίστας
3. void list_destroy( Node *list ) : που απελευθερώνει όλους τους κόμβους της λίστας.

Θα ξεκινήσω με την list_print() που είναι η πιο βατή από όλες, και που ουσιαστικά απλά μετατρέπει σε συνάρτηση τον κώδικα του while-loop που έχουμε ήδη γράψει στο 1ο μέρος.

Ελπίζω όμως πως θα μας βοηθήσει επίσης να ξεκαθαρίσουμε στο μυαλό μας ένα ακόμα "ευαίσθητο" σημείο, που ισχύει για όλες τις συναρτήσεις στη C (ανεξαιρέτως) και που ονομάζεται πέρασμα ορισμάτων "by value" έναντι του περάσματος ορισμάτων "by reference" (όποιος γνωρίζει τις ακριβείς ορολογίες στα Ελληνικά, παρακαλώ ας τις συμπληρώσει).

Παραθέτω τον κώδικα της: list_print()...

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Τύπωμα του πεδίου value όλων των κόμβων της λίστας
* ------------------------------------------------------------------
*/
void list_print( Node *list )
{
while ( list ) {
printf("%d ", list->value);
list = list->next;
}
putchar('\n'); // αλλαγή γραμμής

return;
}


Συγκρίνοντάς τον με τον κώδικα του while-loop στην main() του 1ου μέρους, η 1η χτυπητή διαφορά είναι πως εκεί χρησιμοποιούσαμε έναν βοηθητικό δείκτη dummy προκειμένου να διατρέξουμε τη λίστα από τον πρώτο έως τον τελευταίο της κόμβο, γιατί τον list τον θέλαμε να παραμείνει στην αρχή της λίστας μας και μετά το τέλος του loop.

Αντίθετα τώρα, μέσα στη συνάρτηση print_list() διατρέχουμε τη λίστα απευθείας με τον δείκτη list, άρα φαινομενικά όταν τελειώσει το loop κι επιστρέψει ο έλεγχος στη main() ο δείκτης list δείχνει στο NULL, και άρα χάσαμε την επαφή μας με την αρχή της λίστας.

Σωστά;

Λάθος! Η διαφορά είναι πως στην main ο δείκτης list είναι ο αυθεντικός δείκτης που δείχνει στην αρχή της λίστας μας. Όταν όμως τον περάσουμε ως όρισμα σε μια συνάρτηση, τότε μέσα στη συνάρτηση ΔΕΝ περνάει ο αυθεντικός δείκτης, αλλά ένα αντίγραφό του (που το δημιουργεί εσωτερικά η γλώσσα). Αυτός είναι ο στάνταρ τρόπος περάσματος ορισμάτων μέσα σε συναρτήσεις στη C, και ονομάζεται pass by value, διότι περνάει μέσα στις συναρτήσεις τις ΤΙΜΕΣ μεταβλητών που αντιστοιχούν στα ορίσματα, και όχι τις διευθύνσεις των μεταβλητών.

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

Σημειώστε όμως πως όταν λέμε ότι διαγράφεται το αντίγραφο του δείκτη list ΔΕΝ σημαίνει πως καταστρέφεται ο κόμβος στον οποίον δείχνει (αυτός για να καταστραφεί πρέπει να γίνει free() ). Δηλαδή έχουμε έναν κόμβο χωρίς να δείχνει σε αυτόν κάποιος δείκτης.

Άρα λοιπόν ο list μέσα στην print_list() είναι ένα αντίγραφο του αυθεντικού list που έχουμε ορίσει στην main(). Οπότε όταν τελειώσει η συνάρτηση και η ροή επιστρέψει πίσω στην main() ο αυθεντικός δείκτης list έχει μείνει ανέπαφος, δείχνοντας δηλαδή στην αρχή της λίστας μας.

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

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

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Μέτρημα κι επιστροφή του πλήθους κόμβων της λίστας
* ------------------------------------------------------------------
*/
int list_len( Node *list )
{
register int i = 0;
for (i=0; list; i++) // ισοδυναμεί με: for (i=0; list != NULL; i++)
list = list->next;

/** ΕΝΑΛΛΑΚΤΙΚΟΣ ΚΩΔΙΚΑΣ
while ( list ) { // ισοδυναμεί με: while ( list != ΝULL ) {
list = list->next;
i++;
}
**/
return i;
}


για ποικιλία την υλοποίησα με for-loop αλλά αν σας μπερδεύει, έβαλα σε σχόλια ως εναλλακτικό τρόπο το κλασικό while-loop (προφανώς υπάρχουν κι άλλες υλοποιήσεις).

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

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Απελευθέρωση της μνήμης που έχουμε δεσμεύσει για κάθε κόμβο της λίστας
* ------------------------------------------------------------------
*/
void list_destroy( Node *list )
{
if ( !list ) // ισοδυναμεί με: if ( list == NULL )
return;

Node *dummy = NULL;
while ( list ) { // ισοδυναμεί με: while ( list != NULL ) {
dummy = list->next;
free( list );
list = dummy;
}

return;
}


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

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

Η λύση είναι πριν καταστρέψουμε τον κόμβο, να βάλουμε τον βοηθητικό δείκτη dummy να δείχνει εκεί που δείχνει το πεδίο next του υπό καταστροφή κόμβου. Μετά μπορούμε να καταστρέψουμε με free() τον κόμβο. Πριν επιστρέψει η ροή στη συνθήκη του loop (η οποία ελέγχει τον list) λέμε στον δείκτη list να δείχνει εκεί που δείχνει ο δείκτης dummy (δηλαδή στον επόμενο κόμβο από αυτόν που καταστρέψαμε).

Ελπίζω να είναι κατανοητή η εξήγηση που έδωσα. Αν όχι, ρωτήστε, να το ξανά εξηγήσω.

Οπότε, ας συνδυάσουμε τώρα τον κώδικα του 1ου μέρους με τις συναρτήσεις αυτού του 2ου μέρους...

Κώδικας: Επιλογή όλων


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

typedef struct node {
int value;
struct node *next;
} Node;

/* ------------------------------------------------------------------
* Μέτρημα κι επιστροφή του πλήθους κόμβων της λίστας
* ------------------------------------------------------------------
*/
int list_len( Node *list )
{
register int i = 0;
for (i=0; list; i++) // ισοδυναμεί με: for (i=0; list != NULL; i++)
list = list->next;

/** ΕΝΑΛΛΑΚΤΙΚΟΣ ΚΩΔΙΚΑΣ
while ( list ) { // ισοδυναμεί με: while ( list != ΝULL ) {
list = list->next;
i++;
}
**/
return i;
}

/* ------------------------------------------------------------------
* Τύπωμα του πεδίου value όλων των κόμβων της λίστας
* ------------------------------------------------------------------
*/
void list_print( Node *list )
{
while ( list ) {
printf("%d ", list->value);
list = list->next;
}
putchar('\n'); // αλλαγή γραμμής

return;
}

/* ------------------------------------------------------------------
* Απελευθέρωση της μνήμης που έχουμε δεσμεύσει για κάθε κόμβο της λίστας
* ------------------------------------------------------------------
*/
void list_destroy( Node *list )
{
if ( !list ) // ισοδυναμεί με: if ( list == NULL )
return;

Node *dummy = NULL;
while ( list ) { // ισοδυναμεί με: while ( list != NULL ) {
dummy = list->next;
free( list );
list = dummy;
}

return;
}

// -------------------------------------------------------------------
int main ( void )
{
Node *list = NULL, *newnode = NULL;

// δημιουργία και εισαγωγή του 1ου στοιχείου

list = calloc(1, sizeof(Node) );
if ( !list ) { // αποτυχία της calloc()
puts("*** out of memory, aborting program");
exit(1);
}
list->value = 52;
list->next = NULL;

// δημιουργία και εισαγωγή του 2ου στοιχείου

newnode = calloc(1, sizeof(Node) );
if ( !newnode ) { // αποτυχία της calloc()
puts("*** out of memory, aborting program");
free( list ); // αποδέσμευση μνήμης 1ου στοιχείου
exit(1);
}
newnode->value = 62;
newnode->next = NULL;
list->next = newnode;

// καταμέτρηση και τύπωμα του πλήθους των κόμβων στη λίστα
printf("The list consists of %d nodes\n", list_len( list) );

// τύπωμα των στοιχείων της λίστας
list_print( list );

// αποδέσμευση όλων των κόμβων από τη μνήμη
list_destroy( list );

fflush(stdin); getchar();
exit(0);
}


Μπορείτε να δείτε τον τελικό κώδικα του 2ου μέρους με syntax-highlighting, καθώς και την έξοδο που παράγει, εδώ: http://codepad.org/Br2OcD8g

Σε επόμενα posts θα προσπαθήσω να αναλύσω 2-3 διαφορετικούς τρόπους για εισαγωγή νέων στοιχείων στη λίστα, μέσω αντίστοιχων συναρτήσεων (με κώδικα προφανώς εκτός από σχόλια).