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

全國高等教育自學(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ù)語，了解4類基本的數(shù)據(jù)結(jié)構(gòu)，理解邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的含義及相互關(guān)系，了解數(shù)據(jù)結(jié)構(gòu)的4種基本存儲方法掌握抽象數(shù)據(jù)類型的表示與描述，能夠用抽象數(shù)據(jù)類型表示實(shí)際問題掌握算法的基本概念及重要特性，能夠使用類C語言描述算法掌握算法評估和復(fù)雜性度量的基本概念，能夠?qū)唵嗡惴ㄟM(jìn)行復(fù)雜性評估理解算法的基本設(shè)計(jì)策略的特點(diǎn)，使用基本的算法策略實(shí)現(xiàn)簡單程序本章主要內(nèi)容基本概念和術(shù)語12算法和算法分析3算法設(shè)計(jì)策略簡介數(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)的基本概念，還將介紹算法及其特性，介紹時間、空間復(fù)雜度的概念，在此基礎(chǔ)上，介紹對算法進(jìn)行復(fù)雜度評估的基本方法第一節(jié)

基本概念和術(shù)語需求推動技術(shù)的發(fā)展，程序設(shè)計(jì)語言內(nèi)置的數(shù)據(jù)類型越來越多樣，提供的處理手段也越來越方便快捷當(dāng)需要方便地處理眾多同類型的數(shù)據(jù)時，出現(xiàn)了數(shù)組，“結(jié)構(gòu)”的雛形顯現(xiàn)了數(shù)組——例如，可以表示多個同類型的數(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ù)語

20世紀(jì)80年代以后出現(xiàn)了抽象數(shù)據(jù)類型概念數(shù)據(jù)對數(shù)據(jù)進(jìn)行操作的定義但不涉及操作的具體實(shí)現(xiàn)數(shù)據(jù)是指所有能輸入計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號的集合數(shù)據(jù)是各種各樣的復(fù)雜的數(shù)據(jù)往往由簡單的數(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é)號姓名性別出生日期籍貫M2022103001王義平男2004.11.22山東M2022103002陸東男2004.02.05河南M2022103003李曉敏女2005.01.15江蘇┇┇┇┇┇M2022103030楊志強(qiáng)男2004.10.30陜西章節(jié)目錄示例——“上下級”的關(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ī)中的表示及存儲方式數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯上描述數(shù)據(jù)，表明數(shù)據(jù)元素之間的關(guān)系是什么樣的，這與數(shù)據(jù)的存儲方式無關(guān)，既獨(dú)立于計(jì)算機(jī)，也獨(dú)立于程序設(shè)計(jì)語言數(shù)據(jù)的最小不可分割的單位是數(shù)據(jù)項(xiàng)邏輯上相關(guān)的、具有物理意義的若干數(shù)據(jù)項(xiàng)構(gòu)成一個數(shù)據(jù)元素?cái)?shù)據(jù)元素作為一個完整的對象（整體）是構(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)常用的存儲方法

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

第二節(jié)

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

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

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

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

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

若處理器速度增長10倍

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

算法設(shè)計(jì)策略簡介算法可以分為多種不同的類型，每種類型都有特定的應(yīng)用場景和解決問題的方法設(shè)計(jì)算法時，可以配合采用一些設(shè)計(jì)策略，使得算法的實(shí)現(xiàn)更方便設(shè)計(jì)策略有時也可以稱為設(shè)計(jì)方法，是指在解決特定問題時所采用的一類方法算法分為遞推法、迭代法、遞歸法、貪心法、分治法、動態(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的解時，有時可能僅需規(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ù)前一個值推出下一個值的公式初始時設(shè)定初始值（原值），然后根據(jù)迭代關(guān)系式和原值，求出新值，并用新值替代原值迭代過程不能無限進(jìn)行下去或者設(shè)定一個迭代次數(shù)，當(dāng)達(dá)到這個次數(shù)時迭代過程停止或者設(shè)定一個結(jié)束條件，當(dāng)滿足這個條件時，迭代過程停止程序遞歸法

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

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第二章線性表學(xué)習(xí)目標(biāo)理解線性表的相關(guān)概念，了解其邏輯定義及基本操作，理解線性表數(shù)據(jù)元素之間的邏輯關(guān)系掌握線性表的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞?，了解各自的特點(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)酱鎯皩?shí)現(xiàn)3線性表的順序存儲及實(shí)現(xiàn)進(jìn)一步討論兩種基本實(shí)現(xiàn)方式4單鏈表的應(yīng)用5第一節(jié)

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

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

