算法設(shè)計(jì)與分析 思政課件 第1、2章 緒論、常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用

《算法設(shè)計(jì)與分析》教材：《算法設(shè)計(jì)與分析基礎(chǔ)》（C++語(yǔ)言描述），李春葆等清華大學(xué)出版社2022《算法設(shè)計(jì)與分析基礎(chǔ)（C++語(yǔ)言描述）學(xué)習(xí)與實(shí)驗(yàn)指導(dǎo)》，李春葆等清華大學(xué)出版社20221/43第1章概論1.1算法的概念1.2算法分析CONTENTS提綱2/43算法（algorithm）是求解問(wèn)題的一系列計(jì)算步驟，是一個(gè)由若干運(yùn)算或指令組成的有限序列，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。算法輸入輸出1.1.1什么是算法1.1算法的概念3/43算法的5大特性有窮性：在有限步之后結(jié)束。確定性：每一條指令必須有確切的含義，不會(huì)產(chǎn)生二義性?？尚行裕喝藗儍H用筆和紙做有限次運(yùn)算就能完成。輸入：有零個(gè)或多個(gè)輸入。輸出：有一個(gè)或多個(gè)輸出。4/43算法（有窮性、確定性、可行性）輸入輸出求解問(wèn)題5/43【例1-1】有下列兩段描述：

描述1：

描述2：voidexam1() voidexam2(){ intn; { intx,y; n=2; y=0; while(n%2==0) x=5/y; n=n+2; printf("%d,%d\n",x,y); printf("%d\n",n); }}違反有窮性違反可行性6/43算法設(shè)計(jì)要求正確性：對(duì)指定的每個(gè)輸入實(shí)例都能輸出正確的結(jié)果并停止?？墒褂眯裕河脩粲押眯浴？勺x性：算法邏輯清晰、簡(jiǎn)單和結(jié)構(gòu)化。健壯性：容錯(cuò)性。高效率與低存儲(chǔ)量：好的時(shí)空性能。7/431.1.2算法描述C/C++語(yǔ)言描述算法一般形式boolSum1(intn，ints){ if(n<=0)returnfalse; //參數(shù)錯(cuò)誤時(shí)返回假 s=0; for(inti=1;i<=n;i++) s+=i; returntrue; //參數(shù)正確并計(jì)算出正確結(jié)果時(shí)返回真}算法的返回值：正確執(zhí)行時(shí)返回真，否則返回假算法形參8/43Sum1錯(cuò)誤：inta=10;b=0，調(diào)用Sum1(a,b)b=0。錯(cuò)誤原因：s為輸出參數(shù)，沒(méi)有按輸出參數(shù)設(shè)計(jì)。C++中增加了引用參數(shù)，一個(gè)參數(shù)名前面加上&就變?yōu)橐脜?shù)。引用參數(shù)在執(zhí)行后會(huì)將結(jié)果回傳給對(duì)應(yīng)的實(shí)參。9/43boolSum2(intn，int&s){ if(n<=0)returnfalse; //參數(shù)錯(cuò)誤時(shí)返回假 s=0; for(inti=1;i<=n;i++) s+=i; returntrue; //參數(shù)正確并計(jì)算出正確結(jié)果時(shí)返回真}算法的返回值：正確執(zhí)行時(shí)返回真，否則返回假引用參數(shù)正確的算法10/43②①①①①intmain(){…

fun(a，b)…}intfun(intn,ints){

…}函數(shù)調(diào)用①：?jiǎn)蜗蛑祩鬟f

②：回傳intmain(){

…

fun(a，b)…}intfun(intn,int&s){

…}引用和非引用參數(shù)的差別11/43intSum3(intn){ints=0;for(inti=1;i<=n;i++)s+=i;returns;}簡(jiǎn)單的算法：只有一個(gè)輸出并且通過(guò)約束輸入總能夠得到正確結(jié)果時(shí)，可以直接用函數(shù)返回值表示輸出。12/431.1.3算法和數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的基礎(chǔ)。算法的操作對(duì)象是數(shù)據(jù)結(jié)構(gòu)。在設(shè)計(jì)算法時(shí)通常要構(gòu)建適合這種算法的數(shù)據(jù)結(jié)構(gòu)。13/431.1.4算法設(shè)計(jì)的基本步驟分析求解問(wèn)題選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)策略描述算法證明算法正確性算法分析建立數(shù)學(xué)模型14/431.2算法分析1.2.1算法時(shí)間復(fù)雜度分析1.什么是算法時(shí)間復(fù)雜度分析事前分析估算法：認(rèn)為算法的“運(yùn)行工作量”的大小只依賴(lài)于問(wèn)題規(guī)模n，或者說(shuō)它是問(wèn)題規(guī)模的函數(shù)。算法執(zhí)行時(shí)間是算法中所有語(yǔ)句的執(zhí)行時(shí)間之和，顯然與算法中所有語(yǔ)句的執(zhí)行次數(shù)成正比，可以簡(jiǎn)單地用算法中基本操作的執(zhí)行次數(shù)來(lái)度量。算法中的基本操作是指最深層循環(huán)內(nèi)的原操作，它對(duì)算法執(zhí)行時(shí)間的貢獻(xiàn)最大，是算法中最重要的操作。算法中所有基本操作的執(zhí)行次數(shù)為f(n)。15/43算法時(shí)間復(fù)雜度分析是一種漸進(jìn)分析，是指當(dāng)問(wèn)題規(guī)模n很大并趨于無(wú)窮大時(shí)對(duì)算法的時(shí)間性能分析，可表示為同時(shí)忽略低階項(xiàng)和最高階系數(shù)。16/43算法分析問(wèn)題規(guī)模n，找出其中的基本語(yǔ)句，求出其運(yùn)算次數(shù)f(n)用大O、大

或大

表示17/432.漸

進(jìn)符號(hào)（O、

和

）定義1

f(n)=O(g(n))（讀作“f(n)是g(n)的大O”），其含義是存在正常量c和n0，使得當(dāng)n≥n0時(shí)，有0≤f(n)≤cg(n)也就是說(shuō)f(n)的階不高于g(n)的階，稱(chēng)g(n)為f(n)的上界。cg(n)f(n)nf(n)=O(g(n))n0可以利用極限來(lái)證明，即如果=c并且c≠∞，則有f(n)=O(g(n))。18/43一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=O(nm)。例如3n+2=O(n)，因?yàn)?/p>

成立。10n2+4n+2=O(n4)，因?yàn)?/p>

成立。=c≠∞，則有f(n)=O(g(n))。19/43定義2

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c和n0，使得當(dāng)n≥n0時(shí)，f(n)≥cg(n)也就是說(shuō)f(n)的階不低于g(n)的階，稱(chēng)g(n)為f(n)的下界。f(n)cg(n)nf(n)=

