Khởi tạo danh sách liên kết đơn

Về bản chất thì danh sách liên kết đơn có chức năng giống như một mảng nhưng nó có nhiều ưu điểm hơn so với mảng. Để làm việc với danh sách liên kết đơn, trước tiên các bạn cần phải nắm rõ các kiến thức về con trỏ vì danh sách liên kết có sử dụng con trỏ khá nhiều. Nếu các bạn chưa hiểu rõ về con trỏ thì hãy tham khảo bài viết về con trỏ trong ngôn ngữ lập trình C/C++ của Isinhvien trước khi đọc bài này nhé!

Các phần tử trong danh sách liên kết đơn được kết nối với nhau nhớ các vùng liên kết, chỉ có sự kết nối giữa phần tử phía trước với phần tử phía sau.

Đầu tiên, ta phải khởi tạo một kiểu bản ghi [struct] sẽ gồm có dữ liệu và trường liên kết để liên kết đến phần tử đứng sau nó. Ở ví dụ dưới đây, Isinhvien sẽ khai báo một bản ghi với dữ liệu đơn giản kiểu int và con trỏ *next để trỏ đến phần tử tiếp theo.

struct element { int data; element *next; }; typedef element *List; List F; // hoặc element *F;

Trong đó:

• Kiểu con trỏ List dùng để chỉ đến một phần tử kiểu element.
• Biến con trỏ F luôn luôn chỉ đến phần tử đầu tiên trong danh sách liên kết.

Xem hình ảnh minh họa dưới đây để dễ hiểu hơn nhé!

Danh sách liên kết đơn

Khi mới khởi tạo danh sách là rỗng ta cho F nhận giá trị NULL.

void Create[List &F] { F=NULL; }

Ta liệt kê các phần tử kể từ phần tử đầu tiên được chỉ bởi biến con trỏ F và dựa vào trường liên kết next để lần lượt liệt kê các phần tử tiếp theo. Biến con trỏ p lần lượt chỉ đến từng phần tử trong danh sách bắt đầu từ phần tử đầu tiên chỉ bởi F trở đi

void Display[List F] { List p; p=F; while [p != NULL] { cout next; delete p; } l.tail = NULL; }

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.

void List_Selection_Sort[sList &l]{ node *min; node *p, *q; p = l.head; while[p != l.tail]{ min = p; q = p->next; while[q != NULL]{ if[q->info < min->info]{ min = q; } q= q->next; } swap[min->info, p->info]; p = p->next; } }

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.

Bài trước và bài sau trong môn học