Διαδικασίες

Διαδικασίες

Πίνακες Μονοδιάσταστοι

Μονοδιάστατοι Πίνακες

Τι είναι ο πίνακας γενικά :

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

Πιο αναλυτικά θα μπορούσε  να δοθεί σαν ορισμός το παρακάτω :

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

Συμβολισμός :

Στις εκφωνήσεις ένας πίνακας π.χ. 10 θέσεων συμβολίζεται Α(10).

Στη δήλωση μεταβλητών ενός προγράμματος συμβολίζεται Α[1..10].

Στο λογισμικό ‘Διερμηνευτή Γλώσσας’ στη δήλωση μεταβλητών συμβολίζεται Α[10]     

Έστω ένας πίνακας με όνομα Α δέκα θέσεων - πατήστε ΕΔΩ

Για να γεμίζουμε – διαβάσουμε, για να εμφανίσουμε και επεξεργαστούμε τιμές σε ένα πίνακα πρέπει να χρησιμοποιήσουμε μια επαναληπτική δομή. Επειδή είναι πάντα γνωστός ο αριθμός των θέσεων (κόμβων) – στοιχείων του, συνήθως επιλέγουμε την δομή ΓΙΑ. Ωστόσο η όποια διαδικασία υλοποιείται και τις άλλες δύο δομές επανάληψης ΟΣΟ και ΜΕΧΡΙΣ_ΟΤΟΥ.

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

1. Προσπέλαση
2. Αναζήτηση (έχουμε 2 τύπους αναζήτησης)
3. Αντιγραφή
4. Συγχώνευση
5. Διαχωρισμός
6. Ταξινόμηση
7. Εισαγωγή
8. Διαγραφή

Οι έξι πρώτες εφαρμόζονται και στους δύο τύπους δομών δεδομένων, δηλαδή στις Στατικές και Δυναμικές.

Οι δύο τελευταίες εφαρμόζονται μόνο στις Δυναμικές δομές (Στοίβα και Ουρά).

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

Πρώτα όμως πρέπει να απαντήσουμε στο ερώτημα :  Γιατί και πότε πρέπει να χρησιμοποιήσουμε πίνακα ; Η απάντηση είναι απλή : Όταν για να λυθεί το πρόβλημα απαιτείται η παραμονή κάποιων δεδομένων στη μνήμη του υπολογιστή. Αυτό γιατί, επειδή ο πίνακας δεσμεύει ένα κομμάτι μνήμης για τα δεδομένα, τα ‘κρατά’ καθ’ όλη τη διάρκεια εκτέλεσης του αλγορίθμου – προγράμματος, δίνοντάς μας έτσι τη δυνατότητα να τα επεξεργαστούμε – διαχειριστούμε όταν και όσες φορές θέλουμε.

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

 Για να δείτε ΑΝΑΛΥΤΙΚΑ τις έννοιες που σχετίζονται με τις λειτουργίες - πράξεις επί των πινάκων (ως στατικών δομών) πατήστε ΕΔΩ

 Για να υλοποιήσετε αλγορίθμους που απαιτούν τη χρήση πινάκων προσπαθήστε να επιλέξετε και να συνδιάσετε σωστά τις λειτουργίες - πράξεις που αναλύσαμε, αλλά και να δημιουργήσετε δικές σας. Για προβλήματα - ασκήσεις πατήστε ΕΔΩ. 

Οι ασκήσεις αυτές σχετίζονται με μονοδιάστατους και δισδιάστατους πίνακες. Για τους δισδιάστατους πίνακες γίνεται ανάλυση στην επόμενη ενότητα της σελίδας.

Ασκήσεις για Προχωρημένους ΕΔΩ.

Πίνακες Δισδιάστατοι

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

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

Η πρώτη διαφορά είναι φυσικά στο γέμισμα και την εμφάνιση τιμών ενός δισδιάστατου πίνακα. Έστω ένας πίνακας 2 διαστάσεων Α(4,5), δηλαδή με 4 γραμμές και 5 στήλες. Οπότε κάθε κόμβος – θέση του, πρέπει να προσδιοριστεί και από  τους δύο δείκτες, άρα έχουμε :

Οπότε :

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

Όμως ας θυμόμαστε πάντα ότι :

