自學考試數(shù)據(jù)結構重點總結各章講義精講

自考數(shù)據(jù)結構重點

第一章概論

1.瑞士計算機科學家沃思提出：算法+數(shù)據(jù)結構=程序。算法是對數(shù)據(jù)運算的描述，而數(shù)據(jù)結構包含邏輯結構和存儲

結構。由此可見，程序設計的實質(zhì)是針對實際問題選擇一種好的數(shù)據(jù)結構和設計一個好的算法，而好的算法在很大

程度上取決于描述實際問題的數(shù)據(jù)結構。

2.數(shù)據(jù)是信息的載體°數(shù)據(jù)元素是數(shù)據(jù)的根本單位。一個數(shù)據(jù)元素可以由假設干個數(shù)據(jù)項組成，數(shù)據(jù)項是具有獨立

含義的最小標識單位。數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。

3.數(shù)據(jù)結構指的是數(shù)據(jù)元素之間的相互關系，即數(shù)據(jù)的組織形式。

數(shù)據(jù)結構一般包含以下三方面內(nèi)容：數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構、數(shù)據(jù)的運算

①數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲結構無關，是獨立于計算機的。

數(shù)據(jù)的邏輯結構分類：線性結構和非線性結構

②數(shù)據(jù)元素及其關系在計算機內(nèi)的存儲方法，稱為數(shù)據(jù)的存儲結構(物理結構)。

數(shù)據(jù)的存儲結構是邏輯結構用計算機言語的完成，它依賴于計算機言語。

③數(shù)據(jù)的運算。最常用的檢索、插入、刪除、更新、排序等。

4.數(shù)據(jù)的四種根本存儲方法：順序存儲、鏈接存儲、索引存儲、散列存儲

(1)順序存儲：通常借助程序設計言語的數(shù)組描述。

(2)鏈接存儲：通常借助于程序言語的指針來描述。

(3)索引存儲：索引表由假設干索引項組成。關鍵字是能唯一標識一個元素的一個或多個數(shù)據(jù)項的組合。

(4)散列存儲：該方法的根本思想是：依據(jù)元素的關鍵字直接計算出該元素的存儲地址。

5.算法必須滿足5個準則：輸入，0個或多個數(shù)據(jù)作為輸入；輸出，產(chǎn)生一個或多個輸出；有窮性，算法執(zhí)行有限

步后結束；確定性，每一條指令的含義都明確；可行性，算法是可行的。

算法與程序的區(qū)別：程序必須依賴于計算機程序言語，而一個算法可用自然言語、計算機程序言語、數(shù)學言語或

約定的符號言語來描述。目前常用的描述算法言語有兩類：類Pascal和類C。

6.評價算法的優(yōu)劣：算法的"正確性”是首先要考慮的。此外，主要考慮如下三點：

①執(zhí)行算法所消耗的時間，即時間復雜性；

②執(zhí)行算法所消耗的存儲空間，主要是輔助空間，即空間復雜性；

③算法應易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。

以上幾點最主要的是時間復雜性，時間復雜度常用漸進時間復雜度表示。

7.算法求解問題的輸入量稱為問題的規(guī)模,用一個正整數(shù)n表示。

8.常見的時間復雜度按數(shù)量級遞增排列依次為：常數(shù)階0(1)、對數(shù)階O(logzn)、線性階0(n)、線性對數(shù)階0(nlo&n)、

