Δυναμικές Δομές
(Λίστες, Δένδρα, Γράφοι)

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

Λίστες

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

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

Μία απλά συνδεδεμένη λίστα είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά . Κάθε κόμβος περιέχει εκτός από τα δεδομένα του και έναν δείκτη που δείχνει προς τον επόμενο κόμβο. Ο δείκτης του τελευταίου κόμβου δε δείχνει σε κάποιον κόμβο . Για να το δηλώσουμε αυτό λέμε ότι το πεδίο δείκτη του τελευταίου κόμβου έχει την τιμή NULL. Για να προσπελάσουμε τους κόμβους της λίστας χρειάζεται να γνωρίζουμε τη διεύθυνση του πρώτου κόμβου της λίστας. Η διεύθυνση αυτή αποθηκεύεται σε μία ειδική μεταβλητή που την ονομάζουμε συνήθως Κεφαλή.

Πρόσβαση στους κόμβους μιας συνδεδεμένης λίστας

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

Οι συνδεδεμένες λίστες αξιοποιούνται για την υλοποίηση της στοίβας και της ουράς, λόγω της δυνατότητάς αυξομείωσης του μεγέθους τους.

Διαφορές Λίστας σε σχέση με τον Πίνακα

Σημαντικές διαφορές μεταξύ Λίστας και πίνακα είναι οι παρακάτω:
• O πίνακας θεωρείται μια δομή τυχαίας προσπέλασης, σε αντίθεση με μια λίστα που είναι στην ουσία μια δομή ακολουθιακής ή σειριακής προσπέλασης. Για να φθάσουμε, δηλαδή, σ’ έναν κόμβο μιας λίστας πρέπει να περάσουμε από όλους τους προηγούμενους ξεκινώντας από τον πρώτο.
• O πίνακας έχει σταθερό μέγεθος, το οποίο δηλώνεται εξαρχής κατά την υλοποίηση. Αυτό γίνεται, διότι ο πίνακας είναι στατική δομή δεδομένων σε αντίθεση με τη λίστα που είναι δυ- ναμική δομή και το μέγεθός της μπορεί να μεταβάλλεται καθώς εισέρχονται νέοι κόμβοι στη λίστα ή διαγράφονται κάποιοι άλλοι.
• Oι κόμβοι της λίστας αποθηκεύονται σε μη συνεχόμενες θέσεις μνήμης σε αντιδιαστολή με τους πίνακες, όπου τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.

Πλεονεκτήματα – Μειονεκτήματα Χρήσης Λιστών

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

Μειονεκτήματα των λιστών σε σχέση με τους πίνακες:
• Η τυχαία πρόσβαση στη λίστα δεν επιτρέπεται. Είναι αδύνατο να φτάσετε στον n-οστό κόμβο μιας απλά συνδεδεμένης λίστας χωρίς πρώτα να περάσετε από όλους τους κόμβους διαδοχικά μέχρι τον συγκεκριμένο κόμβο ξεκινώντας από τον πρώτο κόμβο. Εναλλακτικά, στην περίπτωση της διπλά συνδεμένης λίστας μπορείτε να ξεκινήσετε και από τον τελευταίο κόμβο. Επομένως, δεν μπορούμε να πραγματοποιήσουμε με αποτελεσματικό τρόπο δυαδική αναζήτηση σε συνδεδεμένες λίστες.
• Οι συνδεδεμένες λίστες έχουν πολύ μεγαλύτερη επιβάρυνση από τους πίνακες, αφού οι συνδεδεμένοι κόμβοι της λίστας είναι δυναμικά κατανεμημένοι και κάθε κόμβος στη λίστα πρέπει, επιπλέον, να αποθηκεύσει έναν πρόσθετο δείκτη που θα δείχνει στον επόμενο κόμβο. Στην περίπτωση των διπλά συνδεδεμένων λιστών χρειαζόμαστε επιπλέον έναν δεύτερο δείκτη που θα δείχνει στον προηγούμενο κόμβο.

Βασικές πράξεις των συνδεδεμένων λιστών

