數(shù)據結構C語言版復習攻略

第一章：緒論

一、基礎知識

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

另外，注意：

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

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

3、數(shù)據結構及其形式定義。P5

四種基本結構：①集合②線性結構③樹形結構④圖(網)狀結構

4、數(shù)據結構的

邏輯結構(抽象的，與實現(xiàn)無關)

物理結構(存儲結構)順序映像(順序存儲結構)位置“相鄰”

非順序映像(鏈式存儲結構)指針表示關系P6

5、數(shù)據類型P7

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

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

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

6、算法的概念P13

7、算法的五個特征

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

8、算法設計的要求：①正確性②可讀性③健壯性④效率與低存儲量

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

9、算法的時間復雜度P15

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

語句頻度，用歸納法計算。

10、算法的空間復雜度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分析算法的時間復雜度時，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）考試中要求寫算法時，可用類C,也可用C程序。

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

c）技巧：用“邊界值驗證法”檢查下標越界錯誤。

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

d）時間復雜度為0（r）,第3個在最好情況下（待排記錄有序），時間復雜度為0（n）。

第二章、線性表

一、基礎知識和算法

1、線性表及其特點

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

線性結構的特點：①“第一個”②“最后一個”③前驅④后繼。z

2、順序表一線性表的順序存儲結構

（1）特點：a）邏輯上相鄰的元素在物理位置上相鄰。b）隨機訪問。

（2）類型定義

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

constintMAXSIZE=線性表最大長度；

typedefstruct{

DataTypeelem[MAXSIZE];

intlength;

}SqList;

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

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

c）MAXSIZE根據需要確定。如

constintMAXSIZE=64;

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

e）課本上的SqList類型定義中l(wèi)istsize表示已經分配的空間大小（容納數(shù)據元素的個

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

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

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

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

中。

（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++中對應于下標i-K

3°.步驟

第i至最后所有元素后移一個元素

在第i個位置插入元素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為下標，從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個元素

第i個元素之后的元素向前移動一個位置

表長減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)算法分析

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

插入刪除

基本操作移動元素移動元素

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

〃乙,=i\2

時間復雜度0(n)0(n)

尾端操作插入第n+1個元素,不移動刪除第n個元素，不移動

插入、刪除需移動大量元素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];

單鏈表一一線性表的鏈式存儲結構之一

(6)概念

線性鏈表，單鏈表，結點；數(shù)據域，指針域；頭指針，頭結點。

(7)特點

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

(8)類型定義

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

typedefstructLNode{

DataTypedata;datanext

structLNode*next;

}LNode,*LinkList;

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

帶頭結點的單鏈表的基本形態(tài)有:

1°.單鏈表空

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

2°.單鏈表不空

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

(10)基本算法(遍歷)

1°.順序訪問所有元素

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

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

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

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

p=p->next;〃指針沿著鏈表向后移動

)

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

voidPrintLinkList(LinkListL)

(

p=L->next;

while(p!=NULL){

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

p=p->next;

}

)

2°.查找元素x

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

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

//若找到，返回指向該結點的指針；否則返回空指針

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++;//計數(shù)器隨指針改變

)

return0;//未找到

前一個算法的另一種寫法：

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個元素

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個元素

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個元素

若找到，在其后插入新結點

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

//查找第iT個元素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個而不是第i個元素(否則，不容易找到前驅以便插入)。

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

仍然可以插入第i個元素。

c)新建結點時需要動態(tài)分配內存。

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

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

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

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

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

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

思路：

先查找第iT個元素

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

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

(刪除前

//查找第iT個元素p

p=L;j=0;

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

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

}

〃若存在第i個元素，則用x返回數(shù)據，并刪除之

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

s=p->next;//①

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

x=s->data;

free(s);

returntrue;

)

else

returnfalse;

)

注意：

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

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

i個元素存在，否則無法刪除。若寫成p->next&&j==i-l也不妥，因為此時(循環(huán)結束時)

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

也不可以寫成p->next&&p&&j==iT,因為先有p!=0才有p->next,上式顛倒了這一關

系。

c)釋放結點的方法。free(s);

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

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

思路：

建立空表(頭結點)；

