算法設(shè)計與分析（課件）第1章概述1.1算法的概念1.2算法分析1.3算法設(shè)計工具―STL

算法是求解問題的一系列計算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果：算法輸入輸出如果一個算法對其每一個輸入實例，都能輸出正確的結(jié)果并停止，則稱它是正確的。1.1.1什么是算法1.1算法的概念算法設(shè)計應(yīng)滿足以下幾條目標(biāo)：正確性可使用性可讀性健壯性高效率與低存儲量需求

【例1.1】以下算法用于在帶頭結(jié)點的單鏈表h中查找第一個值為x的結(jié)點，找到后返回其邏輯序號（從1計起），否則返回0。分析該算法存在的問題。intfindx(LNode*h，intx){LNode*p=h->next;

inti=0;

while(p->data!=x)

{ i++; p=p->next;

}

returni;}解：問題：intfindx(LNode*h,intx){LNode*p=h->next;

inti=1;

while(p!=NULL&&p->data!=x)

{ i++; p=p->next;

}

if(p==NULL) return0;

else returni;}當(dāng)單鏈表中首結(jié)點值為x時，該算法返回0，此時應(yīng)該返回邏輯序號1。當(dāng)單鏈表中不存在值為x的結(jié)點時，該算法執(zhí)行出錯，因為p為NULL時仍執(zhí)行p=p->next。所以該算法不滿足正確性和健壯性。應(yīng)改為：intfindx(LNode*h,intx){LNode*p=h->next;

inti=0;

while(p->data!=x)

{ i++; p=p->next;

}

returni;}算法具有以下5個重要特征：有限性確定性可行性輸入性輸出性【例1.2】有下列兩段描述：描述1： 描述2：voidexam1(){intn;

n=2;

while(n%2==0)

n=n+2;

printf("%d\n",n);}voidexam2(){intx,y;

y=0;

x=5/y;

printf("%d,%d\n",x,y);}這兩段描述均不能滿足算法的特征，試問它們違反了算法的哪些特征？解：（1）是一個死循環(huán)，違反了算法的有限性特征。（2）出現(xiàn)除零錯誤，違反了算法的可行性特征。voidexam1(){intn;

n=2;

while(n%2==0)

n=n+2;

printf("%d\n",n);}voidexam2(){intx,y;

y=0;

x=5/y;

printf("%d,%d\n",x,y);}1.1.2算法描述以設(shè)計求1+2+…+n值的算法為例說明C/C++語言描述算法的一般形式，該算法如下：boolfun(intn,ints){if(n<0)returnfalse;s=0;for(inti=1;i<=n;i++)s+=i;returntrue;}形參列表返回值

通常用函數(shù)的返回值表示算法能否正確執(zhí)行。有時當(dāng)算法只有一個返回值或者返回值可以區(qū)分算法是否正確執(zhí)行時，用函數(shù)返回來表示算法的執(zhí)行結(jié)果，另外還可以帶有形參表示算法的輸入輸出。

在C語言中調(diào)用函數(shù)時只有從實參到形參的單向值傳遞，執(zhí)行函數(shù)時若改變了形參而對應(yīng)的實參不會同步改變。例如，設(shè)計以下主函數(shù)調(diào)用上面的fun函數(shù)：voidmain(){inta=10,b=0;

if(fun(a,b))printf("%d\n",b);

elseprintf("參數(shù)錯誤\n");}執(zhí)行時發(fā)現(xiàn)輸出結(jié)果為0，因為b對應(yīng)的形參為s，fun執(zhí)行后s=55，但s并沒有回傳給b。在C語言中可以用傳指針方式來實現(xiàn)形參的回傳，但增加了函數(shù)的復(fù)雜性。

為此C++語言中增加了引用型參數(shù)的概念，引用型參數(shù)名前需加上&，表示這樣的形參在執(zhí)行后會將結(jié)果回傳給對應(yīng)的實參。上例采用C++語言描述算法如下所示。當(dāng)將形參s改為引用類型的參數(shù)后，執(zhí)行時main函數(shù)的輸出結(jié)果就正確了即輸出55。boolfun(intn,int&s){if(n<0)returnfalse;s=0;for(inti=1;i<=n;i++)s+=i;returntrue;}引用參數(shù)

結(jié)論：在設(shè)計算法時，如果某個形參需要將執(zhí)行結(jié)果回傳給實參，需要將該形參設(shè)計為引用型參數(shù)。1.1.3算法和數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)既有聯(lián)系又有區(qū)別。聯(lián)系：數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計的基礎(chǔ)。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)，在設(shè)計算法時，通常要構(gòu)建適合這種算法的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)設(shè)計主要是選擇數(shù)據(jù)的存儲方式，如確定求解問題中的數(shù)據(jù)采用數(shù)組存儲還是采用鏈表存儲等。算法設(shè)計就是在選定的存儲結(jié)構(gòu)上設(shè)計一個滿足要求的好算法。區(qū)別：數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上解決實際問題。算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是這些思想的邏輯基礎(chǔ)。1.1.4算法設(shè)計的基本步驟分析求解問題選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略描述算法證明算法正確性算法分析

算法分析是分析算法占用計算機資源的情況。所以算法分析的兩個主要方面是分析算法的時間復(fù)雜度和空間復(fù)雜度。1.2算法分析1.2.1算法時間復(fù)雜度分析1.時間復(fù)雜度分析概述一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，算法的運行時間取決于兩者的綜合效果。boolSolve(doublea[][MAX],intm,intn,double&s){inti;s=0;if(m!=n)returnfalse;for(i=0;i<m;i++)s+=a[i][i];returntrue;}順序結(jié)構(gòu)分支結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)設(shè)n為算法中的問題規(guī)模，通常用大O、大

和

等三種漸進符號表示算法的執(zhí)行時間與n之間的一種增長關(guān)系。分析算法時間復(fù)雜度的一般步驟：算法分析問題規(guī)模n，找出基本語句，求出其運行次數(shù)f(n)用O、或

