10. Υλοποίηση δομών δεδομένων και αλγορίθμων στη C

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

Προαπαιτούμενη γνώση Τύποι δεδομένων, είσοδος/έξοδος, δομές επιλογής και επανάληψης, συναρτήσεις, πίνακες, δομές, δείκτες, αλφαριθμητικά.

10.1 Εισαγωγή

Οι δομές δεδομένων είναι διευθετήσεις αποθηκευμένων δεδομένων που διευκολύνουν τον χειρισμό τους. Τυπικές δομές δεδομένων είναι οι πίνακες, οι λίστες, οι στοίβες, οι ουρές, οι σωροί, οι πίνακες κατακερματισμού, τα γραφήματα και τα δένδρα. Για τις δομές αυτές υπάρχουν διάφορες παραλλαγές τους με ιδιαίτερα χαρακτηριστικά που διευκολύνουν την αποδοτική επίλυση συγκεκριμένων προβλημάτων. Παραδείγματα είναι οι διπλά συνδεδεμένες λίστες, τα ισοζυγισμένα δυαδικά δένδρα, τα κατευθυνόμενα γραφήματα με βάρη καθώς και άλλες δομές. Από την άλλη μεριά, ένας αλγόριθμος είναι μια σειρά λειτουργιών προς εκτέλεση που στοχεύει στην επίλυση ενός προβλήματος. Οι αλγόριθμοι πραγματοποιούν υπολογισμούς, επεξεργασία δεδομένων και εργασίες αυτοματοποίησης. Υπάρχουν αλγόριθμοι που είναι «διάσημοι» λόγω του ότι προσφέρουν κομψές λύσεις σε προβλήματα με υψηλή πρακτική και θεωρητική αξία. Μερικοί τέτοιοι αλγόριθμοι είναι η γρήγορη ταξινόμηση (quicksort), ο αλγόριθμος δυαδικής αναζήτησης για τον εντοπισμό μιας τιμής σε μια ταξινομημένη ακολουθία, ο αλγόριθμος εύρεσης των συντομότερων διαδρομών σε ένα γράφημα του Dijkstra, οι αλγόριθμοι κρυπτογραφικού κατακερματισμού (cryptographic hashes, π.χ. SHA256) και o αλγόριθμος PageRank για την αξιολόγηση της «σπουδαιότητας» κάθε ιστοσελίδας σε ένα δίκτυο ιστοσελίδων.
Η ποιότητα των λύσεων που παράγονται σε υπολογιστικά προβλήματα εξαρτάται από τους αλγορίθμους και τις δομές δεδομένων που χρησιμοποιούνται. Η γνώση του κατάλληλου αλγορίθμου και των κατάλληλων δομών δεδομένων μπορεί να κάνει τη διαφορά ανάμεσα σε ένα λειτουργικό πρόγραμμα και σε ένα πρόγραμμα που είτε σπαταλά πόρους είτε δεν είναι σε θέση να εφαρμοστεί στην πράξη. Από την άλλη μεριά, η γνώση δομών δεδομένων και αλγορίθμων επιτρέπει τη χρήση κοινής ορολογίας που διευκολύνει την επικοινωνία ανάμεσα στα μέλη της ομάδας ανάπτυξης υπολογιστικών λύσεων.
Η C σε αντίθεση με άλλες γλώσσες προγραμματισμού όπως η C++ με τη βιβλιοθήκη STL, η Java με τα Collections, η Python με τις ενσωματωμένες δομές δεδομένων λίστας, πλειάδας, λεξικού και συνόλου, δεν διαθέτει στις βιβλιοθήκες της έτοιμες υλοποιήσεις δομών δεδομένων. Ο προγραμματιστής καλείται να υλοποιήσει ο ίδιος τις δομές δεδομένων που θα χρειαστεί ή να χρησιμοποιήσει κάποια εξωτερική βιβλιοθήκη όπως είναι η glib(1), η klib(2), η STC(3), η M*LIB(4), η CTL(5), η uthash(6) και άλλες, καθώς και υλοποιήσεις όπως η “Abstract Data Types in C”(7). Ειδικά για τη glib χρήσιμες πληροφορίες που περιγράφουν τη χρήση της μπορούν να εντοπιστούν στο ¹. Βιβλία αναφοράς για την υλοποίηση δομών δεδομένων και αλγορίθμων στη C είναι τα ², ³.

10.2 Αφηρημένοι Τύποι Δεδομένων

Οι Αφηρημένοι Τύποι Δεδομένων (ADT=Abstract Data Types) ⁴ είναι μια βασική έννοια της πληροφορικής. Παρέχουν μια υψηλού επιπέδου περιγραφή των δεδομένων και των λειτουργιών που μπορούν να εφαρμοστούν στα δεδομένα χωρίς να περιγράφουν πώς πραγματοποιούνται αυτές οι λειτουργίες. Τα ADTs είναι ανεξάρτητα υλοποίησης που σημαίνει ότι μπορεί να υλοποιηθεί το ίδιο ADT χρησιμοποιώντας διαφορετικές δομές δεδομένων και αλγορίθμους. Για παράδειγμα ο αφηρημένος τύπος δεδομένων «λίστα» μπορεί να υλοποιηθεί είτε με έναν πίνακα είτε με μια συνδεδεμένη λίστα και οι χρήστες του ADT δεν χρειάζεται να γνωρίζουν ποια ακριβώς υλοποίηση έχει χρησιμοποιηθεί. Συνηθισμένοι ADTs είναι οι λίστες, οι στοίβες, οι ουρές, τα δένδρα, τα γραφήματα, τα σύνολα και οι πίνακες αντιστοιχίσεων. Για καθένα από τους ADT που αναφέρθηκαν ακολουθεί μια σύντομη περιγραφή του καθώς και των τυπικών λειτουργιών που μπορεί να υποστηρίζουν.

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

