數(shù)據(jù)結(jié)構(gòu)與算法 課件全套 機(jī)械自考版 第1-8章 緒論、線性表-查找

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第一章緒論學(xué)習(xí)目標(biāo)了解數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)應(yīng)用領(lǐng)域中的作用掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語(yǔ)，了解4類基本的數(shù)據(jù)結(jié)構(gòu)，理解邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的含義及相互關(guān)系，了解數(shù)據(jù)結(jié)構(gòu)的4種基本存儲(chǔ)方法掌握抽象數(shù)據(jù)類型的表示與描述，能夠用抽象數(shù)據(jù)類型表示實(shí)際問題掌握算法的基本概念及重要特性，能夠使用類C語(yǔ)言描述算法掌握算法評(píng)估和復(fù)雜性度量的基本概念，能夠?qū)?jiǎn)單算法進(jìn)行復(fù)雜性評(píng)估理解算法的基本設(shè)計(jì)策略的特點(diǎn)，使用基本的算法策略實(shí)現(xiàn)簡(jiǎn)單程序本章主要內(nèi)容基本概念和術(shù)語(yǔ)12算法和算法分析3算法設(shè)計(jì)策略簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)專業(yè)的必修課程之一，在課程體系中占據(jù)非常重要的地位，起著承上啟下的作用，是學(xué)習(xí)其他計(jì)算機(jī)專業(yè)課程的基礎(chǔ)本章將介紹數(shù)據(jù)結(jié)構(gòu)的基本概念，還將介紹算法及其特性，介紹時(shí)間、空間復(fù)雜度的概念，在此基礎(chǔ)上，介紹對(duì)算法進(jìn)行復(fù)雜度評(píng)估的基本方法第一節(jié)

基本概念和術(shù)語(yǔ)需求推動(dòng)技術(shù)的發(fā)展，程序設(shè)計(jì)語(yǔ)言內(nèi)置的數(shù)據(jù)類型越來(lái)越多樣，提供的處理手段也越來(lái)越方便快捷當(dāng)需要方便地處理眾多同類型的數(shù)據(jù)時(shí)，出現(xiàn)了數(shù)組，“結(jié)構(gòu)”的雛形顯現(xiàn)了數(shù)組——例如，可以表示多個(gè)同類型的數(shù)據(jù)二元組——例如，可以表示復(fù)數(shù)記錄——例如，可以表示學(xué)生信息經(jīng)典著作數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立的一門課程已經(jīng)有很多年了世界著名的計(jì)算機(jī)科學(xué)家DonaldE.Knuth教授的巨著《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》著名的計(jì)算機(jī)科學(xué)家N.Wirth編寫的《算法+數(shù)據(jù)結(jié)構(gòu)=程序》

基本概念和術(shù)語(yǔ)

20世紀(jì)80年代以后出現(xiàn)了抽象數(shù)據(jù)類型概念數(shù)據(jù)對(duì)數(shù)據(jù)進(jìn)行操作的定義但不涉及操作的具體實(shí)現(xiàn)數(shù)據(jù)是指所有能輸入計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)的集合數(shù)據(jù)是各種各樣的復(fù)雜的數(shù)據(jù)往往由簡(jiǎn)單的數(shù)據(jù)構(gòu)成構(gòu)成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素還可以細(xì)分為數(shù)據(jù)項(xiàng)

學(xué)生信息示例——“線性”的關(guān)系某班30名同學(xué)的基本信息學(xué)號(hào)姓名性別出生日期籍貫M2022103001王義平男2004.11.22山東M2022103002陸東男2004.02.05河南M2022103003李曉敏女2005.01.15江蘇┇┇┇┇┇M2022103030楊志強(qiáng)男2004.10.30陜西章節(jié)目錄示例——“上下級(jí)”的關(guān)系“結(jié)構(gòu)”是什么數(shù)據(jù)元素之間的相互關(guān)系構(gòu)成結(jié)構(gòu)，帶有結(jié)構(gòu)特性的數(shù)據(jù)元素集合構(gòu)成數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu)。指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示及存儲(chǔ)方式數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯上描述數(shù)據(jù)，表明數(shù)據(jù)元素之間的關(guān)系是什么樣的，這與數(shù)據(jù)的存儲(chǔ)方式無(wú)關(guān)，既獨(dú)立于計(jì)算機(jī)，也獨(dú)立于程序設(shè)計(jì)語(yǔ)言數(shù)據(jù)的最小不可分割的單位是數(shù)據(jù)項(xiàng)邏輯上相關(guān)的、具有物理意義的若干數(shù)據(jù)項(xiàng)構(gòu)成一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素作為一個(gè)完整的對(duì)象（整體）是構(gòu)成數(shù)據(jù)的基本單位

基本的數(shù)據(jù)結(jié)構(gòu)基本的數(shù)據(jù)結(jié)構(gòu)包括4類集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)示意圖

集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)常用的存儲(chǔ)方法

順序存儲(chǔ)方法鏈?zhǔn)酱鎯?chǔ)方法索引存儲(chǔ)方法散列存儲(chǔ)方法例1-3下列關(guān)于順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，正確的是（A）。A．順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定連續(xù)B．順序存儲(chǔ)結(jié)構(gòu)只用于線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只用于非線性結(jié)構(gòu)C．順序存儲(chǔ)結(jié)構(gòu)一定比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間D．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間抽象數(shù)據(jù)類型除了程序設(shè)計(jì)語(yǔ)言中提供的基本類型外，還可以定義抽象意義下的類型，并為該類型定義一組相關(guān)的操作。這樣定義的數(shù)據(jù)類型稱為抽象數(shù)據(jù)類型（AbstractDataType，ADT）抽象數(shù)據(jù)類型的定義包括類型的名字及對(duì)各個(gè)操作的刻畫，也就是要明確“做什么”對(duì)于每個(gè)操作，要規(guī)定操作的名字、操作執(zhí)行的前提條件、輸入和輸出分別是什么等等。每個(gè)操作通常表示為一個(gè)函數(shù)或是方法定義抽象數(shù)據(jù)類型Triangle

第二節(jié)

算法和算法分析算法的概念在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域幾乎無(wú)處不在算法的設(shè)計(jì)與實(shí)現(xiàn)往往處于核心地位算法的思想是計(jì)算機(jī)程序的靈魂算法規(guī)定的流程決定著程序的執(zhí)行步驟算法的基本概念算法（Algorithm）概念的出現(xiàn)與計(jì)算機(jī)及程序設(shè)計(jì)無(wú)關(guān)使用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)最大公因子的歐幾里得（Euclid）算法，早在2300多年前就提出了，這是目前已知的最古老的算法算法定義定義1-1算法是一個(gè)由若干確定的（無(wú)二義性的）、可執(zhí)行的步驟組成的肯定能夠終止的有序步驟集合算法是描述一個(gè)問題的求解過(guò)程，它由一系列解決問題的清晰指令構(gòu)成可以使用自然語(yǔ)言表示可以使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言表示可以混合使用自然語(yǔ)言與計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言溫度轉(zhuǎn)換將攝氏溫標(biāo)值C轉(zhuǎn)換為華氏溫標(biāo)值F已知計(jì)算公式為：F=(9/5)C+32轉(zhuǎn)換的過(guò)程可以這樣描述輸入一個(gè)攝氏溫標(biāo)值CC乘以常數(shù)9/5（或1.8）前一步的乘積與常數(shù)32相加，得到F輸出結(jié)果F，即轉(zhuǎn)換后的華氏溫標(biāo)值溫度轉(zhuǎn)換算法的程序算法特性算法必須滿足如下的5個(gè)重要特性輸入：有0或多個(gè)輸入值輸出：有1或多個(gè)輸出值有窮性：一個(gè)算法必須在執(zhí)行有窮步驟之后結(jié)束確定性：算法的每一個(gè)步驟必須是有確切含義的可行性：算法中要做的運(yùn)算都是相當(dāng)基本的、能夠精確進(jìn)行的算法的評(píng)估和復(fù)雜性度量算法必須要正確，所以算法的正確性成為評(píng)判算法的首要指標(biāo)還要評(píng)判算法的其他方面，包括它的執(zhí)行效率時(shí)間復(fù)雜度空間復(fù)雜度時(shí)間復(fù)雜度

計(jì)算機(jī)中最重要的資源之一是CPU，顯然，花費(fèi)的時(shí)間與處理的數(shù)據(jù)個(gè)數(shù)有很大的關(guān)系，這個(gè)數(shù)據(jù)個(gè)數(shù)稱為問題規(guī)模，也稱問題大小。執(zhí)行算法花費(fèi)的時(shí)間表示為問題規(guī)模的一個(gè)函數(shù)統(tǒng)計(jì)一個(gè)程序執(zhí)行期間需要執(zhí)行的語(yǔ)句總數(shù)，并且約定，程序設(shè)計(jì)語(yǔ)言中一條基本語(yǔ)句的執(zhí)行時(shí)間為1個(gè)單位時(shí)長(zhǎng)時(shí)間復(fù)雜度一個(gè)算法的時(shí)間效率可以用問題規(guī)模及關(guān)鍵的處理步驟的多少來(lái)定義將算法的運(yùn)行效率表示為問題規(guī)模n的一個(gè)解析式，對(duì)于規(guī)模為n的問題，解析式計(jì)算的值，應(yīng)該是算法處理的步驟數(shù)將關(guān)于n的這個(gè)解析式稱為增長(zhǎng)函數(shù)，表示為T(n)對(duì)于一個(gè)具體的算法，其增長(zhǎng)函數(shù)是一個(gè)近似的表達(dá)式查找給定數(shù)組中的最大值