• Εισαγωγή κόμβου στη λίστα (στην αρχή, στο τέλος της λίστας ή ενδιάμεσα).
• Διαγραφή κόμβου από τη λίστα (διαγραφή από την αρχή, το τέλος της λίστας ή ενδιάμεσα).
• Έλεγχος για το αν η λίστα είναι κενή.
• Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου.
• Διάσχιση της λίστας και προσπέλαση των στοιχείων της.

Δένδρα

Ένα δένδρο αποτελείται από κόμβους, οι οποίοι συνδέονται μεταξύ τους με ακμές. Όταν δύο κόμβοι συνδέονται μεταξύ τους με μία ακμή, τότε ονομάζουμε «γονέα» τον κόμβο από τον οποίο ξεκινάει η ακμή και «παιδί» τον κόμβο στον οποίο καταλήγει η ακμή. Ένας κόμβος μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά. Όλοι οι κόμβοι, εκτός από έναν, έχουν ακριβώς έναν γονέα. Ο κόμβος χωρίς γονέα ονομάζεται «ρίζα» και βρίσκεται στην κορυφή του δένδρου. Κόμβοι με τον ίδιο γονέα ονομάζονται «αδέλφια». Οι κόμβοι χωρίς παιδιά ονομάζονται «φύλλα».

Μπορούμε να έχουμε ένα απλό δένδρο, το οποίο να απαρτίζεται από έναν μόνο κόμβο. Αυτός ο κόμβος είναι και ρίζα του απλού αυτού δένδρου, διότι δεν έχει γονέα και φύλλο, και διότι δεν έχει παιδιά. Ένα δένδρο (είναι μία δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων με βάση τους εξής κανόνες:
• Υπάρχει ένας ξεχωριστός κόμβος που ονομάζεται ρίζα. Αυτός είναι ένας κόμβος χωρίς γονέα.
• Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c παιδί του p.
• Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή, μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο.

Δένδρο θεωρούμε και το κενό δένδρο, δηλαδή το δένδρο που δεν έχει ούτε κόμβους, ούτε ακμές.
Το κενό δένδρο είναι το μόνο δένδρο χωρίς ρίζα.

Δένδρο Απόφασης

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

Δυαδικά Δένδρα

Ένα δυαδικό δένδρο είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί. Μπορούμε, συνεπώς, να μιλάμε για αριστερό και δεξιό υποδένδρο ενός κόμβου. Προφανώς, αν ανταλλάξουμε το αριστερό με το δεξιό υποδένδρο ενός κόμβου παίρνουμε ένα διαφορετικό δένδρο.

Δυαδικά Δένδρα Αναζήτησης

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

Γράφοι

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

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

Διαφορές Γράφου και Δένδρου:

1) Ένα δένδρο μπορεί μόνο να ρέει προς μία κατεύθυνση, από τον κόμβο ρίζας σε κόμβους φύλλων ή κόμβους παιδιών.
2) Ένα δένδρο μπορεί να έχει μόνο μονόδρομες συνδέσεις – ένας κόμβος παιδιού μπορεί να έχει μόνο έναν γονέα και ένα δένδρο δεν μπορεί να έχει βρόχους ή κυκλικούς δεσμούς .

Με τους γράφους, όλοι αυτοί οι περιορισμοί δεν υπάρχουν.
1) Οι γράφοι δεν έχουν την έννοια ενός κόμβου «ρίζας». Οι κόμβοι μπορούν να συνδεθούν με οποιονδήποτε τρόπο.
2) Οι γράφοι, επίσης, δεν έχουν «μονοκατευθυντική» ροή αντ’ αυτού, μπορεί να έχουν κατεύθυνση ή να μην έχουν καμιά κατεύθυνση.

Τύποι Γράφων:

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

Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος.
Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος.

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

Σωστό / Λάθος Ερωτήσεις Θεωρίας Δυναμικών Δομών:

