tailieunhanh - Kiến trúc máy tính - Bài 7

Danh sách liên kết (Linked List) Mô hình cấu trúc dữ liệu trừu tượng Linked List là một dãy các vị trí lữu trữ các đối tượng với số lượng tùy ý. | Bài 7 Danh sách liên kết (Linked List) Danh sách liên kết đơn Danh sách liên kết kép Mô hình cấu trúc dữ liệu trừu tượng Linked List là một dãy các vị trí lữu trữ các đối tượng với số lượng tùy ý. Nó thiết lập một mối quan hệ trước/sau giữa các vị trí Vectors 5/13/2020 11:04:01 PM Danh sách liên kết đơn Các nút (node) được cài đặt bao gồm: Phần tử lưu trữ trong nó Một liên kết đến nút kế tiếp Sử dụng môt con trỏ header, trỏ vào node đầu danh sách và con trỏ trailer trỏ vào node cuối danh sách. next elem header node elem node trailer NULL Cấu trúc của một Node Các thuộc tính Element *elem; Node *next; Các phương thức Node *getnext() - Trả lại địa chỉ của nút kế tiếp Element *getElem() - Trả lại địa chỉ của phần tử mà nút trỏ tới trong nút void setNext(Node *) - Đặt thuộc tính next trỏ đến đ/c phần tử là đối của phương thức void setElem(Element e) - Đặt phần tử e vào nút Cấu trúc danh sách liên kết đơn Các thuộc tính: Node *header Node *trailer Các phương thức . | Bài 7 Danh sách liên kết (Linked List) Danh sách liên kết đơn Danh sách liên kết kép Mô hình cấu trúc dữ liệu trừu tượng Linked List là một dãy các vị trí lữu trữ các đối tượng với số lượng tùy ý. Nó thiết lập một mối quan hệ trước/sau giữa các vị trí Vectors 5/14/2020 12:40:36 AM Danh sách liên kết đơn Các nút (node) được cài đặt bao gồm: Phần tử lưu trữ trong nó Một liên kết đến nút kế tiếp Sử dụng môt con trỏ header, trỏ vào node đầu danh sách và con trỏ trailer trỏ vào node cuối danh sách. next elem header node elem node trailer NULL Cấu trúc của một Node Các thuộc tính Element *elem; Node *next; Các phương thức Node *getnext() - Trả lại địa chỉ của nút kế tiếp Element *getElem() - Trả lại địa chỉ của phần tử mà nút trỏ tới trong nút void setNext(Node *) - Đặt thuộc tính next trỏ đến đ/c phần tử là đối của phương thức void setElem(Element e) - Đặt phần tử e vào nút Cấu trúc danh sách liên kết đơn Các thuộc tính: Node *header Node *trailer Các phương thức chung: long size(), int isEmpty() Các phương thức truy cập: Node *first() Node *last() Các phương thức cập nhật: void replace(Node *p, e) Node *insertAfter(Node *p, Elemnt e), Node * insertFirst(Element e) Node * insertLast(Element e) Node * getNode(int i) void remove(Node *p) Insertion First Hình ảnh phép toán insertFirst(), phép toán trả lại vị trí q A B C header trailer NULL A B C trailer NULL header X A B C trailer NULL header X q Insertion Last Hình ảnh phép toán insertLast(), phép toán trả lại vị trí q A B C header trailer NULL A B C trailer NULL header B C X trailer NULL header A X NULL q Insertion After Hình ảnh phép toán insertAfter(p, X), phép toán trả lại vị trí q A B C header trailer NULL A B C trailer NULL header B X C trailer NULL header A X p Remove Hình ảnh phép toán remove(p) A B C trailer NULL header B X C trailer NULL header A X A B C header trailer NULL p p Bài tập về nhà Xây dựng lớp ứng dụng sử dụng lớp Danh sách liên kết đơn để lưu trữ 1 danh .