數(shù)據(jù)結(jié)構(gòu)與算法 課件 第1-3章 緒論、線性表、棧和隊列

全國高等教育自學考試指定教材

計算機應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第一章緒論學習目標了解數(shù)據(jù)結(jié)構(gòu)在計算機應(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ù)類型表示實際問題掌握算法的基本概念及重要特性，能夠使用類C語言描述算法掌握算法評估和復雜性度量的基本概念，能夠?qū)唵嗡惴ㄟM行復雜性評估理解算法的基本設(shè)計策略的特點，使用基本的算法策略實現(xiàn)簡單程序本章主要內(nèi)容基本概念和術(shù)語12算法和算法分析3算法設(shè)計策略簡介數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法是計算機專業(yè)的必修課程之一，在課程體系中占據(jù)非常重要的地位，起著承上啟下的作用，是學習其他計算機專業(yè)課程的基礎(chǔ)本章將介紹數(shù)據(jù)結(jié)構(gòu)的基本概念，還將介紹算法及其特性，介紹時間、空間復雜度的概念，在此基礎(chǔ)上，介紹對算法進行復雜度評估的基本方法第一節(jié)

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

基本概念和術(shù)語

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

學生信息示例——“線性”的關(guān)系某班30名同學的基本信息學號姓名性別出生日期籍貫M2022103001王義平男2004.11.22山東M2022103002陸東男2004.02.05河南M2022103003李曉敏女2005.01.15江蘇┇┇┇┇┇M2022103030楊志強男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)在計算機中的表示及存儲方式數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯上描述數(shù)據(jù)，表明數(shù)據(jù)元素之間的關(guān)系是什么樣的，這與數(shù)據(jù)的存儲方式無關(guān)，既獨立于計算機，也獨立于程序設(shè)計語言數(shù)據(jù)的最小不可分割的單位是數(shù)據(jù)項邏輯上相關(guān)的、具有物理意義的若干數(shù)據(jù)項構(gòu)成一個數(shù)據(jù)元素數(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)常用的存儲方法

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

第二節(jié)

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

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

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

上述程序的時間復雜度是（

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

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

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

若處理器速度增長10倍

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

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

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

貪心法貪心算法也稱貪婪算法，這是一種通過每一步選擇局部最優(yōu)解來達到整體最優(yōu)解的算法，適用于求某些最優(yōu)解問題求解過程中，一步一步地進行，根據(jù)當前的情況選擇最優(yōu)的可能實際上，這個最優(yōu)是在當前條件下的最優(yōu)，稱為局部最優(yōu)第四章構(gòu)造哈夫曼樹的過程采用了貪心法策略，第六章求最小生成樹的兩個算法也采用了貪心法求解分治法當求解一個輸入規(guī)模為n并且n的取值又很大的問題時，可以把這個大規(guī)模的問題分解為若干個規(guī)模更小且可以獨立求解的問題，然后把各個小問題的解進行合并，得到原問題的解。這就是分治法的思想一般來說，分治法的求解過程分為三個階段即劃分、求解小問題及小問題解的合并第七章介紹的快速排序和歸并排序都采用了分治法求解它們是將大問題分解為2個小問題動態(tài)規(guī)劃法動態(tài)規(guī)劃算法是求多階段決策過程最優(yōu)化的一種方法，它將問題的整體按時間或空間的特征分成若干個前后銜接的階段，把多階段決策問題表示為前后有關(guān)的一系列單階段決策問題，然后逐個求解，從而求出整個問題的最優(yōu)決策動態(tài)規(guī)劃法強調(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!全國高等教育自學考試指定教材

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

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

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

示例

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

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

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

(M2022103030楊志強男2004.10.30陜西))

線性表中常使用非負整數(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ū)，直接后繼可以簡稱為后繼“線性”的含義和特點除表頭a0外，每個元素有且僅有一個直接前驅(qū)除表尾an-1外，每個元素有且僅有一個直接后繼線性表中各元素的次序是固有的，即元素ai(1≤i≤n-2)排在ai-1之后，且排在元素ai+1之前

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

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

例2-2寫出10以內(nèi)（不含10）的非負偶數(shù)組成的線性表10以內(nèi)（不含10）的非負偶數(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返回的是線性表的當前長度，即線性表所含元素的個數(shù)find返回的是要查找的元素x在表中第一次出現(xiàn)的位置。如果表中不包含x，則返回-1當表為空時，isEmpty返回1，否則返回0。當表已滿時，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é)

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

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

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