表示其階2.漸進符號（O、

和

）

定義1（大O符號），f(n)=O(g(n))（讀作“f(n)是g(n)的大O”）當(dāng)且僅當(dāng)存在正常量c和n0，使當(dāng)n≥n0時，f(n)≤cg(n)，即g(n)為f(n)的上界。如3n+2=O(n)，因為當(dāng)n≥2時，3n+2≤4n。

10n2+4n+2=O(n4)，因為當(dāng)n≥2時，10n2+4n+2≤10n4。

大O符號用來描述增長率的上界，表示f(n)的增長最多像g(n)增長的那樣快，也就是說，當(dāng)輸入規(guī)模為n時，算法消耗時間的最大值。這個上界的階越低，結(jié)果就越有價值，所以，對于10n2+4n+2，O(n2)比O(n4)有價值。

一個算法的時間用大O符號表示時，總是采用最有價值的g(n)表示，稱之為“緊湊上界”或“緊確上界”。

一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0，有f(n)=O(nm)。

定義2（大

符號），f(n)=

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

”）當(dāng)且僅當(dāng)存在正常量c和n0，使當(dāng)n≥n0時，f(n)≥cg(n)，即g(n)為f(n)的下界。如3n+2=

(n)，因為當(dāng)n≥1時，3n+2≥3n。

10n2+4n+2=

(n2)，因為當(dāng)n≥1時，10n2+4n+2≥n2。

大

符號用來描述增長率的下界，表示f(n)的增長最少像g(n)增長的那樣快，也就是說，當(dāng)輸入規(guī)模為n時，算法消耗時間的最小值。

與大O符號對稱，這個下界的階越高，結(jié)果就越有價值，所以，對于10n2+4n+2，

(n2)比

(n)有價值。一個算法的時間用大

符號表示時，總是采用最有價值的g(n)表示，稱之為“緊湊下界”或“緊確下界”。

一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0，有f(n)=

(nm)。

定義3（大

符號），f(n)=

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

”）當(dāng)且僅當(dāng)存在正常量c1、c2和n0，使當(dāng)n≥n0時，有c1g(n)≤f(n)≤c2g(n)，即g(n)與f(n)的同階。

如3n+2=

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

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

(nm)。

大

符號比大O符號和大

符號都精確，f(n)=

(g(n)，當(dāng)且僅當(dāng)g(n)既是f(n)的上界又是f(n)的下界。【例1.3】分析以下算法的時間復(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++，所以有：則該算法的時間復(fù)雜度為O(n3)。3.算法的最好、最壞和平均情況

定義4

設(shè)一個算法的輸入規(guī)模為n，Dn是所有輸入的集合，任一輸入I∈Dn，P(I)是I出現(xiàn)的概率，有=1，T(I)是算法在輸入I下所執(zhí)行的基本語句次數(shù)，則該算法的平均執(zhí)行時間為：A(n)=。

也就是說算法的平均情況是指用各種特定輸入下的基本語句執(zhí)行次數(shù)的帶權(quán)平均值。

算法的最好情況為：G(n)=，是指算法在所有輸入I下所執(zhí)行基本語句的最少次數(shù)。

算法的最壞情況為：W(n)=，是指算法在所有輸入I下所執(zhí)行基本語句的最大次數(shù)。

【例1.4】采用順序查找方法，在長度為n的一維實型數(shù)組a[0..n-1]中查找值為x的元素。即從數(shù)組的第一個元素開始，逐個與被查值x進行比較。找到后返回1，否則返回0，對應(yīng)的算法如下：intFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)return1;elsereturn0;}回答以下問題：（1）分析該算法在等概率情況下成功查找到值為x的元素的最好、最壞和平均時間復(fù)雜度。（2）假設(shè)被查值x在數(shù)組a中的概率是q，求算法的時間復(fù)雜度。

解：（1）算法的while循環(huán)中的if語句是基本語句。a數(shù)組中有n個元素，當(dāng)?shù)谝粋€元素a[0]等于x，此時基本語句僅執(zhí)行一次，此時呈現(xiàn)最好的情況，即G(n)=O(1)。當(dāng)a中最后一個元素a[n-1]等于x，此時基本語句執(zhí)行n次，此時呈現(xiàn)最壞的情況，即W(n)=O(n)。intFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)return1;elsereturn0;}對于其他情況，假設(shè)查找每個元素的概率相同，則P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素時基本語句正好執(zhí)行i+1次，所以：A(n)=

=O(n)。intFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)return1;elsereturn0;}

（2）當(dāng)被查值x在數(shù)組a中的概率為q時，算法執(zhí)行有n+1種情況，即n種成功查找和一種不成功查找。對于成功查找，假設(shè)是等概率情況，則元素a[i]被查找到的概率P(a[i])=q/n，成功找到a[i]元素時基本語句正好執(zhí)行i+1次。對于不成功查找，其概率為1-q，不成功查找時基本語句正好執(zhí)行n次。所以：A(n)=

=

如果已知需要查找的x有一半的機會在數(shù)組中，此時q=1/2，則A(n)=[(n+1)/4]+n/2≈3n/4。4.非遞歸算法的時間復(fù)雜度分析對于非遞歸算法，分析其時間復(fù)雜度相對比較簡單，關(guān)鍵是求出代表算法執(zhí)行時間的表達式。通常是算法中基本語句的執(zhí)行次數(shù)，是一個關(guān)于問題規(guī)模n的表達式，然后用漸進符號來表示這個表達式即得到算法的時間復(fù)雜度。【例1.6】給出以下算法的時間復(fù)雜度。voidfunc(intn){inti=1,k=100;

while(i<=n)

{k++;

i+=2;

}}

解：算法中基本語句是while循環(huán)內(nèi)的語句。設(shè)while循環(huán)語句執(zhí)行的次數(shù)為m，i從1開始遞增，最后取值為1+2m，有：

