Εισαγωγή στις Ανοικτές Δομές Δεδομένων

Abstract

Το σύγγραμμα καλύπτει τη σχεδίαση, την υλοποίηση και την ανάλυση κάποιων από τις πιο γνωστές δομές δεδομένων που συναντώνται στη διεθνή βιβλιογραφία της πληροφορικής, όπως, για παράδειγμα, της στοίβας, της ουράς, της ουράς διπλού άκρου, της λίστας (υλοποιημένης σε πίνακα ή με δείκτες), της λίστας παράλειψης, διάφορων τεχνικών πινάκων κατακερματισμού, του δυαδικού δένδρου (συμπεριλαμβανομένου του δυαδικού δένδρου αναζήτησης, του δενδροσωρού, του δένδρου εξιλαστήριων θυμάτων και του ερυθρόμαυρου δένδρου), του σωρού (συμπεριλαμβανομένου του δυαδικού και του τυχαιοποιημένου συγχωνεύσιμου σωρού), του γράφου (συμπεριλαμβανομένης της αναπαράστασής του με πίνακα και με λίστα γειτνίασης), ορισμένων ειδικευμένων δομών δεδομένων για ακέραιους αριθμούς (συμπεριλαμβανομένων διάφορων μορφών δυαδικών ψηφιακών δένδρων), του Β-δένδρου κτλ. Οι αλγόριθμοι υλοποίησης των δομών δεδομένων δίνονται τόσο σε ψευδοκώδικα (βασισμένο στη γλώσσα προγραμματισμού Python), όσο και στις γλώσσες προγραμματισμού C++ και Java. Η ύλη του συγγράμματος κατανέμεται σε 14 κεφάλαια και μπορεί να καλύψει επαρκώς ένα ακαδημαϊκό πρόγραμμα διδασκαλίας 13 εβδομάδων του προπτυχιακού μαθήματος «Δομές Δεδομένων». Επιπρόσθετα, ορισμένα κεφάλαια του συγγράμματος μπορούν να αξιοποιηθούν και σε πιο προχωρημένα στάδια του ακαδημαϊκού προγράμματος σπουδών, μεταξύ άλλων και σε αντίστοιχα μαθήματα μεταπτυχιακού επιπέδου. Το σύγγραμμα εφοδιάζει τον αναγνώστη με το απαραίτητο υπόβαθρο για την αποτελεσματική χρήση των δομών δεδομένων στην υποστήριξη ενός μεγάλου φάσματος εφαρμογών στην πληροφορική. Πιο συγκεκριμένα, η ύλη του βιβλίου παρέχει στον αναγνώστη τη δυνατότητα να αναλύει την επίδοση δομών δεδομένων, να συγκρίνει την αποδοτικότητα και την καταλληλότητά τους για την επίλυση διάφορων προβλημάτων, να σχεδιάζει σύνθετες και προσαρμοσμένες ανά εφαρμογή δομές δεδομένων και να τις υλοποιεί με αποδοτικούς αλγόριθμους στη γλώσσα προγραμματισμού που επιθυμεί.

The book covers the design, implementation and analysis of some of the most well-known data structures in the literature of informatics and computer science, such as, for example, the stack, the queue, the deque, the list (implemented using an array or pointers), the skip list, several hash table methods, the binary tree (including the binary search tree, the treap, the scapegoat tree and the red-black tree), the heap (including the binary heap and the randomized meldable heap), the graph (including its representation by a matrix or as a collection of lists), some specialised data structures for integers (including various forms of binary digital trees), the B-tree, etc. The algorithms for implementing the data structures are given in pseudocode (on the basis of the Python programming language) and in the C++ and Java programming languages. The book is organised into 14 chapters and can adequately cover a 13-week academic semester for the "Data Structures" undergraduate course. In addition, some chapters of the book can be taught at a more advanced stage of the academic curriculum, including in the context of relevant postgraduate courses. The book provides the student with the necessary background for the effective use of the data structures in a wide range of application domains in informatics and computer science. The material of the book aims to enable students to analyse the performance of data structures, to compare their efficiency and suitability for solving various problems, to design complex and application-specific data structures, and to implement them with efficient algorithms in the programming language of their choice.