Στοίβες Η στοίβα (stack) μπορεί να θεωρηθεί ως μια «κατακόρυφη δομή» που επιτρέπει μόνο εισαγωγή στοιχείων στην κορυφή της και διαγραφή στοιχείων από την κορυφή της. Αυτό σημαίνει ότι το τελευταίο στοιχείο που θα εισαχθεί σε μια στοίβα θα είναι και το πρώτο που θα εξαχθεί. Αυτή η ιδιότητα της στοίβας ονομάζεται LIFO (Last In First Out), δηλαδή τελευταίο μέσα πρώτο έξω. Τυπικές λειτουργίες μιας στοίβας είναι η ώθηση ενός στοιχείου στην κορυφή της στοίβας, η απώθηση ενός στοιχείου από την κορυφή της στοίβας, η εκκαθάριση της στοίβας, η ανάκτηση του κορυφαίου στοιχείου της στοίβας (χωρίς την απώθησή του από τη στοίβα) και η επιστροφή του πλήθους των στοιχείων της.

Ουρές Η ουρά (queue) διατηρεί δεδομένα που εισάγονται στο πίσω άκρο της και εξάγονται από το εμπρός άκρο της. Κατ’ αντιστοιχία με τη στοίβα η ιδιότητα που χαρακτηρίζει την ουρά είναι η FIFO (First In First Out), δηλαδή πρώτο μέσα πρώτο έξω. Τυπικές λειτουργίες μιας ουράς είναι η εισαγωγή ενός στοιχείου στο πίσω άκρο της, η εξαγωγή ενός στοιχείου από το εμπρός άκρο της, η εκκαθάριση της ουράς και η επιστροφή του πλήθους των στοιχείων της.

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

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

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

Πίνακες αντιστοιχίσεων ή λεξικά Οι πίνακες αντιστοιχίσεων (associative arrays ή maps ή hashmaps ή dictionaries) αποθηκεύουν ζεύγη της μορφής (κλειδί, τιμή)(1). Κάθε κλειδί μπορεί να εμφανίζεται μόνο μια φορά και κάθε κλειδί μπορεί να αντιστοιχεί σε μια μόνο τιμή. Οι πίνακες αντιστοιχίσεων χρησιμοποιούνται πολύ συχνά στον προγραμματισμό εφαρμογών. Τυπικές λειτουργίες σε έναν πίνακα αντιστοιχίσεων είναι η προσθήκη ενός νέου ζεύγους (κλειδί, τιμή), η αναζήτηση της τιμής για ένα κλειδί και η διαγραφή ενός ζεύγους (κλειδί, τιμή) με βάση την τιμή του κλειδιού.

(key, value)

Μερικές φορές οι όροι «αφηρημένος τύπος δεδομένων» και «δομή δεδομένων» μπορούν να χρησιμοποιούνται χωρίς να γίνεται διάκριση μεταξύ τους (π.χ. «ο αφηρημένος τύπος δεδομένων στοίβα» και «η δομή δεδομένων στοίβα»). Ωστόσο, ενώ ο αφηρημένος τύπος δεδομένων είναι ένα σύνολο προδιαγραφών που ορίζει δεδομένα και λειτουργίες χωρίς να προσδιορίζει γλώσσα προγραμματισμού ή υλοποίηση, η δομή δεδομένων εστιάζει ακριβώς σε μια συγκεκριμένη υλοποίηση προσδιορίζοντας τον τρόπο που τα δεδομένα θα αποθηκεύονται στη μνήμη καθώς και την υλοποίηση των λειτουργιών σε κάποια γλώσσα προγραμματισμού εφαρμόζοντας κατάλληλους αλγορίθμους.
Στη συνέχεια θα παρουσιαστούν υλοποιήσεις στη C για 3 αφηρημένους τύπους δεδομένων. Αρχικά θα παρουσιαστεί μια υλοποίηση στοίβας χρησιμοποιώντας έναν πίνακα συνεχόμενων θέσεων μνήμης. Στη συνέχεια θα παρουσιαστεί μια υλοποίηση απλά συνδεδεμένης λίστας. Τέλος, θα παρουσιαστεί μια υλοποίηση ενός δυαδικού δένδρου αναζήτησης όπου κάθε κόμβος του δένδρου διαθέτει δύο δείκτες προς κόμβους παιδιά.
Να σημειωθεί ότι οι υλοποιήσεις που παραθέτονται δεν είναι οι πλέον αποδοτικές ούτε βέβαια οι μοναδικές που μπορούν να υπάρξουν. Η έμφαση έχει δοθεί στην παρουσίαση της χρησιμότητας χαρακτηριστικών εννοιών της C, όπως οι δείκτες και η δυναμική δέσμευση και αποδέσμευση μνήμης.

