《數(shù)據(jù)結(jié)構(gòu)》講義

WORD格式 可編輯WORD格式 可編輯專業(yè)知識 整理分享專業(yè)知識 整理分享第一章：緒論課程：數(shù)據(jù)結(jié)構(gòu)課題：第一章1.1T.4小節(jié)（共4個課時）什么是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型的表現(xiàn)與實現(xiàn)算法和算法分析目的要求：理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的概念；掌握邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系；理解算法的基本概念；學(xué)會分析算法的時間復(fù)雜性和空間復(fù)雜性。新課重點、難點：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、時間復(fù)雜性和空間復(fù)雜性教學(xué)方法：課堂講解、例題演示，課件演示教學(xué)內(nèi)容及過程： 第1-2課時 計算機的應(yīng)用不再局限于科學(xué)計算，更多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值計算的處理工作。計算機加工處理的對象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進行程序設(shè)計時必須分析待處理的對象的特性及各對象之間存在的關(guān)系 產(chǎn)生背景。什么是數(shù)據(jù)結(jié)構(gòu)計算機解題步驟：建立數(shù)學(xué)模型一一設(shè)計解此數(shù)學(xué)模型的算法一一編制程序一一進行測試調(diào)整一一解答。其中建立數(shù)學(xué)模型的實質(zhì)：找出操作對象之間的關(guān)系。例1.圖書館書目檢索理一對應(yīng)線性關(guān)系例2.博奕樹——對應(yīng)樹型關(guān)系例3.交叉路口交通燈管理 一一對應(yīng)圖狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象及它們之間的關(guān)系和操作 等的學(xué)科。（地位）數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語.數(shù)據(jù)（Data）數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機器且能被處理的各種符號集合。換句話說，數(shù)據(jù)是對客觀事物采用計算機能夠識別、存儲和處理的形式所進行的描述；是計算機加工處理的對象。包括數(shù)值、字符、聲音、圖象等。.數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位 ，是數(shù)據(jù)集合的個體，在計算機中通常作為一個邏輯整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成（ DataItem）。.數(shù)據(jù)對象（DataObject）數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 例如：整數(shù)數(shù)據(jù)對象是集合N={0,±1,土2,…},字母字符數(shù)據(jù)對象是集合C={'A','B',…，'Z'}，表1-1所示的學(xué)籍表也可看作一個數(shù)據(jù)對象。由此可看出，不論數(shù)據(jù)元素集合是無限集（如整數(shù)集） 、有限集（如字符集），還是由多個數(shù)據(jù)項組成的復(fù)合數(shù)據(jù)元素（如學(xué)籍表），只要性質(zhì)相同， 都是同一個數(shù)據(jù)對象。綜上1~3所述，再分析數(shù)據(jù)概念：

其一數(shù)據(jù)持點其二：數(shù)據(jù)構(gòu)成《其一數(shù)據(jù)持點其二：數(shù)據(jù)構(gòu)成《「數(shù)據(jù)元素——組成數(shù)據(jù)的基本單位f與數(shù)據(jù)的關(guān)系是集合的個體，