依次插入數(shù)據結點(每次插入表尾得⑶,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)特點

最后一個結點的指針指向頭結點。

(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)特點

一個結點包含指向后繼(next)和指向前驅(prior)兩個指針，兩個方向又分別構成循環(huán)鏈

表。

(19)類型定義

typedefstructDuLNode{

DataTypedata;

structDuLNode*prior,*next;〃兩個priddata指針

}DuLNode,*DuLinkList;

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

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

非空表。

I

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

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

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

插入和刪除時需要修改兩個方向的指針。

(22)插入和刪除

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

表錯誤!文檔中沒有指定樣式的文字。.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;

順序表與單鏈表的比較

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

順序表單鏈表

以地址相鄰表示關系用指針表示關系

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

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

位置)

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

第三章、棧和隊列

棧

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

順序棧：棧的順序存儲結構；鏈棧：棧的鏈式存儲結構。

鏈棧

存儲結構

用不帶頭結點的單鏈表實現(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)

(

//新建結點

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;

)

順序棧

存儲結構

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

類型定義

簡單說，“數(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不準確的說法，只為便于理解和記憶，不要在正式場合引用。

12°.棧頂元素

前提：棧非空

s.elem[top-l]即是。

隊列

隊列，隊頭，隊尾，空隊列，先進先出(FIFO)。

鏈隊列：隊列的鏈式存儲結構。

循環(huán)隊列：隊列的順序存儲結構之一。

鏈隊列

存儲結構

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

類型定義

課本P61.

typedefstruct{Q.front

LinkListfront;

Q.rear

LinkListrear;

}LinkQueue;Q.frontaia?-*anA

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

基本形態(tài)

隊列空：Q.front==Q.rear。

非空隊列。

基本算法

13°.入隊列

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

14°.出隊列

課本P62。刪除隊頭元素，

特別注意：如果隊列中只有一個元素，則隊頭也同時是隊尾，刪除隊頭元素后也需要修改

隊尾指針。

循環(huán)隊列

存儲結構

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

類型定義

constintMAXSIZE=隊列最大容量；

typedefstruct{

DataTypeelem[MAXSIZE];

intfront,rear;//隊頭、隊尾位置

}SqQueue;

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

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

基本形態(tài)

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

置,rear指向隊尾的下一個位置，隊列內容為［front,rear)?

15°.隊列空

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

不能出隊列。

16°.隊列滿

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

不能入隊列。

17°.隊列不空也不滿

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

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

隊列空：Q.front==Q.rearandQ.tag==0；隊列滿：Q.front==Q.rearandQ.tag==l?

基本算法

19°.入隊列

前提：隊列不滿。

boolEnQueue(SqQueue&Q,DataTypex)

{

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

//入隊列

Q.elem[Q.rear]=x;

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

returntrue;

)

20°.出隊列

前提：隊列非空。

boolDeQueue(SqQueue&Q,DataType&x)

(

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

//出隊列

x=Q.elem[Q.front];

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

returntrue;

)

21°.隊列中元素個數(shù)

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

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

intQueueLength(SqQueueQ)

(

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

)

22°.用標志區(qū)分隊列空和滿

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

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;//隊列非空

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;//隊列空

returntrue;

)

intQueueLength(SqQueueQ)

(

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

returnMAXSIZE;//隊列滿

else

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

)

棧和隊列比較

都是線形結構，棧的操作LIFO(后進先出)，隊列操作FIFO(先進先出)。

簡化的棧和隊列結構

在算法中使用棧和隊列時可以采用簡化的形式。

表錯誤!文檔中沒有指定樣式的文字。"簡化的棧和隊列結構

簡化棧簡化隊列

結構“S口+top”結構“q口+front+rearff

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

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

rear=(rear+l)%MAXSIZE;

出棧X=s[--top];出隊列x=q[front];

front二(front+l)%MAXSIZE;

棧頂s[top-1]隊列頭q[front]

?？誸op==0隊列空front==rear

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

棧和隊列的應用

23°.表達式求值

參見課本P53o

24°.括號匹配

例：檢查表達式中的括號是否正確匹配。如｛（）[]｝正確，（[）]｝則錯誤。

