何謂數(shù)據(jù)結構數(shù)據(jù)結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數(shù)據(jù)的內(nèi)部構成，即一個數(shù)據(jù)由那些成分數(shù)據(jù)構成，以什么方式構成，呈什么結構。數(shù)據(jù)結構有邏輯上的數(shù)據(jù)結構和物理上的數(shù)據(jù)結構之分。邏輯上的數(shù)據(jù)結構反映成分數(shù)據(jù)之間的邏輯關系，而物理上的數(shù)據(jù)結構反映成分數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結構是數(shù)據(jù)存在的形式。數(shù)據(jù)結構是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應，通過這組算法集合可以對數(shù)據(jù)結構中的數(shù)據(jù)進行某種操作。數(shù)據(jù)結構主要研究什么？數(shù)據(jù)結構作為一門學科主要研究數(shù)據(jù)的各種邏輯結構和存儲結構，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結構；數(shù)據(jù)的物理存儲結構；對數(shù)據(jù)的操作（或算法）。通常，算法的設計取決于數(shù)據(jù)的邏輯結構，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結構。什么是數(shù)據(jù)結構？什么是邏輯結構和物理結構？數(shù)據(jù)是指由有限的符號（比如，"0"和"1"，具有其自己的結構、操作、和相應的語義）組成的元素的集合。結構是元素之間的關系的集合。通常來說，一個數(shù)據(jù)結構DS可以表示為一個二元組：DS=(D,S),//i.e.,data-structure=(data-part,logic-structure-part)這里D是數(shù)據(jù)元素的集合（或者是“結點”，可能還含有“數(shù)據(jù)項”或“數(shù)據(jù)域”），S是定義在D（或其他集合）上的關系的集合，S={R|R:D×D×...}，稱之為元素的邏輯結構。邏輯結構有四種基本類型：集合結構、線性結構、樹狀結構和網(wǎng)絡結構。表和樹是最常用的兩種高效數(shù)據(jù)結構，許多高效的算法可以用這兩種數(shù)據(jù)結構來設計實現(xiàn)。表是線性結構的（全序關系），樹(偏序或?qū)哟侮P系)和圖（局部有序(weak/localorders)）是非線性結構。數(shù)據(jù)結構的物理結構是指邏輯結構的存儲鏡像(image)。數(shù)據(jù)結構DS的物理結構P對應于從DS的數(shù)據(jù)元素到存儲區(qū)M（維護著邏輯結構S）的一個映射：P:(D,S)-->M存儲器模型：一個存儲器M是一系列固定大小的存儲單元，每個單元U有一個唯一的地址A(U)，該地址被連續(xù)地編碼。每個單元U有一個唯一的后繼單元U'=succ(U)。P的四種基本映射模型：順序（sequential）、鏈接（linked）、索引（indexed）和散列（hashing）映射。因此，我們至少可以得到4×4種可能的物理數(shù)據(jù)結構：

sequential(sets)

linkedlists

indexedtrees

hashgraphs

（并不是所有的可能組合都合理）數(shù)據(jù)結構DS上的操作：所有的定義在DS上的操作在改變數(shù)據(jù)元素（節(jié)點）或節(jié)點的域時必須保持DS的邏輯和物理結構。DS上的基本操作：任何其他對DS的高級操作都可以用這些基本操作來實現(xiàn)。最好將DS和他的所有基本操作看作一個整體——稱之為模塊。我們可以進一步將該模塊抽象為數(shù)據(jù)類型（其中DS的存儲結構被表示為私有成員，基本操作被表示為公共方法），稱之為ADT。作為ADT，堆棧和隊列都是一種特殊的表，他們擁有表的操作的子集。對于DATs的高級操作可以被設計為（不封裝的）算法，利用基本操作對DS進行處理。好的和壞的DS：如果一個DS可以通過某種“線性規(guī)則”被轉(zhuǎn)化為線性的DS（例如線性表），則稱它為好的DS。好的DS通常對應于好的（高效的）算法。這是由計算機的計算能力決定的，因為計算機本質(zhì)上只能存取邏輯連續(xù)的內(nèi)存單元，因此如何沒有線性化的結構邏輯上是不可計算的。比如對一個圖進行操作，要訪問圖的所有結點，則必須按照某種順序來依次訪問所有節(jié)點（要形成一個偏序），必須通過某種方式將圖固有的非線性結構轉(zhuǎn)化為線性結構才能對圖進行操作。樹是好的DS——它有非常簡單而高效的線性化規(guī)則，因此可以利用樹設計出許多非常高效的算法。樹的實現(xiàn)和使用都很簡單，但可以解決大量特殊的復雜問題，因此樹是實際編程中最重要和最有用的一種數(shù)據(jù)結構。樹的結構本質(zhì)上有遞歸的性質(zhì)——每一個葉節(jié)點可以被一棵子樹所替代，反之亦然。實際上，每一種遞歸的結構都可以被轉(zhuǎn)化為（或等價于）樹形結構。計算機中數(shù)據(jù)的描述方式我們知道，數(shù)據(jù)可以用不同的形式進行描述或存儲在計算機存儲器中。最常見的數(shù)據(jù)描述方法有：公式化描述、鏈接描述、間接尋址和模擬指針。公式化描述借助數(shù)學公式來確定元素表中的每個元素分別存儲在何處，也就通過公式計算元素的存儲器地址。最簡單的情形就是把所有元素依次連續(xù)存儲在一片連續(xù)的存儲空間中，這就是通常所說的連續(xù)線性表，即數(shù)組。復雜一點的情形是利用復雜的函數(shù)關系根據(jù)元素的某些特征來計算元素在內(nèi)存中的位置，這種技術稱為散列技術(Hash，經(jīng)常音譯為哈希技術)。在鏈接描述中，元素表中的每個元素可以存儲在存儲器的不同區(qū)域中，每個元素都包含一個指向下一個元素的指針。這就是通常所說的鏈表。這種描述方法的好處是，知道了第一個元素的位置，就可以依次找到第n個元素的位置，而且在其中插入元素非常方便，缺點是查找某個元素要遍歷所有在該元素之前的元素，實際應用中經(jīng)常和公式化描述結合起來使用。在間接尋址方式中，元素表中的每個元素也可以存儲在存儲器的不同區(qū)域中，不同的是，此時必須保存一張表，該表的第i項指向元素表中的第i個元素，所以這張表是一個用來存儲元素地址的表。指針數(shù)組（元素為指針的數(shù)組）就是這種描述法的應用。這種描述方法是公式化描述和鏈接描述的一種折衷方案，同時具有兩種描述方法的優(yōu)點，但是需要額外的內(nèi)存開銷。模擬指針非常類似于鏈接描述，區(qū)別在于它用整數(shù)代替了指針，整數(shù)所扮演的角色與指針所扮演的角色完全相同。模擬指針的描述方式是鏈接描述和公式化描述的結合，元素被存儲在不同的區(qū)域中，每個元素包含一個指示下一個元素位置的整數(shù)，可以通過某種公式由該整數(shù)計算出下一個元素的存儲器地址。線性表的游標實現(xiàn)就是模擬指針描述法。

算法Algorithm算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。一個算法應該具有以下五個重要的特征：有窮性：一個算法必須保證執(zhí)行有限步之后結束；確切性：算法的每一步驟必須有確切的定義；輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的；可行性：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。

