http://hawstein.com/posts/make-thiner-programming-pearls.html#Heap

開篇

具體化你的解決的問題。下面是A和B的對話。

A：我該如何對磁盤文件進(jìn)行排序？ B：需要排序的內(nèi)容是什么？文件中有多少條記錄？每個記錄的格式是什么？ A：該文件包含至多10,000,000個記錄，每條記錄都是一個7位整數(shù)。 B：如果文件那么小，為什么要使用磁盤排序呢？為什么不在主存中對它排序？ A：該功能是某大型系統(tǒng)中的一部分，大概只能提供1MB主存給它。 B：你能將記錄方面的內(nèi)容說得更詳細(xì)一些嗎？ A：每個記錄是一個7位正整數(shù)，沒有其它的關(guān)聯(lián)數(shù)據(jù)，每個整數(shù)至多只能出現(xiàn)一次。 ... ...

經(jīng)過一系統(tǒng)的問題，我們可以將一個定義模糊不清的問題變得具體而清晰：

輸入： 所輸入的是一個文件，至多包含n個正整數(shù)，每個正整數(shù)都要小于n，這里n=10^7。 如果輸入時某一個整數(shù)出現(xiàn)了兩次，就會產(chǎn)生一個致命的錯誤。 這些整數(shù)與其它任何數(shù)據(jù)都不關(guān)聯(lián)。 輸出： 以增序形式輸出經(jīng)過排序的整數(shù)列表。 約束： 大概有1MB的可用主存，但可用磁盤空間充足。運行時間至多允許幾分鐘， 10秒鐘是最適宜的運行時間。

如果主存容量不是嚴(yán)苛地限制在1MB，比如說可以是1MB多，或是1~2MB之間， 那么我們就可以一次性將所有數(shù)據(jù)都加載到主存中，用Bitmap來做。 10,000,000個數(shù)就需要10,000,000位，也就是10,000,000b = 1.25MB。

程序可分為三個部分：第一，初始化所有的位為0；第二，讀取文件中每個整數(shù)， 如果該整數(shù)對應(yīng)的位已經(jīng)為1，說明前面已經(jīng)出現(xiàn)過這個整數(shù)，拋出異常，退出程序 (輸入要求每個整數(shù)都只能出現(xiàn)一次)。否則，將相應(yīng)的位置1；第三， 檢查每個位，如果某個位是1，就寫出相應(yīng)的整數(shù)，從而創(chuàng)建已排序的輸出文件。

如果主存容量嚴(yán)苛地限制在1MB，而使用Bitmap需要1.25MB， 因此無法一次載入完成排序。那么，我們可以將該文件分割成兩個文件， 再分別用Bitmap處理。分割策略可以簡單地把前一半的數(shù)據(jù)放到一個文件， 后一半的數(shù)據(jù)放到另一個文件，分別排序后再做歸并。 也可以把文件中小于某個數(shù)(比如5,000,000)的整數(shù)放到一個文件，叫l(wèi)ess.txt， 把其余的整數(shù)放到另一個文件，叫g(shù)reater.txt。分別排序后， 把greater.txt的排序結(jié)果追加到less.txt的排序結(jié)果即可。

啊哈！算法

第2章圍繞3個問題展開。

• 給定一個包含32位整數(shù)的順序文件，它至多只能包含40億個這樣的整數(shù)， 并且整數(shù)的次序是隨機的。請查找一個此文件中不存在的32位整數(shù)。 在有足夠主存的情況下，你會如何解決這個問題？ 如果你可以使用若干外部臨時文件，但可用主存卻只有上百字節(jié)， 你會如何解決這個問題？

這是CTCI中的一道題目，詳細(xì)解答請戳以下鏈接：

請猛戳我

• 請將一個具有n個元素的一維向量向左旋轉(zhuǎn)i個位置。例如，假設(shè)n=8,i=3， 那么向量abcdefgh旋轉(zhuǎn)之后得到向量defghabc。

這個問題很常見了，做3次翻轉(zhuǎn)即可，無需額外空間：