平方階0行)立方階0(/)、…、k次方階0(吊)、指數(shù)階0(2")和階乘階0(n!)。

9.一個算法的空間復雜度S(n)定義為該算法所消耗的存儲空間，它是問題規(guī)模n的函數(shù)，它包含存儲算法本身所占

的存儲空間、算法的輸入輸出數(shù)據(jù)所占的存儲空間和算法在運行過程中臨時占用的存儲空間。

第二章線性表

1.數(shù)據(jù)的運算是定義在邏輯結構上的，而運算的具體完成是在存儲結構上進行的。

2.只要確定了線性表存儲的起始位置，線性表中任意一個元素都可隨機存取，所以順序表是一種隨機存取結構。

3.常見的線性表的根本運算：

(1)置空表InitList(L)構造一個空的線性表L。

(2)求表長ListLength(L)求線性表L中的結點個數(shù)，即求表長。

(3)GetNode(L,i)取線性表L中的第i個元素。

(DLocateNode(L,x)在L中查找第一個值為x的元素，并返回該元素在L中的位置。假設L中沒有元素的值為x,

則返回0值。

(5)InsertList(L,i,x)在線性表L的第i個元素之前插入一個值為x的新元素，表L的長度加1。

(6)DeleteList(L,i)刪除線性表L的第i個元素，刪除后表L的長度減1。

4.順序存儲方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。

順序表(SequentialList)：用順序存儲方法存儲的線性表稱為順序表。順序表是一種隨機存取結構，順序表的特

點是邏輯上相鄰的結點其物理位置亦相鄰。

5.順序表上完成的根本運算：

(1)插入：該算法的平均時間復雜度是0(n),即在順序表上進行插入運算，平均要移動一半結點5/2)。

(2)刪除：順序表上做刪除運算，平均要移動表中約一半的結點(nT)/2,平均時間復雜度也是0(n)。

6.采納鏈式存儲結構可以防止一再移動大量元素。一個單鏈表可由頭指針唯一確定，因此單鏈表可以用頭指針的名

字來命名。①生成結點變量的標準函數(shù)p=(ListNodeX)malloc(sizeof(ListNode))；〃函數(shù)malloc分

配一個類型為ListNode的結點變量的空間，并將其首地址放入指針變量p中②釋放結點變量空間的標準函數(shù)

free(p)；//釋放p所指的結點變量空間③結點重量的訪問方法二：p->data和p->next

④指針變量p和結點變量Xp的關系：指針變量p的值一一結點地址，結點變量Xp的值一一結點內(nèi)容

7,建立單鏈表：

(1)頭插法建表：算法：p=(ListNodeX)malloc(sizeof(ListNode));①〃生成新結點

p->data=ch;②〃將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中

p->next=head;(3)

head=p;④

hcnd."A|c|b|InI

戶~T

S-L?|<l?||--------"J

將結點*S插到單俄表hcnd的頭I.

(2)尾插法建表：算法：p=(ListNodeX)malloc(sizeof(ListNode));①〃生成新結點

p->data=ch;②〃將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中

if(head==NULL)

head=p;〃新結點插入空表

else

rear->next=p;③〃將新結點插到Xr之后

rear=p;④〃尾指針指向新表尾

將新結點*5插到單鏈表head的尾上

(3)尾插法建帶頭結點的單鏈表：

頭結點及作用：頭結點是在鏈表的開始結點之前附加一個結點。它具有兩個優(yōu)點：

1.由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置

上操作一致,無須進行特別處理；

2.無論鏈表是否為空，其頭指針都是指向頭結點的非空指針(空表中頭結點的指針域空)，因此空表和非空

表的處理也就統(tǒng)一了。

頭結點數(shù)據(jù)域的陰影表示該局部不存儲信息。在有的應用

head頭結點開始結點終端結點

n->i—中可用于存放表長等附加信息。

(n)中空表

閃

(b)空表

帶頭結點的單鏈表

具體算法：r=head;//尾指針初值也指向頭結點

while((ch=getchar0)!='\n'){

s=(ListNodeX)malloc(sizeof(ListNode));〃生成新結點

s->data=ch;〃將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中

r->next=s;

r=s;

)

r->next=NULL;〃終端結點的指針域置空，或空表的頭結點指針域置空

以上三個算法的時間復雜度均為0(n)。

8.單鏈表上的查找?guī)ь^結點)

(1)按結點序號查找：序號為0的是頭結點。

算法：p=head;j=O;〃從頭結點開始掃描

while(p->next&&j<i){〃順指針向后掃描，直到p->next為NULL或i=j為止

p=p->next;

j++；

)

if(i==j)

returnp;〃找到了第i個結點

elsereturnNULL;〃當i<0或i>0時，找不到第i個結點

時間復雜度：在等概率假設下，平均時間復雜度為：為n/2=0(n)

⑵按結點值查找:

具體算法：ListNodcXp=head->next;〃從開始結點比擬。表非空，p初始值指向開始結點

while(p&&p->data!=key)〃直到p為NULL或p->data為key為止

p=p->next;〃掃描下一結點

returnp;〃假設p=NULL,則查找失敗，否則p指向值為key的結點

時間復雜度為：0(n)

9.插入運算：插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai與a,之間。

hend'

-―A||n|MI???

1A

在單鏈表上插入結點示意圖

s=(ListNodeX)malloc(sizeof(ListNode));②

s->data=x;(3)s->next=p->next@；p->next=s;⑤

算法的時間主要消耗在查找結點上，故時間復雜度亦為0(n)。

10.刪除運算

hcnd'“，一—一

小11aJ4^???

在單鏈表上刪除結點示意圖

r=p->next;②〃使r指向被刪除的結點a：

p->next=r->next③;〃將a,從鏈上摘下

free(r);④〃釋放結點a的空間給存儲池

算法的時間復雜度也是0(n)?p指向被刪除的前一個結點。

鏈表上完成的插入和刪除運算，無須移動結點，僅需修改指針。

11.單循環(huán)鏈表一在單鏈表中，將終端結點的指針域NULL改為指向表頭結點或開始結點即可。推斷空鏈表的條件是

head==head->next;

12.僅設尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對開始結點a,和終端結點a1,查找時間都是0(1)。而

表的操作常常是在表的首尾位置上進行，因此，有用中多采納尾指針表示單循環(huán)鏈表。推斷空鏈表的條件為

rear==rear->next;

