Μενού

Λίστες στο STL

lists stl

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

Γνωρίστε τα πάντα για τις λίστες στο STL μαζί με την εφαρμογή του.

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

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

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

Λίστες στο STL

γ # ερωτήσεις συνέντευξης με απαντήσεις

Τι θα μάθετε:

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

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

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

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

Δήλωση και αρχικοποίηση

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

#include

Η γενική δήλωση για το κοντέινερ λίστας είναι

std::list listName;

Για παράδειγμα,μπορούμε να δηλώσουμε μια λίστα με το όνομα «mylist» τύπου int ως εξής:

std::list mylist;

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

Ας δούμε πώς μπορούμε να προετοιμάσουμε τη λίστα που δημιουργήσαμε παραπάνω.

std::list mylist = {1, 1, 2, 3, 5};

Η παραπάνω προετοιμασία θα παρουσιαστεί στη μνήμη όπως φαίνεται παρακάτω:

Δήλωση και αρχικοποίηση

Μόλις αρχίσουμε τη λίστα, μπορούμε να έχουμε πρόσβαση στα στοιχεία μιας λίστας χρησιμοποιώντας έναν επαναληπτικό. Οι λειτουργίες Iterator «start» και «end» μας βοηθούν να διασχίσουμε τα στοιχεία της λίστας.

Σημείωση: Το Iterator για τη λίστα υποστηρίζει επίσης άλλους επαναληπτικούς επαναλήπτες (rbegin, rend), σταθερούς επαναληπτικούς (cbegin, cend) και σταθερούς αντίστροφους επαναληπτικούς (crbegin, crend) και μπορούν να χρησιμοποιηθούν με παρόμοιο τρόπο όπως τα διανύσματα.

Το ακόλουθο παράδειγμα δείχνει αυτό.

#include #include #include #include using namespace std; int main() { list mylist = {1, 1, 2, 3, 5}; cout<<”List elements are: “; list::iterator it; for(it=mylist.begin();it!=mylist.end();++it) cout<<*it<<” “; }

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 2 3 5

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

Τώρα ας περάσουμε στις λειτουργίες ή τις λειτουργίες που μας παρέχει το κοντέινερ στο STL.

Λειτουργίες λίστας

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

ένθετο (pos, num_elem, elem)

Που,

pos => Θέση στην οποία θα εισαχθούν νέα στοιχεία.
num_elem => Αριθμός στοιχείων που θα εισαχθούν · προεπιλογές στο 1.
αντικείμενο => Πραγματική τιμή που θα εισαχθεί.

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

#include #include // for list operations using namespace std; int main() { list mylist = {1,1,2}; list::iterator it = mylist.begin(); // iterator to point to 4th position advance(it,` 3); // inserts 3 at 4th position mylist.insert(it, 3); cout << 'The list after inserting' << ' 1 element using insert() is : '; for (list::iterator i = mylist.begin();i != mylist.end();i++) cout << *i << ' '; cout << endl; }

Παραγωγή:

Η λίστα μετά την εισαγωγή 1 στοιχείου χρησιμοποιώντας το ένθετο () είναι: 1 1 2 3

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

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

  • push_back :Προσθέτει ένα νέο στοιχείο στο τέλος της λίστας.
  • push_front :Προσθέτει ένα νέο στοιχείο στην αρχή της λίστας.

Ας δούμε ένα παράδειγμα που δείχνει τη χρήση των λειτουργιών push_back και push_front.

#include #include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3}; cout<<'List elements are: '; printlist(mylist); mylist.push_front(0); mylist.push_back(5); cout<<' List contents after push_front and push_back: '; printlist(mylist); }

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 2 3

Λίστα περιεχομένων μετά από push_front και push_back: 0 1 1 2 3 5

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

  • pop_back :Αφαιρεί το τελευταίο στοιχείο στη λίστα συρρικνώνοντας έτσι το μέγεθος της λίστας κατά 1.
  • pop_front :Αφαιρεί το πρώτο στοιχείο στη λίστα συρρικνώνοντας έτσι το μέγεθος της λίστας κατά 1.

Το ακόλουθο παράδειγμα δείχνει τη χρήση των pop_back και pop_front λειτουργιών της λίστας.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); mylist.pop_front(); mylist.pop_back(); cout<<' List contents after push_front and push_back: '; printlist(mylist); }

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 2 3 5

Λίστα περιεχομένων μετά από push_front και push_back: 1 2 3

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

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

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

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<'size of the list: '<

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 2 3 5
μέγεθος της λίστας: 5
Λίστα μετά τη διαγραφή του πρώτου στοιχείου: 1 2 3 5
Νέο μέγεθος της λίστας: 4
μέγεθος της λίστας μετά από διαγραφή: 0

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

  • εμπρός :Επιστρέφει την τιμή του πρώτου στοιχείου της λίστας.
  • πίσω :Επιστρέφει την τιμή του τελευταίου στοιχείου της λίστας.
  • ανταλαγή :Ανταλλάσσει τα περιεχόμενα μιας λίστας με τα περιεχόμενα μιας άλλης λίστας ίδιου μεγέθους και τύπου.
  • ΑΝΤΙΣΤΡΟΦΗ :Ένας αλγόριθμος που αντιστρέφει τη λίστα.
  • είδος :Ταξινόμηση της δεδομένης λίστας.

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

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<' Front of the list: '<

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 2 3 5

Μπροστά από τη λίστα: 1
Πίσω μέρος της λίστας: 5

Αντίστροφη λίστα: 5 3 2 1 1

Περιεχόμενα περιττής λίστας: 1 3 5 7 9

Μετά την ανταλλαγή

mylist: 1 3 5 7 9
Oddlist: 5 3 2 1 1

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

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

Και οι δύο λίστες πρέπει να είναι του ίδιου τύπου.

ματίσματος (θέση, λίστα);

που,

position => Θέση στην οποία θα μεταφερθούν τα περιεχόμενα της λίστας.
list => Λίστα των οποίων τα στοιχεία πρόκειται να μεταφερθούν.

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

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 8,13}; cout<<'List elements are: '; printlist(mylist); list seclist = {2,3,5}; cout<<'list to be spliced: '; printlist(seclist); list:: iterator it = mylist.begin(); it ++; it++; mylist.splice(it,seclist); cout<<' List contents after splicing at position 2: '; printlist(mylist); }

Παραγωγή:

Τα στοιχεία λίστας είναι: 1 1 8 13
λίστα που θα ματιστεί: 2 3 5

Λίστα περιεχομένων μετά τη συναρμολόγηση στη θέση 2: 1 1 2 3 5 8 13

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

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

Δίνεται παρακάτω είναι ένα παράδειγμα για την απόδειξη της συνάρτησης συγχώνευσης.

καλύτερο δωρεάν τείχος προστασίας για τα Windows 10 2018
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1,2,3,5,8}; list seclist = {4,6,7}; cout<<'First List: '; printlist(mylist); cout<

Παραγωγή:

Πρώτη λίστα: 11 2 3 5 8
Δεύτερη λίστα: 4 6 7

Λίστα περιεχομένων μετά τη συγχώνευση δύο λιστών:
1 1 2 3 4 5 6 7 8

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

συμπέρασμα

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

=> Δείτε εδώ για να δείτε τα εκπαιδευτικά σεμινάρια A-Z Of C ++.

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

^