當(dāng)數(shù)組中元素個(gè)數(shù)為10n時(shí)，執(zhí)行的語(yǔ)句個(gè)數(shù)最多為10n+1，即問題規(guī)模擴(kuò)大10倍，所花費(fèi)的時(shí)間也增大約10倍程序段sum=0; //賦初值for(i=0;i<n;i++) //對(duì)每個(gè)n for(j=0;j<n;j++) //對(duì)每個(gè)n sum++; //累加returnsum;主體是一個(gè)二重循環(huán)，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)都執(zhí)行n次，所以sum++的總執(zhí)行次數(shù)為n2，語(yǔ)句執(zhí)行的總數(shù)是n2+2，即增長(zhǎng)函數(shù)T(n)=n2+2當(dāng)問題規(guī)模擴(kuò)大10倍時(shí)，所花的時(shí)間需要增加約100倍漸近時(shí)間復(fù)雜度考查增長(zhǎng)函數(shù)時(shí)，只關(guān)心增長(zhǎng)函數(shù)表達(dá)式中的主項(xiàng)，并且不再考慮主項(xiàng)的系數(shù)表達(dá)式的主項(xiàng)使用記號(hào)O來(lái)表示例1.4中增長(zhǎng)函數(shù)表示為O(n)例1.5中增長(zhǎng)函數(shù)表示為O(n2)這稱為漸近時(shí)間復(fù)雜度，也稱為算法的階定義定義1-2稱（復(fù)雜度）函數(shù)T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常數(shù)c>0與n0，當(dāng)n>n0時(shí)有T(n)≤cf(n)T1(n)=(n+1)/2=O(n2)T2(n)=3n2+4n+5=O(n3)當(dāng)然T1(n)=O(n2)，T2(n)=O(n3)也是對(duì)的，但一般取最低階表示T(n)=O(f(n))說(shuō)明T(n)的階不大于f(n)的階定義定義1-3稱（復(fù)雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0，當(dāng)n>n0時(shí)有T(n)≥cf(n)T1(n)=(n+1)/2=Ω(n)T2(n)=3n2+4n+5=Ω(n2)當(dāng)然T1(n)=Ω(1)，T2(n)=Ω(n)，T2(n)=Ω(nlogn)也都是對(duì)的，同樣地，取它們之中的最高階T(n)=Ω(f(n))說(shuō)明T(n)的階不小于f(n)的階大O表示法和大Ω表示法使我們能夠描述某一算法的上限（如果能找到某一類輸入下開銷最大的函數(shù)）和下限（如果能找到某一類輸入下開銷最小的函數(shù)）當(dāng)上、下限相等時(shí)，可用Θ表示法。如果一種算法既是O(f(n))，又是Ω(f(n))，則稱其是Θ(f(n))的若增長(zhǎng)函數(shù)不隨算法問題規(guī)模變化，則增長(zhǎng)函數(shù)稱為O(1)階，或稱常數(shù)復(fù)雜度與問題規(guī)模成正比的問題求解算法稱為線性操作許多算法具有l(wèi)og2n對(duì)數(shù)復(fù)雜度其他的算法有n的某次冪的多項(xiàng)式復(fù)雜度，如O(n2)或O(n3)更壞的算法是指數(shù)復(fù)雜度，n是指數(shù)，如O(2n)一些增長(zhǎng)函數(shù)的漸近時(shí)間復(fù)雜增長(zhǎng)函數(shù)階時(shí)間復(fù)雜度T(n)=17O(1)常數(shù)T(n)=20n-4O(n)線性T(n)=12nlogn+100nO(nlogn)線性對(duì)數(shù)T(n)=3n2+5n-2O(n2)多項(xiàng)式（平方）T(n)=2n+18n2+3nO(2n)指數(shù)示例

上述程序的時(shí)間復(fù)雜度是（

）A．O(log2n) B．O(n)C．O(nlog2n) D．O(n2)解：答案是B程序段intx=m;while(x>1){ x=x/2;}其中m>1，則時(shí)間復(fù)雜度為（

）A．O(logm) B．O(m2)C．O(m1/2)

D．O(m1/3)解：答案是A

若處理器速度增長(zhǎng)10倍

算法時(shí)間復(fù)雜度提升前最大問題規(guī)模提升后最大問題規(guī)模A1O(n)s110s1A2O(n2)s23.16s2A3O(n3)s32.15s3A4O(2n)s4s4+3.3除了要評(píng)判算法的時(shí)間復(fù)雜度外，算法在運(yùn)行過(guò)程中臨時(shí)占用的空間大小也要考慮，這稱為空間復(fù)雜度。一般地，空間復(fù)雜度也表示為問題規(guī)模的一個(gè)函數(shù)?？紤]空間存儲(chǔ)量時(shí)，算法代碼占用的空間、算法中初始數(shù)據(jù)占用的存儲(chǔ)空間，都不包含在內(nèi)第三節(jié)

算法設(shè)計(jì)策略簡(jiǎn)介算法可以分為多種不同的類型，每種類型都有特定的應(yīng)用場(chǎng)景和解決問題的方法設(shè)計(jì)算法時(shí)，可以配合采用一些設(shè)計(jì)策略，使得算法的實(shí)現(xiàn)更方便設(shè)計(jì)策略有時(shí)也可以稱為設(shè)計(jì)方法，是指在解決特定問題時(shí)所采用的一類方法算法分為遞推法、迭代法、遞歸法、貪心法、分治法、動(dòng)態(tài)規(guī)劃法等遞推法遞推法是一種直接求解的算法設(shè)計(jì)策略，利用問題本身所具有的一種遞推關(guān)系進(jìn)行求解。找到問題本身的遞推關(guān)系是問題求解的前提遞推法的思想是，根據(jù)遞推關(guān)系，能從已求得的問題規(guī)模為1,2,…,i-1的一系列解，構(gòu)造出問題規(guī)模為i的解。求解規(guī)模為i的解時(shí)，有時(shí)可能僅需規(guī)模為1,2,…,i-1的系列解中的一部分，而不是全部示例

由遞推公式可計(jì)算出數(shù)列的第三項(xiàng)，為2再由第二項(xiàng)和第三項(xiàng)，得到第四項(xiàng)的值3再由第三項(xiàng)和第四項(xiàng)，得到第五項(xiàng)的值5以此類推得到數(shù)列的前10項(xiàng)為：1,1,2,3,5,8,13,21,34,55程序迭代法是一種直接求解的方法，往往需要建立迭代關(guān)系式即根據(jù)前一個(gè)值推出下一個(gè)值的公式初始時(shí)設(shè)定初始值（原值），然后根據(jù)迭代關(guān)系式和原值，求出新值，并用新值替代原值迭代過(guò)程不能無(wú)限進(jìn)行下去或者設(shè)定一個(gè)迭代次數(shù)，當(dāng)達(dá)到這個(gè)次數(shù)時(shí)迭代過(guò)程停止或者設(shè)定一個(gè)結(jié)束條件，當(dāng)滿足這個(gè)條件時(shí)，迭代過(guò)程停止程序遞歸法

貪心法貪心算法也稱貪婪算法，這是一種通過(guò)每一步選擇局部最優(yōu)解來(lái)達(dá)到整體最優(yōu)解的算法，適用于求某些最優(yōu)解問題求解過(guò)程中，一步一步地進(jìn)行，根據(jù)當(dāng)前的情況選擇最優(yōu)的可能實(shí)際上，這個(gè)最優(yōu)是在當(dāng)前條件下的最優(yōu)，稱為局部最優(yōu)第四章構(gòu)造哈夫曼樹的過(guò)程采用了貪心法策略，第六章求最小生成樹的兩個(gè)算法也采用了貪心法求解分治法當(dāng)求解一個(gè)輸入規(guī)模為n并且n的取值又很大的問題時(shí)，可以把這個(gè)大規(guī)模的問題分解為若干個(gè)規(guī)模更小且可以獨(dú)立求解的問題，然后把各個(gè)小問題的解進(jìn)行合并，得到原問題的解。這就是分治法的思想一般來(lái)說(shuō)，分治法的求解過(guò)程分為三個(gè)階段即劃分、求解小問題及小問題解的合并第七章介紹的快速排序和歸并排序都采用了分治法求解它們是將大問題分解為2個(gè)小問題動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃算法是求多階段決策過(guò)程最優(yōu)化的一種方法，它將問題的整體按時(shí)間或空間的特征分成若干個(gè)前后銜接的階段，把多階段決策問題表示為前后有關(guān)的一系列單階段決策問題，然后逐個(gè)求解，從而求出整個(gè)問題的最優(yōu)決策動(dòng)態(tài)規(guī)劃法強(qiáng)調(diào)了時(shí)間和空間的連續(xù)性求解最大子序列和問題就是采用動(dòng)態(tài)規(guī)劃法求解的典型示例。給定一個(gè)整數(shù)數(shù)組A，找到一個(gè)具有最大和的連續(xù)子數(shù)組（至少含有一個(gè)元素），返回該最大和例如，A={-2,1,-3,4,-1,2,1,-5,4}得到的最大和是6相應(yīng)的子數(shù)組是{4,-1,2,1}，從A[3]到A[6]程序ThankYou!全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第二章線性表學(xué)習(xí)目標(biāo)理解線性表的相關(guān)概念，了解其邏輯定義及基本操作，理解線性表數(shù)據(jù)元素之間的邏輯關(guān)系掌握線性表的順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式，了解各自的特點(diǎn)掌握順序表及鏈表基本操作的實(shí)現(xiàn)，并能進(jìn)行復(fù)雜度分析掌握靜態(tài)鏈表基本操作的實(shí)現(xiàn)，并能進(jìn)行復(fù)雜度分析能夠設(shè)計(jì)與線性表相關(guān)的數(shù)據(jù)結(jié)構(gòu)，靈活運(yùn)用線性表的基本操作，設(shè)計(jì)算法解決與線性表相關(guān)的實(shí)際問題本章主要內(nèi)容線性表的定義和基本操作12線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)3線性表的順序存儲(chǔ)及實(shí)現(xiàn)進(jìn)一步討論兩種基本實(shí)現(xiàn)方式4單鏈表的應(yīng)用5第一節(jié)

