數(shù)據(jù)結(jié)構(gòu)-復(fù)習(xí)資料

第0章C++極速入門

1.文件后綴名

C++文件的后綴名有許多種，較為常見的是.cpp;頭文件的后綴名也

有很多種，較為常見的是.h。

2.#include

對于#include,這相當(dāng)于Java中的Import作用是引入需要的庫文件。

＜iostream＞中包含了標(biāo)準(zhǔn)輸入輸出流，我們常用的cin和cout函數(shù)以

及＞＞和"運算符都在其中。〈iterator〉是一個迭代器庫，使用

istreamjterator或者ostream_iterator都要把他包含進(jìn)來。＜cstdlib＞提

供了一些函數(shù)和符號常量，如NULLo

3.#include后面接v＞還是',?

對于標(biāo)準(zhǔn)庫，其后應(yīng)該接＜＞，如＜iostream＞;對于自定義的頭文件，

則應(yīng)該用‘’，這時候使用的是相對路徑。

4.什么是聲明？什么是定義？

簡單的來講：聲明就是說明這個類中有什么類型，什么名字的變量

和什么樣的成員函數(shù)（當(dāng)然必須指明函數(shù)的返回值，函數(shù)名和形參

列表），卻不用對變量初始化或者具體寫出成員函數(shù)的實現(xiàn)代碼；而

變量的初始化或者函數(shù)的具體代碼實現(xiàn)的過程叫做定義。

5.C++中聲明和定義類通常的做法

C++是一種面向?qū)ο蟮木幊陶Z言，因此不可避免的要聲明和定義類，

我們在java中總是在把聲明和定義放在一起做，比如剛聲明了一個

變量就給它初始化，或者剛聲明了一個方法緊接著就在后面跟上

{),并在其中給出代碼實現(xiàn)來定義。雖然C++中也可以這樣做，但

通常的做法是把類的聲明放入頭文件中，而把類的定義放入相對應(yīng)

的.cpp中。

6.'作用域運算符

::表示：：右邊的操作數(shù)可以在::左邊的作用域上找到。例如：A::

function()表示這個function()是類A的。

7.命名空間

編碼中，我們總是使用如std::cout這樣的形式會使代碼冗余，如

果一個函數(shù)中總是調(diào)用一個命名空間中的其他函數(shù)，我們可以使用

using聲明來簡化代碼，語法：usingnamespacestd;這樣我們之

后就可以直接調(diào)用cout而省去std::To

8.Const關(guān)鍵字

Const關(guān)鍵字用來使一個變量不可被更改，常用于常量的定義。

9.引用

引用是一個對象的別名，是一種復(fù)合類型，通過在變量名前添加&'

符號來定義，操作引用就是操作對象本身，如inta=10;int&b=a;

b++;此時a的值已經(jīng)變?yōu)榱?1。與指針不同，指針定義后可以變換

所指的對象，但引用一經(jīng)定義，則不能改變與之相關(guān)聯(lián)的對象。

10.C++中的函數(shù)傳參方式

C++中的函數(shù)，有三種參數(shù)傳遞方式，傳值，傳引用，傳指針。傳

值時，會在函數(shù)執(zhí)行時為形參分配內(nèi)存，等待函數(shù)執(zhí)行完畢后，把

形參的值return出去賦給指定的變量，再將形參銷毀，而傳引用時，

函數(shù)會直接操作引用，也就是直接操作引用所綁定的對象，不會為

形參實際分配空間，函數(shù)執(zhí)行完以后也不用再把值賦回去，因為操

作的就是變量本身，效率很高。而傳指針，類似于傳值，會在函數(shù)

內(nèi)部產(chǎn)生一個形參作為實參的副本。操作指針形參時，真正的那個

指針的值并沒有發(fā)生變化，你要是不把形參指針的值再賦回去，相

當(dāng)于沒有操作。

11.操作符的重載

比之于Java只能重載函數(shù)，C++中可以重載操作符顯得更為靈活，

重載操作符的語法為：返回值類型operator關(guān)鍵字要重載的運

算符（形參列表），對于現(xiàn)在的我們，認(rèn)識即可。抱佛腳不要求我們

會使用。

12.析構(gòu)函數(shù)

與Java不同，C++采用手動內(nèi)存管理，因此我們需要手動回收動態(tài)

分配出去的內(nèi)存，因此對于C++類來說，它們還有一類特殊的函數(shù)，

叫做析構(gòu)函數(shù)，在我們使用delete關(guān)鍵字刪除一個對象（確切的說，

是刪除指向這個對象的指針時）時，析構(gòu)函數(shù)會自動被調(diào)用，但并

不是所有時候都需要顯式的編寫析構(gòu)函數(shù)，只有當(dāng)對象在其生命周

期內(nèi)或構(gòu)造函數(shù)中獲取資源時，我們才需編寫以釋放。

13.模板類

我敢保證，你總是在PPT或者其他地方看見這么一行代碼：

template<classType>

這叫啥，這叫模板。模板有兩種，一個叫模板函數(shù)，一個叫模板

類，先說模板函數(shù)，如果有時候你需要定義一大堆的重載函數(shù)，而

這些函數(shù)僅僅只有形參列表中的參數(shù)類型不一樣（就是除過類型，

