自考02142數據結構導論串講筆記

第一張概論

1.1引言

兩項基本任務：數據表示，數據處理

軟件系統生存期：軟件計劃，需求分析，軟件設計，軟件編碼，軟件測試，軟件維護

由一種邏輯結構和一組基本運算構成的整體是實際問題的一種數學模型，這種數學模型的建立，選擇和實現是數

據結構的核心問題。

機外表示——邏輯結構——存儲結構

處理要求一一基本運算和運算------算法

1.2數據，邏輯結構和運算

數據：凡是能夠被計算機存儲，加工的對象通稱為數據

數據元素：是數據的基本單位，在程序中作為一個整體加以考慮和處理。又稱元素，頂點，結點，記錄。數據項：

數據項組成數據元素，但通常不具有完整確定的實際意義，或者不被當做一個整體對待。又稱字段或者域，是數據不

可分割的最小標示單位。

1.2.2數據的邏輯結構

邏輯關系：是指數據元素之間的關聯方式，又稱“鄰接關系”

邏輯結構：數據元素之間邏輯關系的整體稱為邏輯結構。即數據的組織形式。

四種基本邏輯結構：

1集合：任何兩個結點間沒有邏輯關系，組織形式松散

2線性結構：結點按邏輯關系挨次羅列成一條“鎖鏈”

3樹形結構：具有分支，層次特性，形態(tài)像自然界中的樹

4.圖狀結構：各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接。

注意點：

1.邏輯結構與數據元素本身的形式，內容無關。

2.邏輯結構與數據元素的相對位置無關

3.邏輯結構與所含結點個數無關。

運算：運算是指在任何邏輯結構上施加的操作，即對邏輯結構的加工。

加工型運算：改變了原邏輯結構的“值”，如結點個數，結點內容等。

引用型運算:不改變原邏輯結構個數和值，只從中提取某些信息作為運算的結果。

引用：查找，讀取

加工：插入，刪除，更新

同一邏輯結構S上的兩個運算A和B,A的實現需要或者可以利用B,而B的實現不需要利用A,則稱A可以歸約

為B。

假如X是S上的一些運算的集合，丫是X的一個子集，使得X中每一運算都可以規(guī)約為Y中的一個或者多個運算，

而Y中任何運算不可規(guī)約為別的運算，則稱Y中運算（相對于X）為基本運算。

將邏輯結構S和在S上的基本運算集X的整體（S,X）稱為一個數據結構。數據結構包括邏輯結構和處理方式。

1.3存儲實現和運算實現

由于邏輯結構是設計人員根據解題需要選定的數據組織形式，因此存儲實現建立的機內表示應遵循選定的邏輯結

構。另一方面，由于邏輯結構不包括結點內容即數據元素本身的表示，因此存儲實現的另一主要內容是建立數據元素

的機內表示。按上述思路建立的數據的機內表示稱為數據的存儲結構。

存儲結構包括三部份：

1.存儲結點，每一個存儲結點存放一個數據元素。

2.數據元素之間關聯方式的表示，也就是邏輯結構的機內表示。

3.附加設施，如方便運算實現而設置的“啞結點”等。

四種基本存儲方式：

1.順序存儲方式：每一個存儲結點只含一個數據元素。所有存儲結點相繼存放在一個連續(xù)的存儲區(qū)里。用存儲結

點間的位置關系表述數據元素之間的邏輯關系。

2.鏈式存儲方式：每一個存儲結點不僅含有一個數據元素，還包含一組指針。每一個指針指向一個與本結點有邏

輯關系的結點，即用附加的指針表示邏輯關系。

3.索引存儲方式：每一個存儲結點只含一個數據元素，所有存儲結點連續(xù)存放。此外增設一個索引表，索引指示

各存儲結點的存儲位置或者位置區(qū)間端點。

4.散列存儲方式：每一個結點含一個數據元素，各個結點均勻分布在存儲區(qū)里，用散列函數指示各結點的存儲位

置或者位置區(qū)間端點。

1.3.2運算實現

運算只描述處理功能，不包括處理步驟和方法；運算實現的核心是處理步驟的規(guī)定，即算法設計。

