Tin học 11 Kết nối tri thức bài 30

Tin học 11 Kết nối tri thức bài 30: Thiết lập thư viện cho chương trình được VnDoc.com sưu tầm và xin gửi tới bạn đọc cùng tham khảo để có thêm tài liệu giải SGK Tin 11 Kết nối tri thức. Mời các bạn cùng theo dõi bài viết dưới đây.

Khởi động

Câu hỏi. 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.

Bài làm

Một số ví dụ thực tế của mô hình danh sách liên kết:

- Quản lý danh bạ: Một ứng dụng quản lý danh bạ điện thoại di động có thể sử dụng mô hình danh sách liên kết đơn để lưu trữ danh sách các liên hệ. Mỗi liên hệ có thể được biểu diễn là một đối tượng trong danh sách liên kết, trong đó mỗi đối tượng chứa thông tin như tên, số điện thoại, địa chỉ, và liên kết đến liên hệ tiếp theo trong danh sách.

- Trình quản lý tập tin: Một trình quản lý tập tin trên hệ điều hành có thể sử dụng mô hình danh sách liên kết đôi để duyệt qua các thư mục và tập tin trong hệ thống tập tin. Mỗi thư mục hoặc tập tin có thể được biểu diễn là một đối tượng trong danh sách liên kết đôi, trong đó mỗi đối tượng chứa thông tin như tên, đường dẫn, kích thước, và liên kết đến thư mục hoặc tập tin trước và sau nó trong danh sách.

- Quản lý bài đăng trên mạng xã hội: Một mạng xã hội có thể sử dụng mô hình danh sách liên kết kép để quản lý các bài đăng của người dùng. Mỗi bài đăng có thể được biểu diễn là một đối tượng trong danh sách liên kết kép, trong đó mỗi đối tượng chứa thông tin như nội dung, người đăng, thời gian đăng, và liên kết đến bài đăng trước và sau nó trong danh sách.

- Duyệt web: Một trình duyệt web có thể sử dụng mô hình danh sách liên kết kép để duyệt qua các trang web đã xem trước đó. Mỗi trang web có thể được biểu diễn là một đối tượng trong danh sách liên kết kép, trong đó mỗi đối tượng chứa thông tin như URL, tiêu đề, nội dung, và liên kết đến trang web trước và sau nó trong danh sách.

1. Thiết lập lệnh cho chương trình

Hoạt động 1: Tìm hiểu ý nghĩa của thư viện chương trì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ì?

Bài làm

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

2. Có chức năng đưa thư viện vào bộ nhớ để sẵn sàng sử dụng.

Câu hỏi. 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.

Bài làm

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

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

Hoạt động 2: Tìm hiểu 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.

Bài làm

Danh sách liên kết là cấu trúc dữ liệu bao gồm:

Cấu trúc note mô tả các phần tử của danh sách. Mỗi node sẽ có dữ liệu khóa (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.

Câu hỏi 1. Đoạn hàm sau thực hiện công việc gì?

Bài làm

Đoạn mã trên sử dụng thư viện LinkedList và tạo một đối tượng danh sách liên kết mới (gọi là L) bằng cách gọi hàm khởi tạo LL().

Sau đó, thực hiện hai lần gọi hàm insert(L,10) và insert(L,20) để chèn các giá trị 10 và 20 vào danh sách liên kết L.

Cuối cùng, gọi hàm show(L) để hiển thị nội dung của danh sách liên kết L sau khi đã chèn các giá trị 10 và 20 vào trong đó.

Vậy đoạn mã này thực hiện việc tạo danh sách liên kết mới, chèn các giá trị 10 và 20 vào danh sách, và hiển thị danh sách liên kết đó.

Câu hỏi 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.

Bài làm

from LinkedList import *

# Tạo danh sách liên kết mới

L = LL()

# Thêm các tên vào danh sách liên kết

insert(L, "Bình")

insert(L, "Hoa")

insert(L, "Hà")

# Hiển thị nội dung của danh sách liên kết

show(L)

3. Luyện tập

Câu hỏi 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.

Bài làm

def nhap_day_so():

"""Hàm nhập dãy số từ bàn phím"""

n = int(input("Nhập số lượng phần tử của dãy: "))

a = []

for i in range(n):

a.append(int(input(f"Nhập phần tử thứ {i+1}: ")))

return a

def sap_xep_chen(a):

"""Hàm sắp xếp dãy số bằng phương pháp sắp xếp chèn"""

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0 and key < a[j]:

a[j+1] = a[j]

j -= 1

a[j+1] = key

return a

def sap_xep_chon(a):

"""Hàm sắp xếp dãy số bằng phương pháp sắp xếp chọn"""

for i in range(len(a)):

min_idx = i

for j in range(i+1, len(a)):

if a[j] < a[min_idx]:

min_idx = j

a[i], a[min_idx] = a[min_idx], a[i]

return a

def sap_xep_noi_bot(a):

"""Hàm sắp xếp dãy số bằng phương pháp sắp xếp nổi bọt"""

for i in range(len(a)):

for j in range(0, len(a)-i-1):

if a[j] > a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

return a

Câu hỏi 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?

Bài làm

#include <stdio.h>
#include <stdlib.h>
struct Node
{
//khai bao thanh phan du lieu co kieu int
int data;
//khai bao con tro next co kieu Node
Node *next;
};
typedef struct Node NODE;

struct list{
//thanh phan dau danh sach
NODE *pHead;
//thanh phan cuoi danh sach
NODE *pTail;
};
typedef struct list LIST;

void KhoiTao(LIST &ds){
//dat dia chi dau danh sach bang NULL
ds.pHead = NULL;
//dat dia chi cuoi danh sach bang NULL
ds.pTail = NULL;
}
int KiemTraRong(LIST ds){
//neu phan tu dau danh sach NULL
if (ds.pHead == NULL){
//tra ve 1 la co NULL
return 1;
}
//truong hop nguoc lai tra ve khong null
return 0;
}
printf("\nDU LIEU TRONG DANH SACH LIEN KET DON\n");
Xuat(ds);
}

4. Vận dụng

Câu hỏi 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.

Bài làm

Để lấy ra khoá của node đầu tiên trong danh sách liên kết, bạn có thể sử dụng thuộc tính key của đối tượng node đầu tiên trong danh sách.

Câu hỏi 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.

Bài làm

Để xoá phần tử cuối cùng của danh sách liên kết ta cần duyệt từ đầu danh sách đến nút cuối cùng sau đó xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó. Nếu danh sách rỗng hoặc chỉ có một phần tử thì ta chỉ cần xoá phần tử đó và trả về danh sách. Mã nguồn Python cho hàm delete_last() như sau:

def delete_last(L):
# Nếu danh sách rỗng, trả về None
if L is None:
return None

# Nếu danh sách chỉ có một phần tử, xoá phần tử đó và trả về danh sách
if L.next is None:
del L
return None

# Tìm nút cuối cùng và nút trước nó
prev_node = None
curr_node = L
while curr_node.next is not None:
prev_node = curr_node
curr_node = curr_node.next

# Xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó
prev_node.next = None
del curr_node

# Trả về danh sách đã được xoá phần tử cuối cùng
return L

-----------------------------------------------

Bài tiếp theo: Tin học 11 Kết nối tri thức bài 31

VnDoc.com vừa gửi tới bạn đọc bài viết Tin học 11 Kết nối tri thức bài 30: Thiết lập thư viện cho chương trình. Mời các bạn cùng tham khảo thêm tại mục Tin học 11 Kết nối tri thức.