Εισαγωγή

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

Στο κεφάλαιο αυτό παρουσιάζονται οι έννοιες του πίνακα καθώς και οι βασικοί τρόποι επεξεργασίας τους από τη ΓΛΩΣΣΑ.

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

Διδακτικοί στόχοι

Να είναι σε θέση ο μαθητής:

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

Προερωτήσεις

• Πώς μπορούν να αποθηκευτούν πολλά παρόμοια δεδομένα στον υπολογιστή, για παράδειγμα τα ονόματα όλων των μαθητών μίας τάξης;
• Για ποιο λόγο χρησιμοποιούνται στην άλγεβρα οι μεταβλητές με δείκτες;
• Σε ποιες περιπτώσεις χρειάζεται η ταξινόμηση κάποιων δεδομένων;
• Είναι εύκολη η αναζήτηση ενός συγκεκριμένου δεδομένου σε μη ταξινομημένα δεδομένα;

Πολλά από τα προβλήματα τα οποία παρουσιάστηκαν στα προηγούμενα κεφάλαια, απλά επεξεργάζονται μία σειρά δεδομένων.

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

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

Χρησιμοποιώντας λοιπόν μόνο μία μεταβλητή, τη μεταβλητή Θερμοκρασία, το πρόβλημα λύνεται πολύ απλά και το αντίστοιχο πρόγραμμα είναι σύντομο και κατανοητό.

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

Μία άλλη λύση είναι να καταχωρηθεί κάθε θερμοκρασία σε διαφορετική μεταβλητή, έτσι ώστε κάθε τιμή που εισάγεται να διατηρείται στη μνήμη και να μπορεί να συγκριθεί με τη μέση, αφού αυτή υπολογιστεί. Τότε όμως πρέπει να δημιουργηθούν 30 διαφορετικές μεταβλητές Θερμοκρασία1, Θερμοκρασία2,..., Θερμοκρασία30. Για να γραφεί το πρόγραμμα χρειάζονται τριάντα εντολές ΔΙΑΒΑΣΕ και τριάντα εντολές ΑΝ.

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

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

μόνο ένα όνομα Θερμοκρασία, που αναφέρεται και στις τριάντα διαφορετικές θερμοκρασίες.

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

Σχ. 9.1. Ο πίνακας θερμοκρασία

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

Το όνομα του πίνακα μπορεί να είναι οποιοδήποτε δεκτό όνομα της ΓΛΩΣΣΑΣ και ο δείκτης είναι μία ακέραια έκφραση, σταθερή ή μεταβλητή που περικλείεται μέσα στα σύμβολα [ και ]. Το στοιχείο Θερμοκρασία[2], εκφράζει τη θερμοκρασία της δεύτερης ημέρας, αναφέρεται στο δεύτερο στοιχείο του πίνακα Θερμοκρασία και έχει την τιμή 27.

Γενικότερα το στοιχείο Θερμοκρασία[ϊ] αναφέρεται στο i-στό στοιχείο του πίνακα.

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

Για παράδειγμα

ΜΕΤΑΒΛΗΤΕΣ
ΠΡΑΓΜΑΤΙΚΕΣ: θερμοκρασία [30]

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

Παράδειγμα 1

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

Με τη χρήση του πίνακα, όλα τα δεδομένα καταχωρούνται κάτω από το ίδιο όνομα μεταβλητής, στο παράδειγμα Θερμοκρασία. Η ανάγνωση όλων των δεδομένων απλοποιείται, αφού είναι μόνο μία εντολή, ΔΙΑΒΑΣΕ Θερμοκρασία[ί], η οποία βρίσκεται μέσα σε ένα βρόχο και επαναλαμβάνεται

όσες φορές απαιτείται όπως και ο υπολογισμός του αθροίσματος, Σύνολο <-Σύνολο + Θερμοκρασία[ϊ].

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

Παράδειγμα 2

Τα δεδομένα εισάγονται από το πληκτρολόγιο και καταχωρούνται στον πίνακα Χ.

Η μέση τιμή μ δίνεται από τον τύπο

Η τυπική απόκλιση σ δίνεται από τον τύπο

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

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

Προγραμματιστικό περιβάλλον Basic

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

Πέρα από τα πλεονεκτήματα που αναφέρθηκαν, υπάρχουν και δύο μειονεκτήματα από τη χρήση πινάκων.

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

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

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

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

Ας επιστρέψουμε στο προηγούμενο παράδειγμα.

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

Στο προηγούμενο παράδειγμα υπήρχαν 30 τιμές της θερμοκρασίας, μία για κάθε ημέρα του μήνα και για την επίλυση του χρησιμοποιήθηκε ένας πίνακας

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

Έστω ότι οι θερμοκρασίες δίνονται από τον παρακάτω πίνακα.

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