線性表的定義和基本操作線性表是一種線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，存在著唯一的“第一個(gè)”元素、唯一的“第二個(gè)”元素，依此類推線性表中各個(gè)元素依次排列例1-1中給出的某班30名同學(xué)的基本信息（表1-1），就可以組成一個(gè)線性表，可以按照學(xué)號(hào)排列名單

定義定義2-1一個(gè)線性表（linearlist）是由同類型數(shù)據(jù)元素構(gòu)成的有限序列由n(n≥0)個(gè)元素組成的線性表L，可以表示為L(zhǎng)=(a0,a1,…,an-1)這里，ai(0≤i≤n-1)即是線性表中的數(shù)據(jù)元素，也稱為表項(xiàng)線性表中所有數(shù)據(jù)元素都必須是相同類型的數(shù)據(jù)元素的次序就是它們?cè)诒碇械呐帕写涡虻谝粋€(gè)元素是a0，稱為表頭或開始元素第n個(gè)也即最后一個(gè)元素是an-1，稱為表尾或終端元素元素的個(gè)數(shù)n稱為表長(zhǎng)n=0時(shí)稱為空表，記為()

示例

例2-1將例1-1的學(xué)生基本信息表表示為線性表StudentStudent=

((M2022103001王義平男2004.11.22山東),

(M2022103002陸東男2004.02.05河南),…,

(M2022103030楊志強(qiáng)男2004.10.30陜西))

線性表中常使用非負(fù)整數(shù)表示各元素的位置表頭a0的位置為0a1的位置為1ai(0≤i≤n-1)的位置為i對(duì)于元素ai(1≤i≤n-1)，元素aj(0≤j<i)稱為ai的前驅(qū)，其中元素ai-1稱為ai的直接前驅(qū)對(duì)于元素ai(0≤i≤n-2)，元素aj(i<j≤n-1)稱為ai的后繼，其中元素ai+1稱為ai的直接后繼

在不引起歧義的情況下，直接前驅(qū)可以簡(jiǎn)稱為前驅(qū)，直接后繼可以簡(jiǎn)稱為后繼“線性”的含義和特點(diǎn)除表頭a0外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)除表尾an-1外，每個(gè)元素有且僅有一個(gè)直接后繼線性表中各元素的次序是固有的，即元素ai(1≤i≤n-2)排在ai-1之后，且排在元素ai+1之前

如果線性表中各元素的值可以進(jìn)行比較，并且表中元素的值按位置順序遞增或遞減排列，即按值的“大小”有序排列，則線性表稱為有序表表中元素的值不滿足按位置順序遞增或遞減關(guān)系的線性表稱為無(wú)序表

線性表有3個(gè)特點(diǎn)，分別是各元素屬于同一個(gè)類型元素個(gè)數(shù)是有限的各元素之間不一定有大小關(guān)系，但一定有次序關(guān)系

例2-2寫出10以內(nèi)（不含10）的非負(fù)偶數(shù)組成的線性表10以內(nèi)（不含10）的非負(fù)偶數(shù)共有5個(gè)，可以寫出如下的不同形式L1=(0,2,4,6,8) //遞增有序表L2=(8,6,4,2,0) //遞減有序表L3=(2,6,4,0,8) //無(wú)序表線性表的基本操作線性表中有幾個(gè)基本操作會(huì)涉及到位置position

LinearList中定義的函數(shù)都有返回值LinearList中定義的操作都有返回值，有些返回值代表操作的執(zhí)行結(jié)果，另外一些僅表示操作是否已正確執(zhí)行。例如length返回的是線性表的當(dāng)前長(zhǎng)度，即線性表所含元素的個(gè)數(shù)find返回的是要查找的元素x在表中第一次出現(xiàn)的位置。如果表中不包含x，則返回-1當(dāng)表為空時(shí)，isEmpty返回1，否則返回0。當(dāng)表已滿時(shí)，isFull返回1，否則返回0操作的幾個(gè)示例序號(hào)操作操作結(jié)果解釋1initList(&s)()創(chuàng)建空線性表s2for(i=0;i<6;i++)insertList(&s,i,2*i)(0,2,4,6,8,10)在空表s的表尾處依次插入6個(gè)值3removeList(&s,3,&x)(0,2,4,8,10)刪除位置3的值并由x返回該值4setValue(&s,3,-10)(0,2,4,-10,10)給位置3的元素賦值-105find(&s,10)返回值是4在s中查找10，10在位置46find(&s,9)返回值是-1在s中查找9，查找失敗第二節(jié)

線性表的順序存儲(chǔ)及實(shí)現(xiàn)操作的具體實(shí)現(xiàn)需要依賴于線性表的存儲(chǔ)結(jié)構(gòu)?？梢允褂庙樞虼鎯?chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式保存線性表，從而得到線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)使用數(shù)組保存線性表中的各元素，相應(yīng)的線性表稱為順序表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用鏈表保存線性表中的各元素，相應(yīng)的線性表稱為鏈表順序表順序存儲(chǔ)的基本思想是使用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)各個(gè)元素，將線性表中的各數(shù)據(jù)元素，按照其邏輯次序，依次保存在數(shù)組的各個(gè)單元中線性表中邏輯上相鄰的兩個(gè)元素，保存在數(shù)組相鄰的兩個(gè)單元中

分配一個(gè)多大的數(shù)組是個(gè)挑戰(zhàn)順序表的顯著特點(diǎn)

分配了數(shù)組空間后，將線性表中的n個(gè)元素依次保存在數(shù)組中，從表頭至表尾的各個(gè)元素分別對(duì)應(yīng)下標(biāo)0到下標(biāo)n-1的位置數(shù)組是內(nèi)存中一片連續(xù)的空間，相鄰的兩個(gè)單元在內(nèi)存中的實(shí)際地址也是相鄰的，這表明，線性表中邏輯上相鄰的兩個(gè)元素，其存儲(chǔ)地址也是相鄰的存儲(chǔ)示意圖假設(shè)線性表L=(a0,a1,a2,a3,a4,a5)，每個(gè)元素需要占用2個(gè)字節(jié)，分配一個(gè)含8個(gè)元素的數(shù)組A保存LA在內(nèi)存中的示意圖數(shù)組下標(biāo)與線性表元素的位置相對(duì)應(yīng)線性表元素依次存放的特性，決定著表中元素i（i≥0）存儲(chǔ)在數(shù)組的下標(biāo)i處表頭元素保存在位置0處，這個(gè)位置也稱為數(shù)組的首地址只要給定數(shù)組下標(biāo)，就能立即計(jì)算出相應(yīng)元素的存儲(chǔ)地址，并據(jù)此訪問該元素地址計(jì)算

設(shè)LOC(ai)表示元素ai的存儲(chǔ)首地址，每個(gè)元素需占用d個(gè)存儲(chǔ)單元，則有 LOC(ai)=LOC(ai-1)+d進(jìn)一步地有 LOC(ai)=LOC(a0)+i

dLOC(a0)即是數(shù)組的首地址例2-4

設(shè)順序表的每個(gè)元素占8個(gè)存儲(chǔ)單元。第1個(gè)元素的存儲(chǔ)首地址為100，則第6個(gè)元素占用的最后一個(gè)存儲(chǔ)單元的地址是（）A．132 B．139 C．140 D．147解：答案是Dd=8，LOC(a0)=100，第6個(gè)元素是a5LOC(a5)=LOC(a0)+5

8=100+40=140即第6個(gè)元素占用從140開始的8個(gè)存儲(chǔ)單元，那么最后一個(gè)存儲(chǔ)單元是147插入和刪除設(shè)給定一個(gè)順序表，初始時(shí)含有5個(gè)元素。在位置2插入元素27，然后刪除位置3的元素初始順序表在位置2插入元素27刪除位置3的元素

11523196

…

1152723196

…

11527196

…

程序中使用的常量#defineTRUE1#defineFALSE0#defineERROR-1#ifndefmaxSize#definemaxSize100#endif順序表基本運(yùn)算的實(shí)現(xiàn)順序表的定義構(gòu)造空表及清空表判表空、判表滿、求表長(zhǎng)插入新元素插入操作中移動(dòng)元素的平均次數(shù)為n/2刪除操作刪除操作中移動(dòng)元素的平均次數(shù)為(n-1)/2賦值、取值操作查找測(cè)試?yán)?-5設(shè)有順序表L，表長(zhǎng)為n，保存在數(shù)組A中。實(shí)現(xiàn)算法將L逆置，即 L=(a0,a1,…,an-2,an-1)變?yōu)?L=(an-1,an-2,…,a1,a0)將A[0]與A[n-1]進(jìn)行交換，然后將A[1]與A[n-2]進(jìn)行交換，依此類推，當(dāng)交換到L中間元素時(shí)，算法結(jié)束算法實(shí)現(xiàn)第三節(jié)

