Bài giảng Lập trình C++ - Chương 6: Cấu trúc tự trỏ

Chương 6: CẤU TRÚC TỰ TRỎ 1. Cấu trúc tự trỏ 2. Danh sách liên kết a. Định nghĩa DSLK b. Khai báo DSLK c. Thao tác trên DSLK 3. Ngăn xếp a. Định nghĩa ngăn xếp b. Khai báo ngăn xếp c. Thao tác trên ngăn xếp 4. Hàng đợi a. Định nghĩa hàng đợi b. Khai báo hàng đợi c. Thao tác trên hàng đợi 1. Cấu trúc tự trỏ a. Cấu trúc dữ liệu động và cấu trúc dữ liệu tĩnh – Mảng là một tập hợp các phần tử cùng kiểu dữ liệu. Số phần tử được xác định trước do vậy mảng được xem như là một cấu trúc dữ liệu tĩnh. – Việc xác định số phần tử trước khi sử dụng sẽ dẫn tới trường hợp thừa, thiếu bộ nhớ. – Một số thao tác như thêm, xóa bỏ một phần tử trong mảng sẽ dẫn tới nhiều phí tổn khi phải di dời một số lượng lớn các phần tử. – Để khắc phục những nhược điểm của mảng người ta đưa ra cấu trúc tự trỏ. Cấu trúc tự trỏ cho phép tạo mối liên kết giữa các phần tử và cấp phát và thu hồi vùng nhớ động. 1. Cấu trúc tự trỏ b. Một số vấn đề liên quan đến cấu trúc tự trỏ – Các thao tác trên con trỏ: khai báo, truy cập tới địa chỉ &, truy cập tới nội dung *, con trỏ NULL – Các phép toán trên con trỏ: gán, cộng với số nguyên, so sánh giữa các con trỏ – Kiểu dữ liệu dạng con trỏ: vô hướng (thực, nguyên, ký tự), có cấu trúc và cả con trỏ hàm – Việc cấp phát vùng nhớ: *malloc(size), calloc(n, size) – Thu hồi vùng nhớ: free(void *buff) 2. Danh sách liên kết a. Định nghĩa DSLK đơn: – DSLK là một dãy các phần tử có thứ tự. Mỗi phần tử là một nút chứa hai thành phần • Data: Chứa thông tin của nút đó • Next: Là con trỏ chỉ đến nút kế tiếp có cấu trúc tương tự hoặc NULL b. Khai báo DSLK – typedef struct node { kdl data; struct node *Next; }; – Với cấu trúc tự trỏ này ta có thể kéo dài danh sách miễn là bộ nhớ cho phép. – Để quản lý cấu trúc người ta chỉ lưu trữ phần tử đầu do vậy việc truy cập tới từng phần tử trong cấu trúc là rất khó. Cũng có một số giải pháp để giải quyết những hạn chế này. – Từ cấu trúc tự trỏ ta có thể tạo lên các dạng cấu trúc khác như ngăn xếp, hàng đợi, cây nhị phân. 2. Danh sách liên kết c. Thao tác chính trên DSLK – Tạo một node – Tạo một danh sách rỗng – Kiểm tra danh sách có rỗng hay không – Xóa/thêm một phần tử • Xóa/thêm đầu danh sách • Xóa/thêm cuối danh sách • Xóa/thêm sau phần tử thứ k trong danh sách – Duyệt qua danh sách Ngăn xếp a. Định nghĩa ngăn xếp – Ngăn xếp là 1 kiểu danh sách đặc biệt với các thao tác chèn, xóa chỉ thực hiện ở một đầu (đỉnh). Như vậy, ngăn xếp là cấu trúc “vào sau ra trước” – LIFO: Last In First Out – Ngăn xếp được ứng dụng nhiều trong tin học (undo, back) b. Khai báo ngăn xếp – Việc khai báo ngăn xếp được thực hiện giống khai báo một danh sách liên kết Ngăn xếp c. Thao tác trên ngăn xếp – Tạo một node – Tạo một ngăn xếp rỗng – Kiểm tra ngăn xếp có rỗng hay không – Thêm một phần tử vào đầu ngăn xếp – Lấy một phần tử ở đầu ngăn xếp – Duyệt qua ngăn xếp 4. Hàng đợi a. Định nghĩa hàng đợi – Hàng đợi là dạng đặc biệt của danh sách liên kết có nguyên tắc thêm vào ở đầu này và lấy ra ở đầu kia: “Vào trước – ra trước) FIFO: First In - First Out. – Hàng đợi được ứng rộng rãi trong tin học như in hoặc một số ứng dụng khác 4. Hàng đợi b. Khai báo hàng đợi – Khai báo nút typedef struct Node { Kdl Data; struct Node *Next; }; typedef struct Node *PointerType; Hàng đợi bao gồm đầu – cuối typedef struct Queue { PointerType FrontPtr; PointerType RearPtr; }; 4. Hàng đợi c. Thao tác trên hàng đợi – Khởi tạo hàng đợi rỗng – Kiểm tra hàng đợi có rỗng hay không – Lấy ra một phần tử ở đầu hàng đợi – Thêm một phần tử vào cuối hàng đợi – Duyệt qua hàng đợi