《數(shù)據(jù)結構》總復習

第1章緒論第6章樹和二叉樹

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

第3章棧和隊列第8章圖

第4章串第9章查找

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

1

第1章緒論

1.數(shù)據(jù)結構的定義

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

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

(1)數(shù)據(jù)的邏輯結構。

(2)數(shù)據(jù)的存儲結構(物理結構)。

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

數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，它

與數(shù)據(jù)的存儲無關，是獨立于計算機的。

數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實

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

數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結構上的，每

種邏輯結構都有一組相應的運算。但運算的實現(xiàn)與

數(shù)據(jù)的存儲結構有關。

邏輯結構主要有兩大類:

(1)線性結構

(2)非線性結構：

1)樹形結構

2)圖形結構

存儲結構分為如下四種:

(1)順序存儲方法

(2)鏈式存儲方法

(3)索引存儲方法

(4)散列存儲方法

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

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

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

學模型中抽象出來的邏輯數(shù)據(jù)結構和邏輯數(shù)據(jù)結構

上的運算，而不考慮計算機的具體存儲結構和運算

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

3.什么是算法

算法是對特定問題求解步驟的一種描述，它

是指令的有限序列。

算法的五個重要的特性：

有

家

性

(1)

確

走

(2)性

可

行

性

(3)

入

輸

有

(4)

出

輸

有

(5)

4.算法分析,

(1)算法的時間復雜度：是指其基本運算

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

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

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

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

記號讀作“大它表示隨問題規(guī)

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

率相同。

(2)算法空間復雜度：是對一個算法在運行過

程中臨時占用的存儲空間大小的量度。

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

作或就地工作算法。

第2章線性表

1.線性表的定義

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

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

長度，用n表示，n>0o當n=0時，表示線性表是

一個空表，即表中不包含任何元素。

1.線性表的順序存儲結構一順序表

typedefstruct

|

ElemTypeelem[MaxSize];

/*存放順序表元素刃

intlength;

/*存放順序表的長度*/

}SqList;

順序表基本運算的實現(xiàn)

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

長n有關；插入一個元素時所需移動元素的平均次

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

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

表長n有關。刪除一個元素時所需移動元素的

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

度為O(n)。

1

【例2.1]設計一個算法，招1x插入到一個有序

（從小到大排序）的線性表（順序存儲結構）的適當

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

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.線性表的鏈式存儲結構一鏈表

定義單鏈表結點類型：

typedefstructLNode

ElemTypedata;

structLNode*next;

/*指向后繼結點*/

}LinkList;

定義雙鏈表結點類型：

typedefstructDNode

(

ElemTypedata;

structDNode*prior;

/*指向前驅結點*/

structDNode*next;

/*指向后繼結點*/

}DLinkList;

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

重點：頭插法建表和尾插法建表算法，它是

很多算法設計的基礎。

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

性表，采用帶頭結點的he單鏈表存放，編寫

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

得：

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

voidfun(LinkListLinkList*&h%

LinkList*&hb)

(

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

ha=hc;/*ha的頭結點利用he的頭結點*/

ra=ha;/*ra始終指向ha的末尾結點*/

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

/*創(chuàng)建hb頭結點*/

rb=hb;/*rb始終指向hb的末尾結點*/

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;

/*兩個尾結點的next域置空

整個算法實際上是采用尾插法建表。

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

重點：插入和刪除結點的算法。

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

重點：判斷最后一個結點。

第3章棧和隊列

3.1棧

1.棧的定義

棧是一種只能在一端進行插入或刪除操作的

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

為棧頂。表的另一端稱為棧底。當棧中沒有數(shù)據(jù)

元素時，稱為空棧。棧的插入操作通常稱為進棧

或入棧，棧的刪除操作通常稱為退?；虺鰲?。

2.棧的順序存儲結構及其基本運算實現(xiàn)

typedefstruct

{

ElemTypeelem[MaxSize];

inttop;/*棧指針*/

}SqStack;

棧空條件:s->top==-1

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

3.棧的鏈式存儲結構及其基本運算的實現(xiàn)

typedefstructlinknode

{

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

structlinknode*next;/*指針域*/

}LiStack;

帶頭結點的單鏈表來實現(xiàn)（也可不帶頭結點）

Ihead

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

棧滿條件:？

3.2隊列

1.隊列的定義

?隊列簡稱隊，它也是一種運算受限的線性

表，其限制僅允許在表的一端進行插入，而在

表的另一端進行刪除。進行插入的一端稱做隊

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

(front)o

2.隊列的順序存儲結構及其基本運算的實現(xiàn)

typedefstruct

(

ElemTypeelem[MaxSize];

intfront,rear;/*隊首和隊尾指針*/

}SqQueue;

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

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

環(huán)隊列。

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

再前進一個位置就自動到0,這可以利用除法取余的運算

(%)來實現(xiàn)：

隊首指針進1:front=(front+l)%MaxSize

隊尾指針進1:rear=(rear+l)%MaxSize

隊空條件：q->rear==q->front

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

3.隊列的鏈式存儲結構及其基本運算的實現(xiàn)

structqnode

(

ElemTypedata;

structqnode*next;

}QNode;

typedefstruct

(

QNode/front;

QNode*rear;

}LiQueue;

第4章串

1?串的定義

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

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

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

2?串的順序存儲結構-順序串

3.串的鏈式存儲結構一鏈串

