《數(shù)據(jù)結(jié)構(gòu)》總復(fù)習(xí)

第1章緒論第6章樹(shù)和二叉樹(shù)

第2章線性表第7章廣義表

第3章棧和隊(duì)列第8章圖

第4章串第9章查找

第5章數(shù)組和稀疏矩陣第10章內(nèi)排序

1

第1章緒論

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

數(shù)據(jù)-〉數(shù)據(jù)元素->數(shù)據(jù)項(xiàng)

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系。包括:

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)。

(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))。

(3)施加在該數(shù)據(jù)上的運(yùn)算。

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它

與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)

現(xiàn)（亦稱為映象），它是依賴于計(jì)算機(jī)語(yǔ)言的。

數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每

種邏輯結(jié)構(gòu)都有一組相應(yīng)的運(yùn)算。但運(yùn)算的實(shí)現(xiàn)與

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。

邏輯結(jié)構(gòu)主要有兩大類:

(1)線性結(jié)構(gòu)

(2)非線性結(jié)構(gòu)：

1)樹(shù)形結(jié)構(gòu)

2)圖形結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)分為如下四種:

(1)順序存儲(chǔ)方法

(2)鏈?zhǔn)酱鎯?chǔ)方法

(3)索引存儲(chǔ)方法

(4)散列存儲(chǔ)方法

2.抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（AbstractDataType簡(jiǎn)寫為

ADT）指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問(wèn)題的數(shù)

學(xué)模型中抽象出來(lái)的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)

上的運(yùn)算，而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算

的具體實(shí)現(xiàn)算法。

3.什么是算法

算法是對(duì)特定問(wèn)題求解步驟的一種描述，它

是指令的有限序列。

算法的五個(gè)重要的特性：

有

家

性

(1)

確

走

(2)性

可

行

性

(3)

入

輸

有

(4)

出

輸

有

(5)

4.算法分析,

(1)算法的時(shí)間復(fù)雜度：是指其基本運(yùn)算

在算法中重復(fù)執(zhí)行的次數(shù)。

算法中基本運(yùn)算次數(shù)T(n)是問(wèn)題規(guī)模n的某

個(gè)函數(shù)f(n),記作：

T(n)=O(f(n))

記號(hào)讀作“大它表示隨問(wèn)題規(guī)

模n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)

率相同。

(2)算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過(guò)

程中臨時(shí)占用的存儲(chǔ)空間大小的量度。

對(duì)于空間復(fù)雜度為0(1)的算法稱為原地工

作或就地工作算法。

第2章線性表

1.線性表的定義

線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有

限序列。該序列中所含元素的個(gè)數(shù)叫做線性表的

長(zhǎng)度，用n表示，n>0o當(dāng)n=0時(shí)，表示線性表是

一個(gè)空表，即表中不包含任何元素。

1.線性表的順序存儲(chǔ)結(jié)構(gòu)一順序表

typedefstruct

|

ElemTypeelem[MaxSize];

/*存放順序表元素刃

intlength;

/*存放順序表的長(zhǎng)度*/

}SqList;

順序表基本運(yùn)算的實(shí)現(xiàn)

插入數(shù)據(jù)元素算法：元素移動(dòng)的次數(shù)不僅與表

長(zhǎng)n有關(guān)；插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次

數(shù)n/2。平均時(shí)間復(fù)雜度為O(n)。

刪除數(shù)據(jù)元素算法:元素移動(dòng)的次數(shù)也與

表長(zhǎng)n有關(guān)。刪除一個(gè)元素時(shí)所需移動(dòng)元素的

平均次數(shù)為(n-l)/2。刪除算法的平均時(shí)間復(fù)雜

度為O(n)。

1

【例2.1]設(shè)計(jì)一個(gè)算法，招1x插入到一個(gè)有序

（從小到大排序）的線性表（順序存儲(chǔ)結(jié)構(gòu)）的適當(dāng)

位置上，并保持線性表的有序性。

