數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)與算法

同學(xué)們好！現(xiàn)在我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語(yǔ)算法線性表?xiàng)：完?duì)列二叉樹(shù)查找與排序兩類(lèi)問(wèn)題：第一類(lèi).數(shù)值計(jì)算問(wèn)題求解線性方程組；求解高次方程組；模型（問(wèn)題描述）：算法：數(shù)學(xué)方程計(jì)算公式特點(diǎn)：數(shù)據(jù)簡(jiǎn)單。側(cè)重于建立程序，以程序?yàn)橹行?/p>

第1節(jié)數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語(yǔ)第二類(lèi)非數(shù)值計(jì)算問(wèn)題例一:

將一組數(shù)據(jù)按大小進(jìn)行排序。模型:算法:基本操作是“比較兩個(gè)數(shù)的大小”一組數(shù)據(jù)的列表（線性表）特點(diǎn)：程序簡(jiǎn)單，數(shù)據(jù)規(guī)模可能很大，程序設(shè)計(jì)以數(shù)據(jù)為中心主要解決過(guò)程控制，決策和數(shù)據(jù)處理等問(wèn)題。例二：計(jì)算機(jī)對(duì)弈對(duì)弈的規(guī)則和策略棋盤(pán)及棋盤(pán)的（變化）格局特點(diǎn)：需要有交互過(guò)程。棋盤(pán)格局的變化是樹(shù)型結(jié)構(gòu)

模型：算法：例三：鋪設(shè)城市間的天然氣管道模型：算法：圖優(yōu)化策略歸納：

對(duì)于非數(shù)值計(jì)算，程序設(shè)計(jì)的本質(zhì)是：對(duì)需要解決的問(wèn)題選擇一種好的數(shù)學(xué)模型（數(shù)據(jù)結(jié)構(gòu)），并加上一種好的算法。

程序＝數(shù)據(jù)結(jié)構(gòu)＋算法程序:數(shù)據(jù)結(jié)構(gòu):算法:為計(jì)算機(jī)處理問(wèn)題編制一組指令集

處理問(wèn)題的策略問(wèn)題的數(shù)學(xué)模型定位：

數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。第1小節(jié)為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)的操作對(duì)象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理。要使計(jì)算機(jī)能更有效地進(jìn)行這些非數(shù)值性理，就必須弄清楚這些操作對(duì)象的特點(diǎn)，在計(jì)算機(jī)中的表示方式以及各個(gè)操作的具體實(shí)現(xiàn)手段。目的：合理織數(shù)據(jù)，提高程序效益。能被計(jì)算機(jī)處理的符號(hào)(數(shù)值、字符、聲音、圖形、圖像等)的集合。1.數(shù)據(jù):2.數(shù)據(jù)元素:

如果把數(shù)據(jù)作為一個(gè)集合，則集合中的每一個(gè)獨(dú)立“個(gè)體”稱為數(shù)據(jù)元素。數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)集合中的所有數(shù)據(jù)元素的屬性相同。第2小節(jié)數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(yǔ)例如：描述一個(gè)學(xué)生信息的數(shù)據(jù)元素稱之為組合項(xiàng)年月日姓名學(xué)號(hào)班號(hào)性別出生日期入學(xué)成績(jī)?cè)禹?xiàng)數(shù)據(jù)元素也可以由若干數(shù)據(jù)項(xiàng)構(gòu)成。3.數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合。無(wú)限集：整數(shù)數(shù)據(jù)對(duì)象是集合N={0，±1，±2，…}，有限集：大寫(xiě)字母字符數(shù)據(jù)對(duì)象是集合C={‘A’，‘B’，…，‘Z’}，多個(gè)數(shù)據(jù)項(xiàng)組成的復(fù)合數(shù)據(jù)元素集：

10020741班學(xué)生基本情況也可看作一個(gè)數(shù)據(jù)對(duì)象。

4.數(shù)據(jù)結(jié)構(gòu)帶結(jié)構(gòu)的數(shù)據(jù)元素的集合

1）數(shù)據(jù)結(jié)構(gòu)：一個(gè)有相同特性的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”例如：IP地址（IPv4）是一個(gè)用四個(gè)3位的十進(jìn)制數(shù)表示一個(gè)數(shù)據(jù)結(jié)構(gòu)。如：166.111.102.128─a1(166),a2(111),a3(102),a4(128)則：在數(shù)據(jù)元素a1、a2、a3和a4之間存在著“次序”關(guān)系

a1,a2、a2,a3、a3,a4166.111.102.128a1a2a3a4111.166.102.128a2a1a3a4≠注意：又如：在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:列的次序關(guān)系:注意：row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6

a1a2a3a4a5a6

a1a2a3a4a5a6≠2）數(shù)據(jù)結(jié)構(gòu)的形式定義:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。例如:定義“班集體”為一個(gè)數(shù)據(jù)結(jié)構(gòu)Class=(D,S)D={a,b1,…,bn,c1,…cn,d1,…dn

}S={R1,R2}R1={<a,b1>,<a,c1>,<a,d1>}R2={<b1,bj>,<c1,cj>,<d1,dj>|j=2,3,…,n}從數(shù)據(jù)間的關(guān)系來(lái)看，數(shù)據(jù)關(guān)系可歸結(jié)為以下四種結(jié)構(gòu):線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)3）數(shù)據(jù)結(jié)構(gòu)分類(lèi)分類(lèi)數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”

和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)：

是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述。它對(duì)應(yīng)一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系;物理結(jié)構(gòu)：

是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。4）邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

—邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象：所有數(shù)據(jù)元素都映象為二進(jìn)制位串(321)10=(501)8=(101000001)2

A=(101)8=(001000001)2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的具體實(shí)現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。常見(jiàn)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：特點(diǎn)是借助于數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：特點(diǎn)是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。“關(guān)系”的映象：①

順序存儲(chǔ)結(jié)構(gòu)：(1)連續(xù)存放;邏輯上相鄰,物理上也相鄰。

