線性表的特徵：
（1）有且僅有乙個開始結點(表頭結點)a1，它沒有直接前驅，只有乙個直接後繼;
（2）有且僅有乙個終端結點(表尾結點)an，它沒有直接後繼，只有乙個直接前驅;
（3）其它結點都有乙個直接前驅和直接後繼；
（4）元素之間為一對一的線性關係。
在順序儲存結構中為：o(1);在鏈式儲存結構中為：o(n).
棧：先進後出
佇列：先進先出表
二叉樹的性質
性質1 若二叉樹的層數從0開始，則一棵非空二叉樹的第i層結點數，最多為2i個（i>=0）。
性質2 若規定空樹的深度為-1，則深度為k的二叉樹最大結點數為2k+1-1（k>= -1）。
性質3 對任意一棵二叉樹，如果葉子結點個數為n0，度為2的結點個數為n2，則有n0=n2+1。
性質4 具有n個結點的完全二叉樹深度k為不超過log2(n+1)-1 的最大整數。
性質5如果將一棵有n個結點的完全二叉樹從上到下，從左到右對結點編號0，1，2，…，n，然後按此編號將該二叉樹中各結點順序地存放於乙個一維陣列中，對任意結點 i(0≤i≤n)，則有如下結論成立：
（1）若 i>0，則序號為i的結點的雙親結點的序號為(i-1)/2(「/」表示整除），若i=0，則序號為i的結點為根結點，無雙親結點；
（2）若2i+1=n,則序號為i的結點無左子女。即結點為葉結點；
（3）若2i+2=n,則序號為i的結點無右子女。
（4）若結點i序號為奇數且不等於1，則它的左兄弟為i-1；
（5）若結點i序號為偶數且不等於n，它的右兄弟為i+1。
滿二叉樹深度為k具有2k+1-1個結點的二叉樹，稱為滿二叉樹。
從上面滿二叉樹定義可知，必須是二叉樹的每一層上的結點數都達到最大，否則就不是滿二叉樹。即滿二叉樹的每乙個結點或者是乙個分支結點，並恰有兩個非空子結點；或者是葉結點。
完全二叉樹如果一棵具有n個結點的深度為k的二叉樹，它的每乙個結點都與深度為k的滿二叉樹中編號為1~ n的結點一一對應，則稱這棵二叉樹為完全二叉樹
滿二叉樹定理1：非空滿二叉樹的葉結點數等於其分支結點數加1。
二叉樹定理2：乙個非空二叉樹空子樹的數目等於其結點數目加1。
中序遍歷：根結點的左子樹－根結點－根結點的右子樹。
前序遍歷：訪問根結點－根結點的左子樹－根結點的右子樹。
後序遍歷：根結點的左子樹－根結點的右子樹－訪問根結點。
樹的儲存結構和樹類
1、父指標表示法
用一組連續的儲存單元（陣列）儲存樹中的所有結點，每個結點有兩個域：乙個是資料元素域，乙個是指向其父結點的指標域。
並且乙個陣列可以儲存任意多棵無關的樹。陣列內結點可能以任何順序出現。
2、子結點表示法
按樹的度（即樹中所有結點度的最大值）設計結點的子結點指標個數。
3、父子結點表示法
在父指標表示法的基礎上，給陣列的每個結點增加乙個指向該結點所有子結點鍊錶的指標。
4、孩子兄弟結點表示法
乙個結點有四個域：資料元素域，父結點域，左子結點域，右兄弟結點域。
哈夫曼樹自己看書
圖的鄰接矩陣表示
在鄰接矩陣表示中，除了存放頂點本身資訊（用一維陣列儲存）外，還用乙個矩陣表示各個頂點之間的關係（即邊的資訊）。若（i,j）∈e(g)或〈i,j〉∈e(g),則矩陣中第i行第j列元素值為1，否則為0 。
圖的鄰接表表示：
將每個結點的邊用乙個單鏈表鏈結起來，若干個結點可以得到若干個單鏈表，每個單鏈表都有乙個頭結點，所有頭結點組成乙個一維陣列，稱這樣的鍊錶為鄰接表。
圖的遍歷
（1）深度優先搜尋遍歷
深度優先搜尋遍歷可定義如下：
(1)首先訪問頂點i，並將其訪問標記置為訪問過，即visited[i]=1；
(2)然後搜尋與頂點i有邊相連的下乙個頂點j，若j未被訪問過，則訪問它，並將j的訪問標記置為訪問過，visited[j]=1，然後從j開始重複此過程，若j已訪問，再看與i有邊相連的其它頂點；
(3)若與i有邊相連的頂點都被訪問過，則退回到前乙個訪問頂點並重複剛才過程，直到圖中所有頂點都被訪問完為止。
廣度優先搜尋遍歷
廣度優先搜尋的基本思想是：
(1)首先訪問頂點i，並將其訪問標誌置為已被訪問，即visited[i]=1；
(2)接著依次訪問與頂點i有邊相連的所有頂點w1，w2，…，wt；
(3)然後再按順序訪問與w1，w2，…，wt有邊相連又未曾訪問過的頂點；
依此類推，直到圖中所有頂點都被訪問完為止 。
aov網
頂點表示活動，有向邊表示活動的優先關係的有向圖叫做頂點表示活動的網路(actire on vertices)簡稱為aov網。
判斷aov網是否有有向環的方法是對該aov網進行拓撲排序
拓撲排序
實現步驟如下：
（1）在aov網中選乙個入度為0的頂點且輸出之；
（2）從aov網中刪除此頂點及該頂點發出來的所有有向邊；
（3）重複（1）、（2）兩步，直到aov網中所有頂點都被輸出或網中不存在入度為0的頂點。
拓撲排序的時間複雜度為：o(n+e)。
3、aoe網
若在帶權有向圖g中以頂點表示事件，以有向邊表示活動，邊上的權值表示該活動持續的時間，則此帶權有向圖稱為用邊表示活動的網（activity on edge network），簡稱aoe網。
關鍵路徑和關鍵活動：關鍵路徑演算法總的時間複雜度為o(n+e).
從源點到匯點的路徑長度最長的路徑稱為關鍵路徑。
關鍵路徑上的所有活動均為關鍵活動。
聯通分量、生成樹、子圖、極小聯通子圖自己看書
排序、查詢自己看書
資料結構概念
資料結構是資訊的組織方式。對於相同的演算法，用不同的資料結構表示其中的抽象資料型別會造成不同的執行效率。這就有必要研究各種抽象資料型別用不同的資料結構表示的效率差異，以及其適用場合。何謂資料結構 資料結構是在整個電腦科學與技術領域上廣泛被使用的術語。它用來反映乙個資料的內部構成，即乙個資料由那些成分...
資料結構基礎概念
第一章緒論 程式設計的一般過程是 問題 想法 演算法 程式 其實質是資料表示和資料處理。資料結構是研究非數值問題中計算機的操作物件以及它們之間關係和操作的學科。資料元素是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。資料項是資料的最小單位，資料元素是討論資料結構時涉及的最小資料單位。從...
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...