計算機算法基礎(chǔ)1

計算機導(dǎo)法基砒

（課件V0.1）

王多強

華中科技大學(xué)計算機學(xué)院

2011-7-7

序

專業(yè)基礎(chǔ)課程：

數(shù)據(jù)結(jié)構(gòu)、計算機語言

操作系統(tǒng)、編譯

如何編寫計算機程序：

?數(shù)據(jù)結(jié)構(gòu)+算法=程序

?算法：計算機軟件的“靈魂”

算法是計算機科學(xué)和計算機應(yīng)用的核心

2011-7-7

教材：

計算機算法基礎(chǔ)余祥宣等編著華中科技大學(xué)出版社

參考書：

算法設(shè)計與分析王曉東編著清華大學(xué)出版社

計算機算法導(dǎo)引——設(shè)計與分析盧開澄編著清華大

學(xué)出版社

IntroductionToAlgorithm高教出版社，MITPress

學(xué)時：32+8學(xué)時

2011-7-7

章節(jié)安排

?第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)

?第二章分治法

?第三章貪心方法

?第四章動態(tài)規(guī)劃

?第五章檢索與周游

?第六章回溯法?

?第七章分枝邛艮界?

?第八章NP-問題9

2011-7-7

第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)::

1.1算法的定義及特性

1.什么是算法？

★算法如數(shù)字、計算一樣，是一個基本概念。

★算法是解一確定類問題的任意一種特殊的方法。

★在計算機科學(xué)中，算法是使用計算機解一類問題

的精確、有效方法的代名詞；

算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型

問題的一系列運算。

2011-7-7

2.算法的五個重要特性

確定性、能行性、輸入、輸出、有窮性

1）確定性：算法的每種運算必須要有確切的定

義，不能有二義性。

例：不符合確定性的運算

?5/0

?將6或7與x相加I

?未賦值變量參與運算

2011-7-7

2）能行性

算法中有待實現(xiàn)的運算都是基本的運算，

原理上每種運算都能由人用紙和筆在“有限”的

時間內(nèi)完成。

例：整數(shù)的算術(shù)運算是“能行”的

實數(shù)的算術(shù)運算是“不能行”的

2011-7-7

3）輸入

每個算法有。個或多個輸入。這些輸入是在算法開始之前

給出的量，取自于特定的對象集合——定義域（或值域）

4）輸出

一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種

特定關(guān)系的量。

2011-7-7

5）有窮性

一個算法總是在執(zhí)行了有窮步的運算之后終止。

計算過程：只滿足確定性、能行性、輸入、輸出四個特

性的一組規(guī)則

?算法和計算過程的區(qū)別：

＞計算過程：操作系統(tǒng)（不終止的運行過程）

＞算法是“可以終止的計算過程”

?算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投

入到計算機上運行

2011-7-7

4.我們的主要任務(wù)???:

算法學(xué)習(xí)將涉及5個方面的內(nèi)容：：

1）設(shè)計算法：創(chuàng)造性的活動

2）表示算法：思想的表示形式，SPARKS語言

3）確認(rèn)算法：證明算法對所有可能的合法輸入都能得出正確的答案。

算法證明：證明算法的正確性，與語言無關(guān)

程序證明：證明程序的正確性

4）分析算法：對算法的時、空特性做定量分析，以了解算法的好壞

5）測試程序：

調(diào)試：“調(diào)試只能指出有錯誤，而不能指出它們不存在錯誤”

作時空分布圖：驗證分析結(jié)論，優(yōu)化算法設(shè)計

本課程集中于學(xué)習(xí)算法的設(shè)計與分析。通過學(xué)習(xí)，掌握計算機算

法設(shè)計和分析基本策略與方法，為設(shè)計更復(fù)雜、更有效的算法奠定基

礎(chǔ)

2011-7-7

5.課程關(guān)系

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

程序設(shè)計語言：結(jié)構(gòu)化設(shè)計

數(shù)學(xué)基礎(chǔ)

非數(shù)值計算領(lǐng)域的基本知識

2011-7-7

1.2分析算法

1.分析算法的目的

在于：通過對算法的分析，在把算法變成程序?qū)嶋H運行前,

就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好的算

法，改進差的算法，避免無益的人力和物力浪費。