數(shù)據(jù)對象 一性質(zhì)相同的數(shù)據(jù)元家的集合「數(shù)據(jù)元素——組成數(shù)據(jù)的基本單位工與數(shù)據(jù)的關(guān)系是集合的子集).結(jié)構(gòu)(DataStructure)工與數(shù)據(jù)的關(guān)系是集合的子集)數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)(Structure )，有四種基本結(jié)構(gòu)。(1)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個集合的關(guān)系外，無任何其它關(guān)系。(2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對一的線性關(guān)系。(3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。線性結(jié)構(gòu)一一線性表、棧、隊、字符串、數(shù)組、廣義表非線性結(jié)構(gòu)一一樹、 圖數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_structure=(D,S)。其中：D為數(shù)據(jù)結(jié)構(gòu)的有限集，S是D上關(guān)系的有限集。例：復(fù)數(shù)結(jié)構(gòu)Complex=(C,R)其中：C為含兩個實數(shù)的集合{c1,c2};R={P} ,P是集合C上的一種關(guān)系，P={<c1,c2>} ,<c1,c2>為有序偶，c1表示復(fù)數(shù)白實部，c2表示復(fù)數(shù)的虛部。存儲結(jié)構(gòu)TOC\o"1-5"\h\z存儲結(jié)構(gòu)(又稱物理結(jié)構(gòu))是邏輯結(jié)構(gòu)在計算機中的存儲映象，是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，它包括 考據(jù)元素的表示和關(guān)系的表示 。形式化描述：D要存入機器中，建立一從 D的數(shù)據(jù)元素到存儲空間 M單元的映象S,D-M,即對于每一個d,dCD,都有唯一的mCM使S(DD=m,同時這個映象必須明顯或隱含地體現(xiàn)關(guān)系 R。邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系為： 存儲結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身的映象。 邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，兩者綜合起來建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。順序映象(順序存儲結(jié)構(gòu))順序結(jié)構(gòu)用元素在存儲器中的相對位置表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象(非順序存儲結(jié)構(gòu))非順序映像借助指示元素存儲地址的指針表示元素之間的邏輯關(guān)系。一維數(shù)組來描述順序存儲結(jié)構(gòu)，用指針來描述鏈式存儲結(jié)構(gòu)。運算的集合報建性名性期?事工*工事工蚯豆加工南王宜工究女34347345.45盹m451.12李缽445.90]85.6045.005B4,50助斃修男345.DO33(X0025.00?舐網(wǎng)IWXH趕慢女5gsl0有丸的T2I.IKIW05**fltea酸枷加EI9E!身865$m亂a1辟1.3】數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個部分：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合， 就叫做數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型(DataType)數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱 。數(shù)據(jù)類型中定義了兩個集合，即該類型的取值范圍，以及該類型中可允許使用的一組運算。例如高級語言中的數(shù)據(jù)類型就是已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實例。 從這個意義上講，數(shù)據(jù)類型是高級語言中允許的變量種類， 是程序語言中已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)(即程序中允許出現(xiàn)的數(shù)據(jù)形式) 。在高級語言中，整型類型可能的取值范圍是 -32768~+32767,可用的運算符集合為加、 減、乘、除、取模(如C語言中+,-,*,/,%)。抽象數(shù)據(jù)類型1)數(shù)據(jù)的抽象計算機中使用的是二進制數(shù)，匯編語言中則可給出各種數(shù)據(jù)的十進制表示，如 98.65、9.6E3等，它們是二進制數(shù)據(jù)的抽象；使用者在編程時可以直接使用，不必考慮實現(xiàn)細節(jié)。在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型， 如整型、實型、字符型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進一步定義更高級的數(shù)據(jù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等，這種數(shù)據(jù)抽象的層次為設(shè)計者提供了更有利的手段，使得設(shè)計者可以從抽象的概念出發(fā)，從整體考慮，然后自頂向下、逐步展開，最后得到所需結(jié)果?？梢赃@樣看，高級語言中提供整型、實型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出像棧、隊列、樹、圖等復(fù)雜的抽象數(shù)據(jù)類型。2)抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型(簡稱ADT是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計算機內(nèi)如何表示和實現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。從某種意義上講，抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。整數(shù)類型就是一個簡單的抽象數(shù)據(jù)類型實例。“抽象”的意義在于教學(xué)特性的抽象。一個 ADT定義了一個數(shù)據(jù)對象，數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關(guān)系，以及一組處理數(shù)據(jù)的操作。 ADT通常是指由用戶定義且用以表示應(yīng)用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)服務(wù)操作。抽象數(shù)據(jù)類型是近年來計算機科學(xué)中提出的最重要的概念之一，它集中體現(xiàn)了程序設(shè)計中一些最基本的原則：分解、抽象和信息隱藏。一個抽象數(shù)據(jù)類型確定了一個模型，但將模型的實現(xiàn)細節(jié)隱藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏起來。數(shù)學(xué)模型一抽象數(shù)據(jù)類型一數(shù)據(jù)結(jié)構(gòu)，恰好反應(yīng)了信息結(jié)構(gòu)轉(zhuǎn)換的三個重要階段，而在這個轉(zhuǎn)換過程中，數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，抽象數(shù)據(jù)類型是中樞。一個線性表的抽象數(shù)據(jù)類型的描述如下：ADTLinear-list數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對象，i=1,2,…，n,n>0;邏輯結(jié)構(gòu) 所有數(shù)據(jù)元素ai(i=1,2,…，n-1)存在次序關(guān)系<ai,ai+1>,ai無前趨，an無后繼；操作設(shè)L為Linear-list:Initial(L): 初始化空線性表；Length(L): 求線性表的表長;Get(L,i): 取線性表的第i個元素；Insert(L,i,b): 在線性表的第i個位置插入元素b;Delete(L,i): 刪除線性表的第i個元素。3)抽象數(shù)據(jù)類型實現(xiàn)第一種情況： 傳統(tǒng)的面向過程的程序設(shè)計。第二種情況：“包”、 “模型”的設(shè)計方法。第三種情況： 面向?qū)ο蟮某绦蛟O(shè)計(ObjectOrientedProgramming,簡稱OOP。4)ADT的定義ADT的定義格式不唯一，我們采用下述格式定義一個 ADT:ADT抽象數(shù)據(jù)類型名｛數(shù)據(jù)又■象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<結(jié)構(gòu)關(guān)系的定義>基本操作：<基本操作的定義>}ADT 抽象數(shù)據(jù)類型名其中數(shù)據(jù)對象和結(jié)構(gòu)關(guān)系的定義采用數(shù)學(xué)符號和自然語言描述 ，而基本操作的定義格式為：操作名稱(參數(shù)表)初始條件：<初始條件描述>操作Z^果：<操作結(jié)果描述>關(guān)于參數(shù)傳遞參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù) ，又稱值參；第二種參數(shù)既能為操作提供待TOC\o"1-5"\h\z處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。操作前提描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件 ，操作結(jié)果描述操作執(zhí)行之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回結(jié)果。 ADT可用現(xiàn)有計算機語言中已有的數(shù)據(jù)類型 ，即固有數(shù)據(jù)類型來表示和實現(xiàn)。 不同語言的表示和實現(xiàn)方法不盡相同， 如ADT中“返回結(jié)果的參數(shù)”， PASCAL語言用“變參”實現(xiàn)，C++語言通過“引用型參數(shù)”實現(xiàn)，而C語言用“指針參數(shù)”實現(xiàn)。用標準C語言表示和實現(xiàn)ADT描述時，主要包括以下兩個方面 ：通過結(jié)構(gòu)體將int、float等固有類型組合到一起，構(gòu)成一個結(jié)構(gòu)類型，再用typedef為該類型或該類型指針重新起一個名字。用C語言函數(shù)實現(xiàn)各操作?；静僮髦饕幸韵聨追N：插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個指定數(shù)據(jù)元素；更新：改變數(shù)據(jù)結(jié)構(gòu)中某個元素的值， 在概念上等價于刪除和插入操作的組合；查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個特定要求的數(shù)據(jù)元素(的位置和值 )；排序：(在線性結(jié)構(gòu)中)重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系， 使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。結(jié)構(gòu)化的開發(fā)方法與面向?qū)ο蟮拈_發(fā)方法的不同點， 結(jié)構(gòu)化的開發(fā)方法是面向過程的開發(fā)方法， 首先著眼于系統(tǒng)要實現(xiàn)的功能。從系統(tǒng)的輸入和輸出出發(fā)， 分析系統(tǒng)要實現(xiàn)的功能，用自頂向下、逐步細化的方式建立系統(tǒng)的功能結(jié)構(gòu)和相應(yīng)的程序模塊結(jié)構(gòu)。一旦程序功能需要修改， 就會涉及多個模塊，修改量大，易于出錯，并會引起程序的退化。作業(yè)1:1:理解和掌握幾個重要的基本概念：數(shù)據(jù)結(jié)構(gòu)；抽象數(shù)據(jù)類型等；2:理解和運用四種邏輯結(jié)構(gòu)；并進行合理的劃分。 第3-4課時 3抽象數(shù)據(jù)類型的表示和實現(xiàn)(1)預(yù)定義常量和類型。本書中用到以下常量符號， 如True、False、MAXSIZE等，約定用如下宏定義預(yù)先定義： #defineTRUE1defineFALSE0defineMAXSIZE100defineOK1#defineERROR0(2)本書中所有的算法都以如下的函數(shù)形式加以表示， 其中的結(jié)構(gòu)類型使用前面已有的定義。［數(shù)據(jù)類型］ 函數(shù)名(［形式參數(shù)及說明］){ 內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；n* 函數(shù)名*/函數(shù)的定義主要由函數(shù)名和函數(shù)體組成， 函數(shù)體用花括號“「和“}”括起來。函數(shù)中用方括號括起來的部分如“［形式參數(shù)］”為可選項， 函數(shù)名之后的圓括號不可省略。⑶賦值語句。i、簡單賦值；（1）〈變量名〉=〈表達式〉，它表示將表達式的值賦給左邊的變量；（2）〈變量〉++,它表示變量加1后賦值給變量；（3）〈變量〉--,它表示變量減1后賦值給變量。、串聯(lián)賦值#;〈變量1>=<變量2>=<變量3>=??=〈變量k>=〈表達式〉；、成組賦值#;（〈變量1〉，〈變量2〉，〈變量3>,…，〈變量k>）=（〈表達式1〉，〈表達式2〉，〈表達式3>,…，〈表達式k〉）;〈數(shù)組名1>［下標1］［下標2］=〈數(shù)組名2>［下標1］［下標2］;、條件賦值；〈變量名〉=〈條件表達式〉？〈表達式 1〉：〈表達式2〉；（4）條件選擇語句。if （〈表達式〉）語句；if（〈表達式〉）語句1;else 語句2;⑸循環(huán)語句。、for語句for（<表達式1>;〈表達式2〉;〈表達式3>）{ 循環(huán)體語句；}首先計算表達式1的值，然后求表達式2的值，若結(jié)果非零（即為真）則執(zhí)行循環(huán)體語句，最后對表達式3運算，如此循環(huán)， 直到表達式2的值為零（即不成立為假）時為止。2、while語句while（< 條件表達式>）{ 循環(huán)體語句；}while循環(huán)首先計算條件表達式的值，若條件表達式的值非零（即條件成立） ，則執(zhí)行循環(huán)體語句，然后再次計算條件表達式的值，重復(fù)執(zhí)行，直到條件表達式的值為零（即為假）時退出循環(huán)， 執(zhí)行該循環(huán)之后的語句。3、do-while語句do{ 循環(huán)體語句}while（< 條件表達式>）該循環(huán)語句首先執(zhí)行循環(huán)體語句 ，然后計算條件表達式的值， 若條件表達式成立，則再次執(zhí)行循環(huán)體，再計算條件表達式的值，直到條件表達式的值為零，即條件不成立時結(jié)束循環(huán)。 （6）輸入、輸出語句。輸入語句：用函數(shù)scanf實現(xiàn)；特別當數(shù)據(jù)為單個字符時， 用getchar函數(shù)實現(xiàn)；當數(shù)據(jù)為字符串時，用gets函數(shù)實現(xiàn)。輸出語句：用printf函數(shù)實現(xiàn)；當要輸出單個字符時，用putchar函數(shù)實現(xiàn)；當數(shù)據(jù)為字符串時，用puts函數(shù)實現(xiàn)。其中輸入輸出函數(shù)中的類型部分不做嚴格要求， 淡化表述。（7）其它一些語句。①return<表達式>或return: 用于函數(shù)結(jié)束。②break語句：可用在循環(huán)語句或case語句中結(jié)束循環(huán)過程或跳出情況語句。③continue語句： 可用在循環(huán)語句中結(jié)束本次循環(huán)過程， 進入下一次循環(huán)過程。 ④exitw表示出現(xiàn)異常情況時, 控制退出函數(shù)。(8)注釋形式。/*字符串*/ \//注釋句的作用是增強算法的可閱讀性，在算法描述中要求在函數(shù)首部加上對算法功能的必要注釋描述。加注釋說明時如果沒有涉及到的參量一定是多余的，而涉及到的內(nèi)容應(yīng)當作為參量，這實際上是程序設(shè)計中的一個素質(zhì)要求，希望多加注意。(9)一些基本的函數(shù)，例如：max函數(shù)：用于求一個或幾個表達式中的最大值； min函數(shù)：用于求一個或幾個表達式中的最小值； abs函數(shù)：用于求表達式的絕對值； eof函數(shù)：用于判定文件是否結(jié)束； eoln函數(shù)：用于判斷文本行是否結(jié)束。ADT舉例：對于一個復(fù)數(shù)z=x+yiADTcomplex{數(shù)據(jù)對象D={c1,c2|c1,c2立R}數(shù)據(jù)關(guān)系R1={<c1,c2,>}基本操作：TOC\o"1-5"\h\zadd(z1,z2,sum) ;subTracf(z1,z2,difference) ;Get_re億) ；Get_im(z) ;}ADTcomplex;1.4算法.算法(Algorithm)的定義Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.(算法是規(guī)則的有限集合， 是為解決特定問題而規(guī)定的一系列操作。 )是指令的有限序列，其中每一條指令表示一個或多個操作。.算法的特性有窮性：有限步驟之內(nèi)正常結(jié)束， 不能形成無窮循環(huán)。確定性：算法中的每一個步驟必須有確定含義， 無二義性?？尚行裕涸瓌t上能精確進行， 操作可通過已實現(xiàn)的基本運算執(zhí)行有限次而完成。輸入：有多個或。個輸入。(5)輸出：至少有一個或多個輸出。在算法的五大特性中， 最基本的是有限性、 確定性和可行性。.算法設(shè)計的要求)算法的正確性所設(shè)計的程序沒有語法錯誤；所設(shè)計的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；所設(shè)計的程序?qū)τ诰倪x擇的典型、 苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。例如： 要求n個數(shù)的最大值問題， 給出示意算法如下：max=0;for(i=1;i<=n;i++ ){scanf("%f”,x);if(x>max)max=x;}2)可讀性3)健壯性4)高效率和低存儲量