?(rear->next*renr

僅設尾指針的單循環(huán)鏈表

13.循環(huán)鏈表：循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方法稍作改變，即可使得表處理更加方便靈敏。假

設在尾指針表示的單循環(huán)鏈表上完成，則只需修改指針，無須遍歷，其執(zhí)行時間是0(1)。

兩個單循環(huán)位表的位接操作示意圖

具體算法：

LinkListConnect(LinkListA,LinkListB){〃假設A,B為非空循環(huán)鏈表的尾指針

LinkListp=A->next;〃①保存A表的頭結點位置

A->next=B->next->ncxt;//②B表的開始結點鏈接到A表尾

free(B->next);〃③釋放B表的頭結點

B->next=p;〃④

returnB;〃返回新循環(huán)鏈表的尾指針

循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p->next是否

為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。

在單鏈表中，從一己知結點出發(fā)，只能訪問到該結點及其后續(xù)結點，無法找到該結點之前的其它結點。而在單

循環(huán)鏈表中，從任一結點出發(fā)都可訪問到表中全部結點，這一優(yōu)點使某些運算在單循環(huán)鏈表上易于完成。

14.雙向鏈表：雙(向)鏈表中有兩條方向不同的鏈，即每個結點中除next域存放后繼結點地址外，還增加一個指

向其直接前趨的指針域prior。

priordatanext①雙鏈表由頭指針head惟一確定的。

head②帶頭結點的雙鏈表的某些運算變得方便。

(a)結點結構(b)空的雙循孫鎮(zhèn)表③將頭結點和尾結點鏈接起來，為雙(向)循環(huán)鏈表。

—鼻

(c)」「空的雙飾環(huán)鏈表

雙鏈表示意圖

15.雙向鏈表的前插和刪除本結點操作

①雙鏈表的前插操作

雙錯表的前插操作

voidDInsertBefore(DListNodeXp,DataTypex){〃在帶頭結點的雙鏈表中，將值為x的新結點插入Xp之前，設

pWNULL

DListNodeXs=malloc(sizeof(DListNode));〃①

s->data=x;//②

s->prior=p->prior;〃③

s->next=p;//(4)

p->prior->next=s"/⑤

p->prior=s;//@

)

②雙鏈表上刪除結點Xp自身的操作

①

voidDDe1eteNode(DListNodeXp)

{〃在帶頭結點的雙鏈表中，刪除結點Xp,設Xp為非終端結點

p->prior->next=p->next;//①

p->next->prior=p->prior;〃②

free(p);〃③

)

與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的

時間復雜度均為0(1)。

16.順序表和鏈表比擬

時間性能：a、線性表：經(jīng)常性的查找；b、鏈式存儲結構：經(jīng)常插入刪除操作；

空間性能：a、對數(shù)據(jù)量大小事先能夠了解的用線性表；b、數(shù)據(jù)量變化較大的用鏈式存儲結構。

存儲密度越大，存儲空間的利用率越高。顯然，順序表的存儲密度是1,鏈表的存儲密度肯定小于1。

第三章棧和隊列

1.棧稱為后進先出(LastInFirstOut)的線性表，簡稱為LIFO表。

棧是運算受限的線性表，順序棧也是用數(shù)組表示的。

進棧操作：進棧時，需要將S->top加1,①S->top==Stack$izeT表示棧滿

②”上溢〃現(xiàn)象一當棧滿時，再做進棧運算產(chǎn)生空間溢出的現(xiàn)象。

退棧操作：退棧時，需將S->top減1,①S->top〈0表示空棧

②"下溢"現(xiàn)象一當?？諘r，做退棧運算產(chǎn)生的溢出現(xiàn)象。

下溢是正?，F(xiàn)象，常用作程序操縱轉移的條件。

空棧時棧頂指針不能是0,只能是-1。

當程序中同時使用兩個棧時，可以將兩個棧的棧底分別設在順序存儲空間的兩端，讓兩個棧頂各自向中間延伸。當

一個棧中的元素較多而棧使用的空間超過共享空間的一半時，只要另一個棧的元素不多，那么前者就可以占用后者

的局部存儲空間。

順序枝<四，-棧公用個“他館L般我為8人“”郵當Topl=Top2-l時，棧滿

圖_______?

Stackl中有?？臻g崗

4個元素

§____

St.uk：3ik?

poshpop

2.為了克服順序存儲分配固定空間所產(chǎn)生的溢出和空間浪費問題?？刹杉{鏈式存儲結構來存儲棧。鏈棧是沒有附加

頭結點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。

鏈棧中的結點是動態(tài)分配的，所以可以不考慮上溢，無須定義StackFull運算

棧的一個重要應用是完成遞歸，直接調(diào)用自己或間接調(diào)用自己的函數(shù)。

3.同意刪除的一端稱為隊頭(Front),同意插入的一端稱為隊尾(Rear),當隊列中沒有元素時稱為空隊列，隊列亦

稱作先進先出(FirstInFirstOut)的線性表，簡稱為FIFO表。

嵯板不百國

(c)A出色(d)B、CH1隊，隊為空隊列的順序存儲結構稱為順序隊列，順序隊列實際上是一個受限的

順序隊列操作示意圖線性表。

順序隊列的根本操作

①入隊時：將新元素插入rear所指的位置，然后將rear加1。

②出隊時：刪去front所指的元素，然后將front加1并返回被刪元素。

當頭尾指針相等時，隊列為空.

在非空隊列里，頭指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。而棧頂指針指向棧頂元素。

4.循環(huán)隊列：為充分利用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊列

為循環(huán)隊列。

循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1,朝前移動。只不過當頭尾指針指向向量上界(QueueSize-1)

時，其加1操作的結果是指向向量的下界0,這種循環(huán)意義下的加1操作可以描述為：

①方法一：

if(i+l==QueueSize)//i表示front或rear

i=0;

else

i++；

②方法二一利用〃模運算〃

i=(i+l)%QueueSize；

循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相

等。因此，無法通過條件Q.front==Q.rear來判別隊列是“空"還是〃滿"。

解決這個問題的方法至少有三種：

①另設一個標志位以區(qū)別隊列是空還是滿；

②設置一個計數(shù)器記錄隊列中元素的總數(shù)(即隊列長度).

③少用一個元素的空間。約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，假設相等則認為隊列

滿即尾指針Q.rear所指的單元始終為空。

兀素入隊操作世行中.個兀索人隊循環(huán)隊列

的北指Hrear將指向F個存儲巾兀.

?I入隊O新開始O出隊

5.循環(huán)隊列的根本運算：

①置隊空：Q->front=Q->rcar=0;

②判隊空：returnQ->rear==Q->front;

③判隊滿：return(Q->rear+1)%QueueSize==Q->front;

④入隊Q->dataQ->rear]=x;〃新元素插入隊尾

Q->rear=(Q->rear+1)%QueueSize;

⑤出隊temp=Q->dataQ->front];

Q->front=(Q->front+l)%QueueSize;〃循環(huán)意義下的頭指針加1

returntemp;

⑥取隊頭元素returnQ->dataQ->front];

