數(shù)據(jù)結(jié)構(gòu)整理筆記（提綱）（數(shù)據(jù)結(jié)構(gòu)C語言版第二版嚴(yán)蔚敏）

數(shù)據(jù)結(jié)構(gòu)整理筆記（提綱）（數(shù)據(jù)結(jié)構(gòu)C語?版第?版嚴(yán)蔚敏）第?章緒論數(shù)據(jù)結(jié)構(gòu)（這門學(xué)科）：是?門研究數(shù)據(jù)的組織，存儲，和運算的?般?法。數(shù)據(jù)：是客觀事物的符號表?，是所有能輸?到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為?個整體進(jìn)?考慮和處理。數(shù)據(jù)元素?于完整地描述?個對象。數(shù)據(jù)項：組成數(shù)據(jù)元素的、有獨?含義的、不可分割的最?單位。例如：學(xué)?的姓名學(xué)號等。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的?個?集。只要集合內(nèi)的性質(zhì)均相同，都可稱之為?個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在?種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)集合結(jié)構(gòu)（離散結(jié)構(gòu)，因為太簡單，所以不考慮）線性結(jié)構(gòu)?線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)或?狀結(jié)構(gòu)存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)邏輯結(jié)構(gòu)?元組（D，R）D是數(shù)據(jù)關(guān)系的集合R是D關(guān)系上的集合（）代表?序<>代表有序抽象數(shù)據(jù)類型：?般指由?戶定義的、表?應(yīng)?問題的數(shù)學(xué)模型，以及定義在這個模型上的?組操作的總稱。具體包括三部分：數(shù)據(jù)對象，數(shù)據(jù)對象上關(guān)系的集合以及對數(shù)據(jù)對象的基本操作的集合。定義格式：ADT{:<>:<>:<>}ADT抽象數(shù)據(jù)類型名算法：是為了解決某類問題?規(guī)定的?個有限長的操作序列。重要特性有窮性確定性可?性輸?輸出評價算法優(yōu)劣的基本標(biāo)準(zhǔn)正確性能在有限的運?時間內(nèi)得到正確的結(jié)果?？勺x性健壯性?效性時間空間語句頻度：?條語句重復(fù)執(zhí)?的次數(shù)算法的時間復(fù)雜度：（?般指的是最壞時間復(fù)雜度）常量階實例此算法時間復(fù)雜度T(n)=O(1)。算法的空間復(fù)雜度常量階for(inti=0;i<=n/2;i++){t=a[i];a[i]=a[n-i+1];a[n-i-1]=t;}線性階for(inti=0;i<n;i++)b[i]=a[n-i+1];for(inti=0;i<n;i++)a[i]=b[i];此算法需要借助??為n的輔助數(shù)組，所以其空間復(fù)雜度為O(n)。第?章線性表線性表：由n（n>=0）個數(shù)據(jù)特性相同的元素構(gòu)成的有限序列?？毡恚簄=0的線性表。?空的線性表或線性結(jié)構(gòu)的特點：（1）存在唯?的?個被稱作“第?個”的數(shù)據(jù)元素；（2）存在唯?的?個被稱作“最后?個”的數(shù)據(jù)元素；（3）除第?個元素外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有?個前驅(qū)；（4）除最后?個元素外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有?個后繼。順序表線性表的順序存儲結(jié)構(gòu)是?種隨機存取的存儲結(jié)構(gòu)。平均查找長度：在查找時，為確定元素在順序表中的位置，需和給定的值進(jìn)??較的數(shù)據(jù)元素個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度（AverageSearchLengthASL）假設(shè)pi是查找第i個元素的概率，Ci為找到其中關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進(jìn)?過?較的關(guān)鍵字個數(shù)，則在長度為n的線性表中，查找成功時的平均查找長度為ASL=piCi（i:1-n之和）鏈表這東西沒什么好說的，會?些基本的操作就?。把鏈表的基本操作寫?下。第三章棧和隊列棧棧頂，棧底。順序棧鏈棧遞歸*：1.定義是遞歸的?如：階乘，?階Fibonacci數(shù)列1.分治法：2.能將?個問題變成?個新問題，?新問題與原問題的解法相同或類同，不同的僅是處理的對象，并且這些處理對象更?且變化有規(guī)律。3.可以通過上述轉(zhuǎn)化?使問題簡化。4.必須有?個明確的遞歸出?，或稱遞歸的邊界。2.數(shù)據(jù)結(jié)構(gòu)是遞歸的?如：鏈表3.問題的解法是遞歸的?如：Hanoi塔問題，?皇后問題，迷宮問題遞歸的算法效率分析：通過迭代法求解遞歸?程來計算時間復(fù)雜度。隊頭，隊尾順序隊列（循環(huán)隊列）少??個元素空間；隊空的條件：Q.front==Q.rear隊滿的條件：(Q.rear+1)%MAXQSIZE==Q.front鏈隊鏈棧，順序隊，鏈隊的代碼第四章串、數(shù)組和?義表串的模式匹配算法1.BF算法（Brute-Force）就是暴?、這個太簡單就不寫代碼了。2.KMP算法最主要的是如何構(gòu)造next數(shù)組和nextval數(shù)組1.next數(shù)組（模式串）：1.0j=12.maxk(1<k<j)‘p1p2…p(k-1)’==‘p(j-k+1)…p(j-2)p(j-1)’通俗的來說就是看j前?的k-1（1<k<j）字符和從1到k-1的字符是不是?樣3.1?個字符都不匹配1.nextval數(shù)組1.求出next數(shù)組2.根據(jù)next數(shù)組判斷s[j]?=s[next[j]]如果相等nextval[j]=next[next[j]]如果不想等(不相等)nextval[j]=next[j]數(shù)組很簡單就不說了就把?些基本的定義弄熟就?了?義表?般記作LS=(a1,a2,a2,...,n)LS是這個?義表的名稱，n為其長度。ai可以是單個元素，也可以是?義表分別稱為?義表LS的原?和字表。習(xí)慣上，??寫字母表??義表的名稱，??寫字母表?原?。顯然，?義表的定義是?個遞歸的定義，因為在描述?義表時??到了?義表的概念。例?1.A=()——A是?個空表，其長度為0。2.B=(e)——B只有?個原?e，其長度為1。3.C=(a,(b,c,d))——C的長度為2，兩個元素分別為原?a和字表(b,c,d)。4.D=(A,B,C)——D的長度為3，三個字表都是?義表。5.E=(a,E)——這是?個遞歸表，長度為2。E相當(dāng)于?個?限的?義表E=(a,(a,(a,…)))。概念表頭（是?個元素）：為?空?義表的以?個元素，它可以是?個原?也可以是?個?表。表尾（是?個?義表）：除表頭之外，由其余元素構(gòu)成的表。（若只有?個元素，那么其為空表）。1.KMP算法的實現(xiàn)第五章樹和?叉樹樹樹：是n（n>=0）個結(jié)點的有限集，它或為空樹；或為?空樹，對于?空樹T：1.有且僅有?個稱之為根的結(jié)點。2.除根結(jié)點以外的其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,TM,其中每?個集合本??是?棵樹，并且稱之為根的?樹（SubTree）。樹的基本術(shù)語1.結(jié)點：樹中的?個獨?單元。包含?個數(shù)據(jù)元素及若?指向其?樹的分?。2.結(jié)點的度：結(jié)點擁有的?樹數(shù)。（這個結(jié)點后繼的個數(shù)）。3.樹的度：樹內(nèi)各結(jié)點度的最?值。4.葉?：度為0的結(jié)點稱為葉?結(jié)點或者終端結(jié)點。5.?終端結(jié)點：度不為0的結(jié)點稱為?終端結(jié)點或者分?結(jié)點。除根結(jié)點以外，?終端結(jié)點也稱為內(nèi)部結(jié)點。6.雙親和孩?：結(jié)點的?樹的根稱為該結(jié)點的孩?，相應(yīng)地，該結(jié)點稱為孩?的雙親。7.兄弟：同?個雙親的孩?之間互稱兄弟。8.祖先：從根到該結(jié)點所經(jīng)分?上的所有結(jié)點。9.?孫：以某結(jié)點為根的?樹中的任?結(jié)點都稱為該結(jié)點的?孫。10.層次：結(jié)點的層次從根開始定義起，根為第?層，根的孩?為第?層。樹中任?結(jié)點的層次等于其雙親結(jié)點的層次加?。11.堂兄弟：雙親在同?層的結(jié)點互為堂兄弟。12.樹的深度：樹中結(jié)點的最?層次稱為樹的深度或?度。13.有序樹和?序樹：如果將樹中結(jié)點的各?樹看成從左到右是有次序的，則稱該樹為有序樹，否則稱為?序樹。14.森林：是m(m>=0)課互不相交的樹的集合。?叉樹：是n(n>=0)個結(jié)點所構(gòu)成的集合。對于?空樹T：1.有且僅有?個稱之為根的結(jié)點。2.除根結(jié)點外的其余結(jié)點分為兩個互不相交的?集T1和T2，分別稱為T的左?樹和右?樹。?叉樹與樹的區(qū)別1.?叉樹每個結(jié)點?多只有兩棵?樹。2.?叉樹是有序樹。?叉樹的性質(zhì)1.在?叉樹的第i層上?多有2^(i-1)個結(jié)點（i>=1）。2.深度為k的?叉樹?多有2^k-1個結(jié)點。3.對任何?棵?叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。證明*：為總分?數(shù)?叉樹結(jié)點總數(shù)n=n0+n1+n2除了根結(jié)點外，每?個結(jié)點都有?個分?進(jìn)?則n=B+112的結(jié)點射出的，所以B=n1+2*n2于是得n=n1+2*n2+1所以n0=n2+1對于任意?棵樹：樹的總結(jié)點個數(shù)為n=n1+n2+...+nk除了根結(jié)點外，每?個結(jié)點都有?個分?進(jìn)?則n=B+11，2，...，k的結(jié)點射出的，所以B=n1+2*n2+3*n3+...+k*nk于是得n=n1+2*n2+3*n3+...+k*nk+1所以n0=1+n2+2*n3+...+(k-1)*nk滿?叉樹：深度為k且含有2^k-1個結(jié)點的?叉樹。完全?叉樹：深度為k的，有n個結(jié)點的?叉樹，當(dāng)且僅當(dāng)其每?個結(jié)點都與深度為k的滿?叉樹中編號從1-n??對應(yīng)時，稱為完全?叉樹。特點1.葉?節(jié)點只可能在層次最?的兩層上出現(xiàn)（第k層和第k-1層）；2.對任?結(jié)點，若其右分?下的?孫的最?層次為l，則其左分?下的?孫的最?層次必為l或l+1。1.具有n個結(jié)點的完全?叉樹的深度為(向下取整)[log2n]+1。遍歷?叉樹前序（先序）遍歷1.訪問根結(jié)點2.先序遍歷左?樹3.先序遍歷右?樹中序遍歷1.中序遍歷左?樹2.訪問根結(jié)點3.中序遍歷右?樹后序遍歷1.后序遍歷左?樹2.后序遍歷右?樹3.訪問根結(jié)點表達(dá)式的前綴表?：波蘭式。表達(dá)式的后綴表?：逆波蘭式。表達(dá)式的中綴表?：中綴式。如何根據(jù)中綴式寫出波蘭表達(dá)式和逆波蘭表達(dá)式？線索?叉樹構(gòu)造中序線索?叉樹在?叉樹的線索鏈表上添加?個頭結(jié)點，令其lchild指向?叉樹的根結(jié)點，rchild指向中序遍歷時的最后?個節(jié)點；同時令?叉樹中序遍歷序列第?個節(jié)點的lchild和最后?個節(jié)點的rchild指向頭結(jié)點。以結(jié)點p為根的?樹中序線索化1.若p?空，左?樹遞歸線索化2.若p的左孩?為空，則給p加上左線索，將其LTag置為1，讓p的左孩?指針指向pre（前驅(qū)）；否則將LTag置為0。3.若pre的右孩?為空，則給pre加上右線索，將其LTag置為1，讓pre的右孩?指針指向p（后繼）；否則將pre的LTag置為0；4.將pre指向剛訪問過的結(jié)點p，即pre=p。5.右?樹遞歸線索化。voidInThreading(BiThrTreep){//pre為全局變量，初始化時其右孩?指針為空，便于在樹的最左點開始建線索。if(p){InThreading(p->lchild);if(!p->lchild){p->LTag=1;p->lchild=pre;}elsep->LTag=0;if(!pre->rchild){pre->RTag=1;pre->rchild=p;}elsepre->RTag=1;pre=p;InThreading(p->rchild);}}帶頭結(jié)點的?叉樹中序線索化voidInOrderThreading(BiThrTree&Thrt,BithrTreeT){//T，并將其中序線索化。Thrt指向頭結(jié)點Thrt=newBiThrNode;Thrt->LTag=0;Thrt->RTag=1;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;pre->RTag=1;Thrt->rchild=pre;}}遍歷線索?叉樹1.在中序線索?叉樹中查找1.若p->LTag=1，則p的左鏈指向其前驅(qū)；2.若p->LTag=0，則說明p有左?樹，結(jié)點的前驅(qū)是遍歷其左?樹時最后訪問的?個結(jié)點。3.若p->RTag=1，則p的右鏈指向其后繼；4.若p->RTag=0，則說明p有右?樹，結(jié)點的后繼是遍歷其右?樹時訪問的第?個結(jié)點。2.在先序線索?叉樹中查找1.若p->LTag=1，則p的左鏈指向其前驅(qū)；2.若p->LTag=0，則說明p有左?樹，此時p的前驅(qū)有兩種情況：若*p是其雙親的左孩?，則其雙親結(jié)點為其前驅(qū)；否則應(yīng)該是其雙親的左?樹上先序遍歷的最后?個結(jié)點。3.若p->RTag=1，則p的右鏈指向其后繼；4.若p->RTag=0，則說明p有右?樹，*p的后繼必為其左?樹數(shù)（若存在）或右?樹根。3.在后序線索?叉樹中查找1.若p->LTag=1，則p的左鏈指向其前驅(qū)；2.若p->LTag=0，當(dāng)p->RTag=0時，則p的右鏈指?其前驅(qū)；若p->RTag=1時，則p的左鏈指向其前驅(qū)；3.若p->RTag=1，則p的右鏈指向其后繼；4.查找其后繼?較復(fù)雜，若*p是?叉樹的根，*