Slide bài giảng 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

Tóm lược nội dung

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

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS vận dụng kiến thức đã học, trả lời câu hỏi Khởi động tr.146 SGK: Em hãy liệt kê nhược điểm của danh sách mảng.

NỘI DUNG BÀI HỌC GỒM

• Cấu trúc danh sách liên kết
• Một số kiểu danh sách đặc biệt và ứng dụng của danh sách liên kết
• Luyện tập
• Vận dụng

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Cấu trúc danh sách liên kết

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

Nội dung gợi ý:

- 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.

- Phần Next trong một nút là con trỏ Next, kí hiệu mũi tên “→”.

- Về bản chất, kí hiệu mũi tên “→” để thể hiện một kiểu dữ liệu kiểu đặc biệt, gọi là kiểu con trỏ. Cho phép truy cập trực tiếp đến một địa chỉ ô nhớ cụ thể.

- Đuôi danh sách là nút cuối cùng trong danh sách, không có nút nào đứng sau.

+ Đượ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.

- Khi lập trình, cần phân biệt một nút với phần Data chứa dữ liệu trong nút đó, phân biệt phần Data với chính dữ liệu trong nút đó.

Câu 2. Hãy nêu sự khác biệt giữa danh sách liên kết và mảng.

Nội dung gợi ý:

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 trô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.

Câu 3. Hãy trình bày các thao tác thêm nút và xóa nút trong danh sách liên kết.

Nội dung gợi ý:

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

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

Nút mới thêm thành nút đầu tiên, gọi là E. Thao tác theo hai bước sau:

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

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

*Thời gian thực hiện phép thêm nút vào đầu danh sách là O(1), không phụ thuộc độ dài danh sách.

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

- Nối thêm nút mới vào cuối danh sách, nó trở thành nút cuối cùng. 

- Con trỏ Tail trỏ đến nút cuối cùng của danh sách → sửa lại cho Tail trỏ vào E.

* Thời gian thực hiện phép thêm nút vào cuối danh sách là O(1), không phụ thuộc độ dài danh sách.

c) Thêm nút vào giữa danh sách

Tình huống minh họa: curr → B. Thêm nút vào sau nút B. 

* Thời gian thực hiện phép thêm nút vào giữa danh sách là O(1), không phụ thuộc độ dài danh sách.

• Gỡ bỏ nút:

Tình huống minh họa: curr → B. Gỡ bỏ nút sau nút B.

- Ghi lưu con trỏ để truy cập nút C: tmp = B.Next, tức là tmp → C. 

- Cho B.Next trỏ đến nút đứng sau C (là nút D): B.Next = C.Next.

- Sử dụng tmp để giải phóng phần bộ nhớ dành cho C.

*Thao tác gỡ bỏ nút đầu danh sách hay cuối danh sách chỉ khác chút ít. Thời gian thực hiện gỡ bỏ là O(1), không phụ thuộc vào độ dài danh sách.

Danh sách liên kết kép

- Nếu mỗi nút có thêm một con trỏ nữa là Prev trỏ đến nút đứng kề ngay trước thì ta sẽ có danh sách nối kép.

Câu 4. Em 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.

Nội dung gợi ý:

- Phép tìm kiếm: Tìm nút chứa dữ liệu X (Data = X) để xử lí. Phải thực hiện tìm kiếm tuần tự từ đầu danh sách. 

→ Độ phức tạp của phép tìm kiếm là O(n) với n là số nút của danh sách.

- Các thao tác thêm nút, gỡ bỏ nút của danh sách liên kết dù ở bất cứ vị trí nào thì thời gian thực hiện đều là O(1). 

→ Điểm ưu việt hơn danh sách mảng.

- Danh sách liên kết tốn thêm chỗ để lưu trữ thành phần Next. 

→ Đây là nhược điểm so với danh sách mảng.

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

HS thảo luận trả lời câu hỏi: 

Hãy cho biết vai trò và ứng dụng của danh sách liên kết trong đời sống.

Nội dung gợi ý:

- Sử dụng cấu trúc móc nối để liên kết các nút thành một dãy tuần tự tạo ra kiểu danh sách rất linh hoạt.

- Danh sách liên phát huy ưu điểm trong những trường hợp thường xuyên phải:

+ Thêm phần tử, gỡ bỏ phần tử ở bất cứ vị trí nào trong danh sách;

+ Độ dài danh sách thay đổi nhanh và nhiều trong quá trình sử dụng.

HOẠT ĐỘNG LUYỆN TẬP

Câu 1: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chọn tăng dần (select sort)?

A. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp

B. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy

C. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chỗ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng

D. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào bé hơn được cho lên vị trí trên

Câu 2: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (bubble sort)?

A. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp

B. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên

C. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống

D. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chỗ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng

Câu 3: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chèn (insertion sort)?

A. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp

B. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống

C. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng

D. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên

Câu 4: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nhanh (Quick sort)?

A. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng

B. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếpnh u, nếu phần tử nào nhỏ hơn được đứng vị trí trên

C. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp

D. Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá)

Câu 5: Phương pháp nào sau đây chính là phương pháp sắp xếp nhanh (Quick sort)?

A. Phương pháp trộn

B. Phương pháp vun đống

C. Phương pháp chèn

D. Phương pháp phân đoạn

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoàn thành bài tập Vận dụng SGK trang 149: 

Phân tích yêu cầu ứng dụng của một danh sách nhóm đứng đầu top N và cho biết, nếu sử dụng kiểu danh sách của Python để thực hiện thì:

a) Những thao tác cần thực hiện với danh sách top N sẽ được thực hiện qua các phép toán danh sách Python như thế nào?

b) Nêu tên một vài phép toán danh sách của Python không cần thiết cho trường hợp này.