算法分析是計算機領(lǐng)域的“古老”而“前沿”的課題。

2011-7-7

2.重要的假設(shè)和約定

1）計算機模型的假設(shè)

?計算機形式理論模型：Turing機模型

?通用計算機模型：

>順序計算機

>有足夠的“內(nèi)存”

>能在固定的時間內(nèi)存取數(shù)據(jù)單元

2011-7-7

2）計算的約定：：：!

算法的執(zhí)行時間立fJt??

其中，才是算法中用到的某種運算i的次數(shù)——稱為該運算的“頻率計數(shù)”

t是該運算執(zhí)行一次所用的時間——與程序語言和硬件有關(guān)

確定：使用何種運算及其執(zhí)行時間。

?從運算的“時間特性”上將運算的分類：

＞時間囿界于常數(shù)的運算：

.基本算術(shù)運算，如整數(shù)、浮點數(shù)的加、減、乘、除

?字符運算、賦值運算、過程調(diào)用等

特點：盡管每種運算的執(zhí)行時間不同，但一般只花一個

固定量的時間（單位時間）就可完成。

2011-7-7

2）計算的約定（續(xù)）：

A其他運算：

?字符串操作：與字符串中字符的數(shù)量成正比

?記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)

特點：運算時間無定量。

如何分析非時間囿界于常數(shù)的運算：分解成若干時間囿

界于常數(shù)的運算。

如:tstring=Length（String）*tchar

2011-7-7

3）工作數(shù)據(jù)集的選擇

?編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)

配置。然后使用這些數(shù)據(jù)配置運行算法，以了解算法的性

能。

編制測試數(shù)據(jù)是程序測試與算法分析中的關(guān)鍵技術(shù)之一。

?作為算法分析的數(shù)據(jù)集：反映算法的典型特征

?作為程序正確性及性能測試的數(shù)據(jù)集：測試程序的對錯，反映對性

能指標(biāo)產(chǎn)生影響的方面，如邊界值

2011-7-7

3?如何進行算法分析？?

對算法進行全面分析，可分兩個階段進行：

?事前分析：求算法的一個時間/空間限界函數(shù)，即通過對算

法的“理論”分析，得出關(guān)于算法時間和空間

特性

的特征函數(shù)（0、Q）——與計算機物理軟硬

件沒有直接關(guān)系。

?事后測試：將算法編制成程序后實際放到計算機上運行，

收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行

分析判斷一一直接與物理實現(xiàn)有關(guān)。

2011-7-7

1）事前分析

?目的：試圖得出關(guān)于算法特性的一種形式描

述，以“理論上”衡量算法的“好壞”。

?如何給出反映算法特性的描述？

統(tǒng)計算法中各種運算的執(zhí)行情況，包括：

>引用了哪些運算

>每種運算被執(zhí)行的次數(shù)

>該種運算執(zhí)行一次所花費的時間等。

算法的執(zhí)行時間二Zfjtj

2011-7-7

?頻率計數(shù)

頻率計數(shù)：算法中語句或運算的執(zhí)行次數(shù)。

例:

x<—x+yfori<—1tondofori<—1tondo

x<—x+yforj<—1tondo

repeatx—x+y

repeat

repeat

(a)(b)⑹

分析:

(/a\

\7?X—x+y執(zhí)行了1次

(zb!\

\/?x-x+y執(zhí)行了n次

(/c)\

\/?x—x+y執(zhí)行了《次

2011-7-7

一條語句在整個程序運行時實際執(zhí)行時間二

頻率計數(shù)*每執(zhí)行一次該語句所需的時間

?在事前分析中，只限于確定與所使用的機器及其他環(huán)境因

素?zé)o關(guān)的頻率計數(shù)，依此建立一種理論上分析模型。

2011-7-7

?數(shù)量級

—衡量頻率計數(shù)的“大小”的一種測度

>語句的數(shù)量級：語句的執(zhí)行頻率

例：1,n,n2

a算法的數(shù)量級：算法所包含的所有語句的執(zhí)行頻率之和。

數(shù)量級反映了算法復(fù)雜度的最本質(zhì)的特征。

例：假如求解同一個問題的三個算法分別具有n,n2,2數(shù)量級。

若n=10,則可能的執(zhí)行時間將分別是10,100,1000個單

位時間——與環(huán)境因素?zé)o關(guān)。

