數(shù)據(jù)結(jié)構(gòu)C語言版復(fù)習(xí)攻略

第一章：緒論

一、基礎(chǔ)知識(shí)

概念和術(shù)語(黑體字部分)。

另外，注意：

1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。P4

2、數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。P5

3、數(shù)據(jù)結(jié)構(gòu)及其形式定義。P5

四種基本結(jié)構(gòu)：①集合②線性結(jié)構(gòu)③樹形結(jié)構(gòu)④圖(網(wǎng))狀結(jié)構(gòu)

4、數(shù)據(jù)結(jié)構(gòu)的

邏輯結(jié)構(gòu)(抽象的，與實(shí)現(xiàn)無關(guān))

物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))順序映像(順序存儲(chǔ)結(jié)構(gòu))位置“相鄰”

非順序映像(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))指針表示關(guān)系P6

5、數(shù)據(jù)類型P7

抽象數(shù)據(jù)類型(ADT)P7

ADT=(數(shù)據(jù)對象，數(shù)據(jù)關(guān)系，基本操作)

ADT細(xì)分為原子類型，固定聚合，可變聚合類型。P8

6、算法的概念P13

7、算法的五個(gè)特征

①有窮性②確定性③可行性④輸入(0個(gè)或多個(gè))⑤輸出(1個(gè)或多個(gè))

8、算法設(shè)計(jì)的要求：①正確性②可讀性③健壯性④效率與低存儲(chǔ)量

其中正確性的四個(gè)層次(通常要求達(dá)到C層)。

9、算法的時(shí)間復(fù)雜度P15

