擴充二叉樹的特點是什麼

資料結構知識綜述

一、前言

經過一個學期對資料結構與演算法的學習，對這門課程有了更深入的瞭解，瞭解到了資料結構的相關知識，明白了，資料結構的重要性及應用，回顧一個學期，透過這個小論文，來總結一學期的學習成果，資料結構這門課程，具有一定的深度和廣度，有其複雜性，我們一起來分析一下，資料結構與演算法

二、關鍵字

資料、資料元素、資料結構、演算法、資料型別、線性表、順序表、連結串列、棧、佇列、串、陣列、樹、二叉樹、遍歷、森林、哈夫曼樹、圖

三、知識點綜述

（一）演算法描述及演算法複雜度分析

1。 演算法對特定問題求解步驟的一種描述

演算法是一個有窮的規則序列，這些規則決定的某一特定問題的一系列運算，由此問題相關的一定輸入計算機，依照這些規則進行計算和處理，經過有限的計算步驟後，能得到一定的輸出

評價演算法的一般原則

正確性：演算法應能正確的實現處理要求

易讀性：有助於對演算法的理解，便於糾正和，擴充

簡單性：是證明其正確性比較容易對演算法進行修改，也比較方便，嗯

高效率：達到所需的時\空效能

2。演算法複雜度分析演算法色複雜性包括時間複雜性和空間複雜性

用n表示問題的規模的量，把演算法執行所需的時間T表示n的函式記為T（n），不同的T（n）演算法，當n增長時，運算時間增長的快慢不相同； 一個演算法所需的執行時間就是該演算法中所有語句執行次數之和；

漸進時間複雜性：當n逐漸增大時T（n）的極限情況一般簡稱為時間複雜性

T（n）=O（f（n））

當T（n）為多項式時，可取其最高次冪項，且其他的係數也可不寫

常用的時間複雜性順序：O（1）

O（1）為常數數量級即演算法的時間複雜性與輸入規模n無關。

例1

Sum=0……………………………………………………。1次

For（i=1；i<=n；i++）………………………………………n次

For（j=1；j<=n；j++） ………………………………。n*n次

Sum++；…………………………………………n*n次

T（n）=n+1+2（n*n）=O（n*n）

（二）陣列與線性表

1。陣列：陣列是由一些單元組成的，每個單元對應著一-組下標值和一個數組元素。

n維陣列的每個單元對應n個下標值。陣列元素可以是基本資料型別，如整數型、實數型、字元型等，也可以是有多個數據項的一種結構。同一陣列中各個元素必須是同一資料型別，每個陣列元素都佔有相同數量的儲存單元，才能用下標來唯的確定陣列中的元素。

2。一維陣列定址公式

對於一-維陣列，若其下標的下界為LB，上界為UB，第一元素（其下標為LB）的地址為Loc（b）下標為 i的陣列元素A［i］的地址為Loc（i），則計算Loc（i）的定址公式為

Loc（i）=Loc（L B）+（i-LB）*s

陣列下標的下界為0，則陣列中任意-元素A［i］的定址公式為：

Loc（i）=Loc（0）+i*s o<=i<=n-1

3。二維陣列定址公式

設二維陣列A［m］［n］，m\n分別表示陣列的行和列，用Loc（i，j）表示陣列元素A［i］［j］ 的地址，每個單元佔用s個儲存單元，則定址公式為 Loc（i，j）=Loc（0，0）+（i*n+j）*s 0

4。線性表

線性表是由有限數目的相同型別元素組成的序列。

表中的資料元素，除了第一個和最後一個以外，都有一個且只有一個前驅元素，同時也都有一個且只有一個後繼元素；第一個元素只有一個後繼元素而無前驅元素元素。；最後一個元素只有一個前驅元素而無後繼線性 表的元素個數n稱為這個表的長度，當n=0時，這個表叫做空表。線性表在計算機記憶體中採用各元素順序儲存的方式，這種儲存結構叫做向量。每個線性表元素叫做這個向量的一個分量。如果已知線性表第-個元素的地址和每個元素佔用的儲存單元數，由任-元素的序 號就可以計算出該元素在記憶體中的地址。”在程式設計時以維陣列表示線性表最簡單，用的也最普遍。

5。資料元素的插入刪除

1。插入

void insert（A， int n， m， i， G）

{

int j；

if （i<1|li>n+1）

printf（“i值錯！ \n”）；

else

{

for （j=m；j>=i；-）

A［j+1］=A［j］；

/*將第i個元素及其後面的元素後移*/

A［i］=G；

m++； /* 線性表長度加1*/

}

}

