ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Τμήμα Ηλεκτρονικών Μηχ. και Μηχ. Υπολογιστών ΛΟΓ 102: Τεχνολογία Λογισμικού Ι http://www.softlab.ntua.gr/~nickie/TUC/log102/

3η Σειρά Ασκήσεων
Υποδείξεις

Άσκηση 1

Η υλοποίηση της σταθεράς listEmpty καθώς και της συνάρτησης listInsert είναι απλές και έχουν περιγραφεί αρκετές φορές στις παραδόσεις. Το ίδιο ισχύει και για την υλοποίηση της συνάρτησης listPrint, η οποία μπορεί να γίνει επαναληπτικά ή αναδρομικά.

Ένας απλός αλγόριθμος που μπορεί να χρησιμοποιηθεί για την υλοποίηση της listSort είναι αυτός της ταξινόμησης με επιλογή, που περιγράφεται παρακάτω:

• όσο η λίστα που πρέπει να ταξινομηθεί περιέχει στοιχεία
  • βρες το μικρότερο από αυτά
  • μετάφερέ το στην αρχή της λίστας
  • συνέχισε την ταξινόμηση για τα υπόλοιπα στοιχεία της λίστας

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

Άσκηση 2

Ο κόμβος του δυαδικού δένδρου μπορεί να παρασταθεί με μια δομή της μορφής:

   typedef struct node_tag {
      int data;
      struct node_tag * left;
      struct node_tag * right;
   } node, * tree;

Η υλοποίηση της συνάρτησης treeSort πρέπει να εξασφαλίζει ότι η ελάχιστη τιμή κάθε υποδένδρου βρίσκεται στη ρίζα του. Για το λόγο αυτό, είναι ευκολότερο η υλοποίηση να να είναι αναδρομική. Ένας απλός αλγόριθμος είναι ο ακόλουθος:

• βρες την ελάχιστη τιμή του δένδρου
• αντάλλαξέ την με την τιμή της ρίζας
• επανάλαβε το ίδιο για το αριστερό και το δεξί υποδένδρο

Φυσικά υπάρχουν και πολλοί άλλοι αλγόριθμοι (αναδρομικοί ή επαναληπτικοί) που οδηγούν σε σωστά αποτελέσματα.

Προκειμένου να ελέγξετε τη σωστή λειτουργία της treeSort, θα χρειαστεί να υλοποιήσετε τη σταθερά treeEmpty και τις συναρτήσεις treeMake και treePrint, που χρησιμοποιούνται στο κυρίως πρόγραμμα της εκφώνησης.

Η υλοποίηση των treeEmpty και treeMake είναι εξαιρετικά απλή και δίνεται παρακάτω:

   const tree treeEmpty = NULL;

   tree treeMake(int i, tree l, tree r)
   {
      node * n = (node *) malloc(sizeof(node));

      if (n != NULL) {
         n->data = i;
         n->left = l;
         n->right = r;
      }
      return n;
   }

Η υλοποίηση της treePrint μπορεί να γίνει πολύ εύκολα με αναδρομικό τρόπο. Το μοναδικό σημείο που αξίζει προσοχής είναι η σωστή εκτύπωση των παρενθέσεων. Χρησιμοποιήστε για υπόδειγμα τα αποτελέσματα της εκτύπωσης που δίνονται στο τέλος της εκφώνησης.