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

3η Σειρά Ασκήσεων

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

• Με το ηλεκτρονικό ταχυδρομείο, στη διεύθυνση του διδάσκοντα (nickie@softlab.ntua.gr). Παρακαλώ, επισυνάψτε όλα τα αρχεία κώδικα (*.c, *.h) και μόνο αυτά σε ένα μόνο μήνυμα, γράψτε "LOG102, Exercise 3" στο θέμα (subject) του μηνύματος και μην ξεχάσετε να γράψετε μέσα στο μήνυμα το ονοματεπώνυμό σας.
• Με δισκέττα στο διδάσκοντα, πριν ή μετά το μάθημα.

Άσκηση 1 (50%)

Έστω ο τύπος της απλά συνδεδεμένης λίστας ακεραίων αριθμών που ορίζεται παρακάτω:

   typedef struct node_tag {
      int data;
      struct node_tag * next;
   } node, * list;

Ζητείται να υλοποιηθούν οι ακόλουθες σταθερές και συναρτήσεις C:

Προσοχή: Οι υλοποιήσεις των listSort και listReverse δεν πρέπει να μετακινούν τις τιμές των ακεραίων του πεδίου data της λίστας, αλλά τους συνδέσμους που περιέχονται στο πεδίο next.

Να ελεγχθεί ότι η υλοποίηση λειτουργεί σωστά εκτελώντας το παρακάτω πρόγραμμα:

   int main ()
   {
      const int x [] = { 10, 4, 50, 42, 9, 23, 3, 26, 17, 26, 16 };
      list l = listEmpty;
      int i;

      for (i = 0; i < sizeof(x) / sizeof(int); i++)
         listInsert(&l, x[i]);

      printf("Unsorted:\t"); listPrint(l); printf("\n");
      listSort(&l);
      printf("Ascending:\t"); listPrint(l); printf("\n");
      listReverse(&l);
      printf("Descending:\t"); listPrint(l); printf("\n");

      return 0;
   }

το οποίο πρέπει να εκτυπώνει τα ακόλουθα αποτελέσματα:

Unsorted:       16, 26, 17, 26, 3, 23, 9, 42, 50, 4, 10
Ascending:      3, 4, 9, 10, 16, 17, 23, 26, 26, 42, 50
Descending:     50, 42, 26, 26, 23, 17, 16, 10, 9, 4, 3

Άσκηση 2 (50%)

Έστω ο τύπος tree των δυαδικών δένδρων, οι κόμβοι των οποίων περιέχουν ακέραιους αριθμούς. Να υλοποιηθεί σε C η συνάρτηση treeSort με την ακόλουθη επικεφαλίδα:

   void treeSort (tree t); 

Η συνάρτηση αυτή θα πρέπει να μετασχηματίζει επί τόπου ένα δένδρο σε ένα νέο δένδρο της ίδιας δομής, μετακινώντας τα δεδομένα των κόμβων του. Το νέο δένδρο θα πρέπει να είναι στοιχειωδώς ταξινομημένο, δηλαδή θα πρέπει να διαθέτει την εξής ιδιότητα:

Κάθε κόμβος περιέχει τιμή μικρότερη ή ίση των τιμών των κόμβων των υποδένδρων του.

Να ελέγξετε τη σωστή λειτουργία της συνάρτησης με το ακόλουθο πρόγραμμα επίδειξης:

   int main ()
   {
      tree t =
        treeMake(17,
          treeMake(4,
            treeMake(9,
              treeMake(42, treeEmpty, treeEmpty),
              treeEmpty
            ),
            treeMake(26,
              treeMake(50, treeEmpty, treeEmpty),
              treeMake(10, treeEmpty, treeEmpty)
            )
          ),
          treeMake(26,
            treeMake(3,
              treeEmpty,
              treeMake(16, treeEmpty, treeEmpty)
            ),
            treeMake(23, treeEmpty, treeEmpty)
          )
        );
    
      printf("Before:\t"); treePrint(t); printf("\n");
      treeSort(t);
      printf("After:\t"); treePrint(t); printf("\n");
      return 0;
   }

Δυνατά αποτελέσματα αυτού του προγράμματος δίνονται παρακάτω.

Before: 17 (4 (9 (42 | ) | 26 (50 | 10)) | 26 (3 ( | 16) | 23))
After:  3 (4 (9 (42 | ) | 10 (50 | 26)) | 16 (17 ( | 26) | 23))

Το αρχικό και το μετασχηματισμένο δένδρο του παραπάνω παραδείγματος φαίνονται στο σχήμα που ακολουθεί: