導(dǎo)引和基本數(shù)據(jù)結(jié)構(gòu)

1、關(guān)于導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1第一張，PPT共七十四頁，創(chuàng)作于2022年6月2教材計(jì)算機(jī)算法基礎(chǔ)（第二版）余祥宣等 華中科技大學(xué)出版社參考書：1.計(jì)算機(jī)算法設(shè)計(jì)與分析：王曉東，電子工業(yè)出版社2.算法分析與設(shè)計(jì) ：（美）古德里奇，（美）塔瑪西亞，霍紅衛(wèi)譯 人民郵電出版社 課時(shí)安排：28+12考試形式：閉卷成績： 平時(shí)50%+考試50%第二張，PPT共七十四頁，創(chuàng)作于2022年6月3序計(jì)算機(jī)算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心數(shù)據(jù)結(jié)構(gòu)+算法 = 程序算法（algorithm）是一個(gè)在有限時(shí)間內(nèi)逐步執(zhí)行某種任務(wù)的過程數(shù)據(jù)結(jié)構(gòu)（data structure）是一種系統(tǒng)組織和訪問數(shù)據(jù)的方法算法：計(jì)算機(jī)軟件的靈魂

2、第三張，PPT共七十四頁，創(chuàng)作于2022年6月4問題求解(Problem Solving)設(shè)計(jì)程序證明正確性分析算法理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法第四張，PPT共七十四頁，創(chuàng)作于2022年6月5章節(jié)安排第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu) 第二章 分治法 第三章 貪心方法 第四章 動(dòng)態(tài)規(guī)劃 第五章 檢索與周游第六章 回溯法第七章 分枝-限界第八章 NP-問題?算法研討環(huán)節(jié) 第五張，PPT共七十四頁，創(chuàng)作于2022年6月6第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1 算法的定義及特性1. 什么是算法？ 算法如數(shù)字、計(jì)算一樣，是一個(gè)基本概念。 算法是解一類確定問題的任意一種特殊的方法。 在計(jì)算機(jī)

3、科學(xué)中，算法是使用計(jì)算機(jī)解一類問題的精確、有效方法的代名詞： 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算。第六張，PPT共七十四頁，創(chuàng)作于2022年6月72.算法的五個(gè)重要特性 確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算 5/0 將6或7與x相加 未賦值變量參與運(yùn)算第七張，PPT共七十四頁，創(chuàng)作于2022年6月82）能行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在有限的時(shí)間內(nèi)完成。例：整數(shù)的算術(shù)運(yùn)算是“能行”的 實(shí)數(shù)(無理數(shù))的算術(shù)運(yùn)算是“不能行”的第八張，PPT共七十四

4、頁，創(chuàng)作于2022年6月93）輸入 每個(gè)算法有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合定義域（或值域）4）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。第九張，PPT共七十四頁，創(chuàng)作于2022年6月105）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。計(jì)算過程：只滿足確定性、能行性、輸入、輸出四個(gè)特性但不一定能終止的一組規(guī)則。 準(zhǔn)確理解算法和計(jì)算過程的區(qū)別： 不能終止的計(jì)算過程：操作系統(tǒng)。 算法是“可以終止的計(jì)算過程”。 算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計(jì)算機(jī)上運(yùn)行。第十張，PPT共七十四頁，創(chuàng)作于2022年6月114

5、. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng) 2）表示算法：思想的表示形式 3）確認(rèn)算法：證明算法的正確性 程序的證明（程序的形式化證明技術(shù)） 4）分析算法：算法時(shí)空特性分析 5）測試程序：“調(diào)試只能指出有錯(cuò)誤，而不能指出它們 不存在錯(cuò)誤” 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)。第十一張，PPT共七十四頁，創(chuàng)作于2022年6月125. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)語言：結(jié)構(gòu)化設(shè)計(jì) 數(shù)學(xué)基礎(chǔ) 非數(shù)值計(jì)算領(lǐng)域的基本知識(shí)第十二張，PPT共七十四頁，創(chuàng)作于2022年6月131.2 分析算

