Lập trình với các cấu trúc dữ liệu cấp phát động Nội dung Giới thiệu Các cấu trúc móc nối Cấp phát dữ liệu động Danh sách liên kết Ngăn xếp (Stacks) Hàng đợi (Queues) Cây (Trees) Mục tiêu của chương – Cấp phát bộ nhớ động cho các đối tượng dữ liệu. – Cấu trúc dữ liệu liên kết sử dụng con trỏ, – Khởi tạo và thao tác trên danh sách liên kết, hàng đợi, ngăn xếp và cây nhị phân. – Hiểu về khả năng phát triển ứng dụng phức tạp sử dụng cấu trúc dữ liệu liên. | Lập trình với các cấu trúc dữ liệu cấp phát động Nôi dung Giới thiệu Các cấu trúc móc nối Cấp phát dữ liệu động Danh sách liên kết Ngăn xếp Stacks Hàng đợi Queues Cây Trees Giới thiệu Các cấu trúc dữ liệu động - Các cấu trúc dữ liệu cho phép mở rộng và thu nhỏ trong khi thực hiện chuông trình. Các danh sách hên kết - Cho phép chèn thêm và xoá bất kỳ ở đâu Stacks - Cho phép chèn và xoá chỉ trên đỉnh của stack Hàng đợi - Queues - Cho phép chèn ở đáy phía sau và xoá ở đỉnh phía truớc Cây nhị phân - Tìm kiếm và sắp xếp nhanh và hiệu quả _ 3 Mục tiêu của chương -Cấp phát bộ nhớ động cho các đối tượng dữ liệu. - Cấu trúc dữ liệu hên kết sử dụng con trỏ - Khởi tạo và thao tác trên danh sách hên kết hàng đợi ngăn xếp và cây nhị phân. - Hiểu về khả năng phát triển ứng dụng phức tạp sử dụng cấu trúc dữ liệu hên kết. 2 Danh sách liên kết Danh sách liên kết - Tập họp tuyến tính về lớp đối tượng liên kết với nhau các đối tượng liên kết gọi là các nút - Các nút được kết nối với nhau bởi con trỏ - Truy cập thông qua con trỏ trỏ đến nút đầu tiên trong danh sách - Các nút được truy cập thông qua thành phần con trỏ hên kết của nút hiện tại. - Con trỏ hên kết trong nút sau cùng trỏ đến NULL đánh dấu kết thúc danh sách. Sử dụng danh sách liên kết thay cho array khi - Chúng ta không biết trước số phần tử trong danh sách - Danh sách cần được sắp xếp nhanh. startPtr Hg. A graphical representation of a linked list. 4 Mô tả cấu trúc danh sách hên kết TYPE LPtr A ListNode ElementType . ListNode RECORD Data ElementType NextPtr LPtr END VAR H LPtr Danh sách liên kết Một số thao tác cơ bản trên danh sách hên kết - Khởi tạo một danh sách - Bổ sung một phần tử vào đầu danh sách - Tạo một danh sách - Bổ sung một phần tử qA vào sau phần tử trỏ bởi p - Bổ sung một phần tử qA vào truớc phần tử trỏ bởi p - Xóa phần tử liền sau liền truớc p. - Duyệt toàn bộ danh sách - Nối hai danh sách Danh sách liên kết đơn VAR p q LPtr Một danh sách móc nối đơn giản có con trỏ H trỏ đến nút đầu tiên trong .