(g(n))n0可以利用極限來(lái)證明，即如果

并且c≠0，則有f(n)=

(g(n))。20/43≠0，則有f(n)=

(g(n))。例如3n+2=

(n)，因?yàn)?/p>

成立。10n2+4n+2=

(n)，因?yàn)?/p>

成立。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。21/43c2g(n)c1g(n)f(n)n0nf(n)=

(g(n))定義3

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c1、c2和n0，使得當(dāng)n≥n0時(shí)，有

c1g(n)≤f(n)≤c2g(n)也就是說(shuō)g(n)與f(n)的同階，也稱(chēng)g(n)為f(n)的確界?？梢岳脴O限來(lái)證明，即如果

并且0<c<∞，則有f(n)=

(g(n))。22/43，0<c<∞，則有f(n)=

(g(n))。例如3n+2=

(n)。10n2+4n+2=

(n2)。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。23/43大

符號(hào)比大O符號(hào)和大

符號(hào)都要精確，f(n)=

(g(n))隱含著f(n)=O(g(n))和f(n)=

(g(n))。目前國(guó)內(nèi)大部分教科書(shū)中習(xí)慣使用大O符號(hào)，本書(shū)主要也采用這種表示形式。說(shuō)明24/43【例1-2】分析以下算法的時(shí)間復(fù)雜度。voidfun(intn){ints=0,i,j,k;for(i=0;i<n;i++)for(j=0;j<i;j++)for(k=0;k<j;k++)

s++;}算法的基本操作是s++該算法的時(shí)間復(fù)雜度為O(n3)。解25/433.漸進(jìn)符號(hào)的特性（1）傳遞性f(n)=O(g(n))，g(n)=O(h(n))

f(n)=O(h(n))f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))（2）自反性f(n)=O(f(n))f(n)=

(f(n))f(n)=

(f(n))（3）對(duì)稱(chēng)性f(n)=

(g(n))

g(n)=

(f(n))26/434.算法的最好、最壞和平均情況分析定義4設(shè)一個(gè)算法的輸入規(guī)模為n，Dn是所有輸入的集合，任一輸入I∈Dn，P(I)是I出現(xiàn)的概率，有P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本操作次數(shù)，則該算法的平均執(zhí)行時(shí)間為A(n)=

I∈DnP(I)*T(I)對(duì)應(yīng)的時(shí)間復(fù)雜度稱(chēng)為平均時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度反映算法的總體時(shí)間性能。27/43算法的最好情況為G(n)=minI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最少執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱(chēng)為最好時(shí)間復(fù)雜度，最好時(shí)間復(fù)雜度反映算法的最佳性能，即為算法的時(shí)間下界。算法的最壞情況為W(n)=maxI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最大執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱(chēng)為最懷時(shí)間復(fù)雜度，最懷時(shí)間復(fù)雜度為算法的時(shí)間上界。28/43【例1-4】設(shè)計(jì)一個(gè)盡可能高效的算法，在長(zhǎng)度為n的一維整型數(shù)組a[0..n-1]中查找值最大的元素maxe和值最小的元素mine。并分析算法的最好、最壞和平均時(shí)間復(fù)雜度。解voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}29/43該算法的基本語(yǔ)句是元素比較。最好的情況是a中元素遞增排列，元素比較次數(shù)為n-1，即G(n)=n-1=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}30/43最壞的情況是a中元素遞減排列，元素比較次數(shù)為2(n-1)，即W(n)=2(n-1)=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}31/43平均情況下，a中有一半的元素比maxe大，a[i]>maxe比較執(zhí)行n-1次，a[i]<mine比較執(zhí)行(n-1)/2次，因此平均元素比較次數(shù)為3(n-1)/2，即A(n)=3(n-1)/2=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}32/43【例1-5】采用順序查找方法，在長(zhǎng)度為n的一維實(shí)數(shù)數(shù)組a[0..n-1]中查找值為x的元素，即從數(shù)組的第一個(gè)元素開(kāi)始，逐個(gè)與被查值x進(jìn)行比較。找到后返回true，否則返回false。boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}回答以下問(wèn)題：

（1）分析該算法在等概率情況下成功查找到值為x的元素的最好、最壞和平均時(shí)間復(fù)雜度。

（2）假設(shè)被查值x在數(shù)組a中的概率是p，不在數(shù)組a中的概率是1-p，求算法的平均時(shí)間復(fù)雜度。33/43

（1）算法的while循環(huán)中if語(yǔ)句是基本操作（用于元素比較）。a數(shù)組中有n個(gè)元素，當(dāng)?shù)谝粋€(gè)元素a[0]等于x，此時(shí)基本操作僅執(zhí)行一次，此時(shí)呈現(xiàn)最好的情況，即G(n)=1=O(1)。

當(dāng)a中最后一個(gè)元素a[n-1]等于x，此時(shí)基本操作執(zhí)行n次，此時(shí)呈現(xiàn)最壞的情況，即W(n)=n=O(n)。解boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}34/43對(duì)于成功查找的平均情況，假設(shè)查找到每個(gè)元素的概率相同，則P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素時(shí)基本操作正好執(zhí)行i+1次，所以：boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}35/43（2）這里是既考慮成功查找又考慮不成功查找的情況。

對(duì)于成功查找，被查值x在數(shù)組a中的概率為p時(shí)，算法執(zhí)行有n種成功情況，在等概率情況下元素a[i]被查找到的概率P(a[i])=p/n，成功找到a[i]元素時(shí)基本操作執(zhí)行i+1次。

對(duì)于不成功查找，其概率為1-p，所有不成功查找基本操作都只執(zhí)行n次，不妨看成一種情況。如果已知查找的x有一半的機(jī)會(huì)在數(shù)組中，此時(shí)p=1/2，則A(n)=[(n+1)/4]+n/2≈3n/4。36/434.平攤分析考慮這樣一種算法，在算法中有一種操作反復(fù)執(zhí)行時(shí)有這樣的特性，其運(yùn)行時(shí)間始終變動(dòng)，如果這一操作在大多數(shù)時(shí)候運(yùn)行很快，只是偶爾要花費(fèi)大量時(shí)間，對(duì)這樣的算法可以采用平攤分析。在平攤分析中，執(zhí)行一系列數(shù)據(jù)結(jié)構(gòu)操作所需要的時(shí)間是通過(guò)對(duì)執(zhí)行的所有操作求平均而得出的。平攤分析可用來(lái)證明在一系列操作中，即使單一的操作具有較大的代價(jià)，通過(guò)對(duì)所有操作求平均后，平均代價(jià)還是很小的。37/43【例1-6】假設(shè)有一個(gè)可以存放若干個(gè)整數(shù)的整數(shù)表，其類(lèi)型為L(zhǎng)ist，data域是存放整數(shù)元素的動(dòng)態(tài)數(shù)組，capacity域表示data的容量（data數(shù)組中能夠存放的最多元素個(gè)數(shù)，初始容量為常數(shù)m），length域表示長(zhǎng)度（data數(shù)組中存放的實(shí)際元素個(gè)數(shù)）。#definem2 //初始容量常數(shù)structList

