Odhgos Pseydokwdika B

ΣΥΝΟΠΤΙΚΟΣ ΟΔΗΓΟΣ ΨΕΥΔΟΚΩΔΙΚΑ Μέρος Β΄ Λίστες Δείκτης: Είναι μια μεταβλητή (που ονομάζεται μεταβλητή τύπου δείκτη ή απλώς δείκτης), που αντιπροσωπεύει μια θέση της μνήμης όπου βρίσκεται αποθηκευμένη η διεύθυνση μιας άλλης θέσης της μνήμης, στην οποία λέμε ότι «δείχνει» ο δείκτης. Κόμβος: Είναι μια δομή που αντιπροσωπεύει μια οντότητα (έννοια) που έχει ένα όνομα και αποτελείται από διάφορα πεδία (ή μέλη), που παριστάνουν ιδιότητες της οντότητας που αντιπροσωπεύει. Ένα από τα πεδία είναι δείκτης σ’ ένα άλλο (επόμενο) κόμβο. Π.χ. ένας κόμβος με όνομα (ή τύπου) PHONE, που παριστάνει μια καταχώρηση σ’ ένα τηλεφωνικό κατάλογο, είναι ο παρακάτω. Το πεδίο NEXT παριστάνει ένα δείκτη στον επόμενο κόμβο, ενώ τα πεδία NAME NUM. PHONE NEXT NAME NUM

Ας υποθέσουμε ότι ορίζω μια δομή (δηλ. ένα κόμβο) τύπου PHONE που αποθηκεύεται στις θέσεις μνήμης 033-035 (στην πραγματικότητα αυτό καθορίζεται από το λειτουργικό σύστημα του υπολογιστή). Επίσης, ας υποθέσουμε ότι ορίζω ένα δείκτη Ρ στη δομή αυτή, δηλ. μια μεταβλητή τύπου δείκτη που «δείχνει» στη θέση μνήμης (δηλ. στη θέση 033) απ’ όπου αρχίζει η αποθήκευση του κόμβου. Έστω δε ότι η μεταβλητή αυτή (η Ρ) αποθηκεύεται στη θέση μνήμης 030 (στην πραγματικότητα και αυτό καθορίζεται από το λειτουργικό σύστημα του υπολογιστή). Τότε στην (κεντρική) μνήμη του υπολογιστή θα έχω (σχηματικά) την παρακάτω κατάσταση. 029 Ρ

030

031

032

033

034

035

036

033 PHONE

Τότε λέμε ότι ο δείκτης Ρ δείχνει στον κόμβο PHONE. Λίστα: Είναι μια ακολουθία κόμβων (που λέγονται και στοιχεία της λίστας) που συνδέονται μεταξύ τους με δείκτες, έτσι ώστε κάθε κόμβος να δείχνει στον επόμενό του. Π.χ. Η παρακάτω είναι μια λίστα από κόμβους τύπου PHONE, όπου ΝΝΝ1, ΝΝΝ2, ... είναι ονόματα και ΑΑΑ1, ΑΑΑ2, ... είναι αριθμοί τηλεφώνων. Ο δείκτης L, που λέγεται δείκτης αρχής, δείχνει στο πρώτο στοιχείο της λίστας, που λέγεται κεφαλή. Σε μια γλώσσα προγραμματισμού ο δείκτης αρχής αντιπροσωπεύει τη λίστα. Το τελευταίο στοιχείο της λίστας δείχνει στο κενό (NIL).

δείκτες 1

L NEXT ΝΝΝ1 ΑΑΑ1

NEXT ΝΝΝΚ ΑΑΑΚ

NEXT NΝΝ2 ΑΑΑ2

NIL

Δήλωση δείκτη Σύνταξη: <όνομα-δείκτη>: POINTER[<τύπος>]; Το <όνομα-δείκτη> είναι το όνομα της μεταβλητής δείκτη (ή απλώς δείκτη) και <τύπος> είναι ο τύπος των δεδομένων στο οποίο δείχνει ο δείκτης (INTEGER, REAL, CHAR, PHONE κλπ). Π.χ. PH: POINTER[PHONE];

AK: POINTER[INTEGER];

Στην πρώτη δήλωση, δηλώνεται ένας δείκτης με όνομα ΡΗ που θα δείχνει σε δεδομένα τύπου PHONE, δηλ. σε θέσεις μνήμης όπου θα είναι η αρχή καταχώρησης μιας δομής τύπου PHONE. Στη δεύτερη δήλωση δηλώνεται ένας δείκτης με όνομα ΑΚ που θα δείχνει σε δεδομένα τύπου INTEGER, δηλ. σε θέσεις μνήμης όπου θα καταχωρούνται ακέραιοι αριθμοί. Με τις δηλώσεις αυτές κρατούνται θέσεις στη μνήμη για τους δείκτες ΡΗ και ΑΚ. Δήλωση κόμβου Σύνταξη: <όνομα-δομής>: <πεδίο1>: <τύπος1>; <πεδίο2>: <τύπος2>; ... <πεδίον>: <τύποςν>; <δείκτης>: POINTER[<όνομα-δομής>]; Τα <πεδίο1>, <πεδίο2>, ..., <πεδίον> είναι μεταβλητές που παριστάνουν τα πεδία (ιδιότητες) της οντότητας που παριστάνεται από τη δομή <όνομα-δομής> και <δείκτης> μια μεταβλητή δείκτη που δείχνει σ’ ένα κόμβο τύπου <όνομα-δομής>. Π.χ. για τον κόμβο τύπου PHONE θα έχουμε PHONE: NUM: INTEGER; NAME: CHAR; NEXT: POINTER[PHONE];

