Μενού

Εισαγωγή στις δομές δεδομένων στο C ++

introduction data structures c

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Ένα εισαγωγικό σεμινάριο για τις δομές δεδομένων στο C ++.

«Η δομή δεδομένων μπορεί να οριστεί ως μια οργανωμένη συλλογή δεδομένων που βοηθά ένα πρόγραμμα να έχει πρόσβαση σε δεδομένα αποτελεσματικά και γρήγορα, έτσι ώστε ολόκληρο το πρόγραμμα να μπορεί να λειτουργεί με αποτελεσματικό τρόπο. «

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

=> Δείτε εδώ για να εξερευνήσετε τη λίστα με τα πλήρη σεμινάρια C ++.

Εισαγωγή στις δομές δεδομένων στο C ++ (1)

Τι θα μάθετε:

ΣΦΑΙΡΙΚΗ ΕΙΚΟΝΑ

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

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

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

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

Ας δούμε μερικούς από τους όρους που χρησιμοποιούμε κατά την εξέταση των δομών δεδομένων:

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

Παράδειγμα - Δομή δεδομένων

  • Δεδομένα: Είναι η στοιχειώδης τιμή. Στο παραπάνω σχήμα, ο αριθμός μαθητή μπορεί να είναι δεδομένα.
  • Στοιχείο ομάδας: Αυτό είναι το στοιχείο δεδομένων που έχει περισσότερα από ένα δευτερεύοντα στοιχεία. Στο παραπάνω σχήμα, το Όνομα_Μαθητή έχει Όνομα και Επώνυμο.
  • Ρεκόρ: Είναι μια συλλογή στοιχείων δεδομένων. Στο παραπάνω παράδειγμα, στοιχεία δεδομένων όπως ο αριθμός του μαθητή, το όνομα, η τάξη, η ηλικία, ο βαθμός κ.λπ. σχηματίζουν μια εγγραφή μαζί.
  • Οντότητα: Είναι μια κατηγορία δίσκων. Στο παραπάνω διάγραμμα, ο μαθητής είναι μια οντότητα.
  • Χαρακτηριστικό ή πεδίο: Οι ιδιότητες μιας οντότητας ονομάζονται χαρακτηριστικά και κάθε πεδίο αντιπροσωπεύει ένα χαρακτηριστικό.
  • Αρχείο: Ένα αρχείο είναι μια συλλογή εγγραφών. Στο παραπάνω παράδειγμα, μια φοιτητική οντότητα μπορεί να έχει χιλιάδες αρχεία. Έτσι, ένα αρχείο θα περιέχει όλες αυτές τις εγγραφές.

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

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

Ας συζητήσουμε την ανάγκη για δομή δεδομένων στον Προγραμματισμό.

Ανάγκη για δομή δεδομένων στον προγραμματισμό

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

Συνήθως, ανά πάσα στιγμή, η εφαρμογή ενδέχεται να αντιμετωπίσει τα ακόλουθα εμπόδια:

# 1) Αναζήτηση μεγάλων ποσοτήτων δεδομένων: Με την επεξεργασία και αποθήκευση μεγάλου όγκου δεδομένων, ανά πάσα στιγμή το πρόγραμμα μας ενδέχεται να απαιτείται για την αναζήτηση συγκεκριμένων δεδομένων. Εάν τα δεδομένα είναι πολύ μεγάλα και δεν είναι σωστά οργανωμένα, θα χρειαστεί πολύς χρόνος για τη λήψη των απαιτούμενων δεδομένων.

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

# 2) Ταχύτητα επεξεργασίας: Τα μη οργανωμένα δεδομένα μπορεί να οδηγήσουν σε αργή ταχύτητα επεξεργασίας, καθώς θα σπαταληθεί πολύς χρόνος κατά την ανάκτηση και την πρόσβαση στα δεδομένα.

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

# 3) Πολλαπλά ταυτόχρονα αιτήματα: Πολλές εφαρμογές αυτές τις μέρες πρέπει να υποβάλουν ταυτόχρονα αίτημα για δεδομένα. Αυτά τα αιτήματα πρέπει να υποβάλλονται σε αποτελεσματική επεξεργασία για την ομαλή εκτέλεση των εφαρμογών.

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

Ταξινόμηση δομής δεδομένων

Οι δομές δεδομένων που χρησιμοποιούνται στο C ++ μπορούν να ταξινομηθούν ως εξής.

Ταξινόμηση δομών δεδομένων

Η δομή δεδομένων είναι ένας τρόπος οργάνωσης των δεδομένων. Έτσι μπορούμε να ταξινομήσουμε τις δομές δεδομένων όπως εμφανίζονται σε πρωτόγονες ή τυπικές δομές δεδομένων και μη πρωτόγονες ή καθορισμένες από τον χρήστη δομές δεδομένων.

Έχουμε δει όλους τους τύπους δεδομένων που υποστηρίζονται στο C ++. Καθώς αυτός είναι επίσης ένας τρόπος οργάνωσης δεδομένων, λέμε ότι είναι μια τυπική δομή δεδομένων.

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

Γραμμική δομή δεδομένων

Οι γραμμικές δομές δεδομένων έχουν όλα τα στοιχεία τους διατεταγμένα με γραμμικό ή διαδοχικό τρόπο. Κάθε στοιχείο σε μια γραμμική δομή δεδομένων έχει έναν προκάτοχο (προηγούμενο στοιχείο) και έναν διάδοχο (επόμενο στοιχείο)

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

Το πιο δημοφιλές παράδειγμα γραμμικής στατικής δομής δεδομένων είναι ένας πίνακας.

Πίνακας

Ένας πίνακας είναι μια διαδοχική συλλογή στοιχείων του ίδιου τύπου. Κάθε στοιχείο του πίνακα μπορεί να προσεγγιστεί χρησιμοποιώντας τη θέση του στον πίνακα που ονομάζεται ευρετήριο ή δείκτης του πίνακα. Το όνομα του πίνακα δείχνει το πρώτο στοιχείο του πίνακα.

πίνακας

Το παραπάνω που εμφανίζεται είναι ένας πίνακας «a» από στοιχεία n. Τα στοιχεία αριθμούνται από 0 έως n-1. Το μέγεθος του πίνακα (n σε αυτή την περίπτωση) ονομάζεται επίσης η διάσταση του πίνακα. Όπως φαίνεται στο παραπάνω σχήμα, το όνομα του πίνακα δείχνει το πρώτο στοιχείο του πίνακα.

Ο πίνακας είναι η απλούστερη δομή δεδομένων και είναι αποτελεσματικός καθώς τα στοιχεία μπορούν να προσπελαστούν απευθείας χρησιμοποιώντας συνδρομητές. Αν θέλουμε να αποκτήσουμε πρόσβαση στο τρίτο στοιχείο του πίνακα τότε απλά πρέπει να πούμε ένα (2).

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

Οι δημοφιλείς γραμμικές δυναμικές δομές δεδομένων είναι λίστα, στοίβα και ουρά.

Συνδεδεμένη λίστα

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

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

Συνδεδεμένη λίστα

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

Σωρός

Η στοίβα είναι μια γραμμική δομή δεδομένων στην οποία τα στοιχεία μπορούν να προστεθούν ή να αφαιρεθούν μόνο από το ένα άκρο γνωστό ως 'Κορυφή' της στοίβας. Με αυτόν τον τρόπο, η στοίβα εμφανίζει τύπο πρόσβασης μνήμης LIFO (Last In, First Out).

Σωρός

Όπως φαίνεται παραπάνω, τα στοιχεία στη στοίβα προστίθενται πάντα στο ένα άκρο και αφαιρούνται επίσης από το ίδιο άκρο. Αυτό ονομάζεται «Κορυφή» της στοίβας. Όταν προστίθεται ένα στοιχείο, ωθείται προς τα κάτω και η κορυφή της στοίβας αυξάνεται κατά μία θέση.

Ομοίως, όταν αφαιρείται ένα στοιχείο, το πάνω μέρος της στοίβας μειώνεται. Όταν μια στοίβα είναι άδεια, το πάνω μέρος της στοίβας έχει οριστεί σε -1. Υπάρχουν δύο κύριες λειτουργίες 'Push' και 'Pop' που εκτελούνται στη στοίβα.

Ουρά

Η ουρά είναι μια ακόμη γραμμική δομή δεδομένων στην οποία τα στοιχεία προστίθενται στο ένα άκρο που ονομάζεται «πίσω» και διαγράφονται από ένα άλλο άκρο που ονομάζεται «εμπρός». Η ουρά δείχνει το FIFO (First In, First Out) τον τύπο της μεθοδολογίας πρόσβασης στη μνήμη.

Ουρά

Το παραπάνω διάγραμμα δείχνει μια ουρά με πίσω και εμπρός άκρα. Όταν η ουρά είναι άδεια, οι πίσω και οι μπροστινοί δείκτες συμπίπτουν μεταξύ τους.

