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

第0章C++極速入門(mén)

1.文件后綴名

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

有很多種，較為常見(jiàn)的是.h。

2.#include

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

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

及＞＞和"運(yùn)算符都在其中?！磇terator〉是一個(gè)迭代器庫(kù)，使用

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

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

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

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

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

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

簡(jiǎn)單的來(lái)講：聲明就是說(shuō)明這個(gè)類(lèi)中有什么類(lèi)型，什么名字的變量

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

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

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

5.C++中聲明和定義類(lèi)通常的做法

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

我們?cè)趈ava中總是在把聲明和定義放在一起做，比如剛聲明了一個(gè)

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

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

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

的.cpp中。

6.'作用域運(yùn)算符

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

function()表示這個(gè)function()是類(lèi)A的。

7.命名空間

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

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

using聲明來(lái)簡(jiǎn)化代碼，語(yǔ)法：usingnamespacestd;這樣我們之

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

8.Const關(guān)鍵字

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

9.引用

引用是一個(gè)對(duì)象的別名，是一種復(fù)合類(lèi)型，通過(guò)在變量名前添加&'

符號(hào)來(lái)定義，操作引用就是操作對(duì)象本身，如inta=10;int&b=a;

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

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

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

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

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

形參的值return出去賦給指定的變量，再將形參銷(xiāo)毀，而傳引用時(shí)，

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

形參實(shí)際分配空間，函數(shù)執(zhí)行完以后也不用再把值賦回去，因?yàn)椴?/p>

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

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

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

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

11.操作符的重載

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

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

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

會(huì)使用。

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

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

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

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

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

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

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

13.模板類(lèi)

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

template<classType>

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

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

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

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

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

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

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

用于實(shí)現(xiàn)類(lèi)，就叫類(lèi)模板。

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

到底是在是用什么類(lèi)型，我們直接給出實(shí)參就可以。而使用類(lèi)模板

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

語(yǔ)法：類(lèi)名v要用的類(lèi)型〉對(duì)象名。

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

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

你看了上面的解說(shuō)，最好動(dòng)手寫(xiě)上一兩個(gè)C++程序，哪怕不比helloworld

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

第1章概論

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

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

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

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

2.分類(lèi)

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

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

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

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

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

3.ADT

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

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

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

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

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

4.算法性能分析和度■

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

常采用大。表示法來(lái)描述。

第2章數(shù)組

1.簡(jiǎn)介

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

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

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

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

過(guò)數(shù)組的下標(biāo)來(lái)實(shí)現(xiàn)的。

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

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

Addr[i]=a+i*I

3.順序表

定義：把線性表中所有的表項(xiàng)按照邏輯順序依次存儲(chǔ)到一塊指定地

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

操作：

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

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

某一元素。

4.順序表的性能分析

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

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

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

未找到引用源。，若搜索表項(xiàng)的各項(xiàng)可能性相同，則ACN=錯(cuò)誤!未找到引用

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

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

(averagemovingnumber)

插入：AMN=錯(cuò)誤!未找到引用源。

若個(gè)表項(xiàng)插入概率相等，AMN=錯(cuò)誤!未找到引用源。

刪除：AMN=錯(cuò)誤!未找到引用源。

若個(gè)表項(xiàng)刪除概率相等，AMN=錯(cuò)誤!未找到引用源。

5.三角矩陣的存儲(chǔ)

對(duì)于一個(gè)n*n對(duì)稱方陣來(lái)說(shuō)，可以只存儲(chǔ)它的上三角或者下三角部分來(lái)

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

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

aOOa10a11a20a21a22a30a31a32a33

Loc(i,j)=k;

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

k=y

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

6.對(duì)角矩陣的存儲(chǔ)

aooana02000

aio811ai2ai300

3203218223233240

0831832333834835

00842343243345

000853354355J

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

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

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

7.稀疏矩陣

使用一個(gè)三元組只存儲(chǔ)矩陣中的非零元素，可以實(shí)現(xiàn)對(duì)稀疏矩陣的壓

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

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

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

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

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

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

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

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

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

提高效率rowSize□來(lái)記錄每一列有多少個(gè)非零元素，rowStart□來(lái)記錄每

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

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

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

個(gè)字符，

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

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

符。

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

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

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

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

方法，但是需要維持鏈表

9.字符串模式匹配

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