分析：每個左括號都“期待”對應的右括號，匹配成功則可以消去。

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

失敗。當然，如果棧中沒有括號可以匹配,或者最后棧中還有未匹配的左括號，也都是匹

配錯誤。

//檢查輸入的表達式中括號是否匹配

boolMatchBrackets()

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

chars[MAXSIZE];//簡化的棧結構

inttop;//棧頂

//棧初始化

top=0;

//檢查括號是否匹配

ch=getchar();

while(ch!=E0F){

switch(ch){

case'(，['

s[top++]=ch//所有左括號入棧

break;

case')':

if(top==0ors[-top]!=,('）returnfalse;//?？栈蛴依ㄌ柵c棧頂

左括號失配

case:

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

case:

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

)

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

)

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

elsereturnfalse;//棧中尚有未匹配的左括號

}

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

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

26。.作業(yè)排隊

如操作系統(tǒng)中的作業(yè)調度中的作業(yè)排隊，打印機的打印作業(yè)也排成隊列。

27°.按層次遍歷二叉樹

voidLevelOrder(BinTreebt,VisitFuncvisit)

{

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

BinTreeq[MAXSIZE];//簡化的隊列結構

intfront,rear;//隊頭、隊尾

if(!bt)return;

//初始化隊列，根結點入隊列

front=rear=0;

q[rear]二bt;

rear=(rear+l)%MAXSIZE;

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

while(front!=rear){

p=q[front];

front=(front+l)%MAXSIZE;

if(P){

visit(p->data);//訪問結點

q[rear]=p->lchild;

rear=(rear+1)%MAXSIZE;

q[rear]=p->rchild;

rear=(rear+1)%MAXSIZE;

第四章串

基礎知識和算法

概念

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

串的基本操作

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

Assign(s,t),CreateAssign(s,t)將變量t賦值給s,Create(s,cs)根據字串創(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的一部分。____________________________________

注：完成習題集4.廣4.6。

串的存儲結構

表錯誤!文檔中沒有指定樣式的文字。.6串的存儲結構__________________________

定長順序串最大長度固定，超過最大長度則作截斷處理

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

塊鏈存儲表示塊內存儲空間連續(xù)，塊間不連續(xù)______________________________

樹和二叉樹

基礎知識和算法

樹及有關概念

樹，根，子樹；結點，結點的度，葉子（終端結點），分支結點（非終端結點），內部結點,

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

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

二叉樹

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

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

二叉樹的性質

28°.二叉樹的第i層"上至多有‘個結點。

29°.深度為k的二叉樹至多有2k-l個結點。

滿二叉樹：深度為k,有2匚1個結點。

完全二叉樹：給滿二叉樹的結點編號，從上至下，從左至右，n個結點的完全二叉樹中結

點在對應滿二叉樹中的編號正好是從1到no

30°.葉子結點n0,度為2的結點為n2,則n0=m+l。

考慮結點個數(shù)：n=no+m+我

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

可得n0=n2+l

例：1）二叉樹有n個葉子，沒有度為1的結點，共有一個結點。2）完全二叉樹的第3

層有2個葉子，則共有一個結點。

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

樹的深度可能是3或4,所以有5、10或11個結點。

31°.n個結點的完全二叉樹深度為［log〃」+1。

32°.n個結點的完全二叉樹，結點按層次編號

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

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

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

二叉樹的存儲結構

33°.順序存儲結構

用數(shù)組、編號i的結點存放在［i-1］處。適合于存儲完全二叉樹。

i0本書中約定根結點在第1層，也有約定根在第o層的，則計算公式會有所不同.

34°.鏈式存儲結構

二叉鏈表：

typedefstructBTNode{

DataTypedata;

structBTNode*lchild,*rchild;

}BTNode,*BinTree;

三叉鏈表：

typedefstructBTNode{

DataTypedata;

structBTNode*lchild,*rchild,"parent;

}BTNode,*BinTree;

例：用二叉鏈表存儲n個結點的二叉樹(n>0),共有(3)個空指針域；采用三叉鏈表存儲,

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

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

①②③④⑤

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

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

⑤左右子樹均非空。

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

遍歷二叉樹

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

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

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

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

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

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

前綴表達式：-+a*b-cd/ef

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

后綴表達式：abcd-*+ef/-

36°.先序遍歷算法

voidPreorder(BinTreebt)

{

if(bt){

visit(bt->data);

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

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°.按層次遍歷

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

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

voidLevelOrder(BinTreebt)

(

//隊列初始化為空

InitQueue(Q);

//根入隊列

EnQueue(Q,bt);

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

while(!QueueEmpty(Q)){

DeQueue(Q,p);

if(p!=NULL){

visit(p->data);

//左、右子樹入隊列

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild);

)

)

)

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

voidLevelOrder(BinTreebt)

(

constintMAXSIZE=1024;

BinTreeq[MAXSIZE];

intfront,rear;

//隊列初始化為空

front=rear=0;

//根入隊列

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

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

while(front!=rear){

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

if(P){

visit(p->data);

//左、右子樹入隊列

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

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

}

)

)

40°,非遞歸遍歷二叉樹

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

(a)中序非遞歸遍歷

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

問結點，然后移動到右子樹上去。

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);//中序訪問結點的位置

p=p->rchild;

)

)

)

⑹先序非遞歸遍歷

按照中序遍歷的順序，將訪問結點的位置放在第一次指向該結點時。

voidPreorder(BinTreebt,VisitFuncvisit)

InitStack(S);

P=bt;

while(pII!StackEmpty(S)){

if(P){

visit(p);//先序訪問結點的位置

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

p=p->rchild;

)

)

}

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

voidPreorder(BinTreebt,VisitFuncvisit)

(

InitStack(S);

Push(S,bt);

while(!StackEmpty(S)){

Pop(S,p);

if(P){

visit(p);

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

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

)

)

)

(c)后序非遞歸遍歷

后序遍歷時，分別從左子樹和右子樹共兩次返回根結點，只有從右子樹返回時才訪問根結

點，所以增加一個棧標記到達結點的次序。

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轉右子樹

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

p=p->rchild;

}else{

//從右子樹返回(二次出棧)，訪問根結點，p轉上層

visit(p);

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

)

}

)

