tailieunhanh - Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật - Bài 2: Danh sách liên kết

Hoàn tất bài thực hành này, sinh viên có thể: Hiểu được các thành phần của danh sách liên kết; thành thạo các thao tác trên danh sách liên kết: thêm phần tử, xóa phần tử, duyệt danh sách liên kết; áp dụng cấu trúc dữ liệu danh sách liên kết vào việc giải quyết một số bài toán đơn giản. | DANH SÁCH LIÊN KẾT K M C TIÊU Hoàn tất bài thực hành này, sinh viên có thể: c th - Hiểu được các thành phần củ danh sách liên kết. ủa Thành thạo các thao tác trên danh sách liên k thêm phần tử, xóa phần tử, duyệt danh sách o kết: , duy liên kết. Áp dụng cấu trúc dữ liệu danh sách liên kết vào việc giải quyết một số bài toán đơn giản. u k Thời gian thực hành: từ 120 phút đế 400 phút ến TÓM T T Danh sách liên kết là cấu trúc dữ liệu dùng để lưu trữ một danh sách (tập hợp hữ hạn) dữ liệu. li ữu Điểm đặc biệt của cấu trúc này là kh năng chứa của nó động (có thể mở rộng và thu hẹp dễ dàng). u khả ng h Có các loại danh sách liên kết: - Danh sách liên kết đơn Danh sách liên kết kép Danh sách liên kết vòng p ad Mỗi danh sách liên kết là tập hợp các phần tử (node) chứa thông tin lưu trữ của dữ liệu. Giữa các phần tử có một hoặc nhiều liên kết để đảm bảo danh sách liên kết có thể giữ các phần tử này một tđ ph cách chặt chẽ. Ví dụ 1: Phần tử có một liên kết Phần tử có hai liên kết Phần t rỗng n tử Ví dụ 2: Danh sách liên kết đơn t Danh sách liên kết kép t Danh sách liên kết vòng t a kết, ng. Chỉ Trong mỗi phần tử của danh sách liên k thông tin liên kết là vô cùng quan trọng. Ch cần một xử lý không cẩn thận có thể làm mất phần liên kết này thì danh sách liên kết sẽ bị ‘gãy từ phần tử đó t ph gãy’ (không thể truy xuất tiếp các phần tử từ phần tử đó trở về trước hoặc trở về sau). ử - Thêm phần tử: vào đầu danh sách liên k vào cuối danh sách liên kết, vào trước/sau một u kết, t, trư phần tử trên danh sách liên kết. k Xóa phần tử: ở đầu danh sách liên kết, ở cuối danh sách liên kết, một phần tử trên danh sách u k nt liên kết. Duyệt danh sách liên kết: để có thể đi được hết các phần tử trên danh sách liên kết. k Tài li u hư ng d n th c hành môn C u trúc d li u và gi i thu t Trang - 1 Các thao tác cơ bản trên danh sách liên kết: n k N I DUNG TH C HÀNH Cơ bản Sinh viên đọc kỹ phát biểu bài tập và thực hiện theo hướng dẫn: Tổ chức một danh sách liên kết đơn trong đó