DidyouknowAlgorithm一詞的由來Algorithm(算法)一詞本身就十分有趣。初看起來，這個詞好像是某人打算要寫“Logarithm”(對數(shù))一詞但卻把頭四個字母寫的前后顛倒了。這個詞一直到1957年之前在Webster'sNewWorldDictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術)，指的是用阿拉伯數(shù)字進行算術運算的過程。在中世紀時，珠算家用算盤進行計算，而算術家用算術進行計算。中世紀之后，對這個詞的起源已經(jīng)拿不準了，早期的語言學家試圖推斷它的來歷，認為它是從把algiros(費力的)+arithmos(數(shù)字)組合起來派生而成的，但另一些人則不同意這種說法，認為這個詞是從“喀斯迪爾國王Algor”派生而來的。最后，數(shù)學史學家發(fā)現(xiàn)了algorism(算術)一詞的真實起源：它來源于著名的PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibnM?saal-Khowarizm（約公元前825年）——從字面上看，這個名字的意思是“Ja'far的父親，Mohammed和M?sa的兒子，Khowarizm的本地人”。Khowarizm是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm寫了著名的書Kitabaljabrw'al-muqabala(《復原和化簡的規(guī)則》)；另一個詞，“algebra”(代數(shù))，是從他的書的標題引出來的，盡管這本書實際上根本不是講代數(shù)的。逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個詞是由于同arithmetic(算術)相混淆而形成的錯拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學詞典VollstandigesMathematischesLexicon(《數(shù)學大全辭典》)，給出了Algorithmus(算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmusinfinitesimalis(無限小方法)，在當時就用來表示Leibnitz(萊布尼茲)所發(fā)明的以無限小量進行計算的微積分方法。1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法(Euclid'salgorithm)聯(lián)系在一起。這個算法就是在歐幾里德的《幾何原本》(Euclid'sElements,第VII卷，命題i和ii)中所闡述的求兩個數(shù)的最大公約數(shù)的過程(即輾轉(zhuǎn)相除法)。

偽代碼的使用UsageofPseudocode偽代碼(Pseudocode)是一種算法描述語言。使用為代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言(Pascal,C,Java,etc)實現(xiàn)。因此，偽代碼必須結構清晰，代碼簡單，可讀性好，并且類似自然語言。下面介紹一種類Pascal語言的偽代碼的語法規(guī)則。偽代碼的語法規(guī)則在偽代碼中，每一條指令占一行(repeatSuntilC"，需要的時間等于計算條件表達式C需要的時間與執(zhí)行循環(huán)S體需要的時間之和乘以循環(huán)的次數(shù)。與規(guī)則5不同，這里的循環(huán)次數(shù)是隱含的。例如，b_search函數(shù)中的while循環(huán)語句。按規(guī)則(1)-(4)，計算條件表達式"(notfound)and(U≥=L)"與執(zhí)行循環(huán)體I:=(U+L)div2;ifc=A[I]thenfound:=true

else

if

c>A[I]thenL:=I+1

elseU:=I-1;只需要θ(1)時間，而循環(huán)次數(shù)為logm，所以，執(zhí)行此while語句只需要θ(logm)時間。在許多情況下，運用規(guī)則(5)和(6)常常須要借助具體算法的內(nèi)涵來確定循環(huán)的次數(shù)，才不致使時間的估計過于保守。這里舉一個例子?？疾斐绦蚨危篠ize:=m;1i:=1;1whilei<ndo

begin

i:=i+1;

S1;θ(n)

if

Size>0

then1

begin

在1到Size的范圍內(nèi)任選一個數(shù)賦值給t;θ(1)

Size:=Size-t;2

forj:=l

to

t

do

S2θ(n)

end;

end;

程序在各行右端頂格處標注著執(zhí)行相應各行所需要的時間。如果不對算法的內(nèi)涵作較深入的考察，只看到1≤t≤Size≤m，就草率地估計while的內(nèi)循環(huán)for的循環(huán)次數(shù)為Ο(m)，那么，程序在最壞情況下的時間復雜性將被估計為Ο(n2+m·n2)。反之，如果對算法的內(nèi)涵認真地分析，結果將兩樣。事實上，在while的循環(huán)體內(nèi)t是動態(tài)的,size也是動態(tài)的，它們都取決while的循環(huán)參數(shù)i，即t=t(i)記為ti；size=size(i)記為sizei，i=l,2,…,n-1。對于各個i，1≤i≤n-1，ti與m的關系是隱含的，這給準確地計算for循環(huán)的循環(huán)體S2被執(zhí)行的次數(shù)帶來困難。上面的估計比較保守的原因在于我們把S2的執(zhí)行次數(shù)的統(tǒng)計過于局部化。如果不局限于for循環(huán)，而是在整個程序段上統(tǒng)計S2被執(zhí)行的總次數(shù)，那么，這個總次數(shù)等于，又根據(jù)算法中ti的取法及sizei+1=sizei-ti，i=1,2,…,n-1有sizen=size1-。最后利用size1=m和sizen=0得到=m。于是在整個程序段上，S2被執(zhí)行的總次數(shù)為m，所需要的時間為θ(mn)。執(zhí)行其他語句所需要的時間直接運用規(guī)則(l)-(6)容易計算。累加起來，整個程序段在最壞情況下時間復雜性漸近階為θ(n2+mn)。這個結果顯然比前面粗糙的估計準確。規(guī)則(7)對于goto語句。在Pascal中為了便于表達從循環(huán)體的中途跳轉(zhuǎn)到循環(huán)體的結束或跳轉(zhuǎn)到循環(huán)語句的后面語句，引入goto語句。如果我們的程序按照這一初衷使用goto語句，那么，在時間復雜性分析時可以假設它不需要任何額外的時間。因為這樣做既不會低估也不會高估程序在最壞情況下的運行時間的階。如果有的程序濫用了goto語句，即控制轉(zhuǎn)移到前面的語句，那么情況將變得復雜起來。當這種轉(zhuǎn)移造成某種循環(huán)時，只要與別的循環(huán)不交叉，保持循環(huán)的內(nèi)外嵌套，則可以比照規(guī)則(1)-(6)進行分析。當由于使用goto語句而使程序結構混亂時，建議改寫程序然后再做分析。規(guī)則(8)對于過程調(diào)用和函數(shù)調(diào)用語句，它們需要的時間包括兩部分，一部分用于實現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行過程(或函數(shù))本身，這時可以根據(jù)過程(或函數(shù))調(diào)用的層次，由里向外運用規(guī)則(l)-(7)進行分析，一層一層地剝，直到計算出最外層的運行時間便是所求。如果過程(或函數(shù))出現(xiàn)直接或間接的遞歸調(diào)用，則上述由里向外逐層剝的分析行不通。這時我們可以對其中的各個遞歸過程(或函數(shù))，所需要的時間假設為一個相應規(guī)模的待定函數(shù)。然后一一根據(jù)過程(或函數(shù))的內(nèi)涵建立起這些待定函數(shù)之間的遞歸關系得到遞歸方程。最后用求遞歸方程解的漸進階的方法確定最壞情況下的復雜性的漸進階。遞歸方程的種類很多，求它們的解的漸近階的方法也很多，我們將在下一段比較系統(tǒng)地給予介紹。本段只舉一個簡單遞歸過程(或函數(shù))的例子來說明如何建立相應的遞歸方程，同時不加推導地給出它們在最壞情況下的時間復雜性的漸近階。例：再次考察函數(shù)b_search，這里將它改寫成一個遞歸函數(shù)。為了簡明，我們已經(jīng)運用前面的規(guī)則(l)-(6)，統(tǒng)計出執(zhí)行各行語句所需要的時間，并標注在相應行的右端：Functionb_search(C,L,U:integer):integer;單位時間數(shù)varindex,element:integer;

begin

if(U<L)then

1

b_search:=0;

1

else

begin

index:=(L+U)div2;

3

element:=A[index];

2

ifelement=Cthen

1

b_search:=index

1

elseifelement>Cthen

b_search:=b_search(C,L,index-1)

3+T(m/2)

else

b_search:=b_search(C,index+1,U);

3+T(m/2)

end;

end;

其中T(m)是當問題的規(guī)模U-L+1=m時b_search在最壞情況下(這時，數(shù)組A[L..U]中沒有給定的C)的時間復雜性。根據(jù)規(guī)則(l)-(8)，我們有：或化簡為這是一個關于T(m)的遞歸方程。用下一段將介紹的迭代法，容易解得：T(m)=11logm+l3=θ(logm)在結束這一段之前，我們要提一下關于算法在最壞情況下的空間復雜性分析。我們照樣可以給出與分析時間復雜性類似的規(guī)則。這里不贅述。然而應該指出，在出現(xiàn)過程(或函數(shù))遞歸調(diào)用時要考慮到其中隱含的存儲空間的額外開銷。因為現(xiàn)有的實現(xiàn)過程(或函數(shù))遞歸調(diào)用的編程技術需要一個隱含的、額外(即不出現(xiàn)在程序的說明中)的棧來支持。過程(或函數(shù))的遞歸調(diào)用每深人一層就把本層的現(xiàn)場局部信息及調(diào)用的返回地址存放在棧頂備用，直到調(diào)用的最里層。因此遞歸調(diào)用一個過程(或函數(shù))所需要的額外存儲空間的大小即棧的規(guī)模與遞歸調(diào)用的深度成正比，其比例因子等于每深入一層需要保存的數(shù)據(jù)量。比如本段前面所舉的遞歸函數(shù)b_search，在最壞情況下，遞歸調(diào)用的深度為logm，因而在最壞情況下調(diào)用它所需要的額外存儲空間為θ(logm)。遞歸方程解的漸近階的求法上一章所介紹的遞歸算法在最壞情況下的時間復雜性漸近階的分析，都轉(zhuǎn)化為求相應的一個遞歸方程的解的漸近階。因此，求遞歸方程的解的漸近階是對遞歸算法進行分析的關鍵步驟。遞歸方程的形式多種多樣，求其解的漸近階的方法也多種多樣。這里只介紹比較實用的五種方法。代入法這個方法的基本步驟是先推測遞歸方程的顯式解，然后用數(shù)學歸納法證明這一推測的正確性。那么，顯式解的漸近階即為所求。迭代法

這個方法的基本步驟是通過反復迭代，將遞歸方程的右端變換成一個級數(shù)，然后求級數(shù)的和，再估計和的漸近階；或者，不求級數(shù)的和而直接估計級數(shù)的漸近階，從而達到對遞歸方程解的漸近階的估計。套用公式法這個方法針對形如：T(n)=aT(n/b)+f(n)的遞歸方程，給出三種情況下方程解的漸近階的三個相應估計公式供套用。差分方程法

有些遞歸方程可以看成一個差分方程，因而可以用解差分方程(初值問題)的方法來解遞歸方程。然后對得到的解作漸近階的估計。母函數(shù)法這是一個有廣泛適用性的方法。它不僅可以用來求解線性常系數(shù)高階齊次和非齊次的遞歸方程，而且可以用來求解線性變系數(shù)高階齊次和非齊次的遞歸方程，甚至可以用來求解非線性遞歸方程。方法的基本思想是設定遞歸方程解的母函數(shù)，努力建立一個關于母函數(shù)的可解方程，將其解出，然后返回遞歸方程的解。本章將逐一地介紹上述五種井法，并分別舉例加以說明。本來，遞歸方程都帶有初始條件，為了簡明起見，我們在下面的討論中略去這些初始條件。遞歸方程組解的漸進階的求法——代入法用這個辦法既可估計上界也可估計下界。如前面所指出，方法的關鍵步驟在于預先對解答作出推測，然后用數(shù)學歸納法證明推測的正確性。例如，我們要估計T(n)的上界，T(n)滿足遞歸方程：其中是地板(floors)函數(shù)的記號，表示不大于n的最大整數(shù)。我們推測T(n)=O(nlogn)，即推測存在正的常數(shù)C和自然數(shù)n0，使得當n≥n0時有：T(n)≤Cnlogn(6.2)事實上，取n0=22=4，并取那么，當n0≤n≤2n0時，(6.2)成立。今歸納假設當2k-1n0≤n≤2kn0，k≥1時，(1.1.16)成立。那么，當2kn0≤n≤2k+1n0時，我們有：即(6.2)仍然成立，于是對所有n≥n0，(6.2)成立?？梢娢覀兊耐茰y是正確的。因而得出結論：遞歸方程(6.1)的解的漸近階為O(nlogn)。這個方法的局限性在于它只適合容易推測出答案的遞歸方程或善于進行推測的高手。推測遞歸方程的正確解，沒有一般的方法，得靠經(jīng)驗的積累和洞察力。我們在這里提三點建議：(1)如果一個遞歸方程類似于你從前見過的已知其解的方程，那么推測它有類似的解是合理的。作為例子，考慮遞歸方程：右邊項的變元中加了一個數(shù)17，使得方程看起來難于推測。但是它在形式上與(6.1)很類似。實際上，當n充分大時與相差無幾。因此可以推測(6.3)與(6.1)有類似的上界T(n)=O(nlogn)。進一步，數(shù)學歸納將證明此推測是正確的。(2)從較寬松的界開始推測，逐步逼近精確界。比如對于遞歸方程(6.1)，要估計其解的漸近下界。由于明顯地有T(n)≥n，我們可以從推測T(n)=Ω(n)開始，發(fā)現(xiàn)太松后，把推測的階往上提，就可以得到T(n)=Ω(nlogn)的精確估計。(3)作變元的替換有時會使一個末知其解的遞歸方程變成類似于你曾見過的已知其解的方程，從而使得只要將變換后的方程的正確解的變元作逆變換，便可得到所需要的解。例如考慮遞歸方程：看起來很復雜，因為右端變元中帶根號。但是，如果作變元替換m=logn，即令n=2m，將其代入(6.4)，則(6.4)變成：把m限制在正偶數(shù)集上，則(6.5)又可改寫為：T(2m)=2T(2m/2)+m若令S(m)=T(2m)，則S(m)滿足的遞歸方程：S(m)=2S(m/2)+m，與(6.1)類似，因而有：S(m)=O(m1ogm)，進而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn)(6.6)上面的論證只能表明：當(充分大的)n是2的正偶次冪或換句話說是4的正整數(shù)次冪時(6.6)才成立。進一步的分析表明(6.6)對所有充分大的正整數(shù)n都成立，從而，遞歸方程(6.4)解的漸近階得到估計。在使用代入法時，有三點要提醒：(1)記號O不能濫用。比如，在估計(6.1)解的上界時，有人可能會推測T(n)=O(n)，即對于充分大的n，有T(n)≤Cn，其中C是確定的正的常數(shù)。他進一步運用數(shù)學歸納法，推出：從而認為推測T(n)=O(n)是正確的。實際上，這個推測是錯誤的，原因是他濫用了記號O，錯誤地把(C+l)n與Cn等同起來。(2)當對遞歸方程解的漸近階的推測無可非議，但用數(shù)學歸納法去論證又通不過時，不妨在原有推測的基礎上減去一個低階項再試試。作為一個例子，考慮遞歸方程其中是天花板(floors)函數(shù)的記號。我們推測解的漸近上界為O(n)。我們要設法證明對于適當選擇的正常數(shù)C和自然數(shù)n0，當n≥n0時有T(n)≤Cn。把我們的推測代入遞歸方程，得到：我們不能由此推斷T(n)≤Cn，歸納法碰到障礙。原因在于(6.8)的右端比Cn多出一個低階常量。為了抵消這一低階量，我們可在原推測中減去一個待定的低階量b，即修改原來的推測為T(n)≤Cn-b?，F(xiàn)在將它代人(6.7)，得到：只要b≥1，新的推測在歸納法中將得到通過。(3)因為我們要估計的是遞歸方程解的漸近階，所以不必要求所作的推測對遞歸方程的初始條件（如T(0)、T(1)）成立，而只要對T(n)成立，其中n充分大。比如，我們推測(6.1)的解T(n)≤Cnlogn，而且已被證明是正確的，但是當n=l時，這個推測卻不成立，因為(Cnlogn)|n=1=0而T(l)>0。遞歸方程組解的漸進階的求法——迭代法用這個方法估計遞歸方程解的漸近階不要求推測解的漸近表達式，但要求較多的代數(shù)運算。方法的思想是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來達到對方程左端即方程的解的估計。作為一個例子，考慮遞歸方程：接連迭代二次可將右端項展開為：由于對地板函數(shù)有恒等式：(6.10)式可化簡為：這仍然是一個遞歸方程，右端項還應該繼續(xù)展開。容易看出，迭代i次后，將有（6.11）而且當時，(6.11)不再是遞歸方程。這時：(6.13)又因為[a]≤a，由(6.13)可得：而由(6.12)，知i≤log4n，從而，代人(6.14)得：即方程(6.9)的解

T(n)=O(n)。從這個例子可見迭代法導致繁雜的代數(shù)運算。但認真觀察一下，要點在于確定達到初始條件的迭代次數(shù)和抓住每次迭代產(chǎn)生出來的"自由項"(與T無關的項)遵循的規(guī)律。順便指出，迭代法的前幾步迭代的結果常常能啟發(fā)我們給出遞歸方程解的漸近階的正確推測。這時若換用代入法，將可免去上述繁雜的代數(shù)運算。圖6-1與方程(6.15)相應的遞歸樹為了使迭代法的步驟直觀簡明、圖表化，我們引入遞歸樹?？恐f歸樹，人們可以很快地得到遞歸方程解的漸近階。它對描述分治算法的遞歸方程特別有效。我們以遞歸方程T(n)=2T(n/2)+n2(6.15)為例加以說明。圖6-1展示出(6.15)在迭代過程中遞歸樹的演變。為了方便，我們假設n恰好是2的冪。在這里，遞歸樹是一棵二叉樹，因為(6.15)右端的遞歸項2T(n/2)可看成T(n/2)+T(n/2)。圖6-1(a)表示T(n)集中在遞歸樹的根處，(b)表示T(n)已按(6.15)展開。也就是將組成它的自由項n2留在原處，而將2個遞歸項T(n/2)分別攤給它的2個兒子結點。(c)表示迭代被執(zhí)行一次。圖6-1(d)展示出迭代的最終結果。圖6-1中的每一棵遞歸樹的所有結點的值之和都等于T(n)。特別，已不含遞歸項的遞歸樹(d)中所有結點的值之和亦然。我們的目的是估計這個和T(n)。我們看到有一個表格化的辦法：先按橫向求出每層結點的值之和，并記錄在各相應層右端頂格處，然后從根到葉逐層地將頂格處的結果加起來便是我們要求的結果。照此，我們得到(6.15)解的漸近階為θ(n2)。再舉一個例子。遞歸方程：T(n)=T(n/3)+T(2n/3)+n(6.16)的迭代過程相應的遞歸樹如圖6-2所示。其中，為了簡明，再一次略去地板函數(shù)和天花板函數(shù)。圖6-2迭代法解(6.16)的遞歸樹當我們累計遞歸樹各層的值時，得到每一層的和都等于n，從根到葉的最長路徑是設最長路徑的長度為k，則應該有，得，于是即T(n)=O(nlogn)。以上兩個例子表明，借助于遞歸樹，迭代法變得十分簡單易行。遞歸方程組解的漸進階的求法——套用公式法這個方法為估計形如：T(n)=aT(n/b)+f(n)(6.17)的遞歸方程解的漸近階提供三個可套用的公式。(6.17)中的a≥1和b≥1是常數(shù)，f(n)是一個確定的正函數(shù)。(6.17)是一類分治法的時間復雜性所滿足的遞歸關系，即一個規(guī)模為n的問題被分成規(guī)模均為n/b的a個子間題，遞歸地求解這a個子問題，然后通過對這a個子間題的解的綜合，得到原問題的解。如果用T(n)表示規(guī)模為n的原問題的復雜性，用f(n)表示把原問題分成a個子問題和將a個子問題的解綜合為原問題的解所需要的時間，我們便有方程(6.17)。這個方法依據(jù)的是如下的定理：設a≥1和b≥1是常數(shù)f(n)是定義在非負整數(shù)上的一個確定的非負函數(shù)。又設T(n)也是定義在非負整數(shù)上的一個非負函數(shù)，且滿足遞歸方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三類情況下，我們有T(n)的漸近估計式：若對于某常數(shù)ε>0，有

，

則

；若

，

則

；若對其常數(shù)ε>0，有

且對于某常數(shù)c>1和所有充分大的正整數(shù)n有af(n/b)≤cf(n)，則T(n)=θ(f(n))。這里省略定理的證明。在應用這個定理到一些實例之前，讓我們先指出定理的直觀含義，以幫助讀者理解這個定理。讀者可能已經(jīng)注意到，這里涉及的三類情況，都是拿f(n)與作比較。定理直觀地告訴我們，遞歸方程解的漸近階由這兩個函數(shù)中的較大者決定。在第一類情況下，函數(shù)較大，則T(n)=θ()；在第三類情況下，函數(shù)f(n)較大，則T(n)=θ(f(n))；在第二類情況下，兩個函數(shù)一樣大，則T(n)=θ()，即以n的對數(shù)作為因子乘上f(n)與T(n)的同階。此外，定理中的一些細節(jié)不能忽視。在第一類情況下f(n)不僅必須比小，而且必須是多項式地比小，即f(n)必須漸近地小于與的積，ε是一個正的常數(shù)；在第三類情況下f(n)不僅必須比大，而且必須是多項式地比大，還要滿足附加的“正規(guī)性”條件：af(n/b)≤cf(n)。這個附加的“正規(guī)性”條件的直觀含義是a個子間題的再分解和再綜合所需要的時間最多與原問題的分解和綜合所需要的時間同階。我們在一般情況下將碰到的以多項式為界的函數(shù)基本上都滿足這個正規(guī)性條件。還有一點很重要，即要認識到上述三類情況并沒有覆蓋所有可能的f(n)。在第一類情況和第二類情況之間有一個間隙：f(n)小于但不是多項式地小于；類似地，在第二類情況和第三類情況之間也有一個間隙：f(n)大于但不是多項式地大于。如果函數(shù)f(n)落在這兩個間隙之一中，或者雖有，但正規(guī)性條件不滿足，那么，本定理無能為力。下面是幾個應用例子。例1考慮T(n)=9T(n/3)+n0對照(6.17)，我們有a=9，b=3，f(n)=n，，取，便有，可套用第一類情況的公式，得T(n)=θ(n2)。例2考慮T(n)=T(2n/3)+1對照(6.17)，我們有a=1，b=3/2，f(n)=1，，可套用第二類情況的公式，得T(n)=θ(logn)。例3考慮T(n)=3T(n/4)+nlogn對照(6.17)，我們有a=3，b=4，f(n)=nlogn，，只要取，便有。進一步，檢查正規(guī)性條件：只要取c=3/4，便有af(n/b)≤cf(n)，即正規(guī)性條件也滿足?？商子玫谌惽闆r的公式，得T(n)=θ(f(n))=θ(nlogn)。最后舉一個本方法對之無能為力的例子?？紤]T(n)=2T(n/2)+nlogn對照(6.17)，我們有a=2，b=2，f(n)=nlogn，，雖然f(n)漸近地大于，但f(n)并不是多項式地大于，因為對于任意的正常數(shù)ε，，即f(n)在第二類情況與第三類情況的間隙里，本方法對它無能為力。