常見有：0(1),0(n),O(n'),0(log2n)),0(nlog2n),0(2")

語句頻度，用歸納法計(jì)算。

10、算法的空間復(fù)雜度P17

二、算法

起泡排序。P16

另一種形式

voidBubbleSort(DataTypea[],intn)

(

for(i=0;i<n-l;i++)

for(j=0;j<n-i-l;j++)

if(a[j]>a[j+l])

a[j]<—>a[j+l];

)

或

voidBubbleSort(DataTypea[],intn)

(

for(i=l;i<n;i++)

for(j=0;j<n-i;j++)

if(a[j]>a[j+l])

a[j]<—>a[j+l];

)

或

1分析算法的時(shí)間復(fù)雜度時(shí)，logzn常簡單記作logn.

voidBubbleSort(DataTypea[],intn)

(

for(i=0;i<n-l;i++){

change=fasle;

for(j=0;j<n-i-l;j++)

if(a[j]>a[j+l]){

a[j]<—>a[j+l];

change=true;

)

if(!change)break;

說明：

a）考試中要求寫算法時(shí)，可用類C,也可用C程序。

b）盡量書寫算法說明，言簡意賅。

c）技巧：用“邊界值驗(yàn)證法”檢查下標(biāo)越界錯(cuò)誤。

如上第一個(gè)：第二個(gè)循環(huán)條件若寫作j<n-i,則當(dāng)i=0時(shí)a[j+l]會(huì)越界。

d）時(shí)間復(fù)雜度為0（r）,第3個(gè)在最好情況下（待排記錄有序），時(shí)間復(fù)雜度為0（n）。

第二章、線性表

一、基礎(chǔ)知識(shí)和算法

1、線性表及其特點(diǎn)

線性表是n個(gè)數(shù)據(jù)元素的有限序列。

線性結(jié)構(gòu)的特點(diǎn)：①“第一個(gè)”②“最后一個(gè)”③前驅(qū)④后繼。z

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

（1）特點(diǎn)：a）邏輯上相鄰的元素在物理位置上相鄰。b）隨機(jī)訪問。

（2）類型定義

簡而言之，“數(shù)組+長度”）

constintMAXSIZE=線性表最大長度；

typedefstruct{

DataTypeelem[MAXSIZE];

intlength;

}SqList;

注：a）SqList為類型名，可換用其他寫法。

b）DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。

c）MAXSIZE根據(jù)需要確定。如

constintMAXSIZE=64;

d）課本上的SqList類型可在需要時(shí)增加存儲(chǔ)空間，在上面這種定義下不可以

e）課本上的SqList類型定義中l(wèi)istsize表示已經(jīng)分配的空間大?。ㄈ菁{數(shù)據(jù)元素的個(gè)

數(shù)）。當(dāng)插入元素而遇到L.length==L.listsize時(shí)，用realloc（L.elem,L.listsize+增

2這里太簡煉了，只是為了便于記憶。

3不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。凡此情形，都加引號(hào)以示提醒。

量）重新分配內(nèi)存，而reallocO函數(shù)在必要的時(shí)候自動(dòng)復(fù)制原來的元素到新分配的空間

中。

（3）基本形態(tài)

1。.順序表空

條件L.length==001...MAXSIZE-1

不允許刪除操作.el

LemlL.length==0

2°.順序表滿

條件L.length==MAXSIZEL.elem[L.length==MAXSIZ

不允許插入操作L.ele

m[0<L.length<MAXSI

3°.不空也不滿

可以插入，刪除

（4）基本算法一一遍歷

4°.順序訪問所有元素for(i=0;i<L.length;i++)visit(L.elem[i]);

5查找元素x

for(i=0;i<L.length;i++)

if(L.elem[i]==x)break;

if(i<L.length)

找到；

else

未找到；

(2)插入算法Listinsert(&L,i,x)

1°.前提：表不滿

2°.合理的插入范圍：IWiWL.length+1

注：位序i在C/C++中對應(yīng)于下標(biāo)i-K

3°.步驟

第i至最后所有元素后移一個(gè)元素

在第i個(gè)位置插入元素x

表長增1

4°.算法

bool1Listinsert(SqList&L,inti,DataTypex)

(

if(L.length==MAXSIZEIi<l||i>L.length+1)returnfalse;//失敗

//元素后移

for(j=L.length-1;j>=i-l;j—)//這里j為下標(biāo)，從L.lengthT至UiT

L.elem[j+l]=L.elem[j]://若作為位序，有如何修改？

//插入x

L.elem[i-l]=x;

//表長增1

L.length++;

"這里返回true表示正確插入，返回false表示插入失敗。以下常用來區(qū)分操作是否正確執(zhí)行。

returntrue;//插入成功

(3)刪除算法ListDelete(&L,i,&x)

1。.前提：表非空

2。.合理的刪除范圍：length

3°.步驟

取出第i個(gè)元素

第i個(gè)元素之后的元素向前移動(dòng)一個(gè)位置

表長減1

4°.算法

boolListDelete(SqList&L,inti,DataTypefex)

(

if(L.length==0|Ii<l||i>L.length)returnfalse;//失敗

x=L.elem[i-l];

for(j=i;j<L.length;j++)

L.elem[j-l]=L.;

L.length—;

returntrue;//刪除成功

(4)算法分析

表錯(cuò)誤!文檔中沒有指定樣式的文字。.1順序表插入和刪除算法的分析

插入刪除

基本操作移動(dòng)元素移動(dòng)元素

平均移動(dòng)次1"[(〃-/)=4

〃乙,=i\2

時(shí)間復(fù)雜度0(n)0(n)

尾端操作插入第n+1個(gè)元素,不移動(dòng)刪除第n個(gè)元素，不移動(dòng)

插入、刪除需移動(dòng)大量元素0(n)；但在尾端插入、刪除效率高0(1)。

(5)其他算法

1°.InitList(&L),ClearList(&L)

L.length=0;

2°.ListEmpty(L)

returnL.length==0;

3°.ListLength(L)

returnL.length;

4°.GetElem(L,i,&e)

e=L.elem[i-l];

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

(6)概念

線性鏈表，單鏈表，結(jié)點(diǎn)；數(shù)據(jù)域，指針域；頭指針，頭結(jié)點(diǎn)。

(7)特點(diǎn)

用指針表示數(shù)據(jù)之間的邏輯關(guān)系(邏輯相鄰的元素物理位置不一定相鄰)。

(8)類型定義

簡而言之，“數(shù)據(jù)+指針”5。

typedefstructLNode{

DataTypedata;datanext

structLNode*next;

}LNode,*LinkList;

(9)基本形態(tài)

帶頭結(jié)點(diǎn)的單鏈表的基本形態(tài)有:

1°.單鏈表空

條件：L->next==0L—>A

2°.單鏈表不空

條件：L->next!=0L—>c-->a?c-->…c—>UnA

(10)基本算法(遍歷)

1°.順序訪問所有元素

借助指針，“順膜模4”(沿著鏈表訪問結(jié)點(diǎn))。

p=L->next;//注意起始位置的考慮

while(p!=NULL){//判表尾，另外(p!=0)或(p)均可

visit(p->data);//訪問：可以換成各種操作

p=p->next;〃指針沿著鏈表向后移動(dòng)

)

例：打印單鏈表中的數(shù)據(jù)。

voidPrintLinkList(LinkListL)

(

p=L->next;

while(p!=NULL){

print(p->data);//訪問：打印數(shù)據(jù)域

p=p->next;

}

)

2°.查找元素x

//在單鏈表L中查找元素x

不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。

//若找到，返回指向該結(jié)點(diǎn)的指針；否則返回空指針

LinkListFind(LinkListL,DataTypex)

(

p=L->next;

while(p!=NULL){

if(p->data=二x)returnp;//找到x

p=p->next;

)

returnNULL;//未找到

)

//在單鏈表L中查找元素x

//若找到，返回該元素的位序；否則返回0

intFind(LinkListL,DataTypex)

(

p=L->next;j=1;

while(p!=NULL){

if(p->data==x)returnj;//找到x

p=p->next;j++;//計(jì)數(shù)器隨指針改變

)

return0;//未找到

前一個(gè)算法的另一種寫法：

p=L->next;

while(p&&p->data!=x)

p=p->next;

if(p&&p->data==x)returnp;

elsereturn0;

或者

p=L->next;

while(p&&p->data!=x)p=p->next;

returnp;//為什么

3°.查找第i個(gè)元素

LinkListGet(LinkListL,inti)

(

p=L->next;j=1;

while(p&&j<i){

P=p->next;j++;

)

if(p&&j==i)returnp;

elsereturn0;

4°.查找第i-1個(gè)元素

P=L;j=0;

while(p&&j<i-l){

P=p->next;j++;

)

if(p&&j==i-l)returnp;

elsereturn0;

(11)插入算法Listinsert(&L,i,x)

技巧：畫圖輔助分析。

思路：

先查找第iT個(gè)元素

若找到，在其后插入新結(jié)點(diǎn)

bool"Listinsert(LinkList&L,inti,DataTypex)

//查找第iT個(gè)元素P

P=L;j=0;

while(p&&j<i-l){插入前

p=p->next;j++;

)

//若找到，在p后插入x

if(p&&j-i-l){

s=(LinkList)malloc(sizeof(LNode));執(zhí)行①之后

s->data=x;

s->next=p->next;〃①

p->next=s;//②

returntrue;//插入成功

)

else

returnfalse;//插入失敗

)

注意：

a)要讓p指向第iT個(gè)而不是第i個(gè)元素(否則，不容易找到前驅(qū)以便插入)。

b)能夠插入的條件：p&&j==i-l?即使第i個(gè)元素不存在，只要存在第iT個(gè)元素,

仍然可以插入第i個(gè)元素。

c)新建結(jié)點(diǎn)時(shí)需要?jiǎng)討B(tài)分配內(nèi)存。

s=(LinkList)malloc(sizeof(LNode));

若檢查是否分配成功，可用

if(s==NULL)exit(l);〃分配失敗則終止程序

d)完成插入的步驟：①②。技巧：先修改新結(jié)點(diǎn)的指針域。

6這里返回true表示正確插入，返回false表示插入失敗。

(12)刪除算法ListDelete(&L,i,&x)

思路：

先查找第iT個(gè)元素

若找到且其后存在第i個(gè)元素，則用x返回?cái)?shù)據(jù)，并刪除之

boolListDelete(LinkList&L,inti,int&x)

(刪除前

//查找第iT個(gè)元素p

p=L;j=0;

while(p&&j<i-l){

p=p->next;j++;執(zhí)行①之后

}

〃若存在第i個(gè)元素，則用x返回?cái)?shù)據(jù)，并刪除之

if(p&&j==iT&&p->next){//可以刪除

s=p->next;//①

p->next=s->next;//②

x=s->data;

free(s);

returntrue;

)

else

returnfalse;

)

