算法-第一章-導引與基本數(shù)據(jù)結構

計算機算法基礎

1教材計算機算法基礎（第二版）余祥宣等華中科技大學出版社參考書：1.計算機算法設計與分析：王曉東，電子工業(yè)出版社2.算法分析與設計：（美）古德里奇，（美）塔瑪西亞，霍紅衛(wèi)譯人民郵電出版社課時安排：28+12考試形式：閉卷成績：平時50%+考試50%2序計算機算法是計算機科學和計算機應用的核心數(shù)據(jù)結構+算法=程序算法（algorithm）是一個在有限時間內逐步執(zhí)行某種任務的過程數(shù)據(jù)結構（datastructure）是一種系統(tǒng)組織和訪問數(shù)據(jù)的方法算法：計算機軟件的靈魂3問題求解(ProblemSolving)設計程序證明正確性分析算法理解問題精確解或近似解選擇數(shù)據(jù)結構算法設計策略設計算法4章節(jié)安排第一章導引與基本數(shù)據(jù)結構 √第二章分治法 √第三章貪心方法 √第四章動態(tài)規(guī)劃 √第五章檢索與周游 √第六章回溯法 ⊙第七章分枝-限界 ⊙第八章NP-問題

?算法研討環(huán)節(jié)

5第一章導引與基本數(shù)據(jù)結構1.1算法的定義及特性1.什么是算法？

算法如數(shù)字、計算一樣，是一個基本概念。算法是解一類確定問題的任意一種特殊的方法。在計算機科學中，算法是使用計算機解一類問題的精確、有效方法的代名詞：

算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。62.算法的五個重要特性

確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運算必須要有確切的定義，不能有二義性。例：不符合確定性的運算

5/0

將6或7與x相加未賦值變量參與運算72）能行性算法中有待實現(xiàn)的運算都是基本的運算，原理上每種運算都能由人用紙和筆在有限的時間內完成。例：整數(shù)的算術運算是“能行”的實數(shù)(無理數(shù))的算術運算是“不能行”的83）輸入每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域（或值域）4）輸出一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關系的量。95）有窮性

一個算法總是在執(zhí)行了有窮步的運算之后終止。計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不一定能終止的一組規(guī)則。準確理解算法和計算過程的區(qū)別：不能終止的計算過程：操作系統(tǒng)。算法是“可以終止的計算過程”。算法的時效性：只能把在相當有窮步內終止的算法投入到計算機上運行。104.我們的主要任務算法學習將涉及5個方面的內容：

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

2）表示算法：思想的表示形式

3）確認算法：證明算法的正確性程序的證明（程序的形式化證明技術）

4）分析算法：算法時空特性分析

5）測試程序：“調試只能指出有錯誤，而不能指出它們不存在錯誤”

本課程集中于學習算法的設計與分析。通過學習，掌握計算機算法設計和分析基本策略與方法，為設計更復雜、更有效的算法奠定基礎。115.課程關系數(shù)據(jù)結構程序設計語言：結構化設計數(shù)學基礎非數(shù)值計算領域的基本知識121.2分析算法1.分析算法的目的在于：通過對算法的分析，在把算法變成程序實際運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。算法分析是計算機領域的古老而前沿的課題。

進行算法分析的基本技術：抽象132.重要的假設和約定1）計算機模型的假設

Turing機模型：計算機形式理論模型通用計算機模型：順序計算機有足夠的“內存”能在固定的時間內存取數(shù)據(jù)單元

142）計算的約定

算法的執(zhí)行時間=∑Fi*ti

其中，F(xiàn)i是算法中用到的某種運算i的次數(shù)，ti是該運算執(zhí)行一次所用的時間。確定使用什么樣的運算及其執(zhí)行時間。從計算時間上，運算的分類：

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

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

·字符運算

·賦值運算

·過程調用等特點：盡管每種運算的執(zhí)行時間不同，但一般只花一個固定量的時間（單位時間）就可完成。152）計算的約定（續(xù)）

其他運算：

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

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

·

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

如：Tstring=Length（String）*tchar163）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運行算法，以了解算法的性能。測試數(shù)據(jù)集的生成在目前算法證明與程序正確性證明沒有取得理論上的突破性進展的情況下，是程序測試與算法分析中的關鍵技術之一。

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

