當(dāng)函數(shù)執(zhí)行完畢后，如何返回調(diào)用處？

周立功教授數(shù)年之心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》以及《面向AMetal框架與接口的編程（上）》，書本內(nèi)容公開后，在電子行業(yè)掀起一片學(xué)習(xí)熱潮。經(jīng)周立功教授授權(quán)，本公眾號(hào)特對(duì)《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》一書內(nèi)容進(jìn)行連載，愿共勉之。

第二章為程序設(shè)計(jì)技術(shù)，本文為2.3 棧與函數(shù)返回。

當(dāng)函數(shù)執(zhí)行完畢后，如何返回調(diào)用處呢？由于該函數(shù)可能會(huì)被多次調(diào)用，且每次調(diào)用的地方很可能不一樣，這樣被調(diào)用函數(shù)也就不可能知道自己該返回到哪里，因此在調(diào)用函數(shù)時(shí)必須告訴被調(diào)用函數(shù)應(yīng)返回到哪里？

>>> 2.3.1 堆棧

為了保存變量（數(shù)據(jù)），通常計(jì)算機(jī)會(huì)提供非常多的內(nèi)存。為了便于管理內(nèi)存，將所有變量使用的內(nèi)存稱為棧，而將未分配的內(nèi)存區(qū)域稱為堆。這些未分配的內(nèi)存區(qū)域，程序員可以塊為單位請(qǐng)求它。這部分內(nèi)存是由操作系統(tǒng)管理的，一旦一塊內(nèi)存被分配出去，它只能由分配了這塊內(nèi)存的原始代碼使用，并使用指針訪問(wèn)這塊內(nèi)存。由于內(nèi)存是稀缺資源，當(dāng)程序不再需要該內(nèi)存時(shí)，都應(yīng)該釋放回去。如果不這樣做，程序?qū)?huì)耗光內(nèi)存，導(dǎo)致運(yùn)行速度下降甚至崩潰。這就是因?yàn)槌绦騿T沒(méi)有釋放本應(yīng)釋放的內(nèi)存，造成了所謂的內(nèi)存泄漏。

堆和棧是兩種常用的數(shù)據(jù)結(jié)構(gòu)，主要用于數(shù)據(jù)的動(dòng)態(tài)存儲(chǔ)。當(dāng)程序執(zhí)行時(shí)，棧中存儲(chǔ)的是程序的執(zhí)行過(guò)程，比如，main()函數(shù)的局部變量argc和argv都在棧中，而使用malloc()函數(shù)動(dòng)態(tài)分配的內(nèi)存是存儲(chǔ)在堆中的，堆棧共享同一塊內(nèi)存區(qū)域。通常程序棧占據(jù)這塊區(qū)域的下部，而堆用的是上部。當(dāng)調(diào)用函數(shù)時(shí)，函數(shù)的棧幀被推到棧上，棧向上“長(zhǎng)出”一個(gè)棧幀。當(dāng)函數(shù)終止時(shí)，其棧幀從程序棧彈出。雖然棧所使用的內(nèi)存不會(huì)被清理，但最終可能會(huì)被推到程序棧上的另一個(gè)棧幀覆蓋。動(dòng)態(tài)分配的內(nèi)存來(lái)自堆，堆向下生長(zhǎng)。隨著內(nèi)存的分配和釋放，堆中會(huì)布滿碎片。盡管堆是向下生長(zhǎng)的，但這只是大體方向，實(shí)際上內(nèi)存可能在堆上的任意位置分配。

平常大家所說(shuō)的“堆?！敝饕侵笚＃?jì)算機(jī)在硬件上直接支持棧。在計(jì)算機(jī)科學(xué)中，棧是一個(gè)抽象的概念。它的抽象行為特征是棧可以存儲(chǔ)相同類型的數(shù)據(jù)，通常又將棧中的數(shù)據(jù)稱為元素。只允許向棧中壓入一個(gè)元素（即入棧push），或從棧中刪除一個(gè)元素（即出棧pop），且元素按照“后進(jìn)先出”原則處理（last in，first out，LIFO），禁止測(cè)試或修改不在棧頂?shù)脑亍?/p>

圖2.7 四種棧示意圖

如圖2.7所示為通用計(jì)算機(jī)4種形式的棧，分別稱之為滿遞減堆棧、空遞減堆棧、滿遞增堆棧和空遞增堆棧，這些都是棧的物理結(jié)構(gòu)。其中的“遞減”是指數(shù)據(jù)入棧時(shí)堆棧指針的值減少，即堆棧從高地址向下增長(zhǎng)，就像鐘乳石一樣?！斑f增”是指數(shù)據(jù)入棧時(shí)堆棧指針的值增加，即堆棧從低地址向上增長(zhǎng)，就像石筍一樣。而“滿”是指SP指向的存儲(chǔ)單元保存最后入棧的數(shù)據(jù)；“空”是指SP指向的存儲(chǔ)單元將保存下一個(gè)入棧的數(shù)據(jù)。4種形式的棧都對(duì)應(yīng)相同的邏輯數(shù)據(jù)結(jié)構(gòu)，本書后續(xù)章節(jié)除非特殊說(shuō)明，否則均以“滿遞增堆棧”為例。

>>> 2.3.2 入棧與出棧

