.
Στην επιστήμη υπολογιστών, μία δομή δεδομένων πίνακας (array data sctructure) ή απλά πίνακας είναι μία δομή δεδομένων που αποτελείται από μία συλλογή στοιχείων, αριθμημένων με βάση τη θέση τους στη δομή. Με βάση την αρίθμηση αυτή, κάθε στοιχείο ενός πίνακα μπορεί να προσπελαστεί, δοσμένης της θέσης του, σε σταθερό χρόνο. Δεδομένου ότι πρόκειται για μία συλλογή στοιχείων, και όχι ένα σύνολο, δεν αποκλείεται η ύπαρξη διπλοεγγραφών.
Η έννοια του πίνακα είναι ανάλογη με αυτή του διανύσματος, ή των πινάκων στα μαθηματικά.
Αρκετές άλλες βασικές δομές δεδομένων, όπως οι δυναμικοί πίνακες, οι πίνακες κατακερματισμού ή και πιο σύνθετες, όπως το πλέγμα βασίζονται, για την υλοποίησή τους σε πίνακες.
Μονοδιάστατοι Πίνακες
Οι μονοδιάστατοι πίνακες αποτελούν την πιο απλή και ίσως, την πιο συχνά εφαρμοσμένη υποκατηγορία πινάκων. Το χαρακτηριστικό τους είναι ότι αρκεί ένας ακέραιος για να ορίσει τη θέση ενός στοιχείου του πίνακα. Λέμε ότι ένας μονοδιάστατος πίνακας έχει μέγεθος Ν, όταν περιέχει Ν θέσεις.
Ένας πίνακας 6 στοιχείων.
Παράδειγμα
Στην διπλανή εικόνα βλέπετε ένα παράδειγμα μονοδιάστατου πίνακα 6 θέσεων, του οποίου το πρώτο στοιχείο είναι το 4, το δεύτερο (όπως ακριβώς και το έκτο) είναι το 9, κ.ο.κ. Για να εντοπίσουμε ένα στοιχείο, αρκεί να το αναζητήσουμε με βάση τη θέση του. Παρόλο που αυτή η διαδικασία χρειάζεται σταθερό χρόνο (πολυπλοκότητα Ο(1)), η παρόμοια διαδικασία της αναζήτησης με βάση την τιμή (και όχι τη θέση) ενός στοιχείου απαιτεί γραμμικό χρόνο ως προς τον αριθμό των στοιχείων του πίνακα (πολυπλοκότητα Ο(Ν)). Για παράδειγμα, στον διπλανό πίνακα η εύρεση του στοιχείου "3" απαιτεί 4 βήματα, ενώ η εύρεση του στοιχείου "9" απαιτεί 6 βήματα, δηλαδή τη διάτρεξη ολόκληρου του πίνακα.
Αρίθμηση θέσεων πινάκων
Στον πίνακα του προηγούμενου παραδείγματος, μπορούμε να δούμε ότι ο πίνακας αριθμείται ξεκινώντας από το 0 και όχι από το 1. Οπότε, βλέπουμε "θέση 0" για το πρώτο στοιχείο του. Αυτό αποτελεί μια κοινή τακτική αρίθμησης για την πλειοψηφία των σύγχρονων γλωσσών προγραμματισμού, όπως είναι η Java, C/C++ κλπ. Έτσι, δοσμένου ενός πίνακα Ν θέσεων, μπορούμε να προσπελάσουμε τα στοιχεία 0 μέχρι Ν-1. Αναζήτηση του στοιχείου στη θέση Ν θα οδηγούσε σε προγραμματιστικό λάθος (κατά κανόνα) κατά την εκτέλεση.
Ταυτόχρονα, παλιότερες γλώσσες προγραμματισμού, όπως οι Fortran και Cobol, οι κάποιες σύγχρονες, όπως Matlab ξεκινούν την αρίθμηση πινάκων από το 1 και συνεπώς, οι προσπελάσιμες θέσεις ενός πίνακα μεγέθους Ν είναι οι θέσεις 1 μέχρι Ν.
Πράξεις επί πινάκων
Όπως κάθε δομή δεδομένων, έτσι και οι πίνακες υποστηρίζουν τις βασικές μεθόδους τους: εισαγωγή, αναζήτηση και διαγραφή ενός στοιχείου. Εισαγωγή (ψευδοκώδικας και κώδικας σε Java ή C):
διαδικασία Εισαγωγή(Πίνακας πίνακας, ακέραιος θέση, ακέραιος στοιχείο) {
πίνακας[θέση] = στοιχείο; // Αποθήκευση του στοιχείου "στοιχείο" στη θέση "θέση"
}
void insert(int[] array, int index, int element) {
array[index] = element;
}
Αναζήτηση ενός στοιχείου σε δοσμένη θέση (ψευδοκώδικας και κώδικας σε Java ή C):
ακέραιος αναζήτηση(Πίνακας πίνακας, ακέραιος θέση) {
επιστροφή πίνακας[θέση]; // Αποθήκευση του στοιχείου "στοιχείο" στη θέση "θέση"
}
void search(int[] array, int index) {
return array[index];
}
Προκειμένου να διαγραφεί ένα στοιχείο πρέπει να γίνει κάποια σύμβαση, όπως για παράδειγμα ότι ένα διαγραμμένο στοιχείο έχει την τιμή -1 (τιμή "σημαία" ή flag). Εναλλακτικά, το τελευταίο στοιχείο του πίνακα μπορεί να αντιγραφεί στη θέση του διαγραμμένου στοιχείου και στη συνέχεια, ένας δείκτης να αποθηκεύει τη θέση του τελευταίου "σωστού" στοιχείου του πίνακα:
ακέραιος διαγραφή(Πίνακας πίνακας, ακέραιος θέση) {
πίνακας[θέση] = πίνακας[τελευταίο]; // Στη θέση "θέση" μεταφέρουμε την τιμή που υπήρχε στη θέση "τελευταίο"
τελευταίο = τελευταίο - 1;
}
void delete(int[] array, int index) {
array[index] = array[last];
last--;
}
Πολυδιάστατοι Πίνακες
Αποτελούν γενίκευση των μονοδιάστατων πινάκων. Εδώ, η θέση ενός στοιχείου δεν περιγράφεται από έναν μοναδικό ακέραιο, αλλά από μια συλλογή ακεραίων μεγέθους όσο και οι διαστάσεις του πίνακα. Π.χ. ένας δισδιάστατος πίνακας χρειάζεται δύο ακεραίους για να προσπελάσει ένα στοιχείο. Παράδειγμα δισδιάστατων πινάκων είναι τα λογιστικά φύλλα (π.χ. Excel) όπου πολύ εύκολα μπορούμε να βρούμε ένα στοιχείο (κελί), δοσμένης της γραμμής, αλλά και της στήλης στην οποία βρίσκεται.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
