Dữ liệu có thể được tổ chức khác nhau
Điểm theo học sinh và môn có thể nhìn như một bảng hai chiều. Một chuỗi nút liên kết lại được đọc bằng cách lần theo nút kế tiếp. Chọn cấu trúc ảnh hưởng cách truy cập dữ liệu.
Mảng và các nút liên kết
Mảng một chiều tổ chức phần tử theo chỉ số; mảng hai chiều có chỉ số hàng và cột. Trong Python, ta thường dùng list hoặc list các list để thực hành, nhưng list Python không hoàn toàn giống mảng có kích thước cố định trong mọi ngôn ngữ.
Danh sách liên kết gồm các nút chứa dữ liệu và liên kết; dạng đơn mỗi nút trỏ nút kế tiếp. Muốn tới nút sau có thể phải lần từ đầu; không mặc nhiên truy cập tức thì theo chỉ số như mô hình mảng. Chèn nút có thể sửa liên kết tại vị trí đã biết, nhưng việc tìm vị trí vẫn có chi phí.
Đọc hàng và cột
```python
a = [[2, 4, 6], [1, 3, 5]]
print(a[1][2])
print(sum(a[0]))
```
a[1] là hàng thứ hai [1,3,5], phần tử chỉ số 2 là 5. Tổng hàng đầu là 12. Hai dòng kết quả là 5 và 12.
Thử vận dụng
Với a = [[7, 8], [9, 10]], a[0][1] là gì?
7 ở cột 0 của hàng 0.
Đúng: hàng đầu, cột thứ hai.
9 ở hàng 1, cột 0.
10 ở hàng 1, cột 1.
Lời giải
Chọn hàng chỉ số 0 rồi cột chỉ số 1, được 8.
Chèn nút trong danh sách liên kết
Chuỗi nút A → C → kết thúc. Đã biết vị trí A, muốn chèn B sau A: cho B trỏ C rồi cho A trỏ B. Kết quả A → B → C. Phải giữ thông tin tới C trước khi đổi liên kết để không làm mất phần sau.
Ví dụ xem cách làm
Tính tổng cột thứ hai của [[2,4,6],[1,3,5]].
Lời giải
4 + 3 = 7. Cột thứ hai có chỉ số 1: a[0][1] và a[1][1].
Ví dụ xem cách làm
Vì sao không thể khẳng định danh sách liên kết luôn tìm phần tử thứ 100 nhanh như mảng truy cập theo chỉ số?
Lời giải
Danh sách liên kết thường phải lần theo các nút từ vị trí biết trước. Truy cập theo số thứ tự vì vậy khác truy cập trực tiếp bằng chỉ số trong mô hình mảng.
Những điều cần nhớ
Đọc mảng hai chiều theo hàng rồi cột. Với danh sách liên kết, theo dõi các nút và liên kết; không bỏ qua chi phí tìm vị trí.
Đang học