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

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

2、數(shù)據(jù)的方法算法：計(jì)算機(jī)軟件的靈魂第3頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三4問(wèn)題求解(Problem Solving)設(shè)計(jì)程序證明正確性分析算法理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法第4頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三5章節(jié)安排第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu) 第二章 分治法 第三章 貪心方法 第四章 動(dòng)態(tài)規(guī)劃 第五章 檢索與周游第六章 回溯法第七章 分枝-限界第八章 NP-問(wèn)題?算法研討環(huán)節(jié) 第5頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三6第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1 算法的定義及特性1. 什么是算法？ 算法如數(shù)字、

3、計(jì)算一樣，是一個(gè)基本概念。 算法是解一類確定問(wèn)題的任意一種特殊的方法。 在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問(wèn)題的精確、有效方法的代名詞： 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。第6頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三72.算法的五個(gè)重要特性 確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算 5/0 將6或7與x相加 未賦值變量參與運(yùn)算第7頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三82）能行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆

4、在有限的時(shí)間內(nèi)完成。例：整數(shù)的算術(shù)運(yùn)算是“能行”的 實(shí)數(shù)(無(wú)理數(shù))的算術(shù)運(yùn)算是“不能行”的第8頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三93）輸入 每個(gè)算法有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合定義域（或值域）4）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。第9頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三105）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。計(jì)算過(guò)程：只滿足確定性、能行性、輸入、輸出四個(gè)特性但不一定能終止的一組規(guī)則。 準(zhǔn)確理解算法和計(jì)算過(guò)程的區(qū)別： 不能終止的計(jì)算過(guò)程：操作系統(tǒng)。 算法

5、是“可以終止的計(jì)算過(guò)程”。 算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計(jì)算機(jī)上運(yùn)行。第10頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三114. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng) 2）表示算法：思想的表示形式 3）確認(rèn)算法：證明算法的正確性 程序的證明（程序的形式化證明技術(shù)） 4）分析算法：算法時(shí)空特性分析 5）測(cè)試程序：“調(diào)試只能指出有錯(cuò)誤，而不能指出它們 不存在錯(cuò)誤” 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過(guò)學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)。第11頁(yè)，共74頁(yè)，2022年，5月20日

6、，22點(diǎn)36分，星期三125. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)語(yǔ)言：結(jié)構(gòu)化設(shè)計(jì) 數(shù)學(xué)基礎(chǔ) 非數(shù)值計(jì)算領(lǐng)域的基本知識(shí)第12頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三131.2 分析算法1. 分析算法的目的 在于：通過(guò)對(duì)算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無(wú)益的人力和物力浪費(fèi)。 算法分析是計(jì)算機(jī)領(lǐng)域的古老而前沿的課題。 進(jìn)行算法分析的基本技術(shù)：抽象第13頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三142. 重要的假設(shè)和約定1）計(jì)算機(jī)模型的假設(shè) Turing機(jī)模型：計(jì)算機(jī)形式理論模型 通用計(jì)算

7、機(jī)模型： 順序計(jì)算機(jī) 有足夠的“內(nèi)存” 能在固定的時(shí)間內(nèi)存取數(shù)據(jù)單元 第14頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三152）計(jì)算的約定 算法的執(zhí)行時(shí)間=Fi*ti 其中，F(xiàn)i是算法中用到的某種運(yùn)算i的次數(shù)， 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)算 過(guò)程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算的執(zhí)行時(shí)間不同，但一般只花 一個(gè)固定量的時(shí)間（單位時(shí)間）就可完成。第15頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三162）計(jì)算的約定（續(xù)） 其

8、他運(yùn)算： 字符串操作：與字符串中字符的數(shù)量成正比 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特點(diǎn)：運(yùn)算時(shí)間無(wú)定量 如何分析非時(shí)間囿界于常數(shù)的運(yùn)算：分解成若干時(shí)間囿界于常數(shù)的運(yùn)算。 如：Tstring = Length（String）* tchar第16頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三173）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性能。測(cè)試數(shù)據(jù)集的生成在目前算法證明與程序正確性證明沒(méi)有取得理論上的突破性進(jìn)展的情況下，是程序測(cè)試與算法分析中的關(guān)鍵技術(shù)之一。 作為算法分析的數(shù)據(jù)集：典型特征 作為程序

9、性能測(cè)試的數(shù)據(jù)集：對(duì)執(zhí)行指標(biāo)產(chǎn)生影響的性質(zhì)第17頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三183. 如何進(jìn)行算法分析？ 對(duì)算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行：事前分析：就算法本身，通過(guò)對(duì)其執(zhí)行性能的理論分析， 得出關(guān)于算法特性時(shí)間和空間的一個(gè)特征 函數(shù)（、）與計(jì)算機(jī)物理軟硬件沒(méi)有 直接關(guān)系。事后測(cè)試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行， 收集其執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，進(jìn)行 分析判斷直接與物理實(shí)現(xiàn)有關(guān)。第18頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三191）事前分析目的：試圖得出關(guān)于算法執(zhí)行特性的一種形式描 述，以“理論上”衡量算法的“好壞”。如何給出反

10、映算法執(zhí)行特性的描述？ 最直接方法：統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括： 引用了哪些運(yùn)算 每種運(yùn)算被執(zhí)行的次數(shù) 該種運(yùn)算執(zhí)行一次所花費(fèi)的時(shí)間等。 算法的執(zhí)行時(shí)間=Fi*ti第19頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三20頻率計(jì)數(shù) 例： xx+y for i 1 to n do for 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ǔ)句或一種運(yùn)算在算法

11、（或程序）體中的執(zhí)行次數(shù)。第20頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三21一條語(yǔ)句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間= 頻率計(jì)數(shù) * 每執(zhí)行一次該語(yǔ)句所需的時(shí)間 如何刻畫算法執(zhí)行特性的形式描述實(shí)際執(zhí)行時(shí)間受約于諸多實(shí)際因素，如機(jī)器類型、編程與語(yǔ)言、操作系統(tǒng)等，沒(méi)有統(tǒng)一的描述模型。在事前分析中，只限于確定與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立理論分析模型。第21頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三22數(shù)量級(jí) 語(yǔ)句的數(shù)量級(jí)：語(yǔ)句的執(zhí)行頻率 例：1，n ，n2 算法的數(shù)量級(jí)：算法所包含的所有語(yǔ)句的執(zhí) 行頻率之和。算法的數(shù)量級(jí)從本質(zhì)上反映了一個(gè)算法的執(zhí)

12、行特性。例：假如求解同一個(gè)問(wèn)題的三個(gè)算法分別具有n， n2 ， n3數(shù) 量級(jí)。 若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè) 單位時(shí)間與環(huán)境因素?zé)o關(guān)。第22頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三23 計(jì)算時(shí)間/頻率計(jì)數(shù)的表示函數(shù) 通過(guò)事前分析給出算法計(jì)算時(shí)間（頻率計(jì)數(shù)）的一個(gè)函數(shù)表示形式，一般記為與輸入規(guī)模n有關(guān)的函數(shù)形式：f(n)注：最高次項(xiàng)與函數(shù)整體的關(guān)系空間特性分析（略） 第23頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三242）事后測(cè)試目的：運(yùn)行程序，確定程序?qū)嶋H耗費(fèi)的時(shí)間與空間，驗(yàn)證先前的分析結(jié)論包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)

13、計(jì)的算法。分析手段：作時(shí)、空性能分布圖第24頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三254. 計(jì)算時(shí)間的漸近表示記：算法的計(jì)算時(shí)間為f(n) 數(shù)量級(jí)限界函數(shù)為g(n)其中， n是輸入或輸出規(guī)模的某種測(cè)度。 f(n)表示算法的“實(shí)際”執(zhí)行時(shí)間與機(jī)器及語(yǔ)言有關(guān)。 g(n)是形式簡(jiǎn)單的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過(guò)對(duì)計(jì)算時(shí)間或頻率計(jì)數(shù)統(tǒng)計(jì)分析所得的、與機(jī)器及語(yǔ)言無(wú)關(guān)的函數(shù)。 以下給出算法執(zhí)行時(shí)間：上界（）、下界（）、“平均”（ ）的定義。第25頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三261）上界函數(shù)定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所

14、有的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)。 第26頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三27F(n)=3n+2 可取c4，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

15、(2n)第27頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三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|) nm 令c= |am|+|am-1|+|a0| 則，定理得證。第28頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三29 計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響 數(shù)量級(jí)的