reverse(0, i-1); // cbadefgh reverse(i, n-1); // cbahgfed reverse(0, n-1); // defghabc

• 給定一本英語單詞詞典，請找出所有的變位詞集。例如，因為“pots”， “stop”，“tops”相互之間都是由另一個詞的各個字母改變序列而構(gòu)成的， 因此這些詞相互之間就是變位詞。

這個問題可以分3步來解決。第一步將每個單詞按字典序排序， 做為原單詞的簽名，這樣一來，變位詞就會具有相同的簽名。 第二步對所有的單詞按照其簽名進(jìn)行排序，這樣一來，變位詞就會聚集到一起。 第三步將變位詞分組，形成變位詞集。示意圖如下：

數(shù)據(jù)決定程序結(jié)構(gòu)

恰當(dāng)?shù)臄?shù)據(jù)視圖實際上決定了程序的結(jié)構(gòu)。 我們常常可以通過重新組織內(nèi)部數(shù)據(jù)來使程序變得小而美。

發(fā)明家悖論：更一般性的問題也許更容易解決。(有時候吧)

程序員在節(jié)省空間方面無計可施時，將自己從代碼中解脫出來， 退回起點并集中心力研究數(shù)據(jù)，常常能有奇效。數(shù)據(jù)的表示形式是程序設(shè)計的根本。

下面是退回起點進(jìn)行思考時的幾條原則：

• 使用數(shù)組重新編寫重復(fù)代碼。冗長的相似代碼常常可以使用最簡單的數(shù)據(jù)結(jié)構(gòu)—— 數(shù)組來更好地表述。

• 封裝復(fù)雜結(jié)構(gòu)。當(dāng)需要非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時，使用抽象術(shù)語進(jìn)行定義， 并將操作表示為類。

• 盡可能使用高級工具。超文本，名字-值對，電子表格，數(shù)據(jù)庫， 編程語言等都是特定問題領(lǐng)域中的強大的工具。

• 從數(shù)據(jù)得出程序的結(jié)構(gòu)。在動手編寫代碼之前，優(yōu)秀的程序員會徹底理解輸入， 輸出和中間數(shù)據(jù)結(jié)構(gòu)，并圍繞這些結(jié)構(gòu)創(chuàng)建程序。

提到的書籍：Polya的《How to Solve it》，中文書《怎樣解題》； Kernighan和Plauger的《Elements of Programming Style》；Fred Brooks的《人月神話》 Steve McConnell的《代碼大全》；《Rapid Development》； 《Software Project Survival Guide》

編寫正確的程序

本章以二分搜索為例子，講述了如何對程序進(jìn)行驗證及正確性分析。

深入閱讀：David Gries的《Science of Programming》 是程序驗證領(lǐng)域里極佳的一本入門書籍。

編程中的次要問題

到目前為止，你已經(jīng)做了一切該做的事：通過深入挖掘定義了正確的問題， 通過仔細(xì)選擇算法和數(shù)據(jù)結(jié)構(gòu)平衡了真正的需求，通過程序驗證技術(shù)寫出了優(yōu)雅的代碼， 并且對其正確性相當(dāng)有把握。萬事俱備，只欠編程。

• 使用斷言assert

• 自動化測試程序

進(jìn)階閱讀：《Practice of Programming》第5章(調(diào)試)，第6章(測試) 《Code Complete》第25章(單元測試)，第26章(調(diào)試)

程序性能分析

下圖展示了一個程序的性能提升過程， 該程序的作用是對三維空間中n個物體的運動進(jìn)行仿真。從圖中可以看出， 一個程序可以從多方面進(jìn)行性能提升，而其中算法和數(shù)據(jù)結(jié)構(gòu)的選擇又顯得尤為重要。

從設(shè)計層面提升程序性能：

問題定義。良好的問題定義可以有效減少程序運行時間和程序長度。

系統(tǒng)結(jié)構(gòu)。將大型系統(tǒng)分解成模塊，也許是決定其性能的最重要的單個因素。