遞歸方程組解的漸進階的求法——差分方程法這里只考慮形如：T(n)=c1T(n-1)+c2T(n-2)+…+ckT(n-k)+f(n)，n≥k(6.18)的遞歸方程。其中ci(i=l，2，…，k)為實常數(shù)，且ck≠0。它可改寫為一個線性常系數(shù)k階非齊次的差分方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=f(n)，n≥k(6.19)(6.19)與線性常系數(shù)k階非齊次常微分方程的結構十分相似，因而解法類同。限于篇幅，這里直接給出(6.19)的解法，略去其正確性的證明。第一步，求(6.19)所對應的齊次方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=0(6.20)的基本解系：寫出(6.20)的特征方程：C(t)=tk-c1tk-1-c2tk-2-…-ck=0(6.21)若t=r是(6.21)的m重實根，則得(6.20)的m個基礎解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一對l重的共扼復根，則得(6.20)的2l個基礎解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k個的基礎解。而且，這k個基礎解構成了(6.20)的基礎解系。即(6.20)的任意一個解都可以表示成這k個基礎解的線性組合。第二步，求(6.19)的一個特解。理論上，(6.19)的特解可以用Lagrange常數(shù)變易法得到。但其中要用到(6.20)的通解的顯式表達，即(6.20)的基礎解系的線性組合，十分麻煩。因此在實際中，常常采用試探法，也就是根據(jù)f(n)的特點推測特解的形式，留下若干可調(diào)的常數(shù)，將推測解代人(6.19)后確定。由于(6.19)的特殊性，可以利用迭加原理，將f(n)線性分解為若干個單項之和并求出各單項相應的特解，然后迭加便得到f(n)相應的特解。這使得試探法更為有效。為了方便，這里對三種特殊形式的f(n)，給出(6.19)的相應特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常數(shù)。表6-1方程(6.19)的常用特解形式f(n)的形式條

