C3 CTDL

Sự khác biệt giữa kiểu dữ liệu thông thường và kiểu dữ liệu trừu tượng (ADT):

• Kiểu dữ liệu thông thường xác định cả kiểu và phép toán cụ thể.

• Kiểu dữ liệu trừu tượng chỉ định nghĩa các phép toán mà không xác định cách thức triển khai.

Biểu diễn mô hình toán học trong kiểu dữ liệu trừu tượng (ADT):

• Mô hình tập hợp (Set Model)

• Định lý hàm (Function Theorem)

Công dụng của phép toán RETRIEVE(P, L) và cách thức hoạt động:

• Trả về phần tử tại vị trí P trong danh sách L.

• Xóa phần tử tại vị trí P trong danh sách L.

• Thêm phần tử vào danh sách L tại vị trí P.

• Duyệt qua toàn bộ danh sách L.

Vị trí của phần tử đầu tiên trong danh sách liên kết đơn được xác định bởi con trỏ `head`. Con trỏ này luôn trỏ đến phần tử đầu tiên trong danh sách, hoặc `NULL` nếu danh sách rỗng. Vai trò của con trỏ trỏ đến vị trí đầu tiên là gì?

• Giúp dễ dàng tiếp cận phần tử đầu tiên

• Chỉ ra kết thúc của danh sách

• Cập nhật con trỏ của phần tử trước

• Giải phóng bộ nhớ cho phần tử bị xóa

Vị trí sau phần tử cuối trong danh sách liên kết đơn là `NULL`, có nghĩa là không có phần tử nào sau phần tử cuối cùng. Vai trò của con trỏ trong việc xác định vị trí này là gì?

• Giúp nhận biết rằng danh sách đã kết thúc

• Cập nhật con trỏ của phần tử trước

• Giải phóng bộ nhớ cho phần tử bị xóa

• Duyệt qua toàn bộ danh sách

Trong danh sách cài đặt bằng con trỏ, hàm `First(List L)` hoạt động như thế nào để lấy vị trí đầu tiên của danh sách?

• Hàm `First(List L)` trả về con trỏ đến phần tử đầu tiên của danh sách.

• Hàm `First` không duyệt qua danh sách mà chỉ trả về con trỏ `head`.

• Hàm này cho phép người dùng nhanh chóng truy cập phần tử đầu tiên.

• Nếu danh sách có các phần tử `[1, 2, 3]` và `head` trỏ đến phần tử `1`, thì `First(L)` sẽ trả về con trỏ trỏ đến phần tử `1`.

Ngăn xếp (Stack) là gì? Định nghĩa và các đặc điểm cơ bản của ngăn xếp:

• Ngăn xếp (Stack) là một cấu trúc dữ liệu tuyến tính theo nguyên lý LIFO.

• Phần tử cuối cùng được đưa vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra.

• Phép toán này dùng để thêm phần tử vào ngăn xếp.

• Cho phép xem phần tử ở đầu ngăn xếp mà không xóa nó.

Phân tích cấu trúc FIFO (First In - First Out) và so sánh với cấu trúc của các loại dữ liệu khác.

• FIFO là nguyên lý hoạt động của hàng đợi.

• Ngăn xếp sử dụng nguyên lý LIFO.

• Danh sách liên kết có thể được sử dụng theo nhiều cách khác nhau.

• Mảng cho phép truy cập trực tiếp vào bất kỳ phần tử nào.

Hạn chế của kiểu dữ liệu mảng khi nói về khả năng thay đổi kích thước trong quá trình thực hiện chương trình.

• Kích thước cố định

• Mảng không linh hoạt

Thêm phần tử vào đầu danh sách (Insert at Beginning)

• Thêm phần tử vào vị trí đầu tiên của danh sách.

• Tạo một node mới với giá trị cần thêm.

• Con trỏ `next` của node mới trỏ đến phần tử đầu hiện tại.

• Cập nhật con trỏ `head` của danh sách để trỏ đến node mới.