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

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

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

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

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

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

D

BCHFAGE指針域4313NULL371925圖2.5單鏈表的示例圖 a ah圖2.6單鏈表的邏輯狀態(tài)⑻帶頭結(jié)點(diǎn)的空單橙表⑻帶頭結(jié)點(diǎn)的空單橙表㈤帚頭第點(diǎn)的單微表單鏈表可以由頭指針唯一確定。圖單鏈表可以由頭指針唯一確定。圖2.7帶頭結(jié)點(diǎn)單鏈表圖示單鏈表的存儲(chǔ)結(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é)點(diǎn)的單鏈表，則指向單鏈表的頭結(jié)點(diǎn)）；指向新申請的結(jié)點(diǎn)s->dits=c^㈤插入第一個(gè)結(jié)點(diǎn)（b）申謂新站點(diǎn)并賦值⑻插入第小元素為結(jié)構(gòu)指針類型*/是一個(gè)結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn) （對(duì)于帶,若L=NULL（對(duì)于帶頭結(jié)點(diǎn)的單鏈表為 L->next=NULL）,則表示單鏈表為一個(gè)空表，其長度為 0。若不是空表，則可以通過頭指針訪問表中結(jié)點(diǎn)，找到要訪問的所有結(jié)點(diǎn)的數(shù)據(jù)信息。對(duì)于帶頭結(jié)點(diǎn)的單鏈表 L,p=L->next指向表中的第一個(gè)結(jié)點(diǎn) a1,即p->data=a1,而p->next->data=a2。其余依此類推。單鏈表上的基本運(yùn)算.建立單鏈表圖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)尾插法建表⑥地人第一個(gè)結(jié)點(diǎn)指向新申請的結(jié)點(diǎn)空間>efata=￡：②⑥地人第一個(gè)結(jié)點(diǎn)指向新申請的結(jié)點(diǎn)空間>efata=￡：②『出始終指向單攝表的表尾曲插入第二個(gè)結(jié)點(diǎn)0）申請新結(jié)點(diǎn)弁賦值圖2.9尾插法建表圖示.查找在單鏈表中，由于每個(gè)結(jié)點(diǎn)的存儲(chǔ)位置都放在其前一結(jié)點(diǎn)的 next域中，因而即使知道被訪問結(jié)點(diǎn)的序號(hào) i,也不能像順序表那樣直接按序號(hào) i訪問一維數(shù)組中的相應(yīng)元素，實(shí)現(xiàn)隨機(jī)存取，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長度為 n,要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針 L出發(fā)，從頭結(jié)點(diǎn)（L->next）開始順著鏈域掃描， 用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，初值指向頭結(jié)點(diǎn)，用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)（初值為 0）,當(dāng)上=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。查找元素的算法：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é)點(diǎn)的單鏈表L中第i個(gè)位置插入一個(gè)數(shù)據(jù)元素e,需要首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)并由指針pre指示，然后申請一個(gè)新的結(jié)點(diǎn)并由指針 s指示，其數(shù)據(jù)域的值為e,并修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向s,然后使s結(jié)點(diǎn)的指針域指向原第i個(gè)結(jié)點(diǎn)。插入：s->next=p->next; p->next=s;口】申清新的堵點(diǎn)⑷尋找第17個(gè)結(jié)點(diǎn)㈤描入?與橫鏈：“冷I斷

鐫捅鼠

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

鐫捅鼠

pre->next='3f 圖2.10 在單鏈表第i個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的過程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)刪除并釋放糊點(diǎn)圖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課時(shí) 循環(huán)鏈表是單鏈表的另一種形式，它是一個(gè)首尾相接的鏈表。其特點(diǎn)是將單鏈表循環(huán)鏈表(CircularLinkedList)是單鏈表的另一種形式，它是一個(gè)首尾相接的鏈表。其特點(diǎn)是將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由 NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)， 就得到了單鏈形式的循環(huán)鏈表， 并稱為循環(huán)單鏈表。類似地，還有多重鏈的循環(huán)鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)都被鏈在一個(gè)環(huán)上，多重循為循環(huán)單鏈表。類似地，還有多重鏈的循環(huán)鏈表。環(huán)鏈表則是將表中的結(jié)點(diǎn)鏈在多個(gè)環(huán)上。 為了使某些操作實(shí)現(xiàn)起來方便，在循環(huán)單鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。L㈤帶其堵點(diǎn)的空循環(huán)碌L(b)常頭轉(zhuǎn)點(diǎn)的隨環(huán)，單褲表的一般甲式L㈤帶其堵點(diǎn)的空循環(huán)碌L(b)常頭轉(zhuǎn)點(diǎn)的隨環(huán)，單褲表的一般甲式*(rear->nrsl) *TClf(0采用尾指葉的福環(huán)單循表的股形式圖2.12 帶頭結(jié)點(diǎn)循環(huán)單鏈表雙向鏈表O(n)。如果循環(huán)單鏈表的出現(xiàn)，雖然能夠?qū)崿F(xiàn)從任一結(jié)點(diǎn)出發(fā)沿著鏈能找到其前驅(qū)結(jié)點(diǎn)，但時(shí)間耗費(fèi)是

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

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

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