1 of 44

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

2 of 44

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.

  • Danh sách các trang web đã từng duyệt qua.
  • Danh sách các bài hát, video trong một playlist.
  • Danh sách bạn bè trên mạng xã hội.

Ví dụ:

3 of 44

BÀI 30: THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH

4 of 44

NỘI DUNG BÀI HỌC

01

Thiết lập thư viện cho chương trình

02

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

5 of 44

THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH

01

6 of 44

Chia lớp thành các nhóm 2 - 4 HS

Hoạt động 1

Em hãy đọc, thảo luận và trả lời các câu hỏi sau:

2. Ý nghĩa của các hàm trong thư viện chương trình là gì?

1. Vì sao lại cần thư viện chương trình?

7 of 44

a) Một số hàm của thư viện math

  • math là một thư viện các hàm chuẩn của Python liên quan đến các tính toán toán học.

Ví dụ:

sqrt() - hàm tính căn bậc hai

floor() -

làm tròn xuống

ceil() -

làm tròn lên

8 of 44

  • Để đưa thư viện vào bộ nhớ có thể dùng lệnh import hoặc from <thư viện> import <các hàm> như sau:

import math # đưa toàn bộ thư viện math vào bộ nhớ

from math import sqrt, floor, ceil # chỉ đưa vào bộ nhớ ba hàm

hoặc:

9 of 44

Ví dụ

10 of 44

b) Tự thiết lập thư viện

  • Cách thiết lập: Đư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ữ.

* Xét ví dụ sau:

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:

11 of 44

12 of 44

  • Chương trình sử dụng thư viện 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:

1 from lib import * # Đưa tất cả các hàm của thư viện lib vào bộ nhớ

2 A = NhapDL()

3 InsertionSort(A)

4 print(A)

13 of 44

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

14 of 44

Câu hỏi củng cố kiến thức SGK - tr.138

Chương trình sẽ ngắn hơn

Những câu nào sau đây sai về ý nghĩa của việc sử dụng thư viện khi viết chương trình?

A

Các hàm thư viện được viết 1 lần và sử dụng nhiều lần.

B

Chương trình sáng sủa, dễ hiểu hơn.

C

Chương trình sẽ chạy nhanh hơn.

D

15 of 44

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

02

16 of 44

Nhiệm vụ 1. Mô hình danh sách liên kết

Hoạt động 2

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

17 of 44

  • Mỗi danh sách liên kết sẽ bao gồm hai cấu trúc dữ liệu:

1. Cấu trúc Node: mô tả các phần tử độc lập của danh sách. Tối thiểu mỗi node cần có thông tin dữ liệu key (khóa) và thuộc tính next dùng để kết nối sang phần tử tiếp theo trong danh sách.

class Node:

def _init­_(self,key):

self.key = key

self.next = None

18 of 44

  • Mỗi danh sách liên kết sẽ bao gồm hai cấu trúc dữ liệu:

2. Cấu trúc LL (Linked list): sẽ có thông tin head (đầu) sẽ luôn chỉ vào node đầu tiên của danh sách liên kết.

class LL:

def_init_(self):

self.head = None

19 of 44

Cấu trúc LL

key của node

next

chỉ sang node tiếp theo

Các node của danh sách

None là dữ liệu rỗng. Node cuối của danh sách next = None

  • Mô hình danh sách liên kết được tổng hợp trong sơ đồ sau:

20 of 44

  • Một số lệnh, thao tác chính với kiểu dữ liệu 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 khóa k cho trước vào danh sách.

Tìm kiếm phần tử có khóa k trong danh sách cho trước.

Xóa phần tử có khóa k trong danh sách.

21 of 44

  • Thiết lập một số hàm là các 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 khóa k vào đầu của danh sách L.

Chương trình như sau:

1 def insert(L,k):

2 node = Node(k)

3 node.next = L.head

4 L.head = node

22 of 44

2. Hàm delete_first(L) sẽ xóa node đầu tiên của danh sách (nếu danh sách không rỗng):

Chương trình như sau:

1 def delete_first(L,k):

2 if L.head != None:

3 L.head = L.head.next

23 of 44

3. Hàm tìm kiếm phần tử có khóa k trong danh sách L. Nếu tìm thấy sẽ trả về phần tử (node) tương ứng, nếu không tìm thấy trả về None.

Việc tìm kiếm bắt đầu từ node đầu tiên của danh sách (dòng 2). Lần lượt duyệt theo từng phàn tử của danh sách cho đến khi nào tìm thấy phần tử có khóa k hoặc đi đến cuối danh sách thì dừng (các lệnh dòng 3,4).

1 def search(L,k):

2 x = L.head

3 while x != None and x.key != k:

4 x = x.next

5 return x

24 of 44