10.3 Υλοποίηση στοίβας

Στην υλοποίηση της στοίβας που ακολουθεί (κώδικας 10.1), η στοίβα μπορεί να δεχθεί ένα συγκεκριμένο πλήθος στοιχείων που ορίζεται κατά τη δημιουργία της. Τα στοιχεία που περιέχει είναι υποθετικές εργασίες (task_t) με ένα αναγνωριστικό (id) για κάθε εργασία. Η δομή της στοίβας (my_stack_t) περιλαμβάνει έναν πίνακα από στοιχεία task_t και έναν δείκτη προς task_t με όνομα top που δείχνει στο τελευταίο στοιχείο που προστέθηκε στη στοίβα. Επιπλέον, διαθέτει δύο ακέραιες μεταβλητές count και capacity που διατηρούν τιμές για το πλήθος των στοιχείων που έχουν εισαχθεί στη στοίβα και τη μέγιστη χωρητικότητα της στοίβας αντίστοιχα. Το Σχήμα 10.1 δείχνει αριστερά την εικόνα που μπορεί να έχει στο μυαλό του κάποιος που θα χρησιμοποιήσει τη στοίβα ως δομή, ενώ δεξιά παρουσιάζει λεπτομέρειες που αφορούν τη συγκεκριμένη υλοποίηση, όπου ο δείκτης top δείχνει το στοιχείο της στοίβας που βρίσκεται στην κορυφή της.

Σχήμα 10.1: Στοίβα.

Οι συναρτήσεις που περιέχει η υλοποίηση είναι η create_stack(), η push(), η pop(), η print() και η destroy() με τα πρωτότυπά τους να εμφανίζονται στις γραμμές 15 έως και 19.

Κώδικας 10.1: ch10_p1.c - υλοποίηση στοίβας με περιεχόμενα εργασίες (tasks), όπου η χωρητικότητα της στοίβας ορίζεται κατά την εκτέλεση.
#include <stdio.h>
#include <stdlib.h>

typedef struct task {
  int id;
} task_t;

typedef struct stack {
  task_t *tasks;
  int capacity;
  int count;
  task_t *top;
} my_stack_t;

my_stack_t *create_stack(int capacity);
int push(my_stack_t *s, int task_id);
task_t *pop(my_stack_t *s);
void print(my_stack_t *s);
void destroy_stack(my_stack_t *s);

int main(void) {
  // δημιουργία στοίβας με 5 θέσεις
  my_stack_t *stack_ptr = create_stack(5);

  // ώθηση στοιχείων στη στοίβα
  int job_ids[4] = {7, 21, 42, 33};
  for (int i = 0; i < 4; i++) {
    push(stack_ptr, job_ids[i]);
    printf("Task %d pushed, stack size/capacity=%d/%d\n", job_ids[i],
           stack_ptr->count, stack_ptr->capacity);
  }

  // εκτύπωση στοιχείων στοίβας
  print(stack_ptr);

  // απώθηση τεσσάρων στοιχείων από τη στοίβα, 1 προς 1
  for (int i = 0; i < 4; i++) {
    task_t *t = pop(stack_ptr);
    printf("Task %d popped, stack size/capacity=%d/%d\n", t->id,
           stack_ptr->count, stack_ptr->capacity);
  }

  // απόπειρα απώθησης από άδεια στοίβα
  pop(stack_ptr);

  destroy_stack(stack_ptr);
  return 0;
}

my_stack_t *create_stack(int capacity) {
  my_stack_t *s = malloc(sizeof(my_stack_t));
  if (s == NULL) {
    printf("Unable to allocate memory\n");
    exit(-1);
  }
  s->tasks = malloc(sizeof(task_t) * capacity);
  if (s->tasks == NULL) {
    printf("Unable to allocate memory\n");
    exit(-1);
  }
  s->count = 0;
  s->capacity = capacity;
  s->top = NULL;
  return s;
}

int push(my_stack_t *s, int task_id) {
  // έλεγχος αν η στοίβα είναι γεμάτη
  if (s->count == s->capacity) {
    printf("Push of %d failed: maximum capacity of %d is reached!\n", task_id,
           s->capacity);
    return -1;
  }
  // έλεγχος αν η στοίβα δεν έχει στοιχεία
  if (s->top == NULL) {
    s->top = s->tasks;
  } else {
    s->top++;
  }
  s->top->id = task_id;
  s->count++;
  return 0;
}

task_t *pop(my_stack_t *s) {
  // έλεγχος αν η στοίβα είναι άδεια
  if (s->count == 0) {
    printf("Pop failed: the stack is empty!\n");
    return NULL;
  }
  s->count--;
  // έλεγχος αν η στοίβα έχει 1 μόνο στοιχείο
  if (s->top == s->tasks) {
    s->top = NULL;
    return s->tasks;
  } else {
    s->top--;
    return s->top + 1;
  }
}

