Top List List

Sắp xếp List trong C#

STL là viết tắt của cụm từ Standard Template Library, là bộ thư viện chuẩn của C++, STL cung cấp các lớp cài đặt sẵn, cho phép thao tác với các kiểu dữ liệu cơ bản cũng như các kiểu dữ liệu tự định nghĩa, việc thành thạo sử dụng thư viện STL sẽ giúp tiếp kiệm thời gian trong lập trình.

List là gì?

List là một danh sách chứa các đối tượng (các nút (node) – lưu trữ các thông tin dữ liệu và địa chỉ của nút kế tiếp, nút trước đó) liên kết với nhau và cho phép chèn thêm hay xóa bất kì một đối tượng nào trong danh sách. Là một cấu trúc dữ liệu cơ bản để biết thêm tham khảo tại danh sách liên kết đơn.

Cách sử dụng

LƯU Ý : kiểu dữ liệu List là một trong các kiểu dữ liệu mà thư viện STL hỗ trợ, phải include thư viện tương ứng để sử dụng loại dữ liệu mong muốn. Đồng thời phải sử dụng namespace STD để có thể sử dụng code của thư viện này. Để biết thêm về namespace.

Đối với các biến tĩnh cú pháp khai báo như sau:

list<kiểu dữ liệu> TênBiến;

Ví dụ:

list<int> myIntList;

Một số constructor đã được định nghĩa sẵn như:

// default constructor list<int> myList; // fill constructor // myList1 được khởi tạo chứa 4 phần tử có giá trị 50 list<int> myList1(4, 50); // copy constructor //tạo một list mới có 4 phần tử và đều có giá trị là 100 list<int> myList(4, 100); //tạo một list mới với các phần tử và giá trị được chép từ myList vào list<int> copyMyList(myList); ...

Là một danh sách liên kết bao gồm các thao tác push_back() (thêm phần tử vào vị trí cuối của list) và push_font() (thêm phần tử vào vị trí đầu của list)

//create list with value 10 10 10 10 list<int> myList(4, 10); //add new Node have value of 5 to the after last Node of the List myList.push_back(5); //add new Node have value of 5 to the before first Node of the List myList.push_front(6); // result 6 10 10 10 10 5

Còn có các hàm xóa một đối tượng trong danh sách pop_back() (xóa vị trí cuối cùng) hay pop_font() (xóa vị trí đầu tiên)

Ví dụ:

//100 100 100 100 list<int> myList (4, 100); mylist.pop_back(); mylist.pop_front(); // result 100 100

Hoặc xóa một vị trí bất kì trong danh sách(hàm có dạng)

iterator erase (iterator position);

hoặc xóa một vùng trong danh sách

iterator erase (iterator first, iterator last);

Ngoài ra còn có thể xóa một đối tượng có giá trị xác định

void remove (const value_type& val);

Ví dụ:

list<int> myList; //một vòng lập từ 0 tới 9 và thêm vào cuối cùng của list giá trị tương ứng for(int i = 0; i < 10; i++) myList.push_back(i); list<int> list1(myList); // => list1 = [0,1,2,3,4,5,6,7,8,9] //position ở đây truy cập vị trí đầu tiên của mylist và tăng lên tới vị trí thứ 2 list<int>::iterator position = myList.begin(); position++; myList.erase(position); // => mylist = [0,2,3,4,5,6,7,8,9] // position truy cập phần tử đầu tiên list1 position = list1.begin(); // position1 truy cập phần tử đầu tiên của list1 list<int>::iterator position1 = list1.begin(); //tăng con trỏ để con trỏ position1 có thể trỏ tới phần tử thứ 4 so với vị trí đầu tiên của list position1++; position1++; position1++; position1++; // xóa phần tử từ vị trí đầu tới vị trí thứ 4 so vo với vị trí đầu list1.erase(position, position1); // => list1 = {4,5,6,7,8,9} // Thêm 1 phần tử có giá trị 9 vào cuối list list1.push_back(9); // => list1 = {0,4,5,6,7,8,9} list1.remove(9); // => list1 = {0,4,5,6,7,8}

Truy cập đến vị trí đầu tiên của danh sách thông qua hàm begin() hoặc rend()và truy cập đến phần tử cuối cùng danh sách qua hàm end() hoặc rbegin()

list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); //truy cập tới vị trí cuối của list cout << *l.rbegin(); // Output: 3

Để xóa hết danh sách, có thể dùng hàm clear()

list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.clear();// => l = {}

Chèn vào một danh sách có thể dùng hàm:

iterator insert (iterator position, const value_type& val);

Tức là chèn giá trị “val” vào danh sách từ vị trí “position”

Ngoài ra còn có hàm sau:

void insert (iterator position, size_type n, const value_type& val);

Nghĩa là chèn vào danh sách “n” phần tử có giá trị “val” từ vị trí “position”

Hoặc chèn một danh sách từ vị trí “first” đến vị trí “last” vào một danh sách từ vị trí “position”

void insert (iterator position, InputIterator first, InputIterator last);

Ví dụ:

list<int> myList(4, 10); //thêm vào myList 5 phần tử có đều có giá trị là 1 bắt đầu từ đầu của myList myList.insert(myList.begin(), 5, 1); // => myList = [1,1,1,1,1,10,10,10,10] list<int> list1(4, 100);// 100 100 100 100 list<int> l;// 1 2 3 l.push_back(1); l.push_back(2); l.push_back(3); //từ l copy các dữ liệu từ đầu cho tới cuối l vào đầu list1 list1.insert(list1.begin(), l.begin(), l.end()); // => list1 = [1,2,3,100,100,100,100] list<int> list2(4, 10); list2.push_back(5); list2.push_front(6); //thêm vào đầu list2 một phần tử có giá trị là 10 list2.insert(list2.begin(), 10); // => mylist = [10,6,10,10,10,10,5]

Ngoài ra có thể kiểm tra xem danh sách có rỗng hay không thông qua hàm empty() nếu rỗng trả về true và ngược lại

list<int> mylist; for (int i = 1; i <= 10; ++i) mylist.push_back(i); int sum = 0; while (!mylist.empty()) { sum += mylist.front(); mylist.pop_front(); } // => sum = 55

Hoặc trả về kích thước của danh sách thông qua hàm size()

list<int> myints; for(int i = 0; i < 10; i++) myints.push_back(i); cout << "1. size: " << myints.size() << '\n';

Còn có thể sắp xếp danh sách qua hàm sort()

l.push_back(1); l.push_back(5); l.push_back(3); l.push_back(2); l.push_back(7); l.sort(); // 1 2 3 5 7

Nhưng hàm merge() sau khi trộn 2 list lại sẽ tự động sort

std::list<double> first, second; first.push_back (3.1); first.push_back (2.2); first.push_back (2.9); second.push_back (3.7); second.push_back (7.1); second.push_back (1.4); first.sort(); second.sort(); first.merge(second); // 1.4 2.2 2.9 3.1 3.7 7.1

Từ đầu bài viết đã có sử dụng tới iterator để truy cập vào các phần tử trong list vậy iterator là gì.

list<double> first; first.push_back (3.1); first.push_back (2.2); first.push_back (2.9); list<double>::iterator value = first.begin() // *value will be 3.1 value++; // *value will be 2.2

Lưu ý iterator thực chất cũng là một con trỏ. Lưu lại địa chỉ của các phần tử Node trong list STL đã đặt tên là iterator và biến nó thành một đối tượng và biến nó thành một đối tượng dùng để duyệt qua một list, vector, ... để có thể làm việc một cách trực quan nhất.

Ưu điểm và nhược điểm của "list"

Việc sử dụng thành thạo các hàm trong “list” nói chung hoặc danh sách “list” nói riêng sẽ giúp ích rất nhiều về vấn đề quản lý, có thể là quản lý một danh sách thông tin nào đó, với các hàm đã được hỗ trợ viết sẵn sẽ giúp dễ dàng cập nhật và sửa chữa. List hỗ trợ vòng lặp 2 chiều, nhưng lại không thể truy cập ngẫu nhiên như các mảng thông thường vì vậy mà việc tìm kiếm một phần tử trong danh sách sẽ rất chậm, lí do từ việc cấu trúc của List được xây dựng tương tự danh sách liên kết đơn.

Trong những bài trước, ta đã khai báo và sử dụng mảng với các phần tử nằm ở các vị trí ngẫu nhiên và được coi là chưa sắp xếp. Điều đó nghĩa là các phần tử chưa tuân theo một quy tắc nào đó và các phần tử đều nằm “lộn sộn” trong mảng. Đối với bài toán có yêu cầu sắp xếp phần tử trong mảng 1 chiều, ta chủ yếu sắp xếp mảng theo chiều tăng dần hoặc giảm dần.

1.Cách sắp xếp các phần tử trong mảng

Trong bài này, phương pháp được sử dụng để sắp xếp mảng 1 chiều theo phần tử tăng dần hay giảm dần đó là phương pháp Selection Sort (sắp xếp chọn).

Giả sử rằng mảng ban đầu của tôi gồm các phần tử là: 5,9,7,2,3,6,9,10 và tôi cần sắp xếp dãy trên hay mảng trên theo chiều các chữ số tăng dần.

Để thực hiện việc sắp xếp dãy trên theo chiều tăng dần, tôi sẽ cần thực hiện các bước lặp và thực hiện kiểm tra điều kiện.

Tôi chọn lần lượt các phần tử có trong mảng và chọn từ phần tử đầu tiên đến phần tử gần cuối của mảng trên để đem so sánh với các phần tử còn lại trong mảng , nếu phần tử đang được chọn lớn hơn phần tử bất kỳ nào nằm trong danh sách thì sẽ thực hiện đổi chỗ hay hoán vị vị trí cho hai phần tử này, ngược lại thì giữ nguyên vị trí. Xem hình minh họa dưới đây:

Nguồn Sắp xếp chọn – Wiki

2.Sắp xếp tăng dần các phần tử trong mảng