-          Κάθε γραμμή έχει τόσα στοιχεία (κόμβους) όσες είναι οι στήλες.

-          Κάθε στήλη έχει τόσα στοιχεία (κόμβους) όσες είναι οι γραμμές.

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

Για να προσδιοριστεί μια γραμμή θέτουμε στον αριστερό δείκτη Ι τον αριθμό της γραμμής - π.χ. για τη 3^η γραμμή έχουμε Α[3, J] και

Για να προσδιοριστεί μια στήλη θέτουμε στον δεξιό δείκτη J τον αριθμό της στήλης – π.χ. για την 2^η στήλη έχουμε Α[Ι, 2].

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

Αν οι διαστάσεις του τετραγωνικού πίνακα είναι άρτιος αριθμός, τότε έχει κεντρικό στοιχείο (κόμβο), όπου Ι = J.                                                                                                 

Παράδειγμα Α[4, 4], Β[5, 5]. Ο πίνακας Β έχει κεντρικό στοιχείο, ενώ ο Α όχι.

Λύνοντας την παρακάτω γενική ΑΣΚΗΣΗ – δισδιάστατων πινάκων, θα κατανοήσετε πως διαχειριζόμαστε έναν 2σδιάσατο πίνακα, αλλά και πως δημιουργούνται νέοι μονοδιάστατοι πίνακας από αυτόν.

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

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

β) να εμφανίζει το όνομα του παίκτη με τον μεγαλύτερο μέσο όρο πόντων.

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

δ) να εμφανίζονται τα ονόματα των παικτών με τους 3 μεγαλύτερους αριθμούς πόντων. ….

ε) να εμφανίζεται ο μεγαλύτερος αριθμός πόντων για κάθε αγώνα.

στ) να εμφανίζονται τα σύνολα των πόντων για κάθε αθλητή και τα σύνολα των πόντων για κάθε αγώνα.

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

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

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

 Επιπλέον Ασκήσεις ΕΔΩ

Δομή Επανάληψης

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

Υπάρχουν τρία είδη δομής επανάληψης, τα οποία είναι : η δομή ΓΙΑ, η δομή  ΟΣΟ και η δομή ΜΕΧΡΙΣ_ΟΤΟΥ – όπως συνηθίζεται να λέγονται για συντομία.

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

Να υπολογιστεί το άθροισμα :  S = 2+4+6+ … + 100, καθώς και το πλήθος των όρων του (που εδώ είναι προφανές).

Γενικές παρατηρήσεις.

Α.

Ø      Όποιος αλγόριθμός επιλύεται με την ΓΙΑ μπορεί πάντα να επιλυθεί (μετατραπεί) και με την ΟΣΟ και την ΜΕΧΡΙΣ_ΟΤΟΥ

Ø      Όποιος αλγόριθμος επιλύεται με τις ΟΣΟ και ΜΕΧΡΙΣ_ΟΤΟΥ δεν μπορεί πάντα να επιλυθεί (μετατραπεί) στην ΓΙΑ.

Ø      Όποιος αλγόριθμος επιλύεται με την ΟΣΟ, επιλύεται (μετατρέπεται) πάντα στην ΜΕΧΡΙΣ_ΟΤΟΥ και αντιστρόφως.

Β.

     Με τη δομή επανάληψης εισάγονται τρία νέα είδη μεταβλητών, όπου εννοείται ότι διατηρούν τα βασικά χαρακτηριστικά και την έννοια της  ‘μεταβλητής’ που μάθαμε μέχρι τώρα, αλλά έχουν κάποιες επιπλέον ιδιότητες.

Αυτές οι μεταβλητές είναι :

ΑΘΡΟΙΣΤΗΣ : είναι η μεταβλητή που αλλάζει (αυξάνεται) κατά μια τυχαία (διαφορετική) ποσότητα. Π.χ. Sß S + X

ΜΕΤΡΗΤΗΣ : είναι η μεταβλητή που αυξάνεται πάντα κατά μια μονάδα. Π.χ. Μ ß Μ +1.

ΒΗΜΑ : είναι η μεταβλητή που μεταβάλλεται κατά την ίδια – μια σταθερή ποσότητα. Π.χ. Ι ß Ι +1.

Γ. 

 Άρα για το προηγούμενο παράδειγμα,