voidInsert(SqList&A,ElemTypex)

inti=0J;

while(i<A.length&&AS.elem[i]<x)i++;

forg=A.length-l;j>=i;j-)

A.elem[j+l]=A.elem[j];

A.elem[i]=x;

A.length++;

2.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一鏈表

定義單鏈表結(jié)點(diǎn)類型：

typedefstructLNode

ElemTypedata;

structLNode*next;

/*指向后繼結(jié)點(diǎn)*/

}LinkList;

定義雙鏈表結(jié)點(diǎn)類型：

typedefstructDNode

(

ElemTypedata;

structDNode*prior;

/*指向前驅(qū)結(jié)點(diǎn)*/

structDNode*next;

/*指向后繼結(jié)點(diǎn)*/

}DLinkList;

(1)單鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：頭插法建表和尾插法建表算法，它是

很多算法設(shè)計(jì)的基礎(chǔ)。

【例24】設(shè)C={apbDa2，b2,…,a^bn}為一線

性表，采用帶頭結(jié)點(diǎn)的he單鏈表存放，編寫

一個(gè)就地算法，將其拆分為兩個(gè)線性表，使

得：

A—{a],a2，?.”an})C—{b0b2,???,，}

voidfun(LinkListLinkList*&h%

LinkList*&hb)

(

LinkList*p=hc->next/ra/rb;

ha=hc;/*ha的頭結(jié)點(diǎn)利用he的頭結(jié)點(diǎn)*/

ra=ha;/*ra始終指向ha的末尾結(jié)點(diǎn)*/

hb=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建hb頭結(jié)點(diǎn)*/

rb=hb;/*rb始終指向hb的末尾結(jié)點(diǎn)*/

while(p!=NULL)

ra->next=p;ra=p;

/*臀*p鏈到ha單鏈表未尾*/

p=p->next;

if(p!=NULL)

(

rb->next=p;rb=p;

/*將*p鏈到hb單鏈表未尾*/

p=p->next;

ra=rb=NULL;

/*兩個(gè)尾結(jié)點(diǎn)的next域置空

整個(gè)算法實(shí)際上是采用尾插法建表。

(2)雙鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：插入和刪除結(jié)點(diǎn)的算法。

(3)循環(huán)鏈表基本運(yùn)算的實(shí)現(xiàn)二

重點(diǎn)：判斷最后一個(gè)結(jié)點(diǎn)。

第3章棧和隊(duì)列

3.1棧

1.棧的定義

棧是一種只能在一端進(jìn)行插入或刪除操作的

線性表。表中允許進(jìn)行插入、刪除操作的一端稱

為棧頂。表的另一端稱為棧底。當(dāng)棧中沒(méi)有數(shù)據(jù)

元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)棧

或入棧，棧的刪除操作通常稱為退棧或出棧。

2.棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)

typedefstruct

{

ElemTypeelem[MaxSize];

inttop;/*棧指針*/

}SqStack;

?？諚l件:s->top==-1

棧滿條件:s->top==MaxSize-l

3.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

typedefstructlinknode

{

ElemTypedata;/*數(shù)據(jù)域*/

structlinknode*next;/*指針域*/

}LiStack;

帶頭結(jié)點(diǎn)的單鏈表來(lái)實(shí)現(xiàn)（也可不帶頭結(jié)點(diǎn)）

Ihead

?？諚l件:s->next==NULL

棧滿條件:？

3.2隊(duì)列

1.隊(duì)列的定義

?隊(duì)列簡(jiǎn)稱隊(duì)，它也是一種運(yùn)算受限的線性

表，其限制僅允許在表的一端進(jìn)行插入，而在

表的另一端進(jìn)行刪除。進(jìn)行插入的一端稱做隊(duì)

尾(rear)，進(jìn)行刪除的一端稱做隊(duì)首

(front)o

2.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

typedefstruct

(

ElemTypeelem[MaxSize];

intfront,rear;/*隊(duì)首和隊(duì)尾指針*/

}SqQueue;

把數(shù)組的前端和后端連接起來(lái)，形成一個(gè)環(huán)形的順序

表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為循

環(huán)隊(duì)列。

循環(huán)隊(duì)列首尾相連，當(dāng)隊(duì)首指針front=MaxSize?l后,

再前進(jìn)一個(gè)位置就自動(dòng)到0,這可以利用除法取余的運(yùn)算

(%)來(lái)實(shí)現(xiàn)：

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

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

隊(duì)空條件：q->rear==q->front

隊(duì)滿條件：(q?>rear+l)%MaxSize==q->front

3.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

structqnode

(

ElemTypedata;

structqnode*next;

}QNode;

typedefstruct

(

QNode/front;

QNode*rear;

}LiQueue;

第4章串

1?串的定義

串（或字符串），是由零個(gè)或多個(gè)字符組成的有窮

序列。含零個(gè)字符的串稱為空串，用中表示。串中所

含字符的個(gè)數(shù)稱為該串的長(zhǎng)度（或串長(zhǎng)）。

2?串的順序存儲(chǔ)結(jié)構(gòu)-順序串

3.串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一鏈串

KMP算法不作要求。

第5章數(shù)組和稀疏矩陣

1.教組的定義

數(shù)組是n(n>l)個(gè)相同類型數(shù)據(jù)元素

a1?a??????2口

構(gòu)成的有限序列，且該有限序列存儲(chǔ)在一塊地址

連續(xù)的內(nèi)存單元中。

2.數(shù)組的順序存儲(chǔ)結(jié)箱

對(duì)于數(shù)組人忙1??(11?2?@]

以行序?yàn)橹餍颍?/p>