void print(my_stack_t *s) {
  printf("------\n");
  task_t *b_it = s->top; // iterator προς τα πίσω
  for (int i = 0; i < s->count; i++) {
    if (b_it == s->top) {
      printf("%d <--top\n", b_it->id);
    } else {
      printf("%d\n", b_it->id);
    }
    b_it--;
  }
  printf("------\n");
}

void destroy_stack(my_stack_t *s) {
  free(s->tasks);
  free(s);
}

Η συνάρτηση create_stack() δεσμεύει μνήμη τόσο για τη στοίβα όσο και για τις συνεχόμενες θέσεις μνήμης όπου θα αποθηκευτούν τα δεδομένα των εργασιών (tasks). Επιπλέον θέτει το πλήθος στοιχείων της στοίβας στην αρχική τιμή 0, τη χωρητικότητα στην τιμή που έχει δεχθεί ως όρισμα και ορίζει τον δείκτη top στην τιμή NULL.
Η συνάρτηση push() ελέγχει αρχικά αν η στοίβα είναι πλήρης και αν αυτό διαπιστωθεί δεν επιτρέπει την ώθηση στη στοίβα της νέας εργασίας. Αν η στοίβα είναι κενή τότε ορίζεται ότι ο δείκτης top θα δείχνει στην πρώτη θέση της δεσμευμένης μνήμης για τα δεδομένα εργασιών, αλλιώς ο δείκτης top αυξάνεται κατά ένα έτσι ώστε να δείχνει στην επόμενη θέση. Τέλος, αποθηκεύεται ο κωδικός της νέας εργασίας στη θέση που δείχνει ο δείκτης top και αυξάνεται ο μετρητής στοιχείων της στοίβας (count) κατά ένα.
Η συνάρτηση pop() εξετάζει αρχικά αν η στοίβα είναι άδεια, οπότε και δεν επιτρέπει την απώθηση από τη στοίβα. Στη συνέχεια ελέγχει αν η στοίβα έχει μόνο ένα στοιχείο, οπότε η απώθηση θα πρέπει να ορίσει τον δείκτη top στην τιμή NULL, αλλιώς να τον μειώσει κατά ένα. Τέλος, ο μετρητής στοιχείων της στοίβας (count) μειώνεται κατά ένα και η συνάρτηση επιστρέφει έναν δείκτη προς την εργασία που απωθήθηκε. Η συνάρτηση print() εμφανίζει τις εργασίες που περιέχει η στοίβα χρησιμοποιώντας έναν δείκτη (b_it για backwards iterator) που αρχικά δείχνει στο στοιχείο της στοίβας που δείχνει ο δείκτης top (δηλαδή στην κορυφή της στοίβας) και μειώνοντας επαναληπτικά κατά ένα τον δείκτη τόσες φορές όσα τα στοιχεία της στοίβας, επιτυγχάνεται η διάσχιση της στοίβας από την κορυφή προς τα κάτω.
Η συνάρτηση destroy() απελευθερώνει αρχικά τον συνεχόμενο χώρο που έχει δεσμευθεί για τα περιεχόμενα των εργασιών και στη συνέχεια απελευθερώνει τη δομή της στοίβας.
Ακολουθεί η έξοδος που παράγεται κατά την εκτέλεση του προγράμματος.

Task 7 pushed, stack size/capacity=1/5
Task 21 pushed, stack size/capacity=2/5
Task 42 pushed, stack size/capacity=3/5
Task 33 pushed, stack size/capacity=4/5
‐‐‐‐‐‐
33 <‐‐top
42
21
7
‐‐‐‐‐‐
Task 33 popped, stack size/capacity=3/5
Task 42 popped, stack size/capacity=2/5
Task 21 popped, stack size/capacity=1/5
Task 7 popped, stack size/capacity=0/5
Pop failed: the stack is empty!

Μια παρόμοια υλοποίηση που όμως αφορά ουρά καθώς και υλοποιήσεις άλλων δομών δεδομένων μπορούν να εντοπιστούν στο http://thradams.com/generator/queue.html.

10.4 Υλοποίηση απλά συνδεδεμένης λίστας

Μια συνδεδεμένη λίστα είναι μια δομή δεδομένων που αποτελείται από μια ακολουθία στοιχείων που ονομάζονται κόμβοι (nodes). Στην απλούστερη περίπτωση κάθε κόμβος περιέχει δύο συστατικά στοιχεία: τα δεδομένα του κόμβου και έναν δείκτη προς τον επόμενο κόμβο στην ακολουθία, όπως φαίνεται στο Σχήμα 10.2. Οι συνδεδεμένες λίστες επιτρέπουν τη δυναμική δέσμευση μνήμης και την αποδοτική εισαγωγή και διαγραφή στοιχείων, γεγονός που τις καθιστά χρήσιμες σε διάφορες εφαρμογές κατά τον προγραμματισμό με τη C. Υπάρχουν τρεις βασικοί τύποι συνδεδεμένων λιστών, οι απλά συνδεδεμένες λίστες, οι διπλά συνδεδεμένες λίστες και οι κυκλικά συνδεδεμένες λίστες. Οι απλά συνδεδεμένες λίστες, για τις οποίες θα παρουσιαστεί ένα παράδειγμα στη συνέχεια, αποτελούνται από κόμβους που ο καθένας δείχνει στον επόμενό του στη λίστα. Οι διπλά συνδεδεμένες λίστες αποτελούνται από κόμβους, που ο καθένας διαθέτει δύο δείκτες, έναν που δείχνει στον προηγούμενό του στη λίστα και έναν που δείχνει στον επόμενό του στη λίστα. Οι κυκλικά συνδεδεμένες λίστες είναι απλά συνδεδεμένες λίστες, που ο τελευταίος κόμβος της λίστας δείχνει στον πρώτο.

