Κοινή χρήση τεχνολογίας

[C Elementary] Προκαταρκτική κατανόηση της κλάσης λίστας

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Τυπική βιβλιοθήκηλίσταείδος

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

Όταν χρησιμοποιείτε την κλάση λίστας, πρέπει να συμπεριλάβετε το αρχείο κεφαλίδας<list>

2. Κοινές διεπαφές κλάσης λίστας

1. Κατασκευαστές που χρησιμοποιούνται συνήθως

1. Προεπιλεγμένος κατασκευαστής, δημιουργεί μια κενή συνδεδεμένη λίστα

list();

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. }

2. Κατασκευάστε ένα αντικείμενο λίστας και αρχικοποιήστε το με n vals

list(size_type n, const value_type& val =  value_type());

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	for (auto i : lt)
  5. 	{
  6. 		cout << i << " ";
  7. 	}
  8. }

αποτέλεσμα λειτουργίας:

3.Αντιγραφή κατασκευαστή της κλάσης λίστας

list(const list& x);

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	list<int> lt1(lt);
  5. 	for (auto i : lt1)
  6. 	{
  7. 		cout << i << " ";
  8. 	}
  9. }

αποτέλεσμα λειτουργίας:

4. Χρησιμοποιήστε τον κατασκευαστή αρχικοποίησης του επαναλήπτη

  1. Template<class InputIterator>
  2.  
  3. list(InputIterator first, InputIterator last);

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	list<int> lt1(lt.begin(), lt.end());
  5. 	for (auto i : lt1)
  6. 	{
  7. 		cout << i << " ";
  8. 	}
  9. }

αποτέλεσμα λειτουργίας:

2. Διασυνδέσεις χωρητικότητας που χρησιμοποιούνται συνήθως

Είναι ακόμα το ίδιο, επιτρέψτε μου να το συζητήσουμε μαζί εδώ.

1.μέγεθος, κενό, μέγιστο_μέγεθος, αλλαγή μεγέθους

Μέγεθος:ΕΠΙΣΤΡΟΦΗσυνδεδεμένη λίσταΟ αριθμός των στοιχείων στο δοχείο.

size_type size() const;

αδειάζω:ΕΠΙΣΤΡΟΦΗλίσταΕάν το δοχείο είναι άδειο (δηλΜέγεθοςείναι 0).
(Σημείωση: Αυτή η λειτουργία δεν τροποποιεί το κοντέινερ με κανέναν τρόπο. Για εκκαθάρισησυνδεδεμένη λίσταΤα περιεχόμενα του δοχείου, βλλίστα:: σαφής。）

bool empty() const;

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

size_type max_size() const;

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

void resize (size_type n, value_type val = value_type());

Για παράδειγμα:

  1. ​
  2. void test()
  3. {
  4. 	list<int> lt(3, 1);
  5. 	/*list<int> lt1(lt);*/
  6. 	list<int> lt1(lt.begin(), lt.end());
  7. 	list<int> lt2;
  8. 	cout << lt1.size() <<endl;
  9. 	cout << lt1.empty() <<endl;
  10. 	cout << lt2.empty() <<endl;
  11. 	lt1.resize(10);
  12. 	cout << lt1.size() << endl;
  13. 	for (auto i : lt1)
  14. 	{
  15. 		cout << i << " ";
  16. 	}
  17. }
  18.  
  19. ​

αποτέλεσμα λειτουργίας:

3. Κοινή πρόσβαση και διάβαση

1.Iterator

  1. iterator begin();
  2.  
  3. const_iterator begin() const;
  4.  
  5. iterator end();
  6.  
  7. const_iterator end() const;

Iterator: χρησιμοποιείται για τη λήψη της θέσης του πρώτου κόμβου και του τελευταίου κόμβου στη συνδεδεμένη λίσταΕπόμενη θέση (δηλαδή θέση φρουρού)

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt(5, 2);
  4. 	list<int> ::iterator it = lt.begin();
  5. 	while (it != lt.end())
  6. 	{
  7. 		cout << *it << " ";
  8. 		++it;
  9. 	}
  10. }

αποτέλεσμα λειτουργίας:

2. Αντίστροφος επαναλήπτης

reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

Αντίστροφος επαναλήπτης, το rbegin παίρνει τη θέση του τελευταίου κόμβου στο κοντέινερ, το rend παίρνει τη θέση του bit φρουρού στο κοντέινερ

  1. void test()
  2. {
  3. 	list<int> lt = { 1,23,4,4,5,2 };
  4. 	list<int> ::reverse_iterator rit = lt.rbegin();
  5. 	while (rit != lt.rend())
  6. 	{
  7. 		cout << *rit << " ";
  8. 		++rit;
  9. 	}
  10. }

αποτέλεσμα λειτουργίας:

Σημείωση: Το reverse iterator rit θα πρέπει επίσης να χρησιμοποιεί ++ αντί για --

3.μπρος πισω

εμπρός:

front reference();

const_reference front() const;

Επιστρέφει μια αναφορά στα δεδομένα που είναι αποθηκευμένα στον πρώτο κόμβο στη συνδεδεμένη λίστα

πίσω:

αναφορά πίσω();

const_reference back() const;

Επιστρέφει μια αναφορά στα δεδομένα που είναι αποθηκευμένα στον τελευταίο κόμβο της συνδεδεμένης λίστας

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.front() << endl;
  5. 	cout << lt.back() << endl;
  6.  
  7. }