算法和數(shù)據(jù)結(jié)構(gòu)。這個不用說了。

代碼調(diào)優(yōu)。針對代碼本身的改進(jìn)。

系統(tǒng)軟件。有時候改變系統(tǒng)所基于的軟件比改變系統(tǒng)本身更容易。

硬件。更快的硬件可以提高系統(tǒng)的性能。

深入閱讀：Butler Lampson的“Hints for Computer System Design”， 該論文特別適合于集成硬件和軟件的計算機系統(tǒng)設(shè)計。

粗略估算

這一章講述了估算技術(shù)，我認(rèn)為是相當(dāng)有用的一章。

文中先拋出一個問題：密西西比河一天流出多少水？如果讓你來回答， 你會怎么答，注意不能去Google哦。

作者是這么回答這個問題：假設(shè)河的出口大約有1英里寬和20英尺深(1/250英里)， 而河水的流速是每小時5英里，也就是每天120英里。則可以計算出一天的流量：

1英里 * 1/250英里 * 120英里/天 約等于 1/2 英里^3/天

上述算式非常簡單，可是在看到這些文字之前，如果有人真的問你， 密西西比河一天流出多少水？你真的能答上來嗎？還是愣了一下后，擺擺手，說： 這我哪知道！

對于上面的問題，我們至少可以注意到以下兩點：

你需要把問題轉(zhuǎn)換成一個可計算的具體模型。這一點往往不需要太擔(dān)心， 因為我們做的是估算，所以可以忽視很多無關(guān)緊要的因素，可以去簡化你的模型， 記住我們要的只是一個粗略計算的結(jié)果。比如對于上面的問題， 計算密西西比河一天流出多少水其實就是計算其一天的流量，利用中學(xué)所學(xué)知識， 流量 = 截面積 x 流速，那我們就只需計算密西西比河的出水口的截面積和流速即可。 我們可以將出水口簡化成一個矩形，因此就只需要知道出水口的寬和深即可。

你需要知道常識性的東西。上面我們已經(jīng)把問題轉(zhuǎn)換成了一個可計算的具體模型： 流量 = 出水口寬 x 出水口深 x 流速。接下來呢？你需要代入具體的數(shù)值去求得答案。 而這就需要你具備一些常識性的知識了。比如作者就估計了密西西比河的出口有1英里寬， 20英尺深(如果你估計只有幾十米寬，那就相差得太離譜了)。 這些常識性的知識比第1點更值得關(guān)注，因為你無法給出一個靠譜的估算值往往是因為這點。

當(dāng)我們懂得如何把一個問題具體化定義出來并為其選用適當(dāng)?shù)哪Ｐ?#xff0c; 并且我們也積累了必要的常識性的知識后，回答那些初看起來無從下手的問題也就不難了。 這就是估算的力量。

以下是估算時的一些有用提示：

• 兩個答案比一個答案好。即鼓勵你從多個角度去對一個問題進(jìn)行估算， 如果從不同角度得到的答案差別都不大，說明這個估算值是比較靠譜的。

• 快速檢驗。即量綱檢驗。即等式兩邊最終的量綱要一致。 這一點在等式簡單的時候相當(dāng)顯而易見。比如位移的單位是米，時間單位是秒， 速度單位是米/秒，那顯然我們應(yīng)該要用位移去除以時間來得到速度， 這樣才能保證它們單位的一致。你可能會說，我了個去，這種小學(xué)生都懂的事， 你好意思拿出來講。其實不然，當(dāng)你面對的是一個具有多個變量的復(fù)雜物理公式， 或者你提出某種物理假設(shè)，正在考慮將其公式化，該方法可以切切實實地幫你做出檢驗。

• 經(jīng)驗法則。“72法則”：1.假設(shè)以年利率r%投資一筆錢y年，如果r*y = 72， 那么你的投資差不多會翻倍。2.如果一個盤子里的菌群以每小時3%的速率增長， 那么其數(shù)量每天(24小時)都會翻倍。在誤差不超過千分之五的情況下， \pi秒就是一個納世紀(jì)。也就是說：

  3.14秒 = 10-9?* 100年 = 10-7?年

