Danh sách liên kết

Tham khảo tài liệu danh sách liên kết, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Danh sách liên kết Danh sách liên kết (Linked List) Giới thiệu cấu trúc “Danh sách p liên kết” p Các loại hình danh sách liên k ết Danh sách liên kết đơn p p Danh sách liên kết đôi p Danh sách liên kết vòng Cách xây dựng cấu trúc p Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 1Nội dung trình bày Đặt vấn đề p p Danh sách liên kết là gì ? p Cấu tạo của nút p Cấu tạo của danh sách liên kết p Các loại danh sách liên kết p So sánh Mảng và Danh sách liên kết p Các thao tác trên danh sách liên kết đơn p Giới thiệu các loại danh sách liên k ết khác Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 2 1Đặt vấn đề p Nếu muốn thêm (Insert) 1 phần tử vào mảng, phải làm sao ? 10 5 13 11 6 12 9 ? 18 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 3Đặt vấn đề p Phải di chuyển các phần tử về phía sau 1 vị trí ... 18 10 5 13 11 6 12 9 ? chèn phần tử mới vào p …và 10 5 13 11 6 12 9 18 p Vậy chi phí là O(n) Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 4 2Đặt vấn đề p Hỏi: muốn xóa (Delete) một phần tử trong mảng ? 10 5 13 11 6 12 9 ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 5Đặt vấn đề sao có thể thêm (hay xoá) 1 phần tử p Làm mà không phải di chuyển các phần tử khác ? p Ta cần phải dùng một cấu trúc lưu trữ mới Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 6 3Đặt vấn đề tách rời các phần tử của mảng, và kết nối p Ta chúng lại với nhau bằng một “móc xích” 10 20 30 ? ? 18 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 7Đặt vấn đề tác thêm phần tử chỉ cần thay đổi các p Thao mối liên kết tại chỗ 10 20 30 ? ? 18 phí thấp p Chi Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 8 4Danh sách liên kết là gì ? Một dãy tuần tự các nút (Node)p Giữa hai nút có con trỏ liên kếtp Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớp Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)p Thao tác Chèn/Xóa không cần phải dịch chuyển phần tửp Phần tử đầu là pHeadp Có thể truy xuất đến các phần tử khác thông qua con trỏp liên kết Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCMSpring 2004 9Cấu tạo của nút p Tạo lập bằng cách cấp phát bộ nhớ động p Mỗ ...