6、法1. 分析算法的目的 在于：通過對(duì)算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無益的人力和物力浪費(fèi)。 算法分析是計(jì)算機(jī)領(lǐng)域的古老而前沿的課題。 進(jìn)行算法分析的基本技術(shù)：抽象第十三張，PPT共七十四頁，創(chuàng)作于2022年6月142. 重要的假設(shè)和約定1）計(jì)算機(jī)模型的假設(shè) Turing機(jī)模型：計(jì)算機(jī)形式理論模型 通用計(jì)算機(jī)模型： 順序計(jì)算機(jī) 有足夠的“內(nèi)存” 能在固定的時(shí)間內(nèi)存取數(shù)據(jù)單元 第十四張，PPT共七十四頁，創(chuàng)作于2022年6月152）計(jì)算的約定 算法的執(zhí)行時(shí)間=Fi*ti 其中，F(xiàn)i是算法中用到的某種運(yùn)算i的次數(shù)，

7、ti是該運(yùn)算執(zhí)行一次所用的時(shí)間。 確定使用什么樣的運(yùn)算及其執(zhí)行時(shí)間。從計(jì)算時(shí)間上，運(yùn)算的分類： 時(shí)間囿界于常數(shù)的運(yùn)算： 基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除 字符運(yùn)算 賦值運(yùn)算 過程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算的執(zhí)行時(shí)間不同，但一般只花 一個(gè)固定量的時(shí)間（單位時(shí)間）就可完成。第十五張，PPT共七十四頁，創(chuàng)作于2022年6月162）計(jì)算的約定（續(xù)） 其他運(yùn)算： 字符串操作：與字符串中字符的數(shù)量成正比 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特點(diǎn)：運(yùn)算時(shí)間無定量 如何分析非時(shí)間囿界于常數(shù)的運(yùn)算：分解成若干時(shí)間囿界于常數(shù)的運(yùn)算。 如：Tstring = Length（String）* tch

8、ar第十六張，PPT共七十四頁，創(chuàng)作于2022年6月173）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性能。測試數(shù)據(jù)集的生成在目前算法證明與程序正確性證明沒有取得理論上的突破性進(jìn)展的情況下，是程序測試與算法分析中的關(guān)鍵技術(shù)之一。 作為算法分析的數(shù)據(jù)集：典型特征 作為程序性能測試的數(shù)據(jù)集：對(duì)執(zhí)行指標(biāo)產(chǎn)生影響的性質(zhì)第十七張，PPT共七十四頁，創(chuàng)作于2022年6月183. 如何進(jìn)行算法分析？ 對(duì)算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行：事前分析：就算法本身，通過對(duì)其執(zhí)行性能的理論分析， 得出關(guān)于算法特性時(shí)間和空間的一個(gè)特征 函數(shù)（、）

9、與計(jì)算機(jī)物理軟硬件沒有 直接關(guān)系。事后測試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行， 收集其執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，進(jìn)行 分析判斷直接與物理實(shí)現(xiàn)有關(guān)。第十八張，PPT共七十四頁，創(chuàng)作于2022年6月191）事前分析目的：試圖得出關(guān)于算法執(zhí)行特性的一種形式描 述，以“理論上”衡量算法的“好壞”。如何給出反映算法執(zhí)行特性的描述？ 最直接方法：統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括： 引用了哪些運(yùn)算 每種運(yùn)算被執(zhí)行的次數(shù) 該種運(yùn)算執(zhí)行一次所花費(fèi)的時(shí)間等。 算法的執(zhí)行時(shí)間=Fi*ti第十九張，PPT共七十四頁，創(chuàng)作于2022年6月20頻率計(jì)數(shù) 例： xx+y for i 1 to n do for