Σχήμα 10.2: Μια απλά συνδεδεμένη λίστα με 4 κόμβους.

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

1. Display all students
2. Insert a student at the begin of the list
3. Insert a student at the end of the list
4. Delete student by id
5. Delete all students

Η επιλογή 1 διανύει την απλά συνδεδεμένη λίστα και εμφανίζει όλους τους κόμβους της. Η επιλογή 2 εισάγει στην αρχή της λίστας έναν νέο κόμβο. Για τον κόμβο αυτό δεσμεύεται δυναμικά μνήμη και η εισαγωγή του στην αρχή της λίστας γίνεται γρήγορα με απλή διευθέτηση των δεικτών όπου o νέος κόμβος δείχνει εκεί που δείχνει ο δείκτης head (δείκτης στον πρώτο κόμβο της λίστας) και στη συνέχεια ο δείκτης head δείχνει στον νέο κόμβο (βλ. Σχήμα 10.3).

Σχήμα 10.3: Σχηματική αναπαράσταση της απλά συνδεδεμένης λίστας του κώδικα 10.2 για την πράξη της εισαγωγής στην αρχή της λίστας.

Η επιλογή 3 εισάγει στο τέλος της λίστας έναν νέο κόμβο. Για να εισαχθεί ο νέος κόμβος σε αυτήν την περίπτωση θα πρέπει πρώτα να διανυθεί η λίστα μέχρι το τέλος της. Η επιλογή 4 εντοπίζει έναν κόμβο με βάση έναν κωδικό φοιτητή και τον διαγράφει από τη λίστα, αποδεσμεύοντας τη μνήμη που καταλάμβανε ο κόμβος που διαγράφεται (βλ. Σχήμα 10.4).

Σχήμα 10.3: Σχηματική αναπαράσταση της απλά συνδεδεμένης λίστας του κώδικα 10.2 για την πράξη της διαγραφής ενδιάμεσου κόμβου της λίστας.

Η επιλογή 5 διαγράφει όλη τη λίστα αποδεσμεύοντας τη μνήμη που έχει δεσμευθεί για τη λίστα.
Ο κώδικας 10.2 ορίζει τη δομή ενός κόμβου (node_t) που περιέχει έναν δείκτη προς μια δομή student_t και έναν δείκτη προς την ίδια δομή. Πρόκειται δηλαδή για μια αναδρομική δομή (recursive data structure). Τα πρωτότυπα των συναρτήσεων βρίσκονται στις γραμμές κώδικα 15 έως και 20. Η read_student() ζητά από τον χρήστη την εισαγωγή τιμών για έναν φοιτητή (κωδικό και όνομα) και οι υπόλοιπες συναρτήσεις ορίζουν τις λειτουργίες της απλά συνδεδεμένης λίστας.

Κώδικας 10.2: ch10_p2.c - υλοποίηση μιας απλά συνδεδεμένης λίστας.
#include <stdio.h>
#include <stdlib.h>

typedef struct task {
  int id;
} task_t;

typedef struct stack {
  task_t *tasks;
  int capacity;
  int count;
  task_t *top;
} my_stack_t;

my_stack_t *create_stack(int capacity);
int push(my_stack_t *s, int task_id);
task_t *pop(my_stack_t *s);
void print(my_stack_t *s);
void destroy_stack(my_stack_t *s);

int main(void) {
  // δημιουργία στοίβας με 5 θέσεις
  my_stack_t *stack_ptr = create_stack(5);

  // ώθηση στοιχείων στη στοίβα
  int job_ids[4] = {7, 21, 42, 33};
  for (int i = 0; i < 4; i++) {
    push(stack_ptr, job_ids[i]);
    printf("Task %d pushed, stack size/capacity=%d/%d\n", job_ids[i],
           stack_ptr->count, stack_ptr->capacity);
  }

  // εκτύπωση στοιχείων στοίβας
  print(stack_ptr);

  // απώθηση τεσσάρων στοιχείων από τη στοίβα, 1 προς 1
  for (int i = 0; i < 4; i++) {
    task_t *t = pop(stack_ptr);
    printf("Task %d popped, stack size/capacity=%d/%d\n", t->id,
           stack_ptr->count, stack_ptr->capacity);
  }

  // απόπειρα απώθησης από άδεια στοίβα
  pop(stack_ptr);

  destroy_stack(stack_ptr);
  return 0;
}

my_stack_t *create_stack(int capacity) {
  my_stack_t *s = malloc(sizeof(my_stack_t));
  if (s == NULL) {
    printf("Unable to allocate memory\n");
    exit(-1);
  }
  s->tasks = malloc(sizeof(task_t) * capacity);
  if (s->tasks == NULL) {
    printf("Unable to allocate memory\n");
    exit(-1);
  }
  s->count = 0;
  s->capacity = capacity;
  s->top = NULL;
  return s;
}