4. Hàm xóa phần tử có khóa k trong danh sách L.

  • Nếu phần tử cần tìm là node đầu tiên của danh sách thì cách xóa giống hàm delete_first().
  • Trong trường hợp tổng quát cần duyệt để tìm phần tử của danh sách có khóa k. Trong quá trình tìm luôn lưu trữ biến z là node trước của biến y cần xóa (lệnh x.next = y.next).

25 of 44

Chương trình như sau:

Nếu node đầu tiên có khóa k thì xóa node này.

Tìm kiếm node chứa khóa k. y là biến cần tìm, z luôn chỉ vào node trước của y. Nếu tìm thấy khóa k thì xóa node y.

26 of 44

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

1 def show(L):

2 x = L.head

3 while x != None:

4 print(x.key, end = " ")

5 x = x.next

6 print()

Tham khảo toàn bộ thư viện chuẩn trong SGK trang 141

27 of 44

Nhiệm vụ 2. Lập trình cấu trúc danh sách liên kết trên Python

  • Một số ví dụ thiết lập cấu trúc dữ liệu Linked List:

a) Thiết lập một danh sách rỗng

L = LL()

b) Thiết lập một danh sách bao gồm hai node có khóa là 5, 2.

L = LL()

insert(L,5)

insert(L,2)

28 of 44

c) Thiết lập một danh sách bao gồm các phần tử lấy từ dãy A cho trước

A = [5,2,8,10,0,3]

L = LL()

for k in A:

insert(L,k)

29 of 44

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 xóa thông tin trên danh sách liên kết.

30 of 44

Câu hỏi củng cố kiến thức SGK - tr.142

Câu 1. Đoạn chương trình sau thực hiện công việc gì?

from LinkedList import *

L = LL()

insert(L,10)

insert(L,20)

show(L)

Tạo một danh sách liên kết rỗng

Bổ sung các phân tử có khóa 10, 20 vào danh sách

In danh sách ra màn hình

31 of 44

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.

L = LL()

insert(L,"Bình")

insert(L,"Hoa")

insert(L,"Hà"

show(L)

32 of 44

33 of 44

Câu 1: Tên thư viện trong Python có phần mở rộng là

  • D. py
  • A. lib
  • B. pym
  • C. module

34 of 44

Câu 2: Câu lệnh nào trong Python dùng để import tất cả các hàm của thư viện tên lib?

  • A. from lib import *
  • D. from lib include all
  • B. from lib import all
  • C. from lib include *

35 of 44

Câu 3: Hàm lấy căn bậc hai sqrt() có trong thư viện nào của Python?

  • B. math
  • D. calendar
  • A. time
  • C. numpy

36 of 44

Câu 4: Hàm nào xóa node đầu tiên của danh sách (nếu danh sách không rỗng)?

  • C. delete_first(L)
  • D. show(L)
  • A. search(L,k)
  • B. delete(L,k)

37 of 44

Câu 5: Đoạn chương trình sau đang thực hiện công việc gì?

A = [1,2,3,4,5,6,7,8]

L = LL()

for k in A:

insert(L,k)

  • C. Thiết lập một danh sách bao gồm các phần tử lấy từ dãy A cho trước.
  • D. Thiết lập một danh sách liên kết A và bổ sung các phần tử 1, 2, 3, 4, 5, 6, 7, 8
  • A. Thiết lập một danh sách rỗng.
  • B. Thiết lập một danh sách bao gồm 8 node có khóa là 1, 2, 3, 4, 5, 6, 7, 8.

38 of 44

LUYỆN TẬP

Bài 1 (SGK - tr.142). 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.

Thư viện có tên sapxep có thể thiết lập như sau:

39 of 44

40 of 44

Bài 2 (SGK - tr.142). 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 khóa của node đầu tiên của danh sách thì dùng lệnh nào?

Lệnh sau sẽ lấy ra khóa của phần tử đầu tiên trong danh sách L (nếu L không rỗng).

value = L.head.key

41 of 44

VẬN DỤNG

Bài 1 (SGK - tr.142) 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.

1 def len(L):

2 k = 0

3 x = L.head

4 while x != None:

5 x = x.next

6 k = k + 1

7 return k

Tham khảo:

42 of 44

Bài 2 (SGK - tr.142) Viết hàm delete_last(L) có chức năng xóa phần tử cuối cùng của danh sách liên kết L.

Tham khảo:

1 def delete_last(L):

2 if L.head != None:

3 y = L.head

4 x = L.head

5 while x.next != None:

6 y = x

7 x = x.next

8 y.next = None

43 of 44

HƯỚNG DẪN VỀ NHÀ

Ghi nhớ kiến thức đã học

Hoàn thành bài tập trong SBT

Xem trước Bài 31: Thực hành thiết lập thư viện chương trình

44 of 44

CẢM ƠN SỰ CHÚ Ý �LẮNG NGHE CỦA CÁC EM!