示例

例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對于元素ai(1≤i≤n-1)，元素aj(0≤j<i)稱為ai的前驅(qū)，其中元素ai-1稱為ai的直接前驅(qū)對于元素ai(0≤i≤n-2)，元素aj(i<j≤n-1)稱為ai的后繼，其中元素ai+1稱為ai的直接后繼

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

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

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

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

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

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

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

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

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

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

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

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

11523196

…

1152723196

…

11527196

…

程序中使用的常量#defineTRUE1#defineFALSE0#defineERROR-1#ifndefmaxSize#definemaxSize100#endif順序表基本運(yùn)算的實(shí)現(xiàn)順序表的定義構(gòu)造空表及清空表判表空、判表滿、求表長插入新元素插入操作中移動元素的平均次數(shù)為n/2刪除操作刪除操作中移動元素的平均次數(shù)為(n-1)/2賦值、取值操作查找測試?yán)?-5設(shè)有順序表L，表長為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中間元素時，算法結(jié)束算法實(shí)現(xiàn)第三節(jié)

線性表的鏈?zhǔn)酱鎯皩?shí)現(xiàn)線性表還可以使用鏈?zhǔn)酱鎯Ψ绞奖４?，即線性表中的各個元素保存在各自的存儲空間中，形成一個個的結(jié)點(diǎn)這些結(jié)點(diǎn)在內(nèi)存中的地址不要求是相鄰的，它們之間通過指針連接起來以這種方式保存的線性表稱為鏈表每個結(jié)點(diǎn)中包含元素值和指向其他結(jié)點(diǎn)的指針，指針的個數(shù)可以是一個，也可能是兩個，從而形成不同形式的鏈表鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種動態(tài)靈活的存儲方式，它不要求預(yù)先分配一塊連續(xù)的存儲空間，而是按需分配，隨時需要隨時分配同時不要求分配的空間必須是相鄰的，而是由系統(tǒng)決定分配的具體位置，既可以相鄰也可以不相鄰所以在執(zhí)行插入及刪除操作時，不再需要移動元素以保證存儲空間的相鄰性單鏈表單鏈表是由一組動態(tài)分配的結(jié)點(diǎn)形成的鏈表，每個結(jié)點(diǎn)保存線性表中的一個元素及一個指針，指針指向保存其后繼元素的結(jié)點(diǎn)保存L的單鏈表示意圖結(jié)點(diǎn)定義單鏈表中結(jié)點(diǎn)及鏈表的定義示例要在上圖所示的單鏈表L的位置2處插入元素E。當(dāng)前指針為p，指向位置2操作步驟是創(chuàng)建一個新結(jié)點(diǎn)，新結(jié)點(diǎn)中保存值E讓新結(jié)點(diǎn)的next指針指向指針p指向的結(jié)點(diǎn)，這個結(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)酱鎯Y(jié)構(gòu)保存，則要求內(nèi)存中可用存儲單元的地址（）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以答案為D。單鏈表基本操作的實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表中，始終會有一個頭結(jié)點(diǎn)，這個結(jié)點(diǎn)在初始化時創(chuàng)建清空單鏈表判空單鏈表需要判空，通常不需要判滿求長度的兩種實(shí)現(xiàn)位置值與指針的轉(zhuǎn)換插入新元素刪除元素賦值、取值查找例2-9返回指針curr指向結(jié)點(diǎn)的位置效率分析如果給定了當(dāng)前指針，則插入操作和刪除操作的時間復(fù)雜度均為O(1)判定鏈表是否為空的時間復(fù)雜度也為O(1)清空表操作的時間復(fù)雜度是O(n)求表長，兩種實(shí)現(xiàn)分別是O(1)和O(n)查找操作的時間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的最優(yōu)情況下為O(1)最壞的情況下為O(n)平均來看是O(n)查找失敗是O(n)循環(huán)鏈表修改單鏈表的定義，將表尾結(jié)點(diǎn)的指針指回頭結(jié)點(diǎn)，從而形成一類新鏈表這樣的鏈表中，從任何一個結(jié)點(diǎn)出發(fā)沿著指針域的指示可以再回到這個結(jié)點(diǎn)，好象轉(zhuǎn)了一個圈一樣，形象地稱這樣的鏈表為循環(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)中，正確的修改指針的語句序列是（）。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)簡單地說，這兩種實(shí)現(xiàn)方式各有優(yōu)勢。在不同的情況下，對應(yīng)于不同的操作，某一種方式可能會優(yōu)于另外一種。但是哪種方式都不能適用于所有情況示例將下列特性對應(yīng)到順序表和鏈表中，對號入座A．邏輯上相鄰的元素，在內(nèi)存中的存儲位置也相鄰B．不必事先估計(jì)存儲空間C．所需空間與元素個數(shù)成正比D．插入、刪除時不需要移動元素E．支持隨機(jī)存取F．支持順序存取順序表具有的特性有：A、E和F鏈表具有的特性有：B、C、D和F對比存儲每個數(shù)據(jù)元素時空間比較緊湊，并且是占用連續(xù)的空間數(shù)組的每個單元中只需要保存數(shù)據(jù)本身，沒有額外的開銷鏈表在每個結(jié)點(diǎn)上除存儲數(shù)據(jù)元素外，還要留出空間存放指針。單鏈表中每個結(jié)點(diǎn)包含一個指針，雙向鏈表中每個結(jié)點(diǎn)包含兩個指針。這些指針占用的空間稱為結(jié)構(gòu)性開銷為順序表分配的數(shù)組，通常要寬松一些。通常數(shù)組中會有空閑的空間，此時并沒能充分利用數(shù)組的全部空間鏈表中占用的空間大小與鏈表中的元素個數(shù)成正比，分配的結(jié)點(diǎn)是全部使用的當(dāng)線性表的元素個數(shù)相對較少時，鏈表的實(shí)現(xiàn)比順序表的實(shí)現(xiàn)更節(jié)省空間當(dāng)線性表中的元素個數(shù)接近分配的最大個數(shù)，數(shù)組的空間存儲效率很高設(shè)n表示線性表中當(dāng)前元素的個數(shù)，D表示最多可以在數(shù)組中存儲的元素個數(shù)，也就是數(shù)組的大小，P表示指針的存儲單元大小，E表示數(shù)據(jù)元素的存儲單元大小順序表的空間需求為D

