ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ Τμήμα Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών Προγραμματιστικές Τεχνικές http://www.softlab.ntua.gr/~nickie/Courses/progtech/

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

ΠΡΟΣΟΧΗ: Από τις έξι (6) ασκήσεις αυτής της τρίτης σειράς, επιλέξτε και επιδείξτε μόνο τέσσερις (4). Οι ασκήσεις που θα επιλέξετε πρέπει να επιδειχθούν μέχρι το τέλος του εξαμήνου.

1. Εφαρμογή συνάρτησης στα στοιχεία συνδεδεμένης λίστας

α. Γράψτε μια συνάρτηση incList που να δέχεται ως παράμετρο μια απλά συνδεδεμένη λίστα ακεραίων αριθμών L και να παράγει ως αποτέλεσμα μια άλλη λίστα ίσου μήκους, της οποίας κάθε στοιχείο να είναι κατά ένα μεγαλύτερο από το αντίστοιχο στοιχείο της L.

Παράδειγμα:

L          : [1, 2, 3, 4, 5]
incList(L) : [2, 3, 4, 5, 6]

β. Γράψτε μια συνάρτηση mapList που να γενικεύει την προηγούμενη, εφαρμόζοντας μια αυθαίρετη συνάρτηση f πάνω στα στοιχεία της λίστας L. Η συνάρτηση f θα πρέπει να περνά ως παράμετρος της mapList.

Παράδειγμα:

int twice (int x) { return 2*x; }

L                 : [1, 2, 3, 4, 5]
mapList(L, twice) : [2, 4, 6, 8, 10]

γ. Γράψτε ένα πρόγραμμα που να επιδεικνύει τις συναρτήσεις incList και mapList, εφαρμόζοντας αυτές σε κατάλληλα δεδομένα της αρεσκείας σας.

2. Φωλιασμένες και επίπεδες λίστες

α. Υλοποιήστε στη γλώσσα C τον τύπο NestedList των φωλιασμένων λιστών ακεραίων αριθμών. Τα στοιχεία μιας συνδεδεμένης λίστας τύπου NestedList μπορούν να είναι είτε ακέραιοι αριθμοί, είτε άλλες λίστες του ίδιου τύπου.

Παράδειγμα:

L          : [7, [1, 42, 3], 6, [12, [2, 7], 14]]

β. Γράψτε μια συνάρτηση flatten που να δέχεται ως παράμετρο μια φωλιασμένη λίστα ακεραίων αριθμών L και να επιστρέφει μια "επίπεδη" λίστα, που να περιέχει τα ίδια στοιχεία με την L και με την ίδια σειρά.

Παράδειγμα:

flatten(L) : [7, 1, 42, 3, 6, 12, 2, 7, 14]

γ. Γράψτε ένα πρόγραμμα που να επιδεικνύει τη συνάρτηση flatten, εφαρμόζοντάς τη σε κατάλληλα δεδομένα της αρεσκείας σας.

3. Εναλλαγή στοιχείων από αρχή και τέλος ακολουθίας

Γράψτε ένα πρόγραμμα που να διαβάζει από ένα αρχείο INFILE μια ακολουθία ακεραίων αριθμών, της οποίας το μήκος δεν είναι γνωστό. Στη συνέχεια, να τυπώνει στο αρχείο OUTFILE την ίδια ακολουθία εναλλάσσοντας τα στοιχεία της από την αρχή και από το τέλος. Δηλαδή, πρώτα πρέπει να τυπώνεται ο πρώτος ακέραιος, στη συνέχεια ο τελευταίος, έπειτα ο δεύτερος, στη συνέχεια ο προτελευταίος, κ.ο.κ.

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

4. Έλεγχος δένδρου AVL

α. Γράψτε μια συνάρτηση isAVL που να δέχεται ως παράμετρο ένα δυαδικό δένδρο t και να ελέγχει αν πρόκειται για δένδρο AVL. Η συνάρτηση αυτή θα πρέπει να επιστρέφει ένα (1) αν το δένδρο είναι AVL και μηδέν (0) διαφορετικά.

Σημείωση: Ένα δυαδικό δένδρο ονομάζεται δένδρο AVL αν κάθε κόμβος του διαθέτει τις παρακάτω τρεις ιδιότητες:

• Η τιμή που περιέχεται στον κόμβο δεν είναι μικρότερη από κάποια τιμή που περιέχεται στο αριστερό του υποδένδρο.
• Η τιμή που περιέχεται στον κόμβο δεν είναι μεγαλύτερη από κάποια τιμή που περιέχεται στο δεξιό του υποδένδρο.
• Το ύψος των δύο υποδένδρων του κόμβου διαφέρει το πολύ κατά ένα.

β. Γράψτε ένα πρόγραμμα που να επιδεικνύει τη συνάρτηση isAVL, εφαρμόζοντάς τη σε κατάλληλα δεδομένα της αρεσκείας σας.

5. Συνδεδεμένος γράφος

α. Γράψτε μια συνάρτηση isConnected που να δέχεται ως παράμετρο ένα μη κατευθυνόμενο γράφο g και να ελέγχει αν αυτός είναι συνδεδεμένος.

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

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

β. Γράψτε ένα πρόγραμμα που να επιδεικνύει τη συνάρτηση isConnected, εφαρμόζοντάς τη σε κατάλληλα δεδομένα της αρεσκείας σας.

6. Κυκλικός γράφος

α. Γράψτε μια συνάρτηση hasCycle που να δέχεται ως παράμετρο έναν κατευθυνόμενο γράφο g και να ελέγχει αν αυτός περιέχει κύκλο.

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

Ο γράφος g θα δίνεται σε μορφή πίνακα διπλανών κορυφών. Ο πίνακας αυτός θα είναι δύο διαστάσεων και θα περιέχει ένα στοιχείο για κάθε ζεύγος κόμβων του γράφου. Το στοιχείο αυτό θα έχει την τιμή true (1) αν υπάρχει ακμή με κατεύθυνση από τον πρώτο κόμβο προς το δεύτερο, διαφορετικά false (0).

β. Γράψτε ένα πρόγραμμα που να επιδεικνύει τη συνάρτηση hasCycle, εφαρμόζοντάς τη σε κατάλληλα δεδομένα της αρεσκείας σας.