6.隊列的鏈式存儲結構簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。

為了簡化處理，在隊頭結點之前附加一個頭結點，并設隊頭指針指向此結點。

*Q*Q-頭,點一尾.點

Q-frontIAIQ-fror.i____：，I~H1b???|A~|

Q-rear|八|

Q-*roar?

Q)空隊列(b)非空隊列

位隊列示意圖

鏈隊列的根本運算：(帶頭結點)

(1)構造空隊：Q->rear=Q->front；Q->rear->next=NULL;

(2)判隊空：returnQ->rear==Q->front;

(3)入隊：QueueNodeXp=(QueueNodeX)malloc(sizeof(QueueNode));〃申請新結點

p->data=x;p->next=NULL;

Q->rear->next=p;//Xp鏈到原隊尾結點后

Q->rear=p;〃隊尾指針指向新的尾

(4)出隊：當隊列長度大于1時，只需修改頭結點指針，尾指針不變

s=Q->front->next;Q->front->next=s->next;

x=s->data;free(s);returnx;

當隊列長度等于1時，不僅要修改頭結點指針，還要修改尾指針

s=Q->front->next;Q->front->next=NULL;Q->rear==Q->front;

x=s->data;free(s);returnx;

(5)取隊頭元素：returnQ->front->next->data;因為有頭結點，所以用了next

①和鏈棧類似，無須考慮判隊滿的運算及上溢。

②在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結點時，該結點既是隊頭也是隊尾，故刪去此結點

時亦需修改尾指針，旦刪去此結點后隊列變空。

7.用計算機來處理計算算術表達式問題，首先要解決的問題是如何將人們習慣書寫的中綴表達式轉換成后綴表達式。

第四章多維數(shù)組和廣義表

1.數(shù)組的順序存儲方法:一般采納順序存儲方法表示數(shù)組。

(1)行優(yōu)先順序Qll,a⑵…,ain,321,322,?*,>32n,....，3ml,dm2,…，dmn

(2)列優(yōu)先順序an,a2i,—,a?i,ai2,a22,—,a?a,....，am,a2n，…,a?

Pascal和C言語是按行優(yōu)先順序存儲的，而Fortran言語是按列優(yōu)先順序存儲的.

2.為了節(jié)約存儲空間，可以對矩陣中有許多值相同或值為零的元素的矩陣，采納壓縮存儲。

特別矩陣是指相同值的元素或零元素在矩陣中的分布有肯定的規(guī)律。常見的有對稱矩陣、三角矩陣。

(1)對稱矩陣在一個n階方陣A中，假設元素滿足下述性質(zhì)：a“=a」iOWi,jWnT

稱為n階對稱矩陣，它的元素是關于主對角線對稱的，所以只需要存儲矩陣上三角或下三角元素即可，讓兩個

對稱的元素共享一個存儲空間。

矩陣元素以和數(shù)組元素sa[k]之間的關系是

k=iX(i+l)/2+ji2j0Wk〈n(n+l)/2T

k=jX(j+l)/2+ii<j0^k<n(n+l)/2-l

(2)三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角(不包含主角線)

中的元素均為常數(shù)c或零；下三角矩陣的主對角線上方均為常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零。

三角矩陣的壓縮存儲：三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有nX(n+l)/2個，因此，

三角矩陣可壓縮存儲在一維數(shù)組san(n+l)/2+l］中，其中c存放在數(shù)組的最后一個元素中。

三角矩陣的壓縮存儲結構是隨機存取結構。

3.稀疏矩陣:設矩陣鼠,中有s個非零元素，假設s遠遠小于矩陣元素的總數(shù)，則稱A為稀疏矩陣。為了節(jié)約存儲單

元，可用壓縮存儲方法只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還

必須存儲非零元素所在的行、列位置，所以可用三元組(i,j,a“)來確定非零元素。

稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲(三元組表)和鏈式存儲(十字鏈表)。稀疏矩陣的壓縮存儲會失去

隨機存取功能。

稀疏矩陣A和它的三元組表*a

4.廣義表是線性表的推廣，又稱列表。

廣義表是n(n2O)個元素a”a2,a,,a,,的有限序列。其中a：或者是原子或者是一個廣義表。