2011-7-7

?頻率計數(shù)的函數(shù)表示

就計算時間而言，事前分析階段求得算法在頻率計成

上的函數(shù)表示——與規(guī)模n有關(guān)的函數(shù)形式，記為：g(n)

不同的算法，g(n)的具體形式是不同的，如

logn,nlogn,?等

g(n)的一般形式：關(guān)于n的簡單函數(shù)式

“實際”能夠得到的：

1)函數(shù)式的最高次項

2)最高次項與函數(shù)整體的關(guān)系。

?空間特性分析(與時間特性的分析類似，略)

2011-7-7

2）事后測試

?H的：運行程序，統(tǒng)計執(zhí)行實際耗費的準(zhǔn)確的時

間與空間，與事前分析的結(jié)論進行比較，驗證先

前的分析結(jié)論——包括正確性、執(zhí)行性能等，比

較、優(yōu)化所設(shè)計的算法。

?分析手段：作時、空性能分布圖

2011-7-7

4,計算時間的漸近表示?：

記：算法的實際計算時間為f(n),計算時間的限界函數(shù)為g(n)::'

其中，

?n是輸入或輸出規(guī)模的某種測度。

?f(n)表示算法的“實際”執(zhí)行時間一與機器及語言有關(guān)。

?g(n)是事前分析的結(jié)果---一個形式簡單的函數(shù)，如nm,logn,

2n,n!等。是與頻率計數(shù)有關(guān)、而與機器及語言無

關(guān)的函數(shù)。

以下給出算法執(zhí)行時間：上界(0)、下界(。)、“平均”

()有J定義。

2011-7-7

1)上界函數(shù)

定義1如果存在兩個正常數(shù)c和n。，對于所有的nN國,有

If(n)|<c|g(n)

則記作f(n)=O(g(n))

含義：

?如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的

時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的

一個上界函數(shù)。f(n)的數(shù)量級就是g(n)。

?試圖求出最小的g(n),使得f(n)=0(g(n))o

2011-7-7

多項式定理：

定理1若A(n)=*心+…+即口+@0是一個m次多項式，則有

A(n)=O(nm)

即：變量n的固定階數(shù)為m的任一多項式，與此多項式的最高階

W同階。

證明：取國=1,當(dāng)nNrio時，有

m

|A(n)|<|am|n+..,+laJn+laol

+mm

^(|aml|am-il/n+...+|a0|/n)n

m

=(|am|+|am,1|+...+|a0|)n

令c二|am|+|am,1|+...+|a0|

則,定理得證。

2011-7-7

計算時間的數(shù)量級的大小對算法的有效性有決定性的影響

??

例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入，

計算時間的數(shù)量級分別是M和nlogn。貝U,

n=1024：分別需要1048576和10240次運算。

n=2048：分別需要4194304和22528次運算。

分析：

*同等規(guī)模下的計算量比較：

☆規(guī)模增大情況下的比較：在n加倍的情況下，一個0(小)的

算法計算時間增長4倍，而一個0(nlogn)算法則只用兩倍多一點的

時間即可完成。

2011-7-7

多項式時間算法和指數(shù)時間算法

>多項式時間算法：可用多項式(函數(shù))對其計算時間限界

的算法。

常見的多項式限界函數(shù)有：

0(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)

>指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法

常見的指數(shù)時間限界函數(shù)：

O⑵)<O(n!)<O(nn)

說明：當(dāng)n取值較大時，指數(shù)時間算法和多項式時間算法在計算時

間上非常懸殊。

2011-7-7

典型的計算時間函數(shù)曲線

圖1.1一般計算時間函數(shù)的曲線

2011-7-7

?一般認(rèn)識

＞當(dāng)數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計算機系統(tǒng)上運行

具有比O(nlogn)復(fù)雜度還高的算法是比較困難的。

＞指數(shù)時間算法只有在n取值非常小時才實用。

＞要想在順序處理機上擴大所處理問題的規(guī)模，有效的途徑

是降低算法的計算復(fù)雜度，而不是(僅僅依靠)提高計算

機的速度。

2011-7-7

