數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)詳細(xì)無題目

1、數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)內(nèi)容概要：基本概念線性表棧與隊列樹與二叉樹圖查找算法排序算法一、 基本概念1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。2、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。3、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)（抽象的，與實現(xiàn)無關(guān)）物理結(jié)構(gòu)（存儲結(jié)構(gòu)） 順序映像（順序存儲結(jié)構(gòu)）位置“相鄰” 非順序映像（鏈?zhǔn)酱鎯Y(jié)構(gòu)）指針表示關(guān)系4、算法特性：算法具有正確性、有窮性，確定性，（可行性）、輸入，輸出正確性：能按設(shè)計要求解決具體問題，并得到正確的結(jié)果。有窮性：任何一條指令都只能執(zhí)行有限次，即算法必須在執(zhí)行有限步后結(jié)束。確定性：算法中每條指令的含義必須明確，不允許由二義性可行性：算法中待執(zhí)行的操作都十分基本，算法應(yīng)該在有限時間內(nèi)執(zhí)

2、行完畢。輸入：一個算法的輸入可以包含零個或多個數(shù)據(jù)。輸出：算法有一個或多個輸出5、算法設(shè)計的要求：（1）正 確 性：算法應(yīng)能滿足設(shè)定的功能和要求 。 （2）可 讀 性：思路清晰、層次分明、易讀易懂 。 （3）健 壯 性：輸入非法數(shù)據(jù)時應(yīng)能作適當(dāng)?shù)姆磻?yīng)和處理。 （4）高 效 性（時間復(fù)雜度）：解決問題時間越短，算法的效率就越高。 （5）低存儲量（空間復(fù)雜度）：完成同一功能，占用存儲空間應(yīng)盡可能少。二、 線性表1、線性表 List：最常用且最簡單的數(shù)據(jù)結(jié)構(gòu)。含有大量記錄的線性表稱為文件。2、線性表是n個數(shù)據(jù)元素的有限序列。線性結(jié)構(gòu)的特點： “第一個” “最后一個” 前驅(qū) 后繼。3、順序表線性表的順

3、序存儲結(jié)構(gòu)特點a) 邏輯上相鄰的元素在物理位置上相鄰。b) 隨機訪問。01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0L.lengthnext= =null循環(huán)單鏈表為空的判定條件為 L.next= =L線性鏈表的最后一個結(jié)點的指針為NULL頭結(jié)點的數(shù)據(jù)域為空，指針域指向第一個元素的指針。5、順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)6、順序存儲：優(yōu)點：存儲密度大，可隨機存儲 缺點：大

4、小固定；不利于增減節(jié)點;存儲空間不能充分利用；容量難擴充鏈?zhǔn)酱鎯Γ簝?yōu)點：易于插入刪除；可動態(tài)申請空間；表容量僅受內(nèi)存空間限制 缺點：增加了存儲空間的開銷；不可以隨機存儲元素三、 棧與隊列1、棧棧：限定僅在表尾進行插入或刪除操作的線性表。棧頂：表尾端棧底：表頭棧是先進后出的線性表。插入棧頂元素稱為入棧，刪除棧頂元素稱為出棧。2、棧分為鏈棧和順序棧鏈棧a1/anS.an-1用不帶頭結(jié)點的單鏈表實現(xiàn)。順序棧類似于順序表，插入和刪除操作固定于表尾。3、隊列先進先出的線性表。隊尾入隊 對頭出隊允許插入的一端叫做隊尾允許刪除的一端叫做對頭4、鏈隊列5、 循環(huán)隊列typedef struct DataTyp

5、e elemMAXSIZE; int front, rear; / 隊頭、隊尾位置 SqQueue;循環(huán)隊列判斷隊空的條件為 front=rear循環(huán)隊列判斷隊滿的條件為 （rear+1）%m=front在一個循環(huán)隊列中刪除元素時，首先需要后移隊首指針。6、棧與隊列比較：都是線形結(jié)構(gòu)，棧的操作LIFO（后進先出），隊列操作FIFO（先進先出）。四、 樹和二叉樹1. 樹的定義 樹（Tree）：是 n（n0）個有限數(shù)據(jù)元素的集合。 在任意一棵非空樹T中： （1）有且僅有一個特定的稱為樹根（Root）的結(jié)點，根結(jié)點無前趨結(jié)點； （2）當(dāng)n1時，除根結(jié)點之外的其余結(jié)點被分成m(m0)個互不相交的集合T