~~語言和程序的關(guān)系算法：描述了數(shù)據(jù)對象的元素之間的關(guān)系(包括數(shù)據(jù)邏輯關(guān)系、 存儲關(guān)系描述)。描述算法的工具：算法可用自然語言、框圖或高級程序設(shè)計語言進行描述。 自然語言簡單但易于產(chǎn)生二義，框圖直觀但不擅長表達數(shù)據(jù)的組織結(jié)構(gòu)， 而高級程序語言則較為準確但又比較嚴謹。程序是算法在計算機中的實現(xiàn)(與所用計算機及所用語言有關(guān)) 。設(shè)計實現(xiàn)算法過程的步驟找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系(建立結(jié)構(gòu)關(guān)系) 。確定在某一數(shù)據(jù)對象上所施加的運算?？紤]數(shù)據(jù)元素的存儲表示。選擇描述算法的語言。設(shè)計實現(xiàn)求解的算法， 并用程序語言加以描述。對算法作性能評價.性能評價對問題規(guī)模和該算法在運行時所占的空間 S與所耗費的時間T給出一個數(shù)量關(guān)系的評價。問題規(guī)模N對不同的問題其含義不同，對矩陣是階數(shù)，對多項式運算是多項式項數(shù)，對圖是頂點個數(shù)，對集合運算是集合中的元素個數(shù)。.有關(guān)數(shù)量關(guān)系的計算數(shù)量關(guān)系評價體現(xiàn)在時間一一算法編程后在機器中所耗費的時間。數(shù)量關(guān)系評價體現(xiàn)在空間一一算法編程后在機器中所占的存儲量。)關(guān)于算法執(zhí)行時間一個算法的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和， 對于語句的執(zhí)行時間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時間的乘積。2)語句頻度語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。 例1-1兩個nxn階矩陣相乘。藏算法每一語句的語句頻度為1far(i=Ojngi++)n2for(j=0|jVmj++)n1nJ4fortk=Qf n(k++)nJ)n33)算法的時間復(fù)雜度用隨著問題規(guī)模增加的函數(shù)來表征 ，以此T(n)是關(guān)于問題規(guī)模用隨著問題規(guī)模增加的函數(shù)來表征 ，以此T(n)是關(guān)于問題規(guī)模n的函數(shù)，進而分析T(n))。在這里， 我們用“O’來表示數(shù)量級，這樣我即是算法的時間量度，記作：f(n)的增長率相同，稱作算法的漸進時間復(fù)雜度，而對于算法分析，我們關(guān)心的是算法中語句總的執(zhí)行次數(shù)隨n的變化情況并確定 T(n)的數(shù)量級(OrderofMagnitude們可以給出算法的時間復(fù)雜度概念。 所謂算法的時間復(fù)雜度,T(n)=O(f(n))它表示隨問題規(guī)模 n的增大，算法的執(zhí)行時間的增長率和簡稱時間復(fù)雜度。一般情況下， 隨n的增大，T(n)的增長較慢的算法為最優(yōu)的算法。 例如：在下列三段程序段中，給出原操彳x=x+1的時間復(fù)雜度分析。x=x+1;其時間復(fù)雜度為O(1),我們稱之為常量階；for(i=1;i<=n;i++)x=x+1; 其時間復(fù)雜度為O(n),我們稱之為線性階；for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;其時間復(fù)雜度為O(n~~2),我們稱之為平方階。此外算法還能呈現(xiàn)的時間復(fù)雜度有對數(shù)階 O(log2n),~~>數(shù)階O(2n)等。4)數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù)有 7個：O(1)常數(shù)型O(n)線性型O(n2)平方型O(n3)立方型O(2n)指數(shù)型O(log2n)對數(shù)型O(nlog2n)二維型按時間復(fù)雜度由小到大遞增排列成表 1-3(當n充分大時)。不同數(shù)量級的時間復(fù)雜度的形狀如圖 1.6所示，表1-3與圖1.6是同一問題的不同表示形式。 一般情況下，隨n的增大，T(n)增長較慢的算法為最優(yōu)的算法。從中我們應(yīng)該選擇使用多項式階 O(nk)的算法， 而避免使用指數(shù)階的算法。嘀HhIll岫Gn工r?r■股地訴，意再三片出星地上是可宴戲的,實際上R有4a母國在松小的荒固腫;r有意舅，當n牧夫時.不01d11I1I1414i4su日3Ru**UE256464金颯5爵W1砌打針心U8例如：下列程序段：for(i=1;i<n;i++)for(j=i;j<=n;j++)x++;有一個二重循環(huán)， 語句x++的執(zhí)行頻度為： n+(n-1)+(n-2)+…+3+2+1=n(n+1)/2而該語句執(zhí)行次數(shù)關(guān)于 n的增長率為n2,即時間復(fù)雜度為O(n2)。5)最壞時間復(fù)雜度算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集的不同而不同。6)算法的空間復(fù)雜度(略)作業(yè)2：1:圖1.5、P13:算法的5個特征；2:P15:兩段程序的語句的頻度的分析本章教學(xué)總結(jié)：第二章：線性表課程：數(shù)據(jù)結(jié)構(gòu)課題：第二章2.1—2.4小節(jié)(共6個課時)線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)—■兀多項式的表不及相加目的要求：理解線性表的定義和特點；掌握順序表和鏈表的特點，掌握在這兩種存儲結(jié)構(gòu)上各種基本運算的實現(xiàn)算法以及效率的分析，并學(xué)習(xí)在這兩種存儲結(jié)構(gòu)上進行算法設(shè)計的方法； 以達到利用基本算法進行較復(fù)雜算法設(shè)計的目的。新課重點、難點：線性表、 順序表、鏈表教學(xué)方法：課堂講解、例題演示，課件演示教學(xué)內(nèi)容及過程： 第 1-2課時 線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中，? 存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素；? 存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素；? 除第一個元素之外，集合中的每個元素均只有一個前驅(qū)；? 除最后一個元素之外，集合中的每個元素均只有一個后繼。線性表的類型定義線性表的邏輯結(jié)構(gòu)0-0_0_0_0-0例如：英文字母表(A,B,…，Z)就是一個簡單的線性表，表中的每一個英文字母是一個數(shù)據(jù)元素， 每個元素之間存在唯一的順序關(guān)系， 如在英文字母表字母B的前面是字母A而字母B的后面是字母C。在較為復(fù)雜的線性表中，數(shù)據(jù)元素(dataelements)可由若干數(shù)據(jù)項組成，如學(xué)生成績表中，每個學(xué)生及其各科成績是一個數(shù)據(jù)元素，它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項 (item)組成，常被稱為一個記錄(record),含有大量記錄的線性表稱為文件 (file)。數(shù)據(jù)對象(dataobject)是性質(zhì)相同的數(shù)據(jù)元素集合。表2-1 車輛登記表車牌號本名車 型展也A1385C奧迪骷年隰色B4S271福田小卡白色東國大卡孥色■￡線性表(LinearList)是由n(n>0)個類型相同的數(shù)據(jù)元素 a1,a2,…，an組成的有限序列，記作(a1,a2,…，ai-1,ai,ai+1,…，an)。這里的數(shù)據(jù)元素 ai(1wiwn)只是一個抽象的符號，其具體含義在不同情況下可以不同，它既可以是原子類型，也可以是結(jié)構(gòu)類型但同一線性表中的數(shù)據(jù)元素必須屬于同一數(shù)據(jù)對象。此外，線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系 ，即對于非空的線性表(a1,a2,…，ai-1,ai,ai+1,…，an),表中ai-1領(lǐng)先于ai,稱ai-1是ai的直接前驅(qū)，而稱ai是ai-1的直接后繼。除了第一個元素a1外,每個元素ai有且僅有一個被稱為其直接前驅(qū)的結(jié)點 ai-1,除了最后一個元素""an外，每個元素ai有且僅有個被稱為其直接后繼的結(jié)點 ai+1。線性表中元素的個數(shù) n被定義為線性表的長度， n=0時稱為空表。線性表的特點可概括如下：同一性：線性表由同類數(shù)據(jù)元素組成，每一個ai必須屬于同一數(shù)據(jù)對象。有窮性：線性表由有限個數(shù)據(jù)元素組成， 表長度就是表中數(shù)據(jù)元素的個數(shù)。有序性：線性表中表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系 <ai,ai+1>。由此可看出，線性表是一種最簡單的 數(shù)據(jù)結(jié)構(gòu)，因為數(shù)據(jù)元素之間是由一前驅(qū)一后繼的直觀有序的關(guān)系確定；線性表又是一種最常見的數(shù)據(jù)結(jié)構(gòu)，因為矩陣、數(shù)組、字符串、堆棧、 隊列等都符合線性條件。線性表的抽象數(shù)據(jù)類型定義ADTList{數(shù)據(jù)元素：D={ai|aiCElemSet,i=1,2, …，n,n>0,ElemSet為某一數(shù)據(jù)對象}關(guān)系：S={<ai,ai+1>|ai,ai+1CD,i=1,2, …，n-1}基本操作：InitList (&L)初始條件：L為未初始化線性表。操作結(jié)果：將L初始化為空表。DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：將L銷毀。ClearList(&L)初始條件：線性表L已存在。操作結(jié)果： 將表L置為空表。ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：如果L為空表則返回真， 否則返回假。ListLength (L)初始條件：線性表L已存在。操作結(jié)果： 如果L為空表則返回0,否則返回表中的元素個數(shù)。LocateElem(L,e,compare())初始條件： 表L已存在，compare。是數(shù)據(jù)元素判定函數(shù)。操作結(jié)果： 返回L中第1個與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序，如果不存在，返回值為0。GetElem(L,i,&e)初始條件： 表L存在，且1Wi<ListLength(L)。操作結(jié)果： 用e返回線性表L中第i個元素的值。ListInsert(&L,i,e)初始條件：表L已存在，1wiwListLength(L)+1。操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加1。ListDelete(&L,i,&e)初始條件： 表L已存在且非空， 1wiwListLength(L)。操作結(jié)果： 刪除L的第i個數(shù)據(jù)元素， 并用e返回其值，L的長度減1。}ADTList例2—1Voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);For(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);If(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}O(Listlength(LA)*Listlength(LB))例2—2VoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);While((i<=La_Len)&&(j<=Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}線性表的順序表示和實現(xiàn)線性表的順序存儲結(jié)構(gòu)線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。 采用順序存儲結(jié)構(gòu)的線性表通常稱為 順序表。假設(shè)線性表中有n個元素，每個元素占 k個單元，第一個元素的地址為 10c(a1)，則可以通過如下公式計算出第i個元素的地址loc(ai):loc(ai)=loc(a1)+(i-1) xk其中l(wèi)oc(a1)稱為基地址。它是一種隨機存取的數(shù)據(jù)結(jié)構(gòu)。順序存儲結(jié)構(gòu)可以借助于高級程序設(shè)計語言中的一堆數(shù)組來表示，一維數(shù)組的下標與元素在線性表中的序號相^?應(yīng)(C語言中下標等于序號減 1)。線性表的順序存儲結(jié)構(gòu)可用 C語言定義如下：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;/* 線性表占用的數(shù)組空間 */int length;intlistsize;}SeqList;線性表順序存儲結(jié)構(gòu)上的基本運算.初始化操作StatusIniList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;ReturnOK;}.插入操作在這種結(jié)構(gòu)中容易實現(xiàn)隨機存取第 i個數(shù)據(jù)元素，C語言中數(shù)組的下標從0開始，所以ai應(yīng)在L.elem[i-1]中存取。線性表的插入運算是指在表的第 i(1wiwn+1)個位置之前插入一個新元素 e,使長度為n的線性表(e1,…，ei-1,ei,???,en)變成長度為n+1的線性表(e1,…，ei-1,e,ei,…，en)。用順序表作為線性表的存儲結(jié)構(gòu)時， 由于結(jié)點的物理順序必須和結(jié)點的邏輯順序保持一致， 因此我們必須將原表中位置n,n-1,…，i上的結(jié)點，依次后移到位置n+1,n,…，i+1上，空出第i個位置，然后在該位置上插入新結(jié)點e。當i=n+1時，是指在線性表的末尾插入結(jié)點，所以無需移動結(jié)點，直接將 e插入表的末尾即可。例如：已知線性表(4,9,15,28,30,30,42,51,62) ,需在第4個元素之前插入一個元素“21”，則需要將第9個位置到第4個位置的元素依次后移一個位置，然后將“21”插入到第 4個位置，如圖2.3所示。請注意區(qū)分元素的序號和數(shù)組的下標。49J5283030Al5162WWW49J5283030A2?1624915212830305161圖2.3順序表中插入元素StatusListInsert_sq(sqList&L,inti,ElemTypee){If(i<1||i>L.length+1)returnERROR;If(L.length>=L.listsize){newbase=(ElemType*)realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType));If(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]));p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}插入元素時，時間主要耗費在移動元素上。移動個數(shù)取決于插入位置。.刪除操作線性表的刪除運算是指將表的第i(1wiwn)個元素刪去，使長度為n的線性表(e1,??,ei-1,ei,ei+1，…，en)變成長度為n-1的線性表(e1,…，ei-1,ei+1,…，en)。刪除第i個元素(iwiwn〉時需將從第i+1至第n(共n-i)個元素依次向前移動一個位置。例如：線性表(4,9,15,21,28,30,30,42,51,62) 刪除第5個元素， 則需將第6個元素到第10個元素依次向前移動一個位置，如圖 2.4所示。算法描述：StatusListDelete_Sq(sqList&L,inti,ElemType&e){If((i<1)||(i>L.length))returnERROR;P=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;For(++p;p<=q;++p)*(p-1)=*p;--L.Length;returnOK;}TOC\o"1-5"\h\z在順序表中插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動數(shù)據(jù)元素上。對于插入算法而言，設(shè) Pi為在第i個元素之前插入元素的概率，并假設(shè)在任何位置上插入的概率相等，即 Pi=1/(n+1),i=1,2, …，n+1。設(shè)Eins為在長度為n的表中插入一元素所需移動元素的平均次數(shù)， 則ii 1rt1 w+li=i 門+1工=1 2同理，設(shè)Qi為刪除第i個元素的概率，并假設(shè)在任何位置上刪除的概率相等， 即Qi=1/n,i=1, 2,…，no刪除一個元素所需移動元素的平均次數(shù) Edel為瓦畫二￡Qio_】)二一￡(〃—1)=-￡攵=1廠

