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ướ đặ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 | Danh sách liên kết đôi (Doubly Linked List) 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ước nó rear head pos Cài đặt DSLK đôi Cài đặt: dựa trên con trỏ, bao gồm: 3 con trỏ: head (đầu ds), pos (phần tử hiện hành), và rear (cuối ds) biến count: số phần tử của danh sách typedef struct nodet { elem data; struct nodet *next, *prev; } node; typedef node *nodeptr; data prev next typedef struct { nodeptr head, pos, rear; int count; } list; rear head pos Các thao tác trên danh sách liên kết đôi Tương tự như danh sách liên kết đơn ngoại trừ 2 thao tác (cục bộ) làm thay đổi liên kết: Chèn phần tử vào danh sách Xóa phần tử trong danh sách liên kết Bổ sung thêm một số thao tác như: Khởi đầu từ cuối danh sách Di chuyển qua phần tử trước phần tử hiện hành Chèn phần tử x vào danh sách Chèn đầu danh sách (xét theo chiều xuôi): q = head newp->next = q head = newp rear head p q newp Chèn phần tử x vào danh sách Chèn sau p (xét theo chiều xuôi): q = p->next newp->next=q p->next = newp head p q newp rear Giải thuật chèn Cấp phát bộ nhớ cho newp, gán dữ liệu Xác định con trỏ q=(p==NULL? head:p->next) Kết nối xuôi newp next = q; Nếu p=NULL thì head = newp Ngược lại p next = newp Kết nối ngược newp prev = p; Nếu q=NULL thì rear = newp Ngược lại q prev = newp Tăng biến count Hàm chèn phần tử vào danh sách void insertlist(list &l, elem &x, nodeptr p) { nodeptr newp, q; newp = new node; memcpy(&newp->data, &x, sizeof(elem)); q = (p==NULL? : p->next); newp->next = q; if (p==NULL) = newp; else p->next = newp; newp->prev = p; if (q==NULL) = newp; else q->prev = newp; ; } Hàm xóa phần tử trongdanh sách void deletelist(list &l, nodeptr p) { nodeptr t, q; t = (p==NULL? : p->next); q = t->next; if (p==NULL) = q; else p->next = q; if (q==NULL) = p; else q->prev = p; delete t; ; } Bổ sung 2 hàm Khởi đầu tử cuối danh sách void startend(list &l) { = ; } Di chuyển đến phần tử trước phần tử hiện hành void skipbefore(list &l) { if ( == NULL) = ; else = >prev; } Thiết kế kiểu số nguyên lớn với các phép toán: cộng, nhân. Áp dụng tính 100!, 7100 349093429 675432