int push(my_stack_t *s, int task_id) {
  // έλεγχος αν η στοίβα είναι γεμάτη
  if (s->count == s->capacity) {
    printf("Push of %d failed: maximum capacity of %d is reached!\n", task_id,
           s->capacity);
    return -1;
  }
  // έλεγχος αν η στοίβα δεν έχει στοιχεία
  if (s->top == NULL) {
    s->top = s->tasks;
  } else {
    s->top++;
  }
  s->top->id = task_id;
  s->count++;
  return 0;
}

task_t *pop(my_stack_t *s) {
  // έλεγχος αν η στοίβα είναι άδεια
  if (s->count == 0) {
    printf("Pop failed: the stack is empty!\n");
    return NULL;
  }
  s->count--;
  // έλεγχος αν η στοίβα έχει 1 μόνο στοιχείο
  if (s->top == s->tasks) {
    s->top = NULL;
    return s->tasks;
  } else {
    s->top--;
    return s->top + 1;
  }
}

void print(my_stack_t *s) {
  printf("------\n");
  task_t *b_it = s->top; // iterator προς τα πίσω
  for (int i = 0; i < s->count; i++) {
    if (b_it == s->top) {
      printf("%d <--top\n", b_it->id);
    } else {
      printf("%d\n", b_it->id);
    }
    b_it--;
  }
  printf("------\n");
}

void destroy_stack(my_stack_t *s) {
  free(s->tasks);
  free(s);
}

Η συνάρτηση insert_student_at_begin() δέχεται ως όρισμα έναν διπλό δείκτη προς node_t, όπως συμβαίνει και με τις επόμενες 3 συναρτήσεις. Αυτό απαιτείται διότι ενδέχεται να αλλάξει η τιμή του δείκτη head στη main() μέσα από κάποια από αυτές τις συναρτήσεις, οπότε θα πρέπει η συνάρτηση να μπορεί να αλλάξει τη θέση που θα δείχνει ο δείκτης head. Η συνάρτηση δημιουργεί δυναμικά έναν νέο κόμβο και τον ορίζει ως κεφαλή της λίστας, ενώ σε περίπτωση που η λίστα δεν είναι άδεια ορίζει τον δείκτη next του νέου κόμβου να δείχνει προς την παλιά κεφαλή της λίστας.
Η συνάρτηση insert_student_at_end() διασχίζει τη συνδεδεμένη λίστα μέχρι να βρεθεί στον τελευταίο κόμβο της. Δημιουργεί έναν νέο κόμβο και αλλάζει τον δείκτη next του τελευταίου κόμβου έτσι ώστε να δείχνει στον νέο κόμβο. Η διάσχιση της λίστας ξεκινά με έναν δείκτη (curr) να δείχνει στην κεφαλή της λίστας και προχωρά στους επόμενους κόμβους αναθέτοντας σε κάθε βήμα ως τιμή του curr την τιμή που δείχνει ο δείκτης next του κόμβου που δείχνει ο curr. Η διάσχιση ολοκληρώνεται όταν ο δείκτης curr γίνει NULL.
Η συνάρτηση delete_student_by_id() εξετάζει διάφορες ειδικές περιπτώσεις όπως φαίνεται και από τα σχόλια στον κώδικά της. Ενδιαφέρον παρουσιάζει η περίπτωση που η λίστα έχει δύο τουλάχιστον κόμβους, οπότε και χρησιμοποιούνται δύο δείκτες (curr και curr_prev), με τον πρώτο να δείχνει σε έναν κόμβο και τον δεύτερο να δείχνει στον αμέσως προηγούμενο κόμβο. Όταν ο δείκτης curr δείξει στον κόμβο που πρόκειται να διαγραφεί, τότε ορίζεται εκ νέου το πεδίο next του κόμβου που δείχνει o curr_prev έτσι ώστε να δείχνει στο επόμενο στοιχείο του κόμβου που δείχνει ο curr και στη συνέχεια ο κόμβος που δείχνει ο curr να αποδεσμεύεται από τη μνήμη.
Η συνάρτηση delete_all_students() πραγματοποιεί διάσχιση της συνδεδεμένης λίστας αποδεσμεύοντας τόσο τη δομή student_t όπου δείχνει το πεδίο a_student του τρέχοντα κόμβου, όσο και τον ίδιο τον κόμβο της στοίβας (node_t).
Η συνάρτηση print_all_students() εμφανίζει τα περιεχόμενα της συνδεδεμένης λίστας πραγματοποιώντας μια απλή διάσχιση της λίστας και εμφανίζοντας σε κάθε βήμα τα περιεχόμενα του τρέχοντος κόμβου.

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

1. Display all students
2. Insert a student at the begin of the list
3. Insert a student at the end of the list
4. Delete student by id
5. Delete all students
6. Exit
Enter your choice: 3
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
Enter id and name of student: 101 Nikos
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
...
Enter your choice: 3
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
Enter id and name of student: 111 Maria
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
...
Enter your choice: 3
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
Enter id and name of student: 304 Vivi
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
...
Enter your choice: 1
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
ID=101, NAME=Nikos
ID=111, NAME=Maria
ID=304, NAME=Vivi
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
...
Enter your choice: 2
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
Enter id and name of student: 501 Christos
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
...
Enter your choice: 1
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
ID=501, NAME=Christos
ID=101, NAME=Nikos
ID=111, NAME=Maria
ID=304, NAME=Vivi

