Danh sách liên kết là một cấu trúc dữ liệu tuyến tính trong đó mỗi phần tử là một đối tượng riêng biệt. Mỗi phần tử (chúng tôi sẽ gọi nó là một nút) của một danh sách bao gồm hai mục — dữ liệu và một tham chiếu đến nút tiếp theo. Nút cuối cùng có một tham chiếu đến null.
Danh sách được liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút cùng đại diện cho một chuỗi. Đó là cách lưu trữ dữ liệu có cấu trúc để lập trình viên có thể tự động tạo một nơi lưu trữ dữ liệu mới bất cứ khi nào cần thiết. Một số tính năng nổi bật của nó là –
- Danh sách liên kết là một chuỗi các liên kết có chứa các mục.
- Mỗi liên kết chứa một kết nối đến một liên kết khác.
- Mỗi mục trong danh sách được gọi là một nút.
- Nếu danh sách chứa ít nhất một nút, thì một nút mới được định vị là phần tử cuối cùng trong danh sách.
- Nếu danh sách chỉ có một nút, nút đó đại diện cho mục đầu tiên và mục cuối cùng.
Có hai loại danh sách liên kết –
Danh sách liên kết đơn
Danh sách liên kết đơn lẻ là một loại cấu trúc dữ liệu. Trong danh sách liên kết đơn, mỗi nút trong danh sách lưu trữ nội dung của nút và một con trỏ hoặc tham chiếu đến nút tiếp theo trong danh sách.
Danh sách liên kết đôi
Danh sách liên kết kép là một cấu trúc dữ liệu được liên kết bao gồm một tập hợp các bản ghi được liên kết theo trình tự được gọi là các nút. Mỗi nút chứa hai trường tham chiếu đến nút trước đó và nút tiếp theo trong chuỗi các nút.
Danh sách lớp
MFC cung cấp một lớp CList là một triển khai danh sách liên kết mẫu và hoạt động hoàn hảo. Danh sách CList hoạt động giống như danh sách liên kết kép. Một biến kiểu VỊ TRÍ là một khóa cho danh sách. Bạn có thể sử dụng biến VỊ TRÍ làm trình vòng lặp để duyệt qua danh sách theo trình tự và làm dấu trang để giữ một vị trí.
Đây là danh sách các phương thức trong lớp CList.
Sau đây là các thao tác khác nhau trên các đối tượng CList –
Tạo đối tượng CList
Để tạo một bộ sưu tập các giá trị hoặc đối tượng CList, trước tiên bạn phải quyết định loại giá trị của bộ sưu tập. Bạn có thể sử dụng một trong các kiểu dữ liệu nguyên thủy hiện có như int, CString, double, v.v. như được hiển thị bên dưới trong đoạn mã sau.
CList<double, double>m_list;
Thêm các mục
Để thêm một mục, bạn có thể sử dụng hàm CList::AddTail(). Nó thêm một mục vào cuối danh sách. Để thêm một phần tử vào đầu danh sách, bạn có thể sử dụng hàm CList::AddHead(). Trong CList OnInitDialog(), đối tượng được tạo và bốn giá trị được thêm vào như được hiển thị trong đoạn mã sau.
CList<double, double>m_list;
//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);
Lấy vật phẩm
Một biến kiểu VỊ TRÍ là một khóa cho danh sách. Bạn có thể sử dụng biến POSITION làm trình vòng lặp để duyệt qua danh sách theo trình tự.
Bước 1 – Để truy xuất phần tử từ danh sách, chúng ta có thể sử dụng đoạn mã sau để truy xuất tất cả các giá trị.
//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) {
double nData = m_list.GetNext(pos);
CString strVal;
strVal.Format(L"%.2f\n", nData);
m_strText.Append(strVal);
}
Bước 2 – Đây là hàm CMFCCListDemoDlg::OnInitDialog() hoàn chỉnh.
BOOL CMFCCListDemoDlg::OnInitDialog() {
CDialogEx::OnInitDialog();
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
CList<double, double>m_list;
//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);
//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) {
double nData = m_list.GetNext(pos);
CString strVal;
strVal.Format(L"%.f\n", nData);
m_strText.Append(strVal);
}
UpdateData(FALSE);
return TRUE; // return TRUE unless you set the focus to a control
}
Bước 3 – Khi đoạn mã trên được biên dịch và thực thi, bạn sẽ thấy đầu ra sau.
Thêm các mục ở giữa
Để thêm mục vào giữa danh sách, bạn có thể sử dụng các hàm CList::.InsertAfter() và CList::.InsertB Before(). Phải mất hai tham số — Đầu tiên, vị trí (nơi có thể thêm nó) và Thứ hai, giá trị.
Bước 1 – Hãy để chúng tôi chèn một mục mới như được hiển thị trong mã theo dõi.
BOOL CMFCCListDemoDlg::OnInitDialog() {
CDialogEx::OnInitDialog();
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
CList<double, double>m_list;
//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);
POSITION position = m_list.Find(85.26);
m_list.InsertBefore(position, 200.0);
m_list.InsertAfter(position, 300.0);
//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) {
double nData = m_list.GetNext(pos);
CString strVal;
strVal.Format(L"%.2f\n", nData);
m_strText.Append(strVal);
}
UpdateData(FALSE);
return TRUE; // return TRUE unless you set the focus to a control
Bước 2 – Bây giờ bạn có thể thấy rằng trước tiên chúng tôi đã truy xuất vị trí của giá trị 85,26 và sau đó chèn một phần tử vào trước và một phần tử vào sau giá trị đó.
Bước 3 – Khi đoạn mã trên được biên dịch và thực thi, bạn sẽ thấy đầu ra sau.
Cập nhật giá trị mặt hàng
Để cập nhật mục ở giữa mảng, bạn có thể sử dụng hàm CArray::.SetAt(). Nó nhận hai tham số — Thứ nhất, vị trí và Thứ hai, giá trị.
Hãy để chúng tôi cập nhật 300,00 thành 400 trong danh sách như được hiển thị trong đoạn mã sau.
BOOL CMFCCListDemoDlg::OnInitDialog() {
CDialogEx::OnInitDialog();
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
CList<double, double>m_list;
//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);
POSITION position = m_list.Find(85.26);
m_list.InsertBefore(position, 200.0);
m_list.InsertAfter(position, 300.0);
position = m_list.Find(300.00);
m_list.SetAt(position, 400.00);
//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) {
double nData = m_list.GetNext(pos);
CString strVal;
strVal.Format(L"%.2f\n", nData);
m_strText.Append(strVal);
}
UpdateData(FALSE);
return TRUE; // return TRUE unless you set the focus to a control
}
Khi đoạn mã trên được biên dịch và thực thi, bạn sẽ thấy đầu ra sau. Bây giờ bạn có thể thấy rằng giá trị 300,00 được cập nhật thành 400,00.
Xóa mục
Để xóa bất kỳ mục cụ thể nào, bạn có thể sử dụng hàm CList::RemoveAt(). Để xóa tất cả phần tử khỏi danh sách, có thể sử dụng hàm CList::RemoveAll().
Hãy để chúng tôi xóa phần tử có giá trị 95,78.
BOOL CMFCCListDemoDlg::OnInitDialog() {
CDialogEx::OnInitDialog();
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
CList<double, double>m_list;
//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);
POSITION position = m_list.Find(85.26);
m_list.InsertBefore(position, 200.0);
m_list.InsertAfter(position, 300.0);
position = m_list.Find(300.00);
m_list.SetAt(position, 400.00);
position = m_list.Find(95.78);
m_list.RemoveAt(position);
//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) {
double nData = m_list.GetNext(pos);
CString strVal;
strVal.Format(L"%.2f\n", nData);
m_strText.Append(strVal);
}
UpdateData(FALSE);
return TRUE; // return TRUE unless you set the focus to a control
}
Khi đoạn mã trên được biên dịch và thực thi, bạn sẽ thấy đầu ra sau. Bây giờ bạn có thể thấy rằng giá trị 95,78 không còn nằm trong danh sách nữa.