10、i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次 定義： 頻率計(jì)數(shù)：一條語句或一種運(yùn)算在算法（或程序）體中的執(zhí)行次數(shù)。第二十張，PPT共七十四頁，創(chuàng)作于2022年6月21一條語句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間= 頻率計(jì)數(shù) * 每執(zhí)行一次該語句所需的時(shí)間 如何刻畫算法執(zhí)行特性的形式描述實(shí)際執(zhí)行時(shí)間受約于諸多實(shí)際因素，如機(jī)器類型、編程與語言、操作系統(tǒng)等，沒有統(tǒng)一的描述模型。在事前分析中，只限于確定與所

11、使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立理論分析模型。第二十一張，PPT共七十四頁，創(chuàng)作于2022年6月22數(shù)量級(jí) 語句的數(shù)量級(jí)：語句的執(zhí)行頻率 例：1，n ，n2 算法的數(shù)量級(jí)：算法所包含的所有語句的執(zhí) 行頻率之和。算法的數(shù)量級(jí)從本質(zhì)上反映了一個(gè)算法的執(zhí)行特性。例：假如求解同一個(gè)問題的三個(gè)算法分別具有n， n2 ， n3數(shù) 量級(jí)。 若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè) 單位時(shí)間與環(huán)境因素?zé)o關(guān)。第二十二張，PPT共七十四頁，創(chuàng)作于2022年6月23 計(jì)算時(shí)間/頻率計(jì)數(shù)的表示函數(shù) 通過事前分析給出算法計(jì)算時(shí)間（頻率計(jì)數(shù)）的一個(gè)函數(shù)表示形式，一般記為與輸入規(guī)模n有關(guān)

12、的函數(shù)形式：f(n)注：最高次項(xiàng)與函數(shù)整體的關(guān)系空間特性分析（略） 第二十三張，PPT共七十四頁，創(chuàng)作于2022年6月242）事后測試目的：運(yùn)行程序，確定程序?qū)嶋H耗費(fèi)的時(shí)間與空間，驗(yàn)證先前的分析結(jié)論包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計(jì)的算法。分析手段：作時(shí)、空性能分布圖第二十四張，PPT共七十四頁，創(chuàng)作于2022年6月254. 計(jì)算時(shí)間的漸近表示記：算法的計(jì)算時(shí)間為f(n) 數(shù)量級(jí)限界函數(shù)為g(n)其中， n是輸入或輸出規(guī)模的某種測度。 f(n)表示算法的“實(shí)際”執(zhí)行時(shí)間與機(jī)器及語言有關(guān)。 g(n)是形式簡單的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過對(duì)計(jì)算時(shí)間或頻率計(jì)數(shù)統(tǒng)計(jì)分

13、析所得的、與機(jī)器及語言無關(guān)的函數(shù)。 以下給出算法執(zhí)行時(shí)間：上界（）、下界（）、“平均”（ ）的定義。第二十五張，PPT共七十四頁，創(chuàng)作于2022年6月261）上界函數(shù)定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)。 f(n)的數(shù)量級(jí)就是g(n)。試圖求出最小的g(n)，使得f(n) = (g(n)。 第二十六張，PPT共七十四頁，創(chuàng)作于2022年6月27F(n)=3n+2 可取c4

14、，n02，O(n)F(n)=100n+6 可取 c=101，n06，O(n)F(n)=2n2+11n-10 可取c=3， n010，O(n2)F(n)=62n+n2 可取c =7，n0=4 ，O(2n)第二十七張，PPT共七十四頁，創(chuàng)作于2022年6月28多項(xiàng)式定理:定理1 若A(n) = amnm+a1n+a0是一個(gè)m次多項(xiàng) 式，則有A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多 項(xiàng)式的最高階nm同階。 證明：取n0=1,當(dāng)nn0時(shí)，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|

15、) nm 令c= |am|+|am-1|+|a0| 則，定理得證。第二十八張，PPT共七十四頁，創(chuàng)作于2022年6月29 計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響 數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響。 例：假設(shè)解決同一個(gè)問題的兩個(gè)算法，它們都有n個(gè)輸入，計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和22528次運(yùn)算。 分析：在n加倍的情況下，一個(gè)(n2)的算法計(jì)算時(shí)間增長4倍，而一個(gè)(nlogn)算法則只用2倍多一點(diǎn)的時(shí)間即可完成。第二十九張，PPT共七十四頁，創(chuàng)作于2022年6月30 算法分類（計(jì)

