DataStructures: SingleArray-Theory

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

Απόδοση αρχικής τιμής μηδέν στα στοιχεία του πίνακα

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

...
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
  Τ[Ι] <- 0
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Απόδοση διαδοχικών τιμών στα στοιχεία του πίνακα

Το τμήμα αυτό δίνει αρχικές τιμές διαδοχικές στα στοιχεί του πίνακα. Ο σκοπός του είναι να δείξει τη χρήση της μεταβλητής I τόσο ως δείκτη στον πίνακα όσο και ως μια οποιοδήποτε άλλη μεταβλητή.

...
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
  Τ[Ι] <- Ι + a      ! όπου a ένας πραγματικός αριθμός.
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Απόδοση τιμών στα στοιχεία του πίνακα με τιμές που εισάγει ο χρήστης

...
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
  ΔΙΑΒΑΣΕ Τ[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Εμφάνιση στοιχείων πίνακα

...
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΓΡΑΨΕ Τ[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Εύρεση του ελαχίστου στοιχείου ενός πίνακα

...
MΙΝ <- T[1]           ! Θεωρούμε αυθαίρετα ότι το πρώτο στοιχείο του πίνακα έχει την ελάχιστη τιμή.
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ Ν   ! Αφού η πρώτη τιμή έχει “ελεγχθεί”, ξεκινάμε από τη θέση 2.
  ΑΝ Τ[I] < MΙΝ ΤΟΤΕ  ! Εξετάζεται κάθε φορά το στοιχείο στη θέση i.
    MΙΝ <- T[Ι]       ! Αν είναι μικρότερο τότε ενημερώνεται η μεταβλητή Min.
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Προσοχή: Ο παραπάνω αλγόριθμος βρίσκει μόνο ποιο είναι το ελάχιστο στοιχείο του πίνακα. Δε μας δίνει πληροφορία για το πόσα στοιχεία του πίνακα είναι ίσα με το ελάχιστο ούτε τη θέση αυτών. Για παράδειγμα, αν έχουμε τον παρακάτω πίνακα: T [14, 9, 3, 5, 7, 3] θα βρει ότι το ελάχιστο στοιχείο είναι το 3.

Αν θέλουμε να εμφανίσουμε και τη θέση που βρέθηκε το στοιχείο, τότε προσθέτουμε και μία μεταβλητή η οποία κρατάει το Ι.

...
MIN <- T[1]          ! Θεωρούμε αυθαίρετα ότι το πρώτο στοιχείο του πίνακα έχει την ελάχιστη τιμή.
POS <- 1             ! Η θέση στην οποία "βρέθηκε" το ελάχιστο.
ΓΙΑ I ΑΠΟ 2 ΜΕΧΡΙ N  ! Αφού η πρώτη τιμή έχει “ελεγχθεί”, ξεκινάμε από τη θέση 2.
  ΑΝ Τ[I] < MIN ΤΟΤΕ ! Εξετάζεται κάθε φορά το στοιχείο στη θέση i.
    MIN <- T[I]      ! Αν είναι μικρότερο τότε ενημερώνεται η μεταβλητή Min.
    POS <- I         ! Ενημερώνεται και η μεταβλητή pos με τη θέση i.
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

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

Εύρεση του μεγίστου στοιχείου ενός πίνακα

...
MAX <- T[1]
ΓΙΑ I ΑΠΟ 2 ΜΕΧΡΙ N
  ΑΝ Τ[i] > Max ΤΟΤΕ
    MAX <- T[I]
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Εδώ ισχύου οι ίδιες παρατηρήσεις με την εύρεση ελαχίστου.

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

Θεωρούμε ότι ο πίνακας έχει ακέραιους ή πραγματικούς αριθμούς.

...
ΑΘΡΟΙΣΜΑ <- 0
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΑΘΡΟΙΣΜΑ <- ΑΘΡΟΙΣΜΑ + Τ[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...
! και για να βρούμε το μέσο όρο αυτών...
ΑΘΡΟΙΣΜΑ <- ΑΘΡΟΙΣΜΑ / Ν
...

Συγχώνευση πινάκων

Προσάρτηση ενός πίνακα στο τέλος άλλου πίνακα

Έστω ότι έχουμε δύο πίνακες Τ1, Τ2, με διαστάσεις 1 x n1 και 1 x n2 αντίστοιχα. Θέλουμε να δημιουργήσουμε ένα νέο πίνακα Τ όπου ο Τ2 θα προστεθεί στο τέλος του Τ1. Ο νέος πίνακας πρέπει να έχει διάσταση 1 x n όπου n = n1 + n2. Προσοχή: Οι τρεις πίνακες Τ1, Τ2, Τ πρέπει να δέχονται τον ίδιο τύπο στοιχείων, πχ. ακέραιους.

...
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n1
  Τ[i] <- Τ1[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n2
  Τ[n1 + i] <- Τ2[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Πρόσθεση πινάκων

Για να προσθέσουμε δύο πίνακες θα πρέπει αυτοί να έχουν την ίδια διάσταση. Έτσι, θεωρούμε ότι έχουμε δύο πίνακες Τ1, Τ2, με διάσταση 1 x n ο καθένας. Ο τελικός πίνακας θα έχει και αυτός διάσταση 1 x n και το κάθε στοιχείο του θα είναι το άθροισμα των στοιχείων των Τ1, Τ2 στην αντίστοιχη θέση.

...
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
  Τ[i] <- Τ1[i] + Τ2[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
...

Συγχώνευση ταξινομημένων πινάκων σε νέο επίσης ταξινομημένο πίνακα

Έστω ότι έχουμε δύο πίνακες Τ1, Τ2, με διαστάσεις 1 x n1 και 1 x n2 αντίστοιχα όπου τα στοιχεία και των δύο είναι ταξινομημένα. Θέλουμε να δημιουργήσουμε ένα νέο πίνακα Τ όπου τα στοιχεία του θα περιέχουν όλα τα στοιχεία των Τ1 και Τ2, ταξινομημένα. Για παράδειγμα, έστω ότι οι πίνακες Τ1 και Τ2 είναι:

T1 = [1, 3, 4, 6], T2 = [2, 4, 5, 6, 7, 8]
ο νέος πίνακας που θα προκύψει είναι:
Τ = [1, 2, 3, 4, 4, 5, 6, 6, 7, 8]

Για να προκύψει, λοιπόν, ο παραπάνω πίνακας πρέπει να γίνουν τα παρακάτω βήματα:

  1. Διαβάζουμε το πρώτο στοιχείο των πινάκων Τ1, Τ2
  2. Το μικρότερο από αυτά θα γίνει το πρώτο στοιχείο του Τ
  3. Αυξάνεται ο δείκτης του πίνακα που είχε το μικρότερο στοιχείο
  4. Συγκρίνονται τα δύο (το νέο για τον πίνακα που είχε το μικρότερο και το παλιό για τον άλλον)
  5. Το μικρότερο από αυτά θα γίνει το επόμενο στοιχείο του Τ
  6. Επαναλαμβάνεται η διαδικασία από το βήμα 3 μέχρι να τελειώσουν τα στοιχεία ενός πίνακα
  7. Για τον πίνακα που δεν έχουν τελειώσει τα στοιχεία, διαβάζονται όλα σειριακά και αποδίδονται στον πίνακα Τ

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

Ο τμήμα του αλγόριθμου που υλοποιεί την παραπάνω διαδικασία είναι:

...
i <- 1
j <- 1
k <- 1
ΟΣΟ i<=n1 ΚΑΙ j<=n2 ΕΠΑΝΑΛΑΒΕ
  ΑΝ Τ1[i] < T2[j] ΤΟΤΕ
    T[k] <- T1[i]
    i    <- i + 1
  ΑΛΛΙΩΣ
    T[k] <- T2[j]
    j    <- j + 1
  ΤΕΛΟΣ_ΑΝ
  k <- k + 1      ! Ο προορισμός στον νέο πίνακα αυξάνει πάντα
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Το παραπάνω τμήμα τερματίζεται όταν το i ξεπεράσει το n1 ή όταν το j ξεπεράσει
! το n2, διότι τότε ένας από τους δύο όρους γίνεται ψευδής και συνεπώς ψευδής
! και η συνθήκη στο Όσο. Στο σημείο αυτό ελέγχουμε ποιος πίνακας έχει ακόμη
! στοιχεία για να τα αντιγράψουμε. Τώρα μπορούμε να χρησιμοποιήσουμε το ΓΙΑ
ΑΝ i>n1 ΤΟΤΕ            ! Ο Τ1 δεν έχει άλλα στοιχεία, οπότε χειριζόμαστε τον Τ2
  ΓΙΑ l ΑΠΟ j ΜΕΧΡΙ n2  ! Από το σημείο που σταμάτησε ο Τ2 (j) μέχρι το τέλος
    T[k] <- T2[l]
    k    <- k + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ                  ! Έχει τελειώσει ο Τ2
    ΓΙΑ l ΑΠΟ i ΜΕΧΡΙ n1
      T[k] <- T1[l]
      k    <- k + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
...

Ασκήσεις

Page last modified on 18-02-2008 (17:58)