Δομές δεδομένων και αλγόριθμοι: ένας πλήρης οδηγός για προγραμματιστές

Informatec Digital » Πόροι » Δομές δεδομένων και αλγόριθμοι: ένας πλήρης οδηγός για προγραμματιστές

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

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

Τι είναι οι δομές δεδομένων και οι αλγόριθμοι;

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

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

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

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

Από θεωρητική άποψη, συγγραφείς όπως ο Niklaus Wirth διέδωσαν την ιδέα ήδη από τη δεκαετία του 70 ότι αλγόριθμοι + δομές δεδομένων = προγράμματαΔεκαετίες αργότερα, παραμένει εξίσου αληθινό: δεν έχει σημασία αν προγραμματίζετε σε Java, Python, C++ ή αν προέρχεστε από ένα bootcamp, αυτό που θα απαιτηθεί από εσάς σε συνεντεύξεις και σοβαρά projects είναι να ξέρετε πώς να επιλέγετε και να συνδυάζετε καλά και τα δύο στοιχεία.

Γιατί είναι τόσο σημαντικά στον προγραμματισμό;

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

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

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

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

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

Προαπαιτούμενα και απαραίτητα θεμέλια

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

Βοηθάει επίσης πολύ να κατανοήσουμε την ιδέα του αλγοριθμική πολυπλοκότητα και συμβολισμός Big O: πώς αυξάνεται ο χρόνος εκτέλεσης ή η χρήση μνήμης καθώς αυξάνεται το μέγεθος των δεδομένων (n). Η γνώση του τρόπου διάκρισης μεταξύ O(1), O(log n), O(n), O(n log n) και O(n²) σάς επιτρέπει να συγκρίνετε εναλλακτικές λύσεις με ορθή κρίση και να δικαιολογήσετε τις αποφάσεις σας.

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

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

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

Οι πιο συχνά χρησιμοποιούμενες δομές δεδομένων

Στην επιστήμη των υπολογιστών υπάρχουν πολλές δομές δεδομένωνΩστόσο, υπάρχει μια ομάδα «βασικών» συναρτήσεων που επαναλαμβάνονται ξανά και ξανά: πίνακες (διανύσματα), στοίβες, ουρές, συνδεδεμένες λίστες, δέντρα, γραφήματα, δοκιμές και πίνακες κατακερματισμού. Η κατανόηση του τρόπου λειτουργίας τους, των λειτουργιών που προσφέρουν και του τυπικού κόστους τους είναι το κλειδί για την ομαλή λειτουργία του προγραμματισμού.

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

Πίνακες

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

Φανταστείτε έναν πίνακα μεγέθους 4 που περιέχει τις τιμές 1, 2, 3 και 4. Κάθε θέση έχει ένα Άνδρος (0, 1, 2, 3) και μπορείτε να έχετε άμεση πρόσβαση σε οποιοδήποτε στοιχείο με τον δείκτη του σε σταθερό χρόνο O(1). Αυτό καθιστά τους πίνακες πολύ αποτελεσματικούς για τυχαία ανάγνωση.

Υπάρχουν δύο κύριες κατηγορίες: μονοδιάστατοι πίνακες (μία μόνο σειρά στοιχείων) και πολυδιάστατοι πίνακες (για παράδειγμα, πίνακες, οι οποίοι είναι πίνακες από πίνακες). Πολλές γλώσσες προγραμματισμού προσφέρουν και τις δύο παραλλαγές εγγενώς ή με μικρές διαφορές στη σύνταξη και την απόδοση.

Οι βασικές λειτουργίες σε έναν πίνακα είναι συνήθως:

• Εισάγω: τοποθέτηση ενός στοιχείου σε μια συγκεκριμένη θέση, η οποία σε στατικούς πίνακες μπορεί να περιλαμβάνει μετατόπιση άλλων στοιχείων.
• Παίρνω: πρόσβαση στο στοιχείο σε ένα δεδομένο δείκτη, συνήθως O(1).
• Διαγράφω: διαγραφή ή επισήμανση ως κενού του στοιχείου σε μια συγκεκριμένη θέση, συνήθως μετατοπίζοντας τα στοιχεία προς τα αριστερά.
• Μέγεθος: ελέγχει πόσα στοιχεία είναι αποθηκευμένα ή τη μέγιστη χωρητικότητα του πίνακα.

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

