?
本文轉載自GameDev.net，僅供學習交流。因為剛剛開始學習翻譯，難免有些疏漏，如果有哪些地方翻譯的不正確，請不吝告知，萬分感謝。
原文鏈接：http://www.gamedev.net/page/resources/_/technical/general-programming/data-structures-for-pre-college-programmers-choosing-the-right-structure-r2991
?
網絡上的許多初學者還是學生。通常初學者通過在網上看教程，從書上復制代碼和嘗試一些感興趣的東西來學習。
這篇文章是初級開發者所需要了解的數據結構基礎系列文章中的一篇。前一篇文章分析了非線性數據結構。（Non-Linear Structures.）
這篇文章是幫助初學者理解如何選擇一個合適的數據結構或者容器類型。
數據結構
????????? 在該系列的前幾篇文章中說明了最常用的一些數據結構，這里只是一個概括。
????????? 線性的結構包括：數組，動態數組和鏈表。他們之所以是線性的，是因為他們總是呆在你放置他們的地方。數組的隨機訪問 是非常快的，而且在數組末尾添加和刪除數據具有適當良好的性能。如果你頻繁地在中間添加或刪除數據，鏈表將是一個非常好的選擇。
???????? 線性端點數據結構包括：堆和隊列等。他們的工作方式與現實世界中的同名操作非常相似。堆，比如一堆木板或者一個數據堆，你可以把東西放在（push)堆的最上面，可以直接用最早面的一塊木板或者數據，或者你可以直接拿掉（pop)最上面的一個木板或都數據。隊列，像一人排成一個隊伍或一個隊列數據，以從隊尾加入，從隊首移除的方式來工作。
????????? 非線性數據結構包括：數據字典，有序集和無序集。這些結構是內部非線性的，也就是說你把相關數據插入的順序和取出數據的順序是基本無關的。數據字典的工作方式與真正的字典非常相似，它擁有一個關鍵值（key:用來索引的）和值（value:數據值）。一個有序集（ordered set)跟排序過的只包含關鍵值（key)不包含值（value)的數據字典一樣。至于無序集則是像一個數據的抓斗袋（類似抽獎的暗箱),但無序集這個名字是有點誤導性的，實際是他們也是有序的，只是他們排序的方式對我們的使用來說是沒有什么用的。這些非線性的數據結構非常適合快速的查找數據。
一個好的數據結構的影響
? ? ? ? ?大多數時候，程序員只是需要遍歷整個數據集合。通常，當我們需要從頭訪問每個數據項時，我們不關心數據內部是怎么排序的。這種常見的情況中，數據結構的選擇不是很大的問題。
??????? 當有疑問的時候最普遍的選擇是動態數組，它可以變成任意的大小，中規中矩，在后期有需要時也可以很容易的轉換成其它的數據結構。
?????? 但有時候他也有一些問題。
?????? 在游戲中，一個很常見的問題就是尋路。你需要找出一個從a到b的路徑。最常見的尋路算法是a星算法。在a星算法中你需要一個數據結構來存儲部分路徑。這個結構應該是排序過的，這樣可以把我們最最想要的路徑擺放在容器的最前面方便我們使用。如果該路被檢測后發現不是一個完整的路徑，該算法則會使他成為一個更大的路徑的一部分并加入的相當的容器中。?
???????? 使用動態數組作為a星算法的容器將會是一個糟糕的選擇，原因如下：
- 從動態數組的開頭移除一個數組是我們所能執行最低效的一個操作。
- 當加入了一個新的路徑，我們對動態數組進行重新排序是非常低效的。
?
????????? 如果記得之前所說的，還有是這種類型的訪問的最優化的數據結構。我們可以移除最前面的數據，把數據從最后面插入，并自動重排索引出最佳的路徑。優先隊列是a星算法容器類型的一個好的選擇。它通常都內置在語言內部，并通過完善的測試。
根據使用的模式來寫選擇
????????? 使用什么樣的數據結構，通常依據你所使用的設計模式。
動態數組 -- 默認的選擇
????????? 當有疑問的時候，使用動態數組。在c++叫做vector，在java中叫做ArrayList,在c#中叫做List。
????????? 動態數組通常可以符合使用要求。它大多數操作都有好的性能 ，剩余的操作性能也不差。如果你發現你需要其它的數據結構，動態數組也是最容易進行修改的。
堆 -- 只有一端
?????????? 如果你只在單獨的一端添加或刪除。使用堆，在c++中是stack，在java和c#中都叫Statck。
?????????? 有許多算法依賴堆來實現。我的第一個反應就是雙堆計算器（two-stack calculator)。數學問題像漢諾塔也可以通過堆來解決。當然，在游戲編程中，你可能用不到他們。
??????????? 游戲工具經驗解析數據。解析器在很大程度上依賴堆數據結構來保證配對項匹配正確。
???????????? 如果你正在使用各種各樣的ai類型。你可以發現堆數據結構對于自動機家族中的自動下推器是難以估計的實用。
隊列 -- 先進先出
????????? 如果你需要從兩端進行增刪數據，那你你可以使用隊列或者雙端隊列。在c++中叫做queue(隊列)或者deque(雙端隊列).在java中你可以使用Queue或者Deque接口，都是基于LinkList實現的。在c#中只有一個Queue類型，沒有內置雙端隊列（deque）。
????????? 如果你需要保證某些重要的東西第一時間被處理，但除非所有的事情都有序的發生，并且按優先級順序完成。這時你可以使用優先級隊列來處理，在c++中稱為priority_queue.在java中稱為PriorityQueue.C#中你需要自己來實現這個優先級隊列。
非線性結構 -- 快速索引
???????? 如果你需要創建一個穩定的數據結構，并頻繁的進行隨機查找，那么你需要使用非線性數據結構。
???????? 非線性數據結構有的保存一對數據，有的保存獨立的數據。有的是對用戶友好的排序，有的是對計算機友好的排序。如果要列出他們之間的所有組合，又將是一篇文章。實際上，那些在之前的文章中已經詳細的描述過了。 對于這些非線性結構哪些滿足特定的需求，可以查看之前的關于非線性數據結構的文章。
鏈表 -- 頻繁有序的修改
???????? 如果你需要頻繁的在容器中間進行操作數據（增刪），而且你只需要順序的遍歷列表。你可以使用鏈表，在c++中稱為list, 在java和c#中稱為LinkedList。
??????? 當數據需要頻繁的增刪，并且在增刪后必須保持有序狀態時，鏈表是一個非常好的容器選擇。
結論
???????? 選擇正確的數據結構可以讓算法的性能是非常大的改善。
??????? 理解主要的數據結構，包含他們的優缺點可以幫助你選擇你所需要的數據結構。
??????? 我建議你們深入的研究學習這些主要的數據結構。深入學習這些數據結構的計算機科學學位課程通常會持續數星期內。
??????? 希望你已經了解了主要的數據結構，可以在沒有進行數周深入的學習這些數據結構時可以選擇一個好的數據結構。
???????? 這系列的文章已經結束了，感謝閱讀。
本文轉載自GameDev.net，僅供學習交流。因為剛剛開始學習翻譯，難免有些疏漏，如果有哪些地方翻譯的不正確，請不吝告知，萬分感謝。
原文鏈接：http://www.gamedev.net/page/resources/_/technical/general-programming/data-structures-for-pre-college-programmers-choosing-the-right-structure-r2991
?
)
