ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχ. και Μηχ. Υπολογιστών

ΛΟΓ 102: Τεχνολογία Λογισμικού Ι
http://www.softlab.ntua.gr/~nickie/TUC/log102/

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

Ημερομηνία παράδοσης: Τρίτη 16 Μαΐου 2000
Ποσοστό επί της συνολικής βαθμολογίας:

10%

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


Άσκηση 1 (50%)

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

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

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

const list listEmpty;
Η κενή λίστα.
(5%)
void listInsert (list * l, int i);
Εισάγει το στοιχείο i στη λίστα l τοποθετώντας το στην αρχή της λίστας.
(5%)
void listPrint (list l);
Εκτυπώνει μια απλά συνδεδεμένη λίστα.
(10%)
void listSort (list * l);
Ταξινομεί επί τόπου την απλά συνδεδεμένη λίστα l κατ' αύξουσα σειρά.
(15%)
void listReverse (list * l);
Αντιστρέφει επί τόπου την απλά συνδεδεμένη λίστα l.
(15%)

Προσοχή: Οι υλοποιήσεις των 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))

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


Νίκος Παπασπύρου (nickie@softlab.ntua.gr). 17/5/2000 .