t=l ni-l k=Q/.在順序表中查找元素的算法：intLocatElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){i=1;p=L.elem;While(i<=L.length&&!(*compare)(*p++,e))++i;If(i<=L.length)returni;elsereturn0;}.有兩個順序表LA和LB,其元素均為非遞減有序排列， 編寫一個算法，將它們合并成一個順序表LC,要求LC也是非遞減有序排列。例如LA=(2,2,3),LB=(1,3,3,4), 則LC=(1,2,2,3,3,3,4) 。算法思想：設(shè)表LC是一個空表，為使LC也是非遞減有序排列，可設(shè)兩個指針 i、j分別指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j],則當前先將LB.elem[j]插入到表LC中；若LA.elem[i]<LB.elem[j],則當前先將LA.elem[i[插入到表LC中，如此進行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表 LC中VoidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){Pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe));If(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;While(pa<=pa_last&&pb<=pb_last){If(*pa<=*pb)*pc++=*pa++;Else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}由上面的討論可知， 線性表順序表示的優(yōu)點是：(1)無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間(因為邏輯上相鄰的元素其存儲的物理位置也是相鄰的)；(2)可方便地隨機存取表中的任一元素。其缺點是：插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結(jié)點，其效率較低。由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預(yù)先進行靜態(tài)分配，因此當表長變化較大時，難以確定合適的存儲規(guī)模。若按可能達到的最大長度預(yù)先分配表空間，則可能造成一部分空間長期閑置而得不到充分利用；若事先對表長估計不足，則插入操作可能使表長超過預(yù)先分配的空間而造成溢出。作業(yè)1:1:算法2.1、圖2.2、算法2.42:算法2.5、算法2.6 第3-4課時 2.3線性表的鏈式表示和實現(xiàn)單鏈表線性表的鏈式存儲：用一組任意的存儲單元存放線性表的數(shù)據(jù)元素(這組存儲單元可以連續(xù)，也可不連續(xù))為表示數(shù)據(jù)元素之間的邏輯關(guān)系，還需有存儲一個指示后繼的信息一一指針。由數(shù)據(jù)域和指針域構(gòu)成數(shù)據(jù)元素的存儲映象，稱為結(jié)點(Node)。由也next單鏈表包括兩個域： 數(shù)據(jù)域用來存儲結(jié)點的值； 指針域用來存儲數(shù)據(jù)元素的直接后繼的地址(或位置)鏈表正是通過每個結(jié)點的指針域?qū)⒕€性表的 n個結(jié)點按其邏輯順序鏈接在一起。由于鏈表的每個結(jié)點只有一個