線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)線性表還可以使用鏈?zhǔn)酱鎯?chǔ)方式保存，即線性表中的各個(gè)元素保存在各自的存儲(chǔ)空間中，形成一個(gè)個(gè)的結(jié)點(diǎn)這些結(jié)點(diǎn)在內(nèi)存中的地址不要求是相鄰的，它們之間通過(guò)指針連接起來(lái)以這種方式保存的線性表稱為鏈表每個(gè)結(jié)點(diǎn)中包含元素值和指向其他結(jié)點(diǎn)的指針，指針的個(gè)數(shù)可以是一個(gè)，也可能是兩個(gè)，從而形成不同形式的鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種動(dòng)態(tài)靈活的存儲(chǔ)方式，它不要求預(yù)先分配一塊連續(xù)的存儲(chǔ)空間，而是按需分配，隨時(shí)需要隨時(shí)分配同時(shí)不要求分配的空間必須是相鄰的，而是由系統(tǒng)決定分配的具體位置，既可以相鄰也可以不相鄰所以在執(zhí)行插入及刪除操作時(shí)，不再需要移動(dòng)元素以保證存儲(chǔ)空間的相鄰性單鏈表單鏈表是由一組動(dòng)態(tài)分配的結(jié)點(diǎn)形成的鏈表，每個(gè)結(jié)點(diǎn)保存線性表中的一個(gè)元素及一個(gè)指針，指針指向保存其后繼元素的結(jié)點(diǎn)保存L的單鏈表示意圖結(jié)點(diǎn)定義單鏈表中結(jié)點(diǎn)及鏈表的定義示例要在上圖所示的單鏈表L的位置2處插入元素E。當(dāng)前指針為p，指向位置2操作步驟是創(chuàng)建一個(gè)新結(jié)點(diǎn)，新結(jié)點(diǎn)中保存值E讓新結(jié)點(diǎn)的next指針指向指針p指向的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)讓當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)另一種定義方式

帶頭結(jié)點(diǎn)的單鏈表插入在帶頭結(jié)點(diǎn)的單鏈表中實(shí)現(xiàn)插入操作刪除在帶頭結(jié)點(diǎn)的單鏈表L中進(jìn)行刪除例2-6在單鏈表L中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，next是結(jié)點(diǎn)的指針域，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行的操作是（）。A．s->next=p->next;p->next=s;B．p->next=s->next;s->next=p;C．p->next=s;s->next=q;D．q->next=s;s->next=p;答案是D。例2-7在帶頭結(jié)點(diǎn)的單鏈表中，若刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作是（）。A．p->next=p->next->next;B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;答案為A。例2-8線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存，則要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以答案為D。單鏈表基本操作的實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表中，始終會(huì)有一個(gè)頭結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)在初始化時(shí)創(chuàng)建清空單鏈表判空單鏈表需要判空，通常不需要判滿求長(zhǎng)度的兩種實(shí)現(xiàn)位置值與指針的轉(zhuǎn)換插入新元素刪除元素賦值、取值查找例2-9返回指針curr指向結(jié)點(diǎn)的位置效率分析如果給定了當(dāng)前指針，則插入操作和刪除操作的時(shí)間復(fù)雜度均為O(1)判定鏈表是否為空的時(shí)間復(fù)雜度也為O(1)清空表操作的時(shí)間復(fù)雜度是O(n)求表長(zhǎng)，兩種實(shí)現(xiàn)分別是O(1)和O(n)查找操作的時(shí)間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的最優(yōu)情況下為O(1)最壞的情況下為O(n)平均來(lái)看是O(n)查找失敗是O(n)循環(huán)鏈表修改單鏈表的定義，將表尾結(jié)點(diǎn)的指針指回頭結(jié)點(diǎn)，從而形成一類新鏈表這樣的鏈表中，從任何一個(gè)結(jié)點(diǎn)出發(fā)沿著指針域的指示可以再回到這個(gè)結(jié)點(diǎn)，好象轉(zhuǎn)了一個(gè)圈一樣，形象地稱這樣的鏈表為循環(huán)鏈表雙向鏈表雙向鏈表中，表結(jié)點(diǎn)及鏈表的定義typedefintELEMType;typedefstructnode{ //雙向鏈表結(jié)點(diǎn)

ELEMTypedata; structnode*next; //指向后繼結(jié)點(diǎn) structnode*prev; //指向前驅(qū)結(jié)點(diǎn)}DouLinkNode;typedefDouLinkNode*DouLinkList; //雙向鏈表typedefintPosition;雙向鏈表雙向鏈表的初始化輔助函數(shù)setCurr插入新元素刪除元素雙向循環(huán)鏈表例2-11在雙向循環(huán)鏈表中，在指針p所指向的結(jié)點(diǎn)（非尾結(jié)點(diǎn)）之后插入指針s指向的結(jié)點(diǎn)，下列選項(xiàng)中，正確的修改指針的語(yǔ)句序列是（）。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案是D。第四節(jié)進(jìn)一步討論兩種基本實(shí)現(xiàn)方式線性表有兩種基本的實(shí)現(xiàn)方式，分別是順序?qū)崿F(xiàn)和鏈?zhǔn)綄?shí)現(xiàn)簡(jiǎn)單地說(shuō)，這兩種實(shí)現(xiàn)方式各有優(yōu)勢(shì)。在不同的情況下，對(duì)應(yīng)于不同的操作，某一種方式可能會(huì)優(yōu)于另外一種。但是哪種方式都不能適用于所有情況示例將下列特性對(duì)應(yīng)到順序表和鏈表中，對(duì)號(hào)入座A．邏輯上相鄰的元素，在內(nèi)存中的存儲(chǔ)位置也相鄰B．不必事先估計(jì)存儲(chǔ)空間C．所需空間與元素個(gè)數(shù)成正比D．插入、刪除時(shí)不需要移動(dòng)元素E．支持隨機(jī)存取F．支持順序存取順序表具有的特性有：A、E和F鏈表具有的特性有：B、C、D和F對(duì)比存儲(chǔ)每個(gè)數(shù)據(jù)元素時(shí)空間比較緊湊，并且是占用連續(xù)的空間數(shù)組的每個(gè)單元中只需要保存數(shù)據(jù)本身，沒有額外的開銷鏈表在每個(gè)結(jié)點(diǎn)上除存儲(chǔ)數(shù)據(jù)元素外，還要留出空間存放指針。單鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)指針，雙向鏈表中每個(gè)結(jié)點(diǎn)包含兩個(gè)指針。這些指針占用的空間稱為結(jié)構(gòu)性開銷為順序表分配的數(shù)組，通常要寬松一些。通常數(shù)組中會(huì)有空閑的空間，此時(shí)并沒能充分利用數(shù)組的全部空間鏈表中占用的空間大小與鏈表中的元素個(gè)數(shù)成正比，分配的結(jié)點(diǎn)是全部使用的當(dāng)線性表的元素個(gè)數(shù)相對(duì)較少時(shí)，鏈表的實(shí)現(xiàn)比順序表的實(shí)現(xiàn)更節(jié)省空間當(dāng)線性表中的元素個(gè)數(shù)接近分配的最大個(gè)數(shù)，數(shù)組的空間存儲(chǔ)效率很高設(shè)n表示線性表中當(dāng)前元素的個(gè)數(shù)，D表示最多可以在數(shù)組中存儲(chǔ)的元素個(gè)數(shù)，也就是數(shù)組的大小，P表示指針的存儲(chǔ)單元大小，E表示數(shù)據(jù)元素的存儲(chǔ)單元大小順序表的空間需求為D

E單鏈表的空間需求為n

(P+E)n的臨界值n=D

E/(P+E)雙向鏈表比單鏈表中每個(gè)結(jié)點(diǎn)的指針數(shù)多1個(gè)。所以雙向鏈表的結(jié)構(gòu)性開銷是單鏈表的2倍例2-12設(shè)保存線性表L的每個(gè)元素需要的空間為10個(gè)字節(jié)，指針占2個(gè)字節(jié)。若采用單鏈表或含30個(gè)元素的數(shù)組保存L。試分析采用哪種方式空間存儲(chǔ)效率更高，僅需要考慮L中元素根據(jù)題意，采用單鏈表保存L時(shí)，每個(gè)結(jié)點(diǎn)占用的空間為12個(gè)字節(jié)例2-12如果采用數(shù)組保存，則需要的空間是30

10=300個(gè)字節(jié)。使用這些空間保存單鏈表中的結(jié)點(diǎn)的話，可以保存300/12=25在不考慮表頭結(jié)點(diǎn)占用的空間的前提下，如果L中元素個(gè)數(shù)少于25個(gè)，則采用單鏈表更省空間如果多于25個(gè)元素，則采用數(shù)組更省空間如果正好是25個(gè)元素，則單鏈表和數(shù)組占用的空間是一樣大的如何選擇當(dāng)線性表元素個(gè)數(shù)變化較大或者未知時(shí)，最好使用鏈表實(shí)現(xiàn)如果用戶事先知道線性表的大致長(zhǎng)度，則使用順序表的空間效率會(huì)更高些還要考慮到，順序表占用的空間是連續(xù)的，而鏈表占用的空間可能是零散的，并且還需要程序員來(lái)管理空間的分配及釋放操作的時(shí)間復(fù)雜度也要考慮在順序表中是直接定位的，可以實(shí)現(xiàn)隨機(jī)訪問，操作的時(shí)間復(fù)雜度是O(1)單鏈表不能隨機(jī)訪問指定的元素，平均時(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度均為O(n)在給出指向鏈表的當(dāng)前指針后，在單鏈表內(nèi)進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度也可以達(dá)到O(1)順序表的插入和刪除操作，平均和最差時(shí)間復(fù)雜度均為O(n)空閑單元鏈表鏈表中，當(dāng)需要在鏈表中插入一個(gè)結(jié)點(diǎn)時(shí)，需要調(diào)用malloc函數(shù)分配相應(yīng)的空間當(dāng)在鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)，需要調(diào)用delete函數(shù)釋放空間。如果在鏈表中頻繁進(jìn)行插入、刪除結(jié)點(diǎn)的操作，則頻繁調(diào)用這些函數(shù)的時(shí)間開銷會(huì)是非?？捎^的可以針對(duì)實(shí)際應(yīng)用的每類鏈表，定義一個(gè)“伙伴鏈表”，表結(jié)點(diǎn)的結(jié)構(gòu)與所使用的鏈表結(jié)構(gòu)一致伙伴鏈表用來(lái)管理暫時(shí)不用的結(jié)點(diǎn)，可以將伙伴鏈表稱為空閑單元鏈表假設(shè)，保存數(shù)據(jù)的單鏈表為L(zhǎng)當(dāng)從鏈表L中刪除一個(gè)結(jié)點(diǎn)時(shí)，將這個(gè)結(jié)點(diǎn)插入到freelist中當(dāng)需要申請(qǐng)新的結(jié)點(diǎn)空間時(shí)，先查看鏈表freelist。如果freelist不空，則從freelist中獲取一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)中保存相應(yīng)的值，并將該結(jié)點(diǎn)插入到L的相應(yīng)位置，否則調(diào)用malloc函數(shù)分配新的空間，并完成后續(xù)的插入操作插入操作的實(shí)現(xiàn)刪除操作的實(shí)現(xiàn)清空表的操作靜態(tài)鏈表靜態(tài)鏈表的特點(diǎn)保存在數(shù)組中兼具順序表和鏈表特性，空間不零碎，插入刪除不需要移動(dòng)元素鏈表及靜態(tài)鏈表在前一個(gè)靜態(tài)鏈表中插入元素E后的靜態(tài)鏈表刪除元素D后的靜態(tài)鏈表類型定義初始化靜態(tài)鏈表清空靜態(tài)鏈表判空、判滿、求表長(zhǎng)的實(shí)現(xiàn)插入操作的實(shí)現(xiàn)刪除操作的實(shí)現(xiàn)例2-14設(shè)雙向靜態(tài)有序鏈表L保存在含8個(gè)元素的數(shù)組A中，表頭結(jié)點(diǎn)在A[0]中。依次執(zhí)行下列操作，畫出每個(gè)操作后得到的數(shù)組A（1）初始化L（2）將序列618,205,103,501,781,910依次插入到L中，建立雙向靜態(tài)有序鏈表（3）從L中依次刪除元素501、103（4）將元素301插入到L中（1）初始化L（2）插入數(shù)據(jù)序列后（3）刪除兩個(gè)元素后（4）再插入一個(gè)元素后第五節(jié)

