前篇說明了函數的部分實現方式,但並沒有說明函數這個語法的語義,即函數有什麼用及為什麼被使用。對於此,本篇及後續會零散提到一些,在《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映射的地址在程序運行時是變化的,也就不能且無法編譯時靜態一次確定。
為了實現上面的要求,編譯器實際將會在棧上分配內存,然後將地