Ubuntu-gr Forum

ΑΠΛΑ ΣΥΝΔΕΔΕΜΕΝΕΣ ΛΙΣΤΕΣ (Singly Linked Lists) - ΜΕΡΟΣ 3ο

Προσθήκη Νέων Κόμβων στην Αρχή της Λίστας
ΣΥΝΑΡΤΗΣΗ: list_prepend

έγραψε:Μετάβαση στον Πίνακα Περιεχομένων

Στο 3ο και 4ο μέρος θα προσπαθήσω να εξηγήσω μερικές υλοποιήσεις συναρτήσεων για εισαγωγή νέων κόμβων στη λίστα μας. Υπάρχουν διάφοροι τρόποι και μάλιστα διάφορες υλοποιήσεις για κάθε τρόπο. Τα πράγματα μπορούν να γίνουν εξαιρετικά σύνθετα, ανάλογα την υλοποίηση και ανάλογα τις ανάγκες του εκάστοτε project.

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

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

Ας ονομάσουμε αυτή τη συνάρτηση: list_prepend( Node *list, int value ) και ας δούμε καταρχήν κώδικα που ΔΕΝ δουλεύει, λόγω του περάσματος της λίστας by value μέσα στη συνάρτηση. Αλγοριθμικά όμως θα είναι σωστή, οπότε αμέσως μετά απλά θα αλλάξουμε το πέρασμα του ορίσματος από by value σε by reference και θα δουλεύει. Θα δούμε κατόπιν και ένα συνηθισμένο "κολπάκι" με το οποίο μπορούμε να περνάμε by value τη λίστα και να δουλεύει η εισαγωγή.

Ξεκινάμε με τον κώδικα που ΔΕΝ δουλεύει...

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


/*
* Εισαγωγή νέου κόμβου στην αρχή της λίστας BY VALUE
* !!! ΔΕΝ ΔΟΥΛΕΥΕΙ !!!
*/

// -------------------------------------------------------
void list_prepend( Node *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return;

new->value = value;
new->next = list;
list = new;

return;
}

// -------------------------------------------------------
int main( void )
{
Node *list = NULL;
...
list_prepend( list, 52 );
...
return 0;
}


Καταρχήν η αλγοριθμική σκέψη είναι η σωστή:

1. δημιουργούμε πρώτα χώρο στη μνήμη για ένα νέο κόμβο, στον οποίον βάζουμε να δείχνει ο τοπικός δείκτης new: new = calloc(1, sizeof(Node) );
2. σε περίπτωση που η δέσμευση μνήμης αποτύχει, τερματίζουμε την συνάρτηση χωρίς να κάνουμε τίποτα
3. εκχωρούμε την τιμή του ορίσματος value στο αντίστοιχο πεδίο του νέου κόμβου
4. για να κάνουμε τον νέο κόμβο αρχή της λίστας, βάζουμε το πεδίο next του νέου κόμβου να δείχνει όπου δείχνει ο δείκτης list (που είναι βασικά η προηγούμενη αρχή της λίστας)
5. και τέλος ενημερώνουμε τον δείκτη list να δείχνει στον νέο κόμβο, και τερματίζουμε την συνάρτηση

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

Όπως εξηγήσαμε στο 2ο μέρος, στη C όλα τα ορίσματα συναρτήσεων περνιούνται στις συναρτήσεις by value, δηλαδή ως προσωρινά αντίγραφα των αυθεντικών μεταβλητών. Για να μπορέσει ένα όρισμα να διατηρήσει τυχόν αλλαγές που του κάνει η συνάρτηση, θα πρέπει να περαστεί by reference. Αυτό γίνεται περνώντας στη συνάρτηση τη διεύθυνση μνήμης της αυθεντικής μεταβλητής και κατόπιν μέσα στον κώδικα της συνάρτησης δηλώνοντας και χρησιμοποιώντας τον εν λόγω όρισμα ως δείκτη.

