BÀI 30. THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 30. THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Tạo được một thư viện nhỏ của người lập trình. Trình bày được cấu trúc dannh sách liên kết.
Khởi động
Khởi động
Ảnh
- Khởi động:
Em hãy tìm thêm các ví dụ thực tế của mô hình danh sách liên kết.
Hình thành kiến thức
1. Thiết lập thư viện cho chương trình
1. Thiết lập thư viện cho chương trình
Ảnh
Em hãy đọc, thảo luận và trả lời các câu hỏi sau: 1. Vì sao lại cần thư viện chương trình? 2. Ý nghĩa của các hàm trong thư viện chương trình là gì?
- HĐ1: Tìm hiểu ý nghĩa của thư viện chương trình
a. Một số hàm của thư viện math
a. Một số hàm của thư viện math
Thư viện math trong Python chứa các hàm chuẩn liên quan đến tính toán toán học như sqrt(), floor() và ceil(). Để sử dụng thư viện math, có thể dùng lệnh import hoặc from import như sau:
Ảnh
Ảnh
Ảnh
- Ví dụ
- Ví dụ:
Ảnh
Ảnh
b. Tự thiết lập thư viện
b. Tự thiết lập thư viện
Để thiết lập một thư viện, đưa các hàm chuẩn vào một tập chương trình và đặt tên của tệp này chính là tên thư viện muốn lưu trữ. Ví dụ: tập chương trình lib.py đóng vai trò như một thư viện. Thư viện này có hai hàm như sau:
Ảnh
+ tiếp (b. Tự thiết lập thư viện)
Chương trình sử dụng thư viênnj có thể như sau (đặt tệp chương trình này cùng thư mục với tệp thư viện lib.py.
Ảnh
Ảnh
- Ghi nhớ
- Ghi nhớ:
Ảnh
Thư viện chương trình là tập hợp các hàm được đặt trong các mô đun độc lập để dùng chung cho nhiều chương trình khác nhau. Các thư viện này có thể được dùng nhiều lần và có thể cập nhật, nâng cấp bất cứ lúc nào. Trong Python, lệnh import có chức năng đưa thư viện vào bộ nhớ để sẵn sàng sử dụng.
- Câu hỏi củng cố
- Câu hỏi củng cố:
Bài tập trắc nghiệm
Những câu nào sau đây là sai về ý nghĩa của việc sử dụng thư viện khi viết chương trình?
A. Chương trình sẽ ngắn hơn.
B. Các hàm thư viện được viết một lần và sử dụng nhiều lần.
C. Chương trình sẵn sàng, dễ hiểu hơn.
D. Chương trình sẽ chạy nhanh hơn.
2. Cấu trúc danh sách liên kết
2. Cấu trúc danh sách liên kết
Đọc, trao đổi và thảo luận để biết cấu trúc dữ liệu của danh sách liên kết và các thao tác dữ liệu cơ bản trên danh sách liên kết.
- HĐ2: Tìm hiểu cấu trúc danh sách liên kết
Ảnh
- Tìm hiểu
- Tìm hiểu:
Mỗi danh sách liên kết bao gồm hai cấu trúc dữ liệu: Node mô tả các phần tử độc lập của danh sách và cấu trúc LL (linked list) có thông tin head (đầu) luôn chỉ vào node đầu tiên của danh sách liên kết.
Ảnh
- Một số lệnh, thao tác chính với kiểu dữ liệu danh sách liên kết
Ảnh
- Một số lệnh, thao tác chính với kiểu DL danh sách liên kết
Khởi tạo một danh sách liên kết mới. Bổ sung một phần tử với khoá k cho trước vào danh sách. Tìm kiếm phần tử có khoá k tử có khoá k trong danh sách cho trước. Xoá phần tử có khoá k trong danh sách.
- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết
- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết
1. Hàm insert(L,k) sẽ bổ sung (chèn) node với khoá k vào đầu của danh sách L.
Ảnh
+ tiếp
Ảnh
- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết
2. Hàm delete_first(L) sẽ xoá node đầu tiên của danh sách (nếu danh sách không rỗng).
+ tiếp
- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết
3. Hàm tìm kiếm phần tử có khoá k trong danh sách L. Nếu tìm thấy sẽ trả về node tương ứng, nếu không trả về None.
Ảnh
Ảnh
+ tiếp (- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết)
Ảnh
4. Hàm xoá phần tử có khoá k trong danh sách L. + Nếu phần tử cần xoá là node đầu tiên, sử dụng hàm delete_first(). + Nếu không, duyệt danh sách và lưu trữ node trước của node cần xoá. Nếu tìm thấy thì sử dụng lệnh x.next = y.next để xoá.
+ tiếp
- Các hàm thao tác chuẩn trên dữ liệu danh sách liên kết
Hàm show(L) có tính năng hiển thị toàn bộ thông tin của danh sách liên kết.
Ảnh
Ảnh
- Một số ví dụ thiết lập cấp trúc dữ liệu Linked List:
- Một số ví dụ thiết lập cấp trúc dữ liệu Linked List:
Thiết lập một danh sách rỗng.
Ảnh
Thiết lập một danh sách bao gồm hai node có khoá là 5,2.
Thiết lập một danh sách gồm các phần tử lấy từ dãy A cho trước.
Ảnh
Ảnh
- Ghi nhớ
Ảnh
- Ghi nhớ:
Danh sách liên kết là cấu trúc dữ liệu bao gồm:
Cấu trúc node mô tả các phần tử của danh sách. Mỗi node sẽ có dữ liệu khoá (key) là thông tin chính và thông tin next để kết nối sang phần từ tiếp theo của danh sách. Cấu trúc head là đầu của mỗi danh sách liên kết. Head luôn chỉ vào node đầu tiên của danh sách. Node cuối cùng của danh sách sẽ có thông tin next = None (dữ liệu rỗng). Có thể thiết lập các hàm tìm kiếm, bổ sung hoặc xoá thông tin trên danh sách liên kết.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Câu 1. Đoạn chương trình sau thực hiện công việc gì?
Ảnh
Câu 2. Viết đoạn chương trình ngắn sử dụng thư viện LinkedList đề thiết lập một danh sách liên kết L và bổ sung các tên "Bình", "Hoa", "Hà" vào danh sách này.
Luyện tập
- Luyện tập
Ảnh
- Luyện tập
Câu 1: Viết một thư viện bao gồm các hàm nhập dữ liệu là một dãy số và các hàm thư viện bao gồm sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt. Câu 2: Cho trước danh sách liên kết L với cấu trúc như đã mô tả trong bài học, muốn lấy ra khoá của node đầu tiên của danh sách thì dùng lệnh nào?
Vận dụng
- Vận dụng
Ảnh
- Vận dụng:
Câu 1: Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này. Câu 2: Viết hàm delete_Jast(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L.
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "Bài 31. Thực hành thiết lập thư viện chương trình".
Cảm ơn
Ảnh