·作為程序性能測試的數(shù)據(jù)集：對執(zhí)行指標產(chǎn)生影響的性質173.如何進行算法分析？對算法進行全面分析，可分兩個階段進行：事前分析：就算法本身，通過對其執(zhí)行性能的理論分析，得出關于算法特性——時間和空間的一個特征函數(shù)（Ο、Ω）——與計算機物理軟硬件沒有直接關系。事后測試：將算法編制成程序后實際放到計算機上運行，收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行分析判斷——直接與物理實現(xiàn)有關。181）事前分析目的：試圖得出關于算法執(zhí)行特性的一種形式描述，以“理論上”衡量算法的“好壞”。如何給出反映算法執(zhí)行特性的描述？最直接方法：統(tǒng)計算法中各種運算的執(zhí)行情況，包括：引用了哪些運算每種運算被執(zhí)行的次數(shù)該種運算執(zhí)行一次所花費的時間等。

算法的執(zhí)行時間=∑Fi*ti19頻率計數(shù)

例：

x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)

分析：

(a)：x←x+y執(zhí)行了1次

(b)：x←x+y執(zhí)行了n次

(c)：x←x+y執(zhí)行了n2次定義：

頻率計數(shù)：一條語句或一種運算在算法（或程序）體中的執(zhí)行次數(shù)。20一條語句在整個程序運行時實際執(zhí)行時間=

頻率計數(shù)*每執(zhí)行一次該語句所需的時間如何刻畫算法執(zhí)行特性的形式描述實際執(zhí)行時間受約于諸多實際因素，如機器類型、編程與語言、操作系統(tǒng)等，沒有統(tǒng)一的描述模型。在事前分析中，只限于確定與所使用的機器及其他環(huán)境因素無關的頻率計數(shù)，依此建立理論分析模型。21數(shù)量級

語句的數(shù)量級：語句的執(zhí)行頻率例：1，n，n2

算法的數(shù)量級：算法所包含的所有語句的執(zhí)行頻率之和。算法的數(shù)量級從本質上反映了一個算法的執(zhí)行特性。例：假如求解同一個問題的三個算法分別具有n，n2

，n3數(shù)量級。若n=10，則可能的執(zhí)行時間將分別是10，100，1000個單位時間——與環(huán)境因素無關。22

計算時間/頻率計數(shù)的表示函數(shù)通過事前分析給出算法計算時間（頻率計數(shù)）的一個函數(shù)表示形式，一般記為與輸入規(guī)模n有關的函數(shù)形式：f(n)注：最高次項與函數(shù)整體的關系空間特性分析（略）232）事后測試目的：運行程序，確定程序實際耗費的時間與空間，驗證先前的分析結論——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設計的算法。分析手段：作時、空性能分布圖244.計算時間的漸近表示記：算法的計算時間為f(n)

數(shù)量級限界函數(shù)為g(n)其中，

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

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

g(n)是形式簡單的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過對計算時間或頻率計數(shù)統(tǒng)計分析所得的、與機器及語言無關的函數(shù)。

以下給出算法執(zhí)行時間：上界（О）、下界（Ω）、“平均”（）的定義。251）上界函數(shù)定義1如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，有

|f(n)|≤c|g(n)|

則記作f(n)=Ο(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個上界函數(shù)。f(n)的數(shù)量級就是g(n)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。

26F(n)=3n+2

可取c＝4，n0＝2，O(n)F(n)=100n+6

可取c=101，n0＝6，O(n)F(n)=2n2+11n-10

可取c=3，n0＝10，O(n2)F(n)=6×2n+n2

可取c=7，n0=4，O(2n)27多項式定理:定理1若A(n)=amnm+…+a1n+a0是一個m次多項式，則有A(n)=Ο(nm)

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

證明：取n0=1,當n≥n0時，有

|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

≤(|am|+|am-1|+…+|a0|)nm

令c=|am|+|am-1|+…+|a0|

則，定理得證。28

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

例：假設解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數(shù)量級分別是n2和nlogn。則，

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

n=2048：分別需要4194304和22528次運算。分析：在n加倍的情況下，一個Ο(n2)的算法計算時間增長4倍，而一個Ο(nlogn)算法則只用2倍多一點的時間即可完成。29

算法分類（計算時間）多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。常見的多項式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法常見的指數(shù)時間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)說明：當n取值較大時，指數(shù)時間算法和多項式時間算法在計算時間上非常懸殊。30典型的計算時間函數(shù)曲線31當數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計算機系統(tǒng)上運行具有比Ο(nlogn)復雜度還高的算法是比較困難的。指數(shù)時間算法只有在n取值非常小時才實用。要想在順序處理機上擴大所處理問題的規(guī)模，有效的途徑是降低算法的計算復雜度，而不是（僅僅依靠）提高計算機的速度。32計算時間函數(shù)值比較33定義1.2如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，

