Πίνακες θεωρία

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

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

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

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

Δισδιάστατος πίνακας
Ένας δισδιάστατος πίνακας έχει 2 δείκτες, στον οποίο ο πρώτος δείκτης δείχνει τη γραμμή και ο δεύτερος τη στήλη.

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

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

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

Περιπτώσεις στις οποίες συνιστάται η χρήση σειριακής αναζήτησης σε ταξινομημένο πίνακα.
1. Ο πίνακας είναι μικρού μεγέθους.
2. Η αναζήτηση γίνεται σπάνια σε αυτόν τον πίνακα.

ταξινόμηση

Αλγόριθμος ταξινόμηση

!αύξουσα ταξινόμηση
!Ν είναι το μέγεθος του πίνακα Π
Για i από 2 μέχρι Ν
  Για j από Ν μέχρι i με βήμα -1
    Αν Π[j] < Π[j - 1] τότε
      temp ← Π[j]
      Π[j] ← Π[j - 1]
      Π[j - 1] ← temp
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Τέλος 

σειριακή_αναζήτηση_πολλές_φορές

Αλγόριθμος σειριακή_αναζήτηση_πολλές_φορές

!Ν είναι το μέγεθος του πίνακα Π
πλήθος ← 0
Για i από 1 μέχρι N
  Αν συνθήκη_αναζήτησης τότε
    πλήθος ← πλήθος + 1
  Τέλος_αν
Τέλος_επανάληψης
Αν πλήθος = 0 τότε
  Γράψε 'Δεν υπάρχει.'
αλλιώς
  Γράψε 'Υπάρχει ', πλήθος, ' φορές'
Τέλος_αν

Τέλος 

σειριακή_αναζήτηση_μία_φορά

Αλγόριθμος σειριακή_αναζήτηση_μία_φορά

!Ν είναι το μέγεθος του πίνακα Π
i ← 1
βρέθηκε ← Ψευδής
θέση ← -1
Όσο i ≤ Ν και βρέθηκε = Ψευδής επανάλαβε
  Αν συνθήκη_αναζήτησης τότε
    βρέθηκε ← Αληθής
    θέση ← i
  αλλιώς
    i ← i + 1
  Τέλος_αν
Τέλος_επανάληψης
Αν βρέθηκε = Ψευδής τότε
  Γράψε 'Δεν υπάρχει.'
αλλιώς
  Γράψε 'Υπάρχει.'
Τέλος_αν
Αν θέση = -1 τότε
  Γράψε 'Δεν υπάρχει.'
αλλιώς
  Γράψε 'Υπάρχει στη θέση ', i
Τέλος_αν

Τέλος 

πίνακες

Αλγόριθμος πίνακες

!Ν είναι το μέγεθος του πίνακα Π

!Διάβασμα πίνακα
Για i από 1 μέχρι N
  Διάβασε Π[i] 
Τέλος_επανάληψης

!Εμφάνιση πίνακα
Για i από 1 μέχρι N
  Γράψε Π[i] 
Τέλος_επανάληψης

!μέσος όρος πίνακα
άθροισμα ← 0
Για i από 1 μέχρι Ν
  άθροισμα ← άθροισμα + Π[i] 
Τέλος_επανάληψης
μέσος_όρος ← άθροισμα/ Ν

!max πίνακα και max_i(θέση max)
max ← Π[1] 
max_i ← 1
Για i από 2 μέχρι N
  Αν max < Π[i] τότε
    max ← Π[i] 
    max_i ← i
  Τέλος_αν
Τέλος_επανάληψης

Τέλος 

παράλληλη_ταξινόμηση

Αλγόριθμος παράλληλη_ταξινόμηση

!αύξουσα ταξινόμηση
!σε περίπτωση ίσοβαθμίας, ταξινομούμε αλφαβητικά
!Ν είναι το μέγεθος του πίνακα Π και του πίνακα ΟΝ
Για i από 2 μέχρι Ν
  Για j από Ν μέχρι i με βήμα -1
    Αν Π[j] < Π[j - 1] τότε
      temp ← Π[j] 
      Π[j] ← Π[j - 1] 
      Π[j - 1] ← temp
      temp2 ← ΟΝ[j] 
      ΟΝ[j] ← ΟΝ[j - 1] 
      ΟΝ[j - 1] ← temp2
    αλλιώς_αν Π[j] = Π[j - 1] τότε
      Αν ΟΝ[j] < ΟΝ[j - 1] τότε
        temp2 ← ΟΝ[j]
        ΟΝ[j] ← ΟΝ[j - 1] 
        ΟΝ[j - 1] ← temp2
      Τέλος_αν
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Τέλος 