也就是說，1年大概是3.14x107?秒。所以如果有人告訴你，一個程序運行107?秒， 你應(yīng)該能很快反應(yīng)出，他說的其實是4個月。

• 實踐。與許多其他活動一樣，估算技巧只能通過實踐來提高。

如果問題的規(guī)模太大，我們還可以通過求解它的小規(guī)模同質(zhì)問題來做估算。比如， 我們想測試某個程序運行10億次需要多長時間，如果你真去跑10億次， 說不定運行幾個小時都沒結(jié)束，那不是很悲劇？我們可以運行這個程序1萬次或是10萬次， 得出結(jié)果然后倍增它即可。當(dāng)然，這個結(jié)果未必是準(zhǔn)確的， 因為你沒法保證運行時間是隨著運行次數(shù)線性增加的。謹(jǐn)慎起見，我們可以運行不同的次數(shù)， 來觀察它的變化趨勢。比如運行10次，100次，1000次，10000次等， 觀察它的運行時間是否是線性增加的，或是一條二次曲線。

有時候，我們需要為估算的結(jié)果乘上一個安全系數(shù)。比如， 我們預(yù)估完成某項功能需要時間t，那根據(jù)以往經(jīng)驗，也許我們需要為這個值乘上2或4， 這樣也許才是一個靠譜的預(yù)估值。

Little定律：系統(tǒng)中物體的平均數(shù)量等于物體離開系統(tǒng)的平均速率和每個物體在系統(tǒng)中停留 的平均時間的乘積。(如果物體離開和進(jìn)入系統(tǒng)的總體出入流是平衡的， 那么離開速率也就是進(jìn)入速率)

舉個例子，比如你正在排除等待進(jìn)入一個火爆的夜總會， 你可以通過估計人們進(jìn)入的速率來了解自己還要等待多長時間。根據(jù)Little定律， 你可以推論：這個地方可以容納約60人，每個人在里面逗留時間大約是3小時， 因此我們進(jìn)入夜總會的速率大概是每小時20人。現(xiàn)在隊伍中我們前面還有20人， 也就意味著我們還要等待大約一個小時。

深入閱讀：Darrell Huff的《How To Lie With Statistics》；關(guān)鍵詞： 費米近似(Fermi estimate, Fermi problem)

算法設(shè)計技術(shù)

這一章就一個小問題研究了4種不同的算法，重點強調(diào)這些算法的設(shè)計技術(shù)。 研究的這個小問題是一個非常常見的面試題：子數(shù)組之和的最大值。 如果之前沒有聽過，建議Google之。

深入閱讀：Aho,Hopcroft和Ullman的《Data Structures and Algorithms》 Cormen,Leiserson,Rivest和Stein的《Introduction to Algorithms》

代碼調(diào)優(yōu)

前面各章討論了提高程序效率的高層次方法：問題定義，系統(tǒng)結(jié)構(gòu)， 算法設(shè)計及數(shù)據(jù)結(jié)構(gòu)選擇。本章討論的則是低層次的方法：代碼調(diào)優(yōu)。

代碼調(diào)優(yōu)的最重要原理就是盡量少用它。不成熟的優(yōu)化是大量編程災(zāi)害的根源。 它會危及程序的正確性，功能性以及可維護(hù)性。當(dāng)效率很重要時， 第一步就是對系統(tǒng)進(jìn)行性能監(jiān)視，以確定其運行時間的分布狀況。 效率問題可以由多種方法來解決，只有在確信沒有更好的解決方案時才考慮進(jìn)行代碼調(diào)優(yōu)。

事實上，如果不是十分十分必要，不要去做代碼調(diào)優(yōu)， 因為它會犧牲掉軟件的其他許多性質(zhì)。

so，just skip this chapter。

節(jié)省空間

本章講述了節(jié)省空間的一些重要方法。