形參個數(shù)一樣，甚至連變量名都一樣。）,那此時就有一個簡單的辦

法：只寫一個函數(shù)，而使用一個暫不指出的類型把這些類型都替換

掉，等需要用的時候再確定，給啥類型，函數(shù)中用Type標(biāo)記的類型

就是啥，非常靈活。這樣的想法，用于實現(xiàn)函數(shù)，就叫函數(shù)模板，

用于實現(xiàn)類，就叫類模板。

那咋在需要的時候指定類型呢？在函數(shù)模板中，編譯器會推斷出

到底是在是用什么類型，我們直接給出實參就可以。而使用類模板

時，必須為模板形參顯式的指定實參。

語法：類名v要用的類型〉對象名。

接下來，我將告訴你C++極速入門的至關(guān)重要的一句話！你若遵循，技術(shù)必定

突飛猛進(jìn)！請注意，這個真諦是：

你看了上面的解說，最好動手寫上一兩個C++程序，哪怕不比helloworld

復(fù)雜多少都行，否則的話，你看了上面，基本等于白看！

第1章概論

1.、數(shù)據(jù)結(jié)構(gòu)

要想方便的使用數(shù)據(jù)，你就需要把他們組織起來，特別是有大量的數(shù)據(jù)

的時候要用的時候，你不得不組織。所以，拋開那些嚴(yán)謹(jǐn)?shù)亩x，通俗的來

講：組織數(shù)據(jù)的方法或者數(shù)據(jù)被組織起來的形式就是數(shù)據(jù)結(jié)構(gòu)。

2.分類

數(shù)據(jù)結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)也稱為線性表，這

種結(jié)構(gòu)中的所有數(shù)據(jù)都按某種順序排列在一個序列中。而線性表又分為順序

表和鏈表。非線性結(jié)構(gòu)中各個元素不再保持在一個線性序列中，每個數(shù)據(jù)元

素可能與零或多個其他數(shù)據(jù)元素發(fā)生關(guān)系，根據(jù)關(guān)系不同又分為層次結(jié)構(gòu)和

群結(jié)構(gòu)，層次結(jié)構(gòu)如樹，群結(jié)構(gòu)如圖。

3.ADT

Abstractdatatype即抽象數(shù)據(jù)類型，我們要使用一個非內(nèi)置的數(shù)據(jù)

類型時，就需要先對它進(jìn)行設(shè)計，進(jìn)行設(shè)計的時候應(yīng)該關(guān)心這個數(shù)據(jù)類型應(yīng)

該包含那些信息，或者支持那些操作，而不是一開始就關(guān)注這個數(shù)據(jù)類型該

如何實現(xiàn)，所以，好的做法是把數(shù)據(jù)類型抽象一下，把聲明和實現(xiàn)分開，設(shè)

計的時候考慮聲明，用的時候在去實現(xiàn)。

4.算法性能分析和度■

算法的復(fù)雜性度量屬于事前估計，它可以分為時間復(fù)雜度和空間復(fù)雜度，

常采用大。表示法來描述。

第2章數(shù)組

1.簡介

數(shù)組是具有相同類型的若干變量的有序組織形式。通常使用一塊連

續(xù)的內(nèi)存。數(shù)組是線性結(jié)構(gòu)，每個元素都有唯一的前驅(qū)和后繼（第一個

和最后一個元素除外），元素的個數(shù)和數(shù)組的起始地址必須在分配內(nèi)存的

時候就指定。數(shù)組中的元素可以被任意的直接訪問，這個隨機(jī)訪問是通

過數(shù)組的下標(biāo)來實現(xiàn)的。

2.一維數(shù)蛆元素地址推算公式

設(shè)a為該數(shù)組的起始地址，數(shù)組中每個元素要用I的存儲空間，則：

Addr[i]=a+i*I

3.順序表

定義：把線性表中所有的表項按照邏輯順序依次存儲到一塊指定地

址的連續(xù)的存儲空間。顯然數(shù)組是順序表。順序表類至少應(yīng)該支持一下

操作：

（1）插入元素（2）移除元素（3）查找某元素的先驅(qū)（4）查找某

元素的后繼（5）判斷是否為空（6）判斷是否為滿（7）按索引得到

某一元素。

4.順序表的性能分析

主要是分析搜索，插入和刪除運算的實現(xiàn)代碼的時間復(fù)雜度。搜索算法

中，設(shè)各個表項的搜索概率為Pi,找到該表項時數(shù)據(jù)比較次數(shù)為Ci

搜索的平均比較次數(shù)為ACN（averagecomparingnumber）=錯誤！

未找到引用源。，若搜索表項的各項可能性相同，則ACN=錯誤!未找到引用

源。=錯誤!未找到引用源。（1+2+……+n）=錯誤!未找到引用源。

分析順序表的插入和刪除的時間代價主要看循環(huán)內(nèi)的數(shù)據(jù)移動次數(shù)AMN

(averagemovingnumber)

插入：AMN=錯誤!未找到引用源。

若個表項插入概率相等，AMN=錯誤!未找到引用源。

刪除：AMN=錯誤!未找到引用源。

若個表項刪除概率相等，AMN=錯誤!未找到引用源。

