爲什麼要搜索鏈表？

Question

我讀「的算法設計手冊」，它說的是一個基本列出三種操作搜索，插入和刪除。然後它繼續描述一個C中的算法，一旦它找到了它正在尋找的節點（通過比較搜索到的節點的數據），它就返回該節點（從而返回它下面的任何節點）。如果找不到要查找的內容，則返回NULL。

所以我的問題是如果我們知道我們在尋找什麼，爲什麼我們要搜索它？如果只是爲了查看它是否包含在列表中，那麼爲什麼不是布爾函數「包含」我們真正想要的？

Answer 1

節點可能包含的信息不僅僅是您要搜索的值。設想一個模擬文件系統的列表。您可以按名稱搜索文件，但返回的節點可能包含文件名，文件大小，上次修改時間，文件所有者，訪問權限和其他數據。

Answer 2

有時，您需要某個特定節點進行某些操作。請記住，節點本身及其內容是兩個不同的邏輯實體。

Answer 3

布爾函數「contains」可能就是我們想要的。如果我們想要搜索一些我們沒有的數據集，但是我們確實有一個識別碼呢？

嘗試查看教科書中的示例作爲一般示例。搜索布爾值並基於其他值搜索記錄都執行相同的操作，只是輸出不同。

Answer 4

通常，搜索一個節點來處理它。也許你想爲現有節點設置一個新值，刪除節點後面的所有內容，或者在該節點後面插入一些內容。如果您在列表中保留特定順序，則可能會擴展搜索功能的語義以查找大於特定值的第一項等等。

Answer 5

舉一個簡單的例子...

你寫，要求他們年齡的人（年），並將它們存儲在列表中，然後程序會顯示直方圖（有多少人有過每一個時代）或者它可以顯示過去一年有多少人已經21歲了。

在這樣的程序中，您可能不會事先知道最終會出現在列表中的什麼。這就是爲什麼你要搜索它。

Answer 6

鏈接列表結構中唯一的條目是head節點。要訪問列表中的特定節點，您必須通過head節點遍歷到下一個節點，到下一個節點，...並最終到達目標節點，從而進行搜索。因此，contains將完全相同 - 搜索節點，其中equals到您正在尋找的節點。