指針域，故將這種鏈表又稱為單鏈表。由于單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點的指針域中的，而第一個結(jié)點無前趨，因而應(yīng)設(shè)一個頭指針H指向第一個結(jié)點。同時，由于表中最后一個結(jié)點沒有直接后繼，則指定線性表中最后一個結(jié)點的指針域為“空”（NULL。這樣對于整個鏈表的存取必須從頭指針開始。）的單鏈表存儲結(jié)構(gòu)，整個鏈表的存取需從頭指針例如：圖2.5所示為線性表（A,B,C,D,E,F,G,H開始進行，依次順著每個結(jié)點的指針域找到線性表的各個元素。）的單鏈表存儲結(jié)構(gòu)，整個鏈表的存取需從頭指針頭指針H存儲地址1713頭指針H存儲地址17131925313743數(shù)據(jù)城

D

BCHFAGE指針域4313NULL371925圖2.5單鏈表的示例圖 a ah圖2.6單鏈表的邏輯狀態(tài)⑻帶頭結(jié)點的空單橙表⑻帶頭結(jié)點的空單橙表㈤帚頭第點的單微表單鏈表可以由頭指針唯一確定。圖單鏈表可以由頭指針唯一確定。圖2.7帶頭結(jié)點單鏈表圖示單鏈表的存儲結(jié)構(gòu)描述如下：TypedefstructLNode{TypedefstructLNode{ElemTypedata;StructLNode*next;}LNode,*Linklist;/*LinkList假設(shè)L是LinkList 型的變量，則ElemTypedata;StructLNode*next;}LNode,*Linklist;/*LinkList假設(shè)L是LinkList 型的變量，則L頭結(jié)點的單鏈表，則指向單鏈表的頭結(jié)點）；指向新申請的結(jié)點s->dits=c^㈤插入第一個結(jié)點（b）申謂新站點并賦值⑻插入第小元素為結(jié)構(gòu)指針類型*/是一個結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個結(jié)點 （對于帶,若L=NULL（對于帶頭結(jié)點的單鏈表為 L->next=NULL）,則表示單鏈表為一個空表，其長度為 0。若不是空表，則可以通過頭指針訪問表中結(jié)點，找到要訪問的所有結(jié)點的數(shù)據(jù)信息。對于帶頭結(jié)點的單鏈表 L,p=L->next指向表中的第一個結(jié)點 a1,即p->data=a1,而p->next->data=a2。其余依此類推。單鏈表上的基本運算.建立單鏈表圖2.8 頭插法建立單鏈表圖示voidCreateList_L(Linklist&L,intn){L=(Linklist)malloc(sizeof(Lnode));L->next=NULL;

For(i=n;i>0;--i){p=(Linklist)malloc(sizeof(Lnode));scanf(&p->data);p->next=L->next;L->next=p;}}2)尾插法建表⑥地人第一個結(jié)點指向新申請的結(jié)點空間>efata=￡：②⑥地人第一個結(jié)點指向新申請的結(jié)點空間>efata=￡：②『出始終指向單攝表的表尾曲插入第二個結(jié)點0）申請新結(jié)點弁賦值圖2.9尾插法建表圖示.查找在單鏈表中，由于每個結(jié)點的存儲位置都放在其前一結(jié)點的 next域中，因而即使知道被訪問結(jié)點的序號 i,也不能像順序表那樣直接按序號 i訪問一維數(shù)組中的相應(yīng)元素，實現(xiàn)隨機存取，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。算法描述：設(shè)帶頭結(jié)點的單鏈表的長度為 n,要查找表中第i個結(jié)點，則需要從單鏈表的頭指針 L出發(fā)，從頭結(jié)點（L->next）開始順著鏈域掃描， 用指針p指向當前掃描到的結(jié)點，初值指向頭結(jié)點，用j做計數(shù)器，累計當前掃描過的結(jié)點數(shù)（初值為 0）,當上=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。查找元素的算法：StatusGetElem_L(LinklistL,inti,ElemType&e){P=L->next;j=1;While(p&j<i){p=p->next;++j;}if(!pj>i)return ERROR;e=p->data;returnok;}.單鏈表插入操作算法描述：要在帶頭結(jié)點的單鏈表L中第i個位置插入一個數(shù)據(jù)元素e,需要首先在單鏈表中找到第i-1個結(jié)點并由指針pre指示，然后申請一個新的結(jié)點并由指針 s指示，其數(shù)據(jù)域的值為e,并修改第i-1個結(jié)點的指針使其指向s,然后使s結(jié)點的指針域指向原第i個結(jié)點。插入：s->next=p->next; p->next=s;口】申清新的堵點⑷尋找第17個結(jié)點㈤描入?與橫鏈：“冷I斷