5.三角矩陣的存儲

對于一個n*n對稱方陣來說，可以只存儲它的上三角或者下三角部分來

節(jié)省空間，而其上（下）三角矩陣的元素個數(shù)為錯誤!未找到引用源。

可以用一個一維數(shù)組來存放這些元素:

aOOa10a11a20a21a22a30a31a32a33

Loc(i,j)=k;

i(i+1)/2+ji>j

k=y

j(j+1)/2+ii<j

6.對角矩陣的存儲

aooana02000

aio811ai2ai300

3203218223233240

0831832333834835

00842343243345

000853354355J

a11a12a21a22a23a32a33a34.......an(n-1)ann

設(shè)第i(i*1,n)行非零元素的個數(shù)為m,則d=錯誤!未找到引用源。

則帶狀矩陣中，非零元素的個數(shù)為:(2d+1)n-(1+d)d

7.稀疏矩陣

使用一個三元組只存儲矩陣中的非零元素，可以實現(xiàn)對稀疏矩陣的壓

縮，三元組：〈行，列，值〉

對于一個稀疏矩陣，如果要對其進(jìn)行轉(zhuǎn)置，應(yīng)當(dāng)考慮在其壓縮狀態(tài)下

直接對其進(jìn)行轉(zhuǎn)置，最簡單的方法是把三元表內(nèi)的row與col呼喚后，再

對新的三元表進(jìn)行row主序排序。

這里講一種方法：假設(shè)稀疏矩陣A有Cols列，則對這個三元組進(jìn)行

Cols次掃描，第k次掃描是在三元組表中尋找列號為k的所有三元組，意

味著此三元組應(yīng)該放在新表中的第k行，此時交換該三元組的row和col,

再連同value一同存入新的三元表中。

為了提高效率，還有一種快速轉(zhuǎn)置的方法，通過一如兩個輔助數(shù)組來

提高效率rowSize□來記錄每一列有多少個非零元素，rowStart□來記錄每

行第一個三元組應(yīng)該存放在新表中的什么位置

8.String類的抽象數(shù)據(jù)結(jié)構(gòu)

由零個或多個字符的順序排列所組成的數(shù)據(jù)結(jié)構(gòu)，基本組成元素是單

個字符，

soS1S2S3S4.................Sn-1

一個字符串的連續(xù)字符子集叫做子字符串，空字符串不包含任何字

符。

實現(xiàn)可增長字符串有三種方法:（1）創(chuàng)建一個字符緩沖區(qū)并且只初始

化這個區(qū)域的一部分，剩下的緩沖區(qū)以后使用。（2）創(chuàng)建一個新的第三字

符串，其容量是另兩個字符串的容量之和，并把這兩個字符串的內(nèi)容拷貝

進(jìn)來。（3）創(chuàng)建一個字符串鏈表，而不是數(shù)組，這種方法是真正地?zé)o限制

方法，但是需要維持鏈表

9.字符串模式匹配

老師PPT中提到的有兩種模式，一種是樸素匹配，另外一種是KMP

匹配。KMP匹配算法因為無回溯，效率較高。（PPT86頁）

10.STL中的string

STL中已經(jīng)給我們提供了string類供我們使用，只要#include〈string〉

就可以使用了，此類包含了初始化，串接，獲取長度，輸入輸出等基本操

作的支持。string類提供了字符串高級處理函數(shù)的集合。

11.STL中的vector

同樣。只要#include〈vector〉就可以使用STL中的vector了.vector

提供了一個安全的對數(shù)組的替代，因為它提供成員函數(shù)來實現(xiàn)那些更高級

的操作。實際上，可以簡單的理解vector為一個大小可變的數(shù)組。

vector引用的聲明語法：

vector<type>v;

其中type叫做泛型，它制定了vector中存儲的數(shù)據(jù)類型。我們可以

用vector聲明一個整形矩陣：

vector<vector<int>>matrix;

vector有兩個構(gòu)造函數(shù)，vector<type>v構(gòu)造了一個空vector,而

K

vector<int>v(5,42)構(gòu)造了一^1包含5個值為42的元素的vectoro

vector支持對項的隨機(jī)訪問，可以使用如下兩種方式:v口或者v.at(),

并且可以通過vector.push_back()來向vector中添加新項

12.STL中的deque

同樣。只要#include〈deque〉就可以使用STL中的deque了.deque

叫做雙向隊列，類似于vector,但支持雙向操作，deque通過.push_front

()和.pop_front()提供了在表的兩端對元素進(jìn)行高效插入和刪除的操

作。deque占用連續(xù)的存儲空間，并且在所存儲元素的頭和尾部又保留了額

外的存儲空間。

13.習(xí)題:

1.Westorea4x4symmetric(對稱)matrixAintoanarrayB

(indexstartfrom0)withrowmajororderStorethelowertriangle

only,theindexofelementa[2][3]inBis4.

把一個4x4的對稱矩陣A存儲到一個下標(biāo)從0開始的數(shù)組B中，

使用行主序只存儲它的下三角部分，那么a23在數(shù)組B中的索引

是多少？

a11a12a13a14因為是對稱矩陣，

a21a22a23a24所以a23=a32,a32

