2012-08-24 64 views
1

我閱讀有關隊列在算法羅伯特sedwick書避免重複條目使用索引項

當在數據結構中的項目本身就是數組的索引,所以 我們將這樣的項目作爲「索引項」 。通常,我們有一組M對象,保存在另一個數組中,我們需要通過一個 廣義隊列結構作爲更復雜算法的一部分。 對象通過索引放入隊列中,並在刪除 時進行處理,並且每個對象都要精確處理一次。通常 隊列中沒有重複的數組索引直接支持此目標 。

我的問題在最後一句「對象通過索引放在隊列中,當它們被刪除時處理,並且每個對象都被精確處理一次」?我們只使用一個數組而不是兩個數組?

作者的意思是「通常數組中的索引在隊列中沒有重複,直接支持這個目標。」 ?

感謝您的時間和幫助

回答

6

那麼,筆者要解決處理數據的算法任務中所儲存數組:

 +-----+-----+---------+-----+ 
Data = | Foo | Bar | Grandma | Zip | 
     +-----+-----+---------+-----+ 

我們需要處理的某種此數據這是由我們的算法決定的,並且有某種「待辦事項」我們接下來要處理的項目隊列。複製實際的數據對象可能是不可取或不可能的(對象可能很大或不可複製)。的指標隊列的伎倆:

   --+---+---+--\ 
ToDo = [2] --> | 0 | 3 | -----> (1) 
      --+---+---+--/ 

隊列告訴我們,Data[1]是要處理的下一個項目。 Data[3]Data[0]正在等待,我們只是決定Data[2]作爲最近的任務。

(例如,隊列用於樹狀結構的廣度優先搜索:您在下一個隊列中彈出您想要訪問的節點,並將該節點的子節點推入以作後續工作每個節點應該只訪問一次,上面的索引隊列可以讓您將實際的樹元素存儲在Data數組中,並且僅通過輕量級索引來引用它們。)