Για να το καταλάβουμε καλύτερα, ας δούμε ένα απλό παράδειγμα με μια αυθεντική μεταβλητή τύπου int...

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


/*
* ΠΑΡΑΔΕΙΓΜΑ PASS BY VALUE
*/

void test( int x )
{
x = 10;
return;
}

int main( void )
{
int x = 0;
test( x );
printf("%d", x);

return 0;
}


Στον παραπάνω κώδικα το printf θα τυπώσει 0 (και όχι 10) διότι η αλλαγή του x από 0 σε 10 μέσα στη συνάρτηση έγινε σε ένα προσωρινό αντίγραφο του x, και όχι στο αυθεντικό x της main()... pass by value.

Για να διατηρηθεί στο x η αλλαγή που του κάνει η συνάρτηση test θα πρέπει να της περάσουμε το χ by reference, δηλαδή ως δείκτη στη διεύθυνση μνήμης του αυθεντικού x. Δείτε τον τροποποιημένο κώδικα...

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


/*
* ΠΑΡΑΔΕΙΓΜΑ PASS BY REFERENCE
*/

void test( int *x )
{
*x = 10;
return;
}

int main( void )
{
int x = 0;
test( &x );
printf("%d", x);

return 0;
}


Παρατηρήστε πως αφενός στην main() περνάμε στην test() τη διεύθυνση μνήμης του αυθεντικού x, και πως αφετέρου στον κώδικα της συνάρτησης test() το x δηλώνεται και διαχειρίζεται ως δείκτης (ο παραπάνω κώδικας θα τυπώσει τον αριθμό 10 στην οθόνη).

Άρα λοιπόν, για να επιστρέψουμε στον προβληματικό κώδικα της συνάρτησης: list_prepend( list, 52) το μόνο που χρειάζεται να κάνουμε για να δουλεύει σωστά, είναι το όρισμα list να το περάσουμε by reference (αντί για by value που είναι τώρα).

Επειδή είναι όμως ήδη δείκτης σε τύπο Node ( Node *list ), πρέπει να το περάσουμε ως δείκτη σε δείκτη τύπου Node... δηλαδή: Node **list. Κατόπιν, μέσα στον κώδικα της συνάρτησης θα πρέπει να τον διαχειριστούμε ως τέτοιον, άρα όπου τον γράφουμε τώρα ως list θα τον γράφουμε ως: *list ή ως (*list) για πιο σίγουρα. Και τέλος, όταν καλούμε στην main() τη συνάρτηση list_prepend() θα της περνάμε ως 1ο όρισμα τη διεύθυνση μνήμης του list, δηλαδή: list_prepend( &list, 52 ).

Ορίστε ο τροποποιημένος κώδικας που δουλεύει...

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


/*
* Εισαγωγή νέου κόμβου στην αρχή της λίστας BY REFERENCE
* !!! ΔΟΥΛΕΥΕΙ ΑΛΛΑ ΔΕΝ ΕΧΟΥΜΕ ΕΝΔΕΙΞΗ ΕΠΙΤΥΧΙΑΣ ή ΑΠΟΤΥΧΙΑΣ !!!
*/

// -------------------------------------------------------
void list_prepend( Node **list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return;

new->value = value;
new->next = (*list);
(*list) = new;

return;
}

// -------------------------------------------------------
int main( void )
{
Node *list = NULL;
...
list_prepend( &list, 52 );
...
return 0;
}


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

Αντί λοιπόν να την έχουμε void, που δεν επιστρέφει τίποτα, θα την κάνουμε να επιστρέφει έναν int που θα είναι 0 σε περίπτωση σφάλματος και 1 αν όλα εξελίχθηκαν ωραία και καλά. Και για να είναι ξεκάθαρο πως αυτό που επιστρέφει δεν είναι απλά ένας τυχαίος int αλλά μια boolean τιμή FALSE ή TRUE, θα ορίσουμε με typedef έναν πρόσθετο τύπο, που θα τον ονομάσουμε Bool και θα ορίσουμε ως πιθανές τιμές του πρόσθετου τύπου Bool, τις τιμές FALSE και TRUE, που θα αντιστοιχούν στις τιμές 0 και 1, αντίστοιχα.

