數據
元素又稱為元素、結點、記錄是數據的基本單位
數據項是具有獨立含義的最小標識單位
數據的邏輯結構
數據的邏輯結構有以下兩大類：
線性結構：有且僅有一個開始結點和一個終端結點判帮，且所有結點都最多只有一個直接前驅和一個直接后繼泳赋。
線性表是一個典型的線性結構。棧妇菱、隊列、串暴区、數組等都是線性結構闯团。
非線性結構：在該類結構中至少存在一個數據元素,它具有兩個或者兩個以上的前驅或后繼.如樹和二叉樹
集合結構和多維數組、廣義表仙粱、圖房交、堆等數據結構都是非線性結構。
基本邏輯結構
集合結構：數據元素的有限集合缰盏。數據元素之間除了“屬于同一個集合”的關系之外沒有其他關系涌萤。
線性結構：數據元素的有序集合。數據元素之間形成一對一的關系口猜。
樹型結構：樹是層次數據結構负溪，樹中數據元素之間存在一對多的關系。
圖狀結構：圖中數據元素之間的關系是多對多的济炎。
具體例子：
傳統文本（例如書籍中的文章和計算機的文本文件）都是線性結構川抡，閱讀是需要注意順序閱讀，而超文本則是一個非線性結構须尚。在制作文本時崖堤，可將寫作素材按內部聯系劃分成不同關系的單元，然后用制作工具將其組成一個網型結構耐床。閱讀時密幔，不必按線性方式順序往下讀，而是有選擇的閱讀自己感興趣的部分撩轰。
算法
是對特定問題求解步驟的一種描述胯甩，是指令的有限序列昧廷。一個算法是一系列將輸入轉換為輸出的計算步驟。?
算法的重要特性
輸入：算法應該有零個或多個輸入偎箫。
輸出：算法應該有一個或多個輸出木柬。
有窮性：算法必須在執(zhí)行有窮步驟之后正常結束。?
確定性：算法中的每一條指令必須有確切的含義淹办。?
可行性：算法中的每一條指令必須是切實可執(zhí)行的眉枕。
算法設計的要求
正確性：算法應能正確地實現預定功能和要求。
易讀性：算法應易于閱讀和理解怜森，便于調試速挑、修改和擴充。
健壯性：對正確的輸入能得到正確的輸出塔插。當遇到非法輸入時應能作適當的反應或處理梗摇，而不會產生不需要或不正確的結果拓哟。
高效性：解決同一問題的執(zhí)行時間越短想许，算法的時間效率就越高。
低存儲量：解決同一問題的占用存儲空間越少断序，算法的空間效率就越高流纹。
算法的時間復雜度
定義：設問題的規(guī)模為n，把一個算法的時間耗費T(n)稱為該算法的時間復雜度违诗，它是問題規(guī)模為n的函數漱凝。
常用的算法的時間復雜度的順序：（比較時只看最高次冪）
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）
是具有相同數據類型的數據元素的一個有限序列绅项。通常表示為：（a1紊册，a2，… ai快耿，ai+1… an）
線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存放線性表的數據元素囊陡，這種存儲形式的線性表稱為順序表。它的特點是線性表中相鄰的元素在內存中的存儲位置也是相鄰的掀亥。由于線性表中的所有數據元素屬于同一類型撞反，所以每個元素在存儲中所占的空間大小相同。
優(yōu)點：順序存儲結構內存的存儲密度高搪花，可以節(jié)約存儲空間遏片，并可以隨機或順序地存取結點垛膝，但是插入和刪除操作時往往需要移動大量的數據元素，并且要預先分配空間丁稀，并要按最大空間分配吼拥，因此存儲空間得不到充分的利用，從而影響了運行效率线衫。
線性表的鏈式存儲結構凿可，它能有效地克服順序存儲方式的不足，同時也能有效地實現線性表的擴充授账。
單鏈表和循環(huán)鏈表（循環(huán)鏈表是單鏈表的變形）
線性表的鏈式存儲結構是用一組地址任意的存儲單元存放線性表中的數據元素枯跑。除了存儲其本身的值之外，還必須有一個指示該元素直接后繼存儲位置的信息白热，即指出后繼元素的存儲位置敛助。這兩部分信息組成數據元素ai的存儲映像，稱為結點（node）屋确。每個結點包括兩個域：一個域存儲數據元素信息纳击，稱為數據域；另一個存儲直接后繼存儲位置的域稱為指針域攻臀。
指針域中存儲的信息稱做指針或鏈焕数。N個結點鏈結成一個鏈表，由于此鏈表的每一個結點中包含一個指針域刨啸，故又稱線性鏈表或單鏈表堡赔。
循環(huán)鏈表最后一個結點的next指針不為空，而是指向了表的前端设联。為簡化操作善已，在循環(huán)鏈表中往往加入表頭結點。
循環(huán)鏈表的特點是：只要知道表中某一結點的地址离例，就可搜尋到所有其他結點的地址换团。
雙向鏈表
雙向鏈表是指在前驅和后繼方向都能游歷(遍歷)的線性鏈表。
在雙向鏈表結構中粘招，每一個結點除了數據域外啥寇，還包括兩個指針域，一個指針指向該結點的后繼結點洒扎，另一個指針指向它的前趨結點辑甜。通常采用帶表頭結點的循環(huán)鏈表形式。
用指針實現表
用數組實現表時袍冷，利用了數組單元在物理位置上的鄰接關系表示表元素之間的邏輯關系磷醋。
優(yōu)點是：
無須為表示表元素之間的邏輯關系增加額外的存儲空間。
可以方便地隨機存取表中任一位置的元素胡诗。
缺點是：
插入和刪除運算不方便邓线，除表尾位置外淌友，在表的其他位置上進行插入或刪除操作都須移動大量元素，效率較低骇陈。
由于數組要求占用連續(xù)的存儲空間震庭，因此在分配數組空間時，只能預先估計表的大小再進行存儲分配你雌。當表長變化較大時器联，難以確定數組的合適的大小
順序表與鏈表的比較
順序表的存儲空間可以是靜態(tài)分配的，也可以是動態(tài)分配的婿崭。鏈表的存儲空間是動態(tài)分配的拨拓。
順序表可以隨機或順序存取。鏈表只能順序存取氓栈。
順序表進行插入/刪除操作平均需要移動近一半元素渣磷。鏈表則修改指針不需要移動元素。
若插入/刪除僅發(fā)生在表的兩端授瘦，宜采用帶尾指針的循環(huán)鏈表醋界。
存儲密度=結點數據本身所占的存儲量/結點結構所占的存儲總量。
順序表的存儲密度= 1奥务，鏈表的存儲密度< 1物独。
總結：順序表是用數組實現的袜硫，鏈表是用指針實現的氯葬。用指針來實現的鏈表，結點空間是動態(tài)分配的婉陷，鏈表又按鏈接形式的不同帚称，區(qū)分為單鏈表、雙鏈表和循環(huán)鏈表秽澳。
棧(stack)
是限定僅在表尾進行插入或刪除操作的線性表闯睹。棧是一種后進先出(Last In First Out)/先進后出的線性表，簡稱為LIFO表
用指針實現椀Ｉ瘢—鏈(式)棧鏈式棧
無棧滿問題楼吃，空間可擴充
插入與刪除僅在棧頂處執(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）/后進后出特性乱陡。如車站排隊買票，排在隊頭的處理完走掉仪壮，后來的則必須排在隊尾等待憨颠。在程序設計中，比較典型的例子就是操作系統的作業(yè)排隊积锅。
隊列的順序存儲結構稱為順序隊列爽彤，順序隊列實際上是運算受限的順序表，和順序表一樣缚陷，順序隊列也是必須用一個數組來存放當前隊列中的元素适篙。由于隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針分別指示隊頭和隊尾元素在隊列中的位置箫爷。
循環(huán)隊列是為了克服順序隊列中“假溢出”嚷节，通常將一維數組Sq.elem[0]到Sq.elem.[MaxSize-1]看成是一個首尾相接的圓環(huán)，即Sq.elem[0]與Sq.elem .[maxsize-1]相接在一起虎锚。這種形式的順序隊列稱為循環(huán)隊列硫痰。
用線性鏈表表示的隊列稱為鏈隊列。鏈表的第一個節(jié)點存放隊列的隊首結點翁都，鏈表的最后一個節(jié)點存放隊列的隊尾首結點碍论，隊尾結點的鏈接指針為空。另外還需要兩個指針（頭指針和尾指針）才能唯一確定柄慰，頭指針指向隊首結點鳍悠，尾指針指向隊尾結點
遞歸
定義：若一個函數部分地包含它自己或用它自己給自己定義,則稱這個函數是遞歸的税娜；若一個算法直接地或間接地調用自己,則稱這個算法是遞歸的算法。
樹
①結點的度：結點擁有子節(jié)點的個數
②樹的度：該樹中最大的度數
③葉子結點：度為零的結點
④分支結點：度不為零的結點
⑤內部結點：除根結點之外的分支結點
⑥開始結點：根結點又稱為開始結點
結點的高度：該結點到各結點的最長路徑的長度
森林：m（m≥0）棵互不相交的樹的集合藏研。將一棵非空樹的根結點刪去敬矩，樹就變成一個森林；
反之蠢挡，給m棵獨立的樹增加一個根結點弧岳，并把這m棵樹作為該結點的子樹，森林就變成一棵樹业踏。
2．結點的層數和樹的深度
①結點的層數：根結點的層數為1禽炬，其余結點的層數等于其雙親結點的層數加1。
②堂兄弟：雙親在同一層的結點互為堂兄弟勤家。
③樹的深度：樹中結點的最大層數稱為樹的深度腹尖。
注意：要弄清結點的度、樹的度和樹的深度的區(qū)別伐脖。
樹中結點之間的邏輯關系是“一對多”的關系热幔，樹是一種非線性的結構
樹的遍歷
先序遍歷：訪問根結點——先序遍歷根的左子樹——先序遍歷根的右子數
中序遍歷：中序遍歷左子樹——訪問根結點——中序遍歷右子樹
后序遍歷：后序遍歷左子樹——后序遍歷右子樹——訪問根結點
最優(yōu)二叉樹（哈夫曼樹）：最小兩結點數相加的值再與次小結點數合并。
已知一棵二叉樹的前根序序列和中根序序列，構造該二叉樹的過程如下：
1. 根據前根序序列的第一個元素建立根結點；
2. 在中根序序列中找到該元素稿黍，確定根結點的左右子樹的中根序序列；
3. 在前根序序列中確定左右子樹的前根序序列采缚；
4. 由左子樹的前根序序列和中根序序列建立左子樹；
5. 由右子樹的前根序序列和中根序序列建立右子樹。
-已知一棵二叉樹的后根序序列和中根序序列，構造該二叉樹的過程如下：
1. 根據后根序序列的最后一個元素建立根結點却嗡；
2. 在中根序序列中找到該元素，確定根結點的左右子樹的中根序序列嘹承；
3. 在后根序序列中確定左右子樹的后根序序列；
4. 由左子樹的后根序序列和中根序序列建立左子樹如庭；
5. 由右子樹的后根序序列和中根序序列建立右子樹叹卷。
圖
G= ( V , E ) = ( 頂點，邊）
無向完全圖有n（n - 1）/ 2 個邊 坪它，有向完全圖有n（n - 1）個邊 骤竹。n表結點。
邊無向()往毡，弧有向<>
迪杰斯特拉（Dijkstra）算法
是典型的單源最短路徑算法蒙揣，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展开瞭，直到擴展到終點為止懒震。Dijkstra算法是很有代表性的最短路徑算法罩息，在很多專業(yè)課程中都作為基本內容有詳細的介紹，如數據結構个扰，圖論瓷炮，運籌學等等。注意該算法要求圖中不存在負權邊递宅。
弗洛伊德（Floyd）算法<鄰接矩陣求>
是解決任意兩點間的最短路徑的一種算法娘香，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包办龄。Floyd-Warshall算法的時間復雜度為O(N3)烘绽，空間復雜度為O(N2)。
普里姆(Prim)算法
普里姆算法的基本思想：
從連通網絡N= {V,E}中的某一頂點u0出發(fā),選擇與它關聯的具有最小權值的邊(u0,v),將其頂點加入到生成樹頂點集合S中俐填。以后每一步從一個頂點在S中而另一個頂點不在S中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合S中诀姚。如此繼續(xù)下去,直到網絡中的所有頂點都加入到生成樹頂點集合S中為止。
克魯斯卡爾(Kruskal)算法
克魯斯卡爾算法的基本思想：
設有一個有n個頂點的連通網絡N= {V,E},最初先構造一個只有n個頂點,沒有邊的非連通圖T= {V,?},圖中每個頂點自成一個連通分支玷禽。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分支上赫段，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權值最小的邊矢赁。如此重復下去,直到所有頂點在同一個連通分支上為止糯笙。
排序
冒泡排序：比較相鄰2數，大的數后移小的數前移選出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ī)模數據的排序。
快速排序首先選取一個“基準數”境肾，通過基準數將大于它和小于它的數無序地放在基準數的兩邊
如：有 4 ?3 ?1 ?7 ?2 ?5 剔难， i = 1時：3 ?1 ?2 ?4 ?5 ?7（以4為基準數）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i = 2時：1 ?2 ?3 ?4 ?5 ?7（以3為基準數）
插入排序： 略
1、就平均時間性能而言奥喻，快速排序最佳偶宫。但在最壞情況下不如堆排序和歸并排序。（歸并排序對n較大時適用）
2环鲤、當序列中的記錄“基本有序”或n值較小時纯趋，直接插入排序是最佳的方法，因此常將它與其他排序方法結合使用，如快速排序吵冒、歸并排序等纯命。
3、基數排序的時間復雜度也可寫成O(d*n)桦锄，因此它最適用于n值很大而關鍵字較小的序列扎附。
4、穩(wěn)定的排序方法：簡單排序结耀。不穩(wěn)定的排序方法：快速排序留夜、堆排序。
一般來說图甜，排序過程中的“比較”是在相鄰的兩個記錄的關鍵字之間進行的排序方法是穩(wěn)定的碍粥。
代碼實現著重看：表/棧/隊列/遞歸的插入和刪除的實現
