C++從零開始（八）——C++樣例一 
 
 
文章錄入：7747.Net    責任編輯：7747.Net  更新時間：2008-11-19 22:31:07 18 
 【字體：小 大】
 
 
前篇說明了函數的部分實現方式，但并沒有說明函數這個語法的語義，即函數有什么用及為什么被使用。對于此，本篇及后續會零散提到一些，在《C++從零開始（十二）》中再較詳細地說明。本文只是就程序員的基本要求——拿得出算法，給得出代碼——給出一些樣例，以說明如何從算法編寫出C++代碼，并說明多個基礎且重要的編程概念（即獨立于編程語言而存在的概念）。


由算法得出代碼

本系列一開頭就說明了何謂程序，并說明由于CPU的世界和人們存在的客觀物理世界的不兼容而導致根本不能將人編寫的程序（也就是算法）翻譯成CPU指令，但為了能夠翻譯，就必須讓人覺得CPU世界中的某些東西是人以為的算法所描述的某些東西。如電腦屏幕上顯示的圖片，通過顯示器對不同象素顯示不同顏色而讓人以為那是一幅圖片，而電腦只知道那是一系列數字，每個數字代表了一個象素的顏色值而已。
為了實現上面的“讓人覺得是”，得到算法后要做的的第一步就是找出算法中要操作的資源。前面已經說過，任何程序都是描述如何操作資源的，而C++語言本身只能操作內存的值這一種資源，因此編程要做的第一步就是將算法中操作的東西映射成內存的值。由于內存單元的值以及內存單元地址的連續性都可以通過二進制數表示出來，因此要做的第一步就是把算法中操作的東西用數字表示出來。
上面做的第一步就相當于數學建模——用數學語言將問題表述出來，而這里只不過是用數字把被操作的資源表述出來罷了（應注意數字和數的區別，數字在C++中是一種操作符，其有相關的類型，由于最后對它進行計算得到的還是二進制數故使用數字進行表示而不是二進制數，以增強語義）。接著第二步就是將算法中對資源的所有操作都映射成語句或函數。
用數學語言對算法進行表述時，比如將每10分鐘到車站等車的人的數量映射為一隨機變量，也就前述的第一步。隨后定此隨機變量服從泊松分布，也就是上面的第二步。到站等車的人的數量是被操作的資源，而給出的算法是每隔10分種改變這個資源，將它的值變成按給定參數的泊松函數分布的一隨機值。
在C++中，前面已經將資源映射成了數字，接著就要將對資源的操作映射成對數字的操作。C++中能操作數字的就只有操作符，也就是將算法中對資源的所有操作都映射成表達式語句。
當上面都完成了，則算法中剩下的就只有執行順序了，而執行順序在C++中就是從上朝下書寫，而當需要邏輯判斷的介入而改變執行順序時，就使用前面的if和goto語句（不過后者也可以通過if后接的語句來實現，這樣可以減少goto語句的使用，因為goto的語義是跳轉而不是“所以就”），并可考慮是否能夠使用循環語句以簡化代碼。即第三步為將執行流程用語句表示出來。
而前面第二步之所以還說可映射成函數，即可能某個操作比較復雜，還帶有邏輯的意味，不能直接找到對應的操作符，這時就只好利用萬能的函數操作符，對這個操作重復剛才上面的三個步驟以將此操作映射成多條語句（通過if等語句將邏輯信息表現出來），而將這些語句定義為一函數，供函數操作符使用以表示那個操作。
上面如果未明不要緊，后面有兩個例子，都將分別說明各自是如何進行上述步驟的。


排序