件方程(6.19)的特解的形式anC(a)≠0a是C(t)的m重根nsC(1)≠01是C(t)的m重根nsanC(a)≠0a是C(t)的m重根第三步，寫出(6.19)即(6.18)的通解(6.22)其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基礎解系，g(n)是(6.19)的一個特解。然后由(6.18)的初始條件T(i)=Ti，i=1,2,…,k-1來確定(6.22)中的待定的組合常數(shù){ai}，即依靠線性方程組或解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。第四步，估計(6.22)的漸近階，即為所要求。下面用兩個例子加以說明。例l考慮遞歸方程它的相應特征方程為：C(t)=t2-t-1=0解之得兩個單根和。相應的(6.20)的基礎解系為{r0n，r1n}。相應的(6.19)的一個特解為F*(n)=-8，因而相應的(6.19)的通解為：F(n)=a0r0n+a1r1n-8令其滿足初始條件，得二階線性方程組：或或解之得，，從而于是。例2考慮遞歸方程T(n)=4T(n-1)-4T(n-2)+2nn(6.23)和初始條件T(0)=0，T(1)=4/3。它對應的特征方程(6.21)為C(t)=t2-4t+4=0有一個兩重根r=2。故相應的(6.20)的基礎解系為{2n，2nn}。由于f(n)=2nn，利用表6-1，相應的(6.19)的一個特解為T*(n)=n2(p0+p1n)2n，代人(6.23)，定出p0=1/2，p1=1/6。因此相應的(6.19)的通解為：T(n)=a02n+a1n2n+n2(1/2+n/6)2n，令其滿足初始條件得a0=a1=0，從而T(n)=n2(1/2+n/6)2n于是T(n)=θ(n32n)。遞歸方程組解的漸進階的求法——母函數(shù)法關于T(n)的遞歸方程的解的母函數(shù)通常設為：(6.24)當(6.24)右端由于T(n)增長太快而僅在x=0處收斂時可另設(6.25)如果我們可以利用遞歸方程建立A(x)的一個定解方程并將其解出，那么，把A(x)展開成冪級數(shù)，則xn或xn/n!項的系數(shù)便是所求的遞歸方程的解。其漸近階可接著進行估計。下面舉兩個例子加以說明。例1考慮線性變系數(shù)二階齊次遞歸方程(n-1)T(n)=(n-2)T(n-1)+2T(n-2)，n≥2(6.26)和初始條件T(0)=0，T(1)=1。根據(jù)初始條件及(6.26)，可計算T(2)=0，T(3)=T(1)=1。設{T(n)}的母函數(shù)為：由于T(0)=T(2)=0，T(1)=1，有：令B(x)=A(x)/x，即：那么：利用(6.26)并代入T(3)=1，得即兩邊同時沿[0,x]積分，并注意到B(0)=1，有：把B(x)展開成冪級數(shù)，得從而最后得例2考慮線性變系數(shù)一階非齊次遞歸方程D(n)=nD(n-1)+(-1)n