LOC(%尸LOC(acic2)+Ki0)*(d2，+l)+(j0)]*k

以列序?yàn)橹餍?/p>

LOC(,尸LOC(F2)+[(jY2)*(di0+l)+(k)]*k

3.特殊矩陣的壓縮存儲(chǔ):>

(1)對(duì)稱矩陣

若一個(gè)n階方陣Z[n][n]中的元素滿足4可=2幣(09

j<n-l),則稱其為n階對(duì)稱矩陣。

A[0..n-l][0..n-l]->B[0..n(n+l)/2]

.i(i+l)/2+j當(dāng)日時(shí)

k=1

〔j(j+l)/2+i當(dāng)i<j時(shí)

(2)三角矩陣

采用類似的壓縮方法.

4.稀疏矩陣

(1)三元組表示

(2)十字鏈表表示

各種表示的基本思路。

【例5.1】二維數(shù)組A[4][4](即A[0??3][0??3])

的元素起始地址是loc(A[0][0])=1000，元素的長(zhǎng)度

為2,則loc(A[2H2])為多少?

答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-

0+1)+(2-0)]*2=1020。

第6章樹(shù)和二叉樹(shù)

6.1樹(shù)

L樹(shù)的定義

樹(shù)是由n（n>0）個(gè)結(jié)點(diǎn)組成的有限集合（記為T）。

其中，

如果n=0，它是一棵空樹(shù),這是樹(shù)的特例；

如果n>0,這n個(gè)結(jié)點(diǎn)中存在（有僅存在）一個(gè)結(jié)點(diǎn)

作為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱為根（root）,其余結(jié)點(diǎn)可分為

m（m>0）個(gè)互不相交的有限集T2,…，Tm,其

中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根

樹(shù):""------------—一—

2.樹(shù)的表示法(邏輯表示方法)

(1)樹(shù)形表示法

(2)文氏圖表示法

(3)凹入表示法

(4)括號(hào)表示法

3.樹(shù)■的遍歷

先根遍歷算法為：

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一

棵子樹(shù)。

后根遍歷算法為：

(1)按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一

棵子樹(shù)；

(2)訪問(wèn)根結(jié)點(diǎn)。