2

Δημιουργία κόμβου Σύνταξη: ΥΠΟΛΟΓΙΣΕ ΔΗΜΙΟΥΡΓΗΣΕ-ΚΟΜΒΟ(<όνομα-δείκτη>); Η ΔΗΜΙΟΥΡΓΗΣΕ-ΚΟΜΒΟ(<όνομα-δείκτη>) είναι μια διαδικασία (εντολή) με την οποία δημιουργούμε ένα κόμβο που έχει τη δομή των δεδομένων στα οποία δείχνει ο δείκτης με όνομα το <όνομα-δείκτη>. Το ΥΠΟΛΟΓΙΣΕ είναι η εντολή με την οποία καλούμε μια διαδικασία για εκτέλεση. Π.χ. ΥΠΟΛΟΓΙΣΕ ΔΗΜΙΟΥΡΓΗΣΕ-ΚΟΜΒΟ(ΡΗ); Με την εντολή αυτή δημιουργείται ένας κόμβος τύπου PHONE (διότι ο δείκτης ΡΗ είναι δείκτης σε δομή τύπου PHONE), δηλ. κρατούνται θέσεις στη μνήμη για ένα κόμβο τέτοιου τύπου, και ταυτόχρονα ο δείκτης ΡΗ παίρνει σαν τιμή τη διεύθυνση της πρώτης θέσης μνήμης του χώρου που κρατήθηκε, δηλαδή δείχνει σ’ αυτή. Το αποτέλεσμα αυτής της εντολής σχηματικά είναι: ΡΗ

NEXT NAME NUM

NIL

Προσπέλαση-Καταχώρηση σε κόμβο Σύνταξη: <δείκτης>^.<πεδίο> (προσπέλαση) <δείκτης>^.<πεδίο> := <τιμή> (καταχώρηση) Π.χ. Τα ΡΗ^.NUM, PH^.NAME, PH^.NEXT χρησιμοποιούνται όπως οι μεταβλητές, επέχουν δηλ. τη θέση μεταβλητών τύπου INTEGER, CHAR και δείκτη σε PHONE (δηλ. POINTER[PHONE]) αντίστοιχα. Με τις εντολές PH^.NUM:=2610960321 και PH^.NAME:=“XATZHS” καταχωρώ τιμές στα πεδία του κόμβου που δείχνει ο δείκτης ΡΗ. Δήλωση λίστας Σύνταξη: <όνομα-λίστας>: LIST OF <τύπος-κόμβου>; Π.χ.

3

PHONE-LIST: LIST OF PHONE; Εδώ δηλώνουμε μια λίστα με όνομα PHONE-LIST που έχει κόμβους τύπου PHONE. Δομή αλγορίθμου Ένας αλγόριθμος χωρίς υποπρογράμματα (δηλ. διαδικασίες ή συναρτήσεις) έχει την παρακάτω δομή. ΑΛΓΟΡΙΘΜΟΣ <όνομα-αλγορίθμου> ΤΥΠΟΙ <εδώ δηλώνονται νέοι τύποι δεδομένων, όπως π.χ. ο τύπος της δομής ενός κόμβου> ΔΕΔΟΜΕΝΑ <εδώ γίνονται οι δηλώσεις μεταβλητών, δεικτών και λιστών> ΑΡΧΗ <εδώ γράφονται οι εντολές του κυρίως προγράμματος> ΤΕΛΟΣ (Αυτή τη δομή αλγορίθμου θα χρησιμοποιήσετε στην Υποεργασία 4. Στην υποεργασία 3, που δεν υπάρχουν κόμβοι και λίστες, δεν χρειάζεται το τμήμα ΤΥΠΟΙ, διότι δεν υπάρχουν νέοι τύποι να δηλώσετε.)

4

Παράδειγμα Ας υποθέσουμε ότι μας δίνουν μια λίστα ακεραίων, δηλ. μια λίστα που οι κόμβοι της αποτελούνται από ένα ακέραιο αριθμό και τον δείκτη στον επόμενο κόμβο, που τα στοιχεία της είναι διατεταγμένα, δηλ. οι κόμβοι είναι συνδεδεμένοι κατ’ αύξουσα σειρά (δηλ. ο ακέραιος κάθε επόμενου κόμβου είναι μεγαλύτερος από ή ίσος με αυτόν του προηγούμενου). Μας ζητούν δε να γράψουμε ένα αλγόριθμο που να παίρνει ένα νέο κόμβο που μας δίνεται και να τον παρεμβάλλει στη λίστα ώστε να παραμένει διατεταγμένη. Αν θέλουμε να δούμε σχηματικά τι πρέπει να γίνει, ας υποθέσουμε ότι έχουμε την παρακάτω διατεταγμένη λίστα: L NEXT 4