算法：算法規(guī)定了求解給定問題所需的所有處理步躲及其執(zhí)行順序，使得給定類型的任何問題能在有限時間內

被機械的求解。

算法分類：

1：運行終止的程序可執(zhí)行部份：又稱為程序

2:偽語言算法：不可以直接在計算機上運行，但容易編寫和閱讀。

3：非形式算法：用自然語言，同時可能還使用了程序設計語言或者偽語言描述的算法。

1.4算法分析

算法質量評價指標：

1.正確性：能夠正確實現處理要求

2.易讀性：易于閱讀和理解，便于調試，修改和擴充

3.茁壯性：當環(huán)境發(fā)生變化，算法能夠適當做出反應或者處理，不會產生不需要的運行結果

4.高效率：達到所需要的時空性能。

如何確定一個算法的時空性能，稱為算法分析

一個算法的時空性能是指該算法的時間性能和空間性能，前者是算法包含的計算量，后者是算法需要的存儲量。

算法在給定輸入下的計算量：

1.根據該問題的特點選擇一種或者幾種操作作為“標準操作”。

2.確定每一個算法在給定輸入下共執(zhí)行了多少次標準操作，并將此次數規(guī)定為該算法在給定輸入下的計算量。

若無特殊說明，將默認以賦值語句作為標準操作。

最壞情況時間復雜性：算法在所有輸入下的計算量的最大值作為算法的計算量平均時間復雜性：算法在所有輸入下

的計算量的加權平均值作為算法的計算量。

算法的輸入規(guī)模（問題規(guī)模）是指作為該算法輸入的數據所含數據元素的數目，或者與此數目有關的其他參

數。

常見時間復雜性量級：