4.樹(shù)（森林）與二叉樹(shù)之間的相互轉(zhuǎn)換

6.2二叉樹(shù)

1.二叉樹(shù)的定義

二叉樹(shù)也稱為二次樹(shù)或二分樹(shù)，它是有限的

結(jié)點(diǎn)集合，這個(gè)集合或者是空，或者由一個(gè)根結(jié)

點(diǎn)和兩棵互不相交的稱為左子樹(shù)和右子樹(shù)的二叉

樹(shù)組成。

完全二叉樹(shù)，滿二叉樹(shù)的定義

2.二叉樹(shù)性質(zhì):>

性質(zhì)1非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)

數(shù)力口1。^110=02+1.

性質(zhì)2非空二叉樹(shù)上第i層上至多有2川個(gè)結(jié)點(diǎn)

(i>l)o

性質(zhì)3高度為h的二叉樹(shù)至多有2也1個(gè)結(jié)點(diǎn)

(h>l)o

性質(zhì)4完全二叉樹(shù)的性質(zhì)。

性質(zhì)5具有n個(gè)(!>〉0)結(jié)點(diǎn)的完全二叉樹(shù)的高

度為「logzn+l］或I_log2n」+L

.【例6.11將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根

這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),

根結(jié)點(diǎn)的編號(hào)為L(zhǎng)則編號(hào)為49的結(jié)點(diǎn)的左孩子編

號(hào)為_(kāi)。

A.98B.99C.50D.48

答：A

【例6.2］深度為5的二叉樹(shù)至多有一個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10

答：相同滿度時(shí)滿二叉樹(shù)結(jié)點(diǎn)最多，h=5的滿

二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)=25?1=31。本題答案應(yīng)為C。

3.二叉樹(shù)存儲(chǔ)結(jié)構(gòu)

(1)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

(2)二叉鏈存儲(chǔ)結(jié)構(gòu)

typedefstructnode

{ElemTypedata;/*數(shù)據(jù)元素*/

structnode^Ichild;/*指向左孩子*/

structnode*rchild;/*指向右孩子*/

}BTNode;

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

(1)先序遍歷

voidpreorder(BTNode*t)

printf(^%d9\t->data);

preorder(t->lchild);

preorder(t->rchild);

(2)中序遍歷

voidinorder(BTNode*t)

{

inorder(t->lchild);

printf(u%d9\t->data);

inorder(t->rchild);

(3)后序遍歷

voidpostorder(BTNode*t)

(

postorder(t->lchild);

postorder(t->rchild);

printf(66%d9\t->data);

注意：重點(diǎn)掌握基于遍歷的遞歸算法設(shè)計(jì)。

5.二叉樹(shù)的構(gòu)造

任何n(n>0)個(gè)不同結(jié)點(diǎn)的二又樹(shù)，都

可由它的中序序列和先序序列惟一地確定。

任何n(n>0)個(gè)不同結(jié)點(diǎn)的二又樹(shù)，都

可由它的中序序列和后序序列惟一地確定。

掌握它們的構(gòu)造方法。

■

6.線索二叉樹(shù)一一一

⑴線索二叉樹(shù)的概念

對(duì)于具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈存儲(chǔ)

結(jié)構(gòu)時(shí)，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，總共有2n個(gè)指

針域，又由于只有n?l個(gè)結(jié)點(diǎn)被有效指針?biāo)赶?/p>

（樹(shù)根結(jié)點(diǎn)沒(méi)有被有效指針域所指向），則共有

個(gè)空鏈域。

遍歷二叉樹(shù)的結(jié)果是一個(gè)結(jié)點(diǎn)的線性序列?？梢?/p>

的

利用這些空鏈域存放指向結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)

后

指針。這樣的指向該線性序列中的“前驅(qū)”和“

繼”的指針，稱作線索。

對(duì)二叉樹(shù)以某種方式遍歷使其變?yōu)榫€索二叉樹(shù)