減少程序所需數(shù)據(jù)的存儲空間，一般有以下方法：

• 不存儲，重新計算。
• 稀疏數(shù)據(jù)結(jié)構(gòu)。下面著重講一下這點。
• 數(shù)據(jù)壓縮。可以通過壓縮的方式對對象進(jìn)行編碼，以減少存儲空間。
• 分配策略。只有在需要的時候才進(jìn)行分配。
• 垃圾回收。對廢棄的存儲空間進(jìn)行回收再利用。

以下是節(jié)省代碼空間的幾種通用技術(shù)：

• 函數(shù)定義。用函數(shù)替換代碼中的常見模式可以簡化程序，同時減少代碼的空間需求。
• 解釋程序。用解釋程序命令替換長的程序文本。
• 翻譯成機器語言。可以將大型系統(tǒng)中的關(guān)鍵部分用匯編語言進(jìn)行手工編碼。

稀疏數(shù)據(jù)結(jié)構(gòu)

假設(shè)我們有一個200 x 200的矩陣(共40000個元素)，里面只有2000個元素有值， 其它的都為0，示意圖如下：

顯然這是一個稀疏矩陣，直接用一個200 x 200 的二維數(shù)組來存儲這些數(shù)據(jù)會造成大量的空間浪費，共需要200x200x4B=160KB。 所以，我們應(yīng)該想辦法用另一種形式來存儲這些數(shù)據(jù)。

方法一

使用數(shù)組表示所有的列，同時使用鏈表來表示給定列中的活躍元素。 如下圖所示：

該結(jié)構(gòu)中，有200個指針(colhead)和2000條記錄(每條記錄是兩個整數(shù)和一個指針)， 占用空間是200x4B + 2000x12B = 24800B = 24.8KB， 比直接用二維數(shù)組存儲(160KB)要小很多。

方法二

我們可以開三個數(shù)組來保存這些數(shù)，如下圖所示：

firstincol是一個長度為201的數(shù)組，對于第i列，在數(shù)組row中， 下標(biāo)為firstincol[i]到firstincol[i+1]-1對應(yīng)的行元素非0， 其值存儲在相應(yīng)的pointnum數(shù)組中。

比如對于上圖，在第0列中，元素值非0的行有3行，分別是row[0],row[1],row[2], 元素值是pointnum[0],pointnum[1],pointnum[2]；在第1列中，元素值非0的行有2行， 分別是row[3],row[4]，元素值是pointnum[3],pointnum[4]。依次類推。

該結(jié)構(gòu)所需要的存儲空間為2x2000x4B + 201x4B = 16804B = 16.8KB。 由于row數(shù)組中的元素全部都小于200，所以每個元素可以用一個unsigned char來保存， firstincol數(shù)組中元素最大也就2000，所以可以用一個short(或unsigned short)來保存， pointnum中的元素是一個4B的int， 最終所需空間變?yōu)?#xff1a;2000x4B + 2000x1B + 201x2B = 10402B = 10.4KB。

深入閱讀：Fred Brooks的《人月神話》

排序

本章先簡單介紹了插入排序，然后著重講述快速排序。

插入排序

// 版本1 void InsertSort(int a[], int n) { for(int i=1; i<n; ++i) for(int j=i; j>0 && a[j-1]>a[j]; --j) swap(a[j-1], a[j]); } // 版本2 void InsertSort1(int a[], int n) { for(int i=1; i<n; ++i) { int t = a[i]; int j = i; for(; j>0 && a[j-1]>t; --j) a[j] = a[j-1]; a[j] = t; } }

快速排序

我們在這里規(guī)定：小于等于pivot的元素移到左邊，大于pivot的元素移到右邊。

實現(xiàn)1：單向移動版本

這個版本的關(guān)鍵是設(shè)置一快一慢兩個指針，慢指針左側(cè)都是小于等于pivot(包含慢指針?biāo)谖恢?， 慢指針到快指針之間的值是大于pivot，快指針右側(cè)的值是還未比較過的。示意圖如下：

