CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ĐƠN C++

Chia sẻ: Meomeo Nguyen | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

877
lượt xem 97
download

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

CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ĐƠN C++ thêm, sửa, xóa các phân tử trong danh sách liên kết đơn

Chủ đề:

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

Lưu

Nội dung Text: CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ĐƠN C++

CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ĐƠN C++ - Cài đặt: void XoaDau(LIST &l) { if(l.pHead!=NULL) { NODE *pXoa=l.pHead; l.pHead=l.pHead->pNext; delete pXoa; if(l.pHead==NULL)//Trường hợp danh sách có 1 phần tử l.pTail=NULL; } } 6.2. Xóa phần tử cuối (SV tự vẽ hình minh họa) ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... - Đầu vào: DSLK đơn l - Kết quả: DSLK đơn l sau khi xóa phần tử cuối - Giải thuật:
*Trường hợp 1: Nếu l rỗng thì kết thúc *Trường hợp 2: Nếu danh sách có một phần tử thì xóa đầu Ngược lại: B1: pTruoc là con trỏ đứng trước con trỏ cuối của danh sách B2: Cho pTruoc trỏ kế tiếp tới NULL B3: Xóa con trỏ cuối B4: Gán con trỏ cuối là pTruoc - Cài đặt: void XoaCuoi(LIST &l) { if(l.pHead!=NULL) { if(l.pHead==l.pTail) XoaDau(l); else { NODE *pTruoc=TimNodeTruocp(l, l.pTail); pTruoc->pNext=NULL; delete l.pTail; l.pTail=pTruoc; } } } 6.3. Xóa phần tử p cho trước (SV tự vẽ hình minh họa) ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...........................................................................................................................................
........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... - Đầu vào: DSLK đơn l, node p cần xóa - Kết quả: DSLK đơn l sau khi xóa p - Giải thuật: *Trường hợp 1: Nếu p là con trỏ đầu thì xóa đầu *Trường hợp 2: Nếu p là con trỏ cuối thì xóa cuối Ngược lại: B1: pTruoc là con trỏ đứng trước p pSau là con trỏ đứng sau p B2: Xóa p B3: Cho pTruoc trỏ vào pSau - Cài đặt: void Xoap(LIST &l, NODE *p) { if(p==l.pHead) XoaDau(l); else if(p==l.pTail) XoaCuoi(l); else { NODE *pTruoc=TimNodeTruocp(l, p); NODE *pSau = p->pNext; delete p; pTruoc->pNext = pSau; } } 6.4. Xóa phần tử đứng trước phần tử cho trước (SV tự vẽ hình minh họa) ........................................................................................................................................... ........................................................................................................................................... ...........................................................................................................................................
........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................... ...................... - Đầu vào: DSLK đơn l, node p để xác định node cần xóa - Kết quả: DSLK đơn l sau khi xóa trước phần tử p - Giải thuật: *Trường hợp 1: Nếu p là con trỏ đầu thì kết thúc *Trường hợp 2: (p khác con trỏ đầu) B1: pTruoc là con trỏ đứng trước p B2: Xóa pTruoc - Cài đặt: void XoaTruocp(LIST &l, NODE *p) { if(p!=l.pHead) { Trang NODE *pTruoc=TimNodeTruocp(l, p); Xoap(pTruoc); } } 6.5. Xóa phần tử đứng sau phần tử cho trước (SV tự vẽ hình minh họa) ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...........................................................................................................................................
........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... - Đầu vào: DSLK đơn l, node p để xác định node cần xóa - Kết quả: DSLK đơn l sau khi xóa phần tử sau p - Giải thuật: *Trường hợp 1: Nếu p là con trỏ cuối thì kết thúc *Trường hợp 2: (p khác con trỏ cuối) B1: pSau là con trỏ đứng sau p B2: Xóa pSau - Cài đặt: void XoaSaup(LIST &l, NODE *p) { if(p!=l.pTail) { NODE *pSau=p->pNext; Xoap(pSau); } } 6.6.Hủy toàn bộ danh sách (SV tự vẽ hình minh họa) ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... - Đầu vào: DSLK đơn l - Kết quả: DSLK đơn l sau khi hủy (rỗng)
- Giải thuật: Trong khi con trỏ đầu khác NULL thì xóa đầu - Cài đặt: void Huy(LIST &l) { while(l.pHead) XoaDau(l); }