//整數(shù)表的類(lèi)型{ int*data; //動(dòng)態(tài)數(shù)組 intlength; //長(zhǎng)度 intcapacity; //容量};38/43整數(shù)表提供有這些運(yùn)算：初始化Init，即設(shè)置初始容量、分配初始空間和將長(zhǎng)度置為0。私有方法Expand()用于擴(kuò)大容量，當(dāng)長(zhǎng)度達(dá)到容量時(shí)置新容量為兩倍長(zhǎng)度。Add(e)用于在表尾插入元素e。各個(gè)算法如下：voidInit(List&L) //初始化{ L.capacity=m; L.data=newint[L.capacity]; L.length=0;}39/43要求分析調(diào)用Add(e)算法的時(shí)間復(fù)雜度。voidExpand(List&L) //按長(zhǎng)度兩倍擴(kuò)大容量{ int*p=L.data; L.capacity=2*L.length; //設(shè)置新容量 L.data=newint[L.capacity]; for(inti=0;i<L.length;i++) //復(fù)制全部元素 L.data[i]=p[i]; deletep;}voidAdd(List&L,inte) //添加e{ if(L.length==L.capacity)

Expand(L); L.data[L.length]=e; L.length++;}40/43Expand()算法中for循環(huán)執(zhí)行n次（n為復(fù)制的元素個(gè)數(shù)），所以其時(shí)間復(fù)雜度為O(n)。Add(e)算法中可能會(huì)調(diào)用Expand(L)（調(diào)用一次稱(chēng)為一次擴(kuò)容），那么其時(shí)間復(fù)雜度是不是也為O(n)呢？插入n個(gè)元素調(diào)用一次Expand(L)，調(diào)用Expand(L)的時(shí)間為O(n)，其他n-1次插入的時(shí)間為O(1)，平攤結(jié)果是解41/431.2.2算法空間復(fù)雜度分析一個(gè)算法的存儲(chǔ)量包括形參所占空間和臨時(shí)變量所占空間。在對(duì)算法進(jìn)行存儲(chǔ)空間分析時(shí)，只考察臨時(shí)變量所占空間?？臻g復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間大小的量度，一般也作為問(wèn)題規(guī)模n的函數(shù)，以數(shù)量級(jí)形式給出，記作S(n)=O(g(n))、

(g(n))或

(g(n))，其中漸進(jìn)符號(hào)的含義與時(shí)間復(fù)雜度中的含義相同。42/43intmax(inta[]，intn){ intmaxi=0; for(inti=1;i<n;i++) if(a[i]>a[maxi]) maxi=i;

returna[maxi];}函數(shù)體內(nèi)分配的變量空間為臨時(shí)空間，不計(jì)形參占用的空間，這里的僅計(jì)i、maxi變量的空間，其空間復(fù)雜度為O(1)。算法的臨時(shí)空間43/4344/43思政案例第2章常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用2.1線性表2.3棧,隊(duì)列和雙端隊(duì)列2.2字符串2.4二叉樹(shù)和優(yōu)先隊(duì)列CONTENTS提綱2.5樹(shù)和并查集2.6圖2.7二叉排序樹(shù)和平衡二叉樹(shù)2.8哈希表2.9設(shè)計(jì)好的數(shù)據(jù)結(jié)構(gòu)45/9146/912.1線性表2.1.1線性表的定義線性表是性質(zhì)相同的n（n≥0）個(gè)元素的有限序列。每個(gè)元素有唯一的序號(hào)或者位置，也稱(chēng)為下標(biāo)或者索引，通常下標(biāo)是介于0到n-1之間。線性表中的n個(gè)元素從頭到尾分別稱(chēng)為第0個(gè)元素，第1個(gè)元素，依此類(lèi)推。47/91順序表：線性表的順序存儲(chǔ)結(jié)構(gòu)1.順序表structSqList

//順序表類(lèi)型{ intdata[MaxSize]; //MaxSize為data數(shù)組的容量 intlength; //順序表長(zhǎng)度即實(shí)際元素個(gè)數(shù) SqList():length(0){} //構(gòu)造函數(shù)};整數(shù)順序表類(lèi)型48/91鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.鏈表struct

ListNode

//單鏈表結(jié)點(diǎn)類(lèi)型{int

val; //結(jié)點(diǎn)值ListNode

*next; //后繼結(jié)點(diǎn)的地址ListNode()

:

val(0),

next(NULL)

{} //默認(rèn)構(gòu)造函數(shù)ListNode(int

x)

:

val(x),

next(NULL)

{} //重載構(gòu)造函數(shù)1ListNode(int

x,

ListNode

*next):val(x),

next(next)

{} //重載構(gòu)造函數(shù)2};整數(shù)單鏈表結(jié)點(diǎn)類(lèi)型49/91帶頭結(jié)點(diǎn)的單鏈表head…首結(jié)點(diǎn)尾結(jié)點(diǎn)頭結(jié)點(diǎn)

a0an-1∧a1head結(jié)點(diǎn)序號(hào)01n-1…查找序號(hào)為i的結(jié)點(diǎn)插入序號(hào)為i的結(jié)點(diǎn)刪除序號(hào)為i的結(jié)點(diǎn)基本運(yùn)算50/912.1.2vector向量容器v[0]v[1]v[2]…v[n-1]空閑空間表頭表尾長(zhǎng)度為n容量為c51/911.vector的特點(diǎn)v容器相當(dāng)于動(dòng)態(tài)數(shù)組，用于存儲(chǔ)具有相同數(shù)據(jù)類(lèi)型的一組元素，其容量為c（容量表示最多存放的元素個(gè)數(shù)），長(zhǎng)度為n。v容器具有隨機(jī)存取特性?？梢詮膙容器的末尾快速插入和刪除元素，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(1)。在v容器的中間插入和刪除元素速度較慢。v容器具有自動(dòng)擴(kuò)容功能。52/912.定義vector向量vector<int>v1; //定義元素為int的向量v1vector<int>v2(2);

//定義向量v2的容量和長(zhǎng)度為2（2個(gè)元素均為int默認(rèn)值0）vector<double>v3(2，1.2);