a31a32a33a34是數(shù)組里的第5個元素，

a41a42a43a44因此下標(biāo)是40

2.()Theworst-timeforremovinganelementfroma

sequencelist(Big-Oh)isB

a.0(1)b.0(n)c.0(n2)d.0(n3)

從線性表中移除一個元素，最壞情況下的時間復(fù)雜度是多

少？

考慮最壞情況：移除順序表的第一個元素，則后面所有元素

都要向前移一位這是個線性的時間花費，因此時間復(fù)雜度為0(n)

3.Wecanuse3vectortypetostorevalueandloactionof

non-zeroelementsinasparsematrix.

在稀疏矩陣中，我們可以使用一個三元vector來存儲非零元

的值和上^。三元組中一個表項有三個變量，分別是

row,col,value。

第3章鏈表

1.簡介

考慮到數(shù)組的長度固定不變，很可能造成內(nèi)存浪費，也很可能不夠用，

不夠用時擴(kuò)展的開銷很大，在數(shù)組中移除或者插入項的時間是線性的等等缺

點，鏈表誕生了。

鏈表并不是用連續(xù)的存儲空間，而是通過指針指向下一個節(jié)點的地址來

實現(xiàn)邏輯上的連續(xù)，這樣無論在鏈表的何處插入或者刪除一項，所花費的時

間都是恒定的，而且鏈表的大小是無限制的（只要內(nèi)存夠卜

鏈表的一個節(jié)點由它的數(shù)據(jù)項和指針組成，最后一個節(jié)點的指針為空指

針，鏈表會有一個頭結(jié)點，這個頭結(jié)點僅僅是一個指向鏈表第一個節(jié)點的指

針，使用頭結(jié)點的目的是簡化鏈表操作的實現(xiàn)，統(tǒng)一空表和非空表的運算。

我們可以通過頭結(jié)點訪問整個鏈表。

鏈表的缺點是大多數(shù)方法需要聲明，數(shù)組對數(shù)據(jù)元素的訪問速度是鏈表

不可比擬的，因為數(shù)組可以做到隨機(jī)訪問，但鏈表訪問中部元素或者后部元

素（對單鏈表來說）會慢的多，原因是鏈表只能通過上一項找到下一項。

2.單鏈表的插入和刪除元素

插入：①找到第i-1個節(jié)點，并判斷這個插入位置是否合法。

②分配內(nèi)存給新的節(jié)點，并檢查內(nèi)存分配是否成功。

③讓新節(jié)點的指針指向第i個節(jié)點

④使第i-1個節(jié)點的指針指向新節(jié)點。

刪除：①找到第i-1個節(jié)點，并判斷要刪除的位置是否合法。

②使用一個指針指向?qū)⒈粍h除的節(jié)點。

③讓第i-1節(jié)點的指針指向第第i+1個節(jié)點。

?delete掉剛才指向那個指向被刪除節(jié)點的指針。

3.循環(huán)性表

考慮到單鏈表的缺點，如單鏈表訪問當(dāng)前節(jié)點的先驅(qū)難等。因素，

在單鏈表的基礎(chǔ)上，又出現(xiàn)了循環(huán)鏈表和雙向鏈表。

循環(huán)鏈表的尾節(jié)點的指針域指向頭指針，大多數(shù)時候，為了在頭部插

入方便，循環(huán)鏈表不定義頭指針而是定義尾指針rearo

附加頭結(jié)點型循環(huán)鏈表

使用尾指針rear的循環(huán)鏈表

循環(huán)鏈表的應(yīng)用：約瑟夫問題。

4.雙向鋅表

雙向鏈表的誕生是為了解決在鏈表中直接訪問前驅(qū)的問題，雙向鏈

表中每個節(jié)點都有兩個指針，一個指針指向前驅(qū)結(jié)點，一個指針指向后

繼節(jié)點。一個雙向鏈表結(jié)構(gòu)是這樣的：

First

Headinkdatarlink

item

P->llinkPP->rlink

容易發(fā)現(xiàn)：

p==p->ILink->rLink==p->rLink->ILink

刪除節(jié)點的關(guān)鍵代碼：

current->rLink->ILink=current->ILink;

current->ILink->rLink=current->rLink;

在current前驅(qū)方向插入節(jié)點的關(guān)鍵代碼:

newnode->ILink=current->ILink;

newnode->rLink=current;

current->ILink=newnode;

newnode->ILink->rLink=newnode;

5.靜態(tài)性表

如果我們不是動態(tài)的為每一個節(jié)點分配內(nèi)存，而是先分配好一個數(shù)

組（每項含有兩個值，一個存值，一個存指針），并把數(shù)組的下標(biāo)看做地

址，那么我們可以得到一個叫做靜態(tài)鏈表的東西。如圖：

地址（下標(biāo)）數(shù)據(jù)指針

0NULL7

1周4

2錢5

3王NULL

46

5孫8

6鄭3

7趙2

8李1

6.習(xí)題：

1.Whichofthefollowingistrue

①wecanrandomaccessanelementinarray.

②wecanrandomaccessanelementinlinkedlist.

(3)wecantrandomaccessbothinarrayandlinkedlist.

@allaboveiswrong