計算時間函數(shù)值比較

表LI計算時間困數(shù)值

lognnnlognn2n32°

0101..'-12

122484

248166416

382464512256

41664256409665536

532160102432768(4294967296).

2011-7-7

2)下界函數(shù)

定義1.2如果存在兩個正常數(shù)c和n0,對于所有的nNn0,

If(n)2c|g(n)

則記作f(n)。(g(n))

含義:

?如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的

時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)

的一個下界函數(shù)。

?試圖求出“最大”的g(n),使得f(n)=Q(g(n))o

2011-7-7

???

3)“平均情況”限界函數(shù)

???

???

定義1.3如果存在正常數(shù)”，和n0,對于所有的nNn0,有

ct|g(n)|<|f(n)|Cc2|g(n)

則記作

f(n)=?(g5))

含義：

?算法在最好和最壞情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言

是相同的?？煽醋鳎?/p>

既有f(n)=Q(g(n)),又有f(n)=O(g(n))

2011-7-7

4)限界函數(shù)的性質(zhì)

1)若/=o(g)且g=o=),則/=。(%)。即0具有傳

遞性。(Q、。同)

2)/=O(g)當(dāng)且僅當(dāng)g=Q(7)

3)若/=3(g)則g=0(/)o即，Q定乂了一*個等

價關(guān)系(等價類)

證明：

從定義出發(fā)。證明過程略。

2011-7-7

5.常用的整數(shù)求和公式

在算法分析中，在統(tǒng)計語句的頻率時，求和公

式的一般形式為：

如：

=€）（/+1）

\<i<n

2011-7-7

1.3關(guān)于SPARKS語言

?本書為描述算法選用的一種計算機語言

?類PASCAL語言

?結(jié)構(gòu)化設(shè)計

2011-7-7

1.基本語法成分2)變量聲明

類型說明符變量;

1）數(shù)據(jù)類型

integeri,j;

整型integer

booleanb;

實型float

charc

布爾型boolean

3)數(shù)組

字符型char

任意整數(shù)下標(biāo)

integerA(1:5,7:20)

integerB(5,7:20)

2011-7-7

4）賦值運算

（變量）-（表達式）

x—2+x;

5）邏輯運算：andornot

6）關(guān)系運算：<<=#>>

2011-7-7

7）控制結(jié)構(gòu):

順序：（略）

分支：循環(huán)：

?ifconditionthenS1?whileconddo

elseS2S

endif

repeat

?case

?loop

:cond1:S1;

:cond2:S2;S

untilcondrepeat

:condn:Sn?forvble<—starttofinishby

:else:Sn+1incrementdo

endcaseS

repeat

2011-7-7

8）函數(shù)的定義與調(diào)用

過程定義

procedureNAME（（參數(shù)表））

（說明部分）

S

endNAME

過程的調(diào)用：CALL過程名

函數(shù)定義

類型名procedureNAME（（參數(shù)表））

（說明部分）

S

return（表達式）

endNAME

函數(shù)的引川：X-function（參數(shù)）；

2011-7-7

9）變量的分類

a）根據(jù)數(shù)據(jù)類型分類

整型、實型、字符型等

b）根據(jù)作用域分類：

全程變量、局部變量、形式參數(shù)

c）根據(jù)是否帶入、帶出數(shù)據(jù)值/結(jié)果分類：

in型變量

out型變量

inout型變量

邊界效應(yīng)：改變了參變量或全程變量的值

函數(shù)：通過函數(shù)值返回輸出結(jié)果，沒有邊界效應(yīng)

純過程：沒有函數(shù)值返回，只通過邊界效應(yīng)帶出輸出結(jié)果

2011-7-7

10）特殊語句

a）exit

退出當(dāng)前一層的循環(huán)

b）return

退出過程

return（表達式）：函數(shù)返回結(jié)果

c）goto無條件轉(zhuǎn)向語句

gotolabel

11）遞歸

a）直接遞歸：過程中包含對自身的調(diào)用

b）間接遞歸：間接調(diào)用自身

12）輸入輸出

read>print

13）注釋

〃注釋//

2011-7-7

1.4基本數(shù)據(jù)結(jié)構(gòu)

1.棧和隊列

?線性表：n個元素的有序表

