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

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

第3章棧和隊列第8章圖

第4章串第9章查找

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

1

第1章緒論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)順序存儲方法

(2)鏈?zhǔn)酱鎯Ψ椒?/p>

(3)索引存儲方法

(4)散列存儲方法

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

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

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

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

上的運算，而不考慮計算機的具體存儲結(jié)構(gòu)和運算

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

3.什么是算法

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

是指令的有限序列。

算法的五個重要的特性：

有

家

性

(1)

確

走

(2)性

可

行

性

(3)

入

輸

有

(4)

出

輸

有

(5)

4.算法分析,

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

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

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

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

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

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

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

率相同。

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

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

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

作或就地工作算法。

第2章線性表

1.線性表的定義

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

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

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

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

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

typedefstruct

|

ElemTypeelem[MaxSize];

/*存放順序表元素刃

intlength;

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

}SqList;

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

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

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

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

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

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

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

度為O(n)。

1

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

（從小到大排序）的線性表（順序存儲結(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)酱鎯Y(jié)構(gòu)一鏈表

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

typedefstructLNode

ElemTypedata;

structLNode*next;

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

}LinkList;

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

typedefstructDNode

(

ElemTypedata;

structDNode*prior;

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

structDNode*next;

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

}DLinkList;

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

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

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

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

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

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

得：

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

voidfun(LinkListLinkList*&h%

LinkList*&hb)

(

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

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

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

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

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

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

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;

/*兩個尾結(jié)點的next域置空

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

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

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

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

重點：判斷最后一個結(jié)點。

第3章棧和隊列

3.1棧

1.棧的定義

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

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

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

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

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

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

typedefstruct

{

ElemTypeelem[MaxSize];

inttop;/*棧指針*/

}SqStack;

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

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

3.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)

typedefstructlinknode

{

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

structlinknode*next;/*指針域*/

}LiStack;

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

Ihead

棧空條件:s->next==NULL

棧滿條件:？

3.2隊列

1.隊列的定義

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

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

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

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

(front)o

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

typedefstruct

(

ElemTypeelem[MaxSize];

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

}SqQueue;

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

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

環(huán)隊列。

循環(huán)隊列首尾相連，當(dāng)隊首指針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.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)

structqnode

(

ElemTypedata;

structqnode*next;

}QNode;

typedefstruct

(

QNode/front;

QNode*rear;

}LiQueue;

第4章串

1?串的定義

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

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

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

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

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

KMP算法不作要求。

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

1.教組的定義

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

a1?a??????2口

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

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

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

對于數(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當(dāng)日時

k=1

〔j(j+l)/2+i當(dāng)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）個結(jié)點組成的有限集合（記為T）。

其中，

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

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

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

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

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

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

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

(1)樹形表示法

(2)文氏圖表示法

(3)凹入表示法

(4)括號表示法

3.樹■的遍歷

先根遍歷算法為：

(1)訪問根結(jié)點；

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

棵子樹。

后根遍歷算法為：

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

棵子樹；

(2)訪問根結(jié)點。

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

6.2二叉樹

1.二叉樹的定義

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

結(jié)點集合，這個集合或者是空，或者由一個根結(jié)

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

樹組成。

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

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

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

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

性質(zhì)2非空二叉樹上第i層上至多有2川個結(jié)點

(i>l)o

性質(zhì)3高度為h的二叉樹至多有2也1個結(jié)點

(h>l)o

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

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

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

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

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

根結(jié)點的編號為L則編號為49的結(jié)點的左孩子編

號為_。

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

答：A

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

■

6.線索二叉樹一一一

⑴線索二叉樹的概念

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

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

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

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

個空鏈域。

遍歷二叉樹的結(jié)果是一個結(jié)點的線性序列。可以

的

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

后

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

繼”的指針，稱作線索。

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

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

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

不要求掌握算法。

63哈夫寺時

L哈夫曼樹的定義

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

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

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

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

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

第7章廣義表

相關(guān)概念：

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

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

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

分如為的表尾.

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

第8章圖

1.圖的基本概念

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

⑵完全圖

(3)子圖

(4)路徑和路徑長度

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

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

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

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

(1)鄰接矩陣存儲方法

(2)鄰接表存儲方法

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

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

現(xiàn)算法。

3.圖的遍歷

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

voidDFS(ALGraph*G,intv)

(

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

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

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

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

while(p!=NULL)

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

DFS(G,p->adjvex);

p=p->nextarc;

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

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

voidBFS(ALGraph*G,intv「‘

{ArcNode*p;

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

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

intvisited[MAXV];

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

intw,i;

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

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

printf(n%2df;v);

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

―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)；

【例