答案：①。數(shù)組時可以通過下標(biāo)做到隨機(jī)訪問的，也就是對其中的任意

一個元素的訪問，不需要依賴于對其他元素的訪問，但是鏈表是做不到

這一點的，除過頭結(jié)點，要想訪問鏈表中的任何一個元素，必須先訪問

它的先驅(qū)。

2.Writeafunctiontoinsertanelementintoasinglelinkedlistwith

headernode.

解題思路：PPT上有這個方法的代碼，這里就不占篇幅了。

第4章棧和隊列

“食堂打飯要是后來先買,那一定會非常有意思”

1.簡介

?？梢远x為只允許在表的末端進(jìn)行插入和刪除的線性表，允許插入和刪

除的一端叫做棧頂，另一端則叫做棧底，當(dāng)棧中沒有數(shù)據(jù)元素時，棧成為空

棧。棧也叫后進(jìn)先出的線性表。棧應(yīng)該提供以下操作：(1)檢查是否為空;(2)

檢查是否為滿(3)返回棧頂?shù)臄?shù)據(jù)元素(4)將一個新的數(shù)據(jù)元素壓入棧中

(5)將棧頂?shù)臄?shù)據(jù)元素彈出(6)展示棧中所有的數(shù)據(jù)元素。

2.棧的實現(xiàn)

任何列表的實現(xiàn)都可以用來實現(xiàn)棧：例如數(shù)組或者鏈表，基于數(shù)組表示的

棧叫做順序棧，基于鏈表表示的棧叫做鏈?zhǔn)綏?/p>

3.進(jìn)棧

進(jìn)棧時，首先要判斷站內(nèi)是否還有剩余空間，對于一個棧來說，棧的最后

允許存儲的位置是MaxSize-1,如果棧頂指針已經(jīng)top==MaxSize-1,則說明所

有位置均已使用，棧已滿，這時若再有新的數(shù)據(jù)元素進(jìn)棧，則會發(fā)生溢出，程

序會轉(zhuǎn)入溢出處理；若topvMaxSize-1,則先讓棧頂指針加1,指到可加以加

入新元素的位置，再按棧頂所指到的位置將新元素插入。

4.出棧

如果出棧時發(fā)現(xiàn)棧是空棧，即top=-1,則退棧操作將執(zhí)行空棧處理，若當(dāng)

前top>=0,則將棧頂元素彈出，并將棧頂指針減1O讀取棧頂元素值的函數(shù)

getTop(T&)與退棧函數(shù)Pop(T&)的區(qū)別在于：前者沒有改變棧頂指針的

值，后者改變了棧頂指針的值。

5.雙向棧

程序中往往同時存在幾個棧，而各個棧所需的運行空間是動態(tài)變化的，

有的棧膨脹的快，有的?？赡苓€會有許多空閑空間，因此給幾個棧分配同樣

大小的空間并不明智，因此產(chǎn)生了多個棧共享?？臻g的思想。這里只介紹雙

向棧。

0maxSize-1

tttTt

b[Q]HO]Hl]b⑴

雙向棧定義了一個足夠大的?？臻g,,空間的兩端是兩個棧的棧底，兩個棧

的棧頂都向中間延伸，直至兩個棧頂相遇時，才認(rèn)為棧發(fā)生了溢出，但由于

這里的棧是使用數(shù)組表示的，那么在棧頂壓入一個數(shù)據(jù)實際上是在數(shù)組中的

某個位置插入了數(shù)據(jù)，當(dāng)數(shù)據(jù)量很大時，這種插入操作的開銷非常大，因此

下面介紹鏈?zhǔn)綏！?/p>

6.鏈?zhǔn)綏?/p>

采用鏈?zhǔn)綏肀硎疽粋€棧，便于節(jié)點的插入與刪除，鏈?zhǔn)綏５臈ｍ斣诒?/p>

頭，新節(jié)點的插入和棧頂節(jié)點的刪除表頭進(jìn)行。

7.棧的應(yīng)用

(1)括號匹配(2)表達(dá)式計算

8.隊列簡介

隊列是另一種限定存取位置的線性表。它只允許在表的一端插入，在另

一端刪除，允許插入的一端叫做隊尾，允許刪除的一端叫做隊頭。隊列具有

先進(jìn)先出的特性。

隊列的存儲表示也有兩種方式；一種是基于數(shù)組的存儲表示，叫做順序

隊列，另一種是基于鏈表的存儲表示，叫做鏈?zhǔn)疥犃小?/p>

9.順序隊列

利用一個一維數(shù)組作為隊列的存儲結(jié)構(gòu)，并設(shè)兩個指針front和rear。

在隊列剛剛建立的時候，對隊列進(jìn)行初始化front=rear=0，每當(dāng)加入一個新

元素的時候，先將元素添加到rear所指的地方，然后再讓rear指針進(jìn)1。

當(dāng)要退出隊頭元素的時候，先記錄此元素的值，然后再將front指針進(jìn)1O然

后返回記錄下來的。

由于剛才所講的隊列可能會產(chǎn)生一種假溢出的問題，SPfront前面還有

空間可用。所以設(shè)計了循環(huán)隊列來彌補(bǔ)這一缺陷。