6、1，T2，Tm，其中每一個集合Ti（1 i m）本身又是一棵樹，并且稱為根的子樹。2. 基本術(shù)語：結(jié)點的度數(shù)：結(jié)點的非空子樹（即后綴）個數(shù)叫作結(jié)點的度數(shù)樹葉、分支結(jié)點：左（右）子樹均為空二叉樹的結(jié)點稱作樹葉否則稱作分支結(jié)點。結(jié)點的層數(shù)：規(guī)定根的層數(shù)是0，其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加1孩子和雙親：樹的深度：樹的度數(shù)：樹中度數(shù)最大的結(jié)點度數(shù)叫作樹的度數(shù)樹林：是由零個或多個不相交的樹所組成的集合。3. 二叉樹性質(zhì)：1) 二叉樹的第i層上至多有2i-1個結(jié)點。2) 深度為k的二叉樹至多有2k-1個結(jié)點。 滿二叉樹：深度為k，有2k-1個結(jié)點。完全二叉樹：給滿二叉樹的結(jié)點編號，從上至下，從左至右，

7、n個結(jié)點的完全二叉樹中結(jié)點在對應(yīng)滿二叉樹中的編號正好是從1到n。3) 葉子結(jié)點n0，度為2的結(jié)點為n2，則n0 = n2+1?？紤]結(jié)點個數(shù)：n = n0 + n1 + n2考慮分支個數(shù)：n-1 = 2n2 + n1可得n0 = n2+14) n個結(jié)點的完全二叉樹深度為。5) n個結(jié)點的完全二叉樹，結(jié)點按層次編號有： i的雙親是，如果i = 1時為根（無雙親）； i的左孩子是2i，如果2in，則無左孩子； i的右孩子是2i + 1，如果2i + 1n則無右孩子。4. 二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用數(shù)組、編號i的結(jié)點存放在i-1處。適合于存儲完全二叉樹。鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表：typedef str

8、uct BTNode DataType data; struct BTNode *lchild, *rchild; BTNode, *BinTree;三叉鏈表：typedef struct BTNode DataType data; struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree;dataparentlchildrchilddatarchildlchild在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，含有n個結(jié)點的二叉鏈表有n+1個空鏈域。5. 遍歷二叉樹（先序DLR、中序LDR、后序LRD）方法與C語言描述由二叉樹的遞歸定義可知，一棵二叉樹由根結(jié)點（D

9、）、根結(jié)點的左子樹（L）和根結(jié)點的右子樹（R）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。一般有三種方法：先序(前序)遍歷DLR（根左右）、中序遍歷LDR（左根右）、 后序遍歷LRD（左右根）。6. 線索二叉樹n個結(jié)點的二叉鏈表中有n+1個空指針，可以利用其指向前驅(qū)或后繼結(jié)點，叫線索，同時需附加一個標(biāo)志，區(qū)分是子樹還是線索。lchildltagdatartagrchild0/10/1lchild有左子樹，則指向左子樹，標(biāo)志ltag = 0；沒有左子樹，可作為前驅(qū)線索，標(biāo)志ltag = 1。rchild有右子樹，則指向右子樹，標(biāo)志rtag = 0；沒有右子樹，可作為后繼線索，標(biāo)

10、志rtag = 1。7. 樹和森林樹的存儲結(jié)構(gòu)雙親表示法，孩子表示法，孩子兄弟表示法。特點：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結(jié)合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來解決。樹與二叉樹的轉(zhuǎn)換表 Error! No text of specified style in document.1 樹和二叉樹的對應(yīng)關(guān)系樹對應(yīng)的二叉樹根根第一個孩子左孩子下一個兄弟右孩子樹的遍歷樹的結(jié)構(gòu)：根，根的子樹。先根遍歷：。例：ABCDEFGHIJK。后根遍歷：。例：CEDFBHGJKIA。遍歷森林森林的結(jié)構(gòu)：第一棵樹