Για την επεξεργασία των θερμοκρασιών μπορεί να χρησιμοποιηθεί ένας δισδιάστατος πίνακας, στον οποίο ο πρώτος δείκτης δείχνει τη γραμμή (στο παράδειγμα την ημέρα) και ο δεύτερος τη στήλη (την πόλη). Το στοιχείο Θερμοκρασία[30,1] έχει την τιμή 27.

Στην γενική περίπτωση κάθε στοιχείο του πίνακα είναι το στοιχείο Θερμοκρασία[i,j] και αναφέρεται στη θερμοκρασία στην i γραμμή και την j στήλη, όπου το i παίρνει τιμή από 1 έως 30 και το j από 1 έως 10. Ο πίνακας Θερμοκρασία είναι ένας δισδιάστατος πίνακας 30X10.

Παράδειγμα 3

Προγραμματιστικό περιβάλλον Pascal

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

Στο προηγούμενο παράδειγμα έστω ότι έχουμε θερμοκρασίες για κάθε μία πόλη, για κάθε ημέρα αλλά και για κάθε έτος. Τότε κάθε στοιχείο χρειάζεται τρεις δείκτες. Έναν που θα δείχνει το έτος, έναν που θα δείχνει την πόλη και έναν που θα δείχνει την ημέρα. Για παράδειγμα η θερμοκρασία της πρώτης ημέρας, της πρώτης πόλης και του πρώτου έτους είναι 25 και είναι το στοιχείο Θερμοκρασία [1, 1, 1].

Παράδειγμα 4.

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

Το πρόγραμμα ουσιαστικά αποτελείται από τρία τμήματα:

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

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

Τα προγράμματα τα οποία χρησιμοποιούν πίνακες πολύ συχνά απαιτούν συγκεκριμένες επεξεργασίες στα στοιχεία του πίνακα. Οι τυπικές αυτές επεξεργασίες είναι:

• Υπολογισμός αθροισμάτων στοιχείων του πίνακα.
• Εύρεση του μέγιστου ή του ελάχιστου στοιχείου.
• Ταξινόμηση των στοιχείων του πίνακα.
• Αναζήτηση ενός στοιχείου του πίνακα.
• Συγχώνευση δύο πινάκων.

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

στο αντίστοιχο κεφάλαιο των αλγορίθμων, όπου συζητήθηκαν τα πλεονεκτήματα και τα μειονεκτήματα τους.

Συνοπτικά έχουμε:

Υπολογισμός αθροισμάτων στοιχείων του πίνακα.

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

Εύρεση του μέγιστου ή του ελάχιστου στοιχείου.

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

Ταξινόμηση των στοιχείων του πίνακα.

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

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

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

Αναζήτηση ενός στοιχείου του πίνακα.

Δύο είναι οι πλέον διαδεδομένοι αλγόριθμοι αναζήτησης:

• Η σειριακή αναζήτηση
• Η δυαδική αναζήτηση

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

Συγχώνευση δύο πινάκων.

Η συγχώνευση είναι μία από τις βασικές λειτουργίες σε πίνακες.

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

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

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

Μεταβλητή με δείκτη, Πίνακας, Στοιχείο πίνακα, Αναζήτηση, Ταξινόμηση, Συγχώνευση

1. Τι ονομάζεται πίνακας;
2. Για ποιο λόγο χρησιμοποιούνται οι πίνακες;
3. Τι μπορεί να είναι οι δείκτες των πινάκων;
4. Ποια η διαφορά του πίνακα και του στοιχείου ενός πίνακα;
5. Πού ορίζεται η διάσταση του πίνακα;
6. Τι είδους δομή είναι ο πίνακας;
7. Ποιοι πίνακες ονομάζονται μονοδιάστατοι;
8. Δώσε ένα παράδειγμα ενός τρισδιάστατου πίνακα.

9. Πού αποθηκεύονται τα στοιχεία ενός πίνακα;

10. Ποια τα μειονεκτήματα της χρήσης πινάκων;

11. Ποιες οι τυπικές επεξεργασίες πίνακα;

12. Ποιοι είναι οι πιο διαδεδομένοι αλγόριθμοι αναζήτησης; Ποιες οι διαφορές τους;

1. Κ. Αντωνακόπουλος, Turbo Pascal 6.0 Θεωρία και Πράξη, Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 1993.
2. QuickBASIC: Η εργαλειοθήκη του προγραμματιστή, Κλειδάριθμος, Αθήνα, 1991.
3. Χρ. Κοίλιας, Η QuickBasic και οι εφαρμογές της, Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 1992.
4. R. Shackelford, Introduction to Computing and Algorithms, Addison-Wesley, USA, 1998.
5. S. Leestma-L.Nyhoff, Turbo Pascal, Programming and Solving, McMillan, New York, 1990.
6. N. Wirth, Systematic Programming: An introduction, Prentice Hall, 1973.

• http://qbasic.com/

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

Επίσης στο διαδίκτυο παρουσιάζουν ενδιαφέρον ομάδες νέων (Usenet), σχετικές με τις γλώσσες προγραμματισμού.