E單鏈表的空間需求為n

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

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

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

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

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第三章棧和隊(duì)列學(xué)習(xí)目標(biāo)掌握棧和隊(duì)列的邏輯定義、特點(diǎn)及基本操作，了解它們的邏輯表示方法及使用場掌握棧的兩種存儲方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)及復(fù)雜度分析掌握隊(duì)列的兩種存儲方式及各自的特點(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ì)列是線性表的兩個經(jīng)典特例，它們都是操作受限的線性表，即操作的位置需要滿足各自的條件因?yàn)檫@些條件的特殊性，使得實(shí)現(xiàn)各自的操作時過程簡捷，效率更高第一節(jié)

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

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

例3-1設(shè)有5個元素1,2,3,4,5依次入棧，以push(x)表示x入棧，pop(x)表示x出棧，試寫出得到出棧序列2,1,4,3,5的操作過程操作過程為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一個棧的輸入序列為1,2,3,…,n，若輸出序列的第一個元素是n，則第i（1<i≤n）個輸出的元素是（）A．不確定B．n-i+1C．iD．n-i答案為B例3-4元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開頭的序列個數(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棧的存儲及其實(shí)現(xiàn)棧有兩種主要的存儲方式順序存儲鏈?zhǔn)酱鎯樞虼鎯Ψ绞绞褂脭?shù)組保存棧元素，得到的是順序棧鏈?zhǔn)酱鎯Ψ绞绞褂脝捂湵肀４鏃Ｔ?，得到的是鏈?zhǔn)綏ｍ樞驐＜捌鋵?shí)現(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標(biāo)為0的位置同時使用一個變量標(biāo)記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱為棧頂指針順序棧的定義typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 inttop; //棧頂位置}SeqStack;順序棧的基本操作棧頂位置top的兩種定義方式本書采用(a)的方式初始化棧、清空棧判空、判滿入棧入棧時，新元素放在element[top]處，然后top加1第1個元素入棧時放在數(shù)組下標(biāo)為0的位置因?yàn)閿?shù)組空間有限，最大容量是maxSize，所以入棧時需要判定棧不能是滿的出棧出棧時，需要先將top值減1，然后將element[top]處的值通過參數(shù)x返回出棧時需要判定棧不是空的獲取棧頂元素效率top的值既是保存下一個入棧元素的位置，也是棧中所含元素個數(shù)的計(jì)數(shù)器因?yàn)闂５娜霔２僮骷俺鰲２僮鞫荚跅ｍ斶M(jìn)行，所以入棧、出棧、獲取棧頂元素時都不需要移動棧中已有的元素，故時間復(fù)雜度都是O(1)判定?？占皸M等操作的時間復(fù)雜度也是O(1)例3-6也可以將數(shù)組下標(biāo)最大的一端作為棧底若一個棧保存在數(shù)組V[0..n-1]中，初始時棧頂指針top為n，則下列選項(xiàng)中，能夠正確實(shí)現(xiàn)x入棧操作的語句序列是（）。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對頂棧數(shù)組的兩個端點(diǎn)分別作為兩個棧的棧底左側(cè)棧占用數(shù)組0到k的單元，棧頂在k+1位置右側(cè)棧占用數(shù)組m-1到h的單元，棧頂在h-1位置此時必須滿足k<h，才能保證兩個棧不會重疊棧S1入棧時，棧頂值增大，出棧時棧頂值減小棧S2剛好相反，入棧時棧頂值減小，出棧時棧頂值增大例3-7若棧采用順序存儲方式存儲，現(xiàn)有兩個棧共享空間V[0..m-1]，棧1的底在v[0]，棧2的底在V[m-1]，初始時，棧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)綏?，可以看作是一個僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過頭指針完成。所以，在鏈?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ù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過x返回給調(diào)用者元素所占用的空間要釋放掉清空棧及判?？杖霔Ｈ霔r，需要創(chuàng)建一個新結(jié)點(diǎn)，并將新結(jié)點(diǎn)插入在棧頂位置順序棧與鏈?zhǔn)綏５谋容^實(shí)現(xiàn)順序棧和鏈?zhǔn)綏５乃胁僮鞫贾恍枰?shù)時間，因此棧的兩種實(shí)現(xiàn)方式的優(yōu)劣僅體現(xiàn)在它們的存儲效率上順序棧需要預(yù)先申請一個固定長度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個數(shù)相對較少時，空間浪費(fèi)較大鏈?zhǔn)綏５拈L度雖然可變，但是每個元素都需要一個指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開銷棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會開辟一個函數(shù)調(diào)用棧用來保存函數(shù)在調(diào)用過程中所需要的一些信息第二節(jié)

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

a0…am-1

↑front

↑rear

當(dāng)再進(jìn)行若干次入隊(duì)操作后，rear會到達(dá)數(shù)組的末尾，即最后一個下標(biāo)位置。之后再進(jìn)行入隊(duì)操作時，導(dǎo)致數(shù)組下標(biāo)越界。但數(shù)組的前半段可能會因出隊(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ì)操作會涉及到隊(duì)尾rear值的變化，rear=(rear+1)%n，出隊(duì)操作會涉及到隊(duì)頭front值的變化，front=(front+1)%n，其中n是數(shù)組的大小可以把這個數(shù)組想象成一個首尾相接的圓環(huán)，A[n-1]的后面是A[0]“循環(huán)”一詞的含義正是如此空與滿數(shù)組滿時，rear==front條件rear==front也代表空隊(duì)列解決方法：讓數(shù)組中始終剩余至少一個空位置。當(dāng)數(shù)組中僅有一個空位置時，就認(rèn)為已經(jīng)達(dá)到隊(duì)列的最大長度了，隊(duì)列已滿初始時，front=0且rear=0例3-9已知循環(huán)隊(duì)列存儲在一維數(shù)組A[0..n-1]中，且隊(duì)列非空時front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時隊(duì)列為空，且要求第一個進(jìn)入隊(duì)列的元素存儲在A[0]處，則初始時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)造一個空隊(duì)列，隊(duì)頭和隊(duì)尾指針均賦初值0清空隊(duì)列隊(duì)列置空也得到一個空隊(duì)列，可以將隊(duì)頭和隊(duì)尾指針均賦值0，和初始化隊(duì)列的結(jié)果一樣也可以讓隊(duì)頭和隊(duì)尾指針的值相等，表示是一個空隊(duì)列判空與判滿隊(duì)列為空的條件是rear==front隊(duì)列為滿的條件是(rear+1)%n==front求隊(duì)列長度入隊(duì)與出隊(duì)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列采用帶頭指針及尾指針的單鏈表作為隊(duì)列的存儲結(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ì)尾指針相等時，隊(duì)列為空空鏈?zhǔn)疥?duì)列中，隊(duì)頭指針和隊(duì)尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥?duì)列通常不會滿入隊(duì)列出隊(duì)例3-10若使用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列，則進(jìn)行入隊(duì)列操作時（）。A．僅需要修改隊(duì)頭指針，不需要修改隊(duì)尾指針B．僅需要修改隊(duì)尾指針，不需要修改隊(duì)頭指針C．隊(duì)尾指針一定要修改，隊(duì)頭指針也一定要修改D．隊(duì)尾指針一定要修改，隊(duì)頭指針可能要修改答案為D采用鏈?zhǔn)椒绞綄?shí)現(xiàn)隊(duì)列時，也可以配合使用一個空閑單元鏈表，使得入隊(duì)、出隊(duì)時盡量少地調(diào)用malloc函數(shù)及free函數(shù)在鏈?zhǔn)疥?duì)列中，可以將這兩個鏈表合在一起，形成一個圓環(huán)，即使用一個循環(huán)鏈表來表示鏈?zhǔn)疥?duì)列及對應(yīng)的空閑單元鏈表。在這個循環(huán)鏈表中，結(jié)點(diǎn)分為兩部分，一部分結(jié)點(diǎn)用來保存實(shí)際數(shù)據(jù)，另一部分結(jié)點(diǎn)是空閑結(jié)點(diǎn)帶空閑單元鏈表的鏈?zhǔn)疥?duì)列初始狀態(tài)第一個元素入隊(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ì)尾元素的后一個位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個元素，初始時為空。下列判斷隊(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ì)列的相互模擬使用棧來模擬隊(duì)列使用棧模擬的隊(duì)列類型定義typedefstruct{

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

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

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

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

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

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

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

u2+i2

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

u1+i1

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

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

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

5+4=44存儲地址為984+44

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

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

4A[8][4]的存儲地址 =A[0][4]的存儲地址+ A[0][4]與A[8][4]之間的偏移量 =1000+160=1160示例三維數(shù)組D3Array[3][2][4]按行主序下標(biāo)排列的形式對于三維數(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矩陣的壓縮存儲對稱矩陣和三角矩陣從節(jié)省存儲空間的角度考慮，對稱矩陣和上（下）三角矩陣，都可以只保存矩陣中約一半的元素，從而可以節(jié)省差不多一半的存儲空間這樣的存儲形式稱為壓縮存儲壓縮存儲對于對稱矩陣，因?yàn)閷蔷€以上及以下的元素對稱相等，所以只需要保存其中的一半及對角線上的元素即可對于上三角矩陣或下三角矩陣，僅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩陣有n行n列，則這三種形式下需要保存的元素個數(shù)為n

(n+1)/2三角部分

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

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

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

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

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