11、的根，第一棵樹的根的子樹森林， 其余樹(除第一棵外)組成的森林。先序遍歷：。例：ABCDEFGHIJ。中序遍歷：。例：BDCEAGFIJH。注：先序遍歷森林，相當(dāng)于依次先根遍歷每一棵樹；中根遍歷森林相當(dāng)于后根遍歷每一棵樹。ABICDFHGJKEAHBCEGFIJD樹的結(jié)構(gòu)劃分森林的結(jié)構(gòu)劃分遍歷樹、森林與遍歷二叉樹的關(guān)系遍歷樹、森林和二叉樹的關(guān)系樹森林二叉樹先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷8. 哈夫曼樹：葉子結(jié)點帶有權(quán)值的最小帶權(quán)路徑長度的最優(yōu)二叉樹構(gòu)造赫夫曼樹 每次取兩個最小的樹組成二叉樹赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構(gòu)成葉子的前綴編碼。五、

12、圖1完全圖：有12 n(n-1)條變得無向圖有向完全圖：具有n（n-1）條弧的有向圖。權(quán)：與圖的邊或弧相關(guān)的數(shù)。頂點v的度：和v相關(guān)聯(lián)的邊的數(shù)目。入度：以頂點v為頭的弧的數(shù)目出度：以頂點v為尾的弧的數(shù)目回路或環(huán)：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。2. 圖的存儲結(jié)構(gòu)鄰接矩陣：0110000110000101000010010ABCDE鄰接表：typedef struct ArcNode / 弧結(jié)點 int adjvex;/ 鄰接點 struct ArcNode *nextarc;/ 下一個鄰接點 ArcNode;typedef struct VexNode

13、 / 頂點結(jié)點 VertexType data;/ 頂點信息 ArcNode *firstarc;/ 第一個鄰接點 VexNode;const int MAX_VERTEX = 最大頂點個數(shù);typedef struct Graph / 圖 VexNode vexsMAX_VERTEX;/ 頂點向量 int vexnum, arcnum;/ 頂點和弧的個數(shù) Graph;邊(弧)多則需要存儲空間多。ABCDE12/0123423/3/0/03/十字鏈表：十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)?？梢钥闯墒菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合起來的一種鏈表。在十字鏈表中，對應(yīng)于有向圖中每一條弧有一個結(jié)點，對

14、應(yīng)于每個頂點有一個結(jié)點。鄰接多重表3. 圖的遍歷1) 深度優(yōu)先（DFS）搜索訪問方式：從圖中某頂點v出發(fā)： a）訪問頂點v；b）從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷，若從某點出發(fā)所有鄰接點都已訪問過，退回前一個點繼續(xù)上述過程，若退回開始點，結(jié)束。2) 廣度（寬度，BFS）優(yōu)先搜索a）訪問頂點v ；b）訪問同v相鄰的所有未被訪問的鄰接點w1,w2, wk；c）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；4. 生成樹和最小生成樹每次遍歷一個連通圖將圖的邊分成遍歷所經(jīng)過的邊和沒有經(jīng)過的邊兩部分，將遍歷經(jīng)過的邊同圖的頂點構(gòu)

15、成一個子圖，該子圖稱為生成樹。因此有DFS生成樹和BFS生成樹。1) 最小生成樹Kruskal算法一句話，“不構(gòu)成環(huán)的情況下，每次選取最小邊”。ABCDE25331763ABCDE25331763ABCDE25331763(a)(b)(c)ABCDE25331763ABCDE25331763ABCDE25331763(d)(e)(f)普里姆算法記V是連通網(wǎng)的頂點集，U是求得生成樹的頂點集，TE是求得生成樹的邊集。普里姆算法：(a) 開始時，U=v0，TE=；(b) 計算U到其余頂點V-U的最小代價，將該頂點納入U，邊納入TE；(c) 重復(fù)(b)直到U=V。普里姆算法和克魯斯卡爾算法的比較算法普