有

|f(n)|≥c|g(n)|

則記作f(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個下界函數(shù)。試圖求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函數(shù)34定義1.3如果存在正常數(shù)c1，c2和n0，對于所有的n≥n0，有

c1|g(n)|≤|f(n)|≤c2|g(n)|

則記作含義：算法在最好和最壞情況下的計算時間就一個常數(shù)因子范圍內而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))3）“平均情況”限界函數(shù)35漸近分析記號的若干性質（1）傳遞性：f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=O(g(n))，g(n)=O(h(n))

f(n)=O(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；（2）對稱性：f(n)=

(g(n))

g(n)=

(f(n)).（3）互對稱性：f(n)=O(g(n))

g(n)=

(f(n))；36根據(jù)上述定義，下面的結論對于后面的分析是有用的。①若f(n)=O(g(n))且g(n)=O(h(n))，則f(n)=O(h(n))。②若f(n)=O(Kg(n))，其中K為任意大于0的常數(shù)，則f(n)=O(g(n))。③若f1(n)=O(g1(n))且f2(n)=O(g2(n))，則f1(n)+f2(n)=O(max(g1(n)，g2(n)))④若f1(n)=O(g1(n))且f2(n)=O(g2(n))，則f1(n)*f2(n)=O(g1(n)*g2(n))37規(guī)則O(f(n))+O(g(n))=

O(max{f(n),g(n)})的證明：對于任意f1(n)

O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)

O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有n

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，

h(n)=max{f(n),g(n)}。則對所有的n

n3，有

f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)})

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

在算法分析中，在統(tǒng)計語句的頻率時，求和公式的一般表示形式為：如：39練習1.求下列函數(shù)的上界表達式402.（1）假設某算法在輸入規(guī)模為n時的計算時間為T(n)=2n。在某臺計算機上實現(xiàn)并完成該算法的時間為t秒?，F(xiàn)有另一臺計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒內能解輸入規(guī)模為多大的問題？（2）若上述算法的計算時間改進為T(n)=n2，其余條件不變，則在新機器上用t秒時間能解輸入規(guī)模為多大的問題？（3）若上述算法的計算時間改進為T(n)=n，其余條件不變，則在新機器上用t秒時間能解輸入規(guī)模為多大的問題？41解：(1)設新機器用同一算法在t秒內能解輸入規(guī)模為n1的問題。因此有：

2n1=

64*2n

，解得n1=n+6(2)n12=64n2，解得n1=8n(3)n1=64n結論：降低算法復雜度是提高計算效率的關鍵！421.3關于SPARKS語言本書為描述算法選用的一種類計算機語言類PASCAL語言結構化程序描述431.基本語法成分1）數(shù)據(jù)類型：整型、實型、布爾型、字符型2）變量聲明：類型說明符變量；

integeri,j;booleanb;charc3）賦值運算：（變量）←（表達式）4）邏輯運算：andornot5）關系運算：＜≤＝≠≥＞6）數(shù)組聲明：integerA（1：5，7：20）448）控制結構：

順序:

分支:

·ifconditionthenS1elseS2

endif

·case:cond1:S1;:cond2:S2;…:condn:Sn:else:Sn+1

endcase循環(huán):

·whileconddoSrepeat

·loopSuntilcondrepeat

·forvble←starttofinishbyincrementdoSrepeat

2.同質異項3.其它