n≥1(6.27)及初始條件D(0)=1很明顯D(n)隨n的增大而急劇增長。如果仍采用(6.24)形式的函數(shù)，則(6.24)的右端可能僅在x=0處收斂，所以這里的母函數(shù)設為：用xn/n!乘以(6.27)的兩端，然后從1到∞求和得：化簡并用母函數(shù)表達，有：A(x)-1=xA(x)+e-x-1或(1-x)A(x)=e-x從而A(x)=e-x/(1-x)展成冪級數(shù)，則：故算法設計策略這里介紹了一般的算法設計策略，闡述各方法的理論基礎、主要思想及其適用范圍。同時針對一些具體問題來講述如何用這些一般的理論以及各種抽象數(shù)據(jù)類型對問題進行抽象描述，并用最有效的方式設計出解決問題的高效算法。它們將生動地再現(xiàn)計算機程序設計方法學的理論、抽象和設計三個過程，而且，通過對算法正確性的證明和復雜性的分析，深化對大問題的復雜性、概念和形式模型、效率和抽象的層次、折衷和結論等在計算機學科中重復出現(xiàn)的概念的理解。必須強調(diào)指出，對于某些問題(如NP--完全問題)而言，用這里的方法和任何已知的方法都不可能設計出有效的算法。對于這種問題，人們常?？紤]利用具體輸入的某些特點來設計有效算法或設計求問題近似解的有效算法。這一部分內(nèi)容我們將在高級專題中討論。在對有關算法進行形式描述時我們采用類Pascal的偽代碼，并作了一些簡化，略去不言而喻的一些說明，如函數(shù)、形參、變量等類型說明。這里主要討論的算法設計策略有：遞歸技術——最常用的算法設計思想，體現(xiàn)于許多優(yōu)秀算法之中分治法——分而制之的算法思想，體現(xiàn)了一分為二的哲學思想模擬法——用計算機模擬實際場景，經(jīng)常用于與概率有關的問題貪心算法——采用貪心策略的算法設計狀態(tài)空間搜索法——被稱為“萬能算法”的算法設計策略隨機算法——利用隨機選擇自適應地決定優(yōu)先搜索的方向動態(tài)規(guī)劃——常用的最優(yōu)化問題解決方法摘要本文介紹了分治法的基本思想和基本步驟，通過實例討論了利用分治策略設計算法的途徑。目錄