1. Μια διπλά συνδεδεμένη λίστα μπορούμε να τη διατρέξουμε μόνο προς μία κατευθύνση.
2. Σε μια απλά συνδεδεμένη λίστα, τα στοιχεία μπορούν να αφαιρεθούν απο παντού εκτός από το τέλος της.
3. Κάθε λίστα είναι γράφος.
4. Κάθε δένδρο είναι γράφος
5. Σε ένα δυαδικό δένδρο αναζήτησης, κάθε κόμβος-γονέας μπορεί να έχει τουλάχιστον δύο παιδιά.
6. Το φύλο ενός δένδρου είναι ο μόνος κόμβος ενός δένδρου που δεν έχει γονέα.
7. Σε ένα δένδρο, κάθε κόμβος-γονέας μπορεί να έχει οποιονδήποτε αριθμό παιδιών.
8. Οι γράφοι υποχρεωτικά έχουν ακμές με κατεύθυνση.
9. Οι λίστες και οι πίνακες είναι στατικές δομές δεδομένων.
10. Οι στοίβες και οι ουρές υλοποιούνται με λίστες.

Απαντήσεις Θεωρίας Δυναμικών Δομών:

Οι απαντήσεις για τις παραπάνω ερωτήσεις τύπου Σωστό/ Λάθος είναι οι παρακάτω:
1. Λ, 2. Λ, 3. Σ, 4. Σ, 5. Λ, 6. Λ, 7. Σ, 8. Λ, 9. Λ, 10. Σ
Αν θέλετε και άλλες ερωτήσεις τύπου Σωστού / Λάθους ή γενικότερα ερωτήσεις θεωρίας στην ύλη της πληροφορικής Γ λυκείου στο κεφάλαιο δυναμικών δομών μπορείτε να δείτε από τα τεστ, διαγωνίσματα και θεωρίες που έχουμε δημιουργήσει για να σας δώσουν την δυνατότητα να καταφέρετε υψηλό βαθμό στις πανελλαδικές εξετάσεις.

Ερωτήσεις Ανάπτυξης Θεωρίας Λίστες Δένδρα Γράφοι

Παρακάτω σας δίνουμε μερικές ερωτήσεις ανάπτυξης στη θεωρία της πληροφορικής Γ λυκείου στο κεφάλαιο του σχολικού βιβλίου για τις Λίστες Δένδρα και Γράφοι. Μπορείτε να διαβάσετε την ύλη και στη συνέχεια να απαντήσετε. Οι λύσεις στις ερωτήσεις είναι όπως θα ζητηθούν στις πανελλήνιες εξετάσεις και γράφονται στην συνέχεια κάθε ερώτησης.

1. Τι ονομάζουμε «απλά συνδεδεμένη λίστα» και τι «διπλά συνδεδεμένη»;

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

Μία λίστα ονομάζεται «διπλά συνδεδεμένη» όταν μπορούμε να τη διατρέξουμε και προς τις δύο κατευθύνσεις. Για την υλοποίηση της χρειαζόμαστε δύο δείκτες:
α) Τον δείκτη «κεφαλή» που δείχνει τον πρώτο κόμβο της λίστας.
β) Τον δείκτη «ουρά» που δείχνει τον τελευταίο κόμβο της λίστας.

2. Τι είναι το δυαδικό δένδρο αναζήτησης;

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

3. Τι είναι δένδρο, φύλο, γονέας-παιδί, ρίζα, αδέρφια;

1) Δένδρο: είναι ένα σύνολο από κόμβους οι οποίοι συνδέονται μεταξύ τους με ακμές.
2) Γονέας + Παιδί: όταν δύο κόμβοι ενώνονται μεταξύ τους με μία ακμή, γονέας είναι ο κόμβος από τον οποίο ξεκινάει η ακμή και παιδί είναι ο κόμβος στον οποίο καταλήγει η ακμή. Ένας κόμβος μπορεί να έχει κανένα, ένα η περισσότερα παιδιά. (Σ/Λ)
3) Ρίζα : είναι ο κόμβος που δεν έχει γονέα και βρίσκεται στην κορυφή του δένδρου.
4) Αδέρφια: είναι κόμβοι που έχουν τον ίδιο γονέα.
5) Φύλλα: είναι κόμβοι που δεν έχουν παιδιά.

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