Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản - Đậu Ngọc Hà Dương

Chia sẻ: Bạch Đăng Kỳ | Ngày: | Loại File: PPTX | Số trang:76

Thêm vào BST

Báo xấu

28
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản - Đậu Ngọc Hà Dương có nội dung trình bày các kiến thức về danh sách liên kết, ngăn xếp, hàng đợi,... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản - Đậu Ngọc Hà Dương

Cấu trúc dữ liệu và giải thuật CÁC CẤU TRÚC DỮ LiỆU CƠ BẢN Giảng viên:
Nội dung trình bày 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
3 Danh sách liên kết Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Nội dung 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 2012
Giới thiệu 5  Mảng: cấu trúc dữ liệu quen thuộc  Tập có thứ tự  Số 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 2012
Giới thiệu 6  Đánh giá thao tác trên mảng:  Truy xuất phần tử?  Cập nhật?  Chèn phần tử?  Xoá phần tử? Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Giới thiệu 7  Thực tế:  Không xác định được chính xác số lượng phần tử  Danh sách bệnh nhân: tăng/giảm.  Danh sách sinh viên: tăng/giảm.  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 Cấuữ litrúc ấu trúc d dữ ệu và gi liệu ải thu động đáp ật – HCMUS 2012 ứng nhu cầu
Các loại danh sách liên kết 8  Danh sách liên kết đơn  singly linked list  unidirectional linked list  Danh sách liên kết kép  doubly linked list  bidirectional linked list  Danh sách liên kết vòng  circularly linked list Cấu trúc dữ liệu và giải thuật – HCMUS 2012  ring list
Danh sách liên kết đơn 9  Mỗi phần tử có MỘT liên kết đến phần tử phía sau nó. 9 12 37 9 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Danh sách liên kết đơn 10 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Danh sách liên kết kép 11  Mỗi phần tử có HAI liên kết đến phần tử đứng sau và trước nó. 9 12 37 9 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Danh sách liên kết vòng 12  Có mối liên kết giữa phần tử cuối và phần tử đầu 9 12 37 9 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Phần tử trên danh sách liên kết 13  Phần tử (Node, Element)  Phần tử = Dữ liệu + Liên kết  Ví dụ: 12  Phần tử có 1 liên kết 9 9  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 2012
Ví dụ 14  Ví dụ:  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  name Phần tử có dữ liệidu gnumber ồm 1 cấu trúc Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Cài đặt 15  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 2012
Tổ chức 16  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 9 12 37 9 Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Tổ chức 17 9 12 37 9 pHead 9 12 37 9 pHead pTail Cấu trúc dữ liệu và giải thuật – HCMUS 2012
Các thao tác trên danh sách liên kết 18  Thêm phần tử  Duyệt danh sách  Xoá phần tử  Truy xuất phần tử  Xoá ữdanh Cấu trúc d sách liệu và giải thuật – HCMUS 2012
Thêm phần tử 19  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 2012
Thêm phần tử 20  Vào đầu danh sách:  Nếu danh sách rỗng  Phần tử vừa thêm là phần tử đầu danh sách  Ngược lại, 9 1 12 37 9 pHead Cấu trúc dữ liệu và giải thuật – HCMUS 2012