簡介

分治法的基本思想

分治法的適用條件

分治法的基本步驟

分治法的復雜性分析

分治法的幾種變形

分治法的實例分析

其他資料參考文獻現(xiàn)代計算機常用數(shù)據(jù)結構和算法，潘金貴等編著，南京大學出版社，1992算法與數(shù)據(jù)結構，傅清祥王曉東編著，電子工業(yè)出版社，1998DictionaryofAlgorithms,DataStructures,andProblems，PaulE.Black，/dads/,下載該網(wǎng)站的鏡像（1,682KB）簡介對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。分治法的基本思想任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當困難的。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。如果原問題可分割成k個子問題，1<k≤n，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中，并由此產(chǎn)生許多高效算法。分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有steparemergedbeforethe"conquer"step.

pipelineddivideandconquer:Adivideandconquerparadigminwhichpartialresultsfromrecursivecallscanbeusedbeforethecallscomplete.Thetechniqueisoftenusefulforreducingthedepthofanalgorithm.

如果你有關于這兩種算法的資料請告訴我(mailto:Starfish.h@)。分治法的實例分析以上討論的是分治法的基本思想和一般原則，下面我們用具體的例子來說明如何針對具體問題用分治法來設計有效解法。例1和例2是分治法的經(jīng)典范例，其分解和合并過程都比較簡單明顯；例3和例4的合并方法有多種選擇，只有選擇最好的合并方法才能夠改進算法的復雜度；例5是一個計算幾何學中的問題，它的合并步驟需要較高的技巧。例6則是IOI'95的試題WiresandSwitches。例1二分查找例2快速排序例3大整數(shù)乘法例4Strassen矩陣乘法例5最接近點對問題例6導線和開關更多實例請參閱分治法問題集其他資料請參閱以下文章：遞歸技術貪心法動態(tài)規(guī)劃分治法問題集

用遞歸中序遍歷二叉樹

#include<stdlib.h>struct

tree

//聲明樹的結構

{

struct

tree

*left;

int

data;

struct

tree

*right;

};typedef

struct

tree

treenode;

type

treenode

*b_tree;

//聲明二叉樹鏈表//插入二叉樹的節(jié)點

b_tree

insert_node(b_tree

root,int

node)

{

b_tree

newnode;

b_tree

currentnode;

b_tree

parentnode;

newnode=(b_tree)malloc(sizeof(treenode));

//建立新節(jié)點的內(nèi)存空間

newnode->data=node;

newnode->right=NULL;

newnode->left=NULL;

if(root=NULL)

return

newnode;

else

{

currentnode=root;

while(currentnode!=NULL)

{

parentnode=currentnode;

if(

currentnode->data>node)

currentnode=currentnode->left;

else

currentnode=currentnode->right;

}

if(parentnode->data>node)

parentnode->left=newnode;

else

parentnode->right=newnode;

}

return

root;

}//

建立二叉樹

b_tree

create_btree(int

*data,int

len)

{

b_tree

root=NULL;

int

i;

for(i=0;i<len;i++)

root=insert_node(root,data[i]);

return

root;

}//二叉樹中序遍歷

void

inorder(b_tree

point)

{

if(point!=NULL)

{

inorder(point->left);

printf("%d",point->data);

inorder(point->right);

}

}//主程序

void

main(

)

