intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Danh sách liên kết - Nguyễn Minh Huy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST
Báo xấu
13
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Danh sách liên kết, được biên soạn gồm các nội dung chính sau khái niệm danh sách liên kết; Các thao tác trên danh sách đơn; Cải tiến danh sách liên kết đơn. 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 Kỹ thuật lập trình: Danh sách liên kết - Nguyễn Minh Huy

  1. Danh sách liên kết GV. Nguyễn Minh Huy Kỹ thuật lập trình - Nguyễn Minh Huy 1
  2. Nội dung Khái niệm danh sách liên kết. kết. Các thao tác trên danh sách đơn. đơn. Cải tiến danh sách liên kết đơn. đơn. Kỹ thuật lập trình - Nguyễn Minh Huy 2
  3. Nội dung Khái niệm danh sách liên kết. kết. Các thao tác trên danh sách đơn. đơn. Cải tiến danh sách liên kết đơn. đơn. Kỹ thuật lập trình - Nguyễn Minh Huy 3
  4. Khái niệm danh sách liên kết Nhận xét về mảng một chiều: chiều: Tính chất: chất: Các phần tử liên tiếp nhau trong bộ nhớ. nhớ. Kích thước bộ nhớ không co dãn. dãn. a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a ? ? ? ? ? ? ? ? ? ? Ưu điểm: điểm: Truy xuất phần tử bằng chỉ số nhanh. nhanh. Thuận tiện lưu số lượng phần tử cố định. định. Khuyết điểm: điểm: Thêm, Thêm, xóa phần tử không thuận tiện. tiện. Thay đổi kích thước phải cấp lại bộ nhớ. nhớ. Tìm vùng nhớ lớn liên tiếp nhau không dễ. dễ. Kỹ thuật lập trình - Nguyễn Minh Huy 4
  5. Khái niệm danh sách liên kết Giải pháp danh sách liên kết: kết: Bài toán “thuê ngăn tủ đựng đồ”: đồ”: RAM (4GB) 0 Cần thuê N ngăn tủ chứa N đồ vật. vật. Mỗi ngăn tủ chỉ chứa được 1 đồ vật. vật. Giải pháp mảng: mảng: Thuê N ngăn tủ liên tiếp. tiếp. Giữ STT ngăn đầu tiên. tiên. … Giải pháp danh sách liên kết: kết: Thuê N ngăn tủ không liên tiếp. tiếp. Mỗi ngăn chứa: chứa: 1 đồ vật. vật. 232 Mẫu giấy ghi STT ngăn tiếp theo. theo. Giữ STT ngăn tủ đầu tiên. tiên. Kỹ thuật lập trình - Nguyễn Minh Huy 5
  6. Khái niệm danh sách liên kết Danh sách liên kết đơn: đơn: Một dãy các phần tử không liên tiếp. tiếp. Mỗi phần tử = Dữ liệu + Địa chỉ phần tử kế. kế. Phần tử cuối giữ địa chỉ NULL. Giữ địa chỉ phần tử đầu. đầu. data data data head next next next NULL Khai báo trong C: struct SNode { int data; SNode *next; }; Kỹ thuật lập trình - Nguyễn Minh Huy 6
  7. Nội dung Khái niệm danh sách liên kết. kết. Các thao tác trên danh sách đơn. đơn. Cải tiến danh sách liên kết đơn. đơn. Kỹ thuật lập trình - Nguyễn Minh Huy 7
  8. Các thao tác trên danh sách đơn Khởi tạo danh sách: sách: Danh sách rỗng. rỗng. head NULL Kiểm tra danh sách rỗng: rỗng: Kiểm tra head NULL. head NULL ??? Kỹ thuật lập trình - Nguyễn Minh Huy 8
  9. Các thao tác trên danh sách đơn Tìm phần tử: tử: Phần tử thứ i. Phần tử có dữ liệu x. Phần tử cuối dãy. dãy. Thứ tự i data = x cuối dãy data data data data head next next next next NULL Kỹ thuật lập trình - Nguyễn Minh Huy 9
  10. Các thao tác trên danh sách đơn Thêm phần tử: tử: Đầu danh sách. sách. Cuối danh sách. sách. Giữa danh sách: sách: Sau phần tử thứ i. Giữ thứ tự. tự. Thêm đầu Thêm giữa Thêm cuối data data data next next next data data data data head next next next next NULL Kỹ thuật lập trình - Nguyễn Minh Huy 10
  11. Các thao tác trên danh sách đơn Xóa phần tử: tử: Đầu danh sách. sách. Cuối danh sách. sách. Giữa danh sách: sách: Sau phần tử i. Phần tử có dữ liệu x. Xóa cả danh sách. sách. data data data data head next next next next NULL Kỹ thuật lập trình - Nguyễn Minh Huy 11
  12. Nội dung Khái niệm danh sách liên kết. kết. Các thao tác trên danh sách đơn. đơn. Cải tiến danh sách liên kết đơn. đơn. Kỹ thuật lập trình - Nguyễn Minh Huy 12
  13. Cải tiến danh sách liên kết đơn Danh sách liên kết vs. Mảng một chiều: chiều: Danh sách liên kết Mảng một chiều Bố trí phần tử Không liên tục Liên tục Giới hạn bộ nhớ Không giới hạn Vùng nhớ liên tục Thay đổi kích thước Tùy ý Cấp phát lại + sao chép Độ phức tạp: O(1) Độ phức tạp: O(n) Truy xuất phần tử Tuần tự Trực tiếp bằng chỉ số. Độ phức tạp: O(n) Độ phức tạp: O(1) Tìm kiếm Tiến Tiến và lùi. Độ phức tạp: O(n) Độ phức tạp: O(n) Thêm/Xóa phần tử Không dời phần tử Phải dời phần tử Độ phức tạp: O(1) Độ phức tạp: O(n) Hao phí bộ nhớ Lưu địa chỉ phần tử kế Không hao phí Hao phí: 4 * n bytes Kỹ thuật lập trình - Nguyễn Minh Huy 13
  14. Cải tiến danh sách liên kết đơn Danh sách kép: kép: Danh sách đơn duyệt tiến, không lùi. tiến, lùi. Head: duyệt tiến. tiến. Tail: duyệt lùi. lùi. data data data head next next next NULL NULL prev prev prev tail Khai báo trong C: struct DNode struct DList { { int data; DNode *head; DNode *next; DNode *tail; DNode *prev; prev; }; }; Kỹ thuật lập trình - Nguyễn Minh Huy 14
  15. Cải tiến danh sách liên kết đơn Danh sách vòng: vòng: Cần duyệt danh sách đơn nhiều lần. lần. Phần tử danh sách vòng giống danh sách đơn. đơn. Phần tử cuối trỏ đến phần tử đầu. đầu. data data data head next next next Khai báo trong C: struct CNode { int data; CNode *next; }; Kỹ thuật lập trình - Nguyễn Minh Huy 15
  16. Tóm tắt Danh sách liên kết: kết: Phần tử lưu trữ phân tán. tán. Phần tử = dữ liệu + địa chỉ phần tử kế. kế. Phần tử cuối trỏ đến NULL. Các thao tác trên danh sách đơn: đơn: Khởi tạo, kiểm tra rỗng. tạo, rỗng. Tìm, thêm, xóa. Tìm, thêm, xóa. Cải tiến danh sách liên kết đơn: đơn: Danh sách kép. kép. Danh sách vòng. vòng. Kỹ thuật lập trình - Nguyễn Minh Huy 16
  17. Bài tập Bài tập 8.1: Viết chương trình C cài đặt các thao tác (như trong bài học) trên danh học) sách kép và danh sách vòng. vòng. Kỹ thuật lập trình - Nguyễn Minh Huy 17
  18. Bài tập Bài tập 8.2: Viết chương trình C cài đặt các thao tác trên danh sách liên kết đơn: đơn: - Đếm số nút trong danh sách. sách. - Đảo ngược danh sách. sách. - Thêm phần tử (giữ nguyên thứ tự). tự). Kỹ thuật lập trình - Nguyễn Minh Huy 18
  19. Bài tập Bài tập 8.3 (*): Một khuyết điểm của danh sách liên kết so với mảng một chiều là khả năng truy xuất phần tử. tử. Hãy đề xuất một cách cải tiến khả năng truy xuất phần tử của danh sách liên kết sao cho có thể GẦN BẰNG với mảng một chiều. chiều. Kỹ thuật lập trình - Nguyễn Minh Huy 19
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2