//定義向量v3的容量和長(zhǎng)度為2（2個(gè)元素均為double值1.2）vector<int>v4(a，a+5);

//用數(shù)組a[0..4]共5個(gè)元素初始化向量v453/913.vector的成員函數(shù)類(lèi)型成員函數(shù)功能說(shuō)明容量empty()判斷當(dāng)前向量容器是否為空size()返回當(dāng)前向量容器的長(zhǎng)度reserve(c)為當(dāng)前向量容器預(yù)分配c個(gè)元素的存儲(chǔ)空間capacity()返回當(dāng)前向量容器的容量resize(n)

調(diào)整當(dāng)前向量容器的長(zhǎng)度，使其能容納n個(gè)元素訪問(wèn)元素back()返回當(dāng)前向量容器的末尾元素front()返回當(dāng)前向量容器的首元素[idx]返回指定下標(biāo)idx的元素at[idx]同[idx]54/91類(lèi)型成員函數(shù)功能說(shuō)明更新push_back(e)在當(dāng)前向量容器末尾添加了一個(gè)元素eemplace_back(e)同push_back(e)，采用原地構(gòu)造對(duì)象再添加insert(pos,e)在pos位置插入元素e，即將元素e插入到迭代器pos指定元素之前emplace(pos,e)同insert(pos,e)，采用原地構(gòu)造對(duì)象再插入erase()刪除當(dāng)前向量容器中某個(gè)迭代器或者迭代器區(qū)間指定的元素clear()刪除當(dāng)前向量容器中所有元素迭代器begin()返回當(dāng)前向量容器中首元素的迭代器end()返回當(dāng)前向量容器中末尾元素的后一個(gè)元素的迭代器rbegin()返回當(dāng)前向量容器中末尾元素的迭代器rend()返回當(dāng)前向量容器中首元素的前一個(gè)元素的迭代器55/914.vector的應(yīng)用【例2-1】假設(shè)一個(gè)整數(shù)序列采用向量容器v存放，設(shè)計(jì)一個(gè)盡可能高效的算法刪除v中所有的奇數(shù)元素，要求刪除后v中元素的相對(duì)次序保持不變。56/91解法1：整體建表法。先將結(jié)果v看成是一個(gè)空表，用k表示結(jié)果v的元素個(gè)數(shù)（初始為0），用i遍歷v，遇到偶數(shù)時(shí)重新插入到v中，遇到奇數(shù)時(shí)跳過(guò)。最后置v的長(zhǎng)度為k。voiddelodd1(vector<int>&v) //解法1的算法{intk=0; //k記錄結(jié)果v中的元素個(gè)數(shù)inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶數(shù){v[k]=v[i]; //將v[i]重新插入到結(jié)果v中k++; //結(jié)果v的長(zhǎng)度增1}i++;}v.resize(k); //設(shè)置v的長(zhǎng)度為k}解57/91解法2：移動(dòng)法。先將結(jié)果v看成是整個(gè)表，用k表示要?jiǎng)h除的元素個(gè)數(shù)（初始為0），用i遍歷v，遇到偶數(shù)時(shí)將v[i]前移k個(gè)位置，遇到奇數(shù)時(shí)將k增1。最后置v的長(zhǎng)度為n-k。voiddelodd2(vector<int>&v) //解法2的算法{intk=0; //k記錄刪除的元素個(gè)數(shù)inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶數(shù)v[i-k]=v[i]; //將v[i]前移k個(gè)位置else //v[i]是奇數(shù)k++; //奇數(shù)元素個(gè)數(shù)增1i++;}v.resize(v.size()-k); //設(shè)置v的長(zhǎng)度為n-k}58/91解法3：區(qū)間劃分法。用v[0..k]（共k+1個(gè)元素）表示保留的元素區(qū)間（即偶數(shù)區(qū)間），初始時(shí)偶數(shù)區(qū)間為空，所以置k=-1。v[k+1..i-1]（共i-k-1個(gè)元素）表示刪除的元素區(qū)間（即奇數(shù)區(qū)間），i從0開(kāi)始遍歷v，初始時(shí)奇數(shù)區(qū)間也為空。

vi

…vn-1偶數(shù)區(qū)間v0…vkvk+1

…vi-1奇數(shù)區(qū)間

①若v[i]為偶數(shù)，將其添加到偶數(shù)區(qū)間的末尾，再執(zhí)行i++繼續(xù)遍歷。

②若v[i]為奇數(shù)，只需要執(zhí)行i++擴(kuò)大奇數(shù)區(qū)間，再繼續(xù)遍歷。

最后的結(jié)果v中僅保留所有偶數(shù)區(qū)間的k+1個(gè)元素，即置v的長(zhǎng)度為k+1。59/91voiddelodd3(vector<int>&v) //解法3的算法{intk=-1; //v[0..k]表示偶數(shù)元素的區(qū)間inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶數(shù){k++; //擴(kuò)大偶數(shù)區(qū)間swap(v[k],v[i]); //v[k]和v[i]交換}i++;}v.resize(k+1); //設(shè)置v的長(zhǎng)度為k+1}

vi

…vn-1偶數(shù)區(qū)間v0…vkvk+1