?棧和隊列：特殊的線性表

?利用動態(tài)數(shù)據(jù)結(jié)構(gòu)—鏈表實現(xiàn)?；蜿犃?/p>

?利用靜態(tài)數(shù)據(jù)結(jié)構(gòu)—數(shù)組實現(xiàn)棧或隊列

?基于以上兩種表示形式的棧和隊列上的基本運算

2011-7-7

圖L10含有元素工」2，八」且容量為n的環(huán)形隊列

2.樹

定義1.4樹(tree)是一個或多個結(jié)點的有限集合，它使K：

?有一個指定為根(root)的結(jié)點

?剩余結(jié)點被劃分成mNO個不相交的集合：

這些集合的每一個又都是一棵樹，并稱L，…，*為根的子樹。

2011-7-7

關(guān)于樹的重要概念

?結(jié)點的度（degree）：一個結(jié)點的子樹數(shù)

?樹的度：樹中結(jié)點度的最大值

?結(jié)點的級（level）（又叫層）：設(shè)根是1級，若某結(jié)點在p級,

則它的兒子在P+1級

?樹的高度（或深度）：樹中結(jié)點的最大級數(shù)

?葉子（終端結(jié)點）：度為0的結(jié)點

?內(nèi)結(jié)點（非終端結(jié)點）：度不為0的結(jié)點

?森林：m2。個不相交樹的集合。

2011-7-7

3二元樹：：

定義1.5二元樹(binarytree)是結(jié)點的有限集合，它或者為

空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所

組成。

?二元樹與度為2的樹的區(qū)別

?二元樹性質(zhì)：

引理1.1一棵二元樹第i級的最大結(jié)點數(shù)是2"。深度為k的二元

樹的最大結(jié)點數(shù)為2匕1,k>0。

2011-7-7

圖1.14兩棵特殊的二元樹

2011-7-7

?特殊形態(tài)的二元樹

①滿二元樹：深度為k且有2匕1個結(jié)點的二元樹

2011-7-7

②完全二元樹：一棵有n個結(jié)點深度為k的二元樹，當(dāng)它的

結(jié)點相當(dāng)于深度為k的滿二元樹中編號為1到

n的結(jié)點時，稱該二元樹是完全的。

＞完全二元樹的葉子結(jié)點至多出現(xiàn)在相鄰的兩級上。

＞完全二元樹的結(jié)點可以緊湊地存放在一個一維數(shù)組中（性質(zhì)見

引理1.2）。

2011-7-7

③堆：堆是一棵完全二元樹，它的每個結(jié)點的值至少和

該結(jié)點的兒子們（如果存在的話）的值一樣大

（max-堆）（或小，min一堆）。

④二分檢索樹：二分檢索樹T是一棵二元樹，它或者為空,

或者每個結(jié)點含有一個可以比較大小的數(shù)據(jù)元素，且

有：

?T的左子樹的所有元素比根結(jié)點中的元素?。?/p>

?T的右子樹的所有元素比根結(jié)點中的元素大；

?T的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中所有結(jié)點的元素值互異

2011-7-7

3.圖

圖G由稱之為結(jié)點V和邊E的兩個集合組成，記為

G=(V,E)

其中，V是一個有限非空的結(jié)點集合；E是結(jié)點對偶的

集合，E的每一對偶表示G的一條邊。

2011-7-7

有關(guān)圖的的重要概念

?無向圖：邊表示為（i,j）

?有向圖：邊表示為〈i,j〉

?成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）

?鄰接

?結(jié)點的度（出度/入度）

?路徑：由結(jié)點v到v的一條路（path）是結(jié)點

Vp,4,vj2,...,vim,Vq的一個序列，它使得

（Vp，Mi），（VM,Vj2），…，（Vjm,vq）

是E（G）的邊。

?路的長度：組成路的邊數(shù)。

2011-7-7

?簡單路徑：除了第一和最后一個結(jié)點可以相同以外，其它?

所有結(jié)點都不同。：

?環(huán)：第一個和最后一個結(jié)點相同的簡單路。

?連通圖：在無向圖中，如果每對結(jié)點之間都存在一條路徑，則

稱該圖是連通的。

?子圖：是由G的結(jié)點集V的子集（記為VB）和邊集E中連接VB