η μεταβλητή S είναι Αθροιστής,

η μεταβλητή Μ είναι Μετρητής και

η μεταβλητή Ι είναι το Βήμα.

Ο Αθροιστής και ο Μετρητής συνήθως έχουν αρχική τιμή μηδέν(0), όπως για τις ανάγκες του συγκεκριμένου προβλήματος.

Όμως, υπάρχουν πολλές άλλες ιδιαίτερες περιπτώσεις προβλημάτων που η αρχική τους τιμή δεν πρέπει να είναι απαραίτητα μηδέν. Τέτοιες περιπτώσεις θα ήταν αν θέλαμε να προσθέσουμε κάποιο όρο εκτός της ακολουθίας (π.χ. το 21 ή το 0,7), οπότε αν δεν θέλαμε να τις προσθέσουμε στο τελικό άθροισμα εκτός επανάληψης, θα μπορούσαμε να αρχικοποιήσουμε το S με αυτές τις τιμές. Άλλη περίπτωση θα ήταν αν θέλαμε το πλήθος των αριθμών από το 12 και έπειτα με βήμα 2, οπότε θα αρχικοποιούσαμε το Μ με το 12.

Εφόσον έχετε εξοικειωθεί με τη δομή ΟΣΟ και ΜΕΧΡΙΣ_ΟΤΟΥ προσέξτε τις ασκήσεις που έχουν ιδιαίτερο ενδιαφέρον, πατήστε στο σύνδεσμο : Ασκήσεις

ΕΥΡΕΣΗ Μεγαλύτερου και Μικρότερου αριθμού.

Θα διακρίνουμε 2 περιπτώσεις :

1)      Όταν υπάρχει άνω και κάτω όριο τιμής

2)      Όταν δεν υπάρχει άνω και κάτω όριο τιμής

1) Να δίνονται 20 ονόματα ατόμων που στο καθένα αντιστοιχεί ένας ακέραιος αριθμός, δηλ. δίνουμε  επίσης 20 ακέραιους αριθμούς, των οποίων οι τιμές κυμαίνονται από 0 έως και 100 (να μην γίνει έλεγχος εγκυρότητας). Να βρεθεί ο μεγαλύτερος αριθμός που δόθηκε (υποθέστε ότι είναι ένας και μοναδικός) και το όνομα εκείνου που του αντιστοιχεί. Επίσης να βρεθεί η σειρά που δόθηκαν.

            Αρχή

            ΜΑΧ ß 0

            ΜΙΝ ß 100

            Για Ι από 1 μέχρι 20

            Διάβασε Α, ΟΝ

               Αν Α>ΜΑΧ τότε

                        ΜΑΧ ß Α

                        ΝΑΜΕ1 ß ΟΝ

                        ΣΕΙΡΑ1 ß Ι

               Τέλος_Αν

               Αν Α<ΜΙΝ τότε

                        ΜΙΝ ß Α

                        ΝΑΜΕ2 ß ΟΝ

                        ΣΕΙΡΑ2 ß Ι

               Τέλος_Αν

Τέλος_επανάληψης

            Γράψε ΜΑΧ, ΝΑΜΕ1, ΣΕΙΡΑ1

            Γράψε ΜΙΝ, ΝΑΜΕ2, ΣΕΙΡΑ2

            Τέλος

2)      Να βρεθεί ο μεγαλύτερος και ο μικρότερος αριθμός, καθώς και οι σειρά που θα δοθούν, όταν οι τιμές δεν κυμαίνονται μεταξύ κάποιων ορίων και όταν:

Δηλαδή όταν δεν υπάρχει άνω ή κάτω όριο πρέπει να βάλουμε ΜΑΧ και ΜΙΝ τήν πρώτη τιμή του αριθμού που θα διαβάσουμε - δώσουμε από το πληκτρολόγιο και στη συνέχεια αντικαθίσταται όποιος θα είναι μεγαλύτερος ή μικρότερος αντίστοιχα.

Μπορείτε να εξασκηθείτε με ασκήσεις διαφορετικής δυσκολίας και συνδιαστικότητας με άλλες δομές επανάληψης και επιλογής  ΕΔΩ.

Επίσης δώστε ιδιαίτερη προσοχή στις ασκήσεις ΕΔΩ.