TAILIEUCHUNG - Cấu trúc dữ liệu và giải thuật assignment 01 - Unrolled linked list

Trong bài tập lớn này, sinh viên sẽ sửa đổi danh sách liên kết đã học thành một cấu trúc dữ liệu mới là danh sách liên kết mở (unrolled linked list). Cấu trúc dữ liệu này tương tự như danh sách liên kết thông thường ngoại trừ việc có thể có nhiều hơn một phần tử được lưu tại mỗi node. Sinh viên có thể tham khảo thêm về unrolled linked list từ các tài liệu khác, tuy nhiên có thể mô tả sẽ khác ít nhiều so với assignment này. | Vietnam National University – HCMC Hochiminh University of Technology Faculty of Computer Science and Engineering Đại Học Quốc Gia Trường Đại học Bách Khoa Khoa KH&KT Máy Tính CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ASSIGNMENT 01 - Unrolled linked list 1 Giới thiệu Trong bài tập lớn này, sinh viên sẽ sửa đổi danh sách liên kết đã học thành một cấu trúc dữ liệu mới là danh sách liên kết mở (unrolled linked list). Cấu trúc dữ liệu này tương tự như danh sách liên kết thông thường ngoại trừ việc có thể có nhiều hơn một phần tử được lưu tại mỗi node. Sinh viên có thể tham khảo thêm về unrolled linked list từ các tài liệu khác, tuy nhiên có thể mô tả sẽ khác ít nhiều so với assignment này. Giống như mảng (array) và danh sách liên kết, unrolled linked list cũng là cấu trúc dữ liệu tuyến tính. Thay vì lưu một phần tử dữ liệu tại mỗi node, danh sách này lưu một mảng các phần tử tại một node. Nhờ cách này, danh sách tận dụng được lợi thế từ cả hai cấu trúc dữ liệu mảng và danh sách liên kết vì nó giảm được overhead của danh sách liên kết khi lưu nhiều phẩn tử trong một node và có thể thêm, xoá dễ dàng. Một unrolled linked list dcó thể được mô tả như hình bên dưới: Hình 1: Unrolled linked list với tối đa 4 phần tử mỗi node. Mỗi node trong danh sách chứa một array với số lượng phần tử tối đa là maxElements. Vị trí của phần tử trong danh sách có thể được xác định bằng tham khảo hoặc vị trí trong array. Có 2 thao tác cơ bản có thể được thực hiện trên danh sách là phép chèn (insertion) và phép xoá (deletion) • Chèn: để chèn một phần tử vào vị trí cụ thể, chúng ta tìm node mà phần tử cần được đặt vào và chèn phần tử đó vào array, đồng thời tăng số phần tử trong node (numElements). Nếu array của node trước đó đã đầy, chúng ta sẽ tạo ra một node mới ngay sau node hiện tại và chuyển phân nữa số phần tử node hiện tại sang node mới. Thao tác này sẽ làm cho kích thước danh sách tăng lên 1. • Xoá: để xoá một phần tử tại một vị trí cụ thể nào đó, chúng ta tìm node chứa phần tử đó và .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật assignment 01
• Unrolled linked list
• Cấu trúc dữ liệu
• Giải thuật assignment 01
• Danh sách liên kết mở
• Cấu trúc dữ liệu tập hợp TreeSet1
• Ưu hóa mã nguồn
• Bài giảng Cấu trúc dữ liệu
• Danh sách liên kết đơn
• Danh sách hạn chế
• Danh sách đặc
• Khai báo cấu trúc