循環(huán)隊列把數(shù)組的前端和后端連起來，形成一個環(huán)形的表，front和rear

指針進(jìn)到MaxSize-1后，再進(jìn)1就回到了0。這可以用取余算法來實現(xiàn)。

隊頭指針進(jìn)1:front=(front+1)%MaxSize;

隊尾指針進(jìn)1:rear=(rear+1)%MaxSize;

可以用front==rear來判斷隊列是否為空，用(rear+1)%MaxSize==

來判斷隊列是否為滿，即rear若指到front的前一個位置，隊列即滿，這實

際上空出了一個位置用來區(qū)分滿與空輻環(huán)隊列最多只能放下MaxSize-1個

兀素。

10.鏈?zhǔn)疥犃?/p>

隊列的隊頭指針指向單鏈表的第一個節(jié)點，隊尾指針指向單鏈表的最后

一個節(jié)點。用單鏈表表示的鏈?zhǔn)疥犃刑貏e適合與數(shù)據(jù)元素變動比較大的情

況，而且不存在隊列滿而溢出的情況。

11.習(xí)題

1.(D)lnacircularqueuewecandistinguish(區(qū)分)emptyqueues

fromfullqueuesby.

Ausingagapinthearray

Bincrementingqueuepositionsby2insteadof1

Ckeepingacountofthenumberofelements

Daandc

A在數(shù)組中使用一個空元素作為間隔

B增加兩個隊列位置而不是一個

C保持對元素的個數(shù)的計數(shù)

Da和c

A正確，因為循環(huán)隊列的普遍做法是當(dāng)rear指向front的前一個位置時，

就認(rèn)為隊列滿了，因此會空出一個位置，故正確。B我不明白他說的啥意思

C顯然正確，元素個數(shù)達(dá)到所能存儲的最大值就滿了么，個數(shù)為零就是空的

么，因此選D

2.Astackisalistwhereremovalandadditionoccuratthe

sameend.FrequentlyknownaLIFO(Last-In-First-Out)structure.

添加和移除都發(fā)生在列表的同一端，并且是后進(jìn)先出的結(jié)構(gòu)，這顯然是

棧么。

3.Considerthefollowingfunctiontobalancesymbolsstoredinstring

expthatincludesparentheses(圓括號)andnumbers.Pleasefillinblank,

include<stack>

usingnamespacestd;

intmatching(string&exp){

//expisapointertoastringtocheck

intstate=1,i=0;

chare;

stack<char>s;

while(i<exp.length()&&state)

switch(exp[i]){

case

s.pushCQ;

i++；

break;

case

if(!s.empty()){

s.pop();i++;}

else

state=0;//anerroroccurs

break;

default:

i++;break;

}//endofwhile

if(s.empty()&&state)return1;

elsereturn0;

第5章遞歸(Recursion)

1.什么是遞歸？為什么需要遞歸？

Sometimes,thebestwaytosolveaproblemisbysolvingasmaller

versionoftheexactsameproblemfirst

有時候，解決一個問題的最佳途徑是先著手解決這個問題的小規(guī)模情形。

Recursionisatechniquethatsolvesaproblembysolvingasmaller

problemofthesametype

遞歸是一種技巧，它通過解決同類型的小問題來完成問題的解決。

2.遞歸函數(shù)

來看一個遞歸函數(shù)的例子：

IntFunction(intn){

If(n==1||n==2)return1;//(1)

ReturnFunction(n-1)+Function(n-2);//(2)

)

<1>該函數(shù)只接收一個參數(shù)n,返回Fibonacci數(shù)列第n項的值。

<2>該函數(shù)用到了遞歸的設(shè)計，因為求Fibonacci數(shù)列第n項的值這個

問題，可以分割為同類型的子問題：求其第n-1項和第n-2項的值，并

求和。

<3>其中⑴被稱為basecase,是因為它很容易被計算。(2)被稱為

general(recursive)case,它類似于一種遞推。

<4>每種遞歸算法至少要各有一^,bbasecase和generalcaseo

<5>如果沒有basecase,遞歸函數(shù)將導(dǎo)致棧溢出(stackoverflow)o

3.遞歸與迭代(Iteration)

<1>Iterationcanbeusedinplaceofrecursion

迭代可以用來代替遞歸

Aniterativealgorithmusesaloopingstructure

一個迭代算法使用循環(huán)結(jié)構(gòu)。

Arecursivealgorithmusesabranchingstructure

一個遞歸算法使用分支結(jié)構(gòu)。

<2>Recursivesolutionsareoftenlessefficient,intermsofbothtime

andspace,thaniterativesolutions

比起迭代，遞歸通常都是低效率的，在時間和空間上都是。

<3>Recursioncansimplifythesolutionofaproblem,oftenresultingin

shorter,moreeasilyunderstoodsourcecode

遞歸可以簡化一個問題的解決，通常都會帶來更簡短、更通俗易懂

的源代碼。

<4>(Nearly)everyrecursivelydefinedproblemcanbesolved

iteratively,iterativeoptimizationcanbeimplementedafterrecursive

design

(幾乎)每一個以遞歸方式定義的問題都可以用迭代方式解決，在遞歸

設(shè)計之后可以實現(xiàn)迭代優(yōu)化。

4.遞歸的應(yīng)用

<1>分治法(divideandconquer)

Eg:歸并排序，快速排序。

<2>回溯法(backtracking)

Eg:求解八皇后問題。

5.遞歸的算法復(fù)雜度分析

<1>T(n)=C1*T(n/2)+C2*n型(C1、C2均為常數(shù))

每次遞歸數(shù)據(jù)規(guī)模折半，所以是logn趟每趟又有n次(只看數(shù)量級，

所以C2*n等價于n),所以此類型遞歸的算法復(fù)雜度為O(nlogn)。

<2>T(n)=C1*T(n-1)+C2*n型(C1、C2均為常數(shù))

每次遞歸數(shù)據(jù)規(guī)模減一，所以是n趟，每趟又有n次(只看數(shù)量級，

所以C2*n等價于n),所以此類型遞歸的算法復(fù)雜度為0(M2)。

6.習(xí)題

<1>T(n)=2T(n/2)+cnT(n)=T(n-1)+cn

T(n)=0(?)nlognT(n)=0(?)nA2

<2>(B)Arecursivefunctioncancauseaninfinitesequenceof

functioncallsif.

一個遞歸函數(shù)能導(dǎo)致無數(shù)的函數(shù)調(diào)用如果

A.theproblemsizeishalvedateachstep

問題規(guī)模在每一步減半。

B.theterminationconditionismissing

終止條件丟失。

C.nousefulincrementalcomputationisdoneineachstep

在每一步?jīng)]有有用的增量計算。

