Giáo án điện tử Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

NHIỆT LIỆT CHÀO ĐÓN
CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Em hãy nêu nhược điểm của danh sách mảng.

Không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.

BÀI 15: CẤU TRÚC DỮ LIỆU DANH SÁCH LIÊN KẾT VÀ ỨNG DỤNG

NỘI DUNG BÀI HỌC

01

Cấu trúc danh sách liên kết

02

Một số kiểu danh sách đặc biệt và ứng dụng của danh sách liên kết

1.

CẤU TRÚC DANH SÁCH LIÊN KẾT

Hoạt động nhóm từ 3 - 4 HS

Đọc thông tin mục 1 tr.146 - 148 SGK, thảo luận và hoàn thành Phiếu học tập sau:

PHIẾU HỌC TẬP

Cấu trúc danh sách liên kết

Câu 1. Danh sách liên kết là gì? Trình bày cấu trúc của một danh sách liên kết.

Câu 2. Nêu sự khác nhau giữa danh sách liên kết và mảng.

Câu 3. Trình bày thao tác thêm nút và gỡ bỏ nút trong danh sách liên kết.

Câu 4. Dựa vào kiến thức đã học, hãy cho biết thời gian thực hiện các phép toán của danh sách liên kết.

Danh sách liên kết (linked list)

Là một chuỗi nhiều nút (node) lưu trữ rải rác không liền kề trong bộ nhớ.

Một nút có hai thành phần:

Phần Data chứa dữ liệu.

Phần liên kết gọi là Next kí hiệu mũi tên “→”.

- Đuôi danh sách là nút cuối cùng trong danh sách.

Được thể hiện bằng hình vẽ Next trỏ đến Null và được hiểu rằng “không trỏ đến đâu cả, không đi tiếp được nữa”.

Con trỏ Tail trỏ đến nút đuôi danh sách.

- Đầu danh sách được minh họa bằng mũi tên Head trỏ đến nút đầu tiên trong danh sách.

Sự khác nhau giữa danh sách liên kết và mảng

So với mảng, danh sách liên kết có những điểm khác biệt sau:

Các nút danh sách liên kết không được lưu trữ thành một khối liên tục liền kề mà có thể nằm rải rác, tách rời nhau trong bộ nhớ.

Không có chỉ số nên không truy cập bằng chỉ số được.

Cần duyệt tuần tự các nút, so sánh dữ liệu chứa trong nút với yêu cầu tìm kiếm để tìm đúng nút phải truy cập xử lí dữ liệu.

Phép lặp duyệt tuần tự từng nút của danh sách liên kết sử dụng một con trỏ curr (current) chỉ vào nút đang xét, thực hiện như sau:

curr = Head bắt đầu từ Head để truy cập nút A.

curr = A.Next để truy cập nút B; curr = B.Next để truy cập nút C;...

Kết thúc khi gặp curr = Null tức là tình huống curr = D.Next

Thêm nút và bỏ nút

► Thêm nút có 3 trường hợp:

1. a) Thêm nút vào đầu danh sách

Cho E.Next trỏ đến nút A: gán E.Next = Head.

Cho Head trỏ đến nút E: Head → E.

1. b) Thêm nút vào cuối danh sách

Nút thêm vào trở thành nút cuối cùng.