Có nhiều thao tác trên danh sách liên kết đơn như thêm node, hủy node, tìm kiếm node trong danh sách, sắp xếp danh sách,
1. Định nghĩa danh sách liên kết đơn
Giả sử, chúng ta tạo một danh sách liên kết đơn lưu trữ một dãy số nguyên như sau:
struct node{ int info; node *next; }; struct sList{ node *head; node *tail; };2. Khởi tạo một danh sách liên kết đơn rỗng
Xây dựng hàm createList[] để gán các con trỏ head và tail trỏ về NULL.
void createsList[sList &l]{ l.head = NULL; l.tail = NULL; }3. Tạo một node và gán giá trị cho node
Xây dựng hàm createNode[] có tham số là giá trị của node muốn tạo. Hàm createNode[] có kiểu trả về là con trỏ node.
4. Thêm một node vào danh sách
Thêm một node vào đầu danh sách
Trường hợp 1: Nếu danh sách liên kết đơn rỗng thì node mới được xem là node đầu tiên và cũng là node cuối cùng.
Trường hợp 2: Nếu danh sách liên kết đơn không rỗng thì:
- Cho con trỏ liên kết [next] của node mới trỏ vào node đầu tiên trong danh sách hiện tại.
- Cho con trỏ đầu của danh sách liên kết đơn [*head] trỏ vào node mới.
5. Duyệt các phần tử trong danh sách
Duyệt toàn bộ danh sách
void processList[sList &l]{ node *p; p = l.head; while [p!= NULL]{ coutnext; } return p; }Hủy toàn bộ danh sách
Sử dụng lệnh delete để giải phóng bộ nhớ lưu trữ các node trong danh sách.
void deleteList[sList &l]{ node *p; while [l.head!= NULL]{ p = l.head; l.head = p->next; delete p; } l.tail = NULL; }6. Sắp xếp các node trong danh sách
Có thể sử dụng thuật toán sắp xếp chọn trực tiếp [Selection Sort] để sắp xếp danh sách liên kết đơn.
7. Bài tập
Bên dưới là hình minh họa một danh sách liên kết đơn.
Hãy viết chương trình với C++ để thao tác với danh sách liên kết đơn ở trên:
a. Tạo danh sách liên kết đơn như hình minh họa.
b. Thêm một node có giá trị là 9 vào đầu danh sách.
c. Xuất giá trị và địa chỉ của các node trong danh sách lên màn hình.
d. Sắp xếp danh sách theo thứ tự tăng dần các giá trị của các node.
e. Giải phóng bộ nhớ cho toàn bộ danh sách.
- Khái niệm biến [variable] và cách khai báo biến trong Java
- Kiểu dữ liệu enum trong C++
- Sử dụng hàm isset[] trong PHP để kiểm tra một biến có tồn tại hay không?
- Xây dựng danh sách liên kết kép [Doubly Linked List] với con trỏ [pointer]
- Giới thiệu môn học Ngôn ngữ lập trình Python