D.theproblemsizeispositive

問題規(guī)模是確定的。

第6章樹(Tree)

1.關(guān)于樹的一些術(shù)語

<1>根(Root):沒有雙親的結(jié)點。

<2>兄弟(Siblings):有共同雙親的結(jié)點。

<3>內(nèi)結(jié)點(Internalnode):至少有一個孩子的結(jié)點。

<4>外結(jié)點(Externalnode)或葉子(leaf):沒有孩子的結(jié)點。

<5>一個結(jié)點的祖先(Ancestors):雙親、雙親的雙親..

<6>一^t"結(jié)點的后裔(Descendant):孩子、孩子的孩子..

<7>一個結(jié)點的深度(Depth):其祖先的數(shù)目。

<8>一棵樹的高度（Height）:樹中任意結(jié)點中最大的深度。

<9>一個結(jié)點的度（Degree）:其孩子的數(shù)目。

<10>一棵樹的度：樹中任意結(jié)點中最大的度。

<11>子樹（Subtree）:包含指定結(jié)點和它的后裔的一棵樹。

2.二叉樹（BinaryTree）

<1>二叉樹是度為2的樹，即每個結(jié)點最多有兩個孩子。

<2>二叉樹內(nèi)結(jié)點的兩個孩子分別被稱作左孩子和右孩子。

<3>滿二叉樹（Fullbinarytree）是具有2A（k+1）-1個結(jié)點高度為k的二

叉樹。（即每層都是滿的，如下圖所示）

<4>完全二叉樹（Completebinarytree）是指一棵高度為k的二叉樹，

除第k層外，其他各層的結(jié)點樹都達(dá)到最大，第k層所有結(jié)點都連續(xù)集

中在最左邊。（如下圖所示）

3.二叉樹的遍歷

<1>先序遍歷(Preordertraversal)

Inanpreordertraversalanodeisvisitedbeforeitsleftsubtreeand

rightsubtree

在先序遍歷中，每個結(jié)點在它的左子樹和右子樹之前被訪問。

遍歷順序：當(dāng)前結(jié)點，左子樹->右子樹。

AlgorithmPreOrder(v)

if(v非空){

visit(v)〃標(biāo)記訪問結(jié)點v

ifLeftChild(v)〃如果v有左孩子

PreOrder(leftChild(v))〃遞歸遍歷左子樹

ifrightChild(v)〃如果v有右孩子

PreOrder(rightchild(v))〃遞歸遍歷右子樹

}

<2>中序遍歷(Inordertraversal)

Inaninordertraversalanodeisvisitedafteritsleftsubtreeand

beforeitsrightsubtree

在中序遍歷中，每個結(jié)點在它的左子樹之后和右子樹之前被訪問。

遍歷順序：左子樹，當(dāng)前結(jié)點。右子樹。

AlgorithmInOrder(v)

if(v非空){

ifLeftChild(v)〃如果v有左孩子

InOrder(leftChild(v))//遞歸遍歷左子樹

visit(v)〃標(biāo)記訪問結(jié)點v

ifrightChild(v)〃如果v有右孩子

InOrder(rightchild(v))〃遞歸遍歷右子樹

}

<3>后序遍歷(Postordertraversal)

Inanpostordertraversalanodeisvisitedafteritsleftsubtreeand

rightsubtree

在后序遍歷中，每個結(jié)點在它的左子樹和右子樹之后被訪問。

遍歷順序：左子樹，右子樹。當(dāng)前結(jié)點。

AlgorithmPostOrder(v)

if(v非空){

ifLeftChild(v)〃如果v有左孩子

PostOrder(leftChild(v))//遞歸遍歷左子樹

ifrightChild(v)〃如果v有右孩子

PostOrder(rightchild(v))//遞歸遍歷右子樹

visit(v)〃標(biāo)記訪問結(jié)點v

}