單鏈表的應(yīng)用創(chuàng)建單鏈表從鍵盤讀入值創(chuàng)建單鏈表從數(shù)組讀入值創(chuàng)建單鏈表查找單鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)如果知道了單鏈表的長(zhǎng)度，那么訪問倒數(shù)第k個(gè)結(jié)點(diǎn)就很容易了。假設(shè)單鏈表長(zhǎng)度為n，則倒數(shù)第k個(gè)結(jié)點(diǎn)即是第n-k+1個(gè)結(jié)點(diǎn)使用兩個(gè)指針front和rear，均從表頭開始同步向表尾方向移動(dòng)初始時(shí)，先令front前進(jìn)k步，當(dāng)個(gè)“排頭兵”這樣front和rear指向的位置相距k個(gè)結(jié)點(diǎn)然后兩個(gè)指針同步前進(jìn)當(dāng)front到達(dá)表尾時(shí)，rear即位于倒數(shù)第k個(gè)結(jié)點(diǎn)查找倒數(shù)第k個(gè)結(jié)點(diǎn)程序查找單鏈表的中間結(jié)點(diǎn)使用兩個(gè)指針，并同時(shí)從表頭開始向表尾方向移動(dòng)，一個(gè)指針一次走兩步，另一個(gè)指針一次走一步。這樣，當(dāng)“排頭兵”指針到達(dá)表尾時(shí)，后面的指針即指向鏈表的中間結(jié)點(diǎn)。與findKth函數(shù)中一樣，兩個(gè)指針分別是front和rear程序?qū)捂湵砟嬷脤?duì)于單鏈表的其他結(jié)點(diǎn)，讓middle所指結(jié)點(diǎn)的next域指向left所指結(jié)點(diǎn)，即left所指結(jié)點(diǎn)的原后繼（middle所指）變?yōu)樗男虑膀?qū)。然后，三個(gè)指針依次后移一個(gè)位置當(dāng)所有結(jié)點(diǎn)中的next域都轉(zhuǎn)向后，再將head所指的頭結(jié)點(diǎn)鏈接在表頭處程序驗(yàn)證程序ThankYou!全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第三章棧和隊(duì)列學(xué)習(xí)目標(biāo)掌握棧和隊(duì)列的邏輯定義、特點(diǎn)及基本操作，了解它們的邏輯表示方法及使用場(chǎng)掌握棧的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)及復(fù)雜度分析掌握隊(duì)列的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)，重點(diǎn)掌握循環(huán)隊(duì)列的實(shí)現(xiàn)及復(fù)雜度分析掌握結(jié)合了棧和隊(duì)列特點(diǎn)的雙端隊(duì)列了解線性表與棧及隊(duì)列的關(guān)系靈活運(yùn)用棧和隊(duì)列的基本操作，設(shè)計(jì)算法解決與此相關(guān)的實(shí)際問題本章主要內(nèi)容棧12進(jìn)一步討論棧與隊(duì)列3隊(duì)列4棧和隊(duì)列的應(yīng)用棧和隊(duì)列是線性表的兩個(gè)經(jīng)典特例，它們都是操作受限的線性表，即操作的位置需要滿足各自的條件因?yàn)檫@些條件的特殊性，使得實(shí)現(xiàn)各自的操作時(shí)過(guò)程簡(jiǎn)捷，效率更高第一節(jié)

棧棧是一種特殊的線性表，它的特殊性體現(xiàn)在操作的位置上。在含n個(gè)元素的線性表中進(jìn)行插入或刪除時(shí)，操作位置可以有n+1個(gè)或n個(gè)當(dāng)將操作位置限定在線性表的同一端時(shí)，得到的數(shù)據(jù)結(jié)構(gòu)就是棧它是一種受限的線性表?xiàng)５亩x及其基本操作定義3-1棧（stack）是限定僅在一端進(jìn)行插入和刪除的線性表能進(jìn)行插入和刪除的這一端稱為棧頂，線性表的另一端稱為棧底在棧頂插入一個(gè)元素稱為入棧（push）、進(jìn)?；驂簵?，從棧頂刪除一個(gè)元素稱為出棧（pop）或退棧棧的表示將棧S表示為：S=(a0,a1,…,an-1)

通常指定an-1一端為棧頂，a0一端是棧底棧中元素個(gè)數(shù)n稱為棧的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空棧棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿，就允許入棧當(dāng)沒有其他的特殊限制時(shí)，對(duì)于同一個(gè)入棧序列，可能會(huì)得到很多個(gè)合理正確的出棧序列棧的基本操作出棧序列個(gè)數(shù)

例3-1設(shè)有5個(gè)元素1,2,3,4,5依次入棧，以push(x)表示x入棧，pop(x)表示x出棧，試寫出得到出棧序列2,1,4,3,5的操作過(guò)程操作過(guò)程為push(1),push(2),pop(2),pop(1),push(3),

push(4),pop(4),pop(3),push(5),pop(5)例3-2依次讀入數(shù)據(jù)元素序列a,b,c,d,e,f,g并入棧。下列選項(xiàng)中，不可能是出棧序列的是（）A．d,e,c,f,b,g,aB．c,d,b,e,f,a,gC．e,f,d,g,c,b,aD．f,e,g,d,a,c,b答案為D例3-3一個(gè)棧的輸入序列為1,2,3,…,n，若輸出序列的第一個(gè)元素是n，則第i（1<i≤n）個(gè)輸出的元素是（）A．不確定B．n-i+1C．iD．n-i答案為B例3-4元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是（）A．3 B．4 C．5 D．6