(2)結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)。

(3)插入、刪除操作不便（需大量移動(dòng)元素）。②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：(1)非連續(xù)存放,借助指針來(lái)表示元素間的關(guān)系;

(2)插入、刪除操作簡(jiǎn)單，只要修改指針即可；

(3)結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系(1)數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，依賴于計(jì)算機(jī)；離開(kāi)了機(jī)器，則無(wú)法進(jìn)行任何操作。(3)任何一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。5）抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型（簡(jiǎn)稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類(lèi)型的描述方法：ADTname{

數(shù)據(jù)對(duì)象：D={……}

數(shù)據(jù)關(guān)系：R={……}

基本操作：創(chuàng)建；輸出；插入；刪除；等等;}ADTname;【例】復(fù)數(shù)的抽象數(shù)據(jù)類(lèi)型描述ADTComplex{

數(shù)據(jù)對(duì)象：D={c1,c2|c1,c2∈float}

數(shù)據(jù)關(guān)系：R={<c1,c2>|c1,c2分別代表復(fù)數(shù)的實(shí)部和虛部}

基本操作：創(chuàng)建一個(gè)復(fù)數(shù)；輸出一個(gè)復(fù)數(shù)；求兩個(gè)復(fù)數(shù)的和；求兩個(gè)復(fù)數(shù)的積；等等;}ADTComplex;第2節(jié)算法第1小節(jié)算法的基本概念①算法：

是對(duì)特定問(wèn)題求解步驟的一種描述。②算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系：對(duì)存放在物理結(jié)構(gòu)上的數(shù)據(jù),按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。③設(shè)計(jì)算法的步驟：通過(guò)對(duì)問(wèn)題進(jìn)行詳細(xì)地分析，確定方案；確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法；選用某種語(yǔ)言將算法轉(zhuǎn)換成程序；調(diào)試并運(yùn)行這些程序。④算法的特性（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過(guò)已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。

（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。

（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。⑤算法設(shè)計(jì)的要求（1）正確性（Correctness）有4個(gè)層次：

A.程序不含語(yǔ)法錯(cuò)誤；

B.程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果；

C.程序?qū)倪x擇的、典型的、苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果；

D.程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。（2）可讀性（Readability）

算法的第一目的是為了閱讀和交流;可讀性有助于對(duì)算法的理解;可讀性有助于對(duì)算法的調(diào)試和修改。

（3）健壯性（Robustness）

當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理；并且，處理出錯(cuò)的方法應(yīng)該是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值并中止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。

（4）高效率與低存儲(chǔ)量

處理速度快;存儲(chǔ)容量小;時(shí)間和空間是矛盾的、實(shí)際問(wèn)題的求解往往是求得時(shí)間和空間的統(tǒng)一、折中。第2小節(jié)算法評(píng)價(jià)的標(biāo)準(zhǔn)（效率的度量）①評(píng)價(jià)算法好壞的標(biāo)準(zhǔn)

求解同一計(jì)算問(wèn)題可能有許多不同的算法，究竟如何來(lái)評(píng)價(jià)這些算法的好壞以便從中選出較好的算法呢？

選用的算法首先應(yīng)該是“正確”的。此外，主要考慮如下三點(diǎn)：

第一：執(zhí)行算法所耗費(fèi)的時(shí)間；

第二：執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間；

第三：算法應(yīng)易于理解，易于編碼，易于調(diào)試②算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1。必須執(zhí)行程序

2。其它因素掩蓋算法本質(zhì)算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問(wèn)題的規(guī)模3．編寫(xiě)程序的語(yǔ)言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度③時(shí)間復(fù)雜度（指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。）

一般情況下，算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。

算法的時(shí)間復(fù)雜度記做

T(n)=O(f(n))用"O（數(shù)量級(jí)）"來(lái)表示，稱為"階"。

對(duì)算法效率分析問(wèn)題的簡(jiǎn)化：【例】求兩個(gè)n階方陣的乘積C=A×B

constintn=100

;voidMatrixMultiply(intA[n][n]，intB[n][n]，intC[n][n])

{//紅色為各語(yǔ)句的頻度

inti,j,k;

(1)for(i=0;i＜n;j++)n+1

(2)

for(j=0;j＜n;j++)n(n+1)

(3)

{C[i][j]=0;n2

(4)

for(k=0;k＜n;k++)n2

(n+1)

(5)

C[i][j]=C[i][j]+A[i][k]*B[k][j];n3

}

}}該算法中所有語(yǔ)句的頻度之和(即算法的時(shí)間耗費(fèi))為：

T(n)=2n3+3n2+2n+1

這表明，當(dāng)n充分大時(shí)，T(n)和n3之比是一個(gè)不等于零的常數(shù)。即T(n)和n3是同階的，或者說(shuō)T(n)和n3的數(shù)量級(jí)相同。記作T(n)=O(n3)是算法的漸近時(shí)間復(fù)雜度。

for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例選擇排序

void

select_sort(inta[],intn){

}//select_sort基本操作:比較操作時(shí)間復(fù)雜度:O(n2)j=i;//

選擇第i個(gè)最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;

n+1

nn(n-1)/2

nn(n+1)/2【例】（a）x=x+1；O（1）（c）for(i=0;i<n;i++)

（b）for(i=0;i<n;i++)for(j=0;j<n;j++)

x=x+1；O（n）x=x+1；O（n2）

（d）i=1;

while(i<n) i=i*2;O（log2n）常見(jiàn)的時(shí)間復(fù)雜度有：O（1）常數(shù)階

O（log2n）對(duì)數(shù)階

O（n）線性階

O（n2）平方階