i=1+2m≤n

f(n)=m≤(n-1)/2=O(n)。該算法的時間復(fù)雜度為O(n)。5.遞歸算法的時間復(fù)雜度分析遞歸算法是采用一種分而治之的方法，把一個“大問題”分解為若干個相似的“小問題”來求解。對遞歸算法時間復(fù)雜度的分析，關(guān)鍵是根據(jù)遞歸過程建立遞推關(guān)系式，然后求解這個遞推關(guān)系式，得到一個表示算法執(zhí)行時間的表達式，最后用漸進符號來表示這個表達式即得到算法的時間復(fù)雜度?！纠?.7】有以下遞歸算法：voidmergesort(inta[],inti,intj){intm;if(i!=j){

m=(i+j)/2;

mergesort(a,i,m);

mergesort(a,m+1,j);merge(a,i,j,m);}}

其中，mergesort()用于數(shù)組a[0..n-1]（設(shè)n=2k，這里的k為正整數(shù)）的歸并排序，調(diào)用該算法的方式為：

mergesort(a，0，n-1)；

另外merge(a，i，j，m)用于兩個有序子序列a[i..j]和a[j+1..m]的有序合并，是非遞歸函數(shù)，它的時間復(fù)雜度為O(n)（這里n=j-i+1）。分析上述調(diào)用的時間復(fù)雜度。

解：設(shè)調(diào)用mergesort(a，0，n-1)的執(zhí)行時間為T(n)，由其執(zhí)行過程得到以下求執(zhí)行時間的遞歸關(guān)系（遞推關(guān)系式）：T(n)=O(1) 當(dāng)n=1T(n)=2T(n/2)+O(n) 當(dāng)n>1其中，O(n)為merge()所需的時間，設(shè)為cn（c為正常量）。因此：T(n)=2T(n/2)+cn=2[2T(n/22)+cn/2]+cn=22T(n/22)+2cn=23T(n/23)+3cn=…=2kT(n/2k)+kcn=nO(1)+cnlog2n=n+cnlog2n //這里假設(shè)n=2k，則k=log2n=O(nlog2n)voidmergesort(inta[],inti,intj){intm;if(i!=j)

{m=(i+j)/2;

mergesort(a,i,m);

mergesort(a,m+1,j);merge(a,i,j,m);}}【例1.8】求解梵塔問題的遞歸算法如下，分析其時間復(fù)雜度。voidHanoi(intn,charx,chary,charz){if(n==1)

printf("將盤片%d從%c搬到%c\n",n,x,z);

else

{Hanoi(n-1,x,z,y);

printf("將盤片%d從%c搬到%c\n",n,x,z);

Hanoi(n-1,y,x,z);

}}voidHanoi(intn,charx,chary,charz){if(n==1)

printf("將盤片%d從%c搬到%c\n",n,x,z);

else

{Hanoi(n-1,x,z,y);

printf("將盤片%d從%c搬到%c\n",n,x,z);

Hanoi(n-1,y,x,z);

}}解：設(shè)調(diào)用Hanoi(n，x，y，z)的執(zhí)行時間為T(n)，由其執(zhí)行過程得到以下求執(zhí)行時間的遞歸關(guān)系（遞推關(guān)系式）：T(n)=O(1) 當(dāng)n=1T(n)=2T(n-1)+1 當(dāng)n>1T(n)=2[2T(n-2)+1]+1=22T(n-2)+1+21=23T(n-3)+1+21+22=…=2n-1T(1)+1+21+22+…+2n-2=2n-1=O(2n)1.2.2算法空間復(fù)雜度分析

一個算法的存儲量包括形參所占空間和臨時變量所占空間。在對算法進行存儲空間分析時，只考察臨時變量所占空間。

例如，有以下算法，其中臨時空間為變量i、maxi占用的空間。所以，空間復(fù)雜度是對一個算法在運行過程中臨時占用的存儲空間大小的量度，一般也作為問題規(guī)模n的函數(shù)，以數(shù)量級形式給出，記作：

S(n)=O(g(n))、

(g(n))或

(g(n))其中漸進符號的含義與時間復(fù)雜度中的含義相同。intmax(inta[]，intn){inti，maxi=0;

for(i=1;i<=n;i++)

if(a[i]>a[maxi]) maxi=i;returna[maxi];}函數(shù)體內(nèi)分配的變量空間為臨時空間，不計形參占用的空間，這里的僅計i、maxi變量的空間，其空間復(fù)雜度為O(1)。為什么算法占用的空間只考慮臨時空間，而不必考慮形參的空間呢？這是因為形參的空間會在調(diào)用該算法的算法中考慮，例如，以下maxfun算法調(diào)用max算法：voidmaxfun(){intb[]={1,2,3,4,5},n=5;

printf("Max=%d\n",max(b,n));}maxfun算法中為b數(shù)組分配了相應(yīng)的內(nèi)存空間，其空間復(fù)雜度為O(n)，如果在max算法中再考慮形參a的空間，這樣重復(fù)計算了占用的空間。intmax(inta[]，intn){inti，maxi=0;

for(i=1;i<=n;i++)

if(a[i]>a[maxi]) maxi=i;returna[maxi];}算法空間復(fù)雜度的分析方法與前面介紹的時間復(fù)雜度分析方法相似。【例1.9】分析例1.6算法的空間復(fù)雜度。

解：該算法是一個非遞歸算法，其中只臨時分配了i、k兩個變量的空間，它與問題規(guī)模n無關(guān)，所以其空間復(fù)雜度均為O(1)，即該算法為原時工作算法。voidfunc(intn){inti=1,k=100;

while(i<=n)

{ k++; i+=2;

}}

【例1.10】有如下遞歸算法，分析調(diào)用maxelem(a，0，n-1)的空間復(fù)雜度。intmaxelem(inta[],inti,intj){intmid=(i+j)/2,max1,max2;if(i<j){ max1=maxelem(a,i,mid); max2=maxelem(a,mid+1,j); return(max1>max2)?max1:max2;}elsereturna[i];}解：執(zhí)行該遞歸算法需要多次調(diào)用自身，每次調(diào)用只臨時分配3個整型變量的空間（O(1)）。

設(shè)調(diào)用maxelem(a，0，n-1)的空間為S(n)，有：S(n)=O(1) 當(dāng)n=1S(n)=2S(n/2)+O(1) 當(dāng)n>1則：S(n)=2S(n/2)+1=2[2S(n/22)+1]+1=22S(n/22)+1+21=23S(n/23)+1+21+22=…=2kS(n/2k)+1+21+22+…+2k-1（設(shè)n=2k，即k=log2n）=n*1+2k-1=2n-1=O(n)intmaxelem(inta[],inti,intj){intmid=(i+j)/2,max1,max2;if(i<j){ max1=maxelem(a,i,mid); max2=maxelem(a,mid+1,j); return(max1>max2)?max1:max2;}elsereturna[i];}1.3算法設(shè)計工具―STL

1.3.1STL概述STL主要由container（容器）、algorithm（算法）和iterator（迭代器）三大部分構(gòu)成，容器用于存放數(shù)據(jù)對象（元素），算法用于操作容器中的數(shù)據(jù)對象。算法對象1對象2…對象n迭代器容器1.什么是STL容器數(shù)據(jù)結(jié)構(gòu)說

明實現(xiàn)頭文件向量（vector）連續(xù)存儲元素。底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，支持快速隨機訪問<vector>字符串（string）字符串處理容器<string>雙端隊列（deque）連續(xù)存儲的指向不同元素的指針?biāo)M成的數(shù)組。底層數(shù)據(jù)結(jié)構(gòu)為一個中央控制器和多個緩沖區(qū)，支持首尾元素（中間不能）快速增刪，也支持隨機訪問<deque>鏈表（list）由結(jié)點組成的鏈表，每個結(jié)點包含著一個元素。底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，支持結(jié)點的快速增刪<list>

一個STL容器就是一種數(shù)據(jù)結(jié)構(gòu)，如鏈表、棧和隊列等，這些數(shù)據(jù)結(jié)構(gòu)在STL中都已經(jīng)實現(xiàn)好了，在算法設(shè)計中可以直接使用它們。數(shù)據(jù)結(jié)構(gòu)說

明實現(xiàn)頭文件棧（stack）后進先出的序列。底層一般用deque（默認(rèn)）或者list實現(xiàn)<stack>隊列（queue）先進先出的序列。底層一般用deque（默認(rèn)）或者list實現(xiàn)<queue>優(yōu)先隊列（priority_queue）元素的進出隊順序由某個謂詞或者關(guān)系函數(shù)決定的一種隊列。底層數(shù)據(jù)結(jié)構(gòu)一般為vector（默認(rèn)）或者deque<queue>集合（set）/多重集合（multiset）由結(jié)點組成的紅黑樹，每個結(jié)點都包含著一個元素，set中所有元素有序但不重復(fù)，multiset中所有關(guān)鍵字有序但不重復(fù)<set>映射（map）/多重映射（multimap）由（關(guān)鍵字，值）對組成的集合，底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，map中所有關(guān)鍵字有序但不重復(fù)，multimap中所有關(guān)鍵字有序但可以重復(fù)<map>為此，使用STL時必須將下面的語句插入到源代碼文件開頭：

usingnamespacestd;這樣直接把程序代碼定位到std命名空間中。2.什么是STL算法STL算法是用來操作容器中數(shù)據(jù)的模板函數(shù)，STL提供了大約100個實現(xiàn)算法的模版函數(shù)。例如，STL用sort()來對一個vector中的數(shù)據(jù)進行排序，用find()來搜索一個list中的對象。STL算法部分主要由頭文件<algorithm>、<numeric>和<functional>組成。例如，以下程序使用STL算法sort()實現(xiàn)整型數(shù)組a的遞增排序：#include<algorithm>usingnamespacestd;voidmain(){inta[]={2,5,4,1,3};sort(a,a+5);for(inti=0;i<5;i++) printf("%d",a[i]); //輸出:12345printf("\n");}3.什么是STL迭代器STL迭代器用于訪問容器中的數(shù)據(jù)對象。

每個容器都有自己的迭代器，只有容器自己才知道如何訪問自己的元素。

迭代器像C/C++中的指針，算法通過迭代器來定位和操作容器中的元素。常用的迭代器有：iterator：指向容器中存放元素的迭代器，用于正向遍歷容器中的元素。const_iterator：指向容器中存放元素的常量迭代器，只能讀取容器中的元素。reverse_iterator：指向容器中存放元素的反向迭代器，用于反向遍歷容器中的元素。const_reverse_iterator：指向容器中存放元素的常量反向迭代器，只能讀取容器中的元素。迭代器的常用運算如下：++：正向移動迭代器。--：反向移動迭代器。*：返回迭代器所指的元素值。vector<int>myv;myv.push_back(1);myv.push_back(2);myv.push_back(3);vector<int>::iteratorit; //定義正向迭代器itfor(it=myv.begin();it!=myv.end();++it)

//從頭到尾遍歷所有元素 printf("%d",*it); //輸出：123printf("\n");vector<int>::reverse_iteratorrit;

//定義反向迭代器ritfor(rit=myv.rbegin();rit!=myv.rend();++rit)

//從尾到頭遍歷所有元素 printf("%d",*rit); //輸出：321printf("\n");1.3.2常用的STL容器順序容器適配器容器關(guān)聯(lián)容器1.順序容器1）vector（向量容器）

它是一個向量類模板。向量容器相當(dāng)于數(shù)組。

