數(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)文本（例如書籍中的文章和計算機的文本文件）都是線性結構，閱讀是需要注意順序閱讀鸽嫂，而超文本則是一個非線性結構纵装。在制作文本時，可將寫作素材按內部聯(lián)系劃分成不同關系的單元据某，然后用制作工具將其組成一個網(wǎng)型結構搂擦。閱讀時，不必按線性方式順序往下讀哗脖，而是有選擇的閱讀自己感興趣的部分瀑踢。
算法
是對特定問題求解步驟的一種描述，是指令的有限序列才避。一個算法是一系列將輸入轉換為輸出的計算步驟橱夭。?
算法的重要特性
輸入：算法應該有零個或多個輸入。
輸出：算法應該有一個或多個輸出桑逝。
有窮性：算法必須在執(zhí)行有窮步驟之后正常結束棘劣。?
確定性：算法中的每一條指令必須有確切的含義。?
可行性：算法中的每一條指令必須是切實可執(zhí)行的楞遏。
算法設計的要求
正確性：算法應能正確地實現(xiàn)預定功能和要求茬暇。
易讀性：算法應易于閱讀和理解，便于調試寡喝、修改和擴充糙俗。
健壯性：對正確的輸入能得到正確的輸出。當遇到非法輸入時應能作適當?shù)姆磻蛱幚碓蓿粫a(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ù)元素夜涕，這種存儲形式的線性表稱為順序表。它的特點是線性表中相鄰的元素在內存中的存儲位置也是相鄰的属愤。由于線性表中的所有數(shù)據(jù)元素屬于同一類型女器，所以每個元素在存儲中所占的空間大小相同。
優(yōu)點：順序存儲結構內存的存儲密度高住诸，可以節(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ù)
③葉子結點：度為零的結點
④分支結點：度不為零的結點
⑤內部結點：除根結點之外的分支結點
⑥開始結點：根結點又稱為開始結點
結點的高度：該結點到各結點的最長路徑的長度
森林：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è)課程中都作為基本內容有詳細的介紹唇辨，如數(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)定的闪水。