函數(shù)的定義與調用、函數(shù)和過程、變量與形式參數(shù)451.4基本數(shù)據(jù)結構1.棧和隊列棧和隊列：n個元素的線性表利用動態(tài)數(shù)據(jù)結構——鏈表實現(xiàn)棧或隊列利用靜態(tài)數(shù)據(jù)結構——數(shù)組實現(xiàn)?；蜿犃谢谝陨蟽煞N表示形式的棧和隊列上的基本運算462.樹1）樹的一般定義定義1.4樹（tree）是一個或多個結點的有限集合，它使得：有一個指定為根（root）的結點剩余結點被劃分成m≥0個不相交的集合：

T1，…，Tm

這些集合的每一個又都是一棵樹，并稱T1，…，Tm為根的子樹。47關于樹的重要概念結點的度（degree）：一個結點的子樹數(shù)樹的度：樹中結點度的最大值結點的級（level）（又叫層）：設根是1級，若某結點在p級，則它的兒子在p+1級樹的高度（或深度）：樹中結點的最大級數(shù)葉子（終端結點）：度為0的結點內結點（非終端結點）：度不為0的結點森林：m≥0個不相交樹的集合。482）二元樹定義1.5二元樹（binarytree）是結點的有限集合，它或者為空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。二元樹與度為2的樹的區(qū)別二元樹性質1：

引理1.1

一棵二元樹第i級的最大結點數(shù)是2i-1。深度為k的二元樹的最大結點數(shù)為2k-1,k>0。

4950

特殊形態(tài)的二元樹①滿二元樹：深度為k且有2k-1個結點的二元樹

51②完全二元樹：一棵有n個結點深度為k的二元樹，當它的結點相當于深度為k的滿二元樹中編號為1到n的結點時，稱該二元樹是完全的。完全二元樹的葉子結點至多出現(xiàn)在相鄰的兩級上。完全二元樹的結點可以緊湊地存放在一個一維數(shù)組中（性質見引理1.2）。52

③堆：堆是一棵完全二元樹，它的每個結點的值至少和（大于或等于）該結點的兒子們（如果存在的話）的值一樣大（max-堆）（或小，

min-堆）。

④

二分檢索樹：二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個結點含有一個可以比較大小的數(shù)據(jù)元素，且有：

·Ｔ的左子樹的所有元素比根結點中的元素?。?/p>

·Ｔ的右子樹的所有元素比根結點中的元素大；

·Ｔ的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中所有結點的元素值互異533.圖

圖Ｇ由稱之為結點Ｖ和邊Ｅ的兩個集合組成，記為G=（V，E）。其中，Ｖ是一個有限非空的結點集合；Ｅ是結點對偶的集合，Ｅ的每一對偶表示Ｇ的一條邊。54有關圖的的重要概念無向圖：邊的表示（ｉ，ｊ）有向圖：邊的表示〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡鄰接：如果存在邊（i，j）則稱結點i和j鄰接結點的度（出度／入度）路徑：由結點vp到vq的一條路（path）是結點

vp

，

vi1，

vi2，

…，

vim，

vq的一個序列，它使得(vp

，

vi1)

，(vi1

，vi2)

，

…，

(

vim，

vq)是E（G）的邊。路的長度：組成路的邊數(shù)。55簡單路徑：除了第一和最后一個結點可以相同以外，其它所有結點都不同。環(huán)：第一個和最后一個結點相同的簡單路。連通圖：在無向圖中，如果每對結點之間都存在一條路，則稱該圖是連通的。子圖：是由G的結點集V的子集（記為VB）和邊集E

中連接VB中結點的邊的子集所組成的圖。連通分圖：一個圖的最大連通子圖。有向圖的強連通性：在有向圖中，如果對于每一對結點i和j，既存在一條從i到j的路，又存在一條從j

到i的路，則稱該有向圖是強連通的。56圖的表示方法鄰接矩陣鄰接表571.5遞歸和消去遞歸遞歸

一個算法若其中有調用自身的過程，則稱該算法是一個遞歸算法。遞歸是一種強有力的設計方法遞歸的效率問題58

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

F0=F1=1

Fi=Fi-1+Fi-2

（i>1)

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

procedureF(n)//返回第n個斐波那契數(shù)//integernifn<=1thenreturn(1)elsereturn(F(n-1)+F(n-2))

endifendF算法效率：對F(n-1)、F(n-2)存在大量的重復計算改進：保存中間結果59練習題18ProcedureF1(n)Ifn<2thenreturn(1)Elsereturn(F2(2,n,1,1))