1.常數階：o(D即算法的時間復雜性與輸入規(guī)模N無關或者N恒為常數。

2.對數階：01og2N

3.線性階：0(N)

4.平方階：0(N2)

5.指數階：0(2N次方)

通常認為指數階量級的算法實際是不可計算的，而量級低于平方階的算法是高效率的

第二章線性表

2.1線性表的基本概念

線性結構：線性結構是N(N大于等于0)個結點的有窮序列。

AI稱為Ai+1的直接前趨，Ai+1稱為Ai的直接后繼。為滿足運算的封閉性，通常允許一種邏輯結構出現不含

任何結點的情況。不含任何結點的線性結構記為()或者

線性結構的基本特征：若至少含有一個結點，則除起始節(jié)點沒有直接前趨外，其他結點有口惟獨一個直接前趨，

除終端結點沒有直接后繼外，其他結點有且惟獨一個直接后繼。

2.1.2線性表

線性表的邏輯結構是線性結構。所含結點個數稱為線性表的長度(表長)。表長為0的是空表。線性表的基本

運算：

1.初始化initiate(L)：加工型運算，其作用是建立一個空表L=。

2.求表長length(L)：引用型運算，其結果是線性表L的長度。

3.讀表元get(L,i)：引用型運算。若1小于等于i小于等于length(L),其結果是L的第i個結點，

否則為一特殊值。

4.定位(按值查找)locate(L,X)：引用型運算。若L中存在一個或者多個值與X相等，結果為這些結

點的序號最小值，否則，運算結果為0。

5.插入insert(L,Xi)加工型運算。在L的第i個位置上增加一個值為X的新結點，參數i的合法取值

范圍是1—L+lo

6.刪除delete(L,i)：加工型運算。撤銷L的第i個結點ai,i的合法取值范圍是1--N。

2.2線性表的順序實現

2.2.1順序表

順序表是線性表的順序存儲結構，即按順序存儲方式構造的存儲結構。

順序表基本思想：

順序表的一個存儲結點存儲線性表的一個結點的內容，即數據元素(不含其他信息)，所有存儲結點按相應數

據元素間的邏輯關系決定的次序挨次羅列。

順序表的特點：邏輯結構中相鄰的結點在存儲結構中仍相鄰。

順序表的類C語言描述：P17

Constmaxsize=順序表的容量

Typedefstruct

(datatypedate[maxsize]

Intlast;

}sqlist;

SqlistL;

L表示線性表的長度，lastT是終端結點在順序表中的位置。常數maxsi/e為順序表的容量。表長L.last,終端

結點L.data[L.last-1]

2.2.2基本運算在順序表上的實現

1.插入

Voidinset_sqlist(sqlistL,datatypex,inti)

(if(L.sta==maxsize)error('表滿')；/*溢出*/

If(((i<l)!!(i>L.last+D)error('非法位置')；

For(j=L.last;j=I;j—)

L.data[j]=L.data[j-1];/*挨次后移*/

L.data[i-l]=x;/*置入*/

L.last-L.last+1/*修改表長*/

)

2.刪除

Voiddelete_sqlist(sqlistL,int/*)刪除順序表L中第i個位置上的結點*/

(

If((i<l)!!(I>L.last))error('非法位置')；

For(j=i+1;j=L.last;j++)

L.data[j-2]=L.data[j-1]/*挨次前移,注意第一個L.data[j-2存放ai*/L.last=L.last-1/*修

改表長*/

3.定位

Intlocate_sqlist(sqlistL,datatypeX)

/*在順序表中從前往后查找第一個值等于X的結點。若找到則回傳該結點序號，否則回傳0*/

(

1=1；

While((i<=L.last)&&(L.data[i-l]!=x)/)注意：ai在L.data[i_l]"*/

i++;/*從前往后查找*/

if(i<=L.last)return(i)

elsereturn(0)

)

2.2.3順序實現的算法分析

插入:平均時間復雜性：=n/2

平均時間復雜性量級為0(n)

刪除：平均時間復雜性：n-1/2

平均時間復雜性量級：0(n)

定位：平均時間復雜性量級：0(n)

求表長，讀表元：量級0(1)

以上分析得知：順序表的插入，刪除算法的時間性能方面是不理想的。

2.3線性表的鏈接實現

順序表的優(yōu)缺點：

優(yōu)點：1。無需為表示結點間的邏輯關系而增加額外的存儲空間。

2.可以方便地隨機存取表中的任一結點。

缺點：1。插入，刪除運算不方便，除表尾位置外，其他位置上進行插入和刪除操作都必須挪移大量結點，效率

較低。

2.由于順序表要求占用連續(xù)的空間，存儲分配職能預先進行(靜態(tài)分配)，因此當表長變化較大時，可

能造成空間長期閑置或者空間不夠而溢出。

鏈表：采用鏈接方式存儲的線性表稱為鏈表

一種數據結構的鏈接實現是指按鏈式存儲方式構建其存儲結構，并在此鏈式存儲結構上實現其基本運算。

2.3.1單鏈表

單鏈表表示法的基本思想：用指針表示結點間的邏輯關系。

一個存儲結點包含兩部份：

data部份：稱為數據域，用于存儲線性表的一個數據元素。

Next部份：稱為指針域或者鏈域，用于存放一個指針，指向本結點所含數據元素的直接后繼所在的結點

終端結點的指針NULL稱為空指針，不指向任何結點，只起標志作用。

Head稱為頭指針變量，指向單鏈表的第一個結點的，稱為頭指針。

頭指針具有標識單鏈表的作用，故常用頭指針變量來命名單鏈表.

單鏈表的類C語言描述：

Typedefstructnode*pointer;

Structnode

{datatypedata;

Pointernext;

};

TypedefpointerIklist;

2.3.2單鏈表的簡單操作

為了便于實現各種運算，通常在單鏈表第一個結點前增設一個類型相同的結點，稱為頭結點。其他結點稱為表結

點。表結點中第一個和最后一個稱為首結點和尾結點。頭結點的數據域可以不存儲任何信息，也可以存放一個特殊標

志或者表長。

1初始化：

Lklistinitiate_lklist(*建立一個空表*/

(

t二malloc(size);

t->next=NULL;

return(t);)

此算法說明的問題：

1.語句t=malloc(size);有雙重作用：1由malloc自動生成一個類型為node的新結點。2指針型變量t得到

一個值即指針，該指針指向上述新結點。

2.要生成新結點必須通過調用malloc才干實現。

3.語句t->next=NULL的作用是將頭結點*t的鏈域置為NULL。

4.為了建立一個空表，可定義一個lklist類型的變量head,并通過調用head=initiate_lklist使head成為

指向一個空表的頭指針。

2求表長

Intlength_lklist(lklisthead)/*求表head的長度，P是pointer類型的變量*/

{p=head;

>0;

While(p->next!=NULL)

(p=p->next;

J++;)

Return(j);)

3按序號查找

Pointerfind_lklist(Iklisthead,int在單鏈表head中查找第i個結點。若找到則回傳指向該結點的指

針，否則回傳null*/

(P=head;j=0;

While(p->next!=NULL)&&(j<i)

(p=p->next;j++;)

If(i==j)return(p);

Elsereturn(NULL);)

4定位

Intlocate_lklist(Iklisthead,datatypex)

(P=head;j=0;

While((p->next!=NULL)&&(p->data!=x))

(p=p->next;j++;}

Tfp->data==xreturn(j);

Elsereturn(0);

}

5刪除

Voiddelete_lklist(Iklisthead,inti)

(p=find_lklist(head,iT)/*調用按序號查找算法*/

If((p!=NULL)&&(p->next!=NULL))

(q=p->next;

p->next=q->next;

free(q);}

elseerror('不存在第個結點')}

free是庫函數，結果是釋放q所指結點占用的內存空間，同時q的值變成無定義。

6插入

Voidinsert_lklist(Iklisthead,datatypedx,inti)

(

P=find_lklist(head,i~l);

If(p==NULL)

Error('不存在第i個位置')

Else

(s=malloc(size);s->data=x;

s->next=p->next;

p->next=s;}

2.5其他鏈表

循環(huán)鏈表

尾結點的鏈域值不是NULL,而是指向頭結點的指針。優(yōu)點是從任一結點出發(fā)都能通過后移操作而掃描整個循環(huán)鏈

表。

但為找到尾結點，必須從頭指針出發(fā)掃描表中所有結點。改進的方法是不設頭指針而改設尾指針。這樣，頭結點

和尾結點的位置為：rear->next->next和rear.

雙鏈表：在每一個結點中增加一個指針域，所含指針指向前趨結點。

雙鏈表的摘除*P的操作：p->prior->next=p->next;p->next->prior=p->prior;

鏈入操作：P后面鏈入*q:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

2.6順序實現與鏈接實現的比較

空間性能的比較：

存儲結點中數據域占用的存儲量與整個存儲結點占用存儲量之比稱為存儲密度。順序表=1,鏈表<1,所有順序

表空間利用率高。但順序表要事先估計容量，有時造成浪費。

時間性能的比較：

一種實現的時間性能是指該實現中包含的算法的時間復雜性。

定位：順序表和鏈表都是0(n)

讀表元：順序表0(1),鏈表0(n),故當需要隨機存取時，不宜采用鏈表。

摘除，鏈入：順序表0(n),鏈表。(1),時常需要插入刪除時不宜采用順序表。

2.7串

串是由零個或者多個字符組成的又窮序列。含零個字符的串稱為空串。串中所含字符的個數稱為該串的長度。兩

個串徹底一樣時稱為相等的。串中任意個連續(xù)字符組成的子序列稱為該串的子竄，該竄稱為主竄。

字符串常量按字符數組處理，它的值在執(zhí)行過程中不能改變。串變量與其他變量不一樣，不能由賦值語句賦值。

串的基本運算：

1.賦值：ASSIGNS,T):加工型運算。將串變量或者串常量的值傳給串變量。

2.判等：EQUALS,T):引用型運算，若相等返回1,否則返回0。

3.求長：LENGTH(S):引用型運算

4.聯接：CONCAT(S,T):引用型運算。運算結果是聯接在一起形成的新串。

5.求子串：SUBSTR(S,I,j):引用型運算：結果是串S中從第i個字符開始，由連續(xù)j個字符組成的子串。當I,

參數超過范圍時，運算不能執(zhí)行，也沒有結果。

6.插入：INSERTS,I,S2):加工型運算。將串2整個插到$1的第i個字符之后從而產生一個新串。

7.刪除DELETE(S,I,J)加工型運算。從串S中刪去第I個字符開始的長度為J的子串。

8.定位：INDEX(S,T):引用型運算。若串S中存在一個與T相等的子串。則結果為S中第一個這樣的子串的第

一個字符在S中的位置，否則，結果為0。(要求T不是空串)

9.替換：REPLACES,T,R)加工型運算。在S中處處同時以串R置換T的所有浮現所得的新串。

串的存儲：

1.串的順序存儲：緊縮格式，非緊縮格式

2.串的鏈接存儲：將串中每一個存儲結點存儲的字符個數稱為結點大小。結點為1時存儲密度低但操作方便，

大于1時存儲密度高但操作不方便。

第三章棧，隊列和數組

3.1棧

棧是一種特殊的線性表，棧上的插入刪除操作限定在表的某一端進行，稱為棧頂。另一端稱為棧底。不含任何元素

的棧稱為空棧。

棧又稱為先進后出線性表。在棧頂進行插入運算，被稱為進棧，刪除被稱為出棧。

棧的基本運算:

1.初始化：Init$tack(S)加工型運算，設置一個空棧$.

2.進棧：push(S,X)加工型運算，將元素X插入S中，使X稱為棧頂元素。

3.退棧：pop6)加工型運算，當棧不空時，從棧中刪除當前棧頂。

4.讀棧頂：top(S):引用型運算，若S不空，由X返回棧頂元素，S為空時，結果為一特殊標志。

5.判?？誩mpty(S)：引用型運算，若S為空棧，結果為1,否則為0

3.1.2棧的順序實現

順序棧由一個一維數組和一個記錄棧頂位置的變量組成。

空棧中進行出棧操作，發(fā)生下溢，滿棧中進行入棧操作，發(fā)生上溢。

類C語言定義：

#definesqstackmaxsize6/*6是棧的容量*/

Typedefstructsqstack

(DataTypedada[sqstackmaxsize];

Inttop;

}SqStackTP;

棧的基本運算的實現：

1.初始化

IntInitStack(InitStackTp*sq)

(sq->top=0;

Return(1);)

2.進棧

Intpush(sqstackTp*sq,datatypex)

(if(s->top==sqstackmaxsize-1)

(error("棧滿")；return0;)

Else(sq-top++;

Sq->data[sq->top]=x;

Return(1);)

3退棧

Intpop(sqstackTp*sq,datatype*x)

(if(sq->top==0)

(error(下溢")；return(0);)

Else(*x=sq->data[sq->top];

Sq->top一;

Return⑴；)

4判?？?/p>

Intemptystack(stackTp*sq)

(ifsq->top==0)

Return(1);

Elsereturn(0);)

5取棧頂元素

Intgettop(sqstackTp*sq,datatype*x)

(if(sq->top=0)return(0);

Else(*x=sq->data[sq->top];

Return(1);)

3.1.3棧的鏈接實現

鏈棧由棧頂指針I(yè)s惟一確定。棧中其他結點通過他們的next域鏈接起來。棧底結點的next域為NULL因

為鏈棧本身沒有容量限制，所以不會浮現棧滿情況。

3.1.5棧的簡單應用和遞歸

棧與函數調用：

函數調用時，先保存的位置后返回，后保存的位置先返回。所以每遇到一個函數調用便立刻將相應的返回位

置進棧，調用結束時，棧頂元素正好是此函數的返回位置。

遞歸與棧：

滿足遞歸的條件：

1.被定義項在定義中的應用具有更小的尺度。

2.被定義項在最小尺度上的定義不是遞歸的。

3.2隊列

隊列也可以看成一種受限的線性表，插入限定在表的某一端進行(隊尾)，刪除限定在另一端進行(隊頭)隊列又

稱先進先出線性表。

隊列的基本運算：

1.隊列初始化initQueue(Q)加工型運算，設置一個空隊列Q

2.入隊列enQueue(Q,X)加工型運算，將X插入到隊列Q的隊尾。若原隊列為空，則X為原隊尾結點的后繼，同

時是新隊列的隊尾結點。

3.出隊。utQueue(Q,X)加工型運算，若隊列Q不空，則將隊頭元素賦給X,并刪除隊頭結點，其后繼成為新的隊

頭結點。

4.判隊列空emplyQueue(Q)引用型運算，若隊列Q為空，則返回1,否則為0

5.讀隊頭gethead(Q,x)引用型運算，Q不空時由參數X返回隊頭結點的值，否則給一特殊標志。

隊列的順序實現：

隊列的順序實現由一個一維數組及兩個分別指示隊頭和隊尾的變量組成，稱為隊頭指針和隊尾指針。約定隊尾指

針指示隊尾元素在一維數組中的當前位置，隊頭指針指示隊頭元素在一維數組中的當前位置的前一個位置。

如果按sq.rear=sq.rear+1;sq.data[sq.rear]=x'Psq.front=sq.front+1分別進行入隊和出隊操作，則會造成

“假溢出。

循環(huán)隊列的入隊操作：sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x

出隊操作：sq.front=(sq.front+1)%maxsize;

判斷循環(huán)隊列隊滿的條件：((sq.rear+l)%maxsize)==sq.front

隊空的條件：sq.rear==sq.front

3.3數組

二維數組可以看成是一個被推廣的線性表，這種線性表的每一個數據元素本身也是一個線性表。

數組惟獨兩種基本運算：

1.讀：給定一組下標，讀取相應的數據元素

2.寫：給定一組下標，修改相應的數據元素

數組元素的存儲位置是下標的線性函數，計算存儲位置所需的時間取決于乘法的時間，因此，存取任一元素的時

間相等。通常將具有這一特點的存儲結構成為隨機存儲結構。

3.3.3矩陣的壓縮存儲

壓縮存儲的基本思想：值相同的多個元素只分配一個存儲空間，零元素不分配空間。

要壓縮的矩陣分為兩種

1.特殊矩陣：對稱矩陣，三角矩陣。值相同的元素或者零元素的分布有一定規(guī)律叫特殊矩陣。

對稱矩陣通常存儲下三角，n階方陣需要n*(n+l)/2個存儲單元三角矩陣需要n*(n+l)/2+l個存儲單

元，最后一個單元存儲相同的常數。

2.稀疏矩陣：零元素遠多于非零元素，且非零元素的分布沒有規(guī)律。用三元組表存儲稀疏矩陣，只存儲非零元

素。(I,j,aij)

第四章樹

4.1樹的基本概念

樹的定義：

樹是n(n>0)個結點的有窮集合，滿足：

1.有且僅有一個稱為根的結點。

2.其余結點分為m(m>=)個互不相交的非空集合，這些集合中每一個都是一棵樹，稱為根的子樹。

有關術語：

樹上任一結點所擁有的子樹的數目稱為該結點的度。度為0的結點稱為葉子或者終端結點。度大于0的結點稱為

非終端結點或者分支點。一棵樹中所有結點度的最大值稱為該樹的度。

若結點A是B的直接前趨，則稱A是B的雙親或者父節(jié)點，稱B為A的孩子或者子節(jié)點。父節(jié)點相同的結點互稱

為兄弟。

一棵樹的任何結點(不包括根節(jié)點)稱為根的子孫，根節(jié)點稱為其他節(jié)點的祖先。

結點的層數(或者深度)從根開始算，根的層數為1,其他節(jié)點的層數為其雙親的層數加1。樹中結點層數的最大值

稱為該樹的高度或者深度。

樹的基本運算：

1.求根ROOT(T)引用型運算，結果是樹T的根結點。

2.求雙親PARENT(T,X)引用型運算，結果是結點X在樹T上的雙親，若X是樹T的根或者X不在T上，則結

果為一特殊標志。

3.求孩子CHILD(T,X,I)引用型運算，結果是樹T上結點X的第i個孩子，若X不在T上或者X沒有第i個孩

子，結果為一特殊標志。

4.建樹CREATE(X,T1...TK),K>=1,加工型運算，建立一棵以X為根，以T1......TK為第1K課子樹

的樹。

5.剪枝DELETE(T,X,i)加工型運算，刪除樹T上結點X的第i棵子樹，若T無第i棵子樹，則操作為

空。

4.2二叉樹

二叉樹是節(jié)點的有窮集合，它或者是空集，或者同時滿足下述兩個條件：

1.有且僅有一個稱為根的結點。

2.其余結點分為兩個互不相交的集合T1,T2,都是二叉樹，并且T1,T2有順序關系，T1在T2之前，他們分別稱為

根的左子樹和右子樹。

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

空二叉樹，只含根的二叉樹，惟獨非空左子樹的二叉樹，惟獨非空右子樹的二叉樹，同時有非空擺布子樹的二

叉樹。

二叉樹的基本運算：

1.初始化INITIATE(BT)加工型運算，作用是設置一棵空二叉樹

2.求根ROOT(BT)引用型運算，結果是二叉樹BT的根節(jié)點，若BT為空二叉樹，結果為一特殊標志。

3.求雙親PARENT(BT,X)引用型運算，結果是結點X在二叉樹BT上的雙親，若X是根或者不在BT上，

結果為一特殊標志

4.求左孩子【.CHILD(BT,X)右孩子RCHILD(BT,X)引用型運算，結果分別為結點X在BT上的左，右孩子。

若X為BT的葉子或者X不在BT上，結果為一特殊標志。

5.建樹CREAT(X,LBT,RBT)加工型運算，建立一棵X為結點，LBT,RBT為擺布子樹的二叉樹。

6.剪枝DELETEFT(BT,X)和DELETEHT(BT,X)加工型運算，刪除BT結點X的擺布子樹，若無，運算為

空。

二叉樹的性質：

1.二叉樹第i(i>=l層上至多有2『i個結點。

2.深度為K(k>=l)的二叉樹至多有2kT個結點。

3.對任何二叉樹，若2度結點數為n2,則葉子數n=n2+l

深度為K(K>=1)且有2L1結點的二叉樹為滿二叉樹，在第K層刪去最右邊連續(xù)J個結點，得到一棵深度為K的

徹底二叉樹。

徹底二叉樹的性質；l-x|表示不大于X的最大整數。

1.具有N個結點的徹底二叉樹的深度為|」。如叫+1

2.將一棵有n個結點的徹底二叉樹按層編號，則對任一編號為i的結點X有：

若i=l,則結點X是根，若i>l,則X的雙親parent(X)的編號為若i/2|

若2i>n,則結點X無左孩子(且無右孩子)，否則，X的左孩子LCHILD(X)的編號為2i.

若2i+l>n,則結點X無右孩子,否則，X的右孩子RCHILD(X)的編號為2i+l

4.3二叉樹的存儲結構

二叉樹的鏈式存儲結構：

二叉鏈表在做求雙親運算時效率不高，此時可采用三叉鏈表。

具有n個結點的二叉樹中，一共有2n個指針域，其中惟獨n-1個用來指向結點的擺布孩子，其余的n+1個指針域

為NULL.

P81

4.3.2二叉樹的順序存儲結構

按層編號然后存儲。

對于非徹底二叉樹，可采用增加虛結點的方式轉化成徹底二叉樹再進行存儲。虛結點在數組中用特殊記號表示。

但同時會浪費存儲空間。

4.4.二叉樹的遍歷

遍歷一棵二叉樹就是按某種次序系統地“訪問”二叉樹上所有結點，使每一個節(jié)點恰好被訪問一次。

先根遍歷：1訪問根結點2先根遍歷左子樹3先根遍歷右子樹

中根遍歷：1中根遍歷左子樹2訪問根結點3中根遍歷右子樹

后根遍歷：1后根遍歷左子樹2后根遍歷右子樹3訪問根結點。

4.6樹和林

樹的存儲結構；P93

1.孩子鏈表示方法：頭結點分為數據域和指針域，表結點分為孩子域和指針域

可以在頭結點中增加雙親域，稱為帶雙親的孩子鏈表示方法。

2.孩子兄弟鏈表示法：存儲結點均含三個域：數據域，孩子域(存放指向本結點第一個孩子的指針)，兄弟域

(存放指向本結點下一個兄弟的指針)。

3.雙親表示法：數據域，指針域(指示本結點的雙親所在的存儲結點)

將指針域定義為高級語言中的指針類型的鏈式存儲結構成為“動態(tài)鏈表”，相應的指針成為動態(tài)指針。將指針域

定義為整形，子界型的鏈式存儲結構成為靜態(tài)鏈表，相應的指針稱為靜態(tài)指針。

動態(tài)鏈表的結構通過庫函數malloc(size)動態(tài)生成，無需事先規(guī)定表的容量。而靜態(tài)鏈表容量須事先說明。

4.6.2樹的遍歷

1.先根遍歷：若樹非空1訪問根結點2挨次先根遍歷根的各個子樹

2.后根遍歷：1挨次后根遍歷根的各個子樹2訪問根結點

3層次遍歷：2訪問根結點2從左到右，從上到下挨次訪問每層。

二叉樹與樹，林的關系P97

將二叉樹的二叉鏈表和數的孩子兄弟鏈表的左孩子指針，右孩子指針和孩子指針，兄弟指針對應起來。與樹對應

的二叉樹的右子樹一定為空。

判定樹和哈夫曼樹

用于描述分類過程的二叉樹稱為判定樹。判定樹的每一個非終端結點包含一個條件，于是對應于一次比較火判斷，

每一個終端結點包含一個種類標記，對應于一種分類結果。

哈夫曼樹：

給定一組值P1……PK,如何構造一棵有k個葉子且分別以這些值為權的判定樹，使得其平均比較次數最小。滿足

上述條件的判定樹稱為哈夫曼樹。

第五章圖

圖中的小圓圈稱為頂點，連線稱為邊，連線附帶的數值稱為邊的權。

任何兩點間相關聯的無向圖稱為無向徹底圖，一個N個頂點的徹底無向圖的邊數為n(nT)/2.任何兩頂點間都有弧的

有向圖稱為有向徹底圖。一個N個頂點的有向徹底圖弧數位n(n-l)每條邊或者弧都帶權的圖稱為帶權圖或者網。

一個連通圖的生成樹，是含有該連通圖的全部頂點的一個極小聯通子圖。

若連通圖的頂點個數位N,則生成樹的邊數為NT,如果它的一個子圖的邊數大于NT,則其中一定有環(huán)，如果小于，則

一定不連通。

5.2圖的存儲結構

鄰接矩陣

對于無向圖，頂點VI的度是矩陣中第1行(或者列)的元素之和。

對于有向圖，行元素之和為出度，列元素之和為入度。

鄰接表

為每一個頂點建立一個單鏈表，單鏈表中每一個結點稱為表結點，包括兩個域，鄰接點域，用以存放與VI相鄰接

的頂點序號，鏈域，用以指向同VI鄰接的下一個的頂點。

此外，每一個單鏈表設一個表頭結點。每一個表頭結點有兩個域，一個存放頂點VI的信息，另一個指向鄰接表中

的第一個結點。

若一個無向圖有N個頂點，E條變，則它的鄰接表需要N個頭結點和2E個表結點，所以在邊稀疏的情況下，用鄰接

表比鄰接矩陣更節(jié)省存儲空間。

對于無向圖，第I個單鏈表中的結點個數即為VI的度。

對于有向圖，第I個單鏈表中的結點個數只是VI的出度，為求入度，必須遍歷整個鄰接表，所有單鏈表中，鄰接點

域的值為I的結點個數即為入度。

有時為了方便的求入度，可以建立逆鄰接表。

5.3圖的遍歷

從圖中某一頂點出發(fā)訪遍圖中其余頂點，每一個頂點僅訪問一次，叫做圖的遍歷。增設visited[nft組。初值為

0,vi被訪問后，置為1

遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。

最小生成樹問題

拓撲排序

第六章查找表

集合的特點：在集合這種邏輯結構中，任何結點間都不存在邏輯關系。

用來標識數據元素的數據項稱為關鍵字，簡稱鍵，該數據項的值稱為鍵值。

靜態(tài)查找表：以集合為邏輯結構，包括三種基本運算

1.建表CREATE(ST)加工型運算，生成一個由用戶給定的若干數據元素組成的靜態(tài)查找表ST.

2.查找SEARCH(ST,K)引用型運算，若ST中存在鍵值等于K，結果為該鍵在$T中的位置，否則為一特殊標志

3.讀表元GET(ST.pos)引用型運算，結果是pos位置上的數據元素。

動態(tài)查找表：包