數(shù)據(jù)

元素又稱為元素、結點、記錄是數(shù)據(jù)的基本單位

數(shù)據(jù)項是具有獨立含義的最小標識單位

數(shù)據(jù)的邏輯結構

數(shù)據(jù)的邏輯結構有以下兩大類：

線性結構：有且僅有一個開始結點和一個終端結點，且所有結點都最多只有一個直接前驅和一個直接后繼。

線性表是一個典型的線性結構。棧、隊列、串、數(shù)組等都是線性結構。

非線性結構：在該類結構中至少存在一個數(shù)據(jù)元素,它具有兩個或者兩個以上的前驅或后繼.如樹和二叉樹

集合結構和多維數(shù)組、廣義表、圖、堆等數(shù)據(jù)結構都是非線性結構。

基本邏輯結構

集合結構：數(shù)據(jù)元素的有限集合。數(shù)據(jù)元素之間除了“屬于同一個集合”的關系之外沒有其他關系。

線性結構：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間形成一對一的關系。

樹型結構：樹是層次數(shù)據(jù)結構，樹中數(shù)據(jù)元素之間存在一對多的關系。

圖狀結構：圖中數(shù)據(jù)元素之間的關系是多對多的。

具體例子：

傳統(tǒng)文本（例如書籍中的文章和計算機的文本文件）都是線性結構，閱讀是需要注意順序閱讀，而超文本則是一個非線性結構。在制作文本時，可將寫作素材按內(nèi)部聯(lián)系劃分成不同關系的單元，然后用制作工具將其組成一個網(wǎng)型結構。閱讀時，不必按線性方式順序往下讀，而是有選擇的閱讀自己感興趣的部分。

算法

是對特定問題求解步驟的一種描述，是指令的有限序列。一個算法是一系列將輸入轉換為輸出的計算步驟。?

算法的重要特性

輸入：算法應該有零個或多個輸入。

輸出：算法應該有一個或多個輸出。

有窮性：算法必須在執(zhí)行有窮步驟之后正常結束。?

確定性：算法中的每一條指令必須有確切的含義。?

可行性：算法中的每一條指令必須是切實可執(zhí)行的。

算法設計的要求

正確性：算法應能正確地實現(xiàn)預定功能和要求。

易讀性：算法應易于閱讀和理解，便于調試、修改和擴充。

健壯性：對正確的輸入能得到正確的輸出。當遇到非法輸入時應能作適當?shù)姆磻蛱幚?，而不會產(chǎn)生不需要或不正確的結果。

高效性：解決同一問題的執(zhí)行時間越短，算法的時間效率就越高。

低存儲量：解決同一問題的占用存儲空間越少，算法的空間效率就越高。

算法的時間復雜度

定義：設問題的規(guī)模為n，把一個算法的時間耗費T(n)稱為該算法的時間復雜度，它是問題規(guī)模為n的函數(shù)。

常用的算法的時間復雜度的順序：（比較時只看最高次冪）

for ( i = 1 , i < = 10 , i++ ) x=x+c； ? ? ? ? =>O(1)

for ( i = 1 , i < = n , i++ ) x=x+n；? ? ? ? ? =>O(n)

多嵌套一個for，則為 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?=>O(n^2) 以此類推

真題難點：i = 1，while（i < = n)

i = i * 3；=>O(log3^n)

i = i * 2；=>O(log2^n) 以此類推

程序與算法的區(qū)別

程序可以不滿足有窮性。

線性表（Linear List）

是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的一個有限序列。通常表示為：（a1，a2，… ai，ai+1… an）

線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素，這種存儲形式的線性表稱為順序表。它的特點是線性表中相鄰的元素在內(nèi)存中的存儲位置也是相鄰的。由于線性表中的所有數(shù)據(jù)元素屬于同一類型，所以每個元素在存儲中所占的空間大小相同。

優(yōu)點：順序存儲結構內(nèi)存的存儲密度高，可以節(jié)約存儲空間，并可以隨機或順序地存取結點，但是插入和刪除操作時往往需要移動大量的數(shù)據(jù)元素，并且要預先分配空間，并要按最大空間分配，因此存儲空間得不到充分的利用，從而影響了運行效率。