①廣義表通常用圓括號括起來，用逗號分隔其中的元素。

②為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。

③假設廣義表Ls非空(n》l),則&是LS的表頭，其余元素組成的表(a”a.)稱為Ls的表尾。

④廣義表具有遞歸和共享的性質(zhì)

廣義表的深度：一個表展開后所含括號的層數(shù)稱為廣義表的深度。

19.廣義表是一種多層次的線性結構，實際上這就是一種樹形結構。

任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。

head=(a,b)=a,tail(a,b)=(b)對非空表A和(y),也可繼續(xù)分解。

注意:廣義表()和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而后者是長度為1的由

空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。

廣義表是一種有層次的非線性結構，通常采納鏈式存儲結構，每個元素用一個結點表示，結點由3個域構成，其

中一個是tag標志位，用來區(qū)分結點是原子還是子表，當tag為零時結點是子表，第二個域為slink,用以存放子

表的地址；當tag為1時結點是原子，第二個域為data,用以存放元素值。

第五章樹和二叉樹

1.樹的表示法：最常用的是樹形圖表示法；還有3種嵌套集合、凹形、廣義表。

樹結構的根本術語

⑴結點的度(Degree)

樹中的一個結點擁有的子樹數(shù)稱為該結點的度(Degree)。一棵樹的度是指該樹中結點的最大度數(shù)。

度為零的結點稱為葉子(Leaf)或終端結點。度不為零的結點稱分支結點或非終端結點。

除根結點之外的分支結點統(tǒng)稱為內(nèi)部結點。根結點又稱為開始結點。

⑵①路徑(path)假設樹中存在一個結點序列k“…，k”使得k,是k.的雙親(lWi<j),則稱該結點序列

是從h到k,的一條路徑(Path)。

一個結點的祖先是從根結點到該結點路徑上所經(jīng)過的全部結點，而一個結點的子孫則是以該結點為根的子樹

中的全部結點。

結點的層數(shù)(Level)從根起算：根的層數(shù)為1,其余結點的層數(shù)等于其雙親結點的層數(shù)加1。

雙親在同一層的結點互為堂兄弟。

樹中結點的最大層數(shù)稱為樹的高度(Height)或深度(Depth)。

假設將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)；

否則稱為無序樹(UnoderedTree)。假設不特別指明，一般商量的樹都是有序樹。

森林(Forest)是棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個森林;

反之，加上一個結點作樹根，森林就變?yōu)橐豢脴洹?/p>

3.二叉樹與度數(shù)為2的有序樹不同：在有序樹中，雖然一個結點的孩子之間是有左右次序的，但是假設該結點只有

一個孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個孩子也有左右之分。

二叉樹的性質(zhì)：

性質(zhì)1二叉樹第i層上的結點數(shù)目最多為2i(iNl)。例如5層的二叉樹，第5層上的結點數(shù)目最多為2'=16

性質(zhì)2深度為k的二叉樹至多有2卜-1個結點(k》l)。例如深度為5的二叉樹，至多有25-1=31個結點

性質(zhì)3在任意一棵二叉樹中，假設終端結點的個數(shù)為n。，度為2的結點數(shù)為窕，則nFm+1。例如一棵深度為4的二

叉樹(a),其終端結點數(shù)n。為8,度為2的結點樹為7,則8=7+1,nxm+l成立

(b)其終端結點數(shù)n。為6,度為2的結點樹為5,則6=5+1,n0=m+l成立

(n)W義樹0>)完全：叉樹(c)非完全XW

特姝形態(tài)的二乂料

滿二叉樹：一棵深度為k且有2kT個結點的二又樹稱為滿二

叉樹。滿二叉樹的特點：

(1)每一層上的結點數(shù)都到達最大值。即對給定的高度，它是具有最多結點數(shù)的二叉樹。

(2)滿二叉樹中不存在度數(shù)為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。

完全二叉樹：假設一棵深度為k的二叉樹，其前k-1層是一棵滿二叉樹，而最下面一層上的結點都集中在該層最左

邊的假設干位置上，則此二叉樹稱為完全二叉樹。特點：

(1)滿二叉樹是完全二叉樹，完全二叉樹不肯定是滿二叉樹。

(2)在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去假設干結點后得到的二叉樹仍舊是一棵完全二叉樹。

(3)在完全二叉樹中，假設某個結點沒有左孩子，則它肯定沒有右孩子，即該結點必是葉結點。

性質(zhì)4具有n個結點的完全二叉樹的深度為?？趏gnj+l或Rog(n+D]