在迴圈語句中，當i=1時，須迴圈m次表示元素插入線性表頭的前面，則原線性表中m個元素均須向後移動一個單元，這是最不利的情況。

當i=m+1時，則迴圈-一次也不進行，這時元素直接插入到線性表尾的後面，所以線性表的所有m個元素均不移動，這是最好的情況。

2。刪除函式

void delete（A，int n，i）

{}

int j；

if （i<1］ji>n）

printf（i 1t#！ n）；

else

{

for （j=i；j<=n；j++）A［j］=A［j+1］；

n——；

} }

在迴圈語句中，當i=1時，需迴圈（n-1）次，這是要刪除線性表表頭元素，是最不利的情況；當i=n時，則迴圈一次也不執行，只是將元素數目n比原來減少一個，而第n個數據元素不必再考慮，其餘的各單元的元素均維持不變，這是最好的情況。

6。堆疊

堆疊也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。

進行插入或刪除操作的一段稱為棧頂（ top ）另一端稱為棧底（bottom插入元素又稱為入棧（push） ，刪除元素操作稱為出棧（pop）。不含元素的棧稱為空棧。

堆疊又稱為後進先出線性表或LIFO （ Last-In-First-Out ）表。

a。 入棧：先將棧頂指數加一；然後將入棧元素放到棧頂指標所指示下標的位置上

void push （ST， int n， top， G）

{

if （top==n）

printf（“棧溢位！n”）； /* 顯示棧滿資訊*/

else {

top=top+1；

ST［top］=G；

}

}

b。 出棧： 出棧運算時，先將棧頂的元素值賦給某個變數，以備後面的運算應用；

r=然後棧頂指標減1，將棧頂位置下移。

void pop （ST， int top， X）

{

if （top==0）

printf（“空棧！\n”）；

/*棧為空顯示相應的資訊*/

else {

x=ST［top］；

top=top-1； /* 棧頂位置下移*/ }

}

c。 堆疊應用

中綴表示式 A+B

字尾表示式 AB+

字首表示式 +AB

用S1儲存運算數，s2儲存運算子

譯系統處理時，將表示式從左向右逐個掃視- -遍，並根據不同情況按以下原則處理：

若是運算數，則將其壓入S1棧；若是運算子且S2棧是空棧則將其壓入S2棧；13）若是運算子且S2棧為非空棧，且此運算子的級別高於S2棧頂運算子的級別，則將此運算子壓入S2棧；

凡不屬於上面三條的情況，則將S2的棧頂運算子與S1棧最上面的兩個運算數出棧進行運算，並將運算結果壓入S1棧。

7。佇列：佇列是種運 算受限制的線性表，元素的新增在表的一端進行， 而元素的刪除在表的另，允許新增元素的一端稱為隊尾 （ Rear允許刪除元素的一端稱為隊頭 （ Front ），向佇列新增元素稱為入隊，從佇列中刪除元素稱為出隊

新入隊的元 素只能新增在隊尾， 出隊的元素只能是刪除隊頭的元素，佇列的特點是先進入佇列的元素先出隊，所以佇列也稱作先進先出表或FIFO （ First-In-First-Out ）表。

a。入隊

void insert （Q， intn， f，r， x）

{ if （r== n）

printf（“溢位！n”）；/* 判斷是否已到陣列末端*/

else{

r=r+1 ；

Q［r］=x；/*插入元素*/

if（f == 0）

f=1； /*判斷原來是否為空佇列*/

}

}

出隊：從佇列刪除元素時，隊頭指標f後移而即當刪除了最後一個元素，佇列成為了空佇列時，隊頭指標與隊尾指標同時變為0。

void Delete （Q， intf，r， n， x）