線性表的鏈式存儲結構，它能有效地克服順序存儲方式的不足，同時也能有效地實現(xiàn)線性表的擴充。

單鏈表和循環(huán)鏈表（循環(huán)鏈表是單鏈表的變形）

線性表的鏈式存儲結構是用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。除了存儲其本身的值之外，還必須有一個指示該元素直接后繼存儲位置的信息，即指出后繼元素的存儲位置。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像，稱為結點（node）。每個結點包括兩個域：一個域存儲數(shù)據(jù)元素信息，稱為數(shù)據(jù)域；另一個存儲直接后繼存儲位置的域稱為指針域。

指針域中存儲的信息稱做指針或鏈。N個結點鏈結成一個鏈表，由于此鏈表的每一個結點中包含一個指針域，故又稱線性鏈表或單鏈表。

循環(huán)鏈表最后一個結點的next指針不為空，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結點。

循環(huán)鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。

雙向鏈表

雙向鏈表是指在前驅和后繼方向都能游歷(遍歷)的線性鏈表。

在雙向鏈表結構中，每一個結點除了數(shù)據(jù)域外，還包括兩個指針域，一個指針指向該結點的后繼結點，另一個指針指向它的前趨結點。通常采用帶表頭結點的循環(huán)鏈表形式。

用指針實現(xiàn)表

用數(shù)組實現(xiàn)表時，利用了數(shù)組單元在物理位置上的鄰接關系表示表元素之間的邏輯關系。

優(yōu)點是：

無須為表示表元素之間的邏輯關系增加額外的存儲空間。

可以方便地隨機存取表中任一位置的元素。

缺點是：

插入和刪除運算不方便，除表尾位置外，在表的其他位置上進行插入或刪除操作都須移動大量元素，效率較低。

由于數(shù)組要求占用連續(xù)的存儲空間，因此在分配數(shù)組空間時，只能預先估計表的大小再進行存儲分配。當表長變化較大時，難以確定數(shù)組的合適的大小

順序表與鏈表的比較

順序表的存儲空間可以是靜態(tài)分配的，也可以是動態(tài)分配的。鏈表的存儲空間是動態(tài)分配的。

順序表可以隨機或順序存取。鏈表只能順序存取。

順序表進行插入/刪除操作平均需要移動近一半元素。鏈表則修改指針不需要移動元素。

若插入/刪除僅發(fā)生在表的兩端，宜采用帶尾指針的循環(huán)鏈表。

存儲密度=結點數(shù)據(jù)本身所占的存儲量/結點結構所占的存儲總量。

順序表的存儲密度= 1，鏈表的存儲密度< 1。

總結：順序表是用數(shù)組實現(xiàn)的，鏈表是用指針實現(xiàn)的。用指針來實現(xiàn)的鏈表，結點空間是動態(tài)分配的，鏈表又按鏈接形式的不同，區(qū)分為單鏈表、雙鏈表和循環(huán)鏈表。

棧(stack)

是限定僅在表尾進行插入或刪除操作的線性表。棧是一種后進先出(Last In First Out)/先進后出的線性表，簡稱為LIFO表

用指針實現(xiàn)棧—鏈(式)棧鏈式棧

無棧滿問題，空間可擴充

插入與刪除僅在棧頂處執(zhí)行

鏈式棧的棧頂在鏈頭

適合于多棧操作

鏈棧的基本操作

1）進棧運算

進棧算法思想：

1）為待進棧元素x申請一個新結點，并把x賦給 該結點的值域。

2）將x結點的指針域指向棧頂結點。

3）棧頂指針指向x結點，即使x結點成為新的棧頂結點。

具體算法如下：

SNode *Push_L(SNode * top,ElemType x)

{

SNode *p;

p=(SNode*)malloc(sizeof(SNode));

p->data=x;

p->next=top;

top=p;

return? top;

}

2）出棧運算

出棧算法思想如下：