例，具有100個結點的完全二叉樹的深度為：[IglOO1+1=7,2，=642=128^lULlglOOj=6,[1g(100+1)1=7

4.完全二叉樹的編號特點：完全二叉樹中除最下面一層外，各層都充滿了結點。每一層的結點個數(shù)恰好是上一層結

點個數(shù)的2倍。從一個結點的編號就可推得其雙親，左、右孩子等結點的編號。編號從。開始

①假設i=0,則q,為根結點，無雙親；否則，q,的雙親編號為[(iT)/2」。

②假設2i+l〈n,則q,的左孩子的編號是2i+l；否則，q,無左孩子，即卬必定是葉子。

③假設2i+2<n,則5的右孩子的編號是2i+2；否則，q：無右孩子。

對于完全二叉樹而言，使用順序存儲結構既簡單又節(jié)約存儲空間。但對于一般二叉樹來說，采納順序存儲時，為了

使用結點在數(shù)組中的相對位置來表示結點之間的邏輯關系，就必須增加一些虛結點使其成為完全二叉樹的形式。

5.鏈式存儲結構：二叉樹的每個結點最多有兩個孩子。用鏈接方法存儲二叉樹時，每個結點除了存儲結點本身的數(shù)據(jù)

外，還應設置兩個指針域Ichild和rchild,分別指向該結點的左孩子和右孩子。結點的結構為：I'\rI'1,dl

二叉鏈表是一種常用的二叉樹存儲結構。

建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結點是在左子樹上，而逗號右邊結點是在右子樹上。

b、按完全二叉樹的層次順序建立結點。

具有n個結點的二叉鏈表中，共有2n個指針域。其中有nT個用來指示結點的左、右孩子，其余的n+1個為空。

二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。

遞歸工作棧中包含兩項：一項為哪一項遞歸調(diào)用的語句編號，另一項則是指向根結點的指針。

已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下：

首先依據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后依據(jù)中序遍歷序列確定各子樹根的左右子樹。

6.線索二叉樹：n個結點的二叉鏈表必定存在n+1個空指針域，可以利用這些空指針域，存放指向結點在某種遍歷

次序下的前趨和后繼結點的指針，這種指向前驅和后繼結點的指針稱為‘'線索"，這種加上線索的二叉鏈表稱為線索

鏈表，相應的二叉樹稱為線索二叉樹(ThreadedBinaryTree)?

線索鏈表的結點結構：

統(tǒng)制:中的結點量為：其中：ltag和rtag是增加的兩個標志域，用來區(qū)分結點的左、右指針

lchild|ltag〔data|rtag|rc研域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

J。：凝指向結點的右孩子的指針

左標志jfag1就封凝指向結點的左孩子的指針右標志rfag=

tl：娓指向結點的前趨的左線索rc地娓指向結點的后繼的右線索

/1/101.017\

中印稅索ta表

圖中的實線表示指針，虛線表示線索。

線索二叉樹中，一個結點是葉結點的充要條件為：左、右標志均是1。

7.二叉樹的線索化：把對一棵二叉線索鏈表結構中全部結點的空指針域按照某種遍歷次序加線索的過程稱為線索

化。

和中序遍歷算法一樣，遞歸過程中對每結點僅做一次訪問。因此對于n個結點的二叉樹，線索化的算法時間復雜度

為0(n)。

(c)二叉線索鏈表

8.樹、森林到二叉樹的轉換：樹中每個結點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。

將樹轉換成二叉樹：①在全部兄弟結點之間加一道連線；②對每個結點，除了保存與其長子的連線外，去掉該結點

與其它孩子的連線。由于樹根沒有兄弟，故樹轉化為二叉樹后，二叉樹的根結點的右子樹必為空。

樹到二叉樹的轉換樹到二叉樹的轉換

第步：第二步：

在樹中所有兄弟結點對每個結點,除了保

之間加一連線留?j式的氏r的連線外,

去掉該結點?其他孩了的

連線

樹到二叉樹的轉換

將一個森林轉換為二叉樹：

將森林中的每棵樹轉化成二叉樹，然后再將二叉樹的根節(jié)點看做兄弟連在一起,形成一棵二叉樹

森林轉化為二叉樹森林轉化為二叉樹

第一步：

先招森林中的每棵

樹變?yōu)槎鏄?/p>

森林轉化為二叉樹boho

第二步：

將備二叉樹的根結點視

為兄弟從左至右連在一

起，就形成了一棵一又

樹

9.二叉樹到樹、森林的轉換：

方法是：假設二叉樹中結點x是雙親y的左孩子，則把x

的右孩子，右孩子的右孩子，…，都與y用連線連起來，最后去掉全部雙親到右孩子的連線。

義樹到樹、森林的轉換bobo

10.樹的存儲結構：

1.雙親表示法：雙親鏈表表示法利用樹中每個結點的雙親唯一性，

在存儲結點信息的同時，為每個結點附設一個指向其雙親的指針

parent,惟一地表示任何一棵樹。

(1)雙親鏈表表示法的完成

分析：E和F所在結點的雙親域是1,它們的雙親結點在向量中的位

置是1,即B是它們的雙親。

注意：①根無雙親，其parent域為-1。圖6.17(a)

②雙親鏈表表示法中指針parent向上鏈接，合適求指定結MaxTreeSize-1

下標0123456789

點的雙親或祖先(包含根)；求指定結點的孩子或其它后代時，可能dntnABCDEFGIIIJ

2

要遍歷整個數(shù)組。pnrcnl-100011333

2.孩子鏈表法：孩子鏈表表示法是為樹中每個結點設置一個孩子鏈圖6.17樹轉化為：叉樹(a)所示乂樹的&求鏈表T

表，并將這些結點及相應的孩子鏈表的頭指針存放在一個向量中。

圖6.17樹轉化為義樹(a)中樹的孩子鏈表表示法

注意：①孩子結點的數(shù)據(jù)域僅存放了它們在向量空間的序號。

②與雙親鏈表表示法相反，孩子鏈表表示便于完成涉及孩子及其子孫的運算，但不便于完成與雙親有關的運算。

③將雙親鏈表表示法和孩子鏈表表示法結合起來，可形成雙親孩子鏈表表示法。

3.孩子兄弟表示法：在存儲結點信息的同時、附加兩個分別指向該結點最左孩子和右鄰兄弟的指針域，即可得樹的

孩子兄弟鏈表表示。

注意：

這種存儲結構的最大優(yōu)點是：它和二叉樹的二叉鏈

表表示完全一樣?可利用二叉樹的算法來完成對樹的操

作。

11.樹的遍歷:

一般都只給出兩種次序遍歷樹的方法：前序(先根次序)遍歷和后序(后根次序)遍歷。

①前序遍歷一棵樹等價于前序遍歷該樹對應的二叉樹

②后序遍歷一棵樹等價于中序遍歷該樹對應的二叉樹。

對下面(a)圖中所示的森林進行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJII和

BDCA1FJGHE。而(b)圖所示二叉樹的前序序列和中序序列也分別為ABCDEF1GJH和BDCA1FJGHE?

①前序遍歷森林等同于前序遍歷該森林對應的二叉樹

②后序遍歷森林等同于中序遍歷該森林對應的二叉樹

12.從根結點到某結點之間的路徑長度與該結點上權的乘積稱為該結點的帶權路徑長度，樹種全部葉子結點的帶權路

徑長度之和稱為樹的帶權路徑長度。帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。

哈夫曼樹不肯定是二叉樹。

哈夫曼樹又稱為最優(yōu)樹，是一類帶權路徑長度最短的粉。完全二叉樹就是這種路徑長度最短的二叉樹。

①只有葉結點上的權值均相同時，完全二叉樹肯定是最優(yōu)二叉樹，否則完全二叉樹不肯定是最優(yōu)二叉樹。

②最優(yōu)二叉樹中，權越大的葉子離根越近。③最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。

13.哈夫曼算法：

注意：①初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子

②n個葉子的哈夫曼樹要經(jīng)過nT次合并，產(chǎn)生nT個新結點。最終求得的哈夫曼樹有2nT個結點。

③哈夫曼樹是嚴格的二叉樹，沒有度數(shù)為1的分支結點。

14.哈夫曼編碼：

數(shù)據(jù)壓縮過程稱為編碼,反之，解壓縮的過程稱為解碼。

設計一種長短不等的編碼，則必須保證任一字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為前綴編碼。

可以利用二叉樹來設計二進制的前綴編碼，其左分支表示字符0,右分支表示字符1,則以根結點到葉結點路徑上的

分支字符組成的串作為該葉節(jié)點的字符編碼。

因此設計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權構造一棵哈夫曼樹，由哈夫曼樹求

得的編碼就是哈夫曼編碼。

譯碼過程是從樹根結點出發(fā)，逐個讀入電文中的二進制碼。

第六章

1.圖G由兩個集合構成，頂點集合和邊集合，也可以圖G只有頂點而沒有邊。用尖括號表示圖的有向邊＜v“v」＞,有向

邊又稱為弧，起點稱為弧尾，終點稱為弧頭。無向圖的頂點對用圓括號表示(Vi,Vj)。

在無向圖中，稱Vi和V,相鄰接，在有向圖中稱頂點y鄰接到V“頂點V,鄰接于V;

在無向圖中，n的取值范圍是0-n(n-l)/2,將具有n(nT)/2條邊的無向圖稱為無向完全圖。

在有向圖中，n的取值范圍是O-n(n-l),將具有n(n-1)條邊的有向圖稱為有向完全圖。

無向圖中，頂點的度定義為以該頂點為一個端點的邊的數(shù)目，有向圖的度等于出度和入度之和。

在無向圖中，任意兩頂點都有路徑，則稱兩頂點連通。假設圖G中的任意兩個頂點都連通，稱G為連通圖。無向

圖的極X通子圖稱為連通重量，顯然，任何連通圖的連通重量只有一個，即其自身，而非連通的無向圖有多個連通

重量。

在有向圖中，圖G中任意兩頂點連通，稱為強連通圖，極X通子圖稱為強連通重量。

假設在一個圖的每條邊上標上某種數(shù)值，該數(shù)值稱為該邊的權。邊上帶權的圖稱為帶權圖，帶權的連通圖稱為網(wǎng)絡。

2.圖的存儲結構：鄰接矩陣和鄰接表表示法。圖的頂點編號從0開始。

鄰接矩陣表示法：3”打＞或刖,門)是邊，則值為1,不是邊則值為0。

無向圖的鄰接矩陣是按主對角線對稱的。假設G是帶權圖，只要把1換成相應邊上的權值即可，0的位置上可以不

動或將其換成無窮大表示。無向圖的鄰接矩陣表示法可以僅存儲主對角線以下的元素，時間復雜度為0(一)

鄰接表表示法：鄰接表是圖的一種鏈式存儲結構。將無向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表，

將鄰接表的表頭向量稱為頂點表。假設無向圖有n個頂點和e條邊，則它的鄰接表共有n個頭結點和2e個表結點。

建立鄰接表的時間復雜度是O(n+e)。圖的鄰接表表示不是唯一的，這是因為在每個頂點的鄰接表中，各邊結點的

鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關。

3.圖的遍歷：遍歷圖的算法是求解圖的連通性、圖的拓撲排序等算法的根底。

圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。

深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問頂點的先后次序得到的頂點序列稱為圖的深度優(yōu)先遍歷序

列，或簡稱為DFS序列。共需要搜索/個矩陣元素，時間復雜度為鄰接矩陣0(/)或鄰接表O(n+e)。

廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問的頂點，其鄰接點也先被訪問，就是先進先出。

時間復雜度為鄰接矩陣0(一)或鄰接表0(n+e),空間復雜度都是0(n)。

4.生成樹是連通圖的包含圖中全部頂點的一個極小連通子圖，一個圖的極小連通子圖恰為一個無回路的連通圖，也

就是說，假設圖中任意添加一條邊，就會出現(xiàn)回路，假設去掉任意一條邊，都會使之成為非連通圖。

因此，一個具有n個頂點的生成樹有且僅有n-1條邊，但有n-1條邊的圖不肯定是生成樹，同一個圖可以有不同

的生成樹。

生成樹定義為：假設從圖的某頂點出發(fā)，可以系統(tǒng)的訪問到圖的全部頂點，則遍歷時經(jīng)過的邊和圖的全部頂點所

構成的子圖，稱為該圖的生成樹。

最小生成樹：圖的生成樹不唯一，把權值最小的生成樹稱為最小生成樹(MST)。

構造最小生成樹的算法：普里姆Prim算法的時間復雜度為0(n2)與網(wǎng)中邊數(shù)無關適于稠密圖。

克魯斯卡爾Kruskal算法的時間復雜度為0leloge),主要取決于邊數(shù)，較合適于稀疏圖。