設(shè)LOC(ai)表示元素ai的存儲首地址，每個元素需占用d個存儲單元，則有 LOC(ai)=LOC(ai-1)+d進一步地有 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順序表基本運算的實現(xiàn)順序表的定義構(gòu)造空表及清空表判表空、判表滿、求表長插入新元素插入操作中移動元素的平均次數(shù)為n/2刪除操作刪除操作中移動元素的平均次數(shù)為(n-1)/2賦值、取值操作查找測試例2-5設(shè)有順序表L，表長為n，保存在數(shù)組A中。實現(xiàn)算法將L逆置，即 L=(a0,a1,…,an-2,an-1)變?yōu)?L=(an-1,an-2,…,a1,a0)將A[0]與A[n-1]進行交換，然后將A[1]與A[n-2]進行交換，依此類推，當交換到L中間元素時，算法結(jié)束算法實現(xiàn)第三節(jié)

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

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

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

E單鏈表的空間需求為n

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

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

10=300個字節(jié)。使用這些空間保存單鏈表中的結(jié)點的話，可以保存300/12=25在不考慮表頭結(jié)點占用的空間的前提下，如果L中元素個數(shù)少于25個，則采用單鏈表更省空間如果多于25個元素，則采用數(shù)組更省空間如果正好是25個元素，則單鏈表和數(shù)組占用的空間是一樣大的如何選擇當線性表元素個數(shù)變化較大或者未知時，最好使用鏈表實現(xiàn)如果用戶事先知道線性表的大致長度，則使用順序表的空間效率會更高些還要考慮到，順序表占用的空間是連續(xù)的，而鏈表占用的空間可能是零散的，并且還需要程序員來管理空間的分配及釋放操作的時間復雜度也要考慮在順序表中是直接定位的，可以實現(xiàn)隨機訪問，操作的時間復雜度是O(1)單鏈表不能隨機訪問指定的元素，平均時間復雜度和最差時間復雜度均為O(n)在給出指向鏈表的當前指針后，在單鏈表內(nèi)進行插入和刪除操作的時間復雜度也可以達到O(1)順序表的插入和刪除操作，平均和最差時間復雜度均為O(n)空閑單元鏈表鏈表中，當需要在鏈表中插入一個結(jié)點時，需要調(diào)用malloc函數(shù)分配相應(yīng)的空間當在鏈表中刪除一個結(jié)點時，需要調(diào)用delete函數(shù)釋放空間。如果在鏈表中頻繁進行插入、刪除結(jié)點的操作，則頻繁調(diào)用這些函數(shù)的時間開銷會是非?？捎^的可以針對實際應(yīng)用的每類鏈表，定義一個“伙伴鏈表”，表結(jié)點的結(jié)構(gòu)與所使用的鏈表結(jié)構(gòu)一致伙伴鏈表用來管理暫時不用的結(jié)點，可以將伙伴鏈表稱為空閑單元鏈表假設(shè)，保存數(shù)據(jù)的單鏈表為L當從鏈表L中刪除一個結(jié)點時，將這個結(jié)點插入到freelist中當需要申請新的結(jié)點空間時，先查看鏈表freelist。如果freelist不空，則從freelist中獲取一個結(jié)點，結(jié)點中保存相應(yīng)的值，并將該結(jié)點插入到L的相應(yīng)位置，否則調(diào)用malloc函數(shù)分配新的空間，并完成后續(xù)的插入操作插入操作的實現(xiàn)刪除操作的實現(xiàn)清空表的操作靜態(tài)鏈表靜態(tài)鏈表的特點保存在數(shù)組中兼具順序表和鏈表特性，空間不零碎，插入刪除不需要移動元素鏈表及靜態(tài)鏈表在前一個靜態(tài)鏈表中插入元素E后的靜態(tài)鏈表刪除元素D后的靜態(tài)鏈表類型定義初始化靜態(tài)鏈表清空靜態(tài)鏈表判空、判滿、求表長的實現(xiàn)插入操作的實現(xiàn)刪除操作的實現(xiàn)例2-14設(shè)雙向靜態(tài)有序鏈表L保存在含8個元素的數(shù)組A中，表頭結(jié)點在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é)點如果知道了單鏈表的長度，那么訪問倒數(shù)第k個結(jié)點就很容易了。假設(shè)單鏈表長度為n，則倒數(shù)第k個結(jié)點即是第n-k+1個結(jié)點使用兩個指針front和rear，均從表頭開始同步向表尾方向移動初始時，先令front前進k步，當個“排頭兵”這樣front和rear指向的位置相距k個結(jié)點然后兩個指針同步前進當front到達表尾時，rear即位于倒數(shù)第k個結(jié)點查找倒數(shù)第k個結(jié)點程序查找單鏈表的中間結(jié)點使用兩個指針，并同時從表頭開始向表尾方向移動，一個指針一次走兩步，另一個指針一次走一步。這樣，當“排頭兵”指針到達表尾時，后面的指針即指向鏈表的中間結(jié)點。與findKth函數(shù)中一樣，兩個指針分別是front和rear程序?qū)捂湵砟嬷脤τ趩捂湵淼钠渌Y(jié)點，讓middle所指結(jié)點的next域指向left所指結(jié)點，即left所指結(jié)點的原后繼（middle所指）變?yōu)樗男虑膀?qū)。然后，三個指針依次后移一個位置當所有結(jié)點中的next域都轉(zhuǎn)向后，再將head所指的頭結(jié)點鏈接在表頭處程序驗證程序ThankYou!全國高等教育自學考試指定教材

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

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