16、算時(shí)間）多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。 常見的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時(shí)間限界函數(shù)： (2n) (n！) 0。 第四十九張，PPT共七十四頁，創(chuàng)作于2022年6月50第五十張，PPT共七十四頁，創(chuàng)作于2022年6月51 特殊形態(tài)的二元樹 滿二元樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二元樹 第五十一張，PPT共七十四頁，創(chuàng)作于2022年6月52 完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號(hào)為1到n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全

17、的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級(jí)上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見引理1.2）。第五十二張，PPT共七十四頁，創(chuàng)作于2022年6月53 堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和（大于或等于）該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大（ max-堆）（或小， min-堆）。二分檢索樹：二分檢索樹是一棵二元樹，它或者為空，或者其每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且有：的左子樹的所有元素比根結(jié)點(diǎn)中的元素?。坏挠易訕涞乃性乇雀Y(jié)點(diǎn)中的元素大；的左子樹和右子樹也是二分檢索樹。注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異第五十三張，PPT共七十四頁，創(chuàng)作

18、于2022年6月543. 圖 圖由稱之為結(jié)點(diǎn)和邊的兩個(gè)集合組成，記為G=（V，E）。其中，是一個(gè)有限非空的結(jié)點(diǎn)集合；是結(jié)點(diǎn)對(duì)偶的集合，的每一對(duì)偶表示的一條邊。第五十四張，PPT共七十四頁，創(chuàng)作于2022年6月55有關(guān)圖的的重要概念無向圖：邊的表示（，）有向圖：邊的表示，成本：帶有成本的圖稱為網(wǎng)絡(luò)鄰接：如果存在邊（i，j）則稱結(jié)點(diǎn)i和j鄰接結(jié)點(diǎn)的度（出度入度）路徑：由結(jié)點(diǎn)vp到vq的一條路（path）是結(jié)點(diǎn) vp ， vi1 ， vi2 ， ， vim ， vq的一個(gè)序 列，它使得( vp ， vi1 ) ，( vi1 ，vi2 ) ， ， ( vim ， vq )是E（G）的邊。路的長度：組成

19、路的邊數(shù)。第五十五張，PPT共七十四頁，創(chuàng)作于2022年6月56簡單路徑：除了第一和最后一個(gè)結(jié)點(diǎn)可以相同以外， 其它所有結(jié)點(diǎn)都不同。環(huán)：第一個(gè)和最后一個(gè)結(jié)點(diǎn)相同的簡單路。連通圖：在無向圖中，如果每對(duì)結(jié)點(diǎn)之間都存在一條 路，則稱該圖是連通的。子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E 中連接VB中結(jié)點(diǎn)的邊的子集所組成的圖。連通分圖：一個(gè)圖的最大連通子圖。有向圖的強(qiáng)連通性：在有向圖中，如果對(duì)于每一對(duì)結(jié) 點(diǎn)i和j，既存在一條從i到j(luò)的路，又存在一條從j 到i的路，則稱該有向圖是強(qiáng)連通的。第五十六張，PPT共七十四頁，創(chuàng)作于2022年6月57圖的表示方法鄰接矩陣 鄰接表第五十七張，PPT共七十四

