在這一章里,我們重點討論6個有關實用性的數(shù)據(jù)結構。 首先,我們討論AVL樹的替代數(shù)據(jù)結構,包括優(yōu)化版本的伸展樹、紅黑樹、treap,以及用于在大...
投稿
在這一章里,我們重點討論6個有關實用性的數(shù)據(jù)結構。 首先,我們討論AVL樹的替代數(shù)據(jù)結構,包括優(yōu)化版本的伸展樹、紅黑樹、treap,以及用于在大...
關鍵詞 均攤界分析 在這一章,我們會分析在第4章和第6章里介紹過的若干種高級數(shù)據(jù)結構的運行時間,比如伸展樹、平衡樹、隊列、堆等。 在這一章,我們...
截止現(xiàn)在,我們一直在關心算法的有效實現(xiàn)。我們看到:當給出一個算法時,并不需要說明所需要的數(shù)據(jù)結構,由程序員來選擇合適的數(shù)據(jù)結構使得運行時間盡可能...
在這一章里,我們討論幾種解決圖論常見問題的算法。這些算法不僅在實踐中很有用,而且也很有趣,因為在實際生活的應用中,如果不花費精力來仔細地選擇數(shù)據(jù)...
在這一章,我們將描述不相交的集合類來解決等價性問題。 這種數(shù)據(jù)結構實現(xiàn)起來很簡單。每個例程僅需幾行代碼,可使用簡單的數(shù)組。該實現(xiàn)也非???,每個操...
在本章里,我們討論對數(shù)組元素的排序問題。 為了簡化問題,我們會假設數(shù)組中只包含整數(shù)。本章大部分內(nèi)容假設排序能在內(nèi)存完成,以便數(shù)組元素的個數(shù)相對較...
雖然通常都是將發(fā)送給打印機的作業(yè)放進隊列里,但這并不是最好的做法。比如 作業(yè)A可能非常重要,期望的是只要有打印機可用,就立馬運行作業(yè)A。 當打印...
在第4章,我們討論了抽象數(shù)據(jù)類型搜索樹,樹允許對集合元素的許多操作。 在本章里,我們討論抽象數(shù)據(jù)類型哈希表,哈希表支持的僅是二叉搜索樹允許的操作...
這一章會討論本書的主旨和目標,簡短回顧下編程相關概念和離散數(shù)學。 我們將會 理解一個程序在大規(guī)模輸入時的性能跟中等輸入規(guī)模是的性能是同等重要的。...
一個算法就是解決某個問題需要遵循的一套描述清晰的指令集。 一旦給出某個問題的算法且判斷該算法是正確的后,一個非常重要的步驟就是分析該算法需要多少...