注意：

a)要求p找到第iT個(gè)而非第i個(gè)元素。為什么？

b)能夠進(jìn)行刪除的條件：p&&j=i-l&&p->next?條件中的p->next就是要保證第

i個(gè)元素存在，否則無法刪除。若寫成p->next&&j==i-l也不妥，因?yàn)榇藭r(shí)(循環(huán)結(jié)束時(shí))

可能有P==NULL,所以必須先確定p不空。技巧：將條件中的“大前提”放在前面。該條件

也不可以寫成p->next&&p&&j==iT,因?yàn)橄扔衟!=0才有p->next,上式顛倒了這一關(guān)

系。

c)釋放結(jié)點(diǎn)的方法。free(s);

d)完成刪除的步驟：①②。

(13)建立鏈表的兩種方法

思路：

建立空表(頭結(jié)點(diǎn))；

依次插入數(shù)據(jù)結(jié)點(diǎn)(每次插入表尾得⑶,a?,…,a”)，每次插入表頭得(a?,…,a2,aj)。

1°.順序建表

voidCreateLinkList(LinkList&L,intn)

//建立空表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//空表

p=L;〃用p指向表尾

//插入元素

for(i=0;i<n;i++){

scanf(x);

s=(LinkList)malloc(sizeof(LNode))：

s->data=x;

//插入表尾

s->next=p->next;

p->next=s;

p=s;//新的表尾

)

}

2°.逆序建表

voidCreateLinkList(LinkList&L,intn)

(

//建立空表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//空表

//插入元素

for(i=0;i<n;i++){

scanf(x);

s=(LinkList)malloc(sizeof(LNode));

s->data=x;

//插入表頭

s->next=L->next;

L->next=s;

)

)

循環(huán)鏈表

(14)特點(diǎn)

最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)。

(15)類型定義

同單鏈表。

(16)基本形態(tài)

空表：L->next==Lo"----巴

非空表。工--------------------------------------------

L>c->a]c->?...c>3|)

(17)與單鏈表的聯(lián)系一

判斷表尾的方法不同：單鏈表用p==NULL；循環(huán)鏈表用p==L。

其余操作相同。

雙向循環(huán)鏈表

(18)特點(diǎn)

一個(gè)結(jié)點(diǎn)包含指向后繼(next)和指向前驅(qū)(prior)兩個(gè)指針，兩個(gè)方向又分別構(gòu)成循環(huán)鏈

表。

(19)類型定義

typedefstructDuLNode{

DataTypedata;

structDuLNode*prior,*next;〃兩個(gè)priddata指針

}DuLNode,*DuLinkList;

(20)基本形態(tài)

空表：用后向指針判斷L->next==L,或者用前向指針判斷L->prior==L。

非空表。

I

(21)與單鏈表和循環(huán)鏈表的聯(lián)系

最大不同：前驅(qū)容易求得，可以向前遍歷。

判斷表尾的方法與循環(huán)鏈表相同：P==L。

插入和刪除時(shí)需要修改兩個(gè)方向的指針。

(22)插入和刪除

需要修改兩個(gè)方向的指針。例如：(見下表)

表錯(cuò)誤!文檔中沒有指定樣式的文字。.2雙向循環(huán)鏈表的插入和刪除

P之后插入SP之前插入S刪除P之后繼s刪除p

s->next=s->prior=s=p->next;p->prior->next=

p->next;p->prior;p->next=p->next;

p->next=s;p->prior=s;s->next;p->next->prior=

s->prior=p;s->next=p;p->next->prior=p->prior;

s->next->priors->prior->next=P；

=s;s;

順序表與單鏈表的比較

表錯(cuò)誤!文檔中沒有指定樣式的文字。.3順序表和單鏈表的比較

順序表單鏈表

以地址相鄰表示關(guān)系用指針表示關(guān)系

隨機(jī)訪問，取元素0(1)順序訪問，取元素0(n)

插入、刪除需要移動(dòng)元素0(n)插入、刪除不用移動(dòng)元素0(n)(用于查找

位置)