{

b_tree

root=NULL;

int

i,index;

int

value;

int

nodelist[20];

printf("\n

pleaase

input

the

elements

of

binary

tree(exit

for

0

):\n");

index=0;

//讀取數(shù)值存到數(shù)組中

scanf("%d",&value);

while(value!=0)

{

nodelist[index]=value];

index=index+1;

scanf("%d",&value);

}

//建立二叉樹

root=create_btree(nodelist,index);

//中序遍歷二叉樹

printf("\nThe

inorder

traversal

result

is

:");

inorder(root);

printf("\n");

}

Bresenham高效畫線算法

畫線的算法不少，但要作到高速、簡單并不容易。斜率相乘法是最簡單的方法之一，但計算每個點均要花費不少時間用于乘、除法運算；下面介紹的是Bresenham's高效畫線算法，對每個點的坐標計算只要加、減法就能完成。

簡化算法用偽Pascal語言描述如下：

procedureDrawLine(x1,y1,x2,y2:Integer);

var

x,y,DeltaX,DeltaY,HalfX,ErrorTerm,i:Integer;

begin

DeltaX:=x2-x1;

DeltaY:=y2-y1;

HalfX:=(x2-x1)shr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaXdo

begin

Plot(X,Y);

Inc(x);

ErrorTerm:=ErrorTerm+DeltaY;

ifErrorTerm>HalfXthen

begin

ErrorTerm:=ErrorTerm-DeltaX;

Inc(y);

end;

end;

end;

為方便閱讀，上述程序作了簡化。實際程序應略作修正，以分別處理DeltaX與DeltaY比較大小,必要時交換起始、結束點等。

修正后的的偽Pascal算法如下：

procedureDrawLine(x1,y1,x2,y2:Integer);

var

x,y,DeltaX,DeltaY,HalfCount,ErrorTerm,i,Flag:Integer;

begin

DeltaX:=x2-x1;

DeltaY:=y2-y1;ifAbs(DeltaY)<Abs(DeltaX)then

begin

ifDeltaX<0then

begin

i:=x1;x1:=x2;x2:=i;

i:=y1;y1:=y2;y2:=i;

DeltaX:=x2-x1;

DeltaY:=y2-y1;

end;

ifDeltaY<0thenFlag:=-1

elseFlag:=1;

DeltaY:=Abs(DeltaY);

HalfCount:=DeltaXshr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaXdo

begin

Plot(X,Y);

Inc(x);

ErrorTerm:=ErrorTerm+DeltaY;

ifErrorTerm>HalfCountthen

begin

ErrorTerm:=ErrorTerm-DeltaX;

y:=y+Flag;

end;

end;

end

else

begin

ifDeltaY<0then

begin

i:=x1;x1:=x2;x2:=i;

i:=y1;y1:=y2;y2:=i;

DeltaX:=x2-x1;

DeltaY:=y2-y1;

end;

ifDeltaX<0thenFlag:=-1

elseFlag:=1;

DeltaX:=Abs(DeltaX);

HalfCount:=DeltaYshr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaYdo

begin

Plot(X,Y);

Inc(y);

ErrorTerm:=ErrorTerm+DeltaX;

ifErrorTerm>HalfCountthen

begin

ErrorTerm:=ErrorTerm-DeltaY;

x:=x+Flag;

end;

end;

end;

end;

C++的沉迷與愛戀

每年的09/28對於我都是一個特殊的日子--不只是因為教師節(jié)。今年很特殊地沒有普天同慶，那麼我就寫篇文章自己慶祝一下好了。

我於今年七月發(fā)表了一本著作<多型與虛擬>和一本譯作<深度探索C++物件模型>，獲得很大的回響。這些作品都不是針對C++的完全初學者所寫，但從初階到高階為數(shù)眾多的C++guy，熱情地表達了他們對這些主題的喜悅。

在許多來信中，我看到一些有趣的現(xiàn)象，也感受到一些值得整理下來的想法。所以，根據(jù)我個人的學習過往、我的教學經(jīng)驗、以及周遭朋友的心得交流，寫下這篇文章，或可為後學者戒?！?lt;多型與虛擬>序言節(jié)錄首先讓我節(jié)錄<多型與虛擬>一書序言：<多型與虛擬>序節(jié)錄（侯俊杰/松崗/1998/07）一般而言，C++是一個難學易用的語言。C++的難學，初始在於其重重的布幕，布幕之中編譯器對我們的程式碼做了太多的手腳，使我們慣於循序思考的工程腦袋一無所措。及長，又面臨新的思維模式，使我們必須扭轉(zhuǎn)慣常的思考習慣。C++的易用則在於其巨大的彈性，能夠以多型（polymorphism）、虛擬（virtual）、模板（template）、泛型（generalization）等種種型式，讓既有的碼去處理未知的、未來的資料型態(tài)。當然，易用必須先能用。用不好或不能用的話，「寫C++程式」最後就成了只是「使用C++編譯器」，這是大家常拿來彼此調(diào)侃的笑話。在「難學」的背景下，「易用」是使我們依然前仆後繼的動力。愈來愈多的大學資訊科系把C++開在大一課程，這雖然說明C++是多麼地重要，可也苦了資訊新兵們。其實「難學」的最大癥結在於，很難得有一本書，能夠一針見血地指出多型與虛擬的重要性；在我們粗具語法基礎之後，直接把我們導引到最核心最重要的思想，并且在建立這個思想的過程中，提供足夠的必要基礎。●困難度之一「C++是個難學易用的語言」，這句話相信很多人心有戚戚。C++的學習難度，一在於語言本身太多的「幕」，一在於"paradigmshift"（思考模式的移轉(zhuǎn)）。傳統(tǒng)循序語言如C,Pascal,Basic,Fortran...，除了模樣看起來稍有不同，基本上都是函式call來call去，大同小異，很容易掌握。你想做的動作，在code中都看得一清二楚。你所看不到的，犖犖大者也不過就是編譯器為你的函式加上用以處理堆疊的一小段碼（prologue和epilogue），這一小段碼基本上做的是housekeeping工作，你沒看到也沒有關系（更好），并不影響你對程式邏輯的思考。C++不一樣，C++有太多和程式邏輯息息相關的動作是編譯器為我們加上去的。換句話說C++編譯器為我們「加碼」。如果不識清這一節(jié)，學習C++有如霧里看花，霧非霧，花非花。編譯器為我們的C++程式加了什麼碼呢？很多！物件誕生時ctor會被喚起，物件死亡時dtor會被喚起，這都是加碼的結果。ctor中設定vtpr和vtbl，這也是加碼的結果。new單一物件時會產(chǎn)生memoryblockcookie，new物件陣列時會產(chǎn)生一個內(nèi)部結構記錄著objectsize和classctor...，這也都是布幕後的工作?？梢哉f，程式碼中看不到而卻必須完成的所有與程式邏輯有關的動作，統(tǒng)統(tǒng)都是C++編譯器加碼後的結果。當「繼承」發(fā)生，整個情況變得稍微復雜起來?！付嘀乩^承」又更復雜一些，「虛擬繼承」再更復雜一些。這些布幕後的主題，統(tǒng)可歸類為所謂的C++objectmodel（物件模型）。如果不知道這些底層機制，你就只能夠把"makedestructorsvirtualinbaseclasses"（<EffectiveC++>,item14）或"nevertreatarrayspolymorphically"（<MoreEffectiveC++>,item3）這類規(guī)則硬背下來，卻不明白它的道理。用一樣東西，卻不明白它的道理，林語堂如是說：『不高明』。只知道how，不知道why，侯捷如是說：『不高明』。●困難度之二C++的第二個學習難度在於"paradigmshift"（思考模式的移轉(zhuǎn)）。別說自己設計classes了，光使用別人的classes，就都是一種思考模式和行為模式的移轉(zhuǎn)。MFC（或OWL或VCL）programmer必然甚能夠領略并體會我的意思。使用所謂的applicationframework（一種大型的、凝聚性強的、有著物件導向公共基礎建設的classlibrary），你的碼和framework之間究竟是怎樣的關系呢？framework提供的一大堆可改寫的虛擬函式的意義與價值究竟在哪里呢？為什麼framework所設計的種種美好性質(zhì)以及各式各樣的演算法竟然可以施行於我們自己設計的classtypes身上呢？framework被設計時，并不知道我們的存在呀！這正是物件導向中的多型（polymorphism）的威力。稍早所說的C++物件模型，偏屬程式設計的低層面；這里所說的思考模式移轉(zhuǎn)，則是程式設計的高層面。能夠把新思維模式的威力發(fā)揮得最淋漓盡致的，當推物件導向的polymorphism（多型）和generalization（泛型）。如果你沒有使用這兩項特性，等於入C++寶山而空手返?！穹锤矡?，循環(huán)震蕩想像C++是一把用來解決程式問題的刀，要它堅軔，要它鋒利，就必須經(jīng)過多次的回火，在高熱和驟冷之間煉。初學C++語法（syntax）之後，你應該盡快嘗試體驗polymorphism（大致而言也就是虛擬函式的運用）。等到對OOP的精神有了大局掌控的能力，但對C++的許多小細節(jié)不甚清楚，就是回到C++物件模型煉的時機。成長，是在高階（polymorphism）和低階（objectmodel）之間反覆震蕩，才能夠震蕩到更高的位階，而不是平平庸庸於中階（C++syntax）的一灘死水。●不要沉淪於C++syntax100個人跟我說他懂C++/OOP，只有10%不到可以讓我認為他沒有胡吹大氣。太多的人，上嘛上不到polymorphism，下嘛又下不到objectmodel。就這樣不上不下地卡在C++語法層面。大一學了C++，到大四快畢業(yè)了，連virtualfunctions是怎麼回事都期期艾艾支支吾吾說不出個道理。有時候我覺得，太苛責同學也於心不忍，因為同學們事實上處於一種無知的狀態(tài)，既不知道C++/OOP該怎麼學，也不知道哪些書可以教他們那麼學。所以，苛責同學，不如責怪老師。眾所周知，大學教授泰半是動口不動手，普遍的心態(tài)是「論文第一，升等為要；程式語言？哎，末流！」?！改┝鳌拐n程通常由教授們輪流教，誰倒楣誰來教；於是就常常有「下學期要教C++語言了，這學期寒（暑）假趕快去要本書來惡補」的情況發(fā)生。偏偏程式語言這東西，只動口不管用，一定要動手，而且要常動手。老師自己沒有摸到C++/OOP的精神，學生又能學到什麼？有些學校資訊系并不教特定的程式語言，老師們的態(tài)度是「語言是一種自己學就好了的東西嘛，拿到大學殿堂來，哎，不入流」！於是應該好好為學生打下實際基礎的課程，卻天馬行空地騰云駕霧起來，大談抽象意念。飽讀經(jīng)書的老師們可能忽略了，一個完全沒有技術基礎的學子，要的不是形而上的道，而是形而下的器。我們是先能夠欣賞具象畫，還是先能夠欣賞抽象畫？我們不都是先對畢卡索的畫大罵「這是什麼東西」，直到自己的藝術涵養(yǎng)夠豐富了、人生閱練更飽滿了、能夠舉一隅以三隅反了、能夠接觸類旁通左右逢源了，才轉(zhuǎn)而能夠欣賞甚至進入畢卡索的抽象意境嗎？老師們各有專長，要老師們來教非彼專長的大班課、基礎課，我又覺得似乎也太為難老師了。那麼，苛責老師，不如責怪學校當局。如果學校當局能夠聘請經(jīng)驗老道又有教學熱誠的工程師來教這類實務學科，不是三方皆大歡喜嗎？不要說什麼制度僵化啦，難以突破啦，大學是高度自治區(qū)，禮聘幾位兼任老師，不全都是系上的權責范圍內(nèi)嗎？當學子們在課程上學不到他要的東西，就只好閉門自修。但是，循序性（sequential）語言尚有自修學會的可能，物件導向語言嘛，以大學生的程度來講，我認為自修實在困難，只會修出個四不像、半瓶水。管不到學校！管不到教授！自求多福的情況下，希望看到這篇文章的你，知道C++/OOP該怎麼學。●不要沉迷於C++semantics和C++objectmodel對於底層知識有濃厚興趣的朋友，下探到objectmodel領域，一定會非常開心地在objectsize、objectlayout、vptr/vtbl、以及許多布幕後的技術之間玩將起來。了解這些東西，當然是好的，但是由於一探究竟得其奧秘的快感與成就感，使得一些朋友們在這個層面里「玩」起來了，小地方玩得很精，玩得不亦樂乎，玩得忽略了C++/OO的最終目標。最終目標是polymorphism！我要說，在C++syntax以及相對低階的C++semantics里，不要玩得太過火。過猶不及，會傷身的。C++經(jīng)典名書內(nèi)附的一些習題，在我看來頗有點玩得過火的味道。至於什麼百題精選、題庫大成，除了修練基本功之外，都滿無趣的東西。Programming應該是一種天馬行空的想像力與創(chuàng)意的組合；如果你能夠自己想題目，譬如說實作一個天體運行的class體系、或是實作一個生物分類（界門綱目科屬種）體系，不是很有趣嗎？準備資料的過程中，查查百科全書，你也因此查到了太陽系九大行星的幾何資料，哈雷慧星的軌道周期，或是黑面琵鷺的「界門綱目科屬種」英文名稱，這難道不比鉆研於++++i或----i或*&*&p之類的頭腦體操題目有趣嗎？（看過不少這類好笑題目，沒一個記下來，只好胡亂寫幾個運算式。諸位應該知道我說的那種頭腦體操題目）固然，在科學與工程的領域里頭，無技術無以為立，但別把自己弄得過於僵化，過於匠氣。僵化與匠氣是我們教育體系的最大沉疴。到了高專層次，敗象顯露無遺?！衩麜扑]如果沒有介紹幾本好書，我就是為德不卒。讓我再節(jié)錄<多型與虛擬>的二刷感言：<多型與虛擬>一版二刷感言（侯俊杰/松崗/1998/08）...C++相關書籍，如天上繁星，如過江之鯽。廣博如四庫全書者有之（如TheC++ProgrammingLanguage、C++Primer），深奧宛如山重水復有之（如InsideTheC++ObjectModel），獨沽一味者有之（如C++ProgrammingStyle、MoreEffectiveC++），獨樹一幟者有之（如TheDesignandEvolutionofC++），另辟蹊徑者亦有之（如STLtutorialReferenceGuide）。...以下是我認為你應該要擁有的書籍。有趣的是，我才在自己班上做了一個調(diào)查（我教的是物件導向Windows程式設計，學生應該要有良好的C++/OOP基礎），擁有以下1~5本書的人舉手。舉手人數(shù)都很少，而且老是那幾位（最高記錄是擁有四本）。這讓我感覺，強者恒強，弱者恒弱。悲夫！1.C++Primer(3/e),Lippman/A.W./1998（聽說1999將有中譯本）2.TheC++ProgrammingLanguage(3/e),Bjarne/A.W./1997（聽說1999將有中譯本）以上兩本書是C++經(jīng)典百科。就內(nèi)容水平而言，我認為同為瑜亮。普遍的印象是，第一本較易接受，第二本澀味稍重。第二本書作者Bjarne是C++語言的創(chuàng)造者，所以有其權威性。我認識的多位C++/OOP高手，都是兩書齊具。3.InsideTheC++ObjectModel,Lippman/A.W./1996（中譯本<深度探索C++物件模型>）全書講解C++objectmodel，上窮碧落下黃泉。內(nèi)容很好，層次也高，可惜原文書大大小小的錯誤繁如晨星，閱讀時需小心。4.EffectiveC++,Meyers/A.W./1992（印象似有中譯本，名稱忘了，誰可補充說明？）5.MoreEffectiveC++,Meyers/A.W./1996（有中譯本嗎？我不知道，誰可補充說明？）同一作者的這兩本書，專講C++programming的重要觀念，使你的程式更穩(wěn)健更有效率。書中許多觀念涉及C++objectmodel，與(3)書混合看，如魚得水。6.PolymorphisminC++<多型與虛擬>侯俊杰/松崗/1998（沒有中譯本--它本身就是中文書）在語法粗具的基礎上，直接把讀者導引到最核心最重要的思想，并且在建立這個思想的過程中，提供足夠的必要基礎。我只列出一本中文書，是因為這方面的中文書我看得少，英文書看得多?！缚钟羞z珠之憾」這類「八方得體」的話，還是說一下好了:)。注意，這些都只是強本固元用來扎基礎的書籍而已，要觀摩大型程式經(jīng)驗，還有諸如LargeScaleC++SoftwareDesign（JohnLakos/A.W./1996）可以閱讀。OO的世界，不止OOP，還有OOA/OOD，那又是一缸子的學問和一缸子的書。