16、大小對(duì)算法的有效性有決定性的影響。 例：假設(shè)解決同一個(gè)問(wèn)題的兩個(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í)間增長(zhǎng)4倍，而一個(gè)(nlogn)算法則只用2倍多一點(diǎn)的時(shí)間即可完成。第29頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三30 算法分類（計(jì)算時(shí)間）多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。 常見(jiàn)的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (

17、n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法 常見(jiàn)的指數(shù)時(shí)間限界函數(shù)： (2n) (n！) 0。 第49頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三50第50頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三51 特殊形態(tài)的二元樹 滿二元樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二元樹 第51頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三52 完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號(hào)為1到n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級(jí)上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見(jiàn)引

18、理1.2）。第52頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三53 堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和（大于或等于）該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大（ max-堆）（或小， min-堆）。二分檢索樹：二分檢索樹是一棵二元樹，它或者為空，或者其每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且有：的左子樹的所有元素比根結(jié)點(diǎn)中的元素??；的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；的左子樹和右子樹也是二分檢索樹。注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異第53頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三543. 圖 圖由稱之為結(jié)點(diǎn)和邊的兩個(gè)集合組成，記為G=（V，E

19、）。其中，是一個(gè)有限非空的結(jié)點(diǎn)集合；是結(jié)點(diǎn)對(duì)偶的集合，的每一對(duì)偶表示的一條邊。第54頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三55有關(guān)圖的的重要概念無(wú)向圖：邊的表示（，）有向圖：邊的表示，成本：帶有成本的圖稱為網(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）的邊。路的長(zhǎng)度：組成路的邊數(shù)。第55頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分

20、，星期三56簡(jiǎn)單路徑：除了第一和最后一個(gè)結(jié)點(diǎn)可以相同以外， 其它所有結(jié)點(diǎn)都不同。環(huán)：第一個(gè)和最后一個(gè)結(jié)點(diǎn)相同的簡(jiǎn)單路。連通圖：在無(wú)向圖中，如果每對(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)連通的。第56頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三57圖的表示方法鄰接矩陣 鄰接表第57頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三

21、581.5 遞歸和消去遞歸遞歸 一個(gè)算法若其中有調(diào)用自身的過(guò)程，則稱該算法是一個(gè)遞歸算法。 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法 遞歸的效率問(wèn)題第58頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三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)存在大量的重復(fù)

22、計(jì)算改 進(jìn)：保存中間結(jié)果第59頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三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第60頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三61練習(xí)17題假設(shè)t(n)是所給出的F(n)的時(shí)間函數(shù)，證明t(n)=O(2n-2)第61頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)3

23、6分，星期三62練習(xí)18題以下是計(jì)算第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;第63頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三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）=

24、x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/ 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)第64頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三652. 消去遞歸直接遞歸的消去規(guī)則： 基本思路：將遞歸過(guò)程中出現(xiàn)遞歸調(diào)用的地方，用等價(jià)的非遞歸代碼來(lái)代替，并對(duì)return語(yǔ)句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用中的遞歸代碼和return語(yǔ)句，將之轉(zhuǎn)換成等價(jià)的迭代代碼。 初始化 在過(guò)程的

25、開始部分，插入說(shuō)明為棧的代碼并將其初始化為空。在一般情況下，這個(gè)棧用來(lái)存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 將標(biāo)號(hào)L1附于第一條可執(zhí)行語(yǔ)句。然后對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來(lái)代替。第65頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三66 處理遞歸調(diào)用語(yǔ)句 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個(gè)全程變量來(lái)看待。 建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來(lái)計(jì)算返回地址。 此標(biāo)號(hào)放在規(guī)則所描述的程序段中。 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過(guò)程的開始部分：

26、Goto L1第66頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三67 對(duì)遞歸嵌套調(diào)用的處理 如果這過(guò)程是函數(shù)，則對(duì)遞歸過(guò)程中含有此次函數(shù)調(diào)用的那條語(yǔ)句做如下處理：將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方式照抄，并將中建立的標(biāo)號(hào)附于這條語(yǔ)句上。 如果此過(guò)程不是函數(shù)，則將中建立的標(biāo)號(hào)附于所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 以上步驟實(shí)現(xiàn)消去過(guò)程中的遞歸調(diào)用。下面對(duì)過(guò)程中出現(xiàn)return語(yǔ)句進(jìn)行處理（純過(guò)程結(jié)束處的end可看成是一條沒(méi)有值與之聯(lián)系的return語(yǔ)句）。第67頁(yè)，共74頁(yè)，2022年，5月20日，22點(diǎn)36分，星期三68 對(duì)每個(gè)有return語(yǔ)句的地方，執(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è)過(guò)程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。第68頁(yè)，共74頁(yè)