Kiến trúc máy tính - Bài 7
lượt xem 7
download
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ình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Kiến trúc máy tính - Bài 7
- Bài 7 Danh sách liên kết (Linked List) 1
- 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í Danh sách liên kết đơn Danh sách liên kết kép 2
- Danh sách liên kết đơn Các nút (node) được cài đặt bao gồm: next 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 elem node trỏ vào node cuối danh sách. trailer header node NULL elem 3
- 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 Trả lại địa chỉ của phần tử mà nút Element *getElem() 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 4
- Cấu trúc danh sách liên kết đơn Các thuộc tính: Các phương thức cập nhật: Node *header void replace(Node *p, e) Node *trailer Node *insertAfter(Node *p, Các phương thức Elemnt e), chung: Node * insertFirst(Element e) long size(), Node * insertLast(Element e) int isEmpty() Node * getNode(int i) Các phương thức truy void remove(Node *p) cập: Node *first() Node *last() 5
- Insertion First Hình ảnh phép toán insertFirst(), phép toán trả lại vị trí q trailer header NULL A B C trailer header NULL C A B Xq trailer header NULL C X A B 6
- Insertion Last Hình ảnh phép toán insertLast(), phép toán trả lại vị trí q trailer header NULL A B C trailer header NULL C NULL A B q X trailer header NULL X A B C 7
- Insertion After Hình ảnh phép toán insertAfter(p, X), phép toán trả lại vị trí q trailer p header NULL A B C trailer header NULL A B C X trailer header NULL C A B X 8
- Remove Hình ảnh phép toán remove(p) p trailer header NULL C A B X trailer header p A B C X NULL trailer header NULL A B C 9
- 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 sách sinh viên. Mỗi sinh viên gồm các thông tin sau: MaSv, Hoten, Ngay, Thang, Nam sinh, gioi tinh, que quan. Lớp có các các chức năng sau: Thêm một sinh viên vào cuối DS Thêm một sinh viên vào đầu DS Xóa bỏ một sinh viên thu i khỏi DS Thay thế sinh viên thứ I bằng một sinh viên mới Xây dựng chương trinh để chạy lớp ứng dụng 10
- Danh sách liên kết kép Các nút (node) được cài đặt bao prev next gồm: Phần tử lưu trữ trong nó Một liên kết đến nút trước nó Một liên kết đến nút kế tiếp elem n Có hai nút đặc biệt là trailer và header trailer header node Elem 11
- Cấu trúc của một Node Các thuộc tính • Element *elem; • Node *next, *pre; Các phương thức • Node *getnext() Trả lại địa chỉ của nút kế tiếp • Node *getPre() Trả lại địa chỉ của nút trước đó • Element *getElem() Trả lại địa chỉ của phần tử lưu trong nút • void setNext(Node *) Đặt thuộc tính Next trỏ đến đ/c của phần tử là đối của phương thức • void setPre(Node *) Đặt thuộc tính Prior trỏ đến đ/c của phần tử là đối của phương thức • void setElem(Element e) Đặt phần tử e vào nút 12
- Cấu trúc Danh sách liên kết kép Các thuộc tính: Các phương thức cập nhật: Node *header void replace(Node *p, e) Node *trailer Node *insertAfter(Node *p, Các phương thức chung: Elemnt e), long size(), Node *insertBefore(Node *p, int isEmpty() Element e) Các phương thức truy Node * insertFirst(Element e) cập: Node * insertLast(Element e) Node *first() Node * getNode(int i) Node *last() void remove(Node *p) 13
- Insert First Hình ảnh phép toán insertFirst(X), phép toán trả lại vị trí q header trailer A B C trailer header q A B C X q p trailer header X A B C 14
- Insert Last Hình ảnh phép toán insertLast( X), phép toán trả lại vị trí q header trailer A B C trailer header q A B C X q trailer header A B C X 15
- Insert After Hình ảnh phép toán insertAfter(p, X), phép toán trả lại vị trí q p A B C p q A B C X p q A B X C 16
- Thuật toán Insert After Algorithm insertAfter(p,e): //Bổ sung phần tử e vào sau phần tử nút p Tạo ra một nút mới q q.setElement(e) //Đặt gia trị e vào nút p q.setPrev(p) //liên kết q với phần tử trước nó q.setNext(p.getNext())//liên kết với phần tử sau nó (p.getNext()).setPrev(q)//Liên kết phần tử sau p với q p.setNext(q) //liên kết p với q return q //trả lại vị trí của q 17
- Insert Before Hình ảnh phép toán insertBefore(p, X), phép toán trả lại vị trí q p header trailer A B C p header trailer q A B C X p q trailer header A X B C 18
- Xóa Remove Hình ảnh minh họa phép toán remove(p), ở đây p = last() p header trailer A B C D header trailer A B C p D header trailer A B C 19
- Thuật toán remove Algorithm remove(Node *p): //kết nối phần tử trước p với phần tử sau p (p>getPre())>setNext(p>getNext()) //kết nối phần tử sau p với pần tử trước p (p>getNext())>setPre(p>getPre()) //bỏ kết nối p với phần tử trước nó p.setPre(NULL) p.setNext(NULL) delete p 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
7 nguyên nhân gây lỗi Not responding của máy tính
9 p | 322 | 94
-
BXL 32 BIT, VI KIẾN TRÚC NetBurst (NetBurst MICRO-ARCHITECTURE)
8 p | 314 | 77
-
Giáo trình kiến trúc máy tính I - Chương 2
33 p | 220 | 74
-
Giáo trình kiến trúc máy tính I - Chương 3
21 p | 204 | 73
-
Giáo trình kiến trúc máy tính I - Chương 1
30 p | 222 | 72
-
Giáo trình kiến trúc máy tính I - Chương 4
46 p | 169 | 63
-
Giáo trình kiến trúc máy tính I - Chương 7
31 p | 177 | 60
-
Giáo trình kiến trúc máy tính I - Chương 5
20 p | 157 | 59
-
Giáo trình kiến trúc máy tính I - Chương 6
41 p | 160 | 55
-
Kiến trúc máy tính PHẦN II HỢP NGỮ - Chương 7 NHÓM LỆNH CHUYỂN ĐiỀU KHIỂN
40 p | 223 | 37
-
Giáo trình môn học Cấu trúc máy tính - Nghề: Quản trị mạng - Trình độ: Cao đẳng nghề (Phần 1)
67 p | 184 | 36
-
kiến trúc máy tính Vũ Đức Lung phần 7
13 p | 91 | 21
-
Giáo trình Kiến trúc máy tính (Nghề: Quản trị mạng máy tính - Trình độ: Trung cấp) - Trường TCN Quang Trung
97 p | 49 | 14
-
Chương 7 – Tổ chức bộ xử lý
26 p | 120 | 12
-
Giáo trình Cấu trúc máy tính (Nghề: Quản trị mạng máy tính - Trung cấp) - Trường CĐ Nghề Kỹ thuật Công nghệ
51 p | 50 | 12
-
Giáo trình Cấu trúc máy tính (Ngành: Quản trị mạng) - CĐ Công nghiệp Hải Phòng
130 p | 42 | 10
-
Cấu trúc máy tính - Chương 7
36 p | 95 | 8
-
KIẾN TRÚC MÁY TÍNH TIÊN TIẾN
8 p | 101 | 8
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