O(2n）指數(shù)階102030405020040060080010001200140010n20n5nlogn2n22n④空間復(fù)雜度（數(shù)據(jù)、程序、輔助）

一個(gè)算法的空間復(fù)雜度(SpaceComplexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。

⑤算法性能選擇

要節(jié)約算法的執(zhí)行時(shí)間往往要以犧牲更多的空間為代價(jià)；而為了節(jié)省空間可能要耗費(fèi)更多的計(jì)算時(shí)間。因此我們只能根據(jù)具體情況有所側(cè)重：

①若該程序使用次數(shù)較少，則力求算法簡(jiǎn)明易懂；

②對(duì)于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；

③若待解決的問(wèn)題數(shù)據(jù)量極大，機(jī)器的存儲(chǔ)空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。

線性表是最簡(jiǎn)單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。掌握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及線性表的基本運(yùn)算以及實(shí)現(xiàn)算法。

第3節(jié)線性表

線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素的含義廣泛，在不同的具體情況下，可以有不同的含義。1.線性表的定義

線性表L是n（n≥0）個(gè)具有相同屬性的數(shù)據(jù)元素a1，a2，a3，…，an組成的有限序列，其中序列中元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表，即不含有任何元素。常常將非空的線性表(n>0)記作：(a1，a2，…an)

這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。第1小節(jié)線性表的基本概念及運(yùn)算

例1、26個(gè)英文字母組成的字母表（A，B，C、…、Z）

例2、從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。（6，17，28，50，92，188）例3、線性表的邏輯特征：在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a2；

有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨an-1；

其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。

線性表是一種典型的線性結(jié)構(gòu)。2.線性表的基本運(yùn)算(1)初始化線性表(2)求線性表的長(zhǎng)度(3)按序號(hào)取元素(4)按值查找(5)插入元素(6)刪除元素3.線性表的抽象數(shù)據(jù)類(lèi)型ADTLinear_list{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0；}

數(shù)據(jù)關(guān)系：R={<ai-1，ai>|ai-1,ai∈D,i=2,3,…,n}

基本操作：初始化空線性表；求線性表表長(zhǎng)；取線性表的第i個(gè)元素；在線性表的第i個(gè)位置插入元素x；刪除線性表的第i個(gè)元素；修改線性表中的第i個(gè)元素；按某種要求重排線性表中各元素的順序；按某個(gè)特定值查找線性表中的元素；

……}ADTLinear_list；第2小節(jié)線性表的順序結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)又稱順序表1.具有以下兩個(gè)基本特點(diǎn)：

(1)線性表的所有元素所占的存儲(chǔ)空間是連續(xù)的。用物理的連續(xù)表示邏輯的連續(xù)(2)在確定順序表起始位置后，線性表中各數(shù)據(jù)元素可隨機(jī)存取?？呻S機(jī)存取的存儲(chǔ)結(jié)構(gòu)

2.順序表類(lèi)定義及運(yùn)算實(shí)現(xiàn)：typedef

int

ElemType; constintMAXSIZE=100; classSqList{private:

ElemType

elem[MAXSIZE];intlength;public:

SqList(void);~SqList(){};voidCreat(intn);

voidPrintOut();

int

GetLength();

int

Locate(ElemTypex);

ElemType

GetElme(inti);voidInsert(inti,ElemTypex);voidDelete(inti); };

①初始化線性表：使用構(gòu)造函數(shù)實(shí)現(xiàn)SqList::SqList(){length=0;}

②得到線性表長(zhǎng)度：int

SqList::GetLength(){returnlength;}③創(chuàng)建線性表：voidSqList::Creat(intn){

cout<<"輸入"<<n<<"元素:\n";

for(intk=0;k<n;k++)cin>>elem[k]; length=n;}④輸出線性表：voidSqList::PrintOut() {

cout<<"length="<<length;

cout<<"\nPrintOutData:\n";

for(intk=0;k<length;k++)

cout<<setw(6)<<elem[k];

cout<<endl;}⑤查找值為x的元素：int

SqList::Locate(ElemTypex){

inti;

i=0;

while(i<length&&elem[i]!=x)

i++;

if(i<length)returni+1;

elsereturn0;}⑥得到第i個(gè)元素：ElemType