匹配。KMP匹配算法因?yàn)闊o(wú)回溯，效率較高。（PPT86頁(yè)）

10.STL中的string

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

就可以使用了，此類(lèi)包含了初始化，串接，獲取長(zhǎng)度，輸入輸出等基本操

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

11.STL中的vector

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

提供了一個(gè)安全的對(duì)數(shù)組的替代，因?yàn)樗峁┏蓡T函數(shù)來(lái)實(shí)現(xiàn)那些更高級(jí)

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

vector引用的聲明語(yǔ)法：

vector<type>v;

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

用vector聲明一個(gè)整形矩陣：

vector<vector<int>>matrix;

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

K

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

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

并且可以通過(guò)vector.push_back()來(lái)向vector中添加新項(xiàng)

12.STL中的deque

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

叫做雙向隊(duì)列，類(lèi)似于vector,但支持雙向操作，deque通過(guò).push_front

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

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

外的存儲(chǔ)空間。

13.習(xí)題:

1.Westorea4x4symmetric(對(duì)稱)matrixAintoanarrayB

(indexstartfrom0)withrowmajororderStorethelowertriangle

only,theindexofelementa[2][3]inBis4.

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

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

是多少？

a11a12a13a14因?yàn)槭菍?duì)稱矩陣，

a21a22a23a24所以a23=a32,a32

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

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

2.()Theworst-timeforremovinganelementfroma

sequencelist(Big-Oh)isB

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

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

少？

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

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

3.Wecanuse3vectortypetostorevalueandloactionof

non-zeroelementsinasparsematrix.

在稀疏矩陣中，我們可以使用一個(gè)三元vector來(lái)存儲(chǔ)非零元

的值和上^。三元組中一個(gè)表項(xiàng)有三個(gè)變量，分別是

row,col,value。

第3章鏈表

1.簡(jiǎn)介

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

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

點(diǎn)，鏈表誕生了。

鏈表并不是用連續(xù)的存儲(chǔ)空間，而是通過(guò)指針指向下一個(gè)節(jié)點(diǎn)的地址來(lái)

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

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

鏈表的一個(gè)節(jié)點(diǎn)由它的數(shù)據(jù)項(xiàng)和指針組成，最后一個(gè)節(jié)點(diǎn)的指針為空指

針，鏈表會(huì)有一個(gè)頭結(jié)點(diǎn)，這個(gè)頭結(jié)點(diǎn)僅僅是一個(gè)指向鏈表第一個(gè)節(jié)點(diǎn)的指

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

我們可以通過(guò)頭結(jié)點(diǎn)訪問(wèn)整個(gè)鏈表。

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

不可比擬的，因?yàn)閿?shù)組可以做到隨機(jī)訪問(wèn)，但鏈表訪問(wèn)中部元素或者后部元

素（對(duì)單鏈表來(lái)說(shuō)）會(huì)慢的多，原因是鏈表只能通過(guò)上一項(xiàng)找到下一項(xiàng)。

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

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

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

③讓新節(jié)點(diǎn)的指針指向第i個(gè)節(jié)點(diǎn)

④使第i-1個(gè)節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)。

刪除：①找到第i-1個(gè)節(jié)點(diǎn)，并判斷要?jiǎng)h除的位置是否合法。

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

③讓第i-1節(jié)點(diǎn)的指針指向第第i+1個(gè)節(jié)點(diǎn)。

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

3.循環(huán)性表

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

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

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

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

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

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

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

4.雙向鋅表

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

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

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

First

Headinkdatarlink

item

P->llinkPP->rlink

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

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

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

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

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

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

newnode->ILink=current->ILink;

newnode->rLink=current;

current->ILink=newnode;

newnode->ILink->rLink=newnode;

5.靜態(tài)性表

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

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

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

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

0NULL7

1周4

2錢(qián)5

3王NULL

46

5孫8

6鄭3

7趙2

8李1

6.習(xí)題：

1.Whichofthefollowingistrue

①wecanrandomaccessanelementinarray.

②wecanrandomaccessanelementinlinkedlist.

(3)wecantrandomaccessbothinarrayandlinkedlist.

@allaboveiswrong

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

一個(gè)元素的訪問(wèn)，不需要依賴于對(duì)其他元素的訪問(wèn)，但是鏈表是做不到

這一點(diǎn)的，除過(guò)頭結(jié)點(diǎn)，要想訪問(wèn)鏈表中的任何一個(gè)元素，必須先訪問(wèn)