鐫捅鼠

pre->next='3f 圖2.10 在單鏈表第i個結(jié)點前插入一個結(jié)點的過程StatusListInsert_L(Linklistp=L;j=0;While(p&&j<i-1){p=p->next;++j}If(!pj>i-1)&L,inti,ElmeTypee){return口】申清新的堵點⑷尋找第17個結(jié)點㈤描入?與橫鏈：“冷I斷

鐫捅鼠

pre->next='3f 圖2.10 在單鏈表第i個結(jié)點前插入一個結(jié)點的過程StatusListInsert_L(Linklistp=L;j=0;While(p&&j<i-1){p=p->next;++j}If(!pj>i-1)&L,inti,ElmeTypee){returnERROR;s=(Linklist)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return}4.刪除OK;LL(b)刪除并釋放糊點圖2.11StatusListDelete_L(Linklistp=L;j=0;While(p->next&&j<i-1){p=p->next;++j;&L,inti,單鏈表的刪除過程Elemtype&e){}if(!(p->next)j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}合并單鏈表：voidmergelist_L(Linklist&La,Linklist&Lb,Linklist &Lc){pa=La->next;pb=Lb->next;Lc=pc=La;While(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}作業(yè)2:1:圖2.5、圖2.8、圖2.92:算法2.8、算法2.9、算法2.10、算法2.11 第 5-6課時 循環(huán)鏈表是單鏈表的另一種形式，它是一個首尾相接的鏈表。其特點是將單鏈表循環(huán)鏈表(CircularLinkedList)是單鏈表的另一種形式，它是一個首尾相接的鏈表。其特點是將單鏈表最后一個結(jié)點的指針域由 NULL改為指向頭結(jié)點或線性表中的第一個結(jié)點， 就得到了單鏈形式的循環(huán)鏈表， 并稱為循環(huán)單鏈表。類似地，還有多重鏈的循環(huán)鏈表。在循環(huán)單鏈表中，表中所有結(jié)點都被鏈在一個環(huán)上，多重循為循環(huán)單鏈表。類似地，還有多重鏈的循環(huán)鏈表。環(huán)鏈表則是將表中的結(jié)點鏈在多個環(huán)上。 為了使某些操作實現(xiàn)起來方便，在循環(huán)單鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅由一個自成循環(huán)的頭結(jié)點表示。L㈤帶其堵點的空循環(huán)碌L(b)常頭轉(zhuǎn)點的隨環(huán)，單褲表的一般甲式L㈤帶其堵點的空循環(huán)碌L(b)常頭轉(zhuǎn)點的隨環(huán)，單褲表的一般甲式*(rear->nrsl) *TClf(0采用尾指葉的福環(huán)單循表的股形式圖2.12 帶頭結(jié)點循環(huán)單鏈表雙向鏈表O(n)。如果循環(huán)單鏈表的出現(xiàn)，雖然能夠?qū)崿F(xiàn)從任一結(jié)點出發(fā)沿著鏈能找到其前驅(qū)結(jié)點，但時間耗費是

