數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)大綱

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)大綱第一章基本概念：1.數(shù)據(jù)結(jié)構(gòu)的概念：邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是現(xiàn)實(shí)中具體關(guān)系的抽象。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示。算法：算法是求解問(wèn)題的操作序列。2?抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。算法的5個(gè)特征：輸入：0個(gè)或多個(gè)輸入；輸出：1個(gè)或多個(gè)輸出；有窮性：算法必須在有限步內(nèi)結(jié)束；確定性：組成算法的操作必須清晰無(wú)二義性；可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。4?時(shí)間復(fù)雜度：一般來(lái)說(shuō),設(shè)算法中基本操作的執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間復(fù)雜度記作：T(n)=O(f(n))它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率相同。5?空間復(fù)雜度：在本課程中，用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。設(shè)執(zhí)行算法所需的輔助空間是問(wèn)題規(guī)模n的某個(gè)函數(shù)g(n),則算法空間復(fù)雜度記作：S(n)=O(g(n))注：要求會(huì)計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度!

第六章樹(shù)與二叉樹(shù)二叉樹(shù)的基本性質(zhì)：性質(zhì)1在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)性質(zhì)2深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)性質(zhì)3設(shè)二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)n2，則n0=n2+1二叉樹(shù)的存儲(chǔ)：順序：(滿二叉樹(shù)或完全二叉樹(shù)的順序存儲(chǔ))二-二叉樹(shù)存貯結(jié)構(gòu)2<>5?G61二叉樹(shù)的葩序結(jié)構(gòu)藕二叉樹(shù)或蠱全二更脯的順序結(jié)構(gòu)用一組連續(xù)的內(nèi)療單元'按編號(hào)順序依撫存儲(chǔ)蠱全二買則的元塞.例如，用…雉4數(shù)W[]存放一棵蠱全二叉時(shí)，將標(biāo)號(hào)為i的結(jié)虛的數(shù)據(jù)元素存放在分量bt[i]中-存衙位黑隱含r樹(shù)中的關(guān)系「樹(shù)中的關(guān)黍足通過(guò)完全二戈樹(shù)的性廣實(shí)現(xiàn)的*例如，bt[6](1=6)的雙親結(jié)點(diǎn)標(biāo)號(hào)是k=trtinc(i/2)=3,雙親給點(diǎn)所對(duì)應(yīng)的數(shù)組分晝骯[k]2<>5?G60123 4 5 67 m-1(非完全二叉樹(shù)的順序結(jié)構(gòu))非完全二叉樹(shù)的順序結(jié)構(gòu)28D10按完全二叉樹(shù)的形式補(bǔ)齊二叉樹(shù)所缺少的那些結(jié)點(diǎn)，對(duì)二叉樹(shù)結(jié)點(diǎn)編號(hào)，將二叉樹(shù)原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單元龍相應(yīng)^的位置上*但這種方式對(duì)于畸形二叉樹(shù)*

28D10二叉鏈表:2二文鏈表*二叉鏈表中每入結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域r左抬針域*右指針域typedefstructBiTNode{TElemTypedata;StructBiTNode*lchildh*rchild;}BiTNode,*BiTree;三叉鏈表:3三叉鏈表三叉鏈表中每牛結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、雙親指針域*左指針域"右指針域structBT3Node^lchild,旳xh訂山

*parent;:BT3Nodet*B3Tree;

二叉樹(shù)的遍歷①先序：先序遍歷右子樹(shù)訪問(wèn)抿結(jié)點(diǎn)A先序遍歷左子樹(shù)先序遍歷序列：af先序遍歷右子樹(shù)訪問(wèn)抿結(jié)點(diǎn)A先序遍歷左子樹(shù)先序遍歷序列：afb即按TLR的順序遍歷先序遍歷(TLR)若二叉樹(shù)非空訪問(wèn)棍結(jié)點(diǎn)； ’先序遍歷左子樹(shù)： .先序遍歷右子樹(shù)；\(例：先序遍歷右圖所示的二丈樹(shù)⑴⑵左了樹(shù)⑶右子樹(shù)即按TLR的順序遍歷中序遍歷左子樹(shù);例*中序(1)中序遍歷左子樹(shù);例*中序(1)②中序:中序遍歷(LT若二叉樹(shù)非空C1)中序遍歷左子樹(shù)⑵訪問(wèn)根結(jié)點(diǎn)(3)中序遍歷右子樹(shù)歷左子樹(shù)C2)訪問(wèn)根結(jié)點(diǎn)A(3)中序遍歷右子樹(shù)：即按LTR的順序遍歷右子樹(shù)中序遍歷序列：D點(diǎn)G.EAC.F

③后序:例：后序遍歷右圖所示的二叉（1）后序遍歷左子樹(shù)；即按（③后序:例：后序遍歷右圖所示的二叉（1）后序遍歷左子樹(shù)；即按（2）后仔遍歷右子樹(shù)：即按LRT的順序遍歷右子樹(shù)后序遍歷（LR若二叉樹(shù)非空<1）后序遍歷左子樹(shù)（2）后序遍歷右子樹(shù)<3）訪問(wèn)根結(jié)點(diǎn)（3）訪問(wèn)根結(jié)點(diǎn)A后序遍歷睜列：DPGrE,BrFrC?A④層次:LnitQueue(Q);if(T)EnQueue(Q,T);while(!EmptyQucuc(Q))jDeQueue(Q.p);訪問(wèn)LnitQueue(Q);if(T)EnQueue(Q,T);while(!EmptyQucuc(Q))jif(p->ktiild)￡nQueue(Qnp->lchi[d);if(p->rchild)EnQueuefQsp->rchild);J}先序、中序遍歷二叉樹(shù)的非遞歸算法:先序：中序:中序遍歷的非遞歸算法(算法1)StatusInOrderTraverse(BiTreeT){InitStack(S);Push(S；T);while(!StackEmpty(S)){while(GetTop(S?p)&&p)Push(S,p->khild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);visitfp);Push(S,p->rchild)F}returnOK;中序遍歷的非遞歸算法(算法2)StatusInOrderTraverse(BiTrccT){initStack(S);p=T;while(p||!