這個數據的哪個數據結構？

Question

我正在爲一個基本的OOP C++課程編寫一個項目。我必須實現Media類型的對象集（以及派生對象Book,Movie,Album）。對這些集合的操作是：添加元素，刪除某個元素（不一定是第一個或最後一個元素），搜索集合（搜索可以返回多個結果）。排序不是必需的，但我認爲這將是一個很好的補充。

所以我想知道，這將是最好的數據結構？簡單的數組，矢量或列表？ （請注意，我必須寫實現，我不能使用std類。） 因爲我沒有處理大量數據，所以我並不關心效率或內存消耗，但我仍然應該能夠解釋我爲什麼選擇一個特定的數據結構。

我認爲一個列表將是優選的用於去除和添加項目，但向量具有索引操作符[]，可以是用於搜索功能（其可以返回索引的陣列）是有用的。

Answer 1

作爲一款家用的工作，我建議在第一次使用簡單的鏈表。爲了搜索，你可以返回你找到的項目的指針或迭代器（如果你的List類與STL容器兼容）。在你的情況下，你有多個子類，你可能需要把基類 - 媒體的指針放在容器中。如果是的話，你需要考慮如何管理內存。例如釋放元素時釋放內存。

Answer 2

如果你不關心什麼，你爲什麼不乾脆用一個two dimensional array或linked list？我認爲在這種情況下它是最好的。

Answer 3

我會做一個列表，實現爲一個二叉樹。
對於搜索功能，您可以返回一個指針數組。

Answer 4

如果不關心效率或內存消耗，那麼你應該選擇一個與它是一個數組最簡單的實現的東西。在最後插入新項目，通過將陣列中的最後一個東西移動到間隙中來刪除項目。通過遍歷整個數組進行搜索。

如果你沒有關於效率小心，你可能會實現一個哈希表或者平衡樹。

Answer 5

我認爲在你的情況下，最好的容器是一張地圖。每個媒體都有一個id，這是媒體的關鍵（像書本ISBN），所以你不能用同一個id來保存兩本書的地圖。