1）檢查棧是否為空，若為空，進行錯誤處理。

2）取棧頂指針的值，并將棧頂指針暫存。

3）刪除棧頂結點。

SNode *POP_L(SNode * top,ElemType *y)

{SNode *p;

if(top==NULL) return 0;/*鏈棧已空*/

else{

p=top;

*y=p->data;

top=p->next; free(p);

return? top;

}

3）取棧頂元素

具體算法如下：

void gettop(SNode *top)

{

if(top!=NULL)

return(top->data); /*若棧非空，則返回棧頂元素*/

else

return(NULL); /*否則，則返回NULL*/

}

隊列（Queue）

是只允許在表的一端進行插入，而在另一端進行刪除的運算受限的線性表。其所有的插入均限定在表的一端進行，該端稱為隊尾（Rear）；所有的刪除則限定在表的另一端進行，該端則稱為隊頭（Front）。如果元素按照a1，a2，a3....an的順序進入隊列，則出隊列的順序不變，也是a1，a2，a3....an。所以隊列具有先進先出（First In First Out，簡稱FIFO）/后進后出特性。如車站排隊買票，排在隊頭的處理完走掉，后來的則必須排在隊尾等待。在程序設計中，比較典型的例子就是操作系統(tǒng)的作業(yè)排隊。

隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須用一個數(shù)組來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針分別指示隊頭和隊尾元素在隊列中的位置。

循環(huán)隊列是為了克服順序隊列中“假溢出”，通常將一維數(shù)組Sq.elem[0]到Sq.elem.[MaxSize-1]看成是一個首尾相接的圓環(huán)，即Sq.elem[0]與Sq.elem .[maxsize-1]相接在一起。這種形式的順序隊列稱為循環(huán)隊列。

用線性鏈表表示的隊列稱為鏈隊列。鏈表的第一個節(jié)點存放隊列的隊首結點，鏈表的最后一個節(jié)點存放隊列的隊尾首結點，隊尾結點的鏈接指針為空。另外還需要兩個指針（頭指針和尾指針）才能唯一確定，頭指針指向隊首結點，尾指針指向隊尾結點

遞歸

定義：若一個函數(shù)部分地包含它自己或用它自己給自己定義,則稱這個函數(shù)是遞歸的；若一個算法直接地或間接地調用自己,則稱這個算法是遞歸的算法。

樹

①結點的度：結點擁有子節(jié)點的個數(shù)

②樹的度：該樹中最大的度數(shù)

③葉子結點：度為零的結點

④分支結點：度不為零的結點

⑤內(nèi)部結點：除根結點之外的分支結點

⑥開始結點：根結點又稱為開始結點

結點的高度：該結點到各結點的最長路徑的長度

森林：m（m≥0）棵互不相交的樹的集合。將一棵非空樹的根結點刪去，樹就變成一個森林；

反之，給m棵獨立的樹增加一個根結點，并把這m棵樹作為該結點的子樹，森林就變成一棵樹。

2．結點的層數(shù)和樹的深度

①結點的層數(shù)：根結點的層數(shù)為1，其余結點的層數(shù)等于其雙親結點的層數(shù)加1。

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

③樹的深度：樹中結點的最大層數(shù)稱為樹的深度。

注意：要弄清結點的度、樹的度和樹的深度的區(qū)別。

樹中結點之間的邏輯關系是“一對多”的關系，樹是一種非線性的結構

樹的遍歷

先序遍歷：訪問根結點——先序遍歷根的左子樹——先序遍歷根的右子數(shù)

中序遍歷：中序遍歷左子樹——訪問根結點——中序遍歷右子樹

后序遍歷：后序遍歷左子樹——后序遍歷右子樹——訪問根結點

最優(yōu)二叉樹（哈夫曼樹）：最小兩結點數(shù)相加的值再與次小結點數(shù)合并。

已知一棵二叉樹的前根序序列和中根序序列，構造該二叉樹的過程如下：

1. 根據(jù)前根序序列的第一個元素建立根結點；

2. 在中根序序列中找到該元素，確定根結點的左右子樹的中根序序列；

3. 在前根序序列中確定左右子樹的前根序序列；

4. 由左子樹的前根序序列和中根序序列建立左子樹；

5. 由右子樹的前根序序列和中根序序列建立右子樹。

-已知一棵二叉樹的后根序序列和中根序序列，構造該二叉樹的過程如下：

1. 根據(jù)后根序序列的最后一個元素建立根結點；

2. 在中根序序列中找到該元素，確定根結點的左右子樹的中根序序列；

3. 在后根序序列中確定左右子樹的后根序序列；

4. 由左子樹的后根序序列和中根序序列建立左子樹；

5. 由右子樹的后根序序列和中根序序列建立右子樹。

圖

G= ( V , E ) = ( 頂點，邊）

無向完全圖有n（n - 1）/ 2 個邊 ，有向完全圖有n（n - 1）個邊 。n表結點。

邊無向()，弧有向<>

迪杰斯特拉（Dijkstra）算法

是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結構，圖論，運籌學等等。注意該算法要求圖中不存在負權邊。

弗洛伊德（Floyd）算法<鄰接矩陣求>

是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)。

普里姆(Prim)算法

普里姆算法的基本思想：

從連通網(wǎng)絡N= {V,E}中的某一頂點u0出發(fā),選擇與它關聯(lián)的具有最小權值的邊(u0,v),將其頂點加入到生成樹頂點集合S中。以后每一步從一個頂點在S中而另一個頂點不在S中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合S中。如此繼續(xù)下去,直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合S中為止。

克魯斯卡爾(Kruskal)算法

克魯斯卡爾算法的基本思想：

設有一個有n個頂點的連通網(wǎng)絡N= {V,E},最初先構造一個只有n個頂點,沒有邊的非連通圖T= {V,?},圖中每個頂點自成一個連通分支。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分支上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權值最小的邊。如此重復下去,直到所有頂點在同一個連通分支上為止。

排序

冒泡排序：比較相鄰2數(shù)，大的數(shù)后移小的數(shù)前移選出max/min（反之亦可）

如：有 ?4 ?3 ?1 ?7 ?2 ?5，i = 1時：1 ?4 ?3 ? 2 ?7 ?5（兩兩相比）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? i = 2時：1 ? 2 ? 4 ?3 ?5 ?7

簡單選擇排序：首先在所有記錄中選出排序碼最小的記錄，與第一個記錄交換，然后在其余的記錄中再選出排序碼最小的記錄與第二個記錄交換，以此類推，直到所有的記錄排好序為止。

如：有 3 ?2 ?4 ?1 ， i = 1時：1 ?2 ?4 ?3

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i = 2時：1 ?2 ?3 ?4

快速排序：被廣泛認為它是解決一般問題的最佳排序算法，它比較適合解決大規(guī)模數(shù)據(jù)的排序。

快速排序首先選取一個“基準數(shù)”，通過基準數(shù)將大于它和小于它的數(shù)無序地放在基準數(shù)的兩邊

如：有 4 ?3 ?1 ?7 ?2 ?5 ， i = 1時：3 ?1 ?2 ?4 ?5 ?7（以4為基準數(shù)）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i = 2時：1 ?2 ?3 ?4 ?5 ?7（以3為基準數(shù)）

插入排序： 略

排序小結

1、就平均時間性能而言，快速排序最佳。但在最壞情況下不如堆排序和歸并排序。（歸并排序對n較大時適用）

2、當序列中的記錄“基本有序”或n值較小時，直接插入排序是最佳的方法，因此常將它與其他排序方法結合使用，如快速排序、歸并排序等。

3、基數(shù)排序的時間復雜度也可寫成O(d*n)，因此它最適用于n值很大而關鍵字較小的序列。

4、穩(wěn)定的排序方法：簡單排序。不穩(wěn)定的排序方法：快速排序、堆排序。

一般來說，排序過程中的“比較”是在相鄰的兩個記錄的關鍵字之間進行的排序方法是穩(wěn)定的。