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

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

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

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

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

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

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

7、n個(gè)結(jié)點(diǎn)的完全二叉樹中結(jié)點(diǎn)在對(duì)應(yīng)滿二叉樹中的編號(hào)正好是從1到n。3) 葉子結(jié)點(diǎn)n0，度為2的結(jié)點(diǎn)為n2，則n0 = n2+1?？紤]結(jié)點(diǎn)個(gè)數(shù)：n = n0 + n1 + n2考慮分支個(gè)數(shù)：n-1 = 2n2 + n1可得n0 = n2+14) n個(gè)結(jié)點(diǎn)的完全二叉樹深度為。5) n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次編號(hào)有： i的雙親是，如果i = 1時(shí)為根（無雙親）； i的左孩子是2i，如果2in，則無左孩子； i的右孩子是2i + 1，如果2i + 1n則無右孩子。4. 二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)用數(shù)組、編號(hào)i的結(jié)點(diǎn)存放在i-1處。適合于存儲(chǔ)完全二叉樹。鏈?zhǔn)酱鎯?chǔ)結(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)酱鎯?chǔ)結(jié)構(gòu)中，含有n個(gè)結(jié)點(diǎn)的二叉鏈表有n+1個(gè)空鏈域。5. 遍歷二叉樹（先序DLR、中序LDR、后序LRD）方法與C語言描述由二叉樹的遞歸定義可知，一棵二叉樹由根結(jié)點(diǎn)（D

9、）、根結(jié)點(diǎn)的左子樹（L）和根結(jié)點(diǎn)的右子樹（R）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹。一般有三種方法：先序(前序)遍歷DLR（根左右）、中序遍歷LDR（左根右）、 后序遍歷LRD（左右根）。6. 線索二叉樹n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空指針，可以利用其指向前驅(qū)或后繼結(jié)點(diǎn)，叫線索，同時(shí)需附加一個(gè)標(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. 樹和森林樹的存儲(chǔ)結(jié)構(gòu)雙親表示法，孩子表示法，孩子兄弟表示法。特點(diǎn)：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結(jié)合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來解決。樹與二叉樹的轉(zhuǎn)換表 Error! No text of specified style in document.1 樹和二叉樹的對(duì)應(yīng)關(guān)系樹對(duì)應(yīng)的二叉樹根根第一個(gè)孩子左孩子下一個(gè)兄弟右孩子樹的遍歷樹的結(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é)點(diǎn)帶有權(quán)值的最小帶權(quán)路徑長(zhǎng)度的最優(yōu)二叉樹構(gòu)造赫夫曼樹 每次取兩個(gè)最小的樹組成二叉樹赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構(gòu)成葉子的前綴編碼。五、

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

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

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

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

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

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

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

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

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

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