10.5 Υλοποίηση δυαδικού δένδρου αναζήτησης

Ένα δυαδικό δένδρο (binary tree) είναι μια ιεραρχική δομή δεδομένων που αποτελείται από κόμβους που συνδέονται μεταξύ τους με ακμές όπου κάθε κόμβος έχει το το πολύ δύο παιδιά (το αριστερό παιδί και το δεξί παιδί). Το καθένα από τα παιδιά μπορεί το ίδιο να είναι ένα δυαδικό δένδρο, ορίζοντας με αυτόν τον τρόπο μια αναδρομική δομή. Ο αρχικός κόμβος ονομάζεται ρίζα (root) του δένδρου και λειτουργεί ως αφετηρία για τη διάσχισή του. Οι κόμβοι που δεν έχουν παιδιά είναι τα λεγόμενα φύλλα (leaves) του δένδρου.
Τα δυαδικά δένδρα αναζήτησης (BST=Binary Search Trees) είναι μια παραλλαγή των δυαδικών δένδρων όπου κάθε κόμβος διατηρεί μια τιμή κλειδί και πιθανώς κάποια άλλα δεδομένα. Όλοι οι κόμβοι στο αριστερό υποδένδρο ενός κόμβου έχουν τιμές κλειδιών μικρότερες από το κλειδί του κόμβου και όλοι οι κόμβοι στο δεξί υποδένδρο του έχουν τιμές κλειδιών μεγαλύτερες από το κλειδί του κόμβου. Η ιδιότητα αυτή επιτρέπει στις βασικές λειτουργίες αναζήτηση, εισαγωγή και διαγραφή κόμβου να είναι αποδοτικές. Ένα παράδειγμα δυαδικού δένδρου αναζήτησης φαίνεται στο σχήμα 10.5.

Σχήμα 10.5: Παράδειγμα δυαδικού δένδρου αναζήτησης.

Στη συνέχεια, στον κώδικα 10.2, παρουσιάζεται μια απλή υλοποίηση ενός δυαδικού δένδρου αναζήτησης.
Ο κόμβος του δένδρου (node_t) είναι μια δομή που περιέχει μια ακέραια τιμή (data) και δύο δείκτες left και right προς στοιχεία της ίδια δομής. Στις γραμμές 10 έως και 13 εμφανίζονται τα πρωτότυπα των συναρτήσεων insert_node(), inorder(), preorder() και postorder(). Και οι 4 συναρτήσεις είναι αναδρομικές.

Κώδικας 10.3: ch10_p3.c - δυαδικό δένδρο αναζήτησης.
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *left;
  struct node *right;
} node_t;

void insert_node(node_t **tree_ptr, int value);
void inorder(node_t *tree_ptr);
void preorder(node_t *tree_ptr);
void postorder(node_t *tree_ptr);

int main(void) {
  node_t *root_ptr = NULL;
  int values[] = {5, 16, 8, 3, 7, 9, 11, 1, 2, 22};
  for (int i = 0; i < 10; i++) {
    insert_node(&root_ptr, values[i]);
  }

  printf("Inorder traversal\n");
  inorder(root_ptr);

  printf("\nPreorder traversal\n");
  preorder(root_ptr);

  printf("\nPostorder traversal\n");
  postorder(root_ptr);

  return 0;
}

void insert_node(node_t **tree_ptr, int value) {
  if (*tree_ptr == NULL) {
    *tree_ptr = malloc(sizeof(node_t));
    if (tree_ptr == NULL) {
      printf("Unable to allocate memory\n");
      exit(-1);
    }
    (*tree_ptr)->data = value;
    (*tree_ptr)->left = NULL;
    (*tree_ptr)->right = NULL;
    return;
  }
  if (value < (*tree_ptr)->data) {
    insert_node(&((*tree_ptr)->left), value);
  } else if (value > (*tree_ptr)->data) {
    insert_node(&((*tree_ptr)->right), value);
  }
}

void inorder(node_t *tree_ptr) {
  if (tree_ptr != NULL) {
    inorder(tree_ptr->left);
    printf("%2d ", tree_ptr->data);
    inorder(tree_ptr->right);
  }
}

void preorder(node_t *tree_ptr) {
  if (tree_ptr != NULL) {
    printf("%2d ", tree_ptr->data);
    preorder(tree_ptr->left);
    preorder(tree_ptr->right);
  }
}

void postorder(node_t *tree_ptr) {
  if (tree_ptr != NULL) {
    postorder(tree_ptr->left);
    postorder(tree_ptr->right);
    printf("%2d ", tree_ptr->data);
  }
}