以上三種遍歷，均為二叉樹的深度優(yōu)先遍歷(Depth-FirstTraversals,

DFS)

<4>廣度優(yōu)先遍歷（Breadth-FirstTraversals,BFS）

BFS也稱作層次遍歷，一般用隊列來實現(xiàn)層次遍歷，遍歷過程如圖

所示：

關(guān)鍵代碼:

current=q.DeQueue();〃退隊

if(current-leftChild!=NULL)〃左子女

q.EnQueue(current-leftChild);〃進(jìn)隊列

if(current-rightchild!=NULL)〃右子女

q.EnQueue(current->rightchild);〃進(jìn)隊列

4.二叉樹的線索化（Thread）

<1>關(guān)于線索化

二叉樹浪費了許多空間，每個根節(jié)點都有兩個空指針。我們可以利

用這些空指針來幫助我們遍歷二叉樹，可以用這些空指針指向遍歷

順序的后繼結(jié)點，這個過程就叫做線索化。

<2>三種線索化

根據(jù)遍歷種類的不同，線索化分為：先序線索化、中序線索化、后

序線索化。

<3>線索化的具體過程（只以先序線索化為例說明）

如下圖所示:

先寫出先序遍歷順序：ABDECF

紅箭頭表示指向后繼結(jié)點，綠箭頭表示指向前驅(qū)結(jié)點。

每個有空指針位置的結(jié)點，右側(cè)連接紅箭頭，左側(cè)連接綠箭頭。

每個結(jié)點最多連接兩個結(jié)點，如果沒有前驅(qū)或者后繼，則指向NIL,表

示空。

5.優(yōu)先隊列(PriorityQueue)

<1>特點

每次出隊的元素是所有元素中優(yōu)先級最高的。

<2>用二叉堆(BinaryHeap)實現(xiàn)

如上圖所示，二叉堆其實是一棵完全二叉樹，可以分為大根堆

(Max-Heap)和小根堆(Min-Heap),大根堆的任何結(jié)點的權(quán)值都

比其孩子結(jié)點的權(quán)值大，小根堆相反。

堆的一些基本操作(實現(xiàn)自《算法導(dǎo)論》)：

DATA_TYPEPARENT(inti){〃求雙親結(jié)點的索引

return(int)(i/2);

)

DATA_TYPELEFT(inti){〃求左孩子的索引

return2*i;

)

DATA_TYPERIGHT(inti){〃求右孩子的索引

return2*i+1;

}

voidMAX_HEAPIFY(DATA_TYPE*A,inti){

〃保持大根堆性質(zhì)

intI,r,largest;

DATA_TYPEtemp;

I=LEFT(i);

r=RIGHT(i);

if(K=HEAP_SIZE&&A[l]>A[i])largest=I;

elselargest=i;〃選取三個之中權(quán)值最大的

if(r<=HEAP_SIZE&&A[r]>A[largest])largest=r;

if(largest!=i){

temp=A[i];

A[i]=A[largest];

A[largest]=temp;

MAX_HEAPIFY(A,largest);〃遞歸保持堆性質(zhì)

)

}

voidBUILD_MAX_HEAP(DATA_TYPE*A,intlen){

〃自底向上建立堆

HEAP_SIZE=len;

inti;

for(i=(int)(len/2);i>=1;i--){

MAX_HEAPIFY(A,i);

)

6.哈夫曼樹(HuffmanTree)

<1>一些術(shù)語

路（pathX路長（pathlength入結(jié)點的路長（pathlengthofanode卜

二叉樹的路長(pathlengthofabinarytree)

具體關(guān)系如下圖：

PathformAtoG：<A,B><B,E><E,G>

PathlengthformAtoG：3

PathlengthofnodeG：3

Pathlengthofatree：2+3+2=7

結(jié)點的權(quán)值（Weightofanode\帶權(quán)結(jié)點的路長（Pathlengthofa

nodewithweightX帶權(quán)樹的路長（Pathlengthofatreewith

weights\總權(quán)值WPL=ZWixLi0

具體關(guān)系如下圖：

PathlengthofnodeGwithweight：

3*4=12

Pathlengthofthetreewithweights：

2*2+3*4+2*1=18

<2>哈夫曼樹的構(gòu)造

具體算法及證明請參考《離散數(shù)學(xué)》和《算法導(dǎo)論》，此處用簡單圖

示說明問題：

每次從待選點集中選出兩個權(quán)值最小的點，作為左右兒子，其雙親

結(jié)點的權(quán)值等于二者之和，并把雙親結(jié)點作為新節(jié)點加入待選點集，

原來選出的兩個點從待選點集中移除。

<3>哈夫曼編碼(HuffmanCode)

先將欲編碼的字符集按照概率分布建立哈夫曼樹，左子樹代表0,右

子樹代表1,逐個編碼即可。具體如下圖：

abcdef9h

0.050.290.070.080.140.230.030.11

HowtoMinimizea:0110

thelengthofb:10

telegraphese?c:1110

d:1111

e:110

f:00

g:0111

h:010

7.習(xí)題

<1>()Thereisabinarytreewhosee