ΑΠΛΑ ΣΥΝΔΕΔΕΜΕΝΕΣ ΛΙΣΤΕΣ (Singly Linked Lists) - ΜΕΡΟΣ 6ο
Επανακωδικοποίηση Συναρτήσεων
ΣΥΝΑΡΤΗΣΕΙΣ: list_prepend, list_append, list_print, list_destroy (κατάργηση της: list_length)Στο
5ο μέρος, αναδιοργανώσαμε τον ορισμό της λίστας μας σε 2 struct. Ένα Node για τον κάθε κόμβο της, κι ένα List που περιέχει το τρέχον μήκος της λίστας (len) καθώς και 2 δείκτες που δείχνουν στον 1ο και στον τελευταίο κόμβο της, αντίστοιχα (head και tail).
Κάναμε με αυτό τον τρόπο πιο δομημένο το πρόγραμμά μας, συγκεντρώνοντας τις βασικές μεταβλητές διαχείρισης της λίστας μας ως πεδία μέσα μια μόνο μεταβλητή τύπου List, την:
list. Την μεταβλητή αυτή την περνάμε πια ως όρισμα στις διάφορες συναρτήσεις μας, είτε BY VALUE ( όπως στην: list_print() ) είτε BY REFERENCE ( όπως στην: list_destroy() ).
Είδαμε ήδη τις μετατροπές που χρειάστηκε να κάνουμε στον κώδικα των συναρτήσεων: list_print() και list_destroy() καθώς και στην main(). Οπότε είναι ώρα τώρα να τροποποιήσουμε κατάλληλα και τις συναρτήσεις: list_prepend() και list_append() που δημιουργούν και προσθέτουν νέους κόμβους στην αρχή και στο τέλος της λίστας, αντίστοιχα.
Η
list_prepend( List *list, int value ) που δημιουργεί και προσθέτει έναν νέο κόμβο στην αρχή της λίστας μας, γίνεται πλέον έτσι...
- Κώδικας: Επιλογή όλων
/* ------------------------------------------------------------------
* Insert value as FIRST node of list
*/
Bool list_prepend( List *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;
new->value = value;
if ( list->head == NULL ) {
new->next = NULL;
list->head = list->tail = new;
}
else {
new->next = list->head;
list->head = new;
}
(list->len)++;
return TRUE;
}
Καταρχήν η βασική λογική της συνάρτησης είναι ακριβώς ίδια με αυτήν που αναλύθηκε στο
3ο μέρος του tutorial (σημειώστε πως ο εκεί δείκτης: list αντιστοιχεί στον δείκτη: head στον παραπάνω κώδικα).
Δηλαδή...
- δημιουργούμε έναν νέο κόμβο στη μνήμη στον οποίον βάζουμε να δείχνει o δείκτης new
- εκχωρούμε την τιμή του ορίσματος: value στο αντίστοιχο πεδίο του νέου κόμβου
- βάζουμε το πεδίο: next του νέου κόμβου να δείχνει στην αρχή της λίστας μας (head), ώστε να γίνει ο νέος κόμβος η νέα αρχή της λίστας
- βάζουμε τον δείκτη της πρώην αρχής (head) να δείχνει στον νέο κόμβο, που είναι η νέα αρχή της λίστας.
Έχουμε όμως άλλα δυο πεδία στην αναδιοργανωμένη δομή της λίστας μας, τον δείκτη:
tail για να δείχνει στον τελευταίο κόμβο της λίστας και τον int
len για να "κρατάει" το τρέχον μήκος της λίστας μας (τρέχον πλήθος κόμβων).
Όπως μπορείτε να διαπιστώσετε και μόνοι σας στον παραπάνω κώδικα, με τη γραμμή:
- Κώδικας: Επιλογή όλων
list->head = list->tail = new;
βάζουμε τον δείκτη tail να δείχνει (μαζί με τον head) στον νέο κόμβο της λίστας
ΜΟΝΟ κατά την προσθήκη του 1ου κόμβου, όταν δηλαδή η λίστα είναι κενή πριν της προσθέσουμε τον νέο κόμβο. Άπαξ και γίνει η προσθήκη του 1ου κόμβου ο δείκτης tail δεν χρειάζεται να εξεταστεί ξανά (ούτε να αλλαχτεί) διότι όλοι οι μετέπειτα κόμβοι προστίθενται πριν από τον δείκτη tail
Όσο για τον
int len, αυτόν τον αυξάνουμε κατά 1 μετά από
κάθε επιτυχημένη προσθήκη νέου κόμβου στη λίστα, με τη γραμμή:
- Κώδικας: Επιλογή όλων
(list->len)++;
Μία ακόμα
υπενθύμιση πριν περάσουμε στον κώδικα της list_append() είναι πως ο
δείκτης list που περνάμε ως 1o όρισμα της συνάρτησης ΔΕΝ είναι πια δείκτης που δείχνει στον 1ο κόμβο της λίστας μας, αλλά είναι ο BY REFERENCE συμβολισμός του struct list (ή σκέτο List). Ο δείκτης που δείχνει στον 1ο κόμβο της λίστας μας βρίσκεται μέσα στην list (ως πεδίο της) και ονομάζεται head... δηλαδή ο list->head.
Την μεταβλητή list την περνάμε BY REFERENCE στην list_prepend() διότι θέλουμε να διατηρηθούν οι αλλαγές που κάνει η συνάρτηση στα πεδία: head, tail και len της list ( list->head, list->tail και list->len, αντίστοιχα).
Αν ούτε η παραπάνω υπενθύμιση σας βοηθάει να κατανοήσετε τον κώδικα της list_prepend(), τότε πριν συνεχίσετε, διαβάστε ξανά το 5ο μέρος του tutorial και βεβαιωθείτε πως έχετε καταλάβει την αναδιοργάνωση που έχουμε κάνει στη δομή της λίστας μας συγκριτικά με προηγούμενα μέρη του tutorial.Χωρίς περαιτέρω καθυστέρηση, παρουσιάζω και τον κώδικα της:
list_append( List *list, int value )...
- Κώδικας: Επιλογή όλων
/* ------------------------------------------------------------------
* Insert value as LAST node of list
*/
Bool list_append( List *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;
new->value= value;
new->next = NULL;
if ( list->head == NULL ) {
list->head = list->tail = new;
(list->len)++;
return TRUE;
}
list->tail->next = new;
list->tail = new;
(list->len)++;
return TRUE;
}
Πέραν της σύνταξης (που είναι προσαρμοσμένη στην αναδιοργανωμένη δομή της λίστας μας) η βασική λογική του κώδικα είναι ίδια με αυτή που αναλύσαμε στον
δεύτερο μισό του
4ου μέρους αυτού του tutorial. Της γρήγορης δηλαδή εκδοχής που χρησιμοποιεί τον δείκτη: tail για να προσθέσει τον νέο κόμβο στη λίστα, χωρίς να χρειάζεται να διατρέξει ολόκληρη τη λίστα.
Απλώς τώρα έχουμε προσθέσει και τη γραμμή:
- Κώδικας: Επιλογή όλων
(list->len)++;
η οποία αυξάνει το τρέχον μήκος της λίστας μας κατά 1, μετά από
κάθε επιτυχημένη προσθήκη νέου κόμβου.
Με την προϋπόθεση πως έχουμε κατανοήσει ότι έχει καλύψει μέχρι τώρα το tutorial, έχουμε πάρει πολύ καλές βάσεις για τις απλά συνδεδεμένες λίστες.Μερικές καλές ασκήσεις για να τεστάρουμε τις μέχρι τώρα γνώσεις μας είναι να φτιάξουμε συναρτήσεις για την αναζήτηση ή/και διαγραφή του πρώτου κόμβου που θα βρεθεί να έχει την τιμή: value μέσα στη λίστα, π.χ.:
list_del1st( List *list, int value ) και
list_find1st( List *list, int value ). Τις αφήνω να τις κάνετε μόνοι σας για εξάσκηση, ενώ αν θέλετε μπορείτε να τις επεκτείνετε σε πιο γενικές, π.χ. να βρίσκουν ή/και να διαγράφουν όλους του κόμβους που περιέχουν την τιμή: value (
list_delete( List *list, int value ) και
list_search( List *list, int value ) ).
Προς το παρόν παραθέτω τον τελικό κώδικα του
4ου μέρους τροποποιημένο σύμφωνα με τις αλλαγές που κάναμε στο 5ο και στο 6ο μέρος...
- Κώδικας: Επιλογή όλων
/*
* Singly Linked List Tutorial, Part 5 & 6
* (comments are in Greek)
*/
#include <stdio.h>
#include <stdlib.h>
typedef enum { FALSE=0, TRUE } Bool; // ο δικός μας πρόσθετος τύπος Boolean
typedef struct node { // δομή του κάθε κόμβου της λίστας
int value;
struct node *next;
} Node;
typedef struct list { // η κεντρική δομή της λίστας μας
Node *head, *tail;
int len;
} List;
/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην ΑΡΧΗ της λίστας.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_prepend( List *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;
new->value = value;
if ( list->head == NULL ) {
new->next = NULL;
list->head = list->tail = new;
}
else {
new->next = list->head;
list->head = new;
}
(list->len)++;
return TRUE;
}
/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας
* με χρήση δείκτη tail για δραματική επίσπευση της ταχύτητας εισαγωγής.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_append( List *list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;
new->value= value;
new->next = NULL;
if ( list->head == NULL ) {
list->head = list->tail = new;
(list->len)++;
return TRUE;
}
list->tail->next = new;
list->tail = new;
(list->len)++;
return TRUE;
}
/* ------------------------------------------------------------------
* Τύπωμα του πεδίου value όλων των κόμβων της λίστας
* ------------------------------------------------------------------
*/
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 ) // ισοδυναμεί με: if ( list.head == NULL )
return;
Node *dummy = NULL;
while ( list.head ) { // ισοδυναμεί με: while ( list.head != NULL ) {
dummy = list.head->next;
free( list.head );
list.head = dummy;
}
return;
}
// -------------------------------------------------------------------
int main ( void )
{
List list = { .head=NULL, .tail=NULL, .len=0 };
// δημιουργία και εισαγωγή 1ου στοιχείου στο ΤΕΛΟΣ
if ( list_append( &list, 52) == FALSE ) { // αποτυχία
puts("*** out of memory, aborting program");
exit( EXIT_FAILURE );
}
// δημιουργία και εισαγωγή 2ου στοιχείου στο ΤΕΛΟΣ
if ( list_append( &list, 62) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}
// δημιουργία και εισαγωγή 3ου στοιχείου στην ΑΡΧΗ
if ( list_prepend( &list, 72) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}
// δημιουργία και εισαγωγή 4ου στοιχείου στην ΑΡΧΗ
if ( list_prepend( &list, 82) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy(list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}
// καταμέτρηση και τύπωμα του πλήθους των κόμβων στη λίστα
printf("The list consists of %d nodes\n", list.len );
// τύπωμα των πεδίων value του 1ου και του τελευταίου κόμβου
printf("(head = %d, tail = %d)\n", list.head->value, list.tail->value);
// τύπωμα των στοιχείων της λίστας
list_print( list );
// αποδέσμευση όλων των κόμβων από τη μνήμη
list_destroy( list );
fflush(stdin); getchar();
exit( EXIT_SUCCESS );
}
Μπορείτε επίσης να τον δείτε με syntax-highlighting, σύνδεσμο κατεβάσματος και δείγμα εξόδου εδώ:
http://codepad.org/t6WNncoLΜε την αναδιοργάνωση που κάναμε στη δομή της λίστας μας (και πέρα από την καλύτερη γενικότερη δόμηση του προγράμματος και του κώδικά μας) η επιλογή να συμπεριλάβουμε το πεδίο:
len μέσα στη νέα δομή της λίστας και να το ενημερώνουμε σε πραγματικό χρόνο σε κάθε προσθήκη νέων κόμβων, μας επιτρέπει να παίρνουμε
ΑΚΑΡΙΑΙΑ το μήκος της λίστας με μια απλή εξέταση της τιμής που περιέχεται στην μεταβλητή:
list.len.
Συγκρινόμενος αυτός ο τρόπος με τον προηγούμενο που για να υπολογίσει το μήκος της λίστας καλούσε τη συνάρτηση: list_len() και διέτρεχε ΟΛΗ τη λίστα από την αρχή μέχρι το τέλος της, είναι προφανώς η "μέρα με τη νύχτα" !
Αν δεν έχετε πιάσει ή λύσει ακόμα την άσκηση που έβαλα μετά το 5ο μέρος, μπορείτε να δείτε εκ νέου την εκφώνηση της στο spoiler που ακολουθεί, αυτή της φορά με περισσότερες συμβουλές και links:ΕΚΦΩΝΗΣΗ:Γράψτε ένα πρόγραμμα που θα διαβάζει από το πληκτρολόγιο τυχαίο πλήθος λέξεων (μια λέξη ανά γραμμή) και σε τυχαία σειρά μέχρι να διαβάσει τη λέξη "stop". Κάθε λέξη (συμπεριλαμβανομένης της "stop") θα μετατρέπεται σε πεζά γράμματα και ανάλογα με το γράμμα από το οποίο αρχίζει θα αποθηκεύεται στην λίστα του αντίστοιχου γράμματος, σε αντίστροφη χρονολογική σειρά (οι πιο πρόσφατα πληκτρολογημένες λέξεις θα εμφανίζονται πρώτες στη λίστα τους).
Δηλαδή όσες λέξεις ξεκινάνε με το γράμμα a θα αποθηκεύονται στη λίστα που αντιστοιχεί στο a, όσες ξεκινάνε από b θα αποθηκεύονται στη λίστα που αντιστοιχεί στο b, κλπ. Αν μια λέξη αρχίζει από χαρακτήρα μικρότερο του 'a' θα μπαίνει στη λίστα του a, ενώ αν αρχίζει από χαρακτήρα μεγαλύτερο του 'z' θα μπαίνει στη λίστα του z.
Πριν τερματίσει το πρόγραμμα θα τυπώνει τα περιεχόμενα (λέξεις) μόνο όσων λιστών δεν είναι άδειες, καθώς και το σε ποιο γράμμα αντιστοιχούν και πόσες λέξεις περιέχουν. Στο τέλος θα τυπώνει το συνολικό πλήθος των λέξεων που περιέχονται σε όλες τις λίστες. Χάριν απλότητας του κώδικα, θεωρήστε πως κάθε γραμμή εισόδου περιλαμβάνει μια μόνο λέξη.
ΔΕΙΓΜΑ ΕΞΟΔΟΥ:
ΣΥΜΒΟΥΛΕΣ:Το παραπάνω μπορεί να γίνει εύκολα και γρήγορα με μια πολύ απλοϊκή υλοποίηση ενός
hash table, που θα είναι ένας πίνακας από 26 λίστες. Δηλαδή κάθε θέση του πίνακα θα αντιστοιχεί σε ένα γράμμα της λατινικής αλφαβήτου, και θα περιέχει μια απλά συνδεδεμένη λίστα.
Για παράδειγμα:
- Κώδικας: Επιλογή όλων
List alphabet[26];
Για να αντιστοιχείτε το πρώτο γράμμα της κάθε λέξης που διαβάζετε με την κατάλληλη θέση στον πίνακα, εκμεταλλευτείτε το γεγονός πως στην C οι χαρακτήρες αντιστοιχούν σε ASCII codes, που είναι ακέραιοι. Οπότε για παράδειγμα, αν c είναι μια μεταβλητή που περιέχει το 1ο γράμμα μιας λέξης, τότε η λίστα στην οποία θα πρέπει να προστεθεί η λέξη είναι η...
- Κώδικας: Επιλογή όλων
alphabet[ c - 'a' ]
Φτιάξτε μια συνάρτηση:
init_alphabet( List alphabet[] ) η οποία θα αρχικοποιεί και τις 26 λίστες του πίνακα alphabet με τις τιμές: head=NULL, tail=NULL και len=0. Την συνάρτηση αυτή θα πρέπει να την καλέστε πρώτη, πριν ξεκινήσετε να κάνετε οτιδήποτε άλλο στις λίστες σας.
ΑΛΛΕΣ ΣΗΜΕΙΩΣΕΙΣ:Τα hash-tables είναι μια εξαιρετικά δημοφιλής τακτική για μεγάλη επίσπευση στην αναζήτηση στοιχείων.
Φανταστείτε για παράδειγμα να είχατε 10000 λέξεις, την μια δίπλα στην άλλη είτε μέσα σε έναν απλό πίνακα είτε μέσα σε μια απλή λίστα. Για να αναζητήσετε μια από αυτές θα έπρεπε να αρχίστε να διατρέχετε τον πίνακα ή την λίστα από την αρχή, ένα-ένα στοιχείο, μέχρι να βρείτε τη λέξη που αναζητάτε.
Αν η λέξη που αναζητάτε βρίσκεται σε πολύ πίσω θέση του πίνακα ή της λίστας, τότε θα χρειαστείτε πολύ χρόνο μέχρι να την βρείτε (π.χ. αν η λέξη σας είναι η τελευταία, θα χρειαστεί να διατρέξετε ένα-ένα 9999 στοιχεία).
Αντίθετα, με την τεχνική του hash-table, πάτε απευθείας με μια και μόνο κίνηση στη λίστα του πρώτου γράμματος της λέξης σας, και ξεκινάτε να ψάχνετε για τη λέξη σας σε αυτή τη λίστα, η οποία κατά μέσο όρο θα είναι πολύ μικρότερη σε μήκος, συγκρινόμενη με μια ενιαία λίστα ολόκληρου του λεξιλόγιου.
Όσοι ξέρετε Αγγλικά, ρίξτε μια ματιά σε αυτό το άρθρο:
http://www.sparknotes.com/cs/searching/hashtables/section1.html που εξηγεί με απλά λόγια και σχήματα μια επίσης απλή περίπτωση χρήσης ενός hash-table με strings (εκείνος χρησιμοποιεί άλλο κριτήριο για την αντιστοίχιση των λέξεων σε θέσεις του πίνακα, αλλά θα σας βοηθήσει νομίζω να καταλάβετε καλύτερα τη γενική ιδέα του hashing ).