Chương trình sắp xếp tăng dần các phần tử trong mảng 1 chiều, với mảng ban đầu là int number[10] = {8,5,2,6,9,3,1,4,0,7};

#include <stdio.h> int main(){ //khai bao so luong phan tu int n = 10; //khai bao mang int number[n] = {8,5,2,6,9,3,1,4,0,7}; //khai bao bien trung gian de hoan vi int trunggian; //hien thi mang ban dau printf("MANG BAN DAU\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] > number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } //hien thi mang sau khi sap xep tang dan printf("\nMANG SAU KHI SAP XEP TANG DAN\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } }

Hàm sắp xếp các phần tử trong mảng theo chiều tăng dần:

#include <stdio.h> void SapXepTang(int number[], int n){ //khai bao bien trung gian de hoan vi int trunggian; //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] > number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } } int main(){ //khai bao so luong phan tu int n = 10; //khai bao mang int number[n] = {8,5,2,6,9,3,1,4,0,7}; //hien thi mang ban dau printf("MANG BAN DAU\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } //goi ham sap xep tang va truyen vao mang can sap xep va so luong phan tu SapXepTang(number,n); //hien thi mang sau khi sap xep tang dan printf("\nMANG SAU KHI SAP XEP TANG DAN\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } }

3.Sắp xếp giảm dần các phần tử trong mảng

Đối với việc sắp xếp mảng theo chiều tăng dần, ta cần kiểm tra điều kiện trong vòng lặp đó là if(number[i] > number[j]) thì ta thực hiện hoán vị 2 phần tử đó. Tuy nhiên đối với việc sắp xếp mảng theo chiều giảm dần ta sẽ đặt điều kiện ngược lại đó là: if (number[i] < number[j])

#include <stdio.h> int main(){ //khai bao so luong phan tu int n = 10; //khai bao mang int number[n] = {8,5,2,6,9,3,1,4,0,7}; //khai bao bien trung gian de hoan vi int trunggian; //hien thi mang ban dau printf("MANG BAN DAU\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] < number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } //hien thi mang sau khi sap xep giam dan printf("MANG SAU KHI SAP XEP GIAM DAN\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } }

Hàm sắp xếp phần tử mảng giảm dần cũng được thay thế if(number[i] > number[j]) bằng if(number[i] < number[j])

#include <stdio.h> void SapXepGiam(int number[], int n){ //khai bao bien trung gian de hoan vi int trunggian; //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] < number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } } int main(){ //khai bao so luong phan tu int n = 10; //khai bao mang int number[n] = {8,5,2,6,9,3,1,4,0,7}; //hien thi mang ban dau printf("MANG BAN DAU\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } //goi ham sap xep giam va truyen vao mang can sap xep va so luong phan tu SapXepGiam(number,n); //hien thi mang sau khi sap xep giam dan printf("MANG SAU KHI SAP XEP GIAM DAN\n"); for(int i = 0; i < n; i++){ printf("%d \n", number[i]); } }

4.Nhập xuất và sắp xếp phần tử trong mảng

Ở 2 chương trình sắp xếp tăng và sắp xếp giảm dần ở phần trên, ta đang sắp xếp cho mảng cố định. Tuy nhiên ta có thể kết hợp nhập xuất rồi thực hiện việc sắp xếp.

#include <stdio.h> void Nhap(int number[], int n){ for(int i = 0; i < n ; i++){ printf("NHAP A[%d]: ",i); scanf("%d",&number[i]); } } void Xuat(int number[],int n){ for(int i = 0; i < n ; i++){ printf("%d \n",number[i]); } } void SapXepTang(int number[], int n){ //khai bao bien trung gian de hoan vi int trunggian; //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] > number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } } void SapXepGiam(int number[], int n){ //khai bao bien trung gian de hoan vi int trunggian; //thuc hien thuat toan sap xep chon for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j ++){ //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau if(number[i] < number[j]){ //hoan vi 2 phan tu trunggian = number[i]; number[i] = number[j]; number[j] = trunggian; } } } } int main(){ //khai bao so luong phan tu int n; //nhap vao n printf("NHAP VAO N: "); scanf("%d",&n); //khai bao mang n phan tu int number[n]; //goi ham nhap va xuat phan tu Nhap(number,n); printf("MANG SAU KHI NHAP\n"); Xuat(number,n); //goi ham sap xep tang va hien thi mang sau khi sap xep tang SapXepTang(number,n); printf("MANG SAU KHI DUOC SAP XEP TANG DAN\n"); Xuat(number,n); //goi ham sap xep giam va hien thi mang sau khi sap xep giam SapXepGiam(number,n); printf("MANG SAU KHI DUOC SAP XEP GIAM DAN\n"); Xuat(number,n); }

List là gì?

Cách sử dụng

Ưu điểm và nhược điểm của "list"

1.Cách sắp xếp các phần tử trong mảng

2.Sắp xếp tăng dần các phần tử trong mảng

3.Sắp xếp giảm dần các phần tử trong mảng

4.Nhập xuất và sắp xếp phần tử trong mảng

Video liên quan

Bài Viết Liên Quan

Toplist

Bài mới nhất

Chủ đề