Στοίβες

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

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

Οι τυπικές λειτουργίες στοίβας είναι:

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

Στο πλαίσιο των συνεντεύξεων, παρατηρούνται προβλήματα όπως τα ακόλουθα: αξιολόγηση εκφράσεων σε σημειογραφία postfix (RPN), ταξινόμηση στοιχείων χρησιμοποιώντας μόνο στοίβες ή έλεγχος εάν μια συμβολοσειρά παρενθέσεων (και άλλων συμβόλων) είναι σωστά ισορροπημένη χρησιμοποιώντας push and pop.

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

Ουρές

Η ουρά Είναι μια άλλη γραμμική δομή δεδομένων, αλλά αντί να ακολουθεί την αρχή LIFO, χρησιμοποιεί το μοντέλο FIFO: Πρώτος μέσα, πρώτος έξω. Η πιο ξεκάθαρη αναλογία είναι μια ουρά ανθρώπων που περιμένουν σε ένα ταμείο εισιτηρίων κινηματογράφου.

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

Οι βασικές λειτουργίες ουράς περιλαμβάνουν:

• Ουρά: εισαγωγή ενός νέου στοιχείου στο τέλος της ουράς.
• Ντεκουέ: αφαίρεση και επιστροφή του στοιχείου που βρίσκεται στην αρχή.
• Μπροστά ή πάνω: συμβουλευτείτε το πρώτο στοιχείο χωρίς να το αφαιρέσετε.
• είναι άδειο: ελέγξτε αν η ουρά είναι άδεια.

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

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

Συνδεδεμένες λίστες

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

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

Υπάρχουν δύο κύριες παραλλαγές:

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

Τυπικές λειτουργίες σε συνδεδεμένες λίστες περιλαμβάνουν:

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

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

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

Άρμπολς

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

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

Υπάρχουν πολλές ποικιλίες δέντρων, όπως:

• Δέντρο N-ary: κάθε κόμβος μπορεί να έχει έναν μεταβλητό (και πιθανώς μεγάλο) αριθμό παιδιών.
• Ισορροπημένο δέντρο: διατηρεί τα κλαδιά του σε παρόμοιο βάθος για να αποφευχθεί η υποβάθμιση της απόδοσης.
• Δυαδικό δέντρο: κάθε κόμβος έχει το πολύ δύο παιδιά (αριστερό και δεξί).
• Δυαδικό Δέντρο Αναζήτησης (BST): δυαδικό δέντρο με την ιδιότητα ότι όλα στα αριστερά ενός κόμβου είναι μικρότερα και όλα στα δεξιά είναι μεγαλύτερα (σύμφωνα με κάποιο κριτήριο ταξινόμησης).
• Δέντρο AVL, κόκκινο-μαύρο, 2-3 και άλλες παραλλαγέςΑυτά είναι ισορροπημένα δέντρα αναζήτησης που εγγυώνται καλά όρια πολυπλοκότητας στις λειτουργίες εισαγωγής, διαγραφής και αναζήτησης.

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

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

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

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

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

Στον κώδικα, τα γραφήματα συνήθως αναπαρίστανται με δύο βασικούς τρόπους:

• Πίνακας γειτνίασης: ένας πίνακας όπου το κελί υποδεικνύει εάν υπάρχει ακμή μεταξύ της κορυφής i και του j (και πιθανώς το βάρος της σύνδεσης).
• Λίστα γειτνίασης: για κάθε κορυφή αποθηκεύεται μια λίστα με τους γείτονές της, η οποία εξοικονομεί μνήμη σε αραιά γραφήματα.

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

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

Προσπαθεί ή προθέτει δέντρα

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

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

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

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

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

Πίνακες κατακερματισμού και κατακερματισμός

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

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

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

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

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

Πώς σχετίζονται οι αλγόριθμοι και οι δομές δεδομένων

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

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

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

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

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

Πώς να μάθετε δομές δεδομένων και αλγόριθμους

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

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

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

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

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

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

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

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