Τα δεδομένα αποθηκεύονται σε δομές δεδομένων, και μαζί με τους αλγορίθμους φτιάχνουν τα προγράμματα. Το κεφάλαιο εξετάζει πίνακες, στοίβα, ουρά, σειριακή αναζήτηση, ταξινόμηση φυσαλίδας, αναδρομή και, πιο σύντομα, λίστες, δένδρα και γράφους.
Γ΄ Λυκείου · Πληροφορική · 15 λεπτά
Το μάθημα είναι στο σχολικό βιβλίο. Δεν το αντιγράφουμε εδώ. Άνοιξε το επίσημο
κεφάλαιο και γύρνα για την εξάσκηση.
Η σύνοψη, οι όροι και οι ασκήσεις γράφτηκαν με τη βοήθεια τεχνητής νοημοσύνης από το
σχολικό βιβλίο και μπορεί να έχουν λάθη. Πηγή είναι πάντα το βιβλίο: ό,τι σου φαίνεται περίεργο,
έλεγξέ το εκεί. Βρήκες λάθος; Γράψε μας στο aporia@signmak.com.
Σχεδιάγραμμα
Δική μας σύνοψη της ενότητας, για επανάληψη. Πηγή είναι πάντα το βιβλίο.
Τι έγινε
Τα δεδομένα είναι ακατέργαστα γεγονότα· με επεξεργασία και συσχέτιση δίνουν πληροφορία, και ο αλγόριθμος είναι το μέσο γι' αυτό.
Δομή δεδομένων είναι σύνολο αποθηκευμένων δεδομένων μαζί με λειτουργίες πάνω τους: προσπέλαση, εισαγωγή, διαγραφή, αναζήτηση, ταξινόμηση, αντιγραφή, συγχώνευση, διαχωρισμός.
Ο Wirth διατύπωσε το 1976 τη σχέση «Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα»· δομή και αλγόριθμος είναι αδιάσπαστα.
Οι δομές είναι στατικές (σταθερό μέγεθος, συνεχόμενες θέσεις μνήμης, όπως οι πίνακες) ή δυναμικές (μεγαλώνουν και μικραίνουν με δυναμική παραχώρηση μνήμης).
Ο πίνακας κρατά στοιχεία ίδιου τύπου και τα βρίσκουμε με δείκτες· μπορεί να είναι μονοδιάστατος, δισδιάστατος ή ν-διάστατος.
Η στοίβα (LIFO, ώθηση και απώθηση, υπερχείλιση και υποχείλιση) και η ουρά (FIFO, εισαγωγή και εξαγωγή) υλοποιούνται με μονοδιάστατο πίνακα.
Η σειριακή αναζήτηση εξετάζει τα στοιχεία ένα ένα· η ταξινόμηση φυσαλίδας συγκρίνει και ανταλλάσσει γειτονικά στοιχεία, απλούστατη αλλά και η πιο αργή μέθοδος.
Αναδρομή: μια διαδικασία καλεί τον εαυτό της (παραγοντικό, μκδ του Ευκλείδη, Fibonacci). Λίστες, δένδρα και γράφοι χρησιμοποιούν δείκτες σε μη συνεχόμενες θέσεις μνήμης.
Πρόσωπα
Wirth
σχεδίασε την Pascal, διατύπωσε τη σχέση του 1976
Ευκλείδης
ο αλγόριθμός του βρίσκει τον μκδ
Fibonacci
δίνει το όνομά του στην ακολουθία 0, 1, 1, 2, 3, 5...
Η στοίβα λειτουργεί με τη μέθοδο LIFO: βγαίνει πρώτο το στοιχείο που μπήκε τελευταίο, από την κορυφή (ώθηση και απώθηση). Η ουρά λειτουργεί με FIFO: βγαίνει πρώτο όποιο μπήκε πρώτο, με εισαγωγή στο πίσω άκρο και εξαγωγή από το εμπρός, άρα χρειάζεται δύο δείκτες (front και rear).
Πότε αξίζει η σειριακή αναζήτηση;
Είναι η πιο απλή αλλά η λιγότερο αποτελεσματική μέθοδος. Δικαιολογείται όταν ο πίνακας δεν είναι ταξινομημένος, όταν είναι μικρός ή όταν η αναζήτηση σε αυτόν γίνεται σπάνια.
Είναι καλύτερη η αναδρομή από την επανάληψη;
Η αναδρομή συχνά κάνει το πρόγραμμα πιο απλό στη γραφή, όμως κάθε κλήση έχει χρονικό κόστος. Ανάμεσα σε ένα απλό επαναληπτικό και ένα αναδρομικό πρόγραμμα το βιβλίο προτιμά το επαναληπτικό, ιδίως όταν ο χρόνος απόκρισης είναι κρίσιμος.
Ανοίγει το μενού κοινοποίησης του κινητού σου. Αν δεν υπάρχει, αντιγράφεται ο σύνδεσμος.
Νέα από το aporia.gr Νέες ενότητες και ό,τι βρίσκουμε στα θέματα των Πανελληνίων, στη σελίδα μας στο Facebook.