Μη γραμμική δομή δεδομένων

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

Οι μη γραμμικές δομές δεδομένων είναι Δέντρα και Γραφήματα.

Η προεπιλεγμένη πύλη δεν είναι διαθέσιμη Windows 10 2019

Δέντρα

Τα δέντρα είναι μη γραμμικές πολυεπίπεδες δομές δεδομένων που έχουν ιεραρχική σχέση μεταξύ των στοιχείων. Τα στοιχεία του δέντρου ονομάζονται Κόμβοι.

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

Δέντρα

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

Γραφικές παραστάσεις

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

Γραφικές παραστάσεις

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

Λειτουργίες στη δομή δεδομένων

Όλες οι δομές δεδομένων εκτελούν διάφορες λειτουργίες στα στοιχεία της.

Αυτά είναι κοινά σε όλες τις δομές δεδομένων και παρατίθενται ως εξής:

  • Ερευνητικός: Αυτή η λειτουργία εκτελείται για την αναζήτηση ενός συγκεκριμένου στοιχείου ή ενός κλειδιού. Οι πιο συνηθισμένοι αλγόριθμοι αναζήτησης είναι διαδοχική / γραμμική αναζήτηση και δυαδική αναζήτηση.
  • Ταξινόμηση: Η λειτουργία ταξινόμησης περιλαμβάνει τη διευθέτηση των στοιχείων σε μια δομή δεδομένων με μια συγκεκριμένη σειρά είτε αύξουσα είτε φθίνουσα. Υπάρχουν διάφοροι αλγόριθμοι ταξινόμησης που είναι διαθέσιμοι για δομές δεδομένων. Τα πιο δημοφιλή μεταξύ αυτών είναι το Quicksort, το είδος επιλογής, το είδος συγχώνευσης κ.λπ.
  • Εισαγωγή: Η λειτουργία εισαγωγής ασχολείται με την προσθήκη ενός στοιχείου στη δομή δεδομένων. Αυτή είναι η πιο σημαντική λειτουργία και ως αποτέλεσμα της προσθήκης ενός στοιχείου, η διάταξη αλλάζει και πρέπει να προσέξουμε ότι η δομή των δεδομένων παραμένει ανέπαφη.
  • Διαγραφή: Η λειτουργία διαγραφής αφαιρεί ένα στοιχείο από τη δομή δεδομένων. Οι ίδιες προϋποθέσεις που πρέπει να ληφθούν υπόψη για την εισαγωγή πρέπει να πληρούνται και στην περίπτωση της λειτουργίας διαγραφής.
  • Διασχίζοντας: Λέμε ότι διασχίζουμε μια δομή δεδομένων όταν επισκέπτονται κάθε στοιχείο της δομής. Απαιτείται διέλευση για την εκτέλεση συγκεκριμένων συγκεκριμένων λειτουργιών στη δομή δεδομένων.

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

Πλεονεκτήματα της δομής δεδομένων

  • Αφαίρεση: Οι δομές δεδομένων συχνά εφαρμόζονται ως αφηρημένοι τύποι δεδομένων. Οι χρήστες έχουν πρόσβαση μόνο στην εξωτερική διεπαφή χωρίς να ανησυχούν για την υποκείμενη εφαρμογή. Έτσι, η δομή δεδομένων παρέχει ένα επίπεδο αφαίρεσης.
  • Αποδοτικότητα: Η σωστή οργάνωση των δεδομένων έχει ως αποτέλεσμα την αποτελεσματική πρόσβαση στα δεδομένα καθιστώντας τα προγράμματα πιο αποτελεσματικά. Δεύτερον, μπορούμε να επιλέξουμε τη σωστή δομή δεδομένων ανάλογα με τις απαιτήσεις μας.
  • Επαναχρησιμοποίηση: Μπορούμε να επαναχρησιμοποιήσουμε τις δομές δεδομένων που έχουμε σχεδιάσει. Μπορούν επίσης να συγκεντρωθούν σε μια βιβλιοθήκη και να διανεμηθούν στον πελάτη.

συμπέρασμα

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

Στα επόμενα σεμινάριά μας, θα διερευνήσουμε περισσότερα σχετικά με τις δομές δεδομένων μαζί με τις διάφορες τεχνικές αναζήτησης και ταξινόμησης.

=> Κάντε κλικ εδώ για την σειρά απόλυτης προπόνησης C ++.

Συνιστώμενη ανάγνωση

^