NEXT 2

NEXT 7

NIL

Και μας δίνεται ο παρακάτω κόμβος για να τον παρεμβάλλουμε: ΡΗ

NEXT 5

NIL

Για να γίνει αυτό, πρέπει να διέλθουμε τη λίστα από την αρχή συγκρίνοντας κάθε φορά τον ακέραιο του τρέχοντος κόμβου με τον ακέραιο του κόμβου που μας δόθηκε. Όταν ο ακέραιος του τρέχοντος κόμβου είναι μεγαλύτερος από (ή ίσος με) αυτόν του δοθέντος κόμβου, σταματάμε και παρεμβάλουμε τον κόμβο μεταξύ του τρέχοντος και του προηγούμενου. Στην περίπτωσή μας θα σταματήσουμε όταν φτάσουμε στον τρίτο και τελευταίο κόμβο (διότι 7 > 5), οπότε πρέπει να παρεμβάλλουμε τον κόμβο μας μεταξύ των κόμβων με ακεραίους 4 και 7. Η παρεμβολή σχηματικά γίνεται ως εξής: Ρ

NEXT 7

NEXT 4

PRE

NIL

NEXT 5

NIL

CUR

Δηλ. ο δείκτη του κόμβου ‘4’ κατευθύνεται να δείχνει στο νέο κόμβο και ο δείκτης του νέου κόμβου να δείχνει στον κόμβο ‘7’ (Οι δείκτες PRE και CUR έχουν σχέση με τον αλγόριθμο της επόμενης σελίδας). Η υλοποίηση αυτής της διαδικασίας με αλγόριθμο γίνεται όπως φαίνεται στη συνέχεια (ότι βρίσκεται ανάμεσα σε /* */ και με κόκκινο χρώμα είναι σχόλια).

5

ΑΛΓΟΡΙΘΜΟΣ ΠΑΡΕΜΒΟΛΗ-ΚΟΜΒΟΥ ΤΥΠΟΙ AKER-LIST: TIMH: INTEGER; NEXT: POINTER[AKER-LIST]; /* Εδώ ορίζουμε τον τύπο του κόμβου*/ ΔΕΔΟΜΕΝΑ AL: LIST OF AKER-LIST; /* AL είναι η λίστα που μας δίνεται*/ L, P, CUR, PRE: POINTER[AKER-LIST]; /* Ο L είναι ο δείκτης στην κεφαλή (πρώτο κόμβο) της λίστας AL και ο Ρ στο νέο κόμβο (βλ. προηγούμενο σχήμα). Οι CUR, PRE είναι δύο βοηθητικοί δείκτες. Ο πρώτος δείχνει στον τρέχοντα κόμβο (δηλ. στον κόμβο που εξετάζουμε κάθε φορά) και ο PRE στον προηγούμενο. Ο PRE χρειάζεται διότι όταν θα κάνουμε την παρεμβολή χρειάζεται να αλλάξουμε την τιμή του δείκτη του προηγούμενου (από τον τρέχοντα) κόμβου (βλ. προηγούμενο σχήμα).*/ ΑΡΧΗ CUR:= L; PRE:= L; /* Αρχικοποιούμε τους δύο βοηθητικούς δείκτες*/ ΕΝΟΣΩ (CUR <> NIL) AND (CUR^.TIMH < P^.TIMH) ΕΠΑΝΕΛΑΒΕ PRE:= CUR; /* Παίρνει την τιμή του δείκτη στον τρέχοντα κόμβο*/ CUR:= CUR^.NEXT; /* Παίρνει την τιμή του δείκτη στον επόμενο κόμβο, δηλ. προχωράμε στον επόμενο κόμβο*/ ΕΝΟΣΩ-ΤΕΛΟΣ ΕΑΝ (CUR <> NIL) ΤΟΤΕ /*Δηλ. αν δεν φθάσαμε στο τέλος της λίστας*/ PRE^.NEXT:= P; Αυτά γίνονται όταν παρεμβάλλεται ο νέος κόμβος P^.NEXT:= CUR; ενδιάμεσα (όπως στο προηγούμενο σχήμα). ΑΛΛΙΩΣ Αυτό γίνεται όταν ο νέος κόμβος μπαίνει στο τέλος PRE^.NEXT:= P; της λίστας. ΕΑΝ-ΤΕΛΟΣ ΤΕΛΟΣ Ο αλγόριθμος αυτός δεν είναι πλήρης, διότι δεν εξετάζει την περίπτωση να πρέπει να μπει ο νέος κόμβος στη αρχή της λίστας, δηλ. πριν από τον πρώτο κόμβο. Επομένως θέλει κάποια συμπλήρωση.

6