小于等于pivot ｜ 大于pivot ｜ ？slow fast

快指針一次一步向前走，遇到大于pivot什么也不做繼續(xù)向前走。遇到小于等于pivot的元素， 則慢指針slow向前走一步，然后交換快慢指針指向的元素。一次劃分結(jié)束后， 再遞歸對左右兩側(cè)的元素進(jìn)行快排。代碼如下：

// 數(shù)組快排 void QSort(int a[], int head, int end) { if(a==NULL || head==end) return; int slow = head, fast = head + 1; int pivot = a[head]; while(fast != end) { if(a[fast] <= pivot) swap(a[++slow], a[fast]); ++fast; } swap(a[head], a[slow]); QSort(a, head, slow); QSort(a, slow+1, end); }

排序數(shù)組a只需要調(diào)用QSort(a, 0, n)即可。該思路同樣可以很容易地在鏈表上實現(xiàn)：

// 單鏈表快排 void qsort(Node *head, Node *end){ if(head==NULL || head==end) return; Node *slow = head, *fast = head->next; int pivot = head->data; while(fast != end){ if(fast->data <= pivot){ slow = slow->next; swap(slow->data, fast->data); } fast = fast->next; } swap(head->data, slow->data); qsort(head, slow); qsort(slow->next, end); }

排序頭指針為head的單鏈表只需調(diào)用qsort(head, NULL)即可。

實現(xiàn)2：雙向移動版本

版本1能能夠快速完成對隨機整數(shù)數(shù)組的排序，但如果數(shù)組有序， 或是數(shù)組中元素相同，快排的時間復(fù)雜度會退化成O(n2?)，性能變得非常差。

一種緩解方案是使用雙向移動版本的快排，它每次劃分也是使用兩個指針， 不過一個是從左向右移動，一個是從右向左移動，示意圖如下：

小于等于pivot ｜ ？ ｜ 大于pivoti j

指針j不斷向左移動，直到遇到小于等于pivot，就交換指針i和j所指元素 (指針i一開始指向pivot)；指針i不斷向右移動，直到遇到大于pivot的， 就交換指針i和j所指元素。pivot在這個過程中，不斷地?fù)Q來換去， 最終會停在分界線上，分界線左邊都是小于等于它的元素，右邊都是大于它的元素。 這樣就避免了最后還要交換一次pivot的操作，代碼也變得美觀許多。

int partition(int a[], int low, int high){ int pivot = a[low], i=low, j=high; while(i < j){ while(i<j && a[j]>pivot) --j; if(i < j) swap(a[i], a[j]); while(i<j && a[i]<=pivot) ++i; if(i < j) swap(a[i], a[j]); } return i; } void quicksort(int a[], int first, int last){ if(first<last){ int k = partition(a, first, last); quicksort(a, first, k-1); quicksort(a, k+1, last); } }

當(dāng)然，如果對于partition函數(shù)，你如果覺得大循環(huán)內(nèi)的兩個swap還是做了些無用功的話， 也可以把pivot的賦值放到最后一步，而不是在這個過程中swap來swap去的。代碼如下：

int partition(int a[], int low, int high){ int pivot = a[low], i=low, j=high; while(i<j){ while(i<j && a[j]>pivot) --j; if(i<j) a[i++] = a[j]; while(i<j && a[i]<=pivot) ++i; if(i<j) a[j--] = a[i]; } a[i] = pivot; return i; }

如果數(shù)組基本有序，那隨機選擇pivot(而不像上面那樣選擇第一個做為pivot) 會得到更好的性能。在partition函數(shù)里，我們只需要在數(shù)組中隨機選一個元素， 然后將它和數(shù)組中第一個元素交換，后面的劃分代碼無需改變， 就可以達(dá)到隨機選擇pivot的效果。

進(jìn)一步優(yōu)化

對于小數(shù)組，用插入排序之類的簡單方法來排序反而會更快，因此在快排中， 當(dāng)數(shù)組長度小于某個值時，我們就什么也不做。對應(yīng)到代碼中， 就是修改quicksort中的if條件：