δισδιάστατοι_άθροισμα

Αλγόριθμος δισδιάστατοι_άθροισμα

!Πίνακας Π, διάστασης ΝxΜ
!Πίνακας ΑΓ: αθροίσματα γραμμών
!Πίνακας ΑΣ: αθροίσματα στηλών
!άθροισμα: άθροισμα όλου του πίνακα (συνολικό άθροισμα)

!αρχικοποιήσεις
άθροισμα ← 0
Για i από 1 μέχρι Ν
  ΑΓ[i] ← 0
Τέλος_επανάληψης
Για j από 1 μέχρι Μ
  ΑΣ[j] ← 0
Τέλος_επανάληψης

!-------------------1ος τρόπος
Για i από 1 μέχρι Ν
  Για j από 1 μέχρι Μ
    ΑΓ[i] ← ΑΓ[i] + Π[i, j] 
    ΑΣ[j] ← ΑΣ[j] + Π[i, j] 
    άθροισμα ← άθροισμα + Π[i, j] 
  Τέλος_επανάληψης
Τέλος_επανάληψης

!-------------------2ος τρόπος
Για j από 1 μέχρι Μ
  Για i από 1 μέχρι Ν
    ΑΓ[i] ← ΑΓ[i] + Π[i, j] 
    ΑΣ[j] ← ΑΣ[j] + Π[i, j] 
    άθροισμα ← άθροισμα + Π[i, j] 
  Τέλος_επανάληψης
Τέλος_επανάληψης

Τέλος 

δισδιάστατοι_max

Αλγόριθμος δισδιάστατοι_max

!Πίνακας Π, διάστασης ΝxΜ
!Πίνακας MAXΓ: μέγιστα γραμμών
!Πίνακας MAXΣ: μέγιστα στηλών
!max: μέγιστο όλου του πίνακα (συνολικό μέγιστο)

!αρχικοποιήσεις
max ← 0
Για i από 1 μέχρι Ν
  MAXΓ[i] ← Π[i, 1] 
Τέλος_επανάληψης
Για j από 1 μέχρι Μ
  MAXΣ[j] ← Π[1, j] 
Τέλος_επανάληψης

!-------------------1ος τρόπος
Για i από 1 μέχρι Ν
  Για j από 1 μέχρι Μ
    Αν MAXΓ[i] < Π[i, j] τότε
      MAXΓ[i] ← Π[i, j] 
    Τέλος_αν
    Αν MAXΣ[j] < Π[i, j] τότε
      MAXΣ[j] ← Π[i, j] 
    Τέλος_αν
    Αν max < Π[i, j] τότε
      max ← Π[i, j] 
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

!-------------------2ος τρόπος
Για j από 1 μέχρι Μ
  Για i από 1 μέχρι Ν
    Αν MAXΓ[i] < Π[i, j] τότε
      MAXΓ[i] ← Π[i, j] 
    Τέλος_αν
    Αν MAXΣ[j] < Π[i, j] τότε
      MAXΣ[j] ← Π[i, j] 
    Τέλος_αν
    Αν max < Π[i, j] τότε
      max ← Π[i, j] 
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

!3ος τρόπος για maxΓ και maxΣ, συνδυασμός του 1ου και του 2ου τρόπου
Για i από 1 μέχρι Ν
  Για j από 2 μέχρι Μ
    Αν MAXΓ[i] < Π[i, j] τότε
      MAXΓ[i] ← Π[i, j] 
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Για j από 1 μέχρι Μ
  Για i από 2 μέχρι Ν
    Αν MAXΣ[j] < Π[i, j] τότε
      MAXΣ[j] ← Π[i, j] 
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Τέλος 

Β΄Λυκείου

Διαβάσετε μέχρι και τη σελίδα 34 του βιβλίου.



Λήψη αρχείου