EndifEndF1ProcedureF2(i,n,x,y)Ifi<=nThencallF2(i+1,n,y,x+y)

Endif

Return(y)EndF260練習17題假設t(n)是所給出的F(n)的時間函數(shù)，證明t(n)=O(2n-2)61練習18題以下是計算第n個斐波那契數(shù)的函數(shù)ProcedureF1(n)If(n<2)thenreturn(1)Elsereturn(F2(2,n,1,1))

EndifEndf1ProcedureF2(i,n,x,y)ifi≤nthencallF2(i+1,n,y,x+y)

endif

return(y)EndF262例1.4歐幾里得算法

已知兩個非負整數(shù)a和b，且a＞b≥0，求這兩個數(shù)的最大公因數(shù)。輾轉相除法：若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))

endifendGCD

例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;63例1.5遞歸在非數(shù)值算法設計中的應用已知元素x，判斷x是否在A（1：n）中。算法1.9在A（1：n）中檢索xprocedureSEARCH(i)//如果在A（1：n）//中有一元素A（k）=x，則將其第一次出現(xiàn)的下標k返回，否則返回0//globaln,x,A(1:n)case:i>n:return(0):A(i)=x;return(i):else:return(SEARCH(i+1))

endcaseendSEARCH第一次調用ans<-SEARCH(1)642.消去遞歸直接遞歸的消去規(guī)則：

基本思路：將遞歸過程中出現(xiàn)遞歸調用的地方，用等價的非遞歸代碼來代替，并對return語句做適當處理。

13條規(guī)則：處理直接遞歸調用中的遞歸代碼和return語句，將之轉換成等價的迭代代碼。

初始化

⑴在過程的開始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調用的返回地址。⑵將標號L1附于第一條可執(zhí)行語句。然后對于每一處遞歸調用都用一組執(zhí)行下列規(guī)則的指令來代替。65

處理遞歸調用語句⑶將所有參數(shù)和局部變量的值存入棧。

棧頂指針可作為一個全程變量來看待。⑷建立第i個新標號Li，并將i存入棧。這個標號的i值將用來計算返回地址。此標號放在規(guī)則⑺所描述的程序段中。⑸計算這次調用的各實在參數(shù)（可能是表達式）的值，并把這些值賦給相應的形式參數(shù)。⑹插入一條無條件轉向語句轉向過程的開始部分：

GotoL166

對遞歸嵌套調用的處理⑺如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調用的那條語句做如下處理：將該語句的此次函數(shù)調用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的標號附于這條語句上。如果此過程不是函數(shù)，則將⑷中建立的標號附于⑹所產(chǎn)生的轉移語句后面的那條語句。以上步驟實現(xiàn)消去過程中的遞歸調用。下面對過程中出現(xiàn)return語句進行處理（純過程結束處的end可看成是一條沒有值與之聯(lián)系的return語句）。67

對每個有return語句的地方，執(zhí)行下述規(guī)則：⑻如果棧為空，則執(zhí)行正常返回。⑼否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/inout型）的當前值賦給棧頂上的那些對應的變量。⑽如果棧中有返回地址標號的下標，就插入一條此下標從棧中退出的代碼，并把這個下標賦給一個未使用的變量。⑾從棧中退出所有局部變量和參數(shù)的值并把它們賦給對應的變量。⑿如果這個過程是函數(shù)，則插入以下指令，這些指令用來計算緊接在return后面的表達式并將結果值存入棧頂。⒀用返回地址標號的下標實現(xiàn)對該標號的轉向。68例1.6遞歸調用示例求數(shù)組元素中的最大值算法1.10遞歸求取數(shù)組元素的最大值

procedureMAX1(i)//查找數(shù)組A中最大值元素，并返回該元素的最大下標。//globalintegern,A(1:n),j,kintegeriifi<nthenj←MAX1(i+1)//遞歸調用//ifA(i)>A(j)thenk←ielsek←j

endifelsek←n

endif

return(k)//遞歸調用的返回//endMAX169消去上例中的遞歸算法1.11使用上述的規(guī)則消去例1.10中的遞歸代碼

procedureMAX2(i)localintegerj,k;globalintegern,A(1:n)integerIintegerSTACK(1:2*