的過(guò)程稱作按該方式對(duì)二叉樹(shù)進(jìn)行線索化。

(2)二叉樹(shù)進(jìn)行線索化的過(guò)程

不要求掌握算法。

63哈夫寺時(shí)

L哈夫曼樹(shù)的定義

在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，

帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱為哈夫曼樹(shù)

（或最優(yōu)二叉樹(shù)）。

2.哈夫曼樹(shù)的構(gòu)造過(guò)程

3.哈夫曼編碼的構(gòu)造過(guò)程

第7章廣義表

相關(guān)概念：

一個(gè)廣義表中所含元素的個(gè)數(shù)稱為它的長(zhǎng)度..

一個(gè)廣義表中括號(hào)嵌套的最大次數(shù)為它的深度.

表的第一個(gè)元素a1為廣義表GL的表頭，其余部

分如為的表尾.

(a2,?…ai+1,?…a)GL

第8章圖

1.圖的基本概念

(1)頂點(diǎn)的度、入度和出度

⑵完全圖

(3)子圖

(4)路徑和路徑長(zhǎng)度

(5)連通、連通圖和連通分量

(6)強(qiáng)連通圖和強(qiáng)連通分量

⑺權(quán)和網(wǎng)

2.圖的存儲(chǔ)結(jié)構(gòu)

(1)鄰接矩陣存儲(chǔ)方法

(2)鄰接表存儲(chǔ)方法

掌握兩種存儲(chǔ)方法的優(yōu)缺點(diǎn)，

同一種功能在不同存儲(chǔ)結(jié)構(gòu)上的實(shí)

現(xiàn)算法。

3.圖的遍歷

(1)深度優(yōu)先搜索遍歷

voidDFS(ALGraph*G,intv)

(

ArcNode*p;Visited[v]=1;/*置已訪問(wèn)標(biāo)記*/

printf(n%d!\v);/*輸出被訪問(wèn)頂點(diǎn)的編號(hào)*/

p=G->adjlist[v].firstare;

/*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)刃

while(p!=NULL)

{if(visited[p->adjvex]==0)

DFS(G,p->adjvex);

p=p->nextarc;

/*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/

(2)廣度優(yōu)先搜索遍歷"-----

voidBFS(ALGraph*G,intv「‘

{ArcNode*p;

intqueue[MAXV]5front=05rear=0;

/*定義循環(huán)隊(duì)列并初始化*/

intvisited[MAXV];

/*定義存放結(jié)點(diǎn)的訪問(wèn)標(biāo)志的數(shù)組*/

intw,i;

for(i=0;i<G->n;i++)visited[i]=0;

/*訪問(wèn)標(biāo)志數(shù)組初始化*/

printf(n%2df;v);

visited[v]=l;/*置已訪問(wèn)標(biāo)記*/

―rear=(rear+l)%MAXV;——_

queue[rear]=v;/*v進(jìn)隊(duì)*/

while(front!=rear)/*若隊(duì)列不空時(shí)循環(huán)*/

{front=(front+l)%MAXV;

w=queue[front];/*出隊(duì)并賦給w*/

p=G->adjlist[w].firstarc;

while(p!=NULL)

{if(visited[p->adjvex]==0)

{printf(!,%2d!\p->adjvex);

visited[p->adjvex]=l;

rear=(rear+l)%MAXV;

queue[rear]=p->adjvex;

)

p=p->nextarc;

printf(n\nn);

■

，(3)非連通圖的遍歷一?/

采用深度優(yōu)先搜索遍歷非連通無(wú)向圖的算法如下:

DFSl(ALGraph*g)

{

inti;

for(i=0;i<g->n;i+)

if(visited[i]==0)

DFS(gJ);

采用廣度優(yōu)先搜索遍歷非連通無(wú)向圖的算法如下:

BFSl(ALGraph*g)

inti;

for(i=0;i<g->n;i+)

if(visited[i]==0)

BFS(g4)；

【例