if(first < last) 改為 if(last-first > cutoff)

其中cutoff是一個小整數(shù)。程序結(jié)束時，數(shù)組并不是有序的， 而是被組合成一塊一塊隨機排列的值，并且滿足這樣的條件： 某一塊中的元素小于它右邊任何塊中的元素。我們必須通過另一種排序算法對塊內(nèi)進(jìn)行排序。 由于數(shù)組是幾乎有序的，因此插入排序比較適用。

這種方法結(jié)合了快排和插入排序，讓它們?nèi)プ龈髯陨瞄L的事情，往往比單純用快排要快。

深入閱讀：Don Knuth的《The Art of Computer Programming, Volume 3: Sorting and Searching》；Robert Sedgewick的《Algorithms》； 《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。

取樣問題

本章講述了一個小的隨機抽樣問題，并用不同的方法來解決它。

問題：對于整數(shù)m和n，其中m<n，輸出0~n-1范圍內(nèi)m個隨機整數(shù)的有序列表， 不允許重復(fù)。

比如m=3, n=5，那么一種可能輸出是0，2，3(要求有序)。實現(xiàn)1來自Knuth的TAOCP， 時間復(fù)雜度O(n)：

void GenKnuth(int m, int n) { for(int i=0; i<n; ++i) { if((bigrand()%(n-i)) < m) { cout<<i<<endl; --m; } } }

其中，bigrand()的作用是返回一個很大的隨機整數(shù)。

實現(xiàn)2：在一個初始為空的集合里面插入隨機整數(shù)，直到個數(shù)足夠。代碼如下：

void GenSets(int m, int n) { set<int> s; while(s.size() < m) s.insert(bigrand() % n); set<int>::iterator i; for(i=s.begin(); i!=s.end(); ++i) cout<<*i<<endl; }

實現(xiàn)3：把包含整數(shù)0～n-1的數(shù)組順序打亂，然后把前m個元素排序輸出。 該方法的性能通常不如Knuth的算法。代碼如下：

void GenShuf(int m, int n) { int x[n]; for(int i=0; i<n; ++i) x[i] = i; for(int i=0; i<m; ++i) { int j = randint(i, n-1); swap(x[i], x[j]); } sort(x, x+m); for(int i=0; i<m; ++i) cout<<x[i]<<endl; }

深入閱讀：Don Knuth的《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》

搜索

本章詳細(xì)研究這樣一個搜索問題：在沒有其他相關(guān)數(shù)據(jù)的情況下，如何存儲一組整數(shù)？ 為些介紹了5種數(shù)據(jù)結(jié)構(gòu)：有序數(shù)組，有序鏈表，二叉搜索樹，箱，位向量。

其中，二叉搜索樹應(yīng)該熟練掌握，以下是一種實現(xiàn)：

struct Node {int data; Node *lchild, *rchild, *parent; Node(): lchild(NULL), rchild(NULL), parent(NULL) { } }; class BST { private: static const int kMax = 1000; Node *root_, *parent_, nodes_[kMax]; int size_; private: Node* minimum(Node* node); Node* maximum(Node* node); Node* successor(Node* node); Node* predecessor(Node* node); void Insert(Node* &node, int x); void InorderTraver(Node* node); Node* Find(Node* node, int x); public: BST(): root_(NULL), parent_(NULL), size_(0) { memset(nodes_, '\0', sizeof(nodes_)); } void Insert(int x); void InorderTraver(); Node* Find(int x); void Remove(Node* z); }; Node* BST::minimum(Node* node) { if(node == NULL) return NULL; while(node->lchild) node = node->lchild; return node; } Node* BST::maximum(Node* node) { if(node == NULL) return NULL; while(node->rchild) node = node->rchild; return node

轉(zhuǎn)載于:https://www.cnblogs.com/heidsoft/p/4003220.html

總結(jié)

以上是生活随笔為你收集整理的转自把《编程珠玑》读薄的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。