O(n)。如果(向)鏈表(DoubleLinkedList)(向)鏈表(DoubleLinkedList)。typedefstructDulNode{*prior,*next;ElemTypedata;*prior,*next;StructDulNode}DulNode,*DuLinklist;圖2.13雙鏈表的結(jié)點結(jié)構(gòu)由于在雙向鏈表中既有前向鏈又有后向鏈， 尋找任一個結(jié)點的直接前驅(qū)結(jié)點與直接后繼結(jié)點變得非常方便。設(shè)指針p指向雙鏈表中某一結(jié)點，則有下式成立：p->prior->next=p=p->next->prior⑷空的雙叵循環(huán)培表向華⑷空的雙叵循環(huán)培表向華空曲雙叵館環(huán)跖哀圖2.14雙向循環(huán)鏈表圖示.雙向鏈表的前插操作圖2.15雙向鏈表插入操作.雙向鏈表的刪除操作算法描述：圖2.16雙向鏈表的刪除操作.3.5靜態(tài)鏈表靜態(tài)鏈表同樣可以借助一維數(shù)組來描述:#defineMAXSIZE1000typedefstruct{ElemTypedata;intcur;

}component,SlinkList[MAXSIZE];設(shè)S為SlinkList 型變量，則S[0].cur指示第一個結(jié)點在數(shù)組中的位置，設(shè)i=s[0].cur,則s[i].data存放線性表的第一個元素，且s[i].cur 指示第二個結(jié)點在數(shù)組中位置。一般情況，若第i個分量表示鏈表的第k個結(jié)點，則s[i].cur指示第k+1個結(jié)點的位置。在靜態(tài)鏈表中以整型游標 i代替動態(tài)指針p,i=s[i].cur類似于p=p->next。1a2b3c4d5I1a2b3c4d5I￡gh6L0(?)蒯始牝I&2kae4d身f5■7hSii0E5a5(b)插入七后78qio1*Zb3c4d9i右￡5hStQe5GJ副除b后45圖2.17靜態(tài)鏈表的插入和刪除操作示例定位函數(shù):intLocateElem_SL(SlinkListi=s[0].cur;while(i&&s[i].data!=e)returni;s,ElemTypee){i=s[i].cur;}voidIniteSpace_SL(SlinkListfor(i=0;i<MAXSIZE-1;++i)space[MAXSIZE-1].cur=0;intLocateElem_SL(SlinkListi=s[0].cur;while(i&&s[i].data!=e)returni;s,ElemTypee){i=s[i].cur;}voidIniteSpace_SL(SlinkListfor(i=0;i<MAXSIZE-1;++i)space[MAXSIZE-1].cur=0;&space){space[i].cur=i+1;}int}int&space){Malloc_SL(SlinkListi=space[0].cur;&space){if(space[0].cur)space[0].cur=space[i].cur;returni;}voidFree_SL(Slinklist&space,intk){space[k].cur=space[0].cur;space[0].cur=k;}.3.6 順序表和鏈表的比較.基于空間的考慮在鏈表中的每個結(jié)點， 除了數(shù)據(jù)域外，還要額外設(shè)置指針(或光標)域，從存儲密度來講，這是不經(jīng)濟的。所謂存儲密度(StorageDensity), 是指結(jié)點數(shù)據(jù)本身所占的存儲量和整個結(jié)點結(jié)構(gòu)所占的存儲量之比， 即存儲密度=結(jié)點數(shù)據(jù)本身所占的存儲量 /結(jié)點結(jié)構(gòu)所占的存儲總量一般地，存儲密度越大，存儲空間的利用率就越高。顯然，順序表的存儲密度為 1,而鏈表的存儲密度小于1。例如單鏈表的結(jié)點的數(shù)據(jù)均為整數(shù)， 指針所占空間和整型量相同， 則單鏈表的存儲密度為50%因此若不考慮順序表中的備用結(jié)點空間， 則順序表的存儲空間利用率為 100%而單鏈表的存儲空間利用率為 50%由此可知，當線性表的長度變化不大， 易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。.基于時間的考慮順序表是由向量實現(xiàn)的，它是一種隨機存取結(jié)構(gòu)，對表中任一結(jié)點都可以在 0(1)時間內(nèi)直接地存取，而鏈表中的結(jié)點，需從頭指針起順著鏈找才能取得。因此，若線性表的操作主要是進行查找，很少做插入和刪除時，宜采用順序表做存儲結(jié)構(gòu)。在鏈表中的任何位置上進行插入和刪除，都只需要修改指針。而在順序表中進行插入和刪除，平均要移動表中近一半的結(jié)點，尤其是當每個結(jié)點的信息量較大時，移動結(jié)點的時間開銷就相當可觀。因此，對于頻繁進行插入和刪除的線性表， 宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端， 則宜采用尾指針表示的單循環(huán)鏈表。.基于語言的考慮對于沒有提供指針類型的高級語言， 若要采用鏈表結(jié)構(gòu)， 則可以使用光標實現(xiàn)的靜態(tài)鏈表。 雖然靜態(tài)鏈表在存儲分配上有不足之處，但它和動態(tài)鏈表一樣，具有插入和刪除方便的特點。值得指出的是，即使是對那些具有指針類型的語言，靜態(tài)鏈表也有其用武之地。特別是當線性表的長度不變，僅需改變結(jié)點之間的相對關(guān)系時，靜態(tài)鏈表比動態(tài)鏈表可能更方便。.4 —■兀多項式的表不及相加對于符號多項式的各種操作，實際上都可以利用線性表來處理。比較典型的是關(guān)于一元多項式的處理。在數(shù)學(xué)上，一個一元多項式Pn(x)可按升哥的形式寫成：匕(X)=穌+片X+P2X2+P3X3+…+PttXn它實際上可以由n+1個系數(shù)唯一確定。因此，在計算機內(nèi)， 可以用一個線性表P來表示：2，…忠)假設(shè)Qm(x)是一個一元多項式， 則它也可以用一個線性表Q來表示，即Q=(夕國力…應(yīng)加)若假設(shè)m<n則兩個多項式相加的結(jié)果 Rn(x)=Pn(x)+Qn(x),也可以用線性表R來表示：我們可以采用順序存儲結(jié)構(gòu)來實現(xiàn)順序表的方法，使得多項式的相加的算法定義十分簡單，即 p[0]存系數(shù)p0,p[1]存系數(shù)p1,,p[n]存系數(shù)p-n,對應(yīng)單元的內(nèi)容相加即可。但是在通常的應(yīng)用中，多項式的指數(shù)有時可能會很高并且變化很大。 例如：R(x}=1+5尤1°°°。+7/2°°°。若采用順序存儲，則需要20001個空間，而存儲的有用數(shù)據(jù)只有三個，這無疑是一種浪費。若只存儲非零系數(shù)項，則必須存儲相應(yīng)的指數(shù)信息才行。假設(shè)一元多項式Pn(x)=p1xe1+p2xe2+??+pmxem其中pi是指數(shù)為ei的項的系數(shù)(且0weiwe2w…wem=n),若只存非零系數(shù)，則多項式中每一項由兩項構(gòu)成(指數(shù)項和系數(shù)項) ，用線性表來表示， 即采用這樣的方法存儲，在最壞情況下，即n+1個系數(shù)都不為零，則比只存儲系數(shù)的方法多存儲 1倍的數(shù)據(jù)。但對于非零系數(shù)多的多項式則不宜采用這種表示。(3)圖2.18所示為兩個多項式的單鏈表， 分別表示多項式A(x)=7+3x+9x8+5x17和多項式B(x)=8x+22x7-9x8。圖2.18多項式的單鏈表表示法多項式相加的運算規(guī)則是:兩個多項式中所有指數(shù)相同的項的對應(yīng)系數(shù)相加, 若和不為零，則構(gòu)成“和多項式”中的一項；所有指數(shù)不相同的項均復(fù)抄到“和多項式”中。 以單鏈表作為存儲結(jié)構(gòu)，并且 “和多項式“中的結(jié)點無需另外生成，則可看成是將多項式B加到多項式A中，由此得到下列運算規(guī)則（設(shè)p、q分別指向多項式A、B的一項，比較結(jié)點的指數(shù)項）：若p->exp<q->exp,則結(jié)點p所指的結(jié)點應(yīng)是“和多項式”中的一項， 令指針p后移；若p->exp>q->exp,則結(jié)點q所指的結(jié)點應(yīng)是“和多項式”中的一項， 將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移；若p->exp=q->exp,則將兩個結(jié)點中的系數(shù)相加， 當和不為零時修改結(jié)點 p的系數(shù)域，釋放q結(jié)點；若和為零，則和多項式中無此項， 從A中刪去p結(jié)點，同時釋放p和q結(jié)點作業(yè)3:1:圖2.12、圖2.14、圖2.15、圖2.16、圖2.17、圖2.182:算法2.18、算法2.19、算法2.23本章教學(xué)總結(jié)：第三章：棧和隊列課程：數(shù)據(jù)結(jié)構(gòu)課題：第三章3.1—3.4小節(jié)(共6個課時)棧棧的應(yīng)有和舉例棧與遞歸的實現(xiàn)隊列目的要求：理解棧和隊列的定義、特點，學(xué)習(xí)它們的各種組織方式及算法； 掌握它們的空和滿的判斷條件;并學(xué)會它們的簡單應(yīng)用。新課重點、難點：教學(xué)方法：課堂講解、例題演示，課件演示教學(xué)內(nèi)容及過程：第1-2課時棧棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表尾進行，通常將表中允許進行插入、刪除操作的一端稱為棧頂(Top),因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的， 它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底 (Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔?，刪除操作稱為出?；蛲藯?。設(shè)S=(a1,a2,…,an)表示棧，則a1為棧底元素，an為棧頂元素。棧是一種后進先出(LastInFirstOut)的線性表(簡稱LIFO結(jié)構(gòu))。棧只能對棧頂元素進行插入和刪除操作。山棧 進柱(bl嬲調(diào).印拄的表示山棧 進柱(bl嬲調(diào).印拄的表示ADTStack{數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎篒nitStack(&S)初始條件：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。ClearStack(&S)初始條件：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。StackEmpty(S)初始條件：棧S已經(jīng)存在。操作結(jié)果：若S為空棧，則函數(shù)值為TRUE否則FALSEPush(&S,e)初始條件：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱壓入)元素e;Pop(&S,&e)初始條件：棧S已經(jīng)存在。操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。GetTop(S,&e)初始條件：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(&S,e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢谩５谋硎竞蛯崿F(xiàn).順序棧順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性， 還必須附設(shè)一個位置指針 top(棧頂指針)來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=0表示空棧。順序棧的存儲結(jié)構(gòu)可以用 C語言中的一維數(shù)組來表示。 棧的順序存儲結(jié)構(gòu)定義如下：defineTRUE1defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;// ?？墒褂玫淖畲笕萘縸Sqstack;按初始分配量進行第一次存儲分配， base為棧底指針，始終指向棧底。 top為棧頂指針，初值指向棧底，每插入一個元素，top增1;每刪除一個元素，top減1,top始終在棧頂元素的下一個位置上。toptopEQIm。EDCBBbnseAAA—― 1順序?；静僮鞯膶崿F(xiàn)如下 ：⑴初始化。StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));If(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}(2)取棧頂元素StatusGetTop(SqStackS,SElemType&e)if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}⑶入棧。StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}(4)出棧StatusPop(SqStack&S,SelemType&e){If(S.top==S.base)returnERROR;e=*--S.top;returnOK;}在棧的共享技術(shù)中最常用的是兩個棧的共享技術(shù)： 它主要利用了?！皸５孜恢貌蛔?，而棧頂位置動態(tài)變化”的特性。首先為兩個棧申請一個共享的一維數(shù)組空間 S[M,將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0,M-1。由于兩個棧頂動態(tài)變化，這樣可以形成互補，使得每個?？捎玫淖畲罂臻g與實際使用的需求有關(guān)。由此可見，兩棧共享比兩個棧分別申請 M/2的空間利用率高。Stack-。 M7trtQp|O|Kip|l|2.鏈棧3.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換假設(shè)要將十進制數(shù)N轉(zhuǎn)換為d進制數(shù)，一個簡單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到N等于零:X=Nmodd(其中mod為求余運算)N=Ndivd(其中div為整除運算)如(1348)10=(2504)8專業(yè)知識 整理分享專業(yè)知識 整理分享WORD格式可編輯NN/8N%81348168416S2102125202voidconversion。{InitStack(S);scanf("%d,&N);while(N){Push(s,N%8);N=N/8;}while(!StackEmpty){Pop(S,e)；printf( "%d,e);}} 算法：3.1作業(yè)1::圖3.1、3.2:P47:?；静僮鞯乃惴枋觥⑺惴?.1 第 3-4課時4.迷宮求解拓展：填充算法3.3棧與遞歸的實現(xiàn)遞歸是指在定義自身的同時又出現(xiàn)了對自身的調(diào)棧非常重要的一個應(yīng)用是在程序設(shè)計語言中用來實現(xiàn)遞歸。遞歸是指在定義自身的同時又出現(xiàn)了對自身的調(diào)WORD格式 可編輯WORD格式 可編輯專業(yè)知識 整理分享專業(yè)知識 整理分享用。如果一個函數(shù)在其定義體內(nèi)直接調(diào)用自己, 則稱其為直接遞歸函數(shù);如果一個函數(shù)經(jīng)過一系列的中間調(diào)用語句， 通過其它函數(shù)間接調(diào)用自己，則稱其為間接遞歸函數(shù)。.遞歸特性問題1)遞歸函數(shù)若n=口若n=口若n=1其它情況當m=0時當m#口,n-0時當 rtHO時Fib(n)=，[Fibfn-1)4Ftb(n—2)Ackerman函數(shù)；n+1Ack(jn,n)=Ack(jn,n)=Ack{m—1,Ackfm,n—D)上述Ackerman函數(shù)可用一個簡單的C語音函數(shù)描述如下1intick(intmantn){if(m==0)recurnti+1pdaeWfnFkO)returnackCm-1,1”wisereturn呢—1 -1))$I遞歸過程的實現(xiàn)一個函數(shù)調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)做的工作有：TOC\o"1-5"\h\z保留本層參數(shù)與返回地址(將所有的實在參數(shù)、 返回地址等信息傳遞給被調(diào)用函數(shù)保存) ；給下層參數(shù)賦值(為被調(diào)用函數(shù)的局部變量分配存儲區(qū)) ；將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也應(yīng)完成三件工作：保存被調(diào)函數(shù)的計算結(jié)果；恢復(fù)上層參數(shù)(釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)) ；依照被調(diào)函數(shù)保存的返回地址， 將控制轉(zhuǎn)移回調(diào)用函數(shù)。當多個函數(shù)調(diào)用時按后調(diào)用先返回的原則。例求n的階乘#include<stdio.h>langfac(intn){langL;if(!n)L=1;elseL=n*fac(n-1);returnL;}intmain(){intn;langL;scanf("%d,&n);L=fac(n);printf( "%ld",L);}例3-2：n階Hanoi塔問題：假設(shè)有三個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同、依小到大編號為1,2,…，n的圓盤?，F(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列原則：

⑴(2)⑴(2)⑶圓盤可以插在X、Y和Z中的任何一個塔座上；如何實現(xiàn)移動圓盤的操作呢？當 n=1時，問題比較簡單，只要將編號為即可；當n>1時，需利用塔座Y作輔助塔座,上述原則)移至塔座Y上，則可先將編號為(依照上述原則)移至塔座Z上。而如何將特征屬性的問題，只是問題的規(guī)模小個 1,塔問題的函數(shù)。voidhanoi(intn,charx,chary,charz)/*若能設(shè)法將壓在編號為n的圓盤從塔座X移至塔座1的圓盤從塔座X直接移動到塔座Z上n的圓盤上的n-1個圓盤從塔座X(依照Z上，然后再將塔座Y上的n-1個圓盤n-1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同如何實現(xiàn)移動圓盤的操作呢？當 n=1時，問題比較簡單，只要將編號為即可；當n>1時，需利用塔座Y作輔助塔座,上述原則)移至塔座Y上，則可先將編號為(依照上述原則)移至塔座Z上。而如何將特征屬性的問題，只是問題的規(guī)模小個 1,塔問題的函數(shù)。voidhanoi(intn,charx,chary,charz)/*若能設(shè)法將壓在編號為n的圓盤從塔座X移至塔座1的圓盤從塔座X直接移動到塔座Z上n的圓盤上的n-1個圓盤從塔座X(依照Z上，然后再將塔座Y上的n-1個圓盤n-1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同因此可以用同樣方法求解。 由此可得如下算法所示的求解 n階Hanoi按規(guī)則搬到塔座Z上,可用作輔助塔座將塔座X上按直徑由小到大且至上而下編號為 1至n的n個圓盤*/if(n==1)move(x,1,z);/*else{hanoi(n-1,x,z,y);/*move(x,n,z);/*hanoi(n-1,y,x,z);/*}將編號為1的圓盤從X移動Z*/將X上編號為1至n-1的圓盤移到Y(jié),Z作輔助塔*/將編號為n的圓盤從X移到Z*/將Y上編號為1至n-1的圓盤移動到Z,X作輔助塔*/算法：3.5下面給出三個盤子搬動時hanoi(2,A,C,B):hanoi(1,A,B,C)move(A->B)hanoi(1,C,A,B)hanoi(3,A,B,C)遞歸調(diào)用過程:號搬到move(A->C)C12號搬到號搬到move(C->B)B3號搬到A號搬到C號搬到Cmin~\mmhanoi(1,B,C,A)move(B->A)move(B->c)2hanoi(1,A,B,C)move(A->C)1號搬到Cmove(A->c)hanoi(2,B,A,C):3)遞歸問題的優(yōu)點通過上面的例子可看出，遞歸既是強有力的數(shù)學(xué)方法， 也是程序設(shè)計中一個很有用的工具。 其特點是對遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正確性容易證明。遞歸算法求解問題的要素遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。 遞歸算法的要點如下：問題具有類同自身的子問題的性質(zhì)， 被定義項在定義中的應(yīng)用具有更小的尺度。被定義項在最小尺度上有直接解。設(shè)計遞歸算法的方法是：尋找方法，將問題化為原問題的子問題求解(例n!=n*(n-1)!)。設(shè)計遞歸出口，確定遞歸終止條件(例求解n!時，當n=1時，n!=1)。作業(yè)2:1:圖3.72:算法3.5、種子填充算法、兩種算法求解n! 第 5-6課時 3.4隊列隊列的定義隊列(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以

隊列具有先進先出(FistInFistOut,縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾 (rear),允許刪除的一端則稱為隊頭 (front)