5.最短路徑：Dijkstra迪杰斯特拉算法，提出了按路徑長度遞增的順序產(chǎn)生諸頂點的最短路徑算法。

拓撲排序：子工程稱為活動，頂點代表活動，有向邊代表活動的先后關系。這樣的有向無環(huán)圖DAG稱為頂點活動

網(wǎng)，簡稱為AOV網(wǎng)。將有向無環(huán)圖G中全部頂點排成一個線性序列，假設＜u,v〉CE(G),則在線性序列u在v

之前，這種線性序列稱為拓撲序列。由AOV網(wǎng)構造拓撲序列的過程稱為拓撲排序。

檢測的方法是：對有向圖構造其頂點的拓撲序列，假設網(wǎng)中全部頂點都在他的拓撲序列中，則AOV網(wǎng)必定不存在

環(huán)。

AOV網(wǎng)的拓撲序列不是唯一的。

拓撲排序的描述思想：a、在有向圖中選一個沒有前趨(入度為零)的頂點，且輸出之。b、從有向圖中刪除該頂點

及其與該頂點有關的全部邊。c、重復上述步驟，直到全部頂點都已輸出或圖中剩余的頂點中沒有前趨頂點為止。

d、輸出剩余的無前趨結點。

拓撲排序實際上是對鄰接表表示的圖G進行遍歷的過程。時間復雜度是0(n+e)。

