Khái quát về cấu trúc dữ liệu phần 4

Sử dụng rất linh hoạt, cấp phát bộ nhớ khi cần và xóa khi không cần — Bổ sung và xóa bỏ một dữ liệu ₫ược thực hiện thông qua chuyển con trỏ, thời gian thực hiện là hằng ngày.
Nội dung trích xuất từ tài liệu:
Khái quát về cấu trúc dữ liệu phần 4 Bổ sung dữ liệu pHead pHead pHead Dữ liệu T Dữ liệu A Dữ liệu B Dữ liệu A Dữ liệu T Dữ liệu B Dữ liệu C Dữ liệu C Dữ liệu X© 2004, HOÀNG MINH SƠN Dữ liệu X 0x00 Dữ liệu Y 0x00 Dữ liệu Y Bổ sung vào giữa danh sách Bổ sung vào ₫ầu danh sách 25 Chương 4: Khái quát về cấu trúc dữ liệu Xóa bớt dữ liệu pHead pHead Dữ liệu A Dữ liệu A Dữ liệu B Dữ liệu B Dữ liệu C Dữ liệu C Dữ liệu X Dữ liệu X© 2004, HOÀNG MINH SƠN 0x00 Dữ liệu Y 0x00 Dữ liệu Y Xóa dữ liệu ₫ầu danh sách Xóa dữ liệu giữa danh sách 26 Chương 4: Khái quát về cấu trúc dữ liệu Các ₫ặc ₫iểm chính Ưu ₫iểm: — Sử dụng rất linh hoạt, cấp phát bộ nhớ khi cần và xóa khi không cần — Bổ sung và xóa bỏ một dữ liệu ₫ược thực hiện thông qua chuyển con trỏ, thời gian thực hiện là hằng số, không phụ thuộc vào chiều dài và vị trí — Có thể truy nhập và duyệt các phần tử theo kiểu tuần tự Nhược ₫iểm: — Mỗi dữ liệu bổ sung mới ₫ều phải ₫ược cấp phát bộ nhớ ₫ộng — Mỗi dữ liệu xóa bỏ ₫i ₫ều phải ₫ược giải phóng bộ nhớ tương© 2004, HOÀNG MINH SƠN ứng — Nếu kiểu dữ liệu không lớn thì phần overhead chiếm tỉ lệ lớn — Tìm kiếm dữ liệu theo kiểu tuyến tính, mất thời gian 27 Chương 4: Khái quát về cấu trúc dữ liệu Ví dụ: Danh sách thông báo (hộp thư) #include using namespace std; struct MessageItem { string subject; string content; MessageItem* pNext; }; struct MessageList { MessageItem* pHead; }; void initMessageList(MessageList& l); void addMessage(MessageList&, const string& sj,© 2004, HOÀNG MINH SƠN const string& ct); bool removeMessageBySubject(MessageList& l, const string& sj); void removeAllMessages(MessageList&); 28 Chương 4: Khái quát về cấu trúc dữ liệu #include List.h void initMessageList(MessageList& l) { l.pHead = 0; } void addMessage(MessageList& l, const string& sj, const string& ct) { MessageItem* pItem = new MessageItem; pItem->content = ct; pItem->subject = sj; pItem->pNext = l.pHead; l.pHead = pItem; } void removeAllMessages(MessageList& l) { MessageItem *pItem = l.pHead; while (pItem != 0) { MessageItem* pItemNext = pItem->pNext;© 2004, HOÀNG MINH SƠN delete pItem; pItem = pItemNext; } l.pHead = 0; } 29 Chương 4: Khái quát về cấu trúc dữ liệu bool removeMessageBySubject(MessageList& l, const string& sj) { MessageItem* pItem = l.pHead; MessageItem* pItemBefore; while (pItem != 0 && pItem->subject != sj) { pItemBefore = pItem; ...