[C++] Danh sách liên kết đơn và các bài toán C++ - Bài 4

Chào các bạn!

Hôm nay mình sẽ giới thiệu sơ lược về danh sách liên kết đơn, còn chủ yếu là demo một số bài toán trên danh sách liên kết đơn.

Các bạn có thể tìm đọc thêm về sanh sách liên kết đơn thông qua google search nhé!

Danh sách liên kết đơn là một danh sách chứa một hoặc nhiều nút(ở đây mình xin phép gọi là nút), mỗi nút có 2 trường: trường chứa dữ liệu(data) và trường liên kết(link) chứa địa chỉ của nút tiếp theo.

Mô hình danh sách liên kết.



 

First là con trỏ chỉ đến địa chỉ của nút đầu tiên trong danh sách.

Khai báo:

Struct NUT
{
 <Type> data;
 NUT*next;
};typedef NUT*TRO;

Các thao tác cơ bản trên danh sách liên kết đơn

Khởi tạo danh sách: First==NULL;

Bổ sung một nút vào danh sách

Bổ sung vào đầu danh sách

B1: Tạo một nút mới

TRO p=new(NUT);

p->data=x;

B2: Bổ sung nút mới vào DSLK

p->next=FIRST;

FIRST=p;

Bổ sung vào cuối danh sách

B1: Tạo một nút mới(nút p)

TRO p=new(NUT);

p->data=x;

p->FIRST=NULL;

B2: Tìm đến nút cuối cùng của DSLK cần bổ sung(ở đâu mình gọi nó là q)

TRO q=FIRST;

while(q->next!=NULL)

q=q->next;

B3: Nối p vào cuối  DSLK (sau q)

q->next=p;

Sau đây là video demo một số bài toán trên danh sách liên kết đơn.

httpv://www.youtube.com/watch?v=VmyKTB-VAzI

Nguồn: Tự Học IT Online - http://tuhocit.net