Có nhiều thao tác trên danh sách link đơn như thêm node, bỏ node, tra cứu kiếm node vào danh sách, thu xếp danh sách,…

1. Định nghĩa danh sách liên kết đơn

Giả sử, bọn họ tạo một danh sách link đơn lưu trữ một dãy số nguyên như sau:struct node int info; node *next;;struct sListnode *head; node *tail;;

2. Khởi tạo thành một danh sách links đơn rỗng

Xây dựng hàm createList() nhằm gán những con trỏ headtail trỏ về NULL.void createsList(sList &l)l.head = NULL;l.tail = NULL;

3. Chế tạo ra một node với gán giá chỉ trị cho node

Xây dựng hàm createNode() bao gồm tham số là quý giá của node ước ao tạo. Hàm createNode() tất cả kiểu trả về là con trỏ node.node* createNode(int x){node *p;p = new node;if(p==NULL)coutinfo = x;p->next = NULL;return p;

4. Thêm một node vào danh sách

Thêm một node vào đầu danh sáchTrường hòa hợp 1: nếu như danh sách link đơn rỗng thì node mới được xem như là node đầu tiên và cũng là node cuối cùng.

Bạn đang xem: Bài tập danh sách liên kết đơn

Trường hợp 2: giả dụ danh sách links đơn ko rỗng thì:Cho con trỏ links (next) của node mới trỏ vào node đầu tiên trong list hiện tại.Cho bé trỏ đầu của danh sách liên kết đơn (*head) trỏ vào node mới.void insertHead(sList &l, int x)node *p;p = createNode(x);if(p==NULL)coutnext = l.head;l.head = p;Thêm một node vào thời điểm cuối danh sáchTrường đúng theo 1: ví như danh sách links đơn rỗng thì node mới được xem là node trước tiên và cũng là node cuối cùng.Trường hòa hợp 2: nếu như danh sách liên kết đơn ko rỗng thì:Cho bé trỏ links (next) của node cuối danh sách hiện tại trỏ mang lại đến node mới.Cho nhỏ trỏ cuối của danh sách link đơn (*tail) trỏ vào node mới.void insertTail(sList &l, int x)node *p = createNode(x);if(p==NULL)coutnext = p;l.tail = p;Thêm một node p vào sau đó 1 node q vào danh sáchCho bé trỏ links (next) của node p. Chỉ vào node sau của q.Cho nhỏ trỏ liên kết của q chỉ vào node p.Nếu q là nút cuối thì gán lại p là nút cuối.
*

void insertAfter(sList &l, node *p, node *q)p->next = q->next;q->next = p;if (q == l.tail)l.tail = p;

5. Xem xét các thành phần trong danh sách

Duyệt toàn thể danh sáchvoid processList(sList &l)node *p;p = l.head;while (p!= NULL)coutinfonext;Tìm kiếm node có mức giá trị k trong danh sáchHàm searchList() có kiểu trả về là bé trỏ node. Giả dụ tìm thấy x thì node được trả về khác NULL, trái lại node được trả về là NULL.node* searchList(sList l, int k)node *p;p = l.head;while((p!= NULL)&&(p->info != k))p = p->next;return p;Hủy tổng thể danh sáchSử dụng lệnh delete nhằm giải phóng bộ nhớ lưu trữ lưu trữ những node vào 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 tới xếp những node trong danh sách

Có thể áp dụng thuật toán sắp xếp chọn thẳng (Selection Sort) để thu 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 info)min = q;q= q->next; swap(min->info, p->info);p = p->next;

7. Bài xích tập

Bên dưới là hình minh họa một danh sách liên kết đơn.

Xem thêm: * Rewrite The Sentences : 1, Yesterday The Temperature Was 9 Degrees


*

Hãy viết chương trình với C++ để làm việc với danh sách liên kết đơn sinh hoạt trên:a. Chế tạo danh sách link đơn như hình minh họa.b. Thêm 1 node bao gồm giá trị là 9 vào đầu danh sách.c. Xuất cực hiếm 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 sản phẩm tự tăng dần các giá trị của những node.e. Giải phóng bộ nhớ cho toàn cục danh sách.
Bài trước và bài bác sau trong môn học>" data-wpel-link="internal">Xây dựng danh sách link kép (Doubly Linked List) với con trỏ (pointer) >>