Quản lý nhân viên bằng danh sách liên kết đôi C++
Show
1 Cài đặt danh sáchCấu trúc của 1 Node trong danh sách liên kết kép tương đối giống với DSLKD nhưng có thêm một con trỏ trỏ về Node trước nó Cấu trúc của DSLKK không như DSLKD có 1 Con trỏ trỏ đến đầu DS, nhưng DSLKK ngoài con trỏ trỏ đến đầu danh sách còn có thêm 1 con trỏ trỏ đến Node cuối của danh sách 2 Khởi tạo và kiểm tra rỗngKhởi tạo ta cho 2 con trỏ đầu và cuối trỏ vê NULL, Khi kiểm tra rỗng thi chỉ cần xem con trỏ đầu có trỏ về NULL không là đủ 3. Độ dài danh sáchĐể tìm độ dài của DSLKK ta hoàn toàn có thể làm giống như DSLKD, tức dùng con trỏ duyệt từ đầu đến cuối, nhưng trong DSLKK ta có thể dùng 2 con trỏ ở đầu và cuối để đếm int Len (DList L) // Do dai danh sach { Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L int i = 0; //bien dem if (PH != NULL) i = 1; while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam) { if (PH == PT) break; PH = PH->Right; //cho PH tro den Node tiep theo i++; if (PH == PT) break; PT = PT->Left; //cho PT tro den Node truoc do i++; } return i; //tra lai so Node cua L }4. Tạo 1 Node P chứa thông tinNode *Make_Node (item x) //tao 1 Node P chua thong tin la x { Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P P->Data = x; //Ghi du lieu vao Data P->Left = NULL; P->Right = NULL; return P; }5. Chèn phần tử vào vị trí đầu tiênTrước khi chèn vào đầu danh sách cần kiểm tra xem danh sách rỗng hay không. Nếu danh sách rỗng ta cho Head và Tail đều trỏ đến P. Nếu không rỗng thực hiện chèn. 6. Chèn phần tử vào cuối danh sách tương tự như đầu danh sáchvoid Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach { Node *P; P = Make_Node(x); //tao 1 Node P if (Isempty(L)) //Neu danh sach rong { L.Head = P; L.Tail = P; } else { L.Tail->Right = P; //ket noi voi danh sach P->Left = L.Tail; //P tro ve Node truoc L.Tail = P; //luu lai vi tri cuoi } }Trước khi chèn vào vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách. Nếu chèn vào giữa danh sách ta thực hiện theo 4 bước Chèn x vào vị trí k trong danh sách liên kết kép void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach { Node *PH = L.Head, *PT, *R; int i=1, l = Len(L); if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien else { R = Make_Node(x); //tao 1 Node P if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien else if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi else //chen vao vi tri 18. Xóa phần tử đầu, cuối danh sách// Lay gia tri can xoa ra, sau do bo qua 1 Node dau tien void Del_first (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Head->Data; //lay gia tri ra neu can dung L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach } } // Lay gia tri can xoa ra, sau do bo qua 1 Node cuoi void Del_last (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Tail->Data; L.Tail = L.Tail->Left; L.Tail->Right = NULL; } }9. Xóa phần tử ở vị trí kTrước khi xóa ở vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách hay ở giữa void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach { Node *PH = L.Head, *PT; int i=1, l = Len(L); if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien else { if (k == 1) Del_first(L,x); //xoa vi tri dau tien else if (k == l) Del_last(L,x); //xoa vi tri cuoi else //xoa vi tri 110. Tìm phần tử x trong DSint Search (DList L, item x) //tim x trong danh sach { Node *P=L.Head; int i=1; while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach { P = P->Right; i++; } if (P != NULL) return i; //tra ve vi tri tim thay else return 0; //khong tim thay }11. Xóa phần tử x trong DSvoid Del_x (DList &L, item x) //xoa phan tu x trong danh sach { int l = Search(L,x); while (l) { Del_k (L,x,l); //trong khi van tim thay x thi van xoa l = Search(L,x); } }12. Chương trình hoàn chỉnh#include[rps-include post=”2703″ shortcodes=”false”] |