假設(shè)允許入棧和出棧數(shù)據(jù)為int，即sp為(int *)類型變量。如果入棧的數(shù)據(jù)小于sizeof(int)個(gè)字節(jié)，則需要將其轉(zhuǎn)換成int類型數(shù)據(jù)才能入棧，且出棧后也要進(jìn)行相應(yīng)的類型轉(zhuǎn)換。對(duì)于入棧的數(shù)據(jù)大于sizeof(int)個(gè)字節(jié)，則只能拆分?jǐn)?shù)據(jù)，一次入棧數(shù)據(jù)的一部分，通過(guò)多次入棧完成整個(gè)數(shù)據(jù)的入棧；而出棧這個(gè)數(shù)據(jù)也要多次，全部出棧后再組合成原始數(shù)據(jù)。

1. 入棧（push）操作

如果將sp當(dāng)作(int *)類型的變量，則對(duì)于滿遞增堆棧來(lái)說(shuō)，將數(shù)據(jù)data入棧用C語(yǔ)言描述如下（詳見(jiàn)圖2.8）：

圖2.8 入棧操作示意圖

如果data的長(zhǎng)度大于sizeof(int)，則需要將數(shù)據(jù)拆分后多次入棧，入棧的順序可以先低位后高位，也可以反過(guò)來(lái)。如果入棧的順序?yàn)橄鹊臀缓蟾呶唬涫纠斠?jiàn)程序清單 2.27。

程序清單 2.27 先低位后高位順序入棧示例

這里假設(shè)data可以象整數(shù)一樣移位，且sizeof(data)是sizeof(int)的4倍。

2. 出棧（pop）操作

如果將sp當(dāng)作(int *)類型的變量，則對(duì)于滿遞增堆棧來(lái)說(shuō)，將數(shù)據(jù)出棧用C語(yǔ)言描述如下（假設(shè)出棧的數(shù)據(jù)保存到變量data中，詳見(jiàn)圖2.9）：

圖2.9 出棧操作示意圖

如果出棧數(shù)據(jù)data的長(zhǎng)度大于sizeof(int)，則需要多次出棧后拼接數(shù)據(jù)，其拼接的順序?yàn)槿霔５姆葱?。如果入棧的順序?yàn)橄鹊臀缓蟾呶唬斠?jiàn)程序清單 2.28。

程序清單 2.28 先高位后低位順序出棧示例

這里假設(shè)data可以象整數(shù)一樣進(jìn)行位操作，且sizeof(data)是sizeof(int)的4倍。

>>> 2.3.3 函數(shù)的調(diào)用與返回

在討論ADT棧之前，首先看一種用于處理程序運(yùn)行時(shí)的函數(shù)調(diào)用的系統(tǒng)棧。每當(dāng)函數(shù)被調(diào)用時(shí)，系統(tǒng)首先創(chuàng)建一個(gè)稱作活動(dòng)記錄或棧幀的結(jié)構(gòu)，將其放在系統(tǒng)棧的棧頂。初始時(shí)，被調(diào)函數(shù)的活動(dòng)記錄只包含一個(gè)指向前一個(gè)活動(dòng)記錄的指針和一個(gè)返回地址。前一個(gè)活動(dòng)記錄的指針指向調(diào)用函數(shù)的活動(dòng)記錄，而返回地址包含的是函數(shù)調(diào)用結(jié)束后下一條執(zhí)行語(yǔ)句的地址。因?yàn)樵谌魏螘r(shí)刻只有一個(gè)函數(shù)被執(zhí)行，所以被執(zhí)行的函數(shù)就是活動(dòng)記錄位于系統(tǒng)棧棧頂?shù)暮瘮?shù)。

如果該函數(shù)又調(diào)用其它函數(shù)，那么函數(shù)中的局部變量（靜態(tài)局部變量除外）及其參數(shù)也將加到其活動(dòng)記錄中，然后為被調(diào)函數(shù)創(chuàng)建一個(gè)新的活動(dòng)記錄并存放在系統(tǒng)棧棧頂?shù)暮瘮?shù)。當(dāng)被調(diào)函數(shù)結(jié)束時(shí)，刪除該活動(dòng)記錄。此時(shí)調(diào)用函數(shù)的活動(dòng)記錄又位于系統(tǒng)棧的棧頂，繼續(xù)運(yùn)行該函數(shù)。

C語(yǔ)言通過(guò)硬件棧保存函數(shù)的返回地址，被調(diào)用函數(shù)將返回地址出棧到程序計(jì)數(shù)器PC中，以返回到調(diào)用點(diǎn)，其示例代碼詳見(jiàn)程序清單2.29。

程序清單2.29 函數(shù)的調(diào)用與返回示例

對(duì)于程序清單2.29（10）來(lái)說(shuō)，用C語(yǔ)言描述如下：

對(duì)于程序清單2.29（5）來(lái)說(shuō)，用C語(yǔ)言描述如下：

由此可見(jiàn)，當(dāng)調(diào)用函數(shù)時(shí)，將主程序代碼行的下一條指令的地址保存到棧中；當(dāng)函數(shù)返回時(shí)，程序就會(huì)從棧中獲取該地址，并從那一點(diǎn)繼續(xù)向下執(zhí)行。在函數(shù)調(diào)用了其它函數(shù)的情況下，將每一個(gè)返回地址都放到棧中；當(dāng)函數(shù)結(jié)束時(shí)，就可以找到它們?cè)跅Ｖ械牡刂贰?/p>