{ if（f==0）

printf（“”下溢位！n“）； /*判斷是否為空佇列*/

else{

{ x=Q［f］； /*取隊頭元素給x賦值*/

if （f==r）

{ f=0；

/*若出隊的是最後一個元素，變成空佇列*/

r=0；

}else

f=f+1； /* 隊頭指標後移*/

}

（二）連結串列

2。單鏈表

Head

head是單鏈表的頭指標，指向開始結點aanan是終端結點，其指標域為空，不指向任何結點。一個單鏈表由頭指標head唯一標識和確定

指標的概念：假設p是一個pointer型別，應正確區分指標型變數、指標、指標所指的結點和結點的內容這四個密切相關的不同概念：p的值（如果有的話）是一個指標，即是一個所指結點的地址。

該指標（若不是NULL ）指向的某個node型結點用*p來標識。

A。單鏈表的運算

a。 遍歷根據表頭指標右前向後的次序訪問單鏈表各個節點在實際應用中列印顯示各個節點的數值域值

b。 插入在單鏈表上找到插入位置，即找到第i個結點。

可以用遍歷的方法，即從表頭起順次訪問單鏈表的結點，直至找到第i個結點。

生成一個以x為值的新結點。可透過C的庫函式malloc（size）來產生。

將新結點鏈入單鏈表中需要改變相關結點的指標。

p

Head

將新結點*s的鏈域指向結點*p的後繼結點

（即s->next=p->next） 將結點 *p的

鏈域指向新結點（即p->next=s） 。

s

c。 刪除：假設指標q指向待刪除結點的前一個結點，指標p指向要刪除的結點，刪除該結點的操作如下：將該結點的前一個結點*q的鏈域指向*p的後繼結點（即q->next=p->next ）

{node *p， *q；

if （head==NULL）

printf（”連結串列下溢！ \n“）； /* 判空*/

if（head->data==x）/ *如表頭結點值等於x*/p=head；

{

head=head->next；

free（p）

}else

{

q=head； /*從第二個結點開始查詢*/

p=head->next；

while（p！=NULL && p->data！=x）

{ q=P；

p=p->next；

}

if（p！=NULL） /* 找到該結點，刪除*/

{q-> next=p-> next；free（p）；

}else

printf（“未找到！ \n”）； } }

B。雙鏈表

直接前趨 直接後繼

雙鏈表較單鏈表雖然要多佔用一些儲存單元但對其插入和刪除操作以及查詢結點的前趨和後繼都非常方便。雙鏈表結構是種對稱結構， 設指標p指向雙鏈表的某一結點，則雙鏈表的對稱性可用下式來表示：

p=（p->prior）->next=（p->next）->prior即結點*p的地址既存放在其前趨結點

*（p->prior）的後繼指標域中，又存放在它的後繼結點*（p->next）的前趨指標域中

雙鏈表的插入

設要在p所指結點的前面插入一個新結點*q，則需要修改4個指標：

q->prior=p->prior；

q->next=p； p

（p->prior）->next=q；

p->prior

1 3 4 2

q

雙鏈表的刪除

設p指向待刪除的結點，則刪除該結點步驟為

：（ 2（p->prior） ->next=p->next；

（p->next） ->prior=p->prior；

這兩個語句的執行順序可以顛倒，執行這兩個語句之後，可呼叫free（p）， 將*p結點釋放

（三） 串的儲存結構及運算

串：串是由有限個字元組成的序列，又稱為字串，一般記為 ：

s=&apos； a a2 da。。。an構及運算

基本運算： 1。求串的長度len（s） ；

2。判斷兩個串是否相等equal（s，）；，

3。 pj↑#Jib concat（st） ；

4。求某串的子串sub（s，start ，ln ， t）；

5。 Jlil f# insert（s1 ， s2） ；

6。 HHJPR F# delete（s， i，j）；

7。置換 replace（s， t， r） o

串的儲存結構

a。 順序儲存結構：r就是採用與其邏輯結構相對應的儲存結構，即將串的各個字元按順序存入連續的儲存單元中去，邏輯上相鄰的字元在記憶體中也是相鄰的，有時稱為順序串。這種儲存結構，隨機讀寫串中指定的第i個字元最為方便，存取的速度最快。但般每個儲存單元本可以放得下多個字元，只放一個字元不能充分利用儲存空間。

b。 串的連結儲存結構：串的連結儲存結構有時稱為鏈串。

鏈串的儲存形式與般的連結串列類似，是將儲存區分成許多結點，每個結點有一個存放字元的域和一個存放指向下一個結點的指標域。鏈串中的一個儲存結點可以儲存1個或多個字元，通常將鏈串中每個儲存結點所儲存的字元個數稱為結點大小

（四） 樹

- 1。結點的度：樹中每個結點具有的子樹數或者後繼結點數稱為該結點的度。度數為0的結點，即沒有子樹的結點叫作端結點或葉子結點。一棵樹中各個結點度數的最大值叫做這個樹的度。

2。兒子結點和父親結點： -個結點的子樹的根或者後繼結點稱為該結點的兒子結點，反之，該結點則稱為其後繼結點的父親結點。

3。兄弟結點：同一個結點的兒子結點之間互稱為兄弟結點。-

4。子孫結點和祖先結點：一個結點的子樹中所有結點均稱之為該結點的子孫結點。反之，從根結點到達一個結點的路徑上的所有結點，都叫做該結點的祖先結點。

5。樹的深度：樹是一種層次結構，樹中結點的層次（ Level ）是從根結點算起的。根結點為第一層，其兒子結點為第二層。其餘各結點的層數逐層由上而下計算。一棵樹中結點的最大層數叫做此樹的深度或高度。

6。森林： n個樹的集合叫森林

A。二叉樹五種基本形態

（a）空二叉樹

（b）僅有一個根結點的二又樹

（C） 右子樹為空的二叉樹

（d）左子樹為空的二叉樹

（e）左、右子樹均非空的二叉樹

滿二叉樹

如果沒有11到15 就是完全二叉樹

B。

二叉樹的順序儲存結構

適用於完全二叉樹和滿二叉樹

二叉樹的鏈式儲存結構適合於非完全二叉樹

c。 普通樹與二叉樹的轉換：在所有兄弟結點之間加一 連線；

對每個結點，除了保留與其左兒子結點的連線外，去掉該結點與其它兒子結點的連線

把樹轉化為二叉樹得到

D。二叉樹的遍歷

1。中序遍歷：左右根

2．先序遍歷：中左右

3。後序遍歷：左右中

例：

E。哈夫曼樹

哈夫曼樹又稱為最優二又樹，它是這樣定義的：設有n個權值{w1，W2， 。。wn}在這些權值為各個1葉子結點的權所構成的二叉樹中，帶權路徑長度WPL最小的二叉樹叫做哈夫曼樹

（五） 圖

無向圖：對於一個圖G，若邊集合E （G）為無向邊的集合，則稱該圖為無向圖。

有向圖：對於一個圖G，若邊集合E （G）為有向邊的集合，則稱該圖為有向圖。

完全圖：在一個有n個頂點的無向圖中，若每個頂點到其它（ n-1 ）個頂點都連有一條邊，則圖中共有n（n-1）/2 條邊

，頂點的度：圖中與每個頂點相連的邊數，。頂點①的度數為2，頂點②的度數為3，。。。。 。入度、出度：對於有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數目，出度是以該頂點為起點的出邊數目，該頂點的度等於其入度和出度之和。，頂點①的入度為1，出度為2，而頂點②的入度為1，出度為0，因為有一條邊指向它而沒有邊從它指出去。

路徑長度：對於無權的圖，路徑長度指的是沿此路徑上邊的數目；對於有權圖，般是取沿路徑各邊的權之和作為此路徑的長度。

鄰接表的表示的圖的DFS演算法

int visited［MAXVEX］；

void dfsgraph（adjlist adj， int n）

{int i；

for（i=1；i<=n；i++）

visited［i］=0； /* ta visited XéEHNGtèJI */for（i= 1；i<=n；i++）

if（！visited［i］）

dfs（adj， i）； }

void dfs（adjlist adj，int v）

{

struct edgenode *p；visited［v］=1；

printf（%d“，v）；p=adj［v］ - link；

while（p！=NULL）

{if（visited［p - adjvex］==0）

dfs（adjlist，p - adjvex）；

/*從v未訪問的鄰接點出發進行DFS*/

p=p - next； }

（六） 排序

1。 簡單選擇排序：簡單選擇排序的作法是：第一趟掃描所有 資料，選擇其中最小的一個與第一個資料互換；第二趟從第二個資料開始向後掃描，選擇最小的與第二個資料互換；依次進行下去，進行了（n-1）趟掃描以後就完成了整個排序過程。在每一趟描資料時，用一個整型變數跟蹤當前最小資料的位置，然後，第i趟掃描只需將該位置的資料與第i個數據交換即可。這樣掃描n-1次，處理資料的個數從n每次逐漸減1，每次掃描結束時才可能有一次交換資料的操作。

演算法的時間複雜性為O（n*n）

2。 氣泡排序：其基本思想是對存放原始資料的陣列，按從後往前的方向進行多次掃描，每次掃描稱為一趟當發現相鄰兩個數與排序要求的“遞增次序”不符合時，即將這兩個資料進行互換。這樣，較小的資料就會逐單元向前移動

演算法：void bubblesort（sqlist r， int n） {

int i，j，flag；

for（i=1；i<=n-1；i++） {

flag=1；

for（ j=i；j<=n-1；j++）

if （r［j+1］。key < rfj］。key）

{ flag=0；

r［0］=r［j］； /* r［0］用於暫時存放元素*/r［j）=r［j+1］；

r［j+1］=r［0］； ］

if （flag==1）

return； } }

（七） 小結

經過一個學期對資料結構與演算法的學習，學習了，資料結構的基本內容，收穫很大，透過對知識點的總結進一步梳理了思路，同時也感覺到自己又很大的不足，許多知識點掌握不夠透徹，對其理解不夠深入，給理解了，表面意思不能理解其深層紋理，在暑假裡，查缺補漏，爭取把資料結構與演算法掌握的更加透徹！