16、里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)O(e loge)特點只與頂點個數(shù)n有關(guān)與邊的數(shù)目e無關(guān)適用于稠密圖只與邊的數(shù)目e有關(guān)與頂點個數(shù)n無關(guān)適用于稀疏圖5. AOV-網(wǎng) 用頂點表示活動，邊表示活動的優(yōu)先關(guān)系的有向圖稱為AOV網(wǎng)。 拓?fù)渑判颍簩OV網(wǎng)絡(luò)中頂點構(gòu)造拓?fù)溆行蛐蛄械倪^程。拓?fù)渑判虻姆椒?1)在有向圖中選一個沒有前驅(qū)的頂點且輸出之(2)從圖中刪除該頂點和所有以它為尾的弧6. 關(guān)鍵路徑AOE網(wǎng)，關(guān)鍵路徑AOE網(wǎng)(Activity On Edge)帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間。在工程上常用來表示工程進度計劃。關(guān)鍵路徑：從源點到匯點的最長的一條路徑，

17、或者全部由關(guān)鍵活動構(gòu)成的路徑。 7. 最短路徑(1) 迪杰斯特拉算法求一個頂點到其他各頂點的最短路徑。算法：(a) 初始化：用起點v到該頂點w的直接邊(弧)初始化最短路徑，否則設(shè)為；(b) 從未求得最短路徑的終點中選擇路徑長度最小的終點u：即求得v到u的最短路徑；(c) 修改最短路徑：計算u的鄰接點的最短路徑，若(v,u)+(u,w)(v,w)，則以(v,u,w)代替。(d) 重復(fù)(b)-(c)，直到求得v到其余所有頂點的最短路徑。特點：總是按照從小到大的順序求得最短路徑。(2) 弗洛伊德算法求每對頂點之間的最短路徑。依次計算A(0)，A(1)，A(n)。A(0)為鄰接矩陣，計算A(k)時，A

18、(k)(i,j)=minA(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)。技巧：計算A(k)的技巧。第k行、第k列、對角線的元素保持不變，對其余元素，考查A(i,j)與A(i,k)+A(k,j) （“行+列”），如果后者更小則替換A(i,j)，同時修改路徑。六、 查找1. 查找分為：靜態(tài)查找表、動態(tài)查找表、哈希查找表2. 靜態(tài)查找表：對查找表只作查找操作的查找表。動態(tài)查找表：查找過程中同時插入表中不含的元素，或者刪除查找表中已有的元素的操作的查找表。3. 順序查找：順序查找又稱線性查找，是最基本的查找方法之一。順序查找既適用于順序表，也適用于鏈表。4. 二分法（折半）查

19、找：是一種效率較高的查找方法，但前提是表中元素必須按關(guān)鍵字有序（按關(guān)鍵字遞增或遞減）排列。5. 索引順序表查找又稱分塊查找。分塊查找：塊內(nèi)無序、塊間有序、如何分塊效率最高6. 動態(tài)查找表：二叉排序樹查找：二叉排序樹的生成 二叉排序樹(二叉查找樹)：或者是一顆空樹?；蛘呷缦?若它的左子樹不空，則左子樹上所有的結(jié)點的值均小于他的根結(jié)點的值。2若右子樹不空，則右子樹所有結(jié)點的值均大于她得根結(jié)點的值。3 左右子樹也分別為二叉排序樹。7. 哈希表：哈希函數(shù)構(gòu)造：直接定址法、除留余數(shù)法、平方取中法，隨機數(shù)法， 數(shù)字分析法沖突解決方法：開放定址法、拉鏈法、公共溢出區(qū)法七、 排序1.插入類排序：直接插入排序每

20、次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。折半插入排序希爾排序基本思想：先將整個待排序記錄序列分成為若干個子序列分別進行直接插入排序，待整個序列中的記錄 基本有序 時在對全體序列進行一次直接插入排序，子序列的構(gòu)成不是簡單的逐段分割，而是將像個某個增量的記錄組成一個子序列。2.交換類排序起泡排序也稱冒泡法，每相鄰兩個記錄關(guān)鍵字比大小,大的記錄往下沉（也可以小的往上?。?。每一遍把最后一個下沉的位置記下，下一遍只需檢查比較到此為止；到所有記錄都不發(fā)生下沉?xí)r，整個過程結(jié)束（每交換一次，記錄減少一個反序數(shù)）。快速排序在當(dāng)前無序區(qū)R

21、1.H中任取一個數(shù)據(jù)元素作為比較的基準(zhǔn)(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R1.I-1X.KeyRI+1.H(1IH)，當(dāng)R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。3.選擇類排序簡單選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。堆排序堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。4.歸并類排序二路歸并排序5.