Sorted Array

Εισαγωγή

Όπως και στο αταξινόμητη έτσι και εδώ, για την αποθήκευση των λέξεων μέσα στον πίνακα θα γίνει χρήση ενός strcuct (Element). Η δομή έχει ως εξής: υπάρχει ένα πεδίου τύπου string και όνομα word που αποθηκεύει την λέξη αυτούσια επιπλέον, υπάρχει ένα πεδίο τύπου int και με όνομα appearances που αποθηκεύει τις εμφανίσεις της συγκεκριμένης λέξης μέσα στο αρχείο. Ο πίνακας που αποθηκεύει τις λέξεις θα υλοποιηθεί στον σωρό. Σαφέστερα, για την υλοποίηση του πίνακα θα χρησιμοποιηθούν δυο μεταβλητές τύπου int, η size που είναι το μέγεθος του πίνακα (δηλ. των θέσεων που διαθέτει ο πίνακας) και η μεταβλητή posOfLastElement που κρατάει την θέση του τελευταίου στοιχείου μέσα στον πίνακα. Σε περίπτωση όπου ο πίνακας γεμίσει με στοιχεία, καλείται η μέθοδος resize που μεγαλώνει το μέγεθος του πίνακα (διπλασιάζεται η size) έτσι ώστε να μην χαθούν λέξεις από το αρχείο.

Η μέθοδος αρχικά εξετάζει εάν υπάρχει ήδη η λέξη που πρόκειται να εισαχθεί, για αυτό τον έλεγχο καλείται η αναζήτηση που εντοπίζει την θέση της λέξης και την αποθηκεύει σε μια μεταβλητή. Στην περίπτωση που υπάρχει ήδη, η λέξη δεν εισάγεται ξανά στον πίνακα αλλά αυξάνεται ο αριθμός των εμφανίσεων της λέξης αυτής. Αντίθετα όταν δεν υπάρχει εισάγεται στον πίνακα θέτοντας παράλληλα των αριθμό των εμφανίσεων της λέξης σε ένα (1) και η posOfLastElement αυξάνεται κατά ένα (1). Τέλος, ελέγχεται εάν το size ισούται με posOfLastElement, ο έλεγχος αυτός γίνεται για να εξεταστεί εάν ο πίνακας γέμισε. Εάν έχει γεμίσει καλείται η μέθοδος resize

---

Λειτουργίες

Εισαγωγή (insert)

Για την εισαγωγή στο ταξινομημένο πίνακα θα γίνει η χρήση της δυαδικής αναζήτησης και της ταξινόμησης με εισαγωγή. Αρχικά γίνεται η κλήση (η private insert) μια παραλλαγής της δυαδικής αναζήτησης της οποίας το αποτέλεσμα αποθηκεύετε σε μια μεταβλητή. Με παραλλαγή εννοείται πως όταν το στοιχείο υπάρχει ήδη στον πίνακα, η μεταβλητή found που περνιέται με στην συνάρτηση με αναφορά γίνεται true και επιστρέφεται η θέση του στοιχείου μέσα στον πίνακα, αντίθετα όταν το στοιχείο απουσιάζει η δυαδική αναζήτηση βρίσκει την θέση στην οποία πρέπει να τοποθετηθεί το στοιχείο για να διατηρηθεί η ταξινόμηση και η μεταβλητή found γίνεται false. Έπειτα εξετάζεται από την συνάρτηση εισαγωγής η τιμη της found, εάν είναι true αυξάνεται η τιμή της μεταβλητής appearances του Element (struct) που βρίσκεται μέσα στον πίνακα κατά ένα (1) διαφορετικά, κάθε στοιχείο το οποίο βρίσκεται δεξιά από τη θέση που θα πρέπει να εισαχθεί το νέο στοιχείο, μετακινείται κατά μια (1) θέση προς δεξιά και έπειτα το στοιχείο εισάγεται στην σωστή θέση χωρίς να διαταραχθεί η ταξινόμηση ενώ επιπλέον η posOfLastElement αυξάνεται κατά ένα (1). Τέλος, ελέγχεται εάν το size ισούται με posOfLastElement, ο έλεγχος αυτός γίνεται για να εξεταστεί εάν ο πίνακας γέμισε. Εάν έχει γεμίσει καλείται η μέθοδος resize.

Αναζήτηση (search)

Για την αναζήτηση των στοιχείων μέσα από τον πίνακα θα χρησιμοποιηθεί η δυαδική αναζήτηση (η private search) έτσι ώστε να γίνει εκμετάλλευση της ταξινόμησης και επιστρέφει την θέση του στοιχειού μέσα στον πίνακα εάν υπάρχει διαφορετικά επιστρέφει -1. Αφού βρεθεί η θέση του στοιχείου μέσα στον πίνακα επιστρέφεται ο αριθμός των εμφανίσεων της συγκεκριμένης λέξης, σε κάθε άλλη περίπτωση επιστρέφεται η τιμή μηδέν (0).

Διαγραφή (remove)

Όπως στον αταξινόμητο πίνακα, έτσι και εδώ γίνεται κλήση της συνάρτησης δυαδικής αναζήτησης (η private search) ώστε να βρεθεί η θέση της λέξης που πρόκειται να διαγραφεί. Σε περίπτωση που η λέξη εμφανίζεται περισσότερες από μια φορές, το πεδίο του struct που αποθηκεύει τον αριθμό των εμφανίσεων της λέξης (appearances). Εάν η τιμή του πεδίου πριν την κλήση της συνάρτησης είναι ένα (1) τότε, αφού κληθεί αφαιρείται η λέξη από τον πίνακα, τα στοιχεία μετακινούνται κατά μια θέση προς τα αριστερά και η μεταβλητή που αποθηκεύει την θέση του τελευταίου στοιχειού πίνακα (posOfLastElement) μειώνεται κατά ένα (1). Τέλος, εάν πραγματοποιηθεί η διαγραφή επιστρέφεται η λογική τιμή true ενώ εάν η λέξη δεν υπάρχει στον πίνακα επιστρέφεται η λογική τιμή false.