Η συνάρτηση insert_node() είναι αναδρομική και η κλήση της γίνεται με όρισμα που περνά στην παράμετρο tree_ptr, έναν δείκτη προς τη ρίζα. Η συνάρτηση καλεί τον εαυτό της μέχρι να βρεθεί σε κάποιο NULL φύλλο του δένδρου, «στρίβοντας» σε κάθε κόμβο του δένδρου είτε αριστερά είτε δεξιά ανάλογα με την τιμή του κόμβου και το όρισμα value. Όταν εντοπιστεί ένα NULL φύλλο του δένδρου η συνάρτηση δεσμεύει μνήμη για έναν νέο κόμβο με τιμή value και αριστερό παιδί και δεξί παιδί δείκτες προς τη δομή node_t με τιμές NULL. Παρατηρήστε ότι η insert_node() χρησιμοποιεί ως παράμετρο tree_ptr έναν διπλό δείκτη προς node_t διότι θα πρέπει να μπορεί να αλλάξει την τιμή του ορίσματος που περνά στο tree_ptr.
Η συνάρτηση inorder() διασχίζει το δένδρο πραγματοποιώντας πρώτα επίσκεψη στο αριστερό υποδένδρο, μετά στον τρέχοντα κόμβο και μετά στο δεξί υποδένδρο (LVR = Left Value Right). Η συνάρτηση πραγματοποιεί τη λεγόμενη ενδό-διατεταγμένη διάσχιση του δυαδικού δένδρου αναζήτησης που εμφανίζει τις τιμές των κόμβων του σε αύξουσα σειρά.
Η συνάρτηση preorder() διασχίζει το δένδρο πραγματοποιώντας πρώτα επίσκεψη στον τρέχοντα κόμβο, μετά στο αριστερό υποδένδρο, και μετά στο δεξί υποδένδρο (VLR = Value Left Right). Ο τρόπος αυτός διάσχισης του δένδρου ονομάζεται προ-διατεταγμένη διάσχιση και μπορεί να χρησιμοποιηθεί για την αντιγραφή ενός δυαδικού δένδρου.
Η συνάρτηση postorder() διασχίζει το δένδρο πραγματοποιώντας πρώτα επίσκεψη στον τρέχοντα κόμβο, μετά στο αριστερό υποδένδρο, και μετά στο δεξί υποδένδρο (LRV = Left Right Value). Η διάσχιση του δένδρου με αυτόν τον τρόπο ονομάζεται μετά-διατεταγμένη διάσχιση και μια χρήση της είναι στη διαγραφή του δυαδικού δένδρου χωρίς να προκαλούνται διαρροές μνήμης.

Η εκτέλεση του κώδικα δημιουργεί το δυαδικό δένδρο του Σχήματος 10.6.

Σχήμα 10.6:Το δυαδικό δένδρο αναζήτησης που δημιουργεί η εισαγωγή στη σειρά των τιμών 5, 16, 8, 3, 7, 9, 11, 1, 2, 22.

Η έξοδος που παράγεται κατά την εκτέλεση του κώδικα είναι η ακόλουθη:

Inorder traversal
 1   2   3   5   7   8   9   11  16  22

Preorder traversal
 5   3   1   2   16  8   7   9   11  22

Postorder traversal
 2   1   3   7   11  9   8   22  16   5

10.6 Ασκήσεις

Άσκηση 1
Τροποποιήστε την υλοποίηση της στοίβας της παραγράφου 10.3 έτσι ώστε η χωρητικότητα της στοίβας να διπλασιάζεται αυτόματα όταν γεμίζει.

Άσκηση 2
Γράψτε μια υλοποίηση ουράς που να περιέχει στοιχεία πελατών μιας υποθετικής τράπεζας. Για κάθε πελάτη να διατηρείται ένα αναγνωριστικό που τον ταυτοποιεί (id) και το όνομά του (name). Η ουρά να υποστηρίζει τις εξής λειτουργίες: αρχικοποίηση ουράς init(), εισαγωγή στο πίσω άκρο της ουράς enqueue(), εξαγωγή από το εμπρός άκρο της ουράς dequeue(), εμφάνιση περιεχομένων ουράς print(), επιστροφή πλήθους στοιχείων ουράς size(). Δοκιμάστε την ουρά πραγματοποιώντας εισαγωγές και εξαγωγές πελατών.

Άσκηση 3
Συμπληρώστε στην υλοποίηση της απλά συνδεδεμένης λίστας της παραγράφου 10.4 τις λειτουργίες εύρεσης κόμβου της λίστας με βάση τη θέση του search_by_index() και της εύρεσης κόμβου με βάση το αναγνωριστικό φοιτητή search_by_id().

Άσκηση 4
Συμπληρώστε την υλοποίηση του δυαδικού δένδρου αναζήτησης της παραγράφου 10.5 έτσι ώστε να πραγματοποιεί επιπλέον τις εξής λειτουργίες:

εύρεση κόμβου στο δένδρο search()
διαγραφή κόμβου από το δένδρο remove().

Tom Copeland. Manage C data using the GLib collections. https://developer.ibm.com/tutorials/l-glib/. Accessed: 2023-06-01. 2005. ↩
Robert Sedgewick. Algorithms in C, Part1-Part5 (3rd edition). Addison-Wesley Professional, 2001. ↩
Kyle Loudon. Mastering Algorithms with C: Useful Techniques from Sorting to Encryption. O’Reilly Media, 1999. ↩
Nell Dale και Henry M Walker. Abstract data types: specifications, implementations, and applications. Jones & Bartlett Learning, 1996. ↩