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

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
Nội dung trích xuất từ tài liệu:
Danh sách liên kết đôi máy tính ́ ́Danh sach liên kêt đôi(Doubly Linked List)• Là danh sach 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ước nó ́ ́ ̀ poshead 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), và ̉ ̀ ̀ ̣ ̀ ́ 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; prevtypedef node *nodeptr; poshead reartypedef 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 rearwp• 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 phead 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 trỏ 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 thì ́ 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 thì ́ 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 ...