20、頁，創(chuàng)作于2022年6月581.5 遞歸和消去遞歸遞歸 一個(gè)算法若其中有調(diào)用自身的過程，則稱該算法是一個(gè)遞歸算法。 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法 遞歸的效率問題第五十八張，PPT共七十四頁，創(chuàng)作于2022年6月59 例1.3 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 + Fi-2 （i1) 算法1.7 求斐波那契數(shù) procedure F(n) /返回第n個(gè)斐波那契數(shù)/ integer n if n= 1 then return(1) else return(F(n-1) + F(n-2) endif end F算法效率：對(duì)F(n-1) 、F(n-2)存在

21、大量的重復(fù)計(jì)算改 進(jìn)：保存中間結(jié)果第五十九張，PPT共七十四頁，創(chuàng)作于2022年6月60練習(xí)題18Procedure F1(n) If n2 then return(1) Else return (F2(2,n,1,1) EndifEnd F1Procedure F2(i,n,x,y) If i=n Then call F2(i+1,n,y,x+y) Endif Return(y)End F2第六十張，PPT共七十四頁，創(chuàng)作于2022年6月61練習(xí)17題假設(shè)t(n)是所給出的F(n)的時(shí)間函數(shù)，證明t(n)=O(2n-2)第六十一張，PPT共七十四頁，創(chuàng)作于2022年6月62練習(xí)18題以下是計(jì)

22、算第n個(gè)斐波那契數(shù)的函數(shù)Procedure F1(n)If(nb / if b=0 then return(a) else return (GCD(b,a mod b) endif end GCD 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;第六十三張，PPT共七十四頁，創(chuàng)作于2022年6月64例1.5 遞歸在非數(shù)值算法設(shè)計(jì)中的應(yīng)用 已知元素x，判斷x是否在A（1：n）中。 算法1.9 在A（1：n）中檢索x procedure SEARCH(i) /如果在A（1：n）/中有一元素A（k）=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/

23、global n,x,A(1:n) case :in: return(0) :A(i) = x; return(i) :else: return(SEARCH(i+1) endcase end SEARCH第一次調(diào)用ans-SEARCH(1)第六十四張，PPT共七十四頁，創(chuàng)作于2022年6月652. 消去遞歸直接遞歸的消去規(guī)則： 基本思路：將遞歸過程中出現(xiàn)遞歸調(diào)用的地方，用等價(jià)的非遞歸代碼來代替，并對(duì)return語句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用中的遞歸代碼和return語句，將之轉(zhuǎn)換成等價(jià)的迭代代碼。 初始化 在過程的開始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這

24、個(gè)棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 將標(biāo)號(hào)L1附于第一條可執(zhí)行語句。然后對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來代替。第六十五張，PPT共七十四頁，創(chuàng)作于2022年6月66 處理遞歸調(diào)用語句 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個(gè)全程變量來看待。 建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來計(jì)算返回地址。 此標(biāo)號(hào)放在規(guī)則所描述的程序段中。 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分： Goto L1第六十六張，PPT共七十四頁，創(chuàng)作于2022年6月67 對(duì)遞歸

25、嵌套調(diào)用的處理 如果這過程是函數(shù)，則對(duì)遞歸過程中含有此次函數(shù)調(diào)用的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將中建立的標(biāo)號(hào)附于這條語句上。 如果此過程不是函數(shù)，則將中建立的標(biāo)號(hào)附于所產(chǎn)生的轉(zhuǎn)移語句后面的那條語句。 以上步驟實(shí)現(xiàn)消去過程中的遞歸調(diào)用。下面對(duì)過程中出現(xiàn)return語句進(jìn)行處理（純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）。第六十七張，PPT共七十四頁，創(chuàng)作于2022年6月68 對(duì)每個(gè)有return語句的地方，執(zhí)行下述規(guī)則： 如果棧為空，則執(zhí)行正常返回。 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)， out/inout型）的當(dāng)前值賦給棧頂上的那些對(duì)應(yīng)的變量。 如果棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 從棧中退出所有局部變量和參數(shù)的值并把它們賦給對(duì)應(yīng)的變量。 如果這個(gè)過程是函數(shù)，則插入以下指令，這些指令用來計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。第六十八張，P