用于存儲具有相同數(shù)據(jù)類型的一組元素，可以從末尾快速的插入與刪除元素，快速地隨機訪問元素，但是在序列中間插入、刪除元素較慢，因為需要移動插入或刪除處后面的所有元素。vector<int>v1; //定義元素為int的向量v1vector<int>v2(10); //指定向量v2的初始大小為10個int元素vector<double>v3(10，1.23); //指定v3的10個初始元素的初值為1.23vector<int>v4(a，a+5); //用數(shù)組a[0..4]共5個元素初始化v4定義vector容器的幾種方式如下：vector提供了一系列的成員函數(shù)，vector主要的成員函數(shù)如下：empty()：判斷當(dāng)前向量容器是否為空。size()：返回當(dāng)前向量容器的中的實際元素個數(shù)。[]：返回指定下標(biāo)的元素。reserve(n)：為當(dāng)前向量容器預(yù)分配n個元素的存儲空間。capacity()：返回當(dāng)前向量容器在重新進行內(nèi)存分配以前所能容納的元素個數(shù)。resize(n)

：調(diào)整當(dāng)前向量容器的大小，使其能容納n個元素。push_back()：在當(dāng)前向量容器尾部添加了一個元素。insert(pos，elem)：在pos位置插入元素elem，即將元素elem插入到迭代器pos指定元素之前。front()：獲取當(dāng)前向量容器的第一個元素。back()：獲取當(dāng)前向量容器的最后一個元素。erase()：刪除當(dāng)前向量容器中某個迭代器或者迭代器區(qū)間指定的元素。clear()：刪除當(dāng)前向量容器中所有元素。迭代器函數(shù)：begin()、end()、rbegin()、rend()。#include<vector>usingnamespacestd;voidmain(){vector<int>myv; //定義vector容器myvvector<int>::iteratorit; //定義myv的正向迭代器itmyv.push_back(1); //在myv末尾添加元素1it=myv.begin(); //it迭代器指向開頭元素1myv.insert(it,2); //在it指向的元素之前插入元素2myv.push_back(3); //在myv末尾添加元素3myv.push_back(4); //在myv末尾添加元素4it=myv.end(); //it迭代器指向尾元素4的后面it--; //it迭代器指向尾元素4myv.erase(it); //刪除元素4

for(it=myv.begin();it!=myv.end();++it) printf("%d",*it);printf("\n");}2）string（字符串容器）string是一個保存字符序列的容器，所有元素為字符類型，類似vector<char>。

除了有字符串的一些常用操作以外，還有包含了所有的序列容器的操作。字符串的常用操作包括增加、刪除、修改、查找比較、連接、輸入、輸出等。創(chuàng)建string容器的幾種方式如下：charcstr[]="China!GreateWall"; //C-字符串strings1(cstr); //s1:China!GreateWallstrings2(s1); //s2:China!GreateWallstrings3(cstr，7，11); //s3:GreateWallstrings4(cstr，6); //s4:China!strings5(5，'A'); //s5:AAAAA常用的成員函數(shù)如下：empty()：判斷當(dāng)前字符串是否為空串。size()：返回當(dāng)前字符串的實際字符個數(shù)（返回結(jié)果為size_type類型）。length()：返回當(dāng)前字符串的實際字符個數(shù)。[idx]：返回當(dāng)前字符串位于idx位置的字符，idx從0開始。at(idx)：返回當(dāng)前字符串位于idx位置的字符。compare(conststring&str)：返回當(dāng)前字符串與字符串str的比較結(jié)果。在比較時，若兩者相等，返回0；前者小于后者，返回-1；否則返回1。append(cstr)：在當(dāng)前字符串的末尾添加一個字符串str。insert(size_typeidx，conststring&str) ：在當(dāng)前字符串的idx處插入一個字符串str。empty()：判斷當(dāng)前字符串是否為空串。size()：返回當(dāng)前字符串的實際字符個數(shù)（返回結(jié)果為size_type類型）。length()：返回當(dāng)前字符串的實際字符個數(shù)。[idx]：返回當(dāng)前字符串位于idx位置的字符，idx從0開始。at(idx)：返回當(dāng)前字符串位于idx位置的字符。compare(conststring&str)：返回當(dāng)前字符串與字符串str的比較結(jié)果。在比較時，若兩者相等，返回0；前者小于后者，返回-1；否則返回1。append(cstr)：在當(dāng)前字符串的末尾添加一個字符串str。insert(size_typeidx，conststring&str) ：在當(dāng)前字符串的idx處插入一個字符串str。迭代器函數(shù)：begin()、end()、rbegin()、rend()。#include<iostream>#include<string>usingnamespacestd;voidmain(){strings1="",s2,s3="Bye";s1.append("Goodmorning"); //s1="Goodmorning"

s2=s1; //s1="Goodmorning"inti=s2.find("morning"); //i=5s2.replace(i,s2.length()-i,s3); //相當(dāng)于s2.replace(5,7,s3)cout<<"s1:"<<s1<<endl;cout<<"s2:"<<s2<<endl;}求解模板生成工具問題。成成最近在搭建一個網(wǎng)站，其中一些頁面的部分內(nèi)容來自數(shù)據(jù)庫中不同的數(shù)據(jù)記錄，但是頁面的基本結(jié)構(gòu)是相同的。例如，對于展示用戶信息的頁面，當(dāng)用戶為Tom時，網(wǎng)頁的源代碼如下：而當(dāng)用戶為Jerry時，網(wǎng)頁的源代碼如下：CSP-201509-3

這樣的例子在包含動態(tài)內(nèi)容的網(wǎng)站中還有很多。為了簡化生成網(wǎng)頁的工作，成成覺得他需要引入一套模板生成系統(tǒng)。模板是包含特殊標(biāo)記的文本。成成用到的模板只包含一種特殊標(biāo)記，格式為{{VAR}}，其中VAR是一個變量。該標(biāo)記在模板生成時會被變量VAR的值所替代。例如，如果變量name="Tom"，則{{name}}會生成Tom。具體的規(guī)則如下：變量名由大小寫字母、數(shù)字和下劃線（_）構(gòu)成，且第一個字符不是數(shù)字，長度不超過16個字符。變量名是大小寫敏感的，Name和name是兩個不同的變量。變量的值是字符串。如果標(biāo)記中的變量沒有定義，則生成空串，相當(dāng)于把標(biāo)記從模板中刪除。模板不遞歸生成。也就是說，如果變量的值中包含形如{{VAR}}的內(nèi)容，不再做進一步的替換。