SqList::GetElme(inti){

if(i<1||i>length){cout<<"error\n";exit(1);}returnelem[i-1];}⑦第i個(gè)插入值為x的元素：voidSqList::Insert(inti,ElemTypex){

intj;if(i<1||i>length+1) {cout<<"error\n";exit(1);}

if(length==MAXSIZE) {cout<<"overflow!\n";exit(1);}

for(j=length;j>=i;j--)

elem[j]=elem[j-1];

//數(shù)據(jù)元素后移

elem[i-1]=x; //插入x

length++; //表長(zhǎng)度加1}

⑧刪除第i個(gè)元素：voidSqList::Delete(inti){intj;if(i<1||i>length)

{cout<<"不存在第i個(gè)元素\n";exit(0);}for(j=i;j<length;j++)elem[j-1]=elem[j];//向前移動(dòng)元素length--;}voidmain(){

SqListl;l.Creat(3);

cout<<"初始的線性表:\n";

l.PrintOut();

cout<<“\n查找值為x的元素:"<<l.Locate(2)<<endl;

cout<<"\n查找第i個(gè)元素:"<<l.GetElme(1);

cout<<"\n第i個(gè)位置插入值為x的元素:\n";l.Insert(1,10);

l.PrintOut();

cout<<"\n刪除第i個(gè)位置的元素:\n";l.Delete(2);

l.PrintOut();}【例】利用線性表的基本運(yùn)算，編寫(xiě)在線性表A中刪除線性表B中出現(xiàn)的元素的算法。

【解】本題的算法思路是：依次檢查線性表B中的每個(gè)元素，看它是否在線性表A中。若在線性表A中，則將其從A中刪除。本題的算法如下：

voiddelbina(SqList&A,SqList&B){int

i,k;

ElemTypex;

for(i=1;i<=B.GetLength();i++){x=B.GetElme(i);k=A.Locate(x);

if(k>0)A.Delete(k);}}【例】將順序表(a1，a2，a3，…，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大（這里假設(shè)數(shù)據(jù)元素的類(lèi)型具有可比性，可設(shè)為整型）。

【解】基本思路：從第二個(gè)元素開(kāi)始到最后一個(gè)元素，逐一向后掃描，當(dāng)數(shù)據(jù)元素ai比a1大時(shí)，表明它已經(jīng)在a1的后面，不必改變它與a1之間的位置，繼續(xù)比較下一個(gè)；當(dāng)數(shù)據(jù)元素ai比a1小時(shí)，表明它應(yīng)該在a1的前面，此時(shí)將它前面的元素依次向下移動(dòng)一個(gè)位置，然后將它置入最上方。算法如下：voidSqList::part(){

int

i,j;

ElemType

x,y;x=elem[0];//將基準(zhǔn)元素a1置入x中

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

if(elem[i]<x)//當(dāng)前元素小于a1{y=elem[i];

for(j=i-1;j>=0;j--)//移動(dòng)

elem[j+1]=elem[j];elem[0]=y;}}順序存儲(chǔ)結(jié)構(gòu)缺點(diǎn)主要表現(xiàn)在：（1）數(shù)據(jù)元素最大個(gè)數(shù)需預(yù)先確定，使得高級(jí)程序設(shè)計(jì)語(yǔ)言編譯系統(tǒng)需預(yù)先分配相應(yīng)的存儲(chǔ)空間；（2）插入與刪除運(yùn)算的效率很低。為了保持線性表中的數(shù)據(jù)元素順序，在插入操作和刪除操作時(shí)需移動(dòng)大量數(shù)據(jù)。對(duì)于插入和刪除操作頻繁的線性表、將導(dǎo)致系統(tǒng)的運(yùn)行速度難以提高。（3）存儲(chǔ)空間不便于擴(kuò)充。當(dāng)一個(gè)線性表分配順序存儲(chǔ)空間后，若線性表的存儲(chǔ)空間已滿，但還需要插入新的元素，則會(huì)發(fā)生“上溢”錯(cuò)誤。第3小節(jié)線性表的鏈?zhǔn)酱鎯?chǔ)和運(yùn)算實(shí)現(xiàn)

為避免大量結(jié)點(diǎn)的移動(dòng)，可以使用另一種存儲(chǔ)方式:鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈表(LinkedList)。

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素，都需用兩部分來(lái)存儲(chǔ)：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放直接前驅(qū)或直接后繼結(jié)點(diǎn)的地址（指針），稱為指針域，稱這種存儲(chǔ)單元為結(jié)點(diǎn)。

1鏈表的存儲(chǔ)結(jié)構(gòu)C++語(yǔ)言采用結(jié)構(gòu)數(shù)據(jù)類(lèi)型描述結(jié)點(diǎn)如下：typedef

structnode{ElemTypedata;//結(jié)點(diǎn)值

structnode*next;//存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址}

NodeType

;

假設(shè)有一個(gè)線性表為（A,B,C,D,E），存儲(chǔ)空間具有10個(gè)存儲(chǔ)結(jié)點(diǎn)，該線性表在存儲(chǔ)空間中的存儲(chǔ)情況如下圖所示。

2單向鏈表每個(gè)結(jié)點(diǎn)只有一個(gè)指向后繼的指針。也就是說(shuō)訪問(wèn)數(shù)據(jù)元素只能由鏈表頭依次到鏈表尾，而不能做逆向訪問(wèn)。稱這種鏈表為單向鏈表或線性鏈表。這是一種最簡(jiǎn)單的鏈表。對(duì)于空鏈表，頭結(jié)點(diǎn)的指針域?yàn)榭铡＃╝）為帶頭結(jié)點(diǎn)的空鏈(b)為帶頭結(jié)點(diǎn)的單鏈表單鏈表類(lèi)定義及運(yùn)算實(shí)現(xiàn)：classLinkList{private:

NodeType*Head;//鏈表頭指針public:

LinkList(void);~LinkList(){};voidCreat(intn); voidPrintOut();

int

GetLength();

NodeType*Locate(ElemTypex);

NodeType*GetElme(inti);voidInsert(inti,ElemTypex);

voidInsert(inti,NodeType*s)

voidDelete(inti);};①初始化單鏈表：使用構(gòu)造函數(shù)實(shí)現(xiàn)LinkList::LinkList(){Head=new

NodeType;Head->next=0;}

②得到鏈表長(zhǎng)度：int

LinkList::GetLength(){

intnum=0;

NodeType*p;p=Head->next;

while(p!=NULL){num++;p=p->next;}

return(num);}③創(chuàng)建單鏈表表：voidLinkList::Creat(intn){

inti;

NodeType*p,*pup;

if(n>0)

for(i=0;i<n;i++) { p=newNodeType;

cin>>p->data; p->next=NULL;

if(i==0)Head->next=p;elsepup->next=p; pup=p; }}④輸出單鏈表：voidLinkList::PrintOut() {

NodeType*p;p=Head->next;

while(p!=NULL){cout<<setw(6)<<p->data;p=p->next;}

cout<<endl;}⑤查找值為x的節(jié)點(diǎn)：NodeType*LinkList::Locate(ElemTypex){

NodeType*p;p=Head->next;

while(p!=NULL&&p->data!=x)p=p->next;returnp;}⑥得到第i個(gè)節(jié)點(diǎn)：NodeType*LinkList::GetElme(inti){

NodeType*p;

intpos=1;p=Head->next;

if(i<1||i>GetLength())exit(1);

while(pos<i){p=p->next;pos++;}returnp;}s=(LNode*)malloc(sizeof(LNode))；s->data=x；(b)申請(qǐng)新結(jié)點(diǎn)s，數(shù)據(jù)域置xxsheada1a2...ai-1p...aian∧xsheada1a2×...ai-1p...aian∧②①(a)找到插入位置s->next=q->nextq->next=s(c)修改指針域，將新結(jié)點(diǎn)s插入關(guān)鍵語(yǔ)句：qq⑦第i個(gè)插入值為x的元素：voidLinkList::Insert(inti,ElemTypex){

NodeType*p,*q,*s;

intpos=1;p=Head;

if(i<1||i>GetLength()+1)exit(1);s=newNodeType;s->data=x;

while(pos<=i){q=p;p=p->next;pos++;}s->next=q->next;q->next=s;}

如果插入的某節(jié)點(diǎn)：voidLinkList::Insert(inti,NodeType*s){

NodeType*p,*q;

intpos=1;

if(i<1||i>GetLength()+1)exit(1);p=Head;

while(pos<=i){q=p;p=p->next;pos++;}s->next=q->next;q->next=s;}x=p->data；(b)返回被刪除結(jié)點(diǎn)數(shù)據(jù)xxpheada1a2...ai-1q...aian∧(a)找到刪除位置pheada1...(c)修改指針域，將結(jié)點(diǎn)p刪除qai-1pai...an∧ai+1①②關(guān)鍵語(yǔ)句：q->next=p->next；free(p)⑧刪除第i個(gè)元素：voidLinkList::Delete(inti){

intpos=1;

NodeType*q=Head,*p;

if(i<1||i>GetLength())exit(1);

while(pos<i){q=q->next;pos++;}p=q->next;q->next=p->next;deletep;}

voidmain(){

LinkListl;l.Creat(3);

cout<<"初始的線性表:\n";

l.PrintOut();

cout<<endl<<l.GetLength()<<endl;

NodeType*p;p=l.GetElme(2);

cout<<endl<<"第2個(gè)元素："<<p->data<<endl;p=l.Locate(2);

cout<<endl<<"值為2個(gè)元素："<<p->data<<endl;l.Delete(1);

l.PrintOut();}【例】利用前面定義的基本運(yùn)算函數(shù)，編寫(xiě)將一已知的單鏈表H倒置的程序。如圖的操作。(a)為倒置前，(b)為倒置后。圖

單鏈表的倒置【解】算法基本思路：不另外增加新結(jié)點(diǎn)，而只是修改原結(jié)點(diǎn)的指針。設(shè)置指針p，令其指向head->next，并將head->next置空，然后依次將p所指鏈表的結(jié)點(diǎn)順序摘下，插入到head之后即可。具體算法如下：voidLinkList::reverse(){NodeType*p,*q;

if(Head->next!=NULL){p=Head->next;Head->next=NULL;

while(p!=NULL){q=p;p=p->next;Insert(1,q);}}}3循環(huán)鏈表

在單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨∟ULL）。訪問(wèn)單鏈表中任何數(shù)據(jù)只能從鏈表頭開(kāi)始順序訪問(wèn)，而不能進(jìn)行任何位置的隨機(jī)查詢?cè)L問(wèn)。如要查詢的結(jié)點(diǎn)在鏈表的尾部也需遍歷整個(gè)鏈表。所以單鏈表的應(yīng)用受到一定的限制。循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的頭結(jié)點(diǎn)，使整個(gè)鏈表頭尾相接形成一個(gè)環(huán)形。這樣，從鏈表中任一結(jié)點(diǎn)出發(fā)，順著指針鏈都可找到表中其它結(jié)點(diǎn)。循環(huán)鏈表的最大特點(diǎn)是不增加存儲(chǔ)量，只是簡(jiǎn)單地改變一下最后一個(gè)結(jié)點(diǎn)的指針指向，就可以使操作更加方便靈活。圖循環(huán)鏈表結(jié)構(gòu)示意圖帶頭結(jié)點(diǎn)的單循環(huán)鏈表的操作算法和帶頭結(jié)點(diǎn)的單鏈表的操作算法很相似，差別僅在于算法中的循環(huán)條件不同。在循環(huán)單鏈表上實(shí)現(xiàn)上述基本運(yùn)算的改動(dòng)如下：1）．初始化鏈表創(chuàng)建的頭結(jié)點(diǎn)指針域next不為空，而是指向自身，Head->next=Head2）．求線性表長(zhǎng)度GetLength()函數(shù)、查找運(yùn)算locate(x)函數(shù)、鏈表元素輸出運(yùn)算PrintOut()函數(shù)中，循環(huán)遍歷是否進(jìn)行的條件由p!=NULL改為p!=L;其余函數(shù)運(yùn)算沒(méi)有變化，請(qǐng)自行寫(xiě)出相關(guān)函數(shù)的定義。在循環(huán)鏈表中，除了有頭指針head外，有時(shí)還可加上一個(gè)尾指針tail。尾指針tail指向最后一結(jié)點(diǎn)，沿最后一個(gè)結(jié)點(diǎn)的指針又可立即找到鏈表的第一個(gè)結(jié)點(diǎn)。在實(shí)際應(yīng)用中，使用尾指針來(lái)代替頭指針進(jìn)行某些操作往往會(huì)更簡(jiǎn)單?！纠繉蓚€(gè)循環(huán)鏈表首尾相接進(jìn)行合并【解】算法思路：對(duì)兩個(gè)單循環(huán)鏈表La，Lb進(jìn)行的連接操作，是將Lb的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)接到La的尾部。操作時(shí)需要從La的頭指針開(kāi)始找到La的尾結(jié)點(diǎn)，其時(shí)間復(fù)雜性為O(n)。而在循環(huán)鏈表中若采用尾指針La，Lb來(lái)標(biāo)識(shí)，則時(shí)間性能將變?yōu)镺(1)。其連接過(guò)程如下圖所示。圖兩個(gè)循環(huán)鏈表首尾相接進(jìn)行合并

4雙向鏈表

單鏈表只有一個(gè)指向后繼的指針來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系。故從任一結(jié)點(diǎn)開(kāi)始找其后繼結(jié)點(diǎn)很方便，但要找前驅(qū)結(jié)點(diǎn)則比較困難。雙向鏈?zhǔn)绞怯脙蓚€(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。即增加了一個(gè)指向其直接前驅(qū)的指針域，這樣形成的鏈表有兩條不同方向的鏈，前驅(qū)和后繼，因此稱為雙鏈表。在雙鏈表中，根據(jù)已知結(jié)點(diǎn)查找其直接前驅(qū)結(jié)點(diǎn)可以和查找其直接后繼結(jié)點(diǎn)一樣方便。

下面也僅討論帶頭結(jié)點(diǎn)的雙鏈表。

雙向鏈表結(jié)點(diǎn)的定義如下：

typedef

struct

DNode{

ElemTypedata;

struct

DNode*prior;

struct

DNode*next;}Dnode,*DuLinkList;圖雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)圖

在雙向鏈表中也可采用與單鏈表類(lèi)似的方法，用頭指針標(biāo)識(shí)鏈表的開(kāi)頭，也可以帶頭結(jié)點(diǎn)。在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有一個(gè)指向直接前驅(qū)結(jié)點(diǎn)和一個(gè)指向直接后繼結(jié)點(diǎn)的指針。鏈表中第一個(gè)結(jié)點(diǎn)的前驅(qū)指針和最后一個(gè)結(jié)點(diǎn)的后繼指針可以為空，不做任何指向，這是簡(jiǎn)單的雙向鏈表。圖帶頭結(jié)點(diǎn)的雙向鏈表

圖中，如果某指針變量p指向了一個(gè)結(jié)點(diǎn)，則通過(guò)該結(jié)點(diǎn)的指針p可以直接訪問(wèn)它的后繼結(jié)點(diǎn)，即由指針p->next所指向的結(jié)點(diǎn)；也可以直接訪問(wèn)它的前驅(qū)結(jié)點(diǎn)，由指針p->prior指出。這樣在需要查找前驅(qū)的操作中，就不必再?gòu)念^開(kāi)始遍歷整個(gè)鏈表。這種結(jié)構(gòu)極大地簡(jiǎn)化了某些操作。結(jié)點(diǎn)的插入過(guò)程如下圖所雙向鏈表示：

注意：在圖中，關(guān)鍵語(yǔ)句指針操作序列既不是唯一也不是任意的。操作①必須在操作③之前完成，否則*p的前驅(qū)結(jié)點(diǎn)就丟掉了。

在雙向鏈表中找到刪除位置的前一個(gè)結(jié)點(diǎn)，由p指向它，q指向要?jiǎng)h除的結(jié)點(diǎn)。刪除操作如下：①將*p的next域改為指向待刪結(jié)點(diǎn)*q的后繼結(jié)點(diǎn)；②若*q不是指向最后的結(jié)點(diǎn)，則將*q之后結(jié)點(diǎn)的prior域指向*p。

注意：在雙向鏈表中進(jìn)行插入和刪除時(shí)，對(duì)指針的修改需要同時(shí)修改結(jié)點(diǎn)的前驅(qū)指針和后繼指針的指向。

結(jié)點(diǎn)的刪除過(guò)程如下圖所雙向鏈表示：

5循環(huán)雙鏈表與循環(huán)單鏈表一樣，也可以使用循環(huán)雙鏈表。循環(huán)單鏈表和循環(huán)雙鏈表可通過(guò)尾結(jié)點(diǎn)找到頭結(jié)點(diǎn)，也常作為編輯器的數(shù)據(jù)結(jié)構(gòu)，尤其是循環(huán)雙鏈表。

圖

帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的循環(huán)雙鏈表

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)小結(jié)：

克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn),它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來(lái)指示，進(jìn)行數(shù)據(jù)插入或刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：①每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間，當(dāng)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域所占字節(jié)不多時(shí)，指針域所占存儲(chǔ)空間的比重就顯得很大；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。對(duì)任一結(jié)點(diǎn)的操作都要從指針鏈查找到該結(jié)點(diǎn)，這增加了算法的復(fù)雜度。第4節(jié)棧和隊(duì)列第1小節(jié)棧1.棧的定義

棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所示：

進(jìn)行插入和刪除的一端是浮動(dòng)端，通常被稱為棧頂，并用一個(gè)“棧頂指針”指示；而另一端是固定端，通常被稱為棧底。我們經(jīng)常將棧用下圖的形式描述：a1,a2,a3,...,an插入和刪除端圖棧示意圖特性：后進(jìn)先出（LastInFirstOut），簡(jiǎn)稱為L(zhǎng)IFO線性表。舉例1：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)地落在一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。舉例2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時(shí)，將從最上面一層一層地拿取。棧結(jié)構(gòu)的基本操作：（1）初始化棧

（2）入棧

（3）出棧

（4）獲取棧頂元素內(nèi)容

（5）判斷棧是否為空2.棧的抽象數(shù)據(jù)類(lèi)型ADTStack{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}

基本操作：初始化一個(gè)空棧；判棧空，空棧返回True,否則返回False；進(jìn)棧，在棧頂插入一個(gè)元素；出棧，在棧頂刪除一個(gè)元素；取棧頂元素值；置棧為空狀態(tài)；求棧中數(shù)據(jù)元素的個(gè)數(shù)；銷(xiāo)毀棧；

……}ADTStack；3.順序棧類(lèi)定義及運(yùn)算實(shí)現(xiàn)typedef

int

ElemType; constintMAXSIZE=100;classSqstack{private:

ElemType

elem[MAXSIZE];

inttop;public:public:

Sqstack(){top=-1;}

~Sqstack(){}; voidSetEmpty(){top=-1;}

int

IsEmpty(); voidPush(ElemTypee);

ElemTypePop();

ElemType

GetTop(); voidPrintOut();

};①初始化順序棧：使用構(gòu)造函數(shù)實(shí)現(xiàn)Sqstack::

Sqstack(){top=-1;}③入棧：voidSqstack::Push(ElemTypee){if(top==MAXSIZE-1)cout<<“\n棧滿溢出"<<endl;elseelem[++top]=e;}②判斷是否空棧：int

Sqstack::

Sqstack(){if(top==-1)return1;elsereturn0;}④出棧：ElemType

Sqstack::Pop(){

if(top==-1){cout<<“\n棧為空，不能進(jìn)行出棧操作"<<endl;exit(0);//return(0);}returnelem[top--];}⑤獲取棧頂元素：ElemType

Sqstack::GetTop(){if(top==-1){cout<<“\n棧為空，不能進(jìn)行出棧操作"<<endl;exit(0);}returnelem[top];}⑥輸出棧的所有元素：voidSqstack::PrintOut() {cout<<"\nPrintOutData:\n";

if(top==-1)cout<<"\n已是空棧！";else{for(intk=top;k>=0;k--)

cout<<setw(6)<<elem[k];

cout<<endl;}}^若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--“鏈?！?。鏈棧通常用一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表表示。結(jié)點(diǎn)的類(lèi)型定義：typedef

int

ElemType;struct

Lsnode

{ElemTypedata;

Lsnode*next;};將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針4.棧的鏈?zhǔn)酱鎯?chǔ)

top鏈棧類(lèi)定義及運(yùn)算實(shí)現(xiàn)typedef

int

ElemType; classSqstack{private:

Lsnode*top;public:public:

Sqstack(){top=NULL;}

~Sqstack(){};

int

IsEmpty(); voidPush(ElemTypee);

ElemTypePop();

ElemType

GetTop();

voidPrintOut();

};①初始化順序棧：使用構(gòu)造函數(shù)實(shí)現(xiàn)Sqstack::

Sqstack(){top=0;}③入棧：voidSqstack::Push(ElemTypee){Lsnode*p;p=newLsnode;p->data=e;

p->next=top;top=p;

}②判斷是否空棧：int

Sqstack::

Sqstack(){if(top==NULL)return1;elsereturn0;}④出棧：ElemType

Sqstack::Pop(){

Lsnode*p;

ElemTypex;if(top==0)cout<<"Stackisempty!\n";else{x=top->data;p=top;top=top->next;deletep;

returnx;}}⑤獲取棧頂元素：ElemType

Sqstack::GetTop(){if(top==0)cout<<"Stackisempty!\n";returntop->data;}⑥輸出棧的所有元素：voidSqstack::PrintOut() { Lsnode*p; p=top;

cout<<"\nPrintOutData:\n";

if(p==NULL)cout<<"\n已是空棧！";else{while(p!=NULL) {cout<<setw(6)<<p->data;p=p->next;}

cout<<endl;}

}5棧的應(yīng)用舉例【舉例1】將從鍵盤(pán)輸入的字符序列逆置輸出

比如：從鍵盤(pán)上輸入：

tsetasi

sihT算法將輸出：Thisisatest完整算法：

typedefcharStackEntry;voidReverseRead(){

Sqstacks;charch;

cout<<"輸入一串字符:\n"; while((ch=getchar())!='\n')s.Push(ch);while(s.IsEmpty()==0)

cout<<s.Pop();

cout<<endl;}【舉例2】十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制

使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)；重復(fù)此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是所對(duì)應(yīng)的二進(jìn)制數(shù)值。

完整算法：voidDecimal_Binary(){Sqstacks;intdata;cin>>data;while(data){s.Push(data%2);data/=2;}while(!s.IsEmpty())

cout<<s.Pop();cout<<endl;}【舉例3】檢驗(yàn)表達(dá)式中的括號(hào)匹配情況

假設(shè)在一個(gè)算術(shù)表達(dá)式中，可以包含三種括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“[”和“]”和花括號(hào)“{”和“}”，并且這三種括號(hào)可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..?，F(xiàn)在需要設(shè)計(jì)一個(gè)算法，用來(lái)檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用括號(hào)的合法性。

算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間可以嵌套，但不能出現(xiàn)交叉情況。

方法：可以利用一個(gè)棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)時(shí)，從棧中彈出左括號(hào)，檢驗(yàn)匹配情況。在檢驗(yàn)過(guò)程中，若遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)論：（1）當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說(shuō)明到目前為止，右括號(hào)多于左括號(hào)（2）從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類(lèi)型不同，說(shuō)明出現(xiàn)了括號(hào)交叉情況；（3）算術(shù)表達(dá)式輸入完畢，但棧中還有沒(méi)有匹配的左括號(hào)，說(shuō)明左括號(hào)多于右括號(hào)。

第2小節(jié)隊(duì)列1隊(duì)列的定義

隊(duì)列特殊性在于限定插入在線性表的一端進(jìn)行，刪除在線性表的另外一端進(jìn)行。a1a2a3...ai...an-1an刪除端插入端

插入端和刪除端都是浮動(dòng)的。通常我們將插入端稱為隊(duì)尾，用一個(gè)“隊(duì)尾指針”指示；而刪除端被稱為隊(duì)頭，用一個(gè)“隊(duì)頭指針”指示。結(jié)論：先進(jìn)先出（FirstInFirstOut），簡(jiǎn)稱為FIFO線性表。