答案為B例3-5入棧序列是1,2,3,4，出棧序列是2,4,3,1，則棧的容量最小是（）。A．1B．2C．3D．4答案為C棧的存儲(chǔ)及其實(shí)現(xiàn)棧有兩種主要的存儲(chǔ)方式順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)方式使用數(shù)組保存棧元素，得到的是順序棧鏈?zhǔn)酱鎯?chǔ)方式使用單鏈表保存棧元素，得到的是鏈?zhǔn)綏ｍ樞驐＜捌鋵?shí)現(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標(biāo)為0的位置同時(shí)使用一個(gè)變量標(biāo)記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱為棧頂指針順序棧的定義typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 inttop; //棧頂位置}SeqStack;順序棧的基本操作棧頂位置top的兩種定義方式本書采用(a)的方式初始化棧、清空棧判空、判滿入棧入棧時(shí)，新元素放在element[top]處，然后top加1第1個(gè)元素入棧時(shí)放在數(shù)組下標(biāo)為0的位置因?yàn)閿?shù)組空間有限，最大容量是maxSize，所以入棧時(shí)需要判定棧不能是滿的出棧出棧時(shí)，需要先將top值減1，然后將element[top]處的值通過(guò)參數(shù)x返回出棧時(shí)需要判定棧不是空的獲取棧頂元素效率top的值既是保存下一個(gè)入棧元素的位置，也是棧中所含元素個(gè)數(shù)的計(jì)數(shù)器因?yàn)闂５娜霔２僮骷俺鰲２僮鞫荚跅ｍ斶M(jìn)行，所以入棧、出棧、獲取棧頂元素時(shí)都不需要移動(dòng)棧中已有的元素，故時(shí)間復(fù)雜度都是O(1)判定?？占皸M等操作的時(shí)間復(fù)雜度也是O(1)例3-6也可以將數(shù)組下標(biāo)最大的一端作為棧底若一個(gè)棧保存在數(shù)組V[0..n-1]中，初始時(shí)棧頂指針top為n，則下列選項(xiàng)中，能夠正確實(shí)現(xiàn)x入棧操作的語(yǔ)句序列是（）。A．top=top+1;V[top]=x;B．V[top]=x;top=top+1;C．top=top-1;V[top]=x;D．V[top]=x;top=top-1;答案為C對(duì)頂棧數(shù)組的兩個(gè)端點(diǎn)分別作為兩個(gè)棧的棧底左側(cè)棧占用數(shù)組0到k的單元，棧頂在k+1位置右側(cè)棧占用數(shù)組m-1到h的單元，棧頂在h-1位置此時(shí)必須滿足k<h，才能保證兩個(gè)棧不會(huì)重疊棧S1入棧時(shí)，棧頂值增大，出棧時(shí)棧頂值減小棧S2剛好相反，入棧時(shí)棧頂值減小，出棧時(shí)棧頂值增大例3-7若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)有兩個(gè)棧共享空間V[0..m-1]，棧1的底在v[0]，棧2的底在V[m-1]，初始時(shí)，棧1的棧頂top1=0，棧2的棧頂top2=m-1。則棧滿的條件是（）A．|top2-top1|==0B．top1==top2+1C．top1+top2==m-1D．top1==top2答案為B鏈?zhǔn)綏Ｋ^的鏈?zhǔn)綏?，可以看作是一個(gè)僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過(guò)頭指針完成。所以，在鏈?zhǔn)綏Ｖ校梢灾欢x頭指針，尾指針及頭結(jié)點(diǎn)都可以不定義鏈?zhǔn)綏５亩xtypedefintELEMType;typedefstructnode{ //鏈?zhǔn)綏＝Y(jié)點(diǎn)

ELEMTypedata; structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack; //鏈?zhǔn)綏３跏蓟瘲３跏紩r(shí)是個(gè)空棧，所以指向棧頂?shù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時(shí)才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過(guò)x返回給調(diào)用者元素所占用的空間要釋放掉清空棧及判棧空入棧入棧時(shí)，需要?jiǎng)?chuàng)建一個(gè)新結(jié)點(diǎn)，并將新結(jié)點(diǎn)插入在棧頂位置順序棧與鏈?zhǔn)綏５谋容^實(shí)現(xiàn)順序棧和鏈?zhǔn)綏５乃胁僮鞫贾恍枰?shù)時(shí)間，因此棧的兩種實(shí)現(xiàn)方式的優(yōu)劣僅體現(xiàn)在它們的存儲(chǔ)效率上順序棧需要預(yù)先申請(qǐng)一個(gè)固定長(zhǎng)度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個(gè)數(shù)相對(duì)較少時(shí)，空間浪費(fèi)較大鏈?zhǔn)綏５拈L(zhǎng)度雖然可變，但是每個(gè)元素都需要一個(gè)指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開銷棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會(huì)開辟一個(gè)函數(shù)調(diào)用棧用來(lái)保存函數(shù)在調(diào)用過(guò)程中所需要的一些信息第二節(jié)

隊(duì)列隊(duì)列也是一種特殊的線性表，其特殊性也體現(xiàn)在操作的位置上它具有優(yōu)先的特性，即先來(lái)的先得到服務(wù)這種先來(lái)先服務(wù)的特性稱為先進(jìn)先出（FirstInFirstOut），簡(jiǎn)稱FIFO隊(duì)列的定義及其基本操作定義3-2隊(duì)列（queue）是只能在表的一端插入、在另一端刪除的線性表能進(jìn)行插入的一端稱為隊(duì)列尾，簡(jiǎn)稱隊(duì)尾；能進(jìn)行刪除的一端稱為隊(duì)列頭，簡(jiǎn)稱隊(duì)頭在隊(duì)尾插入元素稱為入隊(duì)（enqueue），從隊(duì)頭刪除元素稱為出隊(duì)（dequeue）仍然可以沿用線性表的方法來(lái)表示隊(duì)列，隊(duì)列Q可以表示為 Q=(a0,a1,…,an-1)a0稱為隊(duì)頭元素，an-1稱為隊(duì)尾元素，元素個(gè)數(shù)n稱為隊(duì)列長(zhǎng)度當(dāng)給定隊(duì)列的入隊(duì)序列后，僅能得到一個(gè)出隊(duì)序列，而且是與入隊(duì)序列完全相同的序列。這是由隊(duì)列先進(jìn)先出的特性決定的隊(duì)列的定義隊(duì)列中元素的類型是ELEMType，另外，還有指標(biāo)隊(duì)頭和隊(duì)尾的兩個(gè)量定義如下所示typedefintELEMType;intfront,rear; //隊(duì)頭、隊(duì)尾指針隊(duì)列的操作定義隊(duì)列的存儲(chǔ)及實(shí)現(xiàn)與線性表及棧一樣，隊(duì)列也有兩種實(shí)現(xiàn)方式，分別得到順序隊(duì)列和鏈?zhǔn)疥?duì)列順序隊(duì)列使用一個(gè)一維數(shù)組A（下標(biāo)從0到n-1）來(lái)保存隊(duì)列，假定隊(duì)列中含有m（m≤n）個(gè)元素選擇A[0]作為隊(duì)頭，那么A[m-1]就是隊(duì)尾當(dāng)出隊(duì)時(shí)，隊(duì)頭A[0]從數(shù)組中刪除，此時(shí)要依次將后面的m-1個(gè)元素均前移一個(gè)位置這種情況下出隊(duì)操作的時(shí)間開銷是O(m)存儲(chǔ)結(jié)構(gòu)現(xiàn)在交換隊(duì)頭和隊(duì)尾的位置，選擇A[m-1]是隊(duì)頭，那么A[0]是隊(duì)尾入隊(duì)時(shí)，隊(duì)列中原有的m個(gè)元素均需后移一個(gè)位置，騰出A[0]的位置放置新元素此時(shí)入隊(duì)操作的時(shí)間開銷將為O(m)存儲(chǔ)結(jié)構(gòu)可以使用變量front指示隊(duì)頭位置，使用變量rear指示隊(duì)尾位置稱front為隊(duì)頭指針，rear為隊(duì)尾指針表示的是數(shù)組下標(biāo)通常，front指示的是隊(duì)頭元素所在的位置，rear指示的是隊(duì)尾元素后面的空位置按照慣例，還是將第一個(gè)入隊(duì)的元素保存在數(shù)組下標(biāo)0的位置入隊(duì)的新元素放置到所有元素的后面經(jīng)過(guò)若干次入隊(duì)、出隊(duì)操作后，含m個(gè)元素的隊(duì)列的示意圖如下所示，其中陰影部分表示隊(duì)列中的元素實(shí)際占用的數(shù)組單元

a0…am-1

↑front

↑rear

當(dāng)再進(jìn)行若干次入隊(duì)操作后，rear會(huì)到達(dá)數(shù)組的末尾，即最后一個(gè)下標(biāo)位置。之后再進(jìn)行入隊(duì)操作時(shí)，導(dǎo)致數(shù)組下標(biāo)越界。但數(shù)組的前半段可能會(huì)因出隊(duì)操作而有空閑的單元

x…y

↑front

↑rear可以重復(fù)利用數(shù)組中前面的空閑單元保存后續(xù)入隊(duì)的元素…v

……u…

↑rear

↑front

例3-8設(shè)隊(duì)列保存在最大容量為7的數(shù)組A中，從空隊(duì)列開始，依次執(zhí)行下列各步操作，分別畫出得到的隊(duì)列示意圖依次將5,12,9,37入隊(duì)列將5,12依次出隊(duì)列，并依次將25,8入隊(duì)列將16入隊(duì)列，再將9出隊(duì)列，再將7,4入隊(duì)列循環(huán)隊(duì)列順序隊(duì)列都實(shí)現(xiàn)為循環(huán)隊(duì)列在循環(huán)隊(duì)列中，入隊(duì)操作會(huì)涉及到隊(duì)尾rear值的變化，rear=(rear+1)%n，出隊(duì)操作會(huì)涉及到隊(duì)頭front值的變化，front=(front+1)%n，其中n是數(shù)組的大小可以把這個(gè)數(shù)組想象成一個(gè)首尾相接的圓環(huán)，A[n-1]的后面是A[0]“循環(huán)”一詞的含義正是如此空與滿數(shù)組滿時(shí)，rear==front條件rear==front也代表空隊(duì)列解決方法：讓數(shù)組中始終剩余至少一個(gè)空位置。當(dāng)數(shù)組中僅有一個(gè)空位置時(shí)，就認(rèn)為已經(jīng)達(dá)到隊(duì)列的最大長(zhǎng)度了，隊(duì)列已滿初始時(shí)，front=0且rear=0例3-9已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0..n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是（）A．0,0B．0,n-1C．n-1,0D．n-1,n-1答案是B循環(huán)隊(duì)列的定義typedefintELEMType;typedefstruct{

ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循環(huán)隊(duì)列初始化構(gòu)造一個(gè)空隊(duì)列，隊(duì)頭和隊(duì)尾指針均賦初值0清空隊(duì)列隊(duì)列置空也得到一個(gè)空隊(duì)列，可以將隊(duì)頭和隊(duì)尾指針均賦值0，和初始化隊(duì)列的結(jié)果一樣也可以讓隊(duì)頭和隊(duì)尾指針的值相等，表示是一個(gè)空隊(duì)列判空與判滿隊(duì)列為空的條件是rear==front隊(duì)列為滿的條件是(rear+1)%n==front求隊(duì)列長(zhǎng)度入隊(duì)與出隊(duì)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列采用帶頭指針及尾指針的單鏈表作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)單鏈表的頭指針可以當(dāng)作隊(duì)頭指針front，尾指針可以當(dāng)作隊(duì)尾指針rear鏈?zhǔn)疥?duì)列的定義typedefintELEMType;typedefstructnode{ //鏈?zhǔn)疥?duì)列中結(jié)點(diǎn) ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //鏈?zhǔn)疥?duì)列 LinkQueueNode*front,*rear; //隊(duì)頭指針、隊(duì)尾指針}LinkQueue;初始化、清空隊(duì)列判空循環(huán)隊(duì)列中，當(dāng)隊(duì)頭指針和隊(duì)尾指針相等時(shí)，隊(duì)列為空空鏈?zhǔn)疥?duì)列中，隊(duì)頭指針和隊(duì)尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥?duì)列通常不會(huì)滿入隊(duì)列出隊(duì)例3-10若使用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，則進(jìn)行入隊(duì)列操作時(shí)（）。A．僅需要修改隊(duì)頭指針，不需要修改隊(duì)尾指針B．僅需要修改隊(duì)尾指針，不需要修改隊(duì)頭指針C．隊(duì)尾指針一定要修改，隊(duì)頭指針也一定要修改D．隊(duì)尾指針一定要修改，隊(duì)頭指針可能要修改答案為D采用鏈?zhǔn)椒绞綄?shí)現(xiàn)隊(duì)列時(shí)，也可以配合使用一個(gè)空閑單元鏈表，使得入隊(duì)、出隊(duì)時(shí)盡量少地調(diào)用malloc函數(shù)及free函數(shù)在鏈?zhǔn)疥?duì)列中，可以將這兩個(gè)鏈表合在一起，形成一個(gè)圓環(huán)，即使用一個(gè)循環(huán)鏈表來(lái)表示鏈?zhǔn)疥?duì)列及對(duì)應(yīng)的空閑單元鏈表。在這個(gè)循環(huán)鏈表中，結(jié)點(diǎn)分為兩部分，一部分結(jié)點(diǎn)用來(lái)保存實(shí)際數(shù)據(jù)，另一部分結(jié)點(diǎn)是空閑結(jié)點(diǎn)帶空閑單元鏈表的鏈?zhǔn)疥?duì)列初始狀態(tài)第一個(gè)元素入隊(duì)第三節(jié)

進(jìn)一步討論棧與隊(duì)列雙端隊(duì)列輸入受限的雙端隊(duì)列輸出受限的雙端隊(duì)列例3-11若以1,2,3,4作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是（）。A．1,2,3,4B．4,1,3,2C．4,2,3,1D．4,2,1,3答案是C例3-12循環(huán)隊(duì)列存放在一維數(shù)組A[0..M-1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素，初始時(shí)為空。下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是（）。A．隊(duì)空：end1==end2；隊(duì)滿：end1==(end2+1)modMB．隊(duì)空：end1==end2；隊(duì)滿：end2==(end1+1)mod(M-1)C．隊(duì)空：end2==(end1+1)modM；隊(duì)滿：end1==(end2+1)modMD．隊(duì)空：end1==(end2+1)modM；隊(duì)滿：end2==(end1+1)mod(M-1)答案是A棧與隊(duì)列的相互模擬使用棧來(lái)模擬隊(duì)列使用棧模擬的隊(duì)列類型定義typedefstruct{

SeqStackS,T;}simuQueue; //隊(duì)列typedefintELEMType;初始化入隊(duì)列出隊(duì)列判空、判滿使用隊(duì)列來(lái)模擬棧使用隊(duì)列模擬的棧類型typedefstruct{

SeqQueueP,Q;}simuStack; //使用隊(duì)列來(lái)模擬棧typedefintELEMType;初始化、清空棧判空、判滿求長(zhǎng)度入棧操作出棧第四節(jié)

棧和隊(duì)列的應(yīng)用——括號(hào)的匹配檢查程序中有很多符號(hào)是成對(duì)出現(xiàn)的，并且它們的出現(xiàn)次序必須正確，可以嵌套但不能交錯(cuò)“左”符號(hào)稱為“開”符號(hào)，“右”符號(hào)稱為“閉”符號(hào)如果表達(dá)式中符號(hào)匹配正確，則表達(dá)式稱為平衡的表達(dá)式可以用棧來(lái)實(shí)現(xiàn)檢驗(yàn)符號(hào)平衡性的算法檢驗(yàn)括號(hào)匹配算法的思想從左至右掃描給定的符號(hào)串，忽略所有非括號(hào)的符號(hào)當(dāng)遇到開括號(hào)時(shí)，保存它當(dāng)遇到一個(gè)閉括號(hào)時(shí)，看看它是否對(duì)應(yīng)于最近遇到的開括號(hào)如果是，則丟掉開括號(hào)，并繼續(xù)掃描符號(hào)串如果能掃描完整個(gè)符號(hào)串，且沒有遇到不匹配的情況，則給定的符號(hào)串代表的表達(dá)式是平衡的可以使用棧來(lái)保存遇到的開括號(hào)表達(dá)式不平衡的情況剛掃描到的閉括號(hào)與棧頂開括號(hào)不匹配，說(shuō)明括號(hào)有交錯(cuò)已掃描到表達(dá)式尾，但棧不空，說(shuō)明開括號(hào)數(shù)多于閉括號(hào)數(shù)掃描到閉括號(hào)時(shí)發(fā)現(xiàn)棧為空，說(shuō)明缺少與此閉括號(hào)對(duì)應(yīng)的開括號(hào)檢驗(yàn)括號(hào)平衡性算法的實(shí)現(xiàn)檢驗(yàn)括號(hào)平衡性算法例3-13檢查表達(dá)式[a+(d+e)]時(shí)棧的變化過(guò)程例3-14檢查表達(dá)式{[(])}時(shí)棧的變化過(guò)程表達(dá)式的計(jì)算表達(dá)式的表示形式及計(jì)算次序中綴表達(dá)式： <操作數(shù)><運(yùn)算符><操作數(shù)> c*(a+b)前綴表達(dá)式 <運(yùn)算符><操作數(shù)><操作數(shù)>后綴表達(dá)式 <操作數(shù)><操作數(shù)><運(yùn)算符>將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式——手算給中綴表達(dá)式中的每個(gè)運(yùn)算符加括號(hào)，這樣的表達(dá)式稱為帶完全括號(hào)的中綴表達(dá)式接下來(lái)，將每個(gè)運(yùn)算符右移，緊貼在對(duì)應(yīng)的閉括號(hào)的前面最后，去掉括號(hào)得到后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式——算法自左至右掃描中綴表達(dá)式，當(dāng)遇到操作數(shù)時(shí)，直接輸出它。當(dāng)遇到運(yùn)算符時(shí)，不能像操作數(shù)那樣直接輸出，而是保存在棧中。當(dāng)滿足一定的條件時(shí)才輸出棧頂?shù)倪\(yùn)算符當(dāng)讀到表達(dá)式中的一個(gè)運(yùn)算符時(shí)，將它與棧內(nèi)運(yùn)算符進(jìn)行比較。分以下情況考慮若棧內(nèi)運(yùn)算符的優(yōu)先級(jí)高于棧外運(yùn)算符的優(yōu)先級(jí)，則輸出棧內(nèi)運(yùn)算符，繼續(xù)比較棧外運(yùn)算符與棧內(nèi)運(yùn)算符若棧外運(yùn)算符的優(yōu)先級(jí)高于棧內(nèi)運(yùn)算符的優(yōu)先級(jí)，則棧外運(yùn)算符入棧，繼續(xù)讀入表達(dá)式的下一個(gè)符號(hào)若已經(jīng)讀到表達(dá)式末尾，則依次出棧棧中的全部運(yùn)算符部分運(yùn)算符優(yōu)先級(jí)表運(yùn)算符+,-*,/,%()#棧內(nèi)優(yōu)先級(jí)351-0棧外優(yōu)先級(jí)2481-例3-15將中綴表達(dá)式1+2*3轉(zhuǎn)換為后綴表達(dá)式算法——獲取算符優(yōu)先級(jí)轉(zhuǎn)換算法將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y形式的算法后綴表達(dá)式計(jì)算從左至右掃描后綴表達(dá)式當(dāng)遇到操作數(shù)時(shí)，操作數(shù)進(jìn)棧當(dāng)遇到運(yùn)算符時(shí)，從棧中彈出兩個(gè)操作數(shù)，并進(jìn)行運(yùn)算符所代表的運(yùn)算，結(jié)果仍放到棧中因?yàn)闂５暮筮M(jìn)先出的特性，故從棧中先彈出的操作數(shù)是運(yùn)算符的右操作數(shù)，后彈出的是左操作數(shù)例3-16計(jì)算后綴表達(dá)式123*+值的過(guò)程計(jì)算表達(dá)式算法計(jì)算后綴表達(dá)式算法打印楊輝三角形楊輝三角形的前8行相鄰兩行的對(duì)應(yīng)關(guān)系打印算法打印楊輝三角形算法ThankYou!全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第四章數(shù)組、廣義表和串學(xué)習(xí)目標(biāo)掌握數(shù)組、廣義表和串的基本概念掌握數(shù)組按行主序及按列主序的存儲(chǔ)方式及二維數(shù)組地址計(jì)算方法掌握特殊矩陣的存儲(chǔ)方式及相應(yīng)的地址計(jì)算方法理解廣義表的概念，掌握廣義表的表示及基本運(yùn)算了解模式匹配概念，掌握串的模式匹配算法本章主要內(nèi)容數(shù)組及廣義表12串第一節(jié)

