數(shù)據(jù)結(jié)構(gòu)速成攻略.doc

數(shù)據(jù)結(jié)構(gòu)速成攻略考試題型：選擇、填空、簡(jiǎn)答、算法。第1章 緒論1、存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）： 順序存儲(chǔ)結(jié)構(gòu)（特點(diǎn)：只存數(shù)據(jù)不存關(guān)系，其關(guān)系體現(xiàn)在存儲(chǔ)位置上） 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（特點(diǎn)：需存數(shù)據(jù)及其關(guān)系）2、邏輯結(jié)構(gòu)： 集合 、 線性結(jié)構(gòu) 、 樹型結(jié)構(gòu) 、 圖型結(jié)構(gòu)（其中樹和圖屬于非線性結(jié)構(gòu)）3、數(shù)據(jù)類型:原子類型（非結(jié)構(gòu)，可分解）、結(jié)構(gòu)類型（不可分解）4、算法的時(shí)間復(fù)雜度（一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級(jí)）、空間復(fù)雜度與問題規(guī)模n有關(guān) Eg： for（i=0；in;i+） for(j=0;jm;j+) Aij=0; 則時(shí)間復(fù)雜度為O(m*n)第2章線性表1、 線性表的順序存儲(chǔ)結(jié)構(gòu)（隨機(jī)存取）：順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。設(shè)每個(gè)元素需占用L個(gè)存儲(chǔ)單元，則第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為L(zhǎng)oc（ai）=Loc（ai）+L*（i-1）。當(dāng)在順序存儲(chǔ)結(jié)構(gòu)的線性表中某個(gè)位置上插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)元素上，移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。若表長(zhǎng)為n，則插入、刪除操作平均移動(dòng)個(gè)元素，算法時(shí)間復(fù)雜度為O（n）。優(yōu)點(diǎn)：存儲(chǔ)密度大（1），存儲(chǔ)空間利用率高，便于訪問。缺點(diǎn)：插入或刪除元素時(shí)不方便。宜做查找這樣的靜態(tài)操作。若線性表長(zhǎng)度變化不大（插入、刪除等操作在表尾進(jìn)行），且主要操作是查找，則采用順序表。2、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（順序存取）：鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放（邏輯相鄰物理不一定相鄰），但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。每個(gè)元素由結(jié)點(diǎn)（Node）構(gòu)成，它至少包括兩個(gè)域，數(shù)據(jù)域（data）：存儲(chǔ)數(shù)據(jù)元素信息；指針域（link）：存儲(chǔ)直接后繼存儲(chǔ)位置（指示數(shù)據(jù)元素之間的邏輯關(guān)系）。整個(gè)鏈表的存取必須從頭指針開始進(jìn)行，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，現(xiàn)行鏈表中最后一個(gè)結(jié)點(diǎn)的指針為“空”（NULL）。優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。╪ext=p-next; p-next=s;刪除操作(核心語句)：q=p-next; p-next=q-next; free(q);在單鏈表中，除了首元結(jié)點(diǎn)外，任意結(jié)點(diǎn)內(nèi)的存儲(chǔ)位置由前驅(qū)結(jié)點(diǎn)的后繼指針指示。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡(jiǎn)化鏈表操作。4、L為指向表頭結(jié)點(diǎn)的指針，p為指向表尾結(jié)點(diǎn)的指針，p滿足的條件（判斷是哪類鏈表）：?jiǎn)捂湵?p-next=NULL循環(huán)鏈表（表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)） p-next=L雙向鏈表（結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)） p-next=NULL雙向循環(huán)鏈表 p-next=NULL5、L為指向表頭結(jié)點(diǎn)的指針，鏈表為空，應(yīng)滿足條件：?jiǎn)捂湵?L-next=NULL循環(huán)鏈表 L-next=L雙向鏈表 L-next=NULL雙向循環(huán)鏈表 L-next=NULL & L-prior=NULL第3章棧和隊(duì)列1、棧 棧是限定僅在表尾進(jìn)行插入（進(jìn)棧Push）或刪除（出棧Pop）操作的線性表。表尾端稱為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的。2、隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表。隊(duì)列只允許在表的一端進(jìn)行插入，而在另一端刪除元素。允許插入的一端叫做隊(duì)尾，允許刪除的一端則稱為對(duì)頭。3、棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 順序棧（棧的順序存儲(chǔ)結(jié)構(gòu)）是利用一組地址連續(xù)的存儲(chǔ)單元一次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。（以棧頂指針top=0表示空棧） 順序棧中入棧操作需判斷棧滿，出棧操作需判斷?？铡ｆ湕＃５逆?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。鏈棧中指針方向指向前驅(qū)結(jié)點(diǎn)。鏈棧入棧操作（不需判斷棧滿）：p-data=x;/設(shè)置新結(jié)點(diǎn)的值 p-next=top;/將新元素插入棧中 top=p；/將新元素設(shè)置為棧頂鏈棧出棧操作（需判斷?？眨簆-top;/指向被刪除的棧 top=top-next;/修改棧頂指針 free（p）；4、循環(huán)隊(duì)列，隊(duì)空、隊(duì)滿的條件設(shè)數(shù)組維數(shù)M，兩個(gè)指針front（隊(duì)頭指針）、rear（隊(duì)尾指針）隊(duì)空：front=rear隊(duì)滿：（rear+1）%M=front 入隊(duì)列：rear=（rear+1）%M出隊(duì)列：front=（front+1）%M循環(huán)隊(duì)列中是否能插入下一個(gè)元素與隊(duì)頭指針與隊(duì)尾指針有關(guān)。循環(huán)隊(duì)列用數(shù)組Am存放其元素值，已知隊(duì)頭指針front、隊(duì)尾指針rear，則當(dāng)前隊(duì)列中元素個(gè)數(shù)是（rear-front+m）%m。第4章字符串1、字符串的操作StrAssign(&T,chars):生成一個(gè)其值等于chars的串T。StrCopy(&T,S):由串S復(fù)制得串T。StrEmpty（S）:若S為空串，則返回TRUE，否則返回FALSE。StrCompare（S,T）:若ST則返回值0,若S=T則返回值=0，若ST則返回值=0)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和至多兩棵稱為根的左子樹和右子樹的互不相交的二叉樹組成。注：二叉樹中不存在度大于2的結(jié)點(diǎn)，并且二叉樹的子樹有左子樹和右子樹之分。二叉樹的五中形態(tài)（由三個(gè)結(jié)點(diǎn)構(gòu)成）：空樹、只含根節(jié)點(diǎn)、右子樹為空樹、左子樹為空樹、左右子樹均不為空樹。3、二叉樹的性質(zhì)在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i1）。深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k1）。對(duì)任何一顆二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。4、二叉樹的順序存儲(chǔ)和鏈接存儲(chǔ)二叉樹的順序存儲(chǔ)特點(diǎn)（僅適用于完全二叉樹）：一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)各結(jié)點(diǎn)(定義一個(gè)一維數(shù)組)；自上而下、自左而右存儲(chǔ)結(jié)點(diǎn)；按完全二叉樹上的結(jié)點(diǎn)位置進(jìn)行編號(hào)和存儲(chǔ)。缺點(diǎn)：空間利用率太低！二叉鏈表：鏈表的頭指針指向二叉樹的根節(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)至少包含：數(shù)據(jù)域和左右孩子指針域 lchild data rchild在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)包含：數(shù)據(jù)域、左右孩子指針域和雙親指針。5、在二叉樹的的先序、中序和后續(xù)三種遍歷序列中，已知二叉樹的先序遍歷序列和中序遍歷序列，可求得另一種序列。解題思路：由先序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對(duì)應(yīng)先序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。先序遍歷二叉樹：訪問根節(jié)點(diǎn)。先序遍歷左子樹。先序遍歷右子樹。中序遍歷二叉樹：中序遍歷左子樹。訪問根節(jié)點(diǎn)。中序遍歷右子樹。后序遍歷二叉樹：后序遍歷左子樹。后序遍歷右子樹。訪問根節(jié)點(diǎn)。先序序列的第一個(gè)結(jié)點(diǎn)是根節(jié)點(diǎn)，中序序列根節(jié)點(diǎn)處于左右子樹的中序序列之間。6、中序線索化二叉樹（書132）指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索。加上線索的二叉樹稱之為線索二叉樹。7、完全二叉樹的概念和性質(zhì)一顆深度為k且2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹（沒有度為1的結(jié)點(diǎn)）。深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。完全二叉樹的特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。如果對(duì)一顆有n個(gè)結(jié)點(diǎn)的完全二叉樹（深度為log2n+1）的結(jié)點(diǎn)按層序編號(hào)（從第一層到第log2n+1層，每層從左到右），則對(duì)任意幾點(diǎn)i（1in），有：如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i1，則其雙親是結(jié)點(diǎn)i/2。如果2in，則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn)2i。如果2i+1n，則結(jié)點(diǎn)i無右孩子，否則其右孩子是結(jié)點(diǎn)2i+1。Eg：完全二叉樹的第五層有6個(gè)葉子。求該樹結(jié)點(diǎn)個(gè)數(shù)最多是多少。最大層高：6（葉子只可能存在在最高2層）前5層結(jié)點(diǎn)數(shù)：25-1=31第5層的結(jié)點(diǎn)數(shù)：25-1=16則第6層應(yīng)有結(jié)點(diǎn)數(shù)：（16-6）*2=20該樹結(jié)點(diǎn)個(gè)數(shù)最多是：31+20=51個(gè)8、構(gòu)造赫夫曼樹為字符進(jìn)行編碼，并求出帶全路徑長(zhǎng)度WPL。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長(zhǎng)度計(jì)為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,.n)。構(gòu)造：對(duì)給定的n個(gè)權(quán)值W1,W2,W3,.,Wi,.,Wn構(gòu)成n棵二叉樹的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。重復(fù)兩步，直到集合F中只有一棵二叉樹為止。9、森林的遍歷先序遍歷森立：訪問森林中第一棵樹的根節(jié)點(diǎn)先序遍歷第一棵樹中根節(jié)點(diǎn)的子樹森林先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷森立：中序遍歷森立中第一棵樹的根節(jié)點(diǎn)的子樹森林訪問第一棵樹的根節(jié)點(diǎn)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。10、二叉樹與森林的轉(zhuǎn)換 二叉樹的根結(jié)點(diǎn)是森林中第一棵樹的根結(jié)點(diǎn)二叉樹的左子樹是由第一棵樹根結(jié)點(diǎn)的子樹森林所對(duì)應(yīng)的二叉樹二叉樹的右子樹是由除第一棵樹之外其余樹組成的森林所對(duì)應(yīng)的二叉樹11、赫夫曼編碼任意構(gòu)造一棵以所有要編碼的字符為葉子結(jié)點(diǎn)的二叉樹，并且約定：左分支表示 0；右分支表示 1 。如果把從根結(jié)點(diǎn)到某葉子節(jié)點(diǎn)的路徑上分支字符組成的字符串作為相應(yīng)字符的編碼，那么可以得到一種前綴編碼。注意：每個(gè)字符的編碼長(zhǎng)度等于從根結(jié)點(diǎn)到該葉子結(jié)點(diǎn)的路徑長(zhǎng)度。第7章 圖1、熟悉圖的兩種存儲(chǔ)方法，圖的鄰接矩陣表示和圖的鄰接表表示（見手寫）2、畫出無向圖的鄰接矩陣（或鄰接表），并根據(jù)鄰接矩陣（或鄰接表）寫出從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索（或廣度優(yōu)先搜索）所得的序列（見手寫）3、生成連通網(wǎng)的最小生成樹的普里姆算法和克魯斯卡爾算法，哪種算法適于邊稀疏的連通網(wǎng)，并簡(jiǎn)述該算法。構(gòu)造網(wǎng)的一棵最小生成樹，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。普里姆算法基本思想：Step1：取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根；Step2：往生成樹上添加新的頂點(diǎn) w。在添加的頂點(diǎn) w 和已經(jīng)在生成樹上的頂點(diǎn)v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和 w 之間的邊中取值最?。籗tep3：繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n 個(gè)頂點(diǎn)為止。構(gòu)造網(wǎng)的一棵最小生成樹，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。普里姆算法基本思想：Step1：取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根；Step2：往生成樹上添加新的頂點(diǎn) w。在添加的頂點(diǎn) w 和已經(jīng)在生成樹上的頂點(diǎn)v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和 w 之間的邊中取值最??；Step3：繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n 個(gè)頂點(diǎn)為止。構(gòu)造的最小生成樹不一定唯一，但最小生成樹的權(quán)值之和一定是相同的。比較兩種算法：普里姆算法：O(n2)、適用于稠密圖；克魯斯卡爾算法：O(eloge)、適用于稀疏圖4、用克魯斯卡爾算法（或普里姆算法）求出最小生成樹，寫出求解過程。（見手寫）第9章查找1、構(gòu)造平衡的二叉排序樹（