給出三張卡片，上面隨便寫了三個整數。有三個盒子，分別標號為1、2和3。將三張卡片隨機放到1、2、3這三個盒子中，現在要求排序以使得1、2、3三個盒子中裝的整數是由小到大的順序。
給出一最簡單的算法：稱1、2、3盒子中放的卡片上的整數分別為第一、二、三個數，則先將第一個數和第二個數比較，如果前者大則兩個盒子內的卡片交換；再將第一個和第三個比較，如果前者大則交換，這樣就保證第一個數是最小的。然后將第二個數和第三個數比較，如果前者大則交換，至此排序完成。
第一步：算法中操作的資源是裝在盒子中的卡片，為了將此卡片映射成數字，就注意算法中的卡片和卡片之前有什么不同。算法中區分不同卡片的唯一方法就是卡片上寫的整數，因此在這里就使用一個long類型的數字來表示一個卡片。
算法中有三張卡片，故用三個數字來表示。前面已經說過，數字是裝在內存中的，不是變量中的，變量只不過是映射地址而已。在這里需要三個long類型數字，可以借用定義變量時編譯器自動在棧上分配的內存來記錄這些數字，故可以如此定義三個變量long a1, a2, a3;來記錄三個數字，也就相當于裝三張卡片的三個盒子。
第二步：算法中的操作就是對卡片上的整數的比較和交換。前者很簡單，使用邏輯操作符就可以實現（因為正好將卡片上的整數映射成變量a1、a2和a3中記錄的數字）。后者是交換兩個盒子中的卡片，可以先將一卡片從一盒子中取出來，放在桌子上或其他地方。然后將另一盒子中的卡片取出來放在剛才空出來的盒子。最后將先取出來的卡片放進剛空出來的盒子。前面說的“桌子上或其他地方”是用來存放取出的卡片，C++中只有內存能夠存放數字，因此上面就必須再分配一臨時內存來臨時記錄取出的數字。
第三步：操作和資源都已經映射好了，算法中有如果的就用if替換，由什么重復多少次的就用for替換，有什么重復直到怎樣的就用while或do while替換，如上照著算法映射過來就完了，如下：
void main()
{
long a1 = 34, a2 = 23, a3 = 12;
if( a1 > a2 )
{
long temp = a1;
a1 = a2;
a2 = temp;
}
if( a1 > a3 )
{
long temp = a1;
a1 = a3;
a3 = temp;
}
if( a2 > a3 )
{
long temp = a2;
a2 = a3;
a3 = temp;
}
}
上面就在每個if后面的復合語句中定義了一個臨時變量temp以借助編譯器的靜態分配內存功能來提供臨時存放卡片的內存。上面的元素交換并沒有按照前面所說映射成函數，是因為在這里其只有三條語句且容易理解。如果要將交換操作定義為一函數，則應如下：
void Swap( long *p1, long *p2 ) void Swap( long &r1, long &r2 )
{ {
long temp = *p1; long temp = r1;
*p1 = *p2; r1 = r2;
*p2 = temp; r2 = temp;
} }
void main() void main()
{ {
long a1 = 34, a2 = 23, a3 = 12; long a1 = 34, a2 = 23, a3 = 12;
if( a1 > a2 ) if( a1 > a2 )
Swap( &a1, &a2 ); Swap( a1, a2 );
if( a1 > a3 ) if( a1 > a3 )
Swap( &a1, &a3 ); Swap( a1, a3 );
if( a2 > a3 ) if( a2 > a3 )
Swap( &a2, &a3 ); Swap( a2, a3 );
} }
先看左側的程序。上面定義了函數來表示給定盒子之間的交換操作，注意參數類型使用了long*，這里指針表示引用（應注意指針不僅可以表示引用，還可有其它的語義，以后會提到）。
什么是引用？注意這里不是指C++提出的那個引用變量，引用表示一個連接關系。比如你有手機，則手機號碼就是“和你通話”的引用，即只要有你的手機號碼，就能夠實現“和你通話”。
再比如Windows操作系統提供的快捷方式，其就是一個“對某文件執行操作”的引用，它可以指向某個文件，通過雙擊此快捷方式的圖標就能夠對其所指的文件進行“執行”操作（可能是用某軟件打開這個文件或是直接執行此文件等），但如果刪除此快捷方式卻并不會刪除其所指向的文件，因為它只是“對某文件執行操作”的引用。
人的名字就是對“某人進行標識”的引用，即說某人考上大學通過說那個人的名字則大家就可以知道具體是哪個人。同樣，變量也是引用，它是某塊內存的引用，因為其映射了地址，而內存塊可以通過地址來被唯一表明其存在，不僅僅是標識。注意其和前面的名字不同，因為任何對內存塊的操作，只要知道內存塊的首地址就可以了，而要和某人面對面講話或吃飯，只知道他的名字是不夠的。
應注意對某個東西的引用可以不止一個，如人就可以有多個名字，變量也都有引用變量，手機號碼也可以不止一個。
注意上面引入了函數來表示交換，進而導致了盒子也就成了資源，因此必須將盒子映射成數字。而前面又將盒子里裝的卡片映射成了long類型的數字，由于“裝”這個操作，因此可以想到使用能夠標識裝某個代表卡片的數字的內存塊來作為盒子映射的數字類型，也就是內存塊的首地址，也就是long*類型（注意不是地址類型，因為地址類型的數字并不返回記錄它的內存的地址）。所以上面的函數參數類型為long*。
下面看右側的程序。參數類型變成long&，和指針一樣，依舊表示引用，但注意它們的不同。后者表示它是一個別名，即它是一個映射，映射的地址是記錄作為參數的數字的地址，也就是說它要求調用此函數時，給出的作為參數的數字一定是有地址的數字。所謂的“有地址的數字”表示此數字是程序員創建的，不是編譯器由于臨時原因而生成的臨時內存的地址，如Swap( a1++, a2 );就要報錯。之前已經說明，因為a1++返回的地址是編譯器內部定的，就程序邏輯而言，其是不存在的，而Swap( ++a1, a2 );就是正確的。Swap( 1 + 3, 34 );依舊要報錯，因為記錄1 + 3返回的數字的內存是編譯器內部分配的，就程序邏輯上來說，它們并沒有被程序員用某塊內存記錄起來，也就不會有內存。
一個很簡單的判定規則就是調用時給的參數類型如果是地址類型的數字，則可以，否則不行。
還應注意上面是long&類型，表示所修飾的變量不分配內存，也就是編譯器要靜態地將參數r1、r2映射的地址定下來，對于Swap( a1, a2 );就分別是a1和a2的地址，但對于Swap( a2, a3 );就變成a2和a3的地址了，這樣是無法一次就將r1、r2映射的地址定下來，即r1、r2映射的地址在程序運行時是變化的，也就不能且無法編譯時靜態一次確定。
為了實現上面的要求，編譯器實際將會在棧上分配內存，然后將地址傳遞到函數，再編寫代碼以使得好像動態綁定了r1、r2的地址。這實際和將參數類型定為long*是一樣的效果，即上面的Swap( long&, long& );和Swap( long*, long* );是一樣的，只是語法書寫上不同，內部是相同的，連語義都相同，均表示引用（雖然指針不僅僅只帶有引用的語義）。即函數參數類型為引用類型時，依舊會分配內存以傳遞參數的地址，即等效于指針類型為參數。