C++語言程序設計試題

2001年1月

說明：在本試卷中規(guī)定整型(int)數(shù)據(jù)占用4個字節(jié)的存儲單元。

一、選擇題(每小題1分，共6分)

1．由C++目標文件連接而成的可執(zhí)行文件的缺省擴展名為

。

A．

cpp

B.

exe

C．

obj

D.

lik2．在下面的一維數(shù)組定義中，哪一個有語法錯誤。

A.

int

a[]={1,2,3}

B.

int

a[10]={0}

C.

int

a[]

D.

int

a[5]3．在下面的函數(shù)聲明中，存在著語法錯誤的是

。

A.

void

BC(int

a,int)

B.

void

BD(int,int)

C.

void

BE(int,int=5)

D.

int

BF(int

x;int

y)4.假定AB為一個類，則該類的拷貝構造函數(shù)的聲明語句為

。

A．

AB&(AB

x)

B.

AB(AB

x)

C．

AB(AB

&)

D.

AB(AB*x)5．對于結構中定義的成員，其隱含訪問權限為

。

A．

public

B.

protected

C．

private

D.

static6．當使用fstream流類定義一個流對象并打開一個磁盤文件時，文件的隱含打開方式為

。

A．

ios::in

B.

ios::out

C．

ios::int|ios::out

D.

沒有

二、填空題(每小題2分，共24分)1．執(zhí)行“cout

<<43<<’-‘<<18<<’=’<<43-18<<endl;”語句后得到的輸出結果為

。2．已知’A’～’Z’的ASCII碼為65～90，當執(zhí)行“char

ch=14*5+2;cout

<<ch<<endl;”語句序列后，得到