Πίνακας (δομή δεδομένων): Διαφορά μεταξύ των αναθεωρήσεων

Στην επιστήμη υπολογιστών, μία δομή δεδομένων πίνακας ή απλά πίνακας είναι μία δομή δεδομένων που αποτελείται από μία συλλογή στοιχείων, αριθμημένων με βάση τη θέση τους στη δομή. Με βάση την αρίθμηση αυτή, κάθε στοιχείο ενός πίνακα μπορεί να προσπελαστεί, δοσμένης της θέσης του, σε σταθερό χρόνο. Δεδομένου ότι πρόκειται για μία συλλογή στοιχείων, και όχι ένα σύνολο, δεν αποκλείεται η ύπαρξη διπλοεγγραφών.

Η έννοια του πίνακα είναι ανάλογη με αυτή του διανύσματος, ή των πινάκων στα μαθηματικά.

Αρκετές άλλες βασικές δομές δεδομένων, όπως οι δυναμικοί πίνακες, οι πίνακες κατακερματισμού ή και πιο σύνθετες, όπως το πλέγμα βασίζονται, για την υλοποίησή τους σε πίνακες.

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

Στην διπλανή εικόνα βλέπετε ένα παράδειγμα μονοδιάστατου πίνακα 6 θέσεων, του οποίου το πρώτο στοιχείο είναι το 4, το δεύτερο (όπως ακριβώς και το έκτο) είναι το 9, κ.ο.κ. Για να εντοπίσουμε ένα στοιχείο, αρκεί να το αναζητήσουμε με βάση τη θέση του. Παρόλο που αυτή η διαδικασία χρειάζεται σταθερό χρόνο (πολυπλοκότητα Ο(1)), η παρόμοια διαδικασία της αναζήτησης με βάση την τιμή (και όχι τη θέση) ενός στοιχείου απαιτεί γραμμικό χρόνο ως προς τον αριθμό των στοιχείων του πίνακα (πολυπλοκότητα Ο(Ν)). Για παράδειγμα, στον διπλανό πίνακα η εύρεση του στοιχείου "3" απαιτεί 4 βήματα, ενώ η εύρεση του στοιχείου "9" απαιτεί 6 βήματα, δηλαδή τη διάτρεξη ολόκληρου του πίνακα.

Στον πίνακα του προηγούμενου παραδείγματος, μπορούμε να δούμε ότι ο πίνακας αριθμείται ξεκινώντας από το 0 και όχι από το 1. Οπότε, βλέπουμε "θέση 0" για το πρώτο στοιχείο του. Αυτό αποτελεί μια κοινή τακτική αρίθμησης για την πλειοψηφία των σύγχρονων γλωσσών προγραμματισμού, όπως είναι η Java, C/C++ κλπ. Έτσι, δοσμένου ενός πίνακα Ν θέσεων, μπορούμε να προσπελάσουμε τα στοιχεία 0 μέχρι Ν-1. Αναζήτηση του στοιχείου στη θέση Ν θα οδηγούσε σε προγραμματιστικό λάθος (κατά κανόνα) κατά την εκτέλεση.

Ταυτόχρονα, παλιότερες γλώσσες προγραμματισμού, όπως οι Fortran και Cobol, οι κάποιες σύγχρονες, όπως Matlab ξεκινούν την αρίθμηση πινάκων από το 1 και συνεπώς, οι προσπελάσιμες θέσεις ενός πίνακα μεγέθους Ν είναι οι θέσεις 1 μέχρι Ν.

Όπως κάθε δομή δεδομένων, έτσι και οι πίνακες υλοποιούν τις βασικές πράξεις τους: εισαγωγή, αναζήτηση, διαγραφή.

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