KMP算法不作要求。

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

1.教組的定義

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

a1?a??????2口

構成的有限序列，且該有限序列存儲在一塊地址

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

2.數(shù)組的順序存儲結箱

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

以行序為主序：

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

以列序為主序

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

3.特殊矩陣的壓縮存儲:>

(1)對稱矩陣

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

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

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

.i(i+l)/2+j當日時

k=1

〔j(j+l)/2+i當i<j時

(2)三角矩陣

采用類似的壓縮方法.

4.稀疏矩陣

(1)三元組表示

(2)十字鏈表表示

各種表示的基本思路。

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

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

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

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

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

第6章樹和二叉樹

6.1樹

L樹的定義

樹是由n（n>0）個結點組成的有限集合（記為T）。

其中，

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

如果n>0,這n個結點中存在（有僅存在）一個結點

作為樹的根結點，簡稱為根（root）,其余結點可分為

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

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

樹:""------------—一—

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

(1)樹形表示法

(2)文氏圖表示法

(3)凹入表示法

(4)括號表示法

3.樹■的遍歷

先根遍歷算法為：

(1)訪問根結點；

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

棵子樹。

后根遍歷算法為：

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

棵子樹；

(2)訪問根結點。

4.樹（森林）與二叉樹之間的相互轉換

6.2二叉樹

1.二叉樹的定義

二叉樹也稱為二次樹或二分樹，它是有限的

結點集合，這個集合或者是空，或者由一個根結

點和兩棵互不相交的稱為左子樹和右子樹的二叉

樹組成。

完全二叉樹，滿二叉樹的定義

2.二叉樹性質:>

性質1非空二叉樹上葉結點數(shù)等于雙分支結點

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

性質2非空二叉樹上第i層上至多有2川個結點

(i>l)o

性質3高度為h的二叉樹至多有2也1個結點

(h>l)o

性質4完全二叉樹的性質。

性質5具有n個(!>〉0)結點的完全二叉樹的高

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

.【例6.11將一棵有100個結點的完全二叉樹從根

這一層開始，每一層從左到右依次對結點進行編號,

根結點的編號為L則編號為49的結點的左孩子編

號為_。

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

答：A

【例6.2］深度為5的二叉樹至多有一個結點。

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

答：相同滿度時滿二叉樹結點最多，h=5的滿

二叉樹結點個數(shù)=25?1=31。本題答案應為C。

3.二叉樹存儲結構

(1)二叉樹的順序存儲結構

(2)二叉鏈存儲結構

typedefstructnode

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

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

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

}BTNode;

4.二叉樹的遍歷

(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);

注意：重點掌握基于遍歷的遞歸算法設計。

5.二叉樹的構造

任何n(n>0)個不同結點的二又樹，都

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

任何n(n>0)個不同結點的二又樹，都

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

掌握它們的構造方法。

■

6.線索二叉樹一一一

⑴線索二叉樹的概念

對于具有n個結點的二叉樹，采用二叉鏈存儲

結構時，每個結點有兩個指針域，總共有2n個指

針域，又由于只有n?l個結點被有效指針所指向

（樹根結點沒有被有效指針域所指向），則共有

個空鏈域。

遍歷二叉樹的結果是一個結點的線性序列?？梢?/p>

的

利用這些空鏈域存放指向結點的前驅和后繼結點

后

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

繼”的指針，稱作線索。

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

的過程稱作按該方式對二叉樹進行線索化。

(2)二叉樹進行線索化的過程

不要求掌握算法。

63哈夫寺時

L哈夫曼樹的定義

在n個帶權葉子結點構成的所有二叉樹中，

帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹

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

2.哈夫曼樹的構造過程

3.哈夫曼編碼的構造過程

第7章廣義表

相關概念：

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

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

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

分如為的表尾.

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

第8章圖

1.圖的基本概念

(1)頂點的度、入度和出度

⑵完全圖

(3)子圖

(4)路徑和路徑長度

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

(6)強連通圖和強連通分量

⑺權和網(wǎng)

2.圖的存儲結構

(1)鄰接矩陣存儲方法

(2)鄰接表存儲方法

掌握兩種存儲方法的優(yōu)缺點，

同一種功能在不同存儲結構上的實

現(xiàn)算法。

3.圖的遍歷

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

voidDFS(ALGraph*G,intv)

(

ArcNode*p;Visited[v]=1;/*置已訪問標記*/

printf(n%d!\v);/*輸出被訪問頂點的編號*/

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

/*p指向頂點v的第一條弧的弧頭結點刃

while(p!=NULL)

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

DFS(G,p->adjvex);

p=p->nextarc;

/*p指向頂點v的下一條弧的弧頭結點*/

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

voidBFS(ALGraph*G,intv「‘

{ArcNode*p;

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

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

intvisited[MAXV];

/*定義存放結點的訪問標志的數(shù)組*/

intw,i;

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

/*訪問標志數(shù)組初始化*/

printf(n%2df;v);

visited[v]=l;/*置已訪問標記*/

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

queue[rear]=v;/*v進隊*/

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

{front=(front+l)%MAXV;

w=queue[front];/*出隊并賦給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)先搜索遍歷非連通無向圖的算法如下:

DFSl(ALGraph*g)

{

inti;

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

if(visited[i]==0)

DFS(gJ);

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

BFSl(ALGraph*g)

inti;

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

if(visited[i]==0)

BFS(g4)；

【例