通常指定an-1一端為棧頂，a0一端是棧底棧中元素個數(shù)n稱為棧的長度，當n=0時，稱為空棧棧具有后進先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿，就允許入棧當沒有其他的特殊限制時，對于同一個入棧序列，可能會得到很多個合理正確的出棧序列棧的基本操作出棧序列個數(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并入棧。下列選項中，不可能是出棧序列的是（）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依次進入初始為空的棧中，在所有可能的出棧序列中，以元素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棧的存儲及其實現(xiàn)棧有兩種主要的存儲方式順序存儲鏈式存儲順序存儲方式使用數(shù)組保存棧元素，得到的是順序棧鏈式存儲方式使用單鏈表保存棧元素，得到的是鏈式棧順序棧及其實現(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標為0的位置同時使用一個變量標記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱為棧頂指針順序棧的定義typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 inttop; //棧頂位置}SeqStack;順序棧的基本操作棧頂位置top的兩種定義方式本書采用(a)的方式初始化棧、清空棧判空、判滿入棧入棧時，新元素放在element[top]處，然后top加1第1個元素入棧時放在數(shù)組下標為0的位置因為數(shù)組空間有限，最大容量是maxSize，所以入棧時需要判定棧不能是滿的出棧出棧時，需要先將top值減1，然后將element[top]處的值通過參數(shù)x返回出棧時需要判定棧不是空的獲取棧頂元素效率top的值既是保存下一個入棧元素的位置，也是棧中所含元素個數(shù)的計數(shù)器因為棧的入棧操作及出棧操作都在棧頂進行，所以入棧、出棧、獲取棧頂元素時都不需要移動棧中已有的元素，故時間復雜度都是O(1)判定棧空及棧滿等操作的時間復雜度也是O(1)例3-6也可以將數(shù)組下標最大的一端作為棧底若一個棧保存在數(shù)組V[0..n-1]中，初始時棧頂指針top為n，則下列選項中，能夠正確實現(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ù)組的兩個端點分別作為兩個棧的棧底左側(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鏈式棧所謂的鏈式棧，可以看作是一個僅在表頭位置進行操作的單鏈表將頭指針所指的這一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過頭指針完成。所以，在鏈式棧中，可以只定義頭指針，尾指針及頭結(jié)點都可以不定義鏈式棧的定義typedefintELEMType;typedefstructnode{ //鏈式棧結(jié)點

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

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

a0…am-1

↑front

↑rear

當再進行若干次入隊操作后，rear會到達數(shù)組的末尾，即最后一個下標位置。之后再進行入隊操作時，導致數(shù)組下標越界。但數(shù)組的前半段可能會因出隊操作而有空閑的單元

x…y

↑front

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

……u…

↑rear

↑front

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

ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循環(huán)隊列初始化構(gòu)造一個空隊列，隊頭和隊尾指針均賦初值0清空隊列隊列置空也得到一個空隊列，可以將隊頭和隊尾指針均賦值0，和初始化隊列的結(jié)果一樣也可以讓隊頭和隊尾指針的值相等，表示是一個空隊列判空與判滿隊列為空的條件是rear==front隊列為滿的條件是(rear+1)%n==front求隊列長度入隊與出隊鏈式隊列鏈式隊列采用帶頭指針及尾指針的單鏈表作為隊列的存儲結(jié)構(gòu)單鏈表的頭指針可以當作隊頭指針front，尾指針可以當作隊尾指針rear鏈式隊列的定義typedefintELEMType;typedefstructnode{ //鏈式隊列中結(jié)點 ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //鏈式隊列 LinkQueueNode*front,*rear; //隊頭指針、隊尾指針}LinkQueue;初始化、清空隊列判空循環(huán)隊列中，當隊頭指針和隊尾指針相等時，隊列為空空鏈式隊列中，隊頭指針和隊尾指針都為NULL在內(nèi)存足夠大的情況下，鏈式隊列通常不會滿入隊列出隊例3-10若使用不帶頭結(jié)點的單鏈表存儲隊列，則進行入隊列操作時（）。A．僅需要修改隊頭指針，不需要修改隊尾指針B．僅需要修改隊尾指針，不需要修改隊頭指針C．隊尾指針一定要修改，隊頭指針也一定要修改D．隊尾