Return to ΘΕΩΡΙΑ ΑΕΠΠ

5.Β Δυναμικές Δομές Δεδομένων (Λίστες-Δένδρα-Γράφοι)

AΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ

ΘΕΩΡΙΑ

ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ – ΛΙΣΤΕΣ ΔΕΝΔΡΑ ΓΡΑΦΟΙ 

Οι δομές δεδομένων είναι το κύριο αντικείμενο αυτού του κεφαλαίου. Το υλικό έχει αντληθεί από το νέο βιβλίο (συμπληρωματικό υλικό) Πληροφορική του μαθήματος της Ενότητας 1.3 -Άλλες δομές δεδομένων.

ΛίστεςΔένδρα

  • Άσκηση 1

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

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

    Σχήμα Α: Αναπαράσταση γραμμικής λίστας

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

    Σχήμα Α1: Αναπαράσταση απλά συνδεδεμένης λίστας 7 κόμβων

    Σχηματιζόμενη λέξη: ΜΠΑΛΟΝΙ

    Νέα λέξη: ΜΠΑΛΚΟΝΙ

    Σχήμα Β1: Αναπαράσταση απλά συνδεδεμένης λίστας 9 κόμβων

    Σχηματιζόμενη λέξη: ΠΡΟΣΚΛΗΣΗ

    Νέα λέξη: ΠΡΟΚΛΗΣΗ

    Σχήμα Γ1: Απλά συνδεδεμένη λίστα 7 κόμβων

    Σχηματιζόμενη λίστα ταξινομημένων αριθμών: 12, 19, 25, 47, 65, 73, 91

    Νέα λίστα (διατηρείται η ταξινόμηση): 12, 17, 19, 25, 65, 73, 91, 93

    Σχήμα Δ1: Αναπαράσταση γραμμικής λίστας

    Σχηματιζόμενη λέξη: ΖΑΡΙ

    Νέα λέξη: ΡΙΖΑ

  • Οι κόμβοι καθεμιάς από τις λίστες που ακολουθούν συνδέονται με τρόπο ώστε να σχηματίζουν μια λέξη. Η αναπαράσταση/απεικόνιση των κόμβων κάθε λίστας έχει ως εξής:
    Κάθε κόμβος καταλαμβάνει δύο συνεχόμενες θέσεις στη μνήμη με την πρώτη θέση να περιέχει ένα χαρακτήρα (της σχηματιζόμενης λέξης) και την δεύτερη να “δείχνει” την διεύθυνση του επόμενου κόμβου. Οι διευθύνσεις των κόμβων υποδεικνύονται από τις τιμές των δεικτών του πίνακα.

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

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

    Ζητείται:

    α) να σχεδιάσετε την αρχική λίστα κάθε περίπτωσης.

    β) να εισάγετε τον χαρακτήρα ή τους χαρακτήρες που απουσιάζουν σε κάθε λίστα ώστε να σχηματιστεί η νέα λέξη που κάθε φορά δίνεται και να αναπαραστήσετε εκ νέου την λίστα στη μνήμη του υπολογιστή προχωρώντας στις κατάλληλες κάθε φορά αλλαγές στο σχήμα που δίνεται.

    ……… 18 19 20 ……… 43 44 45 46 47 48 … 65 66 ……… 81 82 83 84 85 ……… 97 98 99 ………
    ……… Ε 65 ……… Ο 84 Α ● Φ 43 ……… Ρ 97 ……… Ι 46 ………

    Σχήμα Α: Αναπαράσταση γραμμικής λίστας

    Σχηματιζόμενη λέξη: ……………..

    Δείκτης κεφαλή = 18

    Νέα λέξη: ΕΥΦΟΡΙΑ

    ……… 43 44 45 46 47 48 ……… 65 66 ……… 81 82 83 84 85 ……… 97 98 99 ………
    ……… Α ● Μ 43 Η 45 ……… ……… ……… Ν 47 ………

    Σχήμα Β: Αναπαράσταση γραμμικής λίστας

    Σχηματιζόμενη λέξη: ……………..

    Δείκτης κεφαλή = 97

    Νέα λέξη: ΝΟΗΜΑ

    ……… 18 19 20 ……… 43 44 45 46 47 48 … 65 66 ……… 81 82 83 84 85 ……… 97 98 99 ………
    ……… ……… Δ 84 Ω ● ……… Ν 65 Ε 82 ……… ………

    Σχήμα Γ: Αναπαράσταση γραμμικής λίστας

    Σχηματιζόμενη λέξη: ……………..

    Δείκτης κεφαλή = 45

    Νέα λέξη: ΓΔΕΡΝΩ

  • Πρόταση

    Ένα δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί.

    Άσκηση 1

    Να τοποθετηθούν με την σειρά που δίνονται σ’ ένα δυαδικό δένδρο ακολουθώντας τον κανόνα που διατυπώθηκε, τα δεδομένα που δίνονται σε καθεμία από τις περιπτώσεις.

    Δεδομένα οι αριθμοί: -9, -5, -1, 0, 12, 14, 21, 33, 45, 58.

    Δεδομένα οι αριθμοί: 45, 21, 78, 19, 32, 81, 31, 79, 101, 31

  • Πρόταση

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

    Άσκηση 2

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

    Δεδομένα οι αριθμοί: 0, -19, 19, 25, -25, -13,13, 15,-1,-20

    Δεδομένα οι αριθμοί: 21, -5, -9, -1, 14, 58, 0, 12, 33, 45

    Δεδομένα οι χαρακτήρες: Ζ, Α,  Ω, Ι, Κ, Μ, Β, Π, Γ

    Δεδομένα τα ονόματα: ΔΙΟΜΗΔΗΣ, ΔΗΜΟΣ, ΔΗΜΗΤΡΗΣ, ΔΙΟΓΕΝΗΣ, ΔΗΜΟΣΘΕΝΗΣ, ΔΗΜΗΤΡΑ, ΔΙΟΝΥΣΗΣ

  • Άσκηση 3

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

    Δεδομένα οι αριθμοί: 19, 21, 31, 32, 45, 78, 79, 81, 101

    Αναλυτική παρουσίαση λύσης

    Δεδομένα οι αριθμοί: 0, 5, 11, 18, 27, 37, 48, 58, 67, 75, 82, 88, 93, 97, 100

    -1, 0, 45, 98, 120, 202, 403, 607, 1000, 1048

    Α, Δ, Ο, Π, Σ, Τ, Φ,Ψ, Ω

    Al, C, Ca, Cl, Cu, F, Fe, H, Hg, I, K, Mg, N, Na, O, P, Pb, S, Si, Ζn

  • Άσκηση 4

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

    Βήμα 1: Κάθε κόμβος αριθμείται από αριστερά προς δεξιά με την αρίθμηση να ξεκινά από την ρίζα στην οποία και αντιστοιχεί ο αριθμός 1.

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

    Επίλυση

    Το δυαδικό δένδρο μετά την αρίθμηση των κόμβων του.

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

      1 2
    1 2 3
    2 4 5
    3 0 6
    4 0 0
    5 7 0
    6 8 9
    7 0 0
    8 0 0
    9 0 0
      1 2
    1 21 78
    2 19 32
    3 81
    4
    5 31
    6 79 101
    7
    8
    9

  • Άσκηση 5

    Δίνονται οι παρακάτω πίνακες αναπαράστασης δυαδικών δένδρων στη μνήμη του υπολογιστή. Κάθε γραμμή του δισδιάστατου  πίνακα αντιστοιχεί και σε ένα κόμβου του δένδρου. Ο πίνακας αποτελείται από 4 στήλες που έχουν ως εξής: Οι στήλες 1, 2 δείχνουν για κάθε κόμβο τον κόμβο που βρίσκεται αριστερά του (αριστερό παιδί) και τον κόμβο που βρίσκεται δεξιά του(δεξί του παιδί). Οι στήλες 3 και 4 (όπου υπάρχουν) έχουν ως περιεχόμενο τα δεδομένα των αντίστοιχων κόμβων των στηλών 1 και 2.  

    Ζητείται να σχεδιάσετε τα δυαδικά δένδρα που αντιστοιχούν στους δοσμένους πίνακες.

    Πίνακας αναπαράστασης δυαδικού δένδρου στη μνήμη του υπολογιστή. Ρίζα ο αριθμός 0.

      1 2 3 4
    1 2 3 -7 18
    2 4 5 -10 -5
    3 6 7 14 20
    4 0 0  
    5 0 8   -3
    6 0 9   15
    7 0 10   71
    8 0 0    
    9 0 0    


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

    Το δυαδικό δένδρο με τους κόμβους συμπληρωμένους με τα δεδομένα των στηλών 3 και 4.

     

    Πίνακας αναπαράστασης δυαδικού δένδρου στη μνήμη του υπολογιστή. 

      1 2
    1 2 3
    2 7 0
    3 4 5
    4 6 0
    5 9 0
    6 0 0
    7 0 8
    8 10 0
    9 0 11

    Πίνακας αναπαράστασης δυαδικού δένδρου στη μνήμη του υπολογιστή.

      1 2
    1 2 3
    2 4 5
    3 6 7
    4 8 9
    5 10 0
    6 0 0
    7 0 0
    8 0 0
    9 0 0

    Πίνακας αναπαράστασης δυαδικού δένδρου στη μνήμη του υπολογιστή.

      1 2
    1 2 3
    2 4 5
    3 6 7
    4 8 9
    5 10 0
    6 0 0
    7 0 0
    8 0 0
    9 0 0