數(shù)組及廣義表數(shù)組是程序設(shè)計(jì)語(yǔ)言中的重要語(yǔ)法成分，很多語(yǔ)言都定義了數(shù)組類型以C語(yǔ)言為例，它定義了一維數(shù)組，數(shù)組元素還可以是數(shù)組，由此得到數(shù)組的數(shù)組，即多維數(shù)組一般地將n（n≥2）維數(shù)組看作是n-1維數(shù)組的數(shù)組從數(shù)據(jù)結(jié)構(gòu)的角度來(lái)理解，一維數(shù)組可以作為線性表的存儲(chǔ)結(jié)構(gòu)，數(shù)組中保存的各元素可以組成一個(gè)線性表多維數(shù)組在系統(tǒng)內(nèi)部都對(duì)應(yīng)一個(gè)隱含的一維數(shù)組，所以多維數(shù)組也是一種線性表例如二維數(shù)組就是以一維數(shù)組為元素的線性表數(shù)組的每個(gè)元素都是形如(index,value)的二元對(duì)，index是數(shù)組下標(biāo)，也稱為索引，value是對(duì)應(yīng)于該下標(biāo)的數(shù)值任何兩個(gè)元素的index值都不相同數(shù)組的基本操作Create(); //創(chuàng)建一個(gè)空的數(shù)組Store(index,value);//添加數(shù)據(jù)(index,value)//同時(shí)刪除有相同index值的數(shù)據(jù)對(duì)（若存在）Retrieve(index);//返回下標(biāo)為index的value值例4-1用數(shù)組表示一個(gè)星期每天的最高溫度hightem={(星期日,30),(星期一,28),(星期二,29),(星期三,32),(星期四,28),(星期五,30),(星期六,31)}數(shù)組上的操作Store(星期一,29);Retrieve(星期五);也可以約定使用0到6來(lái)分別表示星期日到星期六，此時(shí)，數(shù)組hightem可表示為hightem={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}數(shù)組的順序存儲(chǔ)方式數(shù)組的順序存儲(chǔ)有兩種形式。以二維數(shù)組為例，它的元素可以按行排列，也可以按列排列所謂按行排列，就是先排數(shù)組的第一行，緊隨其后排第二行，依此類推所謂按列排列，就是先排數(shù)組的第一列，緊隨其后排第二列，依此類推最終都是將數(shù)組中的全部元素排列成一個(gè)序列C語(yǔ)言中多維數(shù)組下標(biāo)的形式：[i1][i2][i3]…[ik]ij（1≤j≤k）為非負(fù)整數(shù)聲明值為整型類型的k維數(shù)組DkArrayintDkArray[u1][u2][u3]…[uk];每一維的下標(biāo)取值范圍是：0≤ij<uj（1≤j≤k）數(shù)組最多可容納n=u1