注：后序非遞歸遍歷的過程中，棧中保留的是當前結點的所有祖先。這是和先序及中序遍

歷不同的。在某些和祖先有關的算法中，此算法很有價值。

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

下面以中序遍歷為例。

//中序遍歷三叉鏈表存儲的二叉樹

voidInorder(BinTreebt,VisitFuncvisit)

(

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

//找到遍歷的起點

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

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

//開始遍歷

while(p){

//訪問結點

visit(p);

//p轉下一個結點

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

p=p->rchild;

while(p->lchild)p=p->lchild;//轉右子樹的最左下結點

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

f=p->parent;

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

P=f；f=f->parent;

)

)

)

)

遍歷二叉樹的應用

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

43°.根據遍歷序列畫出二叉樹

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

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

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

步驟：①前序序列的第一個是根②在中序序列中標出根，分成左右子樹③在前序序列中

標出左右子樹(根據結點個數(shù)即可)④分別對左右子樹的前序和中序序列重復以上步驟直

至完成。

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

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

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

步驟：①后序序列的最后一個是根②在中序序列中標出根，分成左右子樹③在后序序列

中標出左右子樹(根據結點個數(shù)即可)④分別對左右子樹的后序和中序序列重復以上步驟

直至完成。

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

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

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

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

說明：畫出二叉樹后可以進行遍歷以便驗證。

44°.編寫算法

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

例：求二叉樹結點的個數(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);

)

例：求二叉樹葉子結點的個數(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個結點的二叉鏈表中有n+1個空指針，可以利用其指向前驅或后繼結點，叫線索，同時需

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

Ichild?tagdatartagrchild

*0/10/1

Ichild有左子樹，則指向左子樹，標志Itag==0；

沒有左子樹，可作為前驅線索，標志Itag==1。

rchild有右子樹，則指向右子樹，標志rtag==0：

沒有右子樹，可作為后繼線索，標志rtag==lo

46°.線索化二叉樹

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

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

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

前驅、后繼線索