總結(jié)：需要反復(fù)插入、刪除，宜采用鏈表；反復(fù)提取，很少插入、刪除，宜采用順序表。

第三章、棧和隊(duì)列

棧

棧，棧頂，棧底，空棧，后進(jìn)先出(LIFO),入棧(Push),出棧(Pop)。

順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)；鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

鏈棧

存儲(chǔ)結(jié)構(gòu)

用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)。

S<----->3n---->an-1>'...>aiA

類型定義

同單鏈表。

基本形態(tài)

1°.?？?/p>

條件：S==NULL

S<-----?A

2°.棧非空

>…>

3°.棧滿（一般不出現(xiàn)）S<----->anan-iai/\

基本算法

4°.入棧Push(&s,x)

boolPush(LinkList&s,DataTypex)

(

//新建結(jié)點(diǎn)

p=(LinkList)inalloc(sizeof(LNode));

if(!p)returnfalse;//失敗

p->data=x;

//插入棧頂

p->next=s;

s=p；

returntrue;

)

5°.出棧Pop(&s,&x)

前提：棧非空。

boolPop(LinkList&s,DataType&x)

(

if(s==NULL)returnfalse;//?？?/p>

//刪除棧頂元素

P=s;

s=s->next;

x=p->data;

free(p);

returntrue;

)

6°.棧頂元素

前提：棧非空。

boolTop(LinkList&s,DataType&x)

(

if(s==NULL)returnfalse;//?？?/p>

x=s->data;

returntrue;

)

順序棧

存儲(chǔ)結(jié)構(gòu)

類似于順序表，插入和刪除操作固定于表尾。

類型定義

簡單說，“數(shù)組+長度”7。

constintMAXSIZE=棧的最大容量；

typedefstruct{

DataTypeelem[MAXSIZE];

inttop;

}SqStack;

基本形態(tài)

7°.?？?/p>

條件s.top—0;

8°.棧滿

條件s.top==MAXSIZE

9°.棧不空、不滿

基本算法

10°.入棧Push(&s,x)

前提：棧不滿

boolPush(SqStack&s,DataTypex)

(

if(s.top==MAXSIZE)returnfalse;//棧滿

s.elem[top]=x;//或者s.elem[top++]=x;

top++;//代替這兩行

returntrue;

)

11°.出棧Pop(&s,&x)

前提：棧非空

boolPop(SqStack&s,DataType&x)

(

if(s.top==0)returnfalse;

top一;//可用x=s.elem[—top];

x=s.elem[top];//代替這兩行

returntrue;

)

7不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。

12°.棧頂元素

前提：棧非空

s.elem[top-l]即是。

隊(duì)列

隊(duì)列，隊(duì)頭，隊(duì)尾，空隊(duì)列，先進(jìn)先出(FIFO)。

鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

循環(huán)隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)之一。

鏈隊(duì)列

存儲(chǔ)結(jié)構(gòu)

簡而言之，”單鏈表+尾指針”%

類型定義

課本P61.

typedefstruct{Q.front

LinkListfront;

Q.rear

LinkListrear;

}LinkQueue;Q.frontaia?-*anA

Q.rear-------------------------------------------—f

基本形態(tài)

隊(duì)列空：Q.front==Q.rear。

非空隊(duì)列。

基本算法

13°.入隊(duì)列

課本P62。插入隊(duì)尾，注意保持Q.rear指向隊(duì)尾。

14°.出隊(duì)列

課本P62。刪除隊(duì)頭元素，

特別注意：如果隊(duì)列中只有一個(gè)元素，則隊(duì)頭也同時(shí)是隊(duì)尾，刪除隊(duì)頭元素后也需要修改

隊(duì)尾指針。

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

存儲(chǔ)結(jié)構(gòu)

簡單說，“數(shù)組+頭、尾位置”工

類型定義

constintMAXSIZE=隊(duì)列最大容量；

typedefstruct{

DataTypeelem[MAXSIZE];

intfront,rear;//隊(duì)頭、隊(duì)尾位置

}SqQueue;

8不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。

9不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。

基本形態(tài)

通常少用一個(gè)元素區(qū)分隊(duì)列空和隊(duì)列滿，也可以加一標(biāo)志。約定front指向隊(duì)頭元素的位

置,rear指向隊(duì)尾的下一個(gè)位置，隊(duì)列內(nèi)容為［front,rear)?

15°.隊(duì)列空

條件：Q.front==Q.rear。

不能出隊(duì)列。

16°.隊(duì)列滿

條件：(Q.rear+l)%MAXSIZE==Q.front(少用一個(gè)元素時(shí))。

不能入隊(duì)列。

17°.隊(duì)列不空也不滿

18°.加一標(biāo)志區(qū)分隊(duì)列空和隊(duì)列滿的情況

可以用滿所有空間。隊(duì)列空和隊(duì)列滿時(shí)都有Q.front==Q.rear,再用標(biāo)志區(qū)分。

隊(duì)列空：Q.front==Q.rearandQ.tag==0；隊(duì)列滿：Q.front==Q.rearandQ.tag==l?

基本算法

19°.入隊(duì)列

前提：隊(duì)列不滿。

boolEnQueue(SqQueue&Q,DataTypex)

{

if((Q.rear+l)%MAXSIZE==Q.front)returnfalse;//隊(duì)列滿

//入隊(duì)列

Q.elem[Q.rear]=x;

Q.rear=(Q.rear+l)%MAXSIZE;

returntrue;

)

20°.出隊(duì)列

前提：隊(duì)列非空。

boolDeQueue(SqQueue&Q,DataType&x)