中結(jié)點的邊的子集所組成的圖。

?連通分圖：一個圖的最大連通子圖。

?有向圖的強連通性：在有向圖中，如果對于每一對結(jié)點i和j,

既存在一條從i到j(luò)的路，又存在一條從j

到i的路，則稱該有向圖是強連通的。

2011-7-7

???

圖的表示方法

(a)

圖1.26兩個實例圖

?鄰接矩陣鄰接表

X1.4BU27的鄰接矩陣

1234512345

⑴「01110'■01110-

(2)0010010100

(3)0000011000

(4)0000110001

(b)

⑸L00000.-00010-

圖1?27圖1.26的鄰接表

2011-7-7

1.5遞歸和消去遞歸

1.遞歸

?遞歸是一種強有力的設(shè)計方法

?遞歸的效率問題

2011-7-7

例1.3斐波那契(Fibonacci)序列：

F。=F1二1

F產(chǎn)Fg+F'2(>1)

算法1.7求斐波那契數(shù)

procedureF(n)

〃返回第n個斐波那契數(shù)〃

integern

ifn<=1thenreturn(1)

elsereturn(F(n-1)+F(n-2))

endif

endF

?算法效率：對F(n-1)、F(n-2)存在大量的重復(fù)計算

?改進：保存中間結(jié)果

2011-7-7

例1.4歐幾里得算法

已知兩個非負整數(shù)a和b,且a〉bNO,求這兩個數(shù)的

最大公因數(shù)。

輾轉(zhuǎn)相除法：若b=0,則a和b的最大公因數(shù)等于a；若b>0,

則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。

算法1.8求最大公因數(shù)

procedureGCD(a,b)//約定a>b//

ifb=0thenreturn(a)

elsereturn(GCD(b,amodb))

endif

endGDC

例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;

2011-7-7

例1.5用遞歸策略設(shè)計的檢索算法

已知元素x和元素表A(1：n),判斷x是否等于A中

某元素的值。

算法1.9在A(1：n)中檢索x

procedureSEARCH(i)

〃如果在A(1：n)〃中有一元素A(k二x,則將其第一次出現(xiàn)的下標(biāo)k返回,

否則返回0〃

globaln,x,A(1:n)

case

:i>n:return(O)

:A(i)=x;return(i)

:else:return(SEARCH(i+1))

endcase

endSEARCH

2011-7-7

2.消去遞歸：：

??

直接遞歸的消去規(guī)則：

基本思路：將遞歸調(diào)用的地方用等價的非遞歸代碼來代替，并

對return語句做適當(dāng)處理。

13條規(guī)則：處理直接遞歸調(diào)用和return語句，將之轉(zhuǎn)換成等價

的迭代代碼。

?初始化

⑴在過程的開始部分，插入說明為棧的代碼并將其初始化為

空。在一般情況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、

每次遞歸調(diào)用的返回地址。

⑵將標(biāo)號L附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)

用都用一組執(zhí)行下列規(guī)則的指令來代替。

2011-7-7

?處理遞歸調(diào)用語句

⑶將所有參數(shù)和局部變量的值存入棧。

棧頂指針可作為一個全程變量來看待。

(4)建立第i個新標(biāo)號j,并將i存入棧。這個標(biāo)號的i值將用來

計算返回地址。

此標(biāo)號放在規(guī)則⑺所描述的程序段中。

⑸計算這次調(diào)用的各實在參數(shù)(可能是表達式)的值，并把這

些值賦給相應(yīng)的形式參數(shù)。

(6)插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分：

gotoI

2011-7-7

?對退出一層遞歸調(diào)用后的處理

⑺如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用

的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂

取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄,

并將⑷中建立的標(biāo)號附于這條語句上。

如果此過程不是函數(shù)，則將⑷中建立的標(biāo)號附于⑹所產(chǎn)生的

轉(zhuǎn)移語句后面的那條語句。

以上步驟消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return

語句進行處理。

（純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）

2011-7-7

?對每個有return語句的地方，執(zhí)行下述規(guī)則：

(8)如果棧為空，則執(zhí)行正常返回。

⑼否則，將所有輸出參數(shù)(帶有返回值的出口參數(shù)，out/

inout型)的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。