αποτέλεσμα λειτουργίας:

4.Προσθήκη, διαγραφή, έλεγχος και τροποποίηση λίστας

1) push_front και pop_front

Το push_front ονομάζεται εισαγωγή κεφαλής, εισάγοντας ένα στοιχείο από την κεφαλή της συνδεδεμένης λίστας

void push_front(const value_type& val);

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

void pop_front();

void pop_front();

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.front() << endl;
  5. 	lt.push_front(21345);
  6. 	cout << lt.front() << endl;
  7. 	lt.pop_front();
  8. 	cout << lt.front() << endl;
  9. }

αποτέλεσμα λειτουργίας:

2) push_back και pop_back

Το push_back ονομάζεται εισαγωγή ουράς, εισάγοντας ένα στοιχείο από το τέλος της συνδεδεμένης λίστας

void push_back(const value_type& val);

Το pop_back ονομάζεται διαγραφή ουράς, το οποίο διαγράφει ένα στοιχείο από το τέλος της συνδεδεμένης λίστας.

void pop_back();

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.back() << endl;
  5. 	lt.push_back(21345);
  6. 	cout << lt.back() << endl;
  7. 	lt.pop_back();
  8. 	cout << lt.back() << endl;
  9. }

αποτέλεσμα λειτουργίας:

3) βρείτε

  1. template <class InputIterator, class T>
  2.  
  3. InputIterator find(InputIterator first, InputIterator last, const T& val);

Βρείτε το val στο εύρος δύο επαναλήψεων και επιστρέψτε τον επαναλήπτη στο σημείο που βρίσκεται

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	*pos = 114514;
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

αποτέλεσμα λειτουργίας:

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

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

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

4) εισάγετε

Εισαγωγή επαναλήπτη (θέση επαναλήπτη, τιμή_συνθήκης& val);

void insert(θέση επαναλήπτη, size_type n, const value_type& val);

————————————————————————————————————————

πρότυπο<class InputIterator>

void insert(θέση επαναλήπτη, πρώτος InputIterator, τελευταίος InputIterator).

Εισαγάγετε ένα ή περισσότερα στοιχεία μπροστά από τη θέση

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	lt.insert(pos, 8848);
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

αποτέλεσμα λειτουργίας:

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

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

5) σβήνω

  1. iterator erase(iterator position);
  2.  
  3. iterator erase(iterator first, iterator last);

Διαγράψτε το στοιχείο στη θέση ή όλα τα στοιχεία στο εύρος [πρώτο, τελευταίο)

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	lt.erase(lt.begin());
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

αποτέλεσμα λειτουργίας:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
  9. 	lt.erase(lt.begin(),pos);
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

αποτέλεσμα λειτουργίας:

6) ανταλλαγή

void swap(διάνυσμα& x);

Ανταλλάξτε δύο αντικείμενα λίστας

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	list<int> lt2(6, 12);
  5. 	for (int i = 0; i < 10; i++)
  6. 	{
  7. 		lt.push_back(i);
  8. 	}
  9. 	lt.swap(lt2);
  10. 	for (auto i : lt2)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. 	cout << endl;
  15. }

αποτέλεσμα λειτουργίας:

7) εκχώρηση

πρότυπο<class InputIterator>

void assign (InputIterator πρώτα, InputIterator τελευταίο);

void assign(size_type n, const value_type& val);

Καθορίστε νέο περιεχόμενο για τη λίστα, αντικαταστήστε το τρέχον περιεχόμενό της και τροποποιήστε τον αριθμό των κόμβων

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	lt.assign(4, 0);
  9. 	for (auto i : lt)
  10. 	{
  11. 		cout << i << " ";
  12. 	}
  13. }

αποτέλεσμα λειτουργίας:

8) σαφές

void clear();

Διαγράψτε όλους τους κόμβους στη συνδεδεμένη λίστα

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	lt.clear();
  9. 	cout << lt.size() << endl;
  10. }

αποτέλεσμα λειτουργίας:

5.List διεπαφή τροποποίησης παραγγελίας

(1）είδος

void sort();

πρότυπο<class Compare>

void sort(Σύγκριση comp);

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

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

  1. default (1)	
  2. template <class RandomAccessIterator>
  3.   void sort (RandomAccessIterator first, RandomAccessIterator last);
  4. custom (2)	
  5. template <class RandomAccessIterator, class Compare>
  6.   void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Οι επαναλήπτες έχουν διάφορες λειτουργικές κατηγορίες:

  • Μονόδρομος επαναλήπτης, μπορεί να κάνει μόνο ++
  • Δικατευθυντικός επαναλήπτης, μπορεί να είναι ++ και --
  • Τυχαίος επαναλήπτης, μπορεί να είναι ++, --, + και -

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

(2）ΑΝΤΙΣΤΡΟΦΗ

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

Αντιστρέψτε τη συνδεδεμένη λίστα

Για παράδειγμα:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	for (auto i : lt)
  9. 	{
  10. 		cout << i << " ";
  11. 	}
  12. 	cout << endl;
  13. 	lt.reverse();
  14. 	for (auto i : lt)
  15. 	{
  16. 		cout << i << " ";
  17. 	}
  18. 	cout << endl;
  19.  
  20. }

αποτέλεσμα λειτουργίας:

Εάν υπάρχουν σφάλματα, παρακαλώ διορθώστε με.

Προσωπικό προφίλ

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

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο