Bài giảng Cấu trúc dữ liệu và giải thuật: Doubly/Circular linked list - TS. Ngô Hữu Dũng

INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY<br /> <br /> Data structures and algorithms<br /> Doubly/Circular linked list<br /> Dr. Ngo Huu Dung<br /> <br /> Dẫn nhập<br /> <br /> <br /> Danh sách liên kết đôi<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Danh sách liên kết vòng<br /> <br /> <br /> <br /> <br /> 2<br /> <br /> Hai chiều<br /> Thêm con trỏ previous<br /> Từ một nút có thể duyệt đến nút trước và sau nó<br /> Các thao tác tương tự singly linked list<br />  Xử lý thêm cho con trỏ previous<br /> Nút cuối trỏ đến nút đầu<br /> Có thể là danh sách đơn hoặc đôi<br /> Các thao tác tương tự<br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br /> prev<br /> <br /> data<br /> <br /> next<br /> <br /> prev<br /> <br /> data<br /> <br /> next<br /> <br /> prev<br /> <br /> data<br /> <br /> next<br /> tail<br /> <br /> head<br /> NULL<br /> <br /> NULL<br /> <br /> Doubly linked list<br /> Danh sách liên kết đôi<br /> <br /> Doubly linked list – Khai báo<br /> <br /> <br /> Khai báo nút kiểu cấu trúc<br /> <br /> <br /> <br /> <br /> <br /> Phần dữ liệu (int, float, char, struct…)<br /> Phần liên kết (pointer)<br /> <br /> Khai báo con trỏ head và tail<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> 7.<br /> 8.<br /> 9.<br /> <br /> 4<br /> <br /> struct Node<br /> {<br /> int data;<br /> struct Node *next;<br /> struct Node *prev;<br /> };<br /> typedef struct Node tNode;<br /> tNode *head;<br /> tNode *tail;<br /> <br /> prev<br /> <br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br /> data<br /> <br /> head<br /> tail<br /> <br /> next<br /> <br /> Thao tác cơ bản<br /> Khởi tạo danh sách, nút mới<br />  Thêm phần tử<br /> <br /> <br /> <br /> <br /> <br /> <br /> Duyệt danh sách<br /> <br /> <br /> <br /> <br /> 5<br /> <br /> Min, max, giá trị X<br /> <br /> Xoá phần tử<br /> <br /> <br /> <br /> <br /> Xuất, trích xuất, đếm, tính toán<br /> <br /> Tìm kiếm<br /> <br /> <br /> <br /> <br /> Vào đầu, vào cuối, chèn vào sau một phần tử<br /> <br /> Ở đầu, ở cuối, ở giữa<br /> <br /> Sắp xếp<br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br />