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ướ đặ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

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.