(

if(Q.front==Q.rear)returnfalse;//隊(duì)列空

//出隊(duì)列

x=Q.elem[Q.front];

Q.front=(Q.front+l)%MAXSIZE;

returntrue;

)

21°.隊(duì)列中元素個(gè)數(shù)

結(jié)論：(Q.rear-Q.front+MAXSIZE)%MAXSIZE(.

注：Q.rear-Q.front可能小于0,需要加上MAXSIZE。

intQueueLength(SqQueueQ)

(

return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;

)

22°.用標(biāo)志區(qū)分隊(duì)列空和滿

用標(biāo)志區(qū)分隊(duì)列空和滿時(shí)，隊(duì)列初始化、入隊(duì)列、出隊(duì)列和隊(duì)列長度的算法如下：

voidInitQueue(SqQueue&Q){

Q.front=Q.rear=0;Q.tag=0;

)

boolEnQueue(SqQueue&Q,DataTypex){

if(Q.front==Q.rearandQ.tag==l)returnfalse;

Q.elem[Q.rear]=x;

Q.rear=(Q.rear+l)%MAXSIZE;

if(Q.tag==0)Q.tag=1;//隊(duì)列非空

returntrue;

)

boolDeQueue(SqQueue&Q,DataType&x){

if(Q.front==Q.rearandQ.tag==0)returnfalse;

x=Q.elem[Q.front];

Q.front=(Q.front+l)%MAXSIZE;

if(Q.front==Q.rear)Q.tag=0;//隊(duì)列空

returntrue;

)

intQueueLength(SqQueueQ)

(

if(Q.front-Q.rearandQ.tag==l)

returnMAXSIZE;//隊(duì)列滿

else

return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;//隊(duì)列不滿(包含隊(duì)列空的情況)

)

棧和隊(duì)列比較

都是線形結(jié)構(gòu)，棧的操作LIFO(后進(jìn)先出)，隊(duì)列操作FIFO(先進(jìn)先出)。

簡化的棧和隊(duì)列結(jié)構(gòu)

在算法中使用棧和隊(duì)列時(shí)可以采用簡化的形式。

表錯(cuò)誤!文檔中沒有指定樣式的文字。"簡化的棧和隊(duì)列結(jié)構(gòu)

簡化棧簡化隊(duì)列

結(jié)構(gòu)“S口+top”結(jié)構(gòu)“q口+front+rearff

初始化top=0;初始化front=rear=0;

入棧s[top++]=X；入隊(duì)列q[rear]=x;

rear=(rear+l)%MAXSIZE;

出棧X=s[--top];出隊(duì)列x=q[front];

front二(front+l)%MAXSIZE;

棧頂s[top-1]隊(duì)列頭q[front]

?？誸op==0隊(duì)列空front==rear

說明：只要棧（隊(duì)列）的容量足夠大，算法中可以省去檢查棧（隊(duì)列）滿的情況。

棧和隊(duì)列的應(yīng)用

23°.表達(dá)式求值

參見課本P53o

24°.括號(hào)匹配

例：檢查表達(dá)式中的括號(hào)是否正確匹配。如｛（）[]｝正確，（[）]｝則錯(cuò)誤。

分析：每個(gè)左括號(hào)都“期待”對應(yīng)的右括號(hào)，匹配成功則可以消去。

思路：遇到左括號(hào)則入棧，遇到右括號(hào)則與棧頂括號(hào)相比較，如果匹配則消去，否則匹配

失敗。當(dāng)然，如果棧中沒有括號(hào)可以匹配,或者最后棧中還有未匹配的左括號(hào)，也都是匹

配錯(cuò)誤。

//檢查輸入的表達(dá)式中括號(hào)是否匹配

boolMatchBrackets()

constintMAXSIZE=1024;//棧的最大容量

chars[MAXSIZE];//簡化的棧結(jié)構(gòu)

inttop;//棧頂

//棧初始化

top=0;

//檢查括號(hào)是否匹配

ch=getchar();

while(ch!=E0F){

switch(ch){

case'(，['

s[top++]=ch//所有左括號(hào)入棧

break;

case')':

if(top==0ors[-top]!=,('）returnfalse;//?？栈蛴依ㄌ?hào)與棧頂

左括號(hào)失配

case:

if(top==0ors[--top]!二'）returnfalse;

case:

if(top==0ors[―top]!='{'）returnfalse;

)

ch二getchar();//取下一個(gè)字符

)

if(top=0)returntrue;//正好匹配

elsereturnfalse;//棧中尚有未匹配的左括號(hào)

}

25°.遞歸程序的非遞歸化

將遞歸程序轉(zhuǎn)化為非遞歸程序時(shí)常使用棧來實(shí)現(xiàn)。

26。.作業(yè)排隊(duì)

如操作系統(tǒng)中的作業(yè)調(diào)度中的作業(yè)排隊(duì)，打印機(jī)的打印作業(yè)也排成隊(duì)列。

27°.按層次遍歷二叉樹

voidLevelOrder(BinTreebt,VisitFuncvisit)

{

constintMAXSIZE=1024;//隊(duì)列容量(足夠大即可)

BinTreeq[MAXSIZE];//簡化的隊(duì)列結(jié)構(gòu)

intfront,rear;//隊(duì)頭、隊(duì)尾

if(!bt)return;

//初始化隊(duì)列，根結(jié)點(diǎn)入隊(duì)列

front=rear=0;

q[rear]二bt;

rear=(rear+l)%MAXSIZE;

//隊(duì)列不空，則取出隊(duì)頭訪問并將其左右孩子入隊(duì)列

while(front!=rear){

p=q[front];

front=(front+l)%MAXSIZE;

if(P){

visit(p->data);//訪問結(jié)點(diǎn)

q[rear]=p->lchild;

rear=(rear+1)%MAXSIZE;

q[rear]=p->rchild;

rear=(rear+1)%MAXSIZE;

第四章串

基礎(chǔ)知識(shí)和算法

概念

串，空串，空格串，串的長度；子串，子串在主串中的位置，主串；串相等。

串的基本操作

表錯(cuò)誤!文檔中沒有指定樣式的文字。.5串的基本操作

Assign(s,t),CreateAssign(s,t)將變量t賦值給s,Create(s,cs)根據(jù)字串創(chuàng)

(s,cs)建變量So

Equal(s,t),Length判斷串相等,求串長度。如Length()=0。

(s)

Concat(s,t)串連接。如Concat(“ab"，"cd")="abed”。

Substr(s,pos,len)取子串，pos為開始位置，len為子串長度。

Index(s,t)求子串t在主串s中的位置。如Index(“abc"，“ab”)=1,

Index(aabe“，“be")二3。

Replace(s,t,v)把串s中的字串t替換成Vo如Replace("aaa","aa"，"

a"）="aa”。

Delete（s,pos,len）刪除串s的一部分。____________________________________

注：完成習(xí)題集4.廣4.6。

串的存儲(chǔ)結(jié)構(gòu)

表錯(cuò)誤!文檔中沒有指定樣式的文字。.6串的存儲(chǔ)結(jié)構(gòu)__________________________

定長順序串最大長度固定，超過最大長度則作截?cái)嗵幚?/p>

堆分配存儲(chǔ)表示串的長度幾乎沒有限制

塊鏈存儲(chǔ)表示塊內(nèi)存儲(chǔ)空間連續(xù)，塊間不連續(xù)______________________________

樹和二叉樹

基礎(chǔ)知識(shí)和算法

樹及有關(guān)概念

樹，根，子樹；結(jié)點(diǎn)，結(jié)點(diǎn)的度，葉子（終端結(jié)點(diǎn)），分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)），內(nèi)部結(jié)點(diǎn),

樹的度；孩子，雙親，兄弟，祖先，子孫，堂兄弟；層次（根所在層為第1層），深度，高

度；有序樹，無序樹，二叉樹是有序樹；森林。

二叉樹

二叉樹（二叉樹與度為2的樹不同，二叉樹的度可能是0,1,2）；左孩子，右孩子。

二叉樹的五種基本形態(tài)。

二叉樹的性質(zhì)

28°.二叉樹的第i層"上至多有‘個(gè)結(jié)點(diǎn)。

29°.深度為k的二叉樹至多有2k-l個(gè)結(jié)點(diǎn)。

滿二叉樹：深度為k,有2匚1個(gè)結(jié)點(diǎn)。

完全二叉樹：給滿二叉樹的結(jié)點(diǎn)編號(hào)，從上至下，從左至右，n個(gè)結(jié)點(diǎn)的完全二叉樹中結(jié)

點(diǎn)在對應(yīng)滿二叉樹中的編號(hào)正好是從1到no

30°.葉子結(jié)點(diǎn)n0,度為2的結(jié)點(diǎn)為n2,則n0=m+l。

考慮結(jié)點(diǎn)個(gè)數(shù)：n=no+m+我

考慮分支個(gè)數(shù)：n-1=2n2+n1

可得n0=n2+l

例：1）二叉樹有n個(gè)葉子，沒有度為1的結(jié)點(diǎn)，共有一個(gè)結(jié)點(diǎn)。2）完全二叉樹的第3

層有2個(gè)葉子，則共有一個(gè)結(jié)點(diǎn)。

分析：1）度為2的結(jié)點(diǎn)有n-1個(gè)，所以共2n-l個(gè)結(jié)點(diǎn)。2）注意考慮到符合條件的二叉

樹的深度可能是3或4,所以有5、10或11個(gè)結(jié)點(diǎn)。

31°.n個(gè)結(jié)點(diǎn)的完全二叉樹深度為［log〃」+1。

32°.n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次編號(hào)

有：i的雙親是如果i=1時(shí)為根（無雙親）；

i的左孩子是2i,如果2i>n,則無左孩子；

i的右孩子是2i+1,如果2i+l>n則無右孩子。

二叉樹的存儲(chǔ)結(jié)構(gòu)

33°.順序存儲(chǔ)結(jié)構(gòu)

用數(shù)組、編號(hào)i的結(jié)點(diǎn)存放在［i-1］處。適合于存儲(chǔ)完全二叉樹。

i0本書中約定根結(jié)點(diǎn)在第1層，也有約定根在第o層的，則計(jì)算公式會(huì)有所不同.

34°.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉鏈表：

typedefstructBTNode{

DataTypedata;

structBTNode*lchild,*rchild;

}BTNode,*BinTree;

三叉鏈表：

typedefstructBTNode{

DataTypedata;

structBTNode*lchild,*rchild,"parent;

}BTNode,*BinTree;

例：用二叉鏈表存儲(chǔ)n個(gè)結(jié)點(diǎn)的二叉樹(n>0),共有(3)個(gè)空指針域；采用三叉鏈表存儲(chǔ),

共有(也)個(gè)空指針域。"

二叉樹的五種基本形態(tài)

①②③④⑤

①空樹：bt==NULL②左右子樹均空：bt->lchild==NULLandbt->rchild==NULL

③右子樹為空：bt->rchild==NULL④左子樹為空：bt->lchild==NULL

⑤左右子樹均非空。

前兩種常作為遞歸結(jié)束條件，后三者常需要遞歸。

遍歷二叉樹

35°.常見有四種遍歷方式

按層次遍歷，先序遍歷，中序遍歷，后序遍歷。

按層次遍歷：“從上至下，從左至右”，利用隊(duì)列。

先序遍歷：DLR；中序遍歷：LDR；后序遍歷LRD。

例：寫出a+b*(c-d)-e/f的前綴、中綴和后綴表達(dá)式。

畫出二叉樹，分別進(jìn)行前序、中序、后序遍歷即可得到。

前綴表達(dá)式：-+a*b-cd/ef

中綴表達(dá)式：a+b*c-d-e/f

后綴表達(dá)式：abcd-*+ef/-

36°.先序遍歷算法

voidPreorder(BinTreebt)

{

if(bt){

visit(bt->data);

11答案：(a)n+1(b)n+2,提示：只有根結(jié)點(diǎn)沒有雙親。

Preorder(bt->lchild);

Preorder(bt->rchild);

)

)

37°.中序遍歷算法

voidInorder(BinTreebt)

(

if(bt){

Inorder(bt->lchild);

visit(bt->data);

Inorder(bt->rchild);

38°.后序遍歷

voidPostorder(BinTreebt)

(

if(bt){

Postorder(bt->lchild);

Postorder(bt->rchild);

visit(bt->data);

)

)

39°.按層次遍歷

思路：利用一個(gè)隊(duì)列，首先將根(頭指針)入隊(duì)列，以后若隊(duì)列不空則取隊(duì)頭元素P，如果

P不空，則訪問之，然后將其左右子樹入隊(duì)列，如此循環(huán)直到隊(duì)列為空。

voidLevelOrder(BinTreebt)

(

//隊(duì)列初始化為空

InitQueue(Q);

//根入隊(duì)列

EnQueue(Q,bt);

//隊(duì)列不空則繼續(xù)遍歷

while(!QueueEmpty(Q)){

DeQueue(Q,p);

if(p!=NULL){

visit(p->data);

//左、右子樹入隊(duì)列

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild);

)

)

)

若隊(duì)列表示為“數(shù)組q[]+頭尾front,rear"有:

voidLevelOrder(BinTreebt)

(

constintMAXSIZE=1024;

BinTreeq[MAXSIZE];

intfront,rear;

//隊(duì)列初始化為空

front=rear=0;

//根入隊(duì)列

q[rear]=bt;rear=(rear+1)%MAXSIZE;

//隊(duì)列不空則循環(huán)

while(front!=rear){

p=q[front];front=(front+1)%MAXSIZE;

if(P){

visit(p->data);

//左、右子樹入隊(duì)列

q[rear]=p->lchild;rear=(rear+1)%MAXSIZE;

q[rear]=p->rchild;rear二(rear+1)%MAXSIZE;

}

)

)

40°,非遞歸遍歷二叉樹

一般借助棧實(shí)現(xiàn)。設(shè)想一指針沿二叉樹中序順序移動(dòng)，每當(dāng)向上層移動(dòng)時(shí)就要出棧。

(a)中序非遞歸遍歷

指針P從根開始，首先沿著左子樹向下移動(dòng)，同時(shí)入棧保存；當(dāng)?shù)竭_(dá)空子樹后需要退棧訪

問結(jié)點(diǎn)，然后移動(dòng)到右子樹上去。

voidInOrder(BinTreebt,VisitFuncvisit)

(

InitStack(S);

P=bt;

while(pII!StackEmpty(S)){

if(P){

Push(S,p);

p=p->lchild;

}else(

Pop(S,p);

visit(p);//中序訪問結(jié)點(diǎn)的位置

p=p->rchild;

)

)

)

⑹先序非遞歸遍歷

按照中序遍歷的順序，將訪問結(jié)點(diǎn)的位置放在第一次指向該結(jié)點(diǎn)時(shí)。

voidPreorder(BinTreebt,VisitFuncvisit)

InitStack(S);

P=bt;

while(pII!StackEmpty(S)){

if(P){

visit(p);//先序訪問結(jié)點(diǎn)的位置

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

p=p->rchild;

)

)

}

或者，由于訪問過的結(jié)點(diǎn)便可以棄之不用，只要能訪問其左右子樹即可，寫出如下算法。

voidPreorder(BinTreebt,VisitFuncvisit)

(

InitStack(S);

Push(S,bt);

while(!StackEmpty(S)){

Pop(S,p);

if(P){

visit(p);

Push(S,p->rchild);//先進(jìn)棧，后訪問，所以

Push(S,p->lchild);//這里先讓右子樹進(jìn)棧

)

)

)

(c)后序非遞歸遍歷

后序遍歷時(shí)，分別從左子樹和右子樹共兩次返回根結(jié)點(diǎn)，只有從右子樹返回時(shí)才訪問根結(jié)

點(diǎn)，所以增加一個(gè)棧標(biāo)記到達(dá)結(jié)點(diǎn)的次序。

voidPostOrder(BinTreebt,VisitFuncvisit)

(

InitStack(S),InitStack(tag);

P=bt;

while(pH!StackEmpty(S)){

if(P){

Push(S,p),Push(tag,1);//第一次入棧

p=p->lchild;

}else{

Pop(S,p),Pop(tag,f);

if(f==l){

//從左子樹返回，二次入棧，然后p轉(zhuǎn)右子樹

Push(S,p),Push(tag,2);

p=p->rchild;

}else{

//從右子樹返回(二次出棧)，訪問根結(jié)點(diǎn)，p轉(zhuǎn)上層

visit(p);

p=NULL;//必須的，使下一步繼續(xù)退棧

)

}

)

注：后序非遞歸遍歷的過程中，棧中保留的是當(dāng)前結(jié)點(diǎn)的所有祖先。這是和先序及中序遍

歷不同的。在某些和祖先有關(guān)的算法中，此算法很有價(jià)值。

41°.三叉鏈表的遍歷算法

下面以中序遍歷為例。

//中序遍歷三叉鏈表存儲(chǔ)的二叉樹

voidInorder(BinTreebt,VisitFuncvisit)

(

if(bt==NULL)return;//空樹，以下考慮非空樹

//找到遍歷的起點(diǎn)

p=bt;//Note:p!=nullhere

while(p->lchild)p=p->lchild;

//開始遍歷

while(p){

//訪問結(jié)點(diǎn)

visit(p);

//p轉(zhuǎn)下一個(gè)結(jié)點(diǎn)

if(p->rchild){//右子樹不空，下一個(gè)在右子樹

p=p->rchild;

while(p->lchild)p=p->lchild;//轉(zhuǎn)右子樹的最左下結(jié)點(diǎn)

}else{//右子樹為空，下一個(gè)在上層

f=p->parent;

while(p==f->rchild){//若p是右子樹則一直上溯

P=f；f=f->parent;

)

)

)

)

遍歷二叉樹的應(yīng)用

42°.寫出遍歷序列(前、中、后序)

43°.根據(jù)遍歷序列畫出二叉樹

(a)已知前序和中序序列，唯一確定二叉樹。

例：前序：ABDEGCFH,中序：DBGEAFHC,畫出二叉樹。

分析：前序序列的第一個(gè)是根，這是解題的突破口。

步驟：①前序序列的第一個(gè)是根②在中序序列中標(biāo)出根，分成左右子樹③在前序序列中

標(biāo)出左右子樹(根據(jù)結(jié)點(diǎn)個(gè)數(shù)即可)④分別對左右子樹的前序和中序序列重復(fù)以上步驟直

至完成。

(b)已知后序和中序序列，唯一確定二叉樹。

例：后序:DGEBHFCA,中序：DBGEAFHC,畫出二叉樹。

分析：后序序列的最后一個(gè)是根，這是解題的突破口。

步驟：①后序序列的最后一個(gè)是根②在中序序列中標(biāo)出根，分成左右子樹③在后序序列

中標(biāo)出左右子樹(根據(jù)結(jié)點(diǎn)個(gè)數(shù)即可)④分別對左右子樹的后序和中序序列重復(fù)以上步驟

直至完成。

(c)已知前序和后序序列，不存在度為1的結(jié)點(diǎn)時(shí)能唯一確定二叉樹。

例：前序：ABDEC,后序：DEBCA,畫出二叉樹。又前序AB,后序BA則不能唯一確定二叉樹。

注：對于不存在度為1的結(jié)點(diǎn)的二叉樹，首先確定根結(jié)點(diǎn)，然后總可以將其余結(jié)點(diǎn)序列劃

分成左右子樹，以此類推即可確定二叉樹。

說明：畫出二叉樹后可以進(jìn)行遍歷以便驗(yàn)證。

44°.編寫算法

思路：按五種形態(tài)(①一⑤)分析，適度簡化。

例：求二叉樹結(jié)點(diǎn)的個(gè)數(shù)。

分析：①0;②1;③L+1;④1+R;⑤1+L+R。

簡化：②l+Lo+Rs③1+L+R-o④1+U+R⑤1+L+R可合并成⑤一種情況。

intNodeCount(BinTreebt)

(

if(bt==O)return0;

elsereturn1+NodeCount(bt->lchild)+NodeCount(bt->rchiId);

)

例：求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)。

分析：①0；②1；③L;④R;⑤L+Ro簡化：③④⑤可合并成⑤。

intLeafCount(BinTreebt)

(

if(bt-0)return0;

elseif(bt->lchild—0andbt->rchild-0)return1;

elsereturnLeafCount(bt->lchild)+LeafCount(bt->rchiId);

)

例：求二叉樹的深度。

分析：①0；②1；③1+L;④1+R;⑤l+max(L,R)。簡化：②③④⑤可合并成⑤。

intDepth(BinTreebt)

(

if(bt—0)return0;

elsereturn1+max(Depth(bt->lchiId),Depth(bt->rchiId));

)

線索二叉樹

45°.線索

n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空指針，可以利用其指向前驅(qū)或后繼結(jié)點(diǎn)，叫線索，同時(shí)需

附加一個(gè)標(biāo)志，區(qū)分是子樹還是線索。

Ichild?tagdatartagrchild

*0/10/1

Ichild有左子樹，則指向左子樹，標(biāo)志Itag==0；

沒有左子樹，可作為前驅(qū)線索，標(biāo)志Itag==1。

rchild有右子樹，則指向右子樹，標(biāo)志rtag==0：

沒有右子樹，可作為后繼線索，標(biāo)志rtag==lo

46°.線索化二叉樹

利用空指針作為線索指向前驅(qū)或后繼。左邊空指針可以作為前驅(qū)線索，右邊空指針可以作

為后繼線索，可以全線索化或部分線索化。

表錯(cuò)誤!文檔中沒有指定樣式的文字。.7線索化二叉樹的類型

前驅(qū)、后繼線索