它的先驅(qū)。

2.Writeafunctiontoinsertanelementintoasinglelinkedlistwith

headernode.

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

第4章棧和隊(duì)列

“食堂打飯要是后來(lái)先買(mǎi),那一定會(huì)非常有意思”

1.簡(jiǎn)介

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

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

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

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

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

2.棧的實(shí)現(xiàn)

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

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

3.進(jìn)棧

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

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

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

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

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

4.出棧

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

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

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

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

5.雙向棧

程序中往往同時(shí)存在幾個(gè)棧，而各個(gè)棧所需的運(yùn)行空間是動(dòng)態(tài)變化的，

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

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

向棧。

0maxSize-1

tttTt

b[Q]HO]Hl]b⑴

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

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

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

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

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

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

采用鏈?zhǔn)綏?lái)表示一個(gè)棧，便于節(jié)點(diǎn)的插入與刪除，鏈?zhǔn)綏５臈ｍ斣诒?/p>

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

7.棧的應(yīng)用

(1)括號(hào)匹配(2)表達(dá)式計(jì)算

8.隊(duì)列簡(jiǎn)介

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

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

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

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

隊(duì)列，另一種是基于鏈表的存儲(chǔ)表示，叫做鏈?zhǔn)疥?duì)列。

9.順序隊(duì)列

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

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

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

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

后返回記錄下來(lái)的。

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

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

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

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

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

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

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

來(lái)判斷隊(duì)列是否為滿，即rear若指到front的前一個(gè)位置，隊(duì)列即滿，這實(shí)

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

兀素。

10.鏈?zhǔn)疥?duì)列

隊(duì)列的隊(duì)頭指針指向單鏈表的第一個(gè)節(jié)點(diǎn)，隊(duì)尾指針指向單鏈表的最后

一個(gè)節(jié)點(diǎn)。用單鏈表表示的鏈?zhǔn)疥?duì)列特別適合與數(shù)據(jù)元素變動(dòng)比較大的情

況，而且不存在隊(duì)列滿而溢出的情況。

11.習(xí)題

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

fromfullqueuesby.

Ausingagapinthearray

Bincrementingqueuepositionsby2insteadof1

Ckeepingacountofthenumberofelements

Daandc

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

B增加兩個(gè)隊(duì)列位置而不是一個(gè)

C保持對(duì)元素的個(gè)數(shù)的計(jì)數(shù)

Da和c

A正確，因?yàn)檠h(huán)隊(duì)列的普遍做法是當(dāng)rear指向front的前一個(gè)位置時(shí)，

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

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

么，因此選D

2.Astackisalistwhereremovalandadditionoccuratthe

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

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

棧么。

3.Considerthefollowingfunctiontobalancesymbolsstoredinstring

expthatincludesparentheses(圓括號(hào))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

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

Recursionisatechniquethatsolvesaproblembysolvingasmaller

problemofthesametype

遞歸是一種技巧，它通過(guò)解決同類(lèi)型的小問(wèn)題來(lái)完成問(wèn)題的解決。

2.遞歸函數(shù)

來(lái)看一個(gè)遞歸函數(shù)的例子：

IntFunction(intn){

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

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

)

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

<2>該函數(shù)用到了遞歸的設(shè)計(jì)，因?yàn)榍驠ibonacci數(shù)列第n項(xiàng)的值這個(gè)

問(wèn)題，可以分割為同類(lèi)型的子問(wèn)題：求其第n-1項(xiàng)和第n-2項(xiàng)的值，并

求和。

<3>其中⑴被稱為basecase,是因?yàn)樗苋菀妆挥?jì)算。(2)被稱為

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

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

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

3.遞歸與迭代(Iteration)

<1>Iterationcanbeusedinplaceofrecursion

迭代可以用來(lái)代替遞歸

Aniterativealgorithmusesaloopingstructure

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

Arecursivealgorithmusesabranchingstructure

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

<2>Recursivesolutionsareoftenlessefficient,intermsofbothtime

andspace,thaniterativesolutions

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

<3>Recursioncansimplifythesolutionofaproblem,oftenresultingin

shorter,moreeasilyunderstoodsourcecode

遞歸可以簡(jiǎn)化一個(gè)問(wèn)題的解決，通常都會(huì)帶來(lái)更簡(jiǎn)短、更通俗易懂