…vi-1奇數(shù)區(qū)間60/912.1.3STL通用算法1.常用的通用算法類(lèi)型函數(shù)功能說(shuō)明非更新的序列操作find在指定的[beg，end)范圍內(nèi)查找指定值的元素find_if在指定的[beg，end)范圍內(nèi)查找滿足指定條件的元素count在指定的[beg，end)范圍內(nèi)查找指定值出現(xiàn)的次數(shù)count_if在指定的[beg，end)范圍內(nèi)查找滿足指定條件的次數(shù)更新的序列操作copy復(fù)制指定的[beg，end)范圍內(nèi)的元素swap交換replace將指定的[beg，end)范圍內(nèi)的所有值替換為新值replace_if將指定的[beg，end)范圍內(nèi)滿足條件的所有值替換為新值remove刪除指定的[beg，end)范圍內(nèi)的所有指定的值remove_if刪除指定的[beg，end)范圍內(nèi)的所有滿足指定條件的值unique刪除相鄰重復(fù)的值（并非真正刪除，僅僅將保留的值前移）reverse將指定的[beg，end)范圍內(nèi)的所有值翻轉(zhuǎn)61/91類(lèi)型函數(shù)功能說(shuō)明排序sort非穩(wěn)定的排序stable_sort穩(wěn)定的排序is_sorted檢測(cè)有序性有序序列的二分查找lower_bound在[beg，end)內(nèi)查找第一個(gè)大于等于指定值的元素upper_bound在[beg，end)內(nèi)查找第一個(gè)大于指定值的元素binary_search在指定[beg，end)范圍內(nèi)查找指定值的元素合并merge合并兩個(gè)有序序列set_union求兩個(gè)有序序列的并集set_intersection求兩個(gè)有序序列的交集set_difference求兩個(gè)有序序列的差集數(shù)學(xué)min求兩個(gè)值的最小值max求兩個(gè)值的最大值min_element求一個(gè)序列中的最小值max_element求一個(gè)序列中的最大值accumulate求指定的[beg，end)范圍內(nèi)的值之和其他next_permutation產(chǎn)生下一個(gè)排列prev_permutation產(chǎn)生前一個(gè)排列62/912.sort的使用方法使用對(duì)象：像vector或者數(shù)組等具有隨機(jī)存取特性的容器。1）內(nèi)置數(shù)據(jù)類(lèi)型的排序如果vector中元素是內(nèi)置數(shù)據(jù)類(lèi)型的數(shù)據(jù)，sort()默認(rèn)是以less<T>（小于關(guān)系仿函數(shù)）作為比較函數(shù)實(shí)現(xiàn)遞增排序的。為了實(shí)現(xiàn)遞減排序，需要改為greater<T>（大于關(guān)系仿函數(shù)）。63/91【例2-2】假設(shè)一個(gè)含n個(gè)整數(shù)的序列采用向量容器v存放，設(shè)計(jì)一個(gè)算法求第k（1≤k≤n）大的整數(shù)（不是第k個(gè)不同的整數(shù)）。解法1：將v中整數(shù)元素遞增排序，那么排序后的v[n-k]就是原來(lái)v中第k大的整數(shù)。inttopk1(vector<int>&v,intk) //解法1的算法{sort(v.begin(),v.end()); //將v中所有元素遞增排序returnv[v.size()-k];}64/91解法2：將v中整數(shù)元素遞減排序，那么排序后的v[k-1]就是原來(lái)v中第k大的整數(shù)。inttopk2(vector<int>&v,intk) //解法2的算法{sort(v.begin(),v.end(),greater<int>()); //將v中所有元素遞減排序returnv[k-1];}65/912）自定義數(shù)據(jù)類(lèi)型的排序在聲明結(jié)構(gòu)體類(lèi)型中重載<運(yùn)算符，以實(shí)現(xiàn)按指定成員的遞增或者遞減排序。如sort(v.begin(),v.end())調(diào)用默認(rèn)<運(yùn)算符對(duì)v容器的所有元素實(shí)現(xiàn)排序。自己定義包含關(guān)系比較函數(shù)()的結(jié)構(gòu)體Cmp，在關(guān)系比較函數(shù)()中實(shí)現(xiàn)按指定成員的遞增或者遞減排序。如sort(v.begin(),v.end(),Cmp())調(diào)用Cmp的()運(yùn)算符對(duì)v容器的所有元素實(shí)現(xiàn)排序。自己定義關(guān)系比較函數(shù)myfun，關(guān)系比較函數(shù)myfun中實(shí)現(xiàn)按指定成員的遞增或者遞減排序。如sort(v.begin(),v.end(),myfun)調(diào)用myfun函數(shù)對(duì)v容器的所有元素實(shí)現(xiàn)排序。66/91【例2-3】假設(shè)一個(gè)非空向量容器v中存放若干學(xué)生信息，每個(gè)學(xué)生包含學(xué)號(hào)、姓名、分?jǐn)?shù)和名次，初始時(shí)名次為空。

設(shè)計(jì)一個(gè)算法求出每個(gè)學(xué)生的名次（名次從1開(kāi)始，相同分?jǐn)?shù)的名次相同。67/91解structStud

//學(xué)生元素類(lèi)型{ intno; //學(xué)號(hào) stringname; //姓名 intscore; //分?jǐn)?shù) intrank; //名次 Stud(intno1,stringname1,intscore1) //構(gòu)造函數(shù) { no=no1; name=name1; score=score1; rank=0; }

booloperator<(constStud&s)const

//方式①：重載<運(yùn)算符 { returnscore>s.score; //用于按score遞減排序 }};68/91structCmp //方式②：Cmp中重載()運(yùn)算符{ booloperator()(Stud&s,Stud&t)

