Ένας από τους τύπους δομών δεδομένων που αποτελούν την άμεση ενσωμάτωση των μαθηματικών οντοτήτων στην επιστήμη των υπολογιστών είναι σύνολα. Οι λειτουργίες μαζί τους βασίζονται συχνά σε διάφορους αλγόριθμους. Διαφορετικές γλώσσες προγραμματισμού έχουν τα δικά τους μέσα για την περιγραφή συνόλων.
Απαραίτητη
- - περιβάλλον ανάπτυξης ·
- - μεταφραστής από την επιλεγμένη γλώσσα προγραμματισμού.
Οδηγίες
Βήμα 1
Περιγράψτε το σετ χρησιμοποιώντας τη γλώσσα προγραμματισμού, εάν υπάρχει. Για παράδειγμα, στη γλώσσα Pascal υπάρχει ένα σύνολο δομών που σας επιτρέπει να δηλώσετε τους αντίστοιχους τύπους. Είναι αλήθεια ότι ο όγκος τέτοιων συνόλων δεν πρέπει να υπερβαίνει τα 256 στοιχεία. Ένα παράδειγμα δηλώσεων καθορισμένου τύπου μπορεί να μοιάζει με αυτό:
τύπος
AZLetters = σύνολο "A".. "Z";
AllLetters = σύνολο char;
Οι μεταβλητές και οι σταθερές των τύπων που είναι σύνολα δηλώνονται με τον συνηθισμένο τρόπο. Σε αυτήν την περίπτωση, τα καθορισμένα γράμματα μπορούν να χρησιμοποιηθούν για την προετοιμασία. Για παράδειγμα:
υπ
LettersSet1: AZLetters = ['A', 'B', 'C'];
Βήμα 2
Χρησιμοποιήστε τις δυνατότητες των τυπικών βιβλιοθηκών ή ενοτήτων για να περιγράψετε σύνολα. Έτσι, η βιβλιοθήκη προτύπων C ++, η οποία θα πρέπει να παρέχεται με τον μεταγλωττιστή, περιλαμβάνει ένα πρότυπο για την κατηγορία κοντέινερ συνόλου που εφαρμόζει τη λειτουργικότητα των συνόλων:
πρότυπο <
Κλειδί τάξης, Χαρακτηριστικά τάξης = λιγότερα, τάξη Allocator = κατανεμητής
σύνολο τάξεων
Όπως μπορείτε να δείτε από την λίστα, τα ορίσματα του προτύπου συνόλου είναι: ο τύπος δεδομένων των στοιχείων του συνόλου, ο τύπος του λειτουργικού αντικειμένου για τον προσδιορισμό της σειράς των στοιχείων στο σύνολο και ο τύπος του εκχωρητή μνήμης. Σε αυτήν την περίπτωση, απαιτείται μόνο το πρώτο όρισμα (όπως τα άλλα δύο, το τυπικό δυαδικό predicate λιγότερο και ο τυπικός εκχωρητής χρησιμοποιούνται από προεπιλογή).
Βήμα 3
Εφαρμόστε τάξεις ή πρότυπα κλάσης που χρησιμοποιούνται για την ανάπτυξη πλαισίων που εφαρμόζουν τη λειτουργικότητα της εργασίας με σύνολα, εάν υπάρχουν. Ένα παράδειγμα ενός τέτοιου εργαλείου είναι η κλάση προτύπων QSet της μονάδας QtCore της βιβλιοθήκης Qt. Οι δυνατότητές του είναι παρόμοιες με εκείνες του κοντέινερ STL που περιγράφονται στο προηγούμενο βήμα.
Βήμα 4
Περιγράψτε το σετ χρησιμοποιώντας τα δικά σας μέσα υλοποίησης. Χρησιμοποιήστε σημαίες bit, αποθηκευμένες σε συστοιχίες σταθερού μήκους, για σύνολα στοιχείων απλών τύπων και μικρών μεγεθών. Εφαρμόστε μια καθορισμένη κλάση κοντέινερ για σύνθετους τύπους δεδομένων. Ως βάση, μπορείτε να χρησιμοποιήσετε τη λειτουργικότητα των συσχετιζόμενων ή κατακερματισμένων συστοιχιών. Αυτό, με τη σειρά του, μπορεί να οικοδομηθεί με βάση δέντρα δυαδικής αναζήτησης αυτο-εξισορρόπησης (για παράδειγμα, κόκκινα-μαύρα δέντρα).
