Odhgos Pseydokwdika B

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

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

030 033 Ρ

031

032

033

034

035

036

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 2

NEXT 4

NEXT 7

NIL

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

NEXT 5

NIL

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

NEXT 4

PRE

NIL

NEXT 5

NEXT 7

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