在我編程的10年中，我可以統計一下我使用的數據結構的數量：數組，鏈表（我用這個來堆棧和隊列）和字典。考慮到幾乎所有我寫的應用程序都屬於數據格式/ CRUD類別，這並不奇怪。實踐中的高級數據結構
我從來沒有需要使用紅黑樹，跳過列表，雙端隊列，循環鏈表，優先級隊列，堆，圖，或任何數十個已經研究過的奇特數據結構過去的50年。我覺得我錯過了。
這是一個開放式的問題，但這些「異國情調」的數據結構在實踐中使用在哪裏？有沒有人有使用這些數據結構來解決特定問題的實際經驗？
一些例子。他們是模糊的，因爲他們是爲僱主工作：
一個heap獲得在谷歌風格的搜索的前N個結果。 （從索引中的候選人開始，通過線性遍歷它們，篩選出最大大小爲N的最小堆）。這是一個圖像搜索原型。
Bloom filters將某些數據的大小減少到了幾百萬用戶已經看到的數量，這些數據適合現有的服務器（爲了提高速度，它們都必須在RAM中）;原來的設計將需要許多新的服務器，僅用於該數據庫。
A triangular array representation將推薦引擎的密集對稱陣列的大小減半（出於同樣的原因再次使用RAM）。用戶不得不根據某些關聯進行分組; union-find使這個簡單，快速，準確，而不是慢，哈克和近似。
一個應用程序選擇零售網站根據開車時間在附近的人使用Dijkstra shortest-path優先隊列。其他GIS工作利用了quadtrees和Morton指數。
瞭解數據結構中有什麼 - 土地派上用場 - 「實驗室中的數週可以節省您在圖書館的時間」。 bloom-filter案例僅僅因爲規模而值得：如果問題出現在創業公司而不是雅虎公司，那麼我會使用一個普通的舊hashtable。我認爲其他的例子在任何地方都是合理的（儘管現在你不太可能自己編寫它們）。
它取決於你工作的抽象級別。
我知道我和你有相似的經歷。在目前大多數軟件開發的抽象層面上。 Dictionary和List是我們使用的主要數據結構。
我認爲如果你向下看低級代碼，你會看到更多的「異國情調」的數據結構。
我同意。考慮到我的代碼在軟件堆棧中有多高，如果有我需要的數據結構，並且它不存在於我的代碼下的現有庫中，那麼這通常是庫的一個缺點。 – reuben 2008-12-25 06:03:10
他們經常在圖書館的幕後使用。例如有序字典的數據結構（即associative array通過按鍵alows有序遍歷）是可能不使用red-black tree.
許多數據結構（splay trees浮現在腦海中）是在一定的最優行爲有趣的實現的情況下（temporal locality of reference在張大樹的情況下），所以它們主要與這些情況下的使用有關。在大多數情況下，對這些數據結構的實際操作知識的真正好處是能夠在合理的情況下在合理理解其行爲的情況下使用它們。
採取分揀，例如：
在大多數情況下quicksort 或修飾的快速排序那滴 另一種方法，當 各個段得到足夠小 通常是最快的排序 算法對於大多數目的。 但是，快速排序往往會在 近似排序的數據上顯示 次優行爲。
一個heap sort的主要優點是，它可以在原位 進行具有最小中間 存儲，這使得它相當不錯 用於存儲器用途受限 系統。儘管它平均速度較慢（儘管仍然是n log（n）），但它並不受中劣勢最差情況下的性能 的影響。
第三個例子是一個merge sort，這是可以做到 順序，使得它最好 選擇用於分類的數據集比你的主存儲器多 大。 另一個名稱是 '外部排序'，這意味着您可以使用外部存儲（磁盤或 磁帶）對中間結果進行排序。
B-trees在數據庫中。
R-trees是地理搜索（例如，如果我有每10000種形狀，其具有分散在2-d平面的邊界框，其中這些形狀的相交的任意邊界框B'）
形式的在dequesC++ STL是可生成的向量（比鏈接列表更具有內存效率，並且可以恆定時間在中間「偷看」任意元素）。據我所知，我從來沒有完全使用過雙端隊列（從兩端插入/刪除），但它足夠普遍，您可以將它用作堆棧（從一端插入/刪除）或隊列（插入到另一端，從另一端刪除），並且具有高性能訪問權限以查看中間的任意元素。
我剛剛讀完Java Generics and Collections - 「泛型」部分傷害了我的頭，但集合部分很有用&他們指出跳過列表和樹之間的一些區別（都可以實現地圖/集合）：跳過列表爲您提供了從一個元素到下一個元素的內置常量時間迭代（樹是O（log n）），並且在多線程情況下實現無鎖算法要簡單得多。
優先級隊列用於調度等（此處簡要討論應用程序的webpage）;堆通常用於實現它們。我也發現堆（至少對我來說）是O（n log n）類中最容易理解和實現的。
是的，有時候。我看到的問題是，一些人雖然知道他們，但他們不知道如何真正應用他們。大多數人回到數組鏈表等等。他們會在大多數情況下完成工作，作爲更高級的數據結構（有時你真的必須「踢」到位），但效率不高。人們傾向於做他們更容易的事情，但這不一定是做事的最佳方式。我不能讓他們犯錯，我相信我也是這樣做的，但這就是爲什麼你在編程中看不到很多「高級」概念。
我用環形鏈表實現，我要永遠遍歷隊列（C語言），即網絡連接隊列。
但是我發現，當我使用高級語言時，我並不覺得自己很難用這種方式實現隊列，因爲我可以動態地增長和縮小列表而不用擔心太多。當然，這樣做的性價比很高，因爲我對內存分配何時發生的控制較少，但這是我們爲能夠擁有非常靈活的列表而付出的代價之一。
我只是找到了一個圖形使用通過詢問question＃2 :)
您往往會看到更復雜的數據結構時，它是由代碼的需要而定。通常我會在較低級別處理更復雜的代碼時看到這一點，即在覈心操作系統中，編寫一個類庫的基本部分（實現字符串，數組等），編寫出色的性能或多線程代碼等。我認爲他們扮演着重要角色的另一個地方是實現特定算法，搜索，抽樣，統計分析，優化等算法通常會考慮到特定的數據結構。
我經常使用集合，排序集合（始終保持元素排序順序，支持快速元素插入）和惰性列表。
我想你會看到使用最高級別算法的花哨的數據結構。我想到的主要例子是A *，它使用Graph和由堆實現的優先級隊列。
在財務中，您需要使用樹來計算依賴許多其他動態值的工具的值。電子表格具有類似的依賴關係樹，編譯器在轉換爲機器代碼之前創建一個抽象語法樹。
平衡樹（紅黑等）通常用於實現抽象數據類型。
只有相對少量的抽象數據類型的，諸如
同樣，一組看起來很像一張地圖，但你不需要這些值，只需要鍵。
我發現這些大多數有用的不時;優先級隊列是非常有用的數據結構，並且具有各種算法（例如調度，尋路等）的應用程序。
你說的「詞典」，你可能是指地圖或有序地圖。
一些地圖是無序的（通常實現爲散列） - 這是有序地圖的有用子集。
這是真的嗎？ ISTR斐波那契堆在理論上只是快速的，而不是在實踐中。 – 2013-01-04 21:25:17
有沒有真正的「答案」在我的問題在OP中，但我只是覺得這個帖子是特別整潔:) – Juliet 2008-12-26 22:04:33