Tìm hiểu về danh sách liên hết đơn, ứng dụng trong thực tế và cài đặt bằng c++ Bạn đang tìm hiểu về cấu trúc giải thuật trong lập trình ? Khám phá ngay bài viết này để hiểu rõ hơn về danh sách liên kết đơn (singly linked list), ứng dụng của nó cũng như cài đặt bằng c++. Danh sách liên kết đơn (singly linked list) Danh sách liên kết đơn (singly linked list) là một cấu trúc dữ liệu bao gồm một chuỗi các nút (nodes), mỗi nút chứa một giá trị và một con trỏ đến nút tiếp theo trong danh sách. Đây là một cấu trúc dữ liệu tuyến tính, nhưng không giống như mảng, các phần tử không được lưu trữ liên tiếp trong bộ nhớ. Các thành phần chính của danh sách liên kết đơn: Node: Mỗi nút chứa hai phần: - Dữ liệu: Giá trị của nút. - Con trỏ: Trỏ đến nút tiếp theo trong danh sách. Head: Con trỏ đầu tiên của danh sách, trỏ đến nút đầu tiên. Có 2 giải thuật chính đối với danh sách liên kết là: Insert: Chèn một phần tử vào vị trí bất kỳ trong danh sách liên kết. Delete: Xóa một phần tử ở vị trí bất kỳ trong danh sách liên kết. Ứng dụng của danh sách liên kết đơn trong thực tế Danh sách liên kết đơn có nhiều ứng dụng thực tế trong lập trình và khoa học máy tính. Dưới đây là một số ví dụ phổ biến: Quản lý bộ nhớ động: Danh sách liên kết đơn giúp quản lý bộ nhớ hiệu quả hơn so với mảng, đặc biệt khi kích thước của dữ liệu không cố định hoặc thay đổi thường xuyên. Triển khai các cấu trúc dữ liệu khác: Danh sách liên kết đơn là nền tảng để triển khai các cấu trúc dữ liệu phức tạp hơn như ngăn xếp (stack), hàng đợi (queue), và danh sách liên kết kép (doubly linked list). Hệ thống quản lý tài liệu: Trong các hệ thống quản lý tài liệu, danh sách liên kết đơn có thể được sử dụng để theo dõi các phiên bản của tài liệu hoặc các thay đổi theo thời gian. Trình duyệt web: Các trình duyệt web sử dụng danh sách liên kết đơn để quản lý lịch sử duyệt web. Mỗi trang web được lưu dưới dạng một nút trong danh sách, và người dùng có thể di chuyển qua lại giữa các trang đã truy cập. Ứng dụng trong đồ họa máy tính: Trong đồ họa máy tính, danh sách liên kết đơn có thể được sử dụng để quản lý các đối tượng đồ họa, chẳng hạn như các điểm, đường thẳng, hoặc hình dạng. Hệ thống quản lý bộ nhớ: Trong các hệ điều hành, danh sách liên kết đơn có thể được sử dụng để quản lý các khối bộ nhớ tự do (free memory blocks) trong bộ nhớ động. Ứng dụng trong mạng: Trong các giao thức mạng, danh sách liên kết đơn có thể được sử dụng để quản lý các gói tin (packets) trong hàng đợi truyền tải. Trong phạm vi bài viết này, Stanford sẽ hướng dẫn các bạn học lập trình thực hiện cài đặt thuật toán liên kết đơn bằng ngôn ngữ lập trình c++ như sau: #include <iostream> using namespace std; // Định nghĩa cấu trúc của một nút struct Node { int data; Node* next; }; // Hàm để chèn một nút mới vào đầu danh sách void insertAtHead(Node*& head, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = head; head = newNode; } // Hàm để xóa một nút với giá trị cụ thể void deleteNode(Node*& head, int key) { Node* temp = head; Node* prev = nullptr; // Nếu nút đầu tiên chứa giá trị cần xóa if (temp != nullptr && temp->data == key) { head = temp->next; // Thay đổi head delete temp; // Giải phóng bộ nhớ return; } // Tìm nút chứa giá trị cần xóa while (temp != nullptr && temp->data != key) { prev = temp; temp = temp->next; } // Nếu không tìm thấy giá trị cần xóa if (temp == nullptr) return; // Bỏ qua nút cần xóa prev->next = temp->next; // Giải phóng bộ nhớ delete temp; } // Hàm để in danh sách void printList(Node* head) { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl; } int main() { Node* head = nullptr; // Khởi tạo danh sách rỗng // Chèn các phần tử vào danh sách insertAtHead(head, 10); insertAtHead(head, 20); insertAtHead(head, 30); // In danh sách trước khi xóa cout << "Danh sách trước khi xóa: "; printList(head); // Xóa nút với giá trị 20 deleteNode(head, 20); // In danh sách sau khi xóa cout << "Danh sách sau khi xóa: "; printList(head); return 0; } Giải thích: Node: Định nghĩa cấu trúc của một nút với hai thành phần: data và next. insertAtHead: Hàm để chèn một nút mới vào đầu danh sách. deleteNode: Hàm để xóa một nút với giá trị cụ thể. Nó duyệt qua danh sách để tìm nút cần xóa, cập nhật con trỏ của nút trước đó và giải phóng bộ nhớ của nút cần xóa. printList: Hàm để in các phần tử trong danh sách. main: Hàm chính để khởi tạo danh sách, chèn các phần tử và in danh sách. Danh sách liên kết đơn là một cấu trúc dữ liệu linh hoạt và hiệu quả, giúp giải quyết nhiều vấn đề trong lập trình và khoa học máy tính. Để hiểu rõ hơn về thuật toán này bạn có thể thực hiện lập trình cài đặt thuật toán danh sách liên kết đơn như hướng dẫn trong bài viết. Bạn có thể tìm hiểu thêm về các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công ! Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé. ==========🎬 🎬 🎬========== ☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ Hotline: 0963 723 236 - 0866 586 366 Website: https://stanford.com.vn Facebook: https://www.facebook.com/Stanford.com.vn Youtube: http://bit.ly/2TkKT7I Tags: danh sách liên kết đơn, singly linked list