商人過河問題

3個商人帶著3個仆人過河，過河的工具只有一艘小船，只能同時載兩個人過河，包括劃船的人。在河的任何一邊，只要仆人的數量超過商人的數量，仆人就會聯合起來將商人殺死并搶奪其財物，問應如何設計過河順序才能讓所有人都安全地過到河的另一邊。
給出最弱卻萬能的算法——枚舉法。坐船過河及劃船回來的可能方案為一個仆人、一個商人或兩個商人、兩個仆人及一個商人一個仆人。
故每次從上述的五種方案中選擇一個劃過河去，然后檢查河岸兩側的人數，看是否會發生仆人殺死商人，如果兩邊都不會，則再從上述的五個方案中選擇一個讓人把船劃回來，然后再檢查是否會發生仆人殺死商人，如果沒有就又重新從五個方案中選一個劃過河，如上重復直到所有人都過河了。
上面在選方案時除了保證商人不被殺死，還要保證此方案運行（即過河或劃回來）后，兩岸的人數布局從來都沒有出現過，否則就形成無限循環，且必須合理，即沒有負數。如果有一次的方案選擇失敗，則退回去重新選另一個方案再試。如果所有方案都失敗，則再退回到更上一次的方案選擇。如果一直退到第一次的方案選擇，并且已沒有可選的方案，則說明上題無解。
上面的算法又提出了兩個基本又重要的概念——層次及容器。下面先說明容器。
容器即裝東西的東西，而C++中操作的東西只有數字，因此容器就是裝數字的東西，也就是內存。容器就平常的理解是能裝多個東西，即能裝多個數字。這很簡單，使用之前的數組的概念就行了。但如果一個盒子能裝很多蘋果，那它一定占很大的體積，即不管裝了一個蘋果還是兩個蘋果，那盒子都要占半立方米的體積。數組就好像盒子，不管裝一個元素還是兩個元素，它都是long[10]的類型而要占40個字節。
容器是用來裝東西的，那么要取出容器中裝的東西，就必須有種手段標識容器中裝的東西，對于數組，這個東西就是數組的下標，如long a[10]; a[3];就取出了第四個元素的值。由于有了標識，則還要有一種手段以表示哪些標識是有效的，如上面的a數組，只前面兩個元素記錄了數字，但是卻a[3];，得到的將是錯誤的值，因為只有a[0]和a[1]是有意義的。
因此上面的用數組作容器有很多的問題，但它非常簡單，并能體現各元素之間的順序關系，如元素被排序后的數組。但為了適應復雜算法，必須還要其他容器的支持，如鏈表、樹、隊列等。它們一般也被稱做集合，都是用于管理多個元素用的，并各自給出了如何從眾多的元素中快速找到給定標識所對應的元素，而且都能在各元素間形成一種關系，如后面將要提到的層次關系、前面數組的順序關系等。關于那些容器的具體實現方式，請參考其他資料，在此不表。
上面算法中提到“兩岸的人數布局從來都沒有出現過”，為了實現這點，就需要將其中的資源——人數布局映射為數字，并且還要將曾經出現過的所有人數布局全部記錄下來，也就是用一個容器記錄下來，由于還未說明結構等概念，故在此使用數組來實現這個容器。上面還提到從已有的方案中選擇一個，則可選的方案也是一個容器，同上，依舊使用一數組來實現。
層次，即關系，如希望小學的三年2班的XXX、中國的四川的成都的XXX等，都表現出一種層次關系，這種層次關系是多個元素之間的關系，因此就可以通過找一個容器，那個容器的各元素間已經是層次關系，則這個容器就代表了一種層次關系。樹這種容器就是專門對此而設計的。