舉例：在Windows這類(lèi)多任務(wù)的操作系統(tǒng)環(huán)境中，每個(gè)應(yīng)用程序響應(yīng)一系列的“消息”，像用戶點(diǎn)擊鼠標(biāo)；拖動(dòng)窗口這些操作都會(huì)導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個(gè)應(yīng)用程序創(chuàng)建一個(gè)隊(duì)列，用來(lái)存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過(guò)程就是不斷地從隊(duì)列中讀取消息，并依次給予響應(yīng)。隊(duì)列結(jié)構(gòu)的基本操作：（1）初始化隊(duì)列（2）入隊(duì)（3）出隊(duì)（4）獲取隊(duì)頭元素內(nèi)容（5）判斷隊(duì)列是否為空2.隊(duì)列的抽象數(shù)據(jù)類(lèi)型ADTQueue{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n

基本操作：初始化一個(gè)空隊(duì)列；判隊(duì)空入隊(duì)，在隊(duì)尾插入一個(gè)元素；出隊(duì)，在隊(duì)頭刪除一個(gè)元素；取隊(duì)頭數(shù)據(jù)元素值；置隊(duì)列為空狀態(tài)；銷(xiāo)毀隊(duì)列；

……}ADTQueue;2隊(duì)列的順序存儲(chǔ)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：?jiǎn)栴}1：當(dāng)隊(duì)空時(shí)，隊(duì)頭和隊(duì)尾指針都為-1，隊(duì)列將處于下圖所示的狀態(tài)：此時(shí)若進(jìn)行入隊(duì)操作，就需要讓隊(duì)頭和隊(duì)尾指針都增1，再將新數(shù)據(jù)元素放入該位置。也就是說(shuō)，這樣設(shè)置隊(duì)頭、隊(duì)尾指針位置，在進(jìn)行入隊(duì)操作時(shí)，空隊(duì)與非空隊(duì)狀態(tài)所需要執(zhí)行的操作不完全一樣。解決方法：在算法中，需要對(duì)這兩種情況加以區(qū)分，這勢(shì)必增加了算法的復(fù)雜性。因此，人們?cè)O(shè)想了一種解決方法，即讓隊(duì)頭指針指向隊(duì)列真正隊(duì)頭元素的前一個(gè)位置，如下圖所示。

問(wèn)題2：由于順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間屬于靜態(tài)分配，所以，在添加數(shù)據(jù)元素時(shí)，可能會(huì)出現(xiàn)沒(méi)有剩余單元的情況。如下圖出現(xiàn)

“假溢出”現(xiàn)象。

解決方法：將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接，形成一個(gè)環(huán)狀---“循環(huán)隊(duì)列”。a8a7a6a576543210rearfront①循環(huán)的效果的實(shí)現(xiàn)

假設(shè)為隊(duì)列開(kāi)辟的數(shù)組單元數(shù)目為MAX_QUEUE，在C語(yǔ)言中，它的下標(biāo)在0~MAX_QUEUE-1之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算實(shí)現(xiàn)。如下所示：

front=(front+1)%MAX_QUEUE；

rear=(rear+1)%MAX_QUEUE；當(dāng)front或rear為MAXQUEUE-1時(shí)，上述兩個(gè)公式計(jì)算的結(jié)果就為0。這樣，就使得指針自動(dòng)由后面轉(zhuǎn)到前面，形成循環(huán)的效果。

a7a876543210rearfront76543210rearfront(a)(b)隊(duì)列變?yōu)榭?，?duì)頭和隊(duì)尾指針相等。②隊(duì)空和隊(duì)滿的標(biāo)志問(wèn)題：rearfrontrearfronta6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210(a)(b)隊(duì)列變?yōu)闈M，隊(duì)頭和隊(duì)尾指針也相等。解決隊(duì)列變滿方法：假設(shè)隊(duì)列只剩下一個(gè)單元時(shí)認(rèn)為隊(duì)滿。順序隊(duì)列類(lèi)定義及運(yùn)算實(shí)現(xiàn)typedef

int

ElemType; constintMAXSIZE=4;classSqueue{private:

ElemType

data[MAXSIZE];

int

front,rear;public:

Squeue(){front=-1;rear=-1;} ~Squeue(){};

int

Empty(){if(front==rear)return1;elsereturn0;}voidDisplay(); voidEnQueue(ElemTypex);

ElemType

DelQueue();

ElemType

GetFront();};①初始化順序隊(duì)列：使用構(gòu)造函數(shù)實(shí)現(xiàn)Squeue

::

Squeue(){front=-1;rear=-1;}③入隊(duì)：voidSqueue::EnQueue(ElemTypex){if((rear+1)%MAXSIZE==front)cout<<“隊(duì)滿"<<endl;else{rear=(rear+1)%MAXSIZE;data[rear]=x;}}

②判斷是否空隊(duì)列：int

Squeue

::

Empty(){if(front==rear)return1;elsereturn0;}④出隊(duì)：ElemType

Squeue::DelQueue(){ if(Empty()){cout<<“對(duì)空"<<endl;exit(0);}else{front=(front+1)%MAXSIZE;returndata[front];}}⑤獲取對(duì)頭元素：ElemType

Squeue::GetFront(){if(Empty()){cout<<"對(duì)空"<<endl;exit(0);}elsereturndata[(front+1)%MAXSIZE];}⑥輸出隊(duì)列的所有元素：voidSqueue::Display(){

inti; if(Empty()){cout<<"對(duì)空

"<<endl;return;}

for(i=(front+1)%MAXSIZE;

i!=(rear+1)%MAXSIZE;

i=(i+1)%MAXSIZE)

cout<<setw(6)<<data[i];

cout<<endl;}

在用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示隊(duì)列時(shí)，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：^frontrearstruct

quenode{ElemTypedata;

quenode*next; 域

};

鏈?zhǔn)疥?duì)列類(lèi)定義及運(yùn)算實(shí)現(xiàn)classSqueue{private:

quenode*front,*rear;public:

Squeue(){front=newquenode;rear=front;} ~Squeue(){deletefront;}

int

Empty(){if(front==rear)return1;elsereturn0;}voidDisplay(); voidEnQueue(ElemTypex);

ElemType

DelQueue();

ElemType

GetFront();};①初始化鏈?zhǔn)疥?duì)列：使用構(gòu)造函數(shù)實(shí)現(xiàn)Squeue

::

Squeue(){front=newquenode;

rear=front;

}③入隊(duì)：voidSqueue::EnQueue(ElemTypex){

quenode*s=newquenode;s->data=x;s->next=NULL;

rear->next=s；rear=s;}

②判斷是否空隊(duì)列：int

Squeue

::

Empty(){if(front==rear)