Tài liệu Slide bài giảng cấu trúc giữ liệu và gỉai thuật 2

Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 2 Danh sách liên kết Ngăn xếp Hàng đợi Cấu trúc dữ liệu và giải thuật – HCMUS 2013 3 Cấu trúc dữ liệu và giải thuật – HCMUS 2013 4  Giới thiệu  Các loại danh sách liên kết  Các thao tác trên danh sách liên kết  So sánh danh sách liên kết và mảng  Ứng dụng Cấu trúc dữ liệu và giải thuật – HCMUS 2013 5  Mảng: cấu trúc dữ liệu quen thuộc  Tập  Số có thứ tự lượng phần tử cố định (tĩnh)  Cấp phát vùng nhớ liên tục  Truy xuất phần tử thông qua chỉ số Cấu trúc dữ liệu và giải thuật – HCMUS 2013 6  Đánh giá thao tác trên mảng: xuất phần tử?  Truy  Cập nhật?  Chèn  Xoá phần tử? phần tử? Cấu trúc dữ liệu và giải thuật – HCMUS 2013 7  Thực tế:  Không xác định được chính xác số lượng phần tử sách bệnh nhân: tăng/giảm.  Danh sách sinh viên: tăng/giảm.  Danh  Vùng nhớ thay đổi trong quá trình sử dụng => Không đủ vùng nhớ cấp phát liên tục. => Cấu trúc dữ liệu động đáp ứng nhu cầu Cấu trúc dữ liệu và giải thuật – HCMUS 2013 8  Danh sách liên kết đơn    Danh sách liên kết kép    singly linked list uni-directional linked list doubly linked list bi-directional linked list Danh sách liên kết vòng   circularly linked list ring list Cấu trúc dữ liệu và giải thuật – HCMUS 2013 9  Mỗi phần tử có MỘT liên kết đến phần tử phía sau nó. 12 99 37 Cấu trúc dữ liệu và giải thuật – HCMUS 2013 10  Mỗi phần tử có HAI liên kết đến phần tử đứng sau và trước nó. 12 99 Cấu trúc dữ liệu và giải thuật – HCMUS 2013 37 11  Có mối liên kết giữa phần tử cuối và phần tử đầu 12 99 37 Cấu trúc dữ liệu và giải thuật – HCMUS 2013 12  Phần tử (Node, Element)  Phần  Ví tử = Dữ liệu + Liên kết dụ:  Phần tử có 1 liên kết  Phần tử có 2 liên kết  Phần tử rỗng Cấu trúc dữ liệu và giải thuật – HCMUS 2013 12 99 13  Phần tử có dữ liệu gồm 1 thành phần number  Phần tử có dữ liệu gồm 3 thành phần name id number  Phần tử có dữ liệu gồm 1 cấu trúc name id number Cấu trúc dữ liệu và giải thuật – HCMUS 2013 14  Sinh viên tự viết phần cài đặt cho các ví dụ trên Cấu trúc dữ liệu và giải thuật – HCMUS 2013 15  Mỗi danh sách liên kết bao gồm:  Con trỏ đến phần tử đầu (hoặc/và cuối) danh sách.  (Các) phần tử trên danh sách  Dữ liệu  Các mối liên kết 12 99 Cấu trúc dữ liệu và giải thuật – HCMUS 2013 37 16 12 99 37 Head 12 99 Head Cấu trúc dữ liệu và giải thuật – HCMUS 2013 37 Tail 17  Thêm phần tử  Duyệt danh sách  Xoá phần tử  Xoá danh sách Cấu trúc dữ liệu và giải thuật – HCMUS 2013 18  Vào đầu danh sách  Sau một phần tử  Vào cuối danh sách Cấu trúc dữ liệu và giải thuật – HCMUS 2013 19  Vào đầu danh sách:  Nếu danh sách rỗng  Phần  Ngược 1 tử vừa thêm là phần tử đầu danh sách lại, 12 99 Head Cấu trúc dữ liệu và giải thuật – HCMUS 2013 37 20  Sau một phần tử (pNode):  Nếu danh sách rỗng?  Nếu danh sách khác rỗng?  Tạo node mới có dữ liệu là Data.  Cập nhật lại liên kết của CurNode và node vừa tạo. 12 CurNode X 99 37 1 Cấu trúc dữ liệu và giải thuật – HCMUS 2013