u2

u3

…

uk個(gè)整數(shù)所需要的內(nèi)存空間sizeof(DkArray)=n

sizeof(int)個(gè)字節(jié)若開始地址為start，則占用的空間將延伸至start+sizeof(DkArray)-1。intD2Array[3][6];對(duì)應(yīng)一個(gè)3行6列的矩陣通常int占4個(gè)字節(jié)數(shù)組D2Array中含有18個(gè)元素共占用18

4=76個(gè)字節(jié)編號(hào)對(duì)上述的下標(biāo)表格按行自上而下、同一行中自左至右進(jìn)行連續(xù)編號(hào)，從0開始按行優(yōu)先把二維數(shù)組中的下標(biāo)映射到0到n-1之間的某個(gè)整數(shù)的方式稱為行主序，也稱為行主映射按列優(yōu)先，對(duì)下標(biāo)表格從第一列開始，從上到下進(jìn)行連續(xù)編號(hào)，直到最后一列映射函數(shù)行主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i1

u2+i2

其中u2是數(shù)組的列數(shù)列主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i2

u1+i1

其中u1是數(shù)組的行數(shù)例4-3二維數(shù)組A[10][5]采用行主序方式存儲(chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，若A[0][4]的存儲(chǔ)地址是1000，則A[8][4]的存儲(chǔ)地址是多少？解：給定的數(shù)組A是10行5列，需要從A[0][4]的存儲(chǔ)地址反推出數(shù)組A的首地址，然后再計(jì)算A[8][4]的存儲(chǔ)地址行主序所對(duì)應(yīng)的映射函數(shù)為map(i1,i2)=i1

u2+i2本題中：u2=5，map(0,4)=4每個(gè)元素占4個(gè)存儲(chǔ)單元 A[0][0]的存儲(chǔ)地址=1000-4

4=984根據(jù)計(jì)算公式，A[8][4]的映射編號(hào)是 map(8,4)=8

5+4=44存儲(chǔ)地址為984+44

4=1160換一種計(jì)算方法A[0][4]和A[8][4]之間的元素個(gè)數(shù)是 8

5=40A[0][4]與A[8][4]之間的偏移量 =40

4A[8][4]的存儲(chǔ)地址 =A[0][4]的存儲(chǔ)地址+ A[0][4]與A[8][4]之間的偏移量 =1000+160=1160示例三維數(shù)組D3Array[3][2][4]按行主序下標(biāo)排列的形式對(duì)于三維數(shù)組ThrDimenArray[u1][u2][u3]，其行主序的映射函數(shù)應(yīng)為 map(i1,i2,i3)=i1

u2

u3+i2

u3+i3排列規(guī)律所有第一維值為i1的元素都排在第一維值大于i1的元素之前。第一維值相同的元素?cái)?shù)目為u2

u3。因此第一維值小于i1的元素?cái)?shù)目為i1

u2

u3，第一維值等于i1且第二維值小于i2的元素?cái)?shù)目為i2

u3，第一維值等于i1第二維值等于i2且第三維值小于i3的元素?cái)?shù)目為i3矩陣的壓縮存儲(chǔ)對(duì)稱矩陣和三角矩陣從節(jié)省存儲(chǔ)空間的角度考慮，對(duì)稱矩陣和上（下）三角矩陣，都可以只保存矩陣中約一半的元素，從而可以節(jié)省差不多一半的存儲(chǔ)空間這樣的存儲(chǔ)形式稱為壓縮存儲(chǔ)壓縮存儲(chǔ)對(duì)于對(duì)稱矩陣，因?yàn)閷?duì)角線以上及以下的元素對(duì)稱相等，所以只需要保存其中的一半及對(duì)角線上的元素即可對(duì)于上三角矩陣或下三角矩陣，僅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩陣有n行n列，則這三種形式下需要保存的元素個(gè)數(shù)為n

(n+1)/2三角部分

例4-4設(shè)有一個(gè)10行10列的下三角矩陣A，采用行優(yōu)先壓縮存儲(chǔ)方式，保存A中第一個(gè)元素a00的地址是100，保存a11的地址是108，則保存元素a44的地址是（）A．115B．156C．160D．212答案為B稀疏矩陣稀疏矩陣該矩陣只有10個(gè)非零元素，每個(gè)非零元素用一個(gè)三元組表示三元組表三元組表應(yīng)是一個(gè)有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元組再按列的大小排列對(duì)應(yīng)前例的三元組表i0012234455j1200521405v891-3121624615-7稀疏矩陣的存儲(chǔ)結(jié)構(gòu)typedefstruct{ inti,j; //存儲(chǔ)非零元素的下標(biāo)

ELEMTypev; //存儲(chǔ)非零元素的值}triTerm;typedefstruct{ introws,cols; //矩陣的行數(shù)、列數(shù) intterms; //非零元素個(gè)數(shù)

triTermtri[maxSize]; //三元組表}SparseMatrix;輸入三元組生成三元組表的程序矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置即是行、列互換，i行的元素放置到i列，這也意味著，j列的元素放置在j行。如果矩陣是n

m的，則轉(zhuǎn)置后得到的矩陣是m

n的很容易想到，將三元組表中的每個(gè)三元組項(xiàng)的i與j互換，即可得到轉(zhuǎn)置后矩陣的三元組表但是這樣轉(zhuǎn)換后得到的三元組表不再按行主序排列，不便于后續(xù)操作的實(shí)現(xiàn)所以要實(shí)現(xiàn)的矩陣轉(zhuǎn)置程序，必須得到一個(gè)按行主序排列的三元組表思路可以像readSparseMatrix函數(shù)那樣處理，讀入原矩陣的一個(gè)三元組，插入到目標(biāo)矩陣的三元組表中可以使用一個(gè)臨時(shí)計(jì)數(shù)數(shù)組，記錄原矩陣的每個(gè)三元組在目標(biāo)矩陣的三元組表中的插入位置，以輔助完成轉(zhuǎn)置操作，由此避免了三元組的移動(dòng)，高效率地實(shí)現(xiàn)轉(zhuǎn)置操作不失一般性，設(shè)原矩陣A的行數(shù)是rows，列數(shù)是cols。則轉(zhuǎn)置后矩陣B的行數(shù)是cols，列數(shù)是rows。三元組的個(gè)數(shù)沒有改變A中處于0列的元素，將是B中處于0行的元素。所以B的三元組表中的最前面的元素，是A中列值為0的元素。接下來(lái)是A中列值為1的元素，依此類推，最后是A中列值為cols-1的元素。使用臨時(shí)數(shù)組ColSize來(lái)保存統(tǒng)計(jì)結(jié)果前例中的矩陣，臨時(shí)數(shù)組ColSize內(nèi)容在B的三元組表中，為各行元素預(yù)留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素對(duì)于A的三元組(0,1,8)和(4,1,24)，轉(zhuǎn)置后分別為(1,0,8)和(1,4,24)，它們應(yīng)該保存在上述第二部分，即位置3和位置4中故由ColSize數(shù)組中的元素值，從前向后依次相加，得到RowNext的值012345603577810轉(zhuǎn)置算法數(shù)組的應(yīng)用走迷宮是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問題不失一般性，使用一個(gè)m行n列的矩陣maze表示迷宮，讓機(jī)器人R尋找從maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宮的唯一出口）間的可行路徑任一時(shí)刻，R在迷宮中的位置用行、列號(hào)[i][j]來(lái)表示，這時(shí)它有4個(gè)方向可以進(jìn)行試探，即從圖上看是上、下、左、右設(shè)下一位置是[g][h]，顯然[g][h]