的源代碼。

<4>(Nearly)everyrecursivelydefinedproblemcanbesolved

iteratively,iterativeoptimizationcanbeimplementedafterrecursive

design

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

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

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

<1>分治法(divideandconquer)

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

<2>回溯法(backtracking)

Eg:求解八皇后問(wèn)題。

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

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

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

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

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

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

所以C2*n等價(jià)于n),所以此類(lèi)型遞歸的算法復(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.

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

A.theproblemsizeishalvedateachstep

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

B.theterminationconditionismissing

終止條件丟失。

C.nousefulincrementalcomputationisdoneineachstep

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

D.theproblemsizeispositive

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

第6章樹(shù)(Tree)

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

<1>根(Root):沒(méi)有雙親的結(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

2.二叉樹(shù)（BinaryTree）

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

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

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

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

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

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

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

3.二叉樹(shù)的遍歷

<1>先序遍歷(Preordertraversal)

Inanpreordertraversalanodeisvisitedbeforeitsleftsubtreeand

rightsubtree

在先序遍歷中，每個(gè)結(jié)點(diǎn)在它的左子樹(shù)和右子樹(shù)之前被訪問(wèn)。

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

AlgorithmPreOrder(v)

if(v非空){

visit(v)〃標(biāo)記訪問(wèn)結(jié)點(diǎn)v

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

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

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

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

}

<2>中序遍歷(Inordertraversal)

Inaninordertraversalanodeisvisitedafteritsleftsubtreeand

beforeitsrightsubtree

在中序遍歷中，每個(gè)結(jié)點(diǎn)在它的左子樹(shù)之后和右子樹(shù)之前被訪問(wèn)。

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

AlgorithmInOrder(v)

if(v非空){

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

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

visit(v)〃標(biāo)記訪問(wèn)結(jié)點(diǎn)v

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

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

}

<3>后序遍歷(Postordertraversal)

Inanpostordertraversalanodeisvisitedafteritsleftsubtreeand

rightsubtree

在后序遍歷中，每個(gè)結(jié)點(diǎn)在它的左子樹(shù)和右子樹(shù)之后被訪問(wèn)。

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

AlgorithmPostOrder(v)

if(v非空){

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

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

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

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

visit(v)〃標(biāo)記訪問(wèn)結(jié)點(diǎn)v

}

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

DFS)

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

BFS也稱作層次遍歷，一般用隊(duì)列來(lái)實(shí)現(xiàn)層次遍歷，遍歷過(guò)程如圖

所示：

關(guān)鍵代碼:

current=q.DeQueue();〃退隊(duì)

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

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

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

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

4.二叉樹(shù)的線索化（Thread）

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

二叉樹(shù)浪費(fèi)了許多空間，每個(gè)根節(jié)點(diǎn)都有兩個(gè)空指針。我們可以利

用這些空指針來(lái)幫助我們遍歷二叉樹(shù)，可以用這些空指針指向遍歷

順序的后繼結(jié)點(diǎn)，這個(gè)過(guò)程就叫做線索化。

<2>三種線索化

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

序線索化。

<3>線索化的具體過(guò)程（只以先序線索化為例說(shuō)明）

如下圖所示:

先寫(xiě)出先序遍歷順序：ABDECF

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

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

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

示空。

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

<1>特點(diǎn)

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

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

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

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

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

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

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

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;〃選取三個(gè)之中權(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.哈夫曼樹(shù)(HuffmanTree)

<1>一些術(shù)語(yǔ)

路（pathX路長(zhǎng)（pathlength入結(jié)點(diǎn)的路長(zhǎng)（pathlengthofanode卜

二叉樹(shù)的路長(zhǎng)(pathlengthofabinarytree)

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

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

PathlengthformAtoG：3

PathlengthofnodeG：3

Pathlengthofatree：2+3+2=7

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

nodewithweightX帶權(quán)樹(shù)的路長(zhǎng)（Pathlengthofatreewith

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

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

PathlengthofnodeGwithweight：

3*4=12

Pathlengthofthetreewithweights：

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

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

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

示說(shuō)明問(wèn)題：

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

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

原來(lái)選出的兩個(gè)點(diǎn)從待選點(diǎn)集中移除。

<3>哈夫曼編碼(HuffmanCode)

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

子樹(shù)代表1,逐個(gè)編碼即可。具體如下圖：

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