goupee.vn Trường Đại Học Bách Khoa Hà Nội goupee.com Khoa Điện Tử - Viễn Thông Bộ môn: Điện tử - Tin học Phần 3: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 9: Cấu trúc Tuyến Tính Danh sách móc nối cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Nội dung goupee.com • Giới thiệu – Con trỏ và cấu trúc lưu trữ móc nối – Mô tả danh sách móc nối – Các loại danh sách móc nối • Danh sách nối đơn – Danh sách nối đơn thẳng – Danh sách nối đơn vòng • Danh sách nối kép – Danh sách nối kép thẳng – Danh sách nối kép vòng • Cài đặt LIFO, FIFO bằng cấu trúc lưu trữ móc nốicuu duong than cong . com – LIFO – FIFO fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Con trỏ & Cấu trúc lưu trữ móc nối – Con trỏ (pointer): là một kiểu dữ liệu (datatype) mà giá trị của nó chỉ dùng để chỉ đến một giá trị khác chứa trong bộ nhớ. P A – Các thao tác cơ bản • Khởi tạo (khai báo): int * P; • Lấy địa chỉ 1 đối tượng int A; P = &A; • Truy nhập vào đối tượng được trỏ:cuu duong than cong . com*P = 20; • Cấp phát bộ nhớ động cho đối tượng DL động: P = new int; • Giải phóng đối tượng DL động: delete P; fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Con trỏ & Cấu trúc lưu trữ móc nối – Cấu trúc lưu trữ móc nối – Cấu tạo P • Con trỏ: trỏ đến các nút • Các nút: chứa thông tin về các phần tử và có thể cả con trỏ – Đặc điểm: • Cấu trúc lưu trữ động: cấp phát bộ nhớ trong khi chạy (run-time) • Linh hoạt trong tổ chức cấu trúc: các con trỏ trong cấu trúc có thể tùy ýcuu duong than cong . com thay đổi địa chỉ chỉ đến • Có ít nhất một điểm truy nhập: dùng con trỏ P fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Mô tả danh sách móc nối - Linked List – Tổ chức CTLT: gồm hai thành phần • Các nút (node): lưu trữ các phần tử của danh sách và các con trỏ để liên kết đến các phần tử khác. • Các con trỏ (pointer): biểu diễn các quan hệ trước sau giữa các phần tử. Có ít nhất một con trỏ đóng vai trò điểm truy nhập. H A B C LinkedList – Cấu trúc 1 nút gồm hai phần: • Phần dữ liệu info next • Phần con trỏ chỉ đến nút tiếp theocuu duong than cong . com – H: con trỏ trỏ vào nút đầu của danh sách – Thứ tự và độ dài danh sách có thể thay đổi tuỳ thích fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Cài đặt danh sách bằng CTLT móc nối – Khai báo cấu trúc: struct Node { Type info; Node* next; }; typedef Node* LinkedList; – Nút trống (null, nil): khi con trỏ không chỉ đến đâu: next = NULL – Danh sách rỗng: H LinkedList H;cuu duong than cong . comA B C H = NULL; – Danh sách đầy: khi không còng đủ bộ nhớ để cấp phát fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Phân loại danh sách móc nối Phân loại theo hướng con trỏ (hay số con trỏ trong 1 nút) – Danh sách nối đơn (single linked list): • con trỏ luôn chỉ theo một hướng trong danh sách H A B C – Danh sách nối kép (double linked list) • 2 con trỏ chỉ theo hai hướng trong danh sách H cuu duong than cong . comA B C fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Giới thiệu chung goupee.com • Phân loại danh sách móc nối Phân loại theo cách móc nối vòng hoặc thẳng – Danh sách nối thẳng: truy cập vào danh sách thông qua điểm truy nhập H H A B C – Danh sách nối vòng (circularly linked list): bất cứ nút nào trong danh sách cũng có thể coi là nút đầu hay nút cơ sở (mọi nút có vai trò như nhau) H A B C cuu duong than cong . com first (head) A B C fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt danh sách nối đơn goupee.com • Mô tả – Danh sách nối đơn thẳng (single linked list): • Dùng 1 con trỏ luôn chỉ theo một hướng trong danh sách • Phần tử (nút) cuối của danh sách có con trỏ NULL • Các nút sắp xếp tuần tự trong danh sách H A B C struct Node { Type info; Node* next;cuu duong than cong . com }; typedef Node* PNode; //Kiểu con trỏ nút typedef Node* LinkedList; //Kiểu danh sách nối đơn fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt danh sách nối đơn goupee.com • Danh sách nối đơn thẳng – Các thao tác cơ bản • Khởi tạo danh sách: tạo ra một danh sách rỗng • Kiểm tra trạng thái hiện tại của DS: • Rỗng (Empty): khi con trỏ H = NULL • Phép xen một phần tử mới vào danh sách • Xen phần tử mới vào trước phần tử hiện tại Q: InsertAfter • Xen phần tử mới vào sau phần tử hiện tại Q: InsertBefore • Phép xoá phần tử khỏi danh sách: Delete • Phép tìm kiếm phần tử có dữ liệu = x:cuu duong than cong . comSearch • Phép duyệt danh sách: Traverse fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt danh sách nối đơn goupee.com • Khởi tạo danh sách: void InitList (LinkedList & H) { H = NULL; } • Kiểm tra trạng thái: bool IsEmpty (LinkedList H) { return (H == NULL); } cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối đơn goupee.com • Thao tác bổ sung một phần tử mới K vào sau phần tử hiện tại được trỏ bởi P trong d/s H. Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung PNode InsertAfter(LinkedList & H, PNode P, int K){ Bổ sung một nút Q để chứa K P Nếu d/s H rỗng (H=P=NULL) thì: Q->next = NULL; H=Q; Trái lại, thì: / Q->next=P->next; P->next = Q; return Q; } cuu duong than cong . comK Q fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt hàm bổ sung sau goupee.com 1. PNode InsertAfter(LinkedList & H, PNode P, int K){ 2. PNode Q = new Node; P 3. Q->info = K; 4. if (H==NULL){ 5. H = Q; 6. Q->next = NULL; / 7. 8. }else { 9. if (P==NULL) return NULL; K 10. Q->next = P->next; 11. P->next = Q; Q 12. } cuu duong than cong . com 13. return Q; 14. } fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối đơn goupee.com • Thao tác bổ sung một phần tử mới vào trước phần tử hiện tại P trong d/s H. Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung PNode InsertBefore(LinkedList & H, PNode P, int K) { Bổ sung một nút Q để chứa K Nếu d/s H rỗng (H=P=NULL) thì: P Q->next = NULL; H=Q; a / Trái lại, thì: Chuyển giá trị từ nút P sang nút Q K Cập nhật giá trị của P bằng K a Q->next = P->next; P->next=Q;cuu duong than cong . com return P; Q } fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt hàm bổ sung trước goupee.com 1. PNode InsertBefore(LinkedList & H, PNode P, int K){ 2. PNode Q = new Node; 3. Q->info = K; 4. if (H==NULL){ 5. H = Q; P 6. Q->next = NULL; 7. return Q; 8. }else { a / 9. if (P==NULL) return NULL; 10. Q->info = P->info; K 11. P->info = K; a 12. Q->next = P->next; 13. P->next = Q; 14. } cuu duong than cong . comQ 15. return P; 16. } fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối đơn goupee.com • Phép xóa phần tử hiện tại mà con trỏ P trỏ tới trong danh sách H. void DeleteNode(LinkedList & H, PNode P) { Nếu ds H chỉ có một phần tử (H=P và P->next = NULL) Cập nhật ds thành rỗng: H=NULL; Giải phóng nút P: delete P; Trái lại Nếu nút P là nút đầu ds (P = H) H = H->next; Giải phóng nút P Trái lại Tìm đến nút R đứng ngay trước nút P; R->next= P->next; Giải phóng nút P; } R P cuu duong than cong . com / a fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cài đặt hàm xóa một nút goupee.com • Hàm xóa phần tử hiện tại mà con trỏ P trỏ tới trong ds H. Nó trả về con trỏ trỏ đến nút kế tiếp của nút bị xóa PNode DeleteNode(LinkedList & H, PNode P){ if (P==NULL) return NULL; if (H==P &&P->next==NULL){//Neu ds H chi co 1 phan tu H=NULL; delete P; return NULL; }else { if (H==P){//Neu P la nut dau tien H=P->next; delete P; return H; }else { PNode R=H; while (R->next != P) R=R->next; R->next = P->next;delete P;cuu duong than cong . com return R->next; } } } fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối đơn goupee.com • Phép duyệt danh sách (có thể ứng dụng vào tính số phần tử của danh sách): void Traverse (LinkedList H) { Pnode P; P = H; while (P != NULL) { Visit (P); P = P->next; } } cuu duong than cong . com – Hàm Visit có thể là bất cứ chương trình nào đó làm việc với nút được lựa chọn (P). Nếu đơn thuần nó chỉ tăng lên 1 thì ta có hàm tính tổng số phần tử có trong danh sách. fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối kép goupee.com • Mô tả – Với danh sách đơn sử dụng một con trỏ, ta chỉ có thể duyệt danh sách theo một chiều – Danh sách nối kép (double linked list): • Con trỏ trái (nextL): trỏ tới thành phần bên trái (phía trước) • Con trỏ phải (nextR): trỏ tới thành phần bên phải (phía sau) – Đặc điểm • Sử dụng 2 con trỏ, giúp ta luôn xem xét được cả 2 chiều của danh sách • Tốn bộ nhớ nhiều hơn L R cuu duong than cong . comA A A 1 2 3 nextL INFO nextR fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Danh sách nối kép goupee.com • Định nghĩa danh sách nối kép thẳng struct DNode { Type info; H T DNode *nextL, *nextR; }; A1 A2 A3 typedef DNode* PDNode; typedef struct { PDNode H; //con trỏ đầu PDNode T; //con trỏ cuối } DoubleLinkedList; cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐTTH - Khoa ĐTVT, Đại Học BKHN. Kỹ thuật lập trình - Chương 9 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!