Danh sách liên kết đôi máy tính

Chia sẻ: Nguyen Nam | Ngày: | Loại File: PPT | Số trang:12

Thêm vào BST

Báo xấu

179
lượt xem 39
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Là danh sách mà mỗi phần tử có 2 mối liên kết: Next: để kết nối với phần tử kế tiếp; Prev: để kết nối với phần tử trướ nó.Cài đặt: dự trên con trỏ bao gồm: 3 con trỏ: head, pos và rear; biến count: số phần tử của danh sách

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Danh sách liên kết đôi máy tính

́ ́ Danh sach liên kêt đôi (Doubly Linked List)
• Là danh sach mà môi phân tử có 2 môi liên ́ ̃ ̀ ́ ́ kêt: – Next: để kêt nôi với phân tử kế tiêp ́ ́ ̀ ́ – Prev: để kêt nôi với phân tử trước nó ́ ́ ̀ pos head rear
̣̀ Cai đăt DSLK đôi • Cai đăt: dựa trên con tro, bao gôm: ̀ ̣ ̉ ̀ • 3 con tro: head (đâu ds), pos (phân tử hiên hanh), và ̉ ̀ ̀ ̣ ̀ ́ rear (cuôi ds) • biên count: số phân tử cua danh sach ́ ̀ ̉ ́ typedef struct nodet { next elem data; data struct nodet *next, *prev; } node; prev typedef node *nodeptr;
pos head rear typedef struct { nodeptr head, pos, rear; int count; } list;
́ ́ ́ ́ Cac thao tac trên danh sach liên kêt đôi • Tương tự như danh sach liên kêt đơn ngoai ́ ́ ̣ trừ 2 thao tac (cuc bô) lam thay đôi liên kêt: ́ ̣ ̣̀ ̉ ́ – Chen phân tử vao danh sach ̀ ̀ ̀ ́ – Xoa phân tử trong danh sach liên kêt ́ ̀ ́ ́ • Bổ sung thêm môt số thao tac như: ̣ ́ – Khởi đâu từ cuôi danh sach ̀ ́ ́ – Di chuyên qua phân tử trước phân tử hiên hanh ̉ ̀ ̀ ̣ ̀
Chen phân tử x vao danh sach ̀ ̀ ̀ ́ q p head rear wp • Chen đâu danh sach (xet theo chiêu xuôi): ̀ ̀ ́ ́ ̀ – q = head – newp->next = q – head = newp
Chen phân tử x vao danh sach ̀ ̀ ̀ ́ q p head rear newp • Chen sau p (xet theo chiêu xuôi): ̀ ́ ̀ – q = p->next – newp->next=q – p->next = newp
̉ ̣ ̀ Giai thuât chen Câp phat bộ nhớ cho newp, gan dữ liêu ́ ́ ́ ̣ 1. Xac đinh con trỏ q=(p==NULL? head:p->next) ̣́ 2. ́́ 3. Kêt nôi xuôi 3.1 newp→next = q; 3.2 Nêu p=NULL thì ́ head = newp 3.3 Ngược lai ̣ p→next = newp Kêt nôi ngược ́́ 4. 4.1 newp→prev = p; 4.2 Nêu q=NULL thì ́ rear = newp 4.3 Ngược lai ̣ q→prev = newp ́ 5. Tăng biên count
Ham chen phân tử vao danh sach ̀ ̀ ̀ ̀ ́ void insertlist(list &l, elem &x, nodeptr p) { nodeptr newp, q; newp = new node; memcpy(&newp->data, &x, sizeof(elem)); q = (p==NULL? l.head: p->next); newp->next = q; if (p==NULL) l.head = newp; else p->next = newp; newp->prev = p; if (q==NULL) l.rear = newp; else q->prev = newp; l.count++;
Ham xoa phân tử trongdanh sach ̀ ́ ̀ ́ void deletelist(list &l, nodeptr p) { nodeptr t, q; t = (p==NULL? l.head: p->next); q = t->next; if (p==NULL) l.head = q; else p->next = q; if (q==NULL) l.rear = p; else q->prev = p; delete t; l.count--; }
Bổ sung 2 ham ̀ • Khởi đâu tử cuôi danh sach ̀ ́ ́ void startend(list &l) { l.pos = l.rear; } • Di chuyên đên phân tử trước phân tử hiên hanh ̉ ́ ̀ ̀ ̣ ̀ void skipbefore(list &l) { if (l.pos == NULL) l.pos = l.rear; else l.pos = l.pos->prev; }
• Thiêt kế kiêu số nguyên lớn với cac phep ́ ̉ ́ ́ ́ ̣ ́ ̣ ́ toan: công, nhân. Ap dung tinh 100!, 7100 • 349093429 • 675432