Ένας λίγο ασυνήθιστος αλλά ενδεδειγμένος τρόπος να κάνουμε κάτι τέτοιο στη C είναι συνδυάζοντας τις εντολές typedef και enum (enumerated types) ως εξής:

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


typedef enum { FALSE=0, TRUE } Bool; // το TRUE ισούται με 1 επειδή έπεται αμέσως μετά το FALSE που το ορίσαμε να ισούται με 0


Οπότε, ο τροποποιημένος κώδικας του προηγούμενου παραδείγματος είναι ο εξής...

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


typedef enum { FALSE=0, TRUE } Bool;

/*
* Εισαγωγή νέου κόμβου στην αρχή της λίστας BY REFERENCE
* !!! ΔΟΥΛΕΥΕΙ ΚΑΝΟΝΙΚΑ ΚΑΙ ΕΠΙΣΤΡΕΦΕΙ TRUE ή FALSE !!!
*/

// -------------------------------------------------------
Bool list_prepend( Node **list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;

new->value = value;
new->next = (*list);
(*list) = new;

return TRUE;
}

// -------------------------------------------------------
int main( void )
{
Node *list = NULL;
...
if ( list_prepend( &list, 52 ) == FALSE ) {
// εδώ γράφουμε κώδικα που διαχειρίζεται την αποτυχία εισαγωγής
// συνήθως τυπώνουμε μήνυμα σφάλματος, αποδεσμεύουμε τυχόν προηγούμενα
// δεσμευμένους κόμβους της λίστας (π.χ. με: list_destroy( list ) και
// τερματίζουμε βίαια το πρόγραμμα (π.χ. με: exit(EXIT_FAILURE); ή return EXIT_FAILURE; )
}
...
return EXIT_SUCCESS;
}


Ρισκάροντας να σας μπερδέψω λιγάκι τώρα που τα ξεκαθαρίσαμε, αλλά επειδή σας το "υποσχέθηκα", θα σας δείξω μια δεύτερη υλοποίηση της συνάρτησης: list_prepend() κατά την οποία περνάμε την λίστα by value και κατόπιν την αναγκάζουμε να μας επιστρέφει την ανανεωμένη λίστα πριν τερματίσει.

Ο κώδικας είναι σχεδόν ίδιος με την πρώτη-πρώτη υλοποίηση αυτού του post (αυτή που έχω χαρακτηρίσει πως δεν δουλεύει) με τη διαφορά πως αυτή τη φορά θα βάλουμε τη συνάρτηση να επιστρέφει την ανανεωμένη λίστα, άρα ο τύπος επιστροφής της θα αλλάξει από void σε Node *. Για να πάρουμε την ανανεωμένη λίστα στην main() θα πρέπει να εκχωρήσουμε την τιμή επιστροφής της list_prepend() στον αυθεντικό δείκτη list.

Ο κώδικας πιστεύω αποσαφηνίζει καλύτερα την παραπάνω περιγραφή:

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


/*
* Εισαγωγή νέου κόμβου στην αρχή της λίστας BY VALUE
* !!! ΔΟΥΛΕΥΕΙ ΑΝ ΕΚΜΕΤΑΛΛΕΥΤΟΥΜΕ ΤΗΝ ΤΙΜΗ ΕΠΙΣΤΡΟΦΗΣ ΤΗΣ ΣΥΝΑΡΤΗΣΗΣ!!!
* !!! ΕΠΙΣΤΡΕΦΕΙ NULL ΣΕ ΠΕΡΙΠΤΩΣΗ ΑΠΟΤΥΧΙΑΣ
*/

// -------------------------------------------------------
Node *list_prepend( Node *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return NULL;

new->value = value;
new->next = list;
list = new;

return list; // μπορούμε κι απευθείας: return new; ενοποιώντας τις 2 τελευταίες γραμμές σε 1
}

// -------------------------------------------------------
int main( void )
{
Node *list = NULL;
...
list = list_prepend( list, 52 );
if ( !list ) { // ισοδυναμεί με: if ( list == NULL ) {
// εδώ γράφουμε κώδικα που διαχειρίζεται την αποτυχία εισαγωγής
// συνήθως τυπώνουμε μήνυμα σφάλματος, αποδεσμεύουμε τυχόν προηγούμενα
// δεσμευμένους κόμβους της λίστας (π.χ. με: list_destroy( list ) και
// τερματίζουμε βίαια το πρόγραμμα (π.χ. με: exit(EXIT_FAILURE); ή return EXIT_FAILURE; )
}
...
return EXIT_SUCCESS;
}


Το "κλειδί" στον παραπάνω κώδικα είναι στην main() στη γραμμή:

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

list = list_prepend( list, 52 );

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

Και φυσικά η παραπάνω εκχώρηση έχει νόημα επειδή αλλάξαμε ελαφρώς τον κώδικα της list_prepend() ώστε αντί για void να επιστρέφει το αλλαγμένο αντίγραφο του list

Προσωπικά προτιμώ την BY REFERENCE εκδοχή της list_prepend() επειδή την θεωρώ πιο "straight forward" και πιο συνεπή ως προς τη στάνταρ χρήση όλων των συναρτήσεων που χρησιμοποιούν ορίσματα by reference. Συνδυασμένη μάλιστα με τιμή επιστροφής FALSE ή TRUE νομίζω είναι και πιο κατανοητή σε όσους προέρχονται από άλλες γλώσσες (με κόστος όμως τον ελαφρώς δυσκολότερο κώδικα λόγω του διπλού δείκτη).

Όμως και η BY VALUE εκδοχή της με επιστροφή του ανανεωμένου αντίγραφου της λίστας είναι πολύ συνηθισμένη υλοποίηση και χρησιμοποιείται κατά κόρον. Εγώ θα συνεχίσω να χρησιμοποιώ τις BY REFERENCE εκδοχές των συναρτήσεων στη συνέχεια αυτού του tutorial, αλλά εννοείται πως κανείς δεν σας εμποδίζει να χρησιμοποιήσετε την BY VALUE αν την καταλαβαίνετε πιο καλά.

Οπότε ο ολοκληρωμένος κώδικας στο τέλος του 2ου μέρους, μπορεί πλέον να γραφτεί ως εξής (με την BY REFERENCE εκδοχή της list_prepend() )...

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


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

typedef enum { FALSE=0, TRUE } Bool; // ο δικός μας πρόσθετος τύπος Boolean

typedef struct node { // δομή του κάθε κόμβου της λίστας
int value;
struct node *next;
} Node;

/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην αρχή της λίστας.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_prepend( Node **list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;

new->value = value;
new->next = (*list);
(*list) = new;

return TRUE;
}

/* ------------------------------------------------------------------
* Μέτρημα κι επιστροφή του πλήθους κόμβων της λίστας
* ------------------------------------------------------------------
*/
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;

// δημιουργία και εισαγωγή του 1ου στοιχείου
if ( list_prepend( &list, 52) == FALSE ) { // αποτυχία
puts("*** out of memory, aborting program");
exit( EXIT_FAILURE);
}

// δημιουργία και εισαγωγή του 2ου στοιχείου
if ( list_prepend( &list, 62) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit(1);
}

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

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

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

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


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

Προς το παρόν μπορείτε να δείτε τον τελικό κώδικα αυτού του ποστ με syntax-highlighting, δείγμα εξόδου και σύνδεσμο κατεβάσματος εδώ: http://codepad.org/cpRAjH5F