{ returns.score>t.score; //用于按score遞減排序 }};boolmyfun(Stud&s,Stud&t)

//方式③：自己定義比較函數(shù)myfun{ returns.score>t.score; //用于按score遞減排序}69/91voidgetrank(vector<Stud>&v) //求所有學(xué)生的名次{ sort(v.begin(),v.end()); //方式①：將v中元素按分?jǐn)?shù)遞減排序

//sort(v.begin(),v.end(),Cmp()); //方式②：將v中元素按分?jǐn)?shù)遞減排序 //sort(v.begin(),v.end(),myfun); //方式③：將v中元素按分?jǐn)?shù)遞減排序 v[0].rank=1; for(inti=1;i<v.size();i++) //求名次 { if(v[i].score==v[i-1].score) v[i].rank=v[i-1].rank; else v[i].rank=i+1; }}70/912.1.4list鏈表容器a0a1…an-1表頭表尾71/911.list的特點(diǎn)ls容器采用帶頭結(jié)點(diǎn)的循環(huán)雙鏈表實(shí)現(xiàn)。ls容器可以在任何地方快速插入與刪除，對(duì)應(yīng)的時(shí)間復(fù)雜度均為O(1)。ls容器中每個(gè)結(jié)點(diǎn)單獨(dú)分配空間，不存在空間不夠的情況。ls容器不具有隨機(jī)存取特性，查找序號(hào)為i（0≤i≤n-1）的元素值的時(shí)間復(fù)雜度為O(n)。72/912.定義list容器list<int>l1; //定義元素為int的鏈表l1list<int>l2(10); //指定鏈表l2的初始大小為10個(gè)int元素list<double>l3(10，1.23); //指定l3的10個(gè)初始元素的初值為1.23list<int>l4(a，a+5); //用數(shù)組a[0..4]共5個(gè)元素初始化l473/913.list的成員函數(shù)類(lèi)型成員函數(shù)功能說(shuō)明容量empty()判斷鏈表容器是否為空size()返回鏈表容器的長(zhǎng)度訪問(wèn)元素back()返回鏈表容器的末尾元素front()返回鏈表容器的首元素更新push_back(e)在鏈表尾部插入元素eemplace_back(e)同push_back(e)，采用原地構(gòu)造對(duì)象再添加push_front(e)在鏈表首部插入元素eemplace_front(e)同push_front(e)，采用原地構(gòu)造對(duì)象再添加insert(pos,e)在pos位置插入元素einsert(pos,n,e)在pos位置插入n個(gè)元素einsert(pos,pos1,pos2)在迭代器pos處插入[pos1,pos2)的元素pop_back()刪除鏈表容器的末尾元素pop_front()刪除鏈表容器的首元素。erase()從鏈表容器中刪除一個(gè)或幾個(gè)元素clear()刪除鏈表容器中所有的元素74/91類(lèi)型成員函數(shù)功能說(shuō)明操作remove()刪除鏈表容器中所有指定值的元素remove_if(cmp)刪除鏈表容器中滿足條件的元素unique()刪除鏈表容器中相鄰的重復(fù)元素merge()合并兩個(gè)有序鏈表容器中的元素reverse()反轉(zhuǎn)當(dāng)前鏈表容器的所有元素sort()對(duì)鏈表容器中的元素排序迭代器begin()返回當(dāng)前鏈表容器中首元素的迭代器end()返回當(dāng)前鏈表容器中末尾元素的后一個(gè)元素的迭代器rbegin()返回當(dāng)前鏈表容器中末尾元素的迭代器rend()返回當(dāng)前鏈表容器中首元素的前一個(gè)元素的迭代器STL提供的sort()排序算法僅支持具有隨機(jī)存取特性的容器，而list容器不支持隨機(jī)訪問(wèn)，為此，list鏈表容器提供了sort()成員函數(shù)用于元素排序，類(lèi)似的還有unique()、reverse()、merge()等成員函數(shù)。說(shuō)明75/912.2字符串2.2.1字符串的定義字符串簡(jiǎn)稱(chēng)為串，是字符的有限序列，可以看成元素類(lèi)型是字符的線性表。一個(gè)串s中若干連續(xù)的字符構(gòu)成的串t稱(chēng)為s的子串?？沾侨魏未淖哟蓚€(gè)串相等當(dāng)且僅當(dāng)它們的長(zhǎng)度相同并且對(duì)應(yīng)位置的字符均相同。76/911.順序串structSqString

//順序串類(lèi)型{ chardata[MaxSize]; //MaxSize為data數(shù)組的容量 intlength; //順序串長(zhǎng)度即實(shí)際元素個(gè)數(shù) SqList():length(0){} //構(gòu)造函數(shù)};77/912.鏈串struct

SNode

//鏈串的結(jié)點(diǎn)類(lèi)型{ char

val; //結(jié)點(diǎn)值 ListNode

*next; //后繼結(jié)點(diǎn)的地址 ListNode()

:

val(0),

next(NULL)

{} //默認(rèn)構(gòu)造函數(shù) ListNode(char

x)

:

val(x),

next(NULL)

{} //重載構(gòu)造函數(shù)1 ListNode(char

x,

SNode

*next):val(x),

next(next)