第七章排序

1.如果待排序文件中存在多個關鍵字相同的記錄，經(jīng)過排序后，這些具有相同關鍵字的記錄之間的相對次序保持不

變，該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。

排序在內(nèi)存中處理，不涉及數(shù)據(jù)的內(nèi)外存交換，稱為內(nèi)部排序，反之為外部排序。內(nèi)部排序又分為五類：插入、

選擇、交換、歸并和分配排序.

在排序過程中需進行兩種操作：比擬兩個關鍵字的大小、改變指向記錄的指針或移動記錄本身，而待排序記錄的

存儲形式一般有三種：順序結構、鏈式結構和輔助表。

評價排序算法的標準：執(zhí)行算法需要的時間，以及算法所需要的附加空間。還有算法本身的復雜度。

排序的時間開銷，一般情況下可用算法中關鍵字的比擬次數(shù)和記錄的移動次數(shù)來衡量。

2.插入排序：每次將一個待排序記錄按其關鍵字大小插入到前面已排好序的文件中的適當位置。

直接插入排序：每次從無序區(qū)取出第一個元素把它插入到有序區(qū)的適當位置，使之成為新的有序區(qū)，經(jīng)過n-1次

插入后完成。算法中R0］作用：保存Ri］副本，監(jiān)視數(shù)組下標變量j是否越界。所以R0］稱為哨兵。每次的比擬是從

后往前比擬的。

時間復雜度最好是0(n),最壞是0(/),所以是0(/)?？臻g復雜度0(1),所以是就地排序。是穩(wěn)定的算法。

初始情況是有序區(qū)中只有一個元素R1］,無序區(qū)中R2..n］。

希爾排序(縮小增量排序)：算法不穩(wěn)定。記錄的總比擬次數(shù)和總移動次數(shù)都要比直接插入排序少得多，特別是當

n越大越明顯。希爾排序的時間依賴于增量序列，最后一個增量必須是1,盡量防止增量互為倍數(shù)的情況。

下標1234567891c)

初始關鍵字36254827652543587632

I__________________________________________I

t1

［_______I

I_________________________________________I

I________________I

d=525254827323643587665

IlI