輸入格式：輸入的第一行包含兩個整數(shù)m和n，分別表示模板的行數(shù)和模板生成時給出的變量個數(shù)。接下來m行，每行是一個字符串，表示模板。接下來n行，每行表示一個變量和它的值，中間用一個空格分隔。值是字符串，用雙引號（"）括起來，內(nèi)容可包含除雙引號以外的任意可打印ASCII字符（ASCII碼范圍32,33,35～126）。

輸出格式：輸出包含若干行，表示模板生成的結(jié)果。112<!DOCTYPEhtml><html><head><title>User{{name}}</title></head><body><h1>{{name}}</h1><p>Email:<ahref="mailto:{{email}}">{{email}}</a></p><p>Address:{{address}}</p></body></html>name"DavidBeckham"email"david@"樣例輸入：<!DOCTYPEhtml><html><head><title>UserDavidBeckham</title></head><body><h1>DavidBeckham</h1><p>Email:<ahref="mailto:david@">david@</a></p><p>Address:</p></body></html>樣例輸出：0≤m≤100，0≤n≤100輸入的模板每行長度不超過80個字符（不包含換行符）。輸入保證模板中所有以{{開始的子串都是合法的標(biāo)記，開始是兩個左大括號和一個空格，然后是變量名，結(jié)尾是一個空格和兩個右大括號。輸入中所有變量的值字符串長度不超過100個字符（不包括雙引號）。保證輸入的所有變量的名字各不相同。評測用例規(guī)模與約定：

解：采用vector<string>向量content存放網(wǎng)頁，每一行作為一個元素。用map<string，string>容器存放轉(zhuǎn)換字符串。例如，對于題目中的樣例，content向量中下標(biāo)為0到10的元素如下：<!DOCTYPEhtml><html><head><title>User{{name}}</title></head><body><h1>{{name}}</h1><p>Email:<ahref="mailto:{{email}}">{{email}}</a></p><p>Address:{{address}}</p></body>mymap映射容器中包含如下兩個結(jié)點（注意雙引號是值的一部分）：mymap[email]="david@"mymap[name]="DavidBeckham"

然后掃描content的每個元素，查找形如“{{var}}”的字符串，將{{var}}用mymap[var]替換（注意替換部分不包含雙引號），在一個元素中可以有多個需要替換的內(nèi)容。例如，將：href="mailto:{{email}}">{{email}}</a></p>替換為：href="mailto:david@">david@</a></p>字符串查找、替換均采用string的成員函數(shù)完成。對應(yīng)的程序如下：#include<iostream>#include<vector>#include<string>#include<map>usingnamespacestd;vector<string>content; //存放網(wǎng)頁map<string，string>mymap; //存放轉(zhuǎn)換字符串intm，n;voidtrans() //網(wǎng)頁轉(zhuǎn)換{for(inti=0;i<m;i++) //轉(zhuǎn)換content向量中的所有行{ intpos=0，pos1，pos2; do {pos1=content[i].find("{{"，pos);

//從pos位置開始查找第一個{{

pos2=content[i].find("}}"，pos1);

//從pos1位置開始查找第一個}} if(pos1>=0&&pos2>=0) //找到{{}} { stringvar=content[i].substr(pos1+3，pos2-pos1-4); if(mymap.count(var)) //提取形如{{var}} {stringresult=mymap[var].substr(2， mymap[var].length()-3); content[i].replace(pos1，var.length()+6，result);//替換 } else content[i].replace(pos1，var.length()+6，""); pos=pos1+var.length(); } else //沒有找到{{}}，pos指向當(dāng)前字符串末尾 pos=content[i].length(); }while(pos<content[i].length());}}intmain(){inti;stringline;cin>>m>>n;cin.ignore(); //屏蔽回車鍵for(i=0;i<m;i++) //輸入m行存放在content向量中{ getline(cin，line); content.push_back(line);}for(i=0;i<n;i++) //輸入n行按空格分為兩個部分{ getline(cin，line); intpos=line.find(""); mymap.insert(map<string，string>::value_type( line.substr(0，pos)，line.substr(pos)));}

trans();for(i=0;i<m;i++) //輸出網(wǎng)頁轉(zhuǎn)換結(jié)果 cout<<content[i]<<endl;return0;}3）deque（雙端隊列容器）

它是一個雙端隊列類模板。雙端隊列容器由若干個塊構(gòu)成，每個塊中元素地址是連續(xù)的，塊之間的地址是不連續(xù)的，有一個特定的機制將這些塊構(gòu)成一個整體。可以從前面或后面快速插入與刪除元素，并可以快速地隨機訪問元素，但刪除元素較慢?！眍^表尾………定義deque雙端隊列容器的幾種方式如下：deque<int>dq1; //定義元素為int的雙端隊列dq1deque<int>dq2(10); //指定dq2的初始大小為10個int元素deque<double>dq3(10，1.23);

//指定dq3的10個初始元素的初值為1.23deque<int>dq4(dq2.begin()，dq2.end());

//用dq2的所有元素初始化dq4deque主要的成員函數(shù)如下：empty()：判斷雙端隊列容器是否為空隊。size()：返回雙端隊列容器中元素個數(shù)。push_front(elem)：在隊頭插入元素elem。push_back(elem)：在隊尾插入元素elem。pop_front()：刪除隊頭一個元素。pop_back()：刪除隊尾一個元素。erase()：從雙端隊列容器中刪除一個或幾個元素。clear()：刪除雙端隊列容器中所有元素。迭代器函數(shù)：begin()、end()、rbegin()、rend()。#include<deque>usingnamespacestd;voiddisp(deque<int>&dq) //輸出dq的所有元素{deque<int>::iteratoriter; //定義迭代器iterfor(iter=dq.begin();iter!=dq.end();iter++) printf("%d",*iter);printf("\n");}voidmain(){deque<int>dq; //建立一個雙端隊列dqdq.push_front(1); //隊頭插入1dq.push_back(2); //隊尾插入2dq.push_front(3); //隊頭插入3dq.push_back(4); //隊尾插入4printf("dq:");disp(dq);dq.pop_front(); //刪除隊頭元素dq.pop_back(); //刪除隊尾元素printf("dq:");disp(dq);}4）list（鏈表容器）

它是一個雙鏈表類模板?？梢詮娜魏蔚胤娇焖俨迦肱c刪除。它的每個結(jié)點之間通過指針鏈接，不能隨機訪問元素。表頭表尾…定義list容器的幾種方式如下：list<int>l1; //定義元素為int的鏈表l1list<int>l2(10); //指定鏈表l2的初始大小為10個int元素list<double>l3(10，1.23); //指定l3的10個初始元素的初值為1.23list<int>l4(a，a+5); //用數(shù)組a[0..4]共5個元素初始化l4list的主要成員函數(shù)如下：empty()：判斷鏈表容器是否為空。size()：返回鏈表容器中實際元素個數(shù)。push_back()：在鏈表尾部插入元素。pop_back()：刪除鏈表容器的最后一個元素。remove()：刪除鏈表容器中所有指定值的元素。remove_if(cmp)：刪除鏈表容器中滿足條件的元素。erase()：從鏈表容器中刪除一個或幾個元素。unique()：刪除鏈表容器中相鄰的重復(fù)元素。clear()：刪除鏈表容器中所有的元素。insert(pos，elem)：在pos位置插入元素elem，即將元素elem插入到迭代器pos指定元素之前。insert(pos，n，elem)：在pos位置插入n個元素elem。insert(pos，pos1，pos2)：在迭代器pos處插入[pos1，pos2)的元素。reverse()：反轉(zhuǎn)鏈表。sort()：對鏈表容器中的元素排序。迭代器函數(shù)：begin()、end()、rbegin()、rend()。

說明：STL提供的sort()排序算法主要用于支持隨機訪問的容器，而list容器不支持隨機訪問，為此，list容器提供了sort()采用函數(shù)用于元素排序。類似的還有unique()、reverse()、merge()等STL算法。#include<list>usingnamespacestd;voiddisp(list<int>&lst) //輸出lst的所有元素{list<int>::iteratorit;for(it=lst.begin();it!=lst.end();it++) printf("%d",*it);printf("\n");}voidmain(){list<int>lst; //定義list容器lstlist<int>::iteratorit,start,end;lst.push_back(5); //添加5個整數(shù)5,2,4,1,3lst.push_back(2);lst.push_back(4);lst.push_back(1);lst.push_back(3);printf("初始lst:");disp(lst);it=lst.begin(); //it指向首元素5start=++lst.begin(); //start指向第2個元素2end=--lst.end(); //end指向尾元素3lst.insert(it,start,end);printf("執(zhí)行l(wèi)st.insert(it,start,end)\n");printf("插入后lst:");disp(lst);}2.關(guān)聯(lián)容器1）set（集合容器）/multiset（多重集容器）set和multiset都是集合類模板，其元素值稱為關(guān)鍵字。set中元素的關(guān)鍵字是唯一的，multiset中元素的關(guān)鍵字可以不唯一，而且默認(rèn)情況下會對元素按關(guān)鍵字自動進行升序排列。

查找速度比較快，同時支持集合的交、差和并等一些集合上的運算，如果需要集合中的元素允許重復(fù)那么可以使用multiset。set/multiset的成員函數(shù)如下：empty()：判斷容器是否為空。size()：返回容器中實際元素個數(shù)。insert()：插入元素。erase()：從容器刪除一個或幾個元素。clear()：刪除所有元素。count(k)：返回容器中關(guān)鍵字k出現(xiàn)的次數(shù)。find(k)：如果容器中存在關(guān)鍵字為k的元素，返回該元素的迭代器，否則返回end()值。upper_bound()：返回一個迭代器，指向關(guān)鍵字大于k的第一個元素。lower_bound()：返回一個迭代器，指向關(guān)鍵字不小于k的第一個元素。迭代器函數(shù)：begin()、end()、rbegin()、rend()。#include<set>usingnamespacestd;voidmain(){set<int>s; //定義set容器sset<int>::iteratorit; //定義set容器迭代器its.insert(1);s.insert(3);s.insert(2);s.insert(4);s.insert(2);printf("s:");for(it=s.begin();it!=s.end();it++) printf("%d",*it);printf("\n");s:1234

multiset<int>ms; //定義multiset容器msmultiset<int>::iteratormit;

//定義multiset容器迭代器mitms.insert(1);ms.insert(3);ms.insert(2);ms.insert(4);ms.insert(2);printf("ms:");for(mit=ms.begin();mit!=ms.end();mit++) printf("%d",*mit);printf("\n");}ms:12234map和multimap都是映射類模板。映射是實現(xiàn)關(guān)鍵字與值關(guān)系的存儲結(jié)構(gòu)，可以使用一個關(guān)鍵字key來訪問相應(yīng)的數(shù)據(jù)值value。

在set/multiset中的key和value都是key類型，而key和value是一個pair類結(jié)構(gòu)。pair類結(jié)構(gòu)的聲明形如：2）map（映射容器）/multimap（多重映射容器）structpair{Tfirst;Tsecond;}

map/multimap利用pair的<運算符將所有元素即key-value對按key的升序排列，以紅黑樹的形式存儲，可以根據(jù)key快速地找到與之對應(yīng)的value（查找時間為O(log2n)）。

map中不允許關(guān)鍵字重復(fù)出現(xiàn)，支持[]運算符；而multimap中允許關(guān)鍵字重復(fù)出現(xiàn)，但不支持[]運算符。map/multimap的主要成員函數(shù)如下：empty()：判斷容器是否為空。size()：返回容器中實際元素個數(shù)。map[key]：返回關(guān)鍵字為key的元素的引用，如果不存在這樣的關(guān)鍵字，則以key作為關(guān)鍵字插入一個元素（不適合multimap）。insert(elem)：插入一個元素elem并返回該元素的位置。clear()：刪除所有元素。find()：在容器中查找元素。count()：容器中指定關(guān)鍵字的元素個數(shù)（map中只有1或者0）。迭代器函數(shù)：begin()、end()、rbegin()、rend()。

在map中修改元素非常簡單，這是因為map容器已經(jīng)對[]運算符進行了重載。例如：map<char,int>mymap;

//定義map容器mymap，其元素類型為pair<char,int>mymap['a']=1;//或者mymap.insert(pair<char，int>('a',1));

獲得map中一個值的最簡單方法如下：

intans=mymap['a'];只有當(dāng)map中有這個關(guān)鍵字（'a'）時才會成功，否則會自動插入一個元素，值為初始化值?？梢允褂胒ind()方法來發(fā)現(xiàn)一個關(guān)鍵字是否存在。#include<map>usingnamespacestd;voidmain(){map<char,int>mymap; //定義map容器mymapmymap.insert(pair<char,int>('a',1));

//插入方式1mymap.insert(map<char,int>::value_type('b',2));

//插入方式2mymap['c']=3; //插入方式3map<char,int>::iteratorit;for(it=mymap.begin();it!=mymap.end();it++) printf("[%c,%d]",it->first,it->second);printf("\n");}[a,1][b,2][c,3]3.適配器容器1）stack（棧容器）

它是一個棧類模板，和數(shù)據(jù)結(jié)構(gòu)中的棧一樣，具有后進先出的特點。棧容器默認(rèn)的底層容器是deque。也可以指定其他底層容器。

例如，以下語句指定myst棧的底層容器為vector：stack<string,vector<string>>myst; //第2個參數(shù)指定底層容器為vector

注意：stack容器沒有begin()/end()和rbegin()/rend()這樣的用于迭代器的成員函數(shù)。stack容器主要的成員函數(shù)如下：empty()：判斷棧容器是否為空。size()：返回棧容器中實際元素個數(shù)。push(elem)：元素elem進棧。top()：返回棧頂元素。pop()：元素出棧。#include<stack>usingnamespacestd;voidmain(){stack<int>st;

st.push(1);st.push(2);st.push(3);printf("棧頂元素:%d\n",st.top());printf("出棧順序:");while(!st.empty()) //棧不空時出棧所有元素{ printf("%d",st.top()); st.pop();}printf("\n");}2）queue（隊列容器）

它是一個隊列類模板，和數(shù)據(jù)結(jié)構(gòu)中的隊列一樣，具有先進先出的特點。不允許順序遍歷，沒有begin()/end()和rbegin()/rend()這樣的用于迭代器的成員函數(shù)。主要的成員函數(shù)如下：empty()：判斷隊列容器是否為空。size()：返回隊列容器中實際元素個數(shù)。front()：返回隊頭元素。back()：返回隊尾元素。push(elem)：元素elem進隊。pop()：元素出隊。#include<queue>usingnamespacestd;voidmain(){queue<int>qu;qu.push(1);qu.push(2);qu.push(3);printf("隊頭元素:%d\n",qu.front());printf("隊尾元素:%d\n",qu.back());printf("出隊順序:");while(!qu.empty()) //出隊所有元素{ printf("%d",qu.front()); qu.pop();}printf("\n");}3）priority_queue（優(yōu)先隊列容器）

它是一個優(yōu)先隊列類模板。優(yōu)先隊列是一種具有受限訪問操作的存儲結(jié)構(gòu)，元素可以以任意順序進入優(yōu)先隊列。

一旦元素在優(yōu)先隊列容器中，出隊操作將出隊列最高優(yōu)先級元素。主要的成員函數(shù)如下：empty()：判斷優(yōu)先隊列容器是否為空。size()：返回優(yōu)先隊列容器中實際元素個數(shù)。push(elem)：元素elem進隊。top()：獲取隊頭元素。pop()：元素出隊。#include<queue>usingnamespacestd;voidmain(){priority_queue<int>qu;qu.push(3);qu.push(1);qu.push(2);printf("隊頭元素:%d\n",qu.top());printf("出隊順序:");while(!qu.empty()) //出隊所有元素{ printf("%d",qu.top()); qu.pop();}printf("\n");}1.3.3STL在算法設(shè)計中的應(yīng)用

算法設(shè)計重要步驟是設(shè)計數(shù)據(jù)的存儲結(jié)構(gòu)，除非特別指定，程序員可以采用STL中的容器存放主數(shù)據(jù)，選擇何種容器不僅要考慮數(shù)據(jù)的類型，還有考慮數(shù)據(jù)的處理過程。

例如，字符串可以采用string或者vector<char>來存儲，鏈表可以采用list來存儲。1.存放主數(shù)據(jù)

【例1.11】有一段英文由若干單詞組成，單詞之間用一個空格分隔。編寫程序提取其中的所有單詞。

解：這里的主數(shù)據(jù)是一段英文，采用string字符串str存儲它，最后提取的單詞采用vector<string>容器words存儲。#include<iostream>#include<string>#include<vector>usingnamespacestd;voidsolve(stringstr,vector<string>&words)//產(chǎn)生所有單詞words{stringw;inti=0;intj=str.find(""); //查找第一個空格while(j!=-1) //找到單詞后循環(huán){ w=str.substr(i,j-i); //提取一個單詞 words.p