ΑΠΛΑ ΣΥΝΔΕΔΕΜΕΝΕΣ ΛΙΣΤΕΣ (Singly Linked Lists) - ΜΕΡΟΣ 5ο
Αναβαθμισμένη Δομή Λίστας (ενσωμάτωση δεικτών Κεφαλής & Ουράς και ενσωμάτωση Μήκους)
Επίσης: Οι διαχωριστικοί χαρακτήρες της τελείας: . και του βέλους: ->
Μέχρι στιγμής έχουμε καλύψει πολλές από τις βασικές αρχές που διέπουν τις απλά συνδεδεμένες λίστες και μάλιστα είμαστε σε θέση να τις χρησιμοποιήσουμε για την υλοποίηση κι άλλων πολύ συνηθισμένων δομών, όπως είναι η στοίβα (stack) και η ουρά (queue).
Η ανάλυση των στοιβών και των ουρών δεν περιλαμβάνεται στους στόχους αυτής της σειράς των tutorials. Περιληπτικά όμως, οι στοίβες είναι δομές όπου όλοι οι κόμβοι προστίθενται και αφαιρούνται από την αρχή της λίστας (π.χ. φανταστείτε έναν πάκο από τραπουλόχαρτα στα οποία μπορείτε να τραβάτε ή να βάζετε χαρτιά μονάχα στην κορυφή του).
Ουρές είναι δομές όπου οι κόμβοι προστίθενται μονάχα στην αρχή και αφαιρούνται μονάχα από το τέλος (π.χ. φανταστείτε μια ουρά από κόσμο μπροστά από το ταμείο μιας τράπεζας... γεμίζει μόνο από πίσω και αδειάζει μόνο από μπροστά).
Η πιο συνηθισμένη υλοποίηση των στοιβών και ουρών είναι με απλά συνδεδεμένες λίστες (θα βρείτε και με πίνακες) και πάντα συνοδεύονται από μια σειρά συγκεκριμένων πράξεων (operations) που δεν είναι τίποτα άλλο από συναρτήσεις που πρέπει να υλοποιηθούν για τις λειτουργίες των δομών.
Για παράδειγμα, για τις στοίβες πρέπει να γραφτούν κατ' ελάχιστο συναρτήσεις για τις πράξεις: empty(), push(), pop() και peek(). Η empty() εξετάζει αν η στοίβα είναι κενή, η push() προσθέτει ένα νέο στοιχείο στη κορυφή, η pop() εξετάζει κι αφαιρεί όποιο στοιχείο βρίσκεται στην κορυφή και η peek() εξετάζει το στοιχείο της κορυφής χωρίς να το αφαιρεί (μπορεί να την συναντήσετε και ως: top() )
Το πρόγραμμα της Ξερής που έφτιαξα και πόσταρα σε προηγούμενο ποστ χρησιμοποιεί κατά κόρον στοίβες (ο κώδικας των πράξεων είναι στα αρχεία: stack.c και stack.h).
Οι ουρές (queues) μεταξύ άλλων πράξεων περιλαμβάνουν τις enqueue() και dequeue(). Η πρώτη προσθέτει κόμβους στο τέλος της ουράς και η δεύτερη αφαιρεί κόμβους από την αρχή της. Άρα η υλοποίησή της βασίζεται στην ύπαρξη δύο δεικτών, έναν στην αρχή κι έναν στο τέλος της ουράς (που σε όρους απλά συνδεδεμένης λίστας είναι ο head και ο tail που είδαμε στο 4ο μέρος... μόνο που ο head αντιστοιχεί στο πίσω μέρος της ουράς και ο tail στο εμπρός μέρος της ουράς
)Η παραπάνω εισαγωγή (πέρα από την ενημερωτική της πλευρά) δείχνει πως υπάρχουν περιπτώσεις όπου η διατήρηση δεικτών στην αρχή και στο τέλος των λιστών παίζουν πολύ συχνά σημαντικό ρόλο, και άρα το να τους έχουμε ως ξεχωριστές μεταβλητές χύμα στην main() δεν είναι από τις καλύτερες επιλογές. Ειδικά σε προγράμματα που χρησιμοποιούν πολλές λίστες, μπορεί να οδηγήσει εύκολα σε... χαώδη κώδικα με ένα κάρο χύμα μεταβλητές.
Η λύση είναι για κάθε τύπο λίστας να φτιάξουμε μια ξεχωριστή δομή, η οποία θα περιέχει μέσα της τόσο τη λίστα όσο και μεταβλητές που μας βοηθάνε να τη διαχειριστούμε σε επίπεδο υψηλότερο από την εσωτερική δομή του κάθε κόμβου της λίστας.
Στο δικό μας παράδειγμα που έχουμε αναπτύξει μέχρι στιγμής στα προηγούμενα μέρη του tutorial, τέτοιες μεταβλητές υψηλότερου επιπέδου είναι οι δείκτες head και tail. Μπορούμε μάλιστα να προσθέσουμε μια ακόμα, την len (ή size) η οποία θα αντιστοιχεί στο συνολικό πλήθος των στοιχείων της λίστας ανά πάσα στιγμή, και θα την ενημερώνουμε κάθε φορά που προσθέτουμε ή αφαιρούμε κάποιον κόμβο. Αυτό θα έχει σαν αποτέλεσμα να μη χρειαζόμαστε πλέον τη συνάρτηση: list_len() η οποία έτσι κι αλλιώς είναι δραματικά αργή!
Η δομή που περιγράφει τον κάθε κόμβο παραμένει ίδια με πριν...
- Κώδικας: Επιλογή όλων
typedef struct node {
int value;
struct node *next;
} Node;
Τώρα όμως θα προσθέσουμε μια ακόμα που θα περιέχει τους δείκτες head και tail, καθώς επίσης και έναν int για το συνολικό πλήθος των στοιχείων της λίστας...
- Κώδικας: Επιλογή όλων
typedef struct list {
Node *head, *tail;
int len;
} List;
Οπότε τώρα χρειάζεται να τροποποιήσουμε και τον κώδικα, τόσο στη main() όσο και στις συναρτήσεις.
Σε ότι αφορά τη main, η λίστα μας πλέον δεν θα είναι ένας δείκτης σε Node αλλά θα είναι μια απλή μεταβλητή τύπου struct list (ή λόγω του typedef, τύπου List)...
- Κώδικας: Επιλογή όλων
...
int main( void )
{
List list;
...
return EXIT_SUCCESS;
}
η οποία αποτελείται από 3 πεδία: List.head, List.tail, List.len (παρατηρήστε πως εφόσον η μεταβλητή list ΔΕΝ είναι δείκτης, τα πεδία της περιγράφονται με τελείες και όχι με το σύμβολο -> )
Μπορούμε μάλιστα (και ενδείκνυται κιόλας) να τα αρχικοποιήσουμε με default τιμές κατά τον νέο ορισμό της λίστας...
- Κώδικας: Επιλογή όλων
...
int main( void )
{
List list = { .head=NULL, .tail=NULL, .len=0 }; // στάνταρ τρόπος αρχικοποίησης πεδίων στα struct, στην ANSI C
...
return EXIT_SUCCESS;
}
Κατόπιν πρέπει να προσαρμόσουμε αντίστοιχα τον κώδικα των συναρτήσεων, όπου πλέον αρκεί να τους περνάμε ως όρισμα το list (είτε by value, είτε by reference) αντί για τα 2 ξεχωριστά ορίσματα που περνάγαμε μέχρι τώρα, για τους δείκτες head και tail.
Ας δούμε πρώτα τις: list_print() και list_destroy() που είναι συντακτικά πιο βατές και μετά θα δούμε και τον κώδικα των list_prepend() και list_append()...
- Κώδικας: Επιλογή όλων
// ------------------------------------------------------------------
void list_print( List list )
{
while ( list.head ) {
printf("%d ", list.head->value);
list.head = list.head->next;
}
putchar('\n'); // αλλαγή γραμμής
return;
}
// ------------------------------------------------------------------
void list_destroy( List *list )
{
if ( list->head == NULL )
return;
Node *dummy = NULL;
while ( list->head ) {
dummy = list->head->next;
free( list->head );
list->head = dummy;
}
return;
}
Η πρώτη παρατήρηση είναι πως στην list_print() την λίστα την περνάμε by value, ενώ στην list_destroy() την περνάμε by reference. Δεν χρειάζεται να περαστεί by reference στην list_destroy() (άλλωστε άμα δείτε στα προηγούμενα μέρη, by value την περνάμε στην list_destroy) απλά το έκανα έτσι τώρα για να γίνει εμφανής η διαφορά μεταξύ του συμβολισμού -> και της απλής τελείας, όταν περιγράφουμε τα πεδία μιας μεταβλητής που είναι τύπου struct.
Στο σώμα της list_print() η list είναι απλή μεταβλητή τύπου struct list (ή ισοδύναμα, τύπου List) με το struct να περιέχει ως ένα από τα πεδία του τον δείκτη head (που δείχνει σε struct node ή, ισοδύναμα, σε σκέτο Node).
Άρα η list ΔΕΝ είναι δείκτης, αλλά ο list.head είναι δείκτης.
Όταν λοιπόν θέλουμε να αναφερθούμε στα πεδία value και next του struct node στο οποίο δείχνει ο δείκτης head, χρησιμοποιούμε τον συμβολισμό ->. Δηλαδή, head->value και head->next. Όταν όμως θέλουμε να αναφερθούμε στον head που είναι πεδίο του struct list της μεταβλητής list η οποία ΔΕΝ είναι δείκτης σε struct list, τότε χρησιμοποιούμε την κλασική τελεία: list.head
Άρα λοιπόν, για να αναφερθούμε π.χ. στο πεδίο value ξεκινώντας από την μεταβλητή list, γράφουμε: list.head->value (και ομοίως, list.head->next).
Εξετάζοντας τώρα τον κώδικα της list_destroy() όπου επίτηδες έχω περάσει την list by reference, ώστε μέσα στο σώμα της συνάρτησης να είναι δείκτης, βλέπουμε πως χρησιμοποιούμε τον συμβολισμό -> ΚΑΙ για να αναφερθούμε στον δείκτη head: list->head και άρα και για να αναφερθούμε στο πεδίο next του struct node στο οποίο δείχνει ο head: list->head->next;
Καταλαβαίνω πως είναι παραπάνω από πιθανό να έχει χαθεί λιγάκι η μπάλα
Είναι όμως κρίσιμης σημασίας να τα ξεκαθαρίσετε στο μυαλό σας πριν προχωρήσουμε παρακάτω!
Δεν ξέρω αν θα σας βοηθήσει, αλλά αν προέρχεστε από αντικειμενοστραφείς γλώσσες, φανταστείτε ΣΥΝΤΑKΤΙΚΑ (ΚΑΙ ΜΟΝΟ ΣΥΝΤΑΚΤΙΚΑ) τα struct ως κλάσεις και τα πεδία του struct ως μεθόδους. Οπότε αν η list είναι ένα αντικείμενο της κλάσης List και ο head μια μέθοδος αυτής της κλάσης, για να αναφερθείτε στην μέθοδο head του αντικειμένου list θα γράφατε: list.head
Αν υπήρχε κάποιος τρόπος ώστε το αντικείμενο list να ήταν δείκτης στην κλάση List, τότε αντί για τελεία θα καλούσατε την μέθοδο στο αντικείμενο-δείκτη list με ->... δηλαδή: list->head
ΕΠΑΝΑΛΑΜΒΑΝΩ το παραπάνω σκεφτείτε το ΣΥΝΤΑΚΤΙΚΑ ΚΑΙ ΜΟΝΟ ΣΥΝΤΑΚΤΙΚΑ! Μην προσπαθήσετε δηλαδή να αντιστοιχήσετε σε επίπεδο λογικής τα struct με κλάσεις, τα πεδία των structs σε μεθόδους και τις μεταβλητές τύπου struct σε αντικείμενα, γιατί θα μπερδευτείτε χειρότερα! Αν το παραπάνω σας μπερδεύει χειρότερα, ΞΕΧΑΣΤΕ ΤΟ ΤΕΛΕΙΩΣ και μείνετε μονάχα στις έννοιες της C και μόνο, προκειμένου να τα ξεκαθαρίσετε στο μυαλό σας.
Όπως και να έχει πάντως, βεβαιωθείτε πως έχετε κατανοήσει πλήρως τι είναι οι δείκτες, τι είναι τα struct, τι είναι τα πεδία των struct και τις μεταξύ τους σχέσεις και διαφορές, πριν προχωρήσουμε στον κώδικα των συναρτήσεων list_prepend() και list_append()... κι αργότερα στις: list_insert_ascending() και list_insert_descending().
Ο καλύτερος τρόπος είναι να γράφετε δικά σας μικρά παραδείγματα σε κώδικα, για ότι δεν έχετε καταλάβει πλήρως, μέχρι να το κατανοήσετε. Εννοείται πως σε οποιαδήποτε απορία εγώ είμαι πάντα ανοιχτός
Αν από την άλλη μεριά αισθάνεστε πως τα έχετε εμπεδώσει (συμπεριλαμβανομένου και αυτού του 5ου μέρους), τότε είστε έτοιμοι να υλοποιήσετε μόνοι σας και ουρές (queues) και πολύ περισσότερο στοίβες (stacks)... ή τουλάχιστον να παρακολουθήσετε με άνεση σχετικά άρθρα και παραδείγματα όπως στα παραπάνω links.
Εμείς στη συνέχεια των tutorials θα δούμε τον τροποποιημένο κώδικα για τις: list_prepend() και list_append() και κατόπιν θα δούμε και τις συναρτήσεις: list_insert_descend() και list_insert_ascend() που θα εισαγάγουν κόμβους απευθείας ταξινομημένους, σε φθίνουσα και σε αύξουσα σειρά αντίστοιχα.
