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

Chia sẻ: Utyew WSFGQWET | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

81
lượt xem 9
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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; pItem = pItem->pNext; } if (pItem != 0) { if (pItem == l.pHead) l.pHead = 0; else pItemBefore->pNext = pItem->pNext; delete pItem; } return pItem != 0; © 2004, HOÀNG MINH SƠN } 30 Chương 4: Khái quát về cấu trúc dữ liệu
Chương trình minh họa #include #include "list.h" using namespace std; void main() { MessageList myMailBox; initMessageList(myMailBox); addMessage(myMailBox,"Hi","Welcome, my friend!"); addMessage(myMailBox,"Test","Test my mailbox"); addMessage(myMailBox,"Lecture Notes","Programming Techniques"); removeMessageBySubject(myMailBox,"Test"); MessageItem* pItem = myMailBox.pHead; while (pItem != 0) { cout subject > c; removeAllMessages(myMailBox); } 31 Chương 4: Khái quát về cấu trúc dữ liệu
Bài tập về nhà Xây dựng kiểu danh sách móc nối chứa các ngày lễ trong năm và ý nghĩa của mỗi ngày (string), cho phép: — Bổ sung một ngày lễ vào ₫ầu danh sách — Tìm ý nghĩa của một ngày (₫ưa ngày tháng là tham số) — Xóa bỏ ₫i một ngày lễ ở ₫ầu danh sách — Xóa bỏ ₫i một ngày lễ ở giữa danh sách (₫ưa ngày tháng là tham số) — Xóa bỏ ₫i toàn bộ danh sách Viết chương trình minh họa cách sử dụng © 2004, HOÀNG MINH SƠN 32 Chương 4: Khái quát về cấu trúc dữ liệu