{} //重載構(gòu)造函數(shù)2};78/912.2.2string字符串容器1.定義string容器string()：建立一個(gè)空的字符串。string(conststring&str)：用字符串str建立當(dāng)前字符串。string(conststring&str,size_typeidx)：用字符串str起始于idx的字符建立當(dāng)前字符串。string(conststring&str,size_typeidx,size_typenum)：用字符串str起始于idx的num個(gè)字符建立當(dāng)前字符串。string(constchar*cstr)：用C-字符串cstr建立當(dāng)前字符串。string(constchar*chars,size_typenum)：用C-字符串cstr開(kāi)頭的num個(gè)字符建立當(dāng)前字符串。string(size_typenum,charc)：用num個(gè)字符c建立當(dāng)前字符串。79/912.string的成員函數(shù)類(lèi)型成員函數(shù)功能說(shuō)明容量empty()判斷當(dāng)前字符串是否為空串size()返回當(dāng)前字符串的長(zhǎng)度length()與size()相同訪問(wèn)元素back()返回當(dāng)前字符串容器的末尾元素front()返回當(dāng)前字符串容器的首元素[idx]返回當(dāng)前字符串位于idx位置的字符，idx從0開(kāi)始at(idx)返回當(dāng)前字符串位于idx位置的字符80/91類(lèi)型成員函數(shù)功能說(shuō)明更新append(str)在當(dāng)前字符串的末尾添加一個(gè)字符串strpush_back(c)在當(dāng)前字符串的末尾添加一個(gè)字符cinsert(size_typeidx,conststring&str)在當(dāng)前字符串的idx序號(hào)處插入一個(gè)字符串strreplace(size_typeidx,size_typenum,conststring&str)將當(dāng)前字符串中起始于idx的num個(gè)字符用一個(gè)字符串str替換replace(iteratorbeg,iteratorend,conststring&str)將[beg,end)區(qū)間的所有字符用字符串str替換pop_back()刪除當(dāng)前字符串的末尾字符erase()刪除當(dāng)前字符串中的所有的字符erase(size_typeidx)刪除當(dāng)前字符串的從idx開(kāi)始的所有字符erase(size_typeidx,size_typenum)刪除當(dāng)前字符串的從idx開(kāi)始的num個(gè)字符clear()刪除當(dāng)前字符串中的所有的字符81/91類(lèi)型成員函數(shù)功能說(shuō)明字符串操作find(string&s,size_typepos=0)在當(dāng)前字符串中從pos位置（默認(rèn)為0）開(kāi)始向后查找字符串s的第一個(gè)位置rfind(string&s,size_typepos=npos)在當(dāng)前字符串中從pos位置（默認(rèn)為npos）開(kāi)始向前查找字符串s的第一個(gè)位置substr(size_typeidx)返回當(dāng)前字符串起始于idx的子串substr(size_typeidx,size_typenum)返回當(dāng)前字符串起始于idx的長(zhǎng)度為num的子串compare(conststring&str)返回當(dāng)前字符串與字符串str的比較結(jié)果。在比較時(shí)，若兩者相等則返回0，前者小于后者則返回-1，否則返回1迭代器begin()返回當(dāng)前字符串容器中首元素的迭代器end()返回當(dāng)前字符串容器中末尾元素的后一個(gè)元素的迭代器rbegin()返回當(dāng)前字符串容器中末尾元素的迭代器rend()返回當(dāng)前字符串容器中首元素的前一個(gè)元素的迭代器82/913.string的應(yīng)用【例2-4】假設(shè)兩個(gè)字符串s和t均采用string容器存儲(chǔ)。設(shè)計(jì)一個(gè)算法利用string的成員函數(shù)求t在s中不重疊出現(xiàn)的次數(shù)。例如s="aaaaa"，t="aa"，結(jié)果為2。intCount(string&s,string&t){ intcnt=0; intpos=s.find(t,0); while(pos!=string::npos) //在s中找到t { cnt++; pos=s.find(t,pos+1); //繼續(xù)在后續(xù)字符中查找 } returncnt;}解83/91【例2-5】假設(shè)有3個(gè)字符串str、s和t，均采用string容器存儲(chǔ)。設(shè)計(jì)一個(gè)算法利用string的成員函數(shù)將str中所有的子串s用t串替換。例如str="ababcd"，s="ab"，t="123"，替換后str變?yōu)?123123cd"。voidReplaceall(string&str,string&s,string&t){ intm=s.size(); intpos=str.find(s,0); while(pos!=string::npos) //在str中找到s { str.replace(pos,m,t); //替換 pos=str.find(s,pos+1); //繼續(xù)在后續(xù)字符中查找 }}解84/912.3棧、隊(duì)列和雙端隊(duì)列2.3.1棧、隊(duì)列和雙端隊(duì)列的定義棧是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，規(guī)定只能在其中一端進(jìn)行進(jìn)棧和出棧操作。隊(duì)列是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，規(guī)定只能在一端進(jìn)隊(duì)元素，另外一端出隊(duì)元素。雙端隊(duì)列是一種特殊的線性表，有前、后兩個(gè)端點(diǎn)，每個(gè)端點(diǎn)都可以進(jìn)隊(duì)和出隊(duì)元素。85/912.3.2deque雙端隊(duì)列容器前端后端前端進(jìn)前端出后端進(jìn)后端出86/91dq容器在實(shí)現(xiàn)上由若干個(gè)塊構(gòu)成，每個(gè)塊中元素地址是連續(xù)的，塊之間的地址是不連續(xù)的，系統(tǒng)有一個(gè)特定的機(jī)制將這些塊構(gòu)成一個(gè)整體并且維護(hù)相關(guān)操作。由于dq容器采用分塊存放容器中的元素，所以空間的重新分配要比vector快，因?yàn)橹匦路峙淇臻g后，原有的元素不需要復(fù)制。dq容器提供了隨機(jī)訪問(wèn)迭代器，但隨機(jī)訪問(wèn)的時(shí)間不再是O(1)，也遠(yuǎn)好于O(n)。dq容器在前后端進(jìn)隊(duì)和出隊(duì)除元素的時(shí)間復(fù)雜度均為O(1)，但在中間位置插入和刪除元素速度較慢。dq容器不同于隊(duì)列，它提供了遍歷元素的迭代器成員函數(shù)，可以正向或者反向遍歷其中的全部元素。1.deque的特點(diǎn)87/912.定義deque容器deque<int>dq1; //定義元素類(lèi)型為int的空雙端隊(duì)列dq1deque<int>dq2(10); //指定dq2初始為10個(gè)int元素deque<double>dq3(10,1.23); //指定dq3的10個(gè)初始元素均為1.23deque<int>dq4(dq2.begin(),dq2.end()); //用dq2的所有元素初始化dq488/913.deque的成員函數(shù)類(lèi)型成員函數(shù)功能說(shuō)明容量empty()判斷雙端隊(duì)列容器是否為空隊(duì)size()返回雙端隊(duì)列的長(zhǎng)度訪問(wèn)元素back()返回當(dāng)前雙端隊(duì)列容器的末尾元素front()返回當(dāng)前雙端隊(duì)列容器的首元素[idx]返回指定下標(biāo)idx的元素at[idx]同[idx]89/91類(lèi)型成員函數(shù)功能說(shuō)明容量empty()判斷雙端隊(duì)列容器是否為空隊(duì)更新push_front(e)在隊(duì)頭插入元素epush_back(e)在隊(duì)尾插入元素epop_front()出隊(duì)一個(gè)隊(duì)頭元素pop_back()出隊(duì)一個(gè)隊(duì)尾元素insert()在雙端隊(duì)列容器中插入一個(gè)或幾個(gè)元素erase()從雙端隊(duì)列容器中刪除一個(gè)或幾個(gè)元素clear()出隊(duì)雙端隊(duì)列容器中所有元素迭代器begin()返回當(dāng)前雙端隊(duì)列容器中首元素的迭代器end()返回當(dāng)前雙端隊(duì)列容器中末尾元素的后一個(gè)元素的迭代器rbegin()返回當(dāng)前雙端隊(duì)列容器中末尾元素的迭代器rend()返回當(dāng)前雙端隊(duì)列容器中首元素的前一個(gè)元素的迭代器前端front后端backpush_frontpop_frontpush_backpop_back90/91deque容器在出隊(duì)元素函數(shù)（pop_front、pop_back）中并不檢測(cè)隊(duì)空，所以在調(diào)用這些函數(shù)時(shí)務(wù)必保證容器是非空的，否則會(huì)導(dǎo)致程序停止正常工作。說(shuō)明前端front后端backpush_frontpop_frontpush_backpop_back91/914.deque的應(yīng)用【例2-6】給定一個(gè)含n個(gè)整數(shù)的序列

nums

和滑動(dòng)窗口的大小

k（1≤k≤n），設(shè)計(jì)一個(gè)算法求出所有滑動(dòng)窗口里的最大值。例如，nums=（4，3，5，4，3，3，6，7），k=3。nums:[4，3，5]，4，3，3，6，7

5nums:4，[3，5，4]，3，3，6，7

5nums:4，3，[5，4，3]，3，6，7

5nums:4，3，5，[4，3，3]，6，7

4nums:4，3，5，4，[3，3，6]，7

6nums:4，3，5，4，3，[3，6，7]

7結(jié)果是（5，5，5，4，6，7）92/91解vector<int>maxSlidingWindow(vector<int>&nums,intk){ intn=nums.size(); deque<int>dq; vector<int>ans; for(inti=0;i<k;i++) //處理nums前k個(gè)元素 { if(dq.empty()) //隊(duì)空時(shí)將元素下標(biāo)i進(jìn)隊(duì)尾 dq.push_back(i); else //隊(duì)不空時(shí) { while(!dq.empty()&&nums[i]>nums[dq.back()]) dq.pop_back(); //將隊(duì)尾小于nums[i]的元素從隊(duì)尾出隊(duì) dq.push_back(i); //將元素下標(biāo)i進(jìn)隊(duì)尾 }}93/91 ans.push_back(nums[dq.front()]); //隊(duì)頭元素添加到ans中 for(inti=k;i<n;i++) //處理nums中剩余的元素 { if(dq.empty()) //隊(duì)空時(shí)將元素下標(biāo)i進(jìn)隊(duì)尾 dq.push_back(i); else //隊(duì)不空時(shí) { while(!dq.empty()&&nums[i]>nums[dq.back()]) dq.pop_back(); //將隊(duì)尾小于nums[i]的元素從隊(duì)尾出隊(duì) dq.push_back(i); //將元素下標(biāo)i進(jìn)隊(duì)尾 } if(dq.front()<i-k+1) //將隊(duì)頭過(guò)期的元素從隊(duì)頭出隊(duì) dq.pop_front(); ans.push_back(nums[dq.front()]); //新隊(duì)頭元素添加到ans中 } returnans;}94/912.3.3queue隊(duì)列容器1.queue的特點(diǎn)qu容器只能在隊(duì)頭出隊(duì)（刪除）、在隊(duì)尾進(jìn)隊(duì)（插入）元素，不能在中間位置刪除和插入元素，因此隊(duì)中元素先進(jìn)先出。qu容器具有自動(dòng)擴(kuò)容功能，不必考慮隊(duì)滿的情況。qu容器中的元素不允許順序遍歷，不支持begin()/end()和rbegin()/rend()迭代器函數(shù)。95/912.定義queue容器queue<int>qu1; //定義int類(lèi)型的空隊(duì)列qu1（底層容器是deque）list<int>ls(3,2);

//定義含3個(gè)元素值均為2的ls容器queue<int,list<int>>qu2(ls);

//由ls創(chuàng)建隊(duì)列qu296/913.queue的成員函數(shù)成員函數(shù)功能說(shuō)明empty()判斷隊(duì)列容器是否為空size()返回隊(duì)列容器的長(zhǎng)度f(wàn)ront()返回隊(duì)頭元素back()返回隊(duì)尾元素push(e)進(jìn)隊(duì)元素epop()出隊(duì)一個(gè)元素queue容器在出隊(duì)元素函數(shù)（pop）中并不檢測(cè)隊(duì)空，所以在調(diào)用該函數(shù)時(shí)務(wù)必保證容器是非空的，否則會(huì)導(dǎo)致程序停止正常工作。說(shuō)明97/914.queue的應(yīng)用【例2-7】給定一個(gè)含n（n>1）個(gè)整數(shù)的隊(duì)列容器qu，設(shè)計(jì)一個(gè)算法出隊(duì)其中序號(hào)為k（1≤k≤n）的元素（從隊(duì)頭開(kāi)始數(shù)，隊(duì)頭元素的序號(hào)為1），并返回該元素。98/91intpopk(queue<int>&qu,intk){intn=qu.size(),x;for(inti=1;i<k;i++) //處理序號(hào)1到k-1的元素{x=qu.front();qu.pop(); //出隊(duì)元素xqu.push(x); //將x進(jìn)隊(duì)}inte=qu.front();qu.pop(); //出隊(duì)序號(hào)為k的元素efor(inti=k+1;i<=n;i++) //處理序號(hào)k+1到n的元素{x=qu.front();qu.pop(); //出隊(duì)元素x

qu.push(x); //將x進(jìn)隊(duì)}returne; }解前端后端99/912.3.4stack棧容器1.stack的特點(diǎn)st容器只能在棧頂出棧（刪除）和進(jìn)棧（插入）元素，不能在中間位置刪除和插入元素，因此棧中元素后進(jìn)先出。st容器具有自動(dòng)擴(kuò)容功能，不必考慮棧滿的情況。st容器中的元素不允許順序遍歷，不支持begin()/end()和rbegin()/rend()迭代器函數(shù)。100/912.定義stack容器stack<int>st1; //定義int類(lèi)型的空棧st1（底層容器是deque）vector<int>v(2,10);

//定義含2個(gè)元素值均為10的v容器stack<int,vector<int>>st2(v);

//由v容器創(chuàng)建st2101/913.stack的成員函數(shù)成員函數(shù)功能說(shuō)明empty()判斷棧容器是否為空size()返回棧容器的長(zhǎng)度push(e)進(jìn)棧元素etop()返回棧頂元素pop()元素一個(gè)出棧stack容器在出棧元素函數(shù)（pop）中并不檢測(cè)?？眨栽谡{(diào)用該函數(shù)時(shí)務(wù)必保證容器是非空的，否則會(huì)導(dǎo)致程序停止正常工作。說(shuō)明102/91【例2-8】給定一個(gè)含若干單詞的字符串s，單詞之間用一個(gè)或者多個(gè)空格分隔。設(shè)計(jì)一個(gè)算法將s中所有單詞翻轉(zhuǎn)并且返回翻轉(zhuǎn)后的結(jié)果，結(jié)果字符串中兩個(gè)單詞之間只有一個(gè)空格。

例如s="theskyis

blue"翻轉(zhuǎn)的結(jié)果t="blue

isskythe"。103/91stringReversewords(string&s){ stack<string>st; inti=0; while(i<s.length()) //遍歷字符串s { while(i<s.length()&&s[i]=='')i++; //跳過(guò)空字符 stringtmp=""; while(i<s.length()&&s[i]!='') //提取單詞tmp {tmp+=s[i];i++;} st.push(tmp); //將tmp進(jìn)棧 } stringans=""; while(!st.empty()) //出棧所有單詞連接成字符串a(chǎn)ns { if(ans.length()==0) ans+=st.top(); else ans+=""+st.top(); st.pop(); } returnans;}解104/912.4二叉樹(shù)和優(yōu)先隊(duì)列2.4.1二叉樹(shù)1.二叉樹(shù)的定義二叉樹(shù)是有限的結(jié)點(diǎn)集合。這個(gè)集合或者是空，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。214356105/91在一棵二叉樹(shù)中如果所有分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都集中在二叉樹(shù)的最下一層，這樣的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。在一棵二叉樹(shù)中如果最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于2，并且最下面一層的葉子結(jié)點(diǎn)都依次排列在該層最左邊的位置上，則這樣的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。012543601243106/91滿二叉樹(shù)/完全二叉樹(shù)層序編號(hào)：(i-1)/2i2i+12i+201243107/9121435(a)一棵二叉樹(shù)53421403521(b)補(bǔ)齊為完全二叉樹(shù)021124334NIL55(c)二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)2.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1）二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)108/912）二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)root21∧3∧∧4∧5∧∧21435109/91整數(shù)二叉鏈結(jié)點(diǎn)類(lèi)型TreeNodestruct

TreeNode

//二叉鏈結(jié)點(diǎn)類(lèi)型{ int

val; //結(jié)點(diǎn)值 TreeNode

*left; //左孩子結(jié)點(diǎn)地址 TreeNode

*right; //右孩子結(jié)點(diǎn)地址 TreeNode()

:

val(0),

left(nullptr),

right(nullptr)

{} TreeNode(int

x)

:

val(x),

left(nullptr),

right(nullptr)

{} TreeNode(int

x,

TreeNode

*left,

TreeNode

*right)

: