【文章內(nèi)容簡介】 特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對稱矩陣、三角矩陣。（1）對稱矩陣 在一個n階方陣A中，若元素滿足下述性質(zhì)： aij=aji 0≤i，j≤n1稱為n階對稱矩陣，它的元素是關(guān)于主對角線對稱的，所以只需要存儲矩陣上三角或下三角元素即可，讓兩個對稱的元素共享一個存儲空間。矩陣元素aij和數(shù)組元素sa【k】之間的關(guān)系是k=i(i+1)/2+j i≥j 0≤kn(n+1)/21 k=j(j+1)/2+i i＜j 0≤kn(n+1)/21對稱矩陣的地址計算公式：LOC(aij)=LOC(sa[0])+[I(I+1)/2+J]d，其中I=max(i,j)，J=min(i,j)（2）三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角(不包括主角線)中的元素均為常數(shù)c或零；下三角矩陣的主對角線上方均為常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零。三角矩陣的壓縮存儲：三角矩陣中的重復(fù)元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲在一維數(shù)組sa[n(n+1)/2+1]中，其中c存放在數(shù)組的最后一個元素中。①上三角矩陣中aij和sa[k]之間的對應(yīng)關(guān)系k=i(2ni+1)/2+ji 當(dāng)i≤j k=n(n+1)/2 當(dāng)i＞j②下三角矩陣中aij和sa[k]之間的對應(yīng)關(guān)系k=i(i+1)/2+j 當(dāng)i≥j k=n(n+1)/2 當(dāng)i＜j三角矩陣的壓縮存儲結(jié)構(gòu)是隨機存取結(jié)構(gòu)。:設(shè)矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)，則稱A為稀疏矩陣。為了節(jié)省存儲單元，可用壓縮存儲方法只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行、列位置，所以可用三元組(i，j，aij)來確定非零元素。稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲(三元組表)和鏈?zhǔn)酱鎯?十字鏈表)。稀疏矩陣的壓縮存儲會失去隨機存取功能。,又稱列表。廣義表是n(n≥0)個元素a1，a2，…，ai，…，an的有限序列。其中ai或者是原子或者是一個廣義表。 ?、購V義表通常用圓括號括起來，用逗號分隔其中的元素。 ?、跒榱藚^(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。 ?、廴魪V義表Ls非空(n≥1)，則al是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為Ls的表尾。　 ④廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個表展開后所含括號的層數(shù)稱為廣義表的深度。，實際上這就是一種樹形結(jié)構(gòu)。廣義表的兩個特殊的基本運算：取表頭head(Ls)和取表尾tail(Ls).任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。 head=(a，b)=a，tail(a，b)=(b) 對非空表A和(y)，也可繼續(xù)分解。 注意:廣義表()和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而后者是長度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。廣義表是一種有層次的非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個元素用一個結(jié)點表示，結(jié)點由3個域構(gòu)成，其中一個是tag標(biāo)志位，用來區(qū)分結(jié)點是原子還是子表，當(dāng)tag為零時結(jié)點是子表，第二個域為slink，用以存放子表的地址；當(dāng)tag為1時結(jié)點是原子，第二個域為data，用以存放元素值。第五章 樹和二叉樹：最常用的是樹形圖表示法；還有3種嵌套集合、凹形、廣義表。樹結(jié)構(gòu)的基本術(shù)語（1）結(jié)點的度(Degree) 　樹中的一個結(jié)點擁有的子樹數(shù)稱為該結(jié)點的度(Degree)。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。 　度為零的結(jié)點稱為葉子(Leaf)或終端結(jié)點。度不為零的結(jié)點稱分支結(jié)點或非終端結(jié)點。 　除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。根結(jié)點又稱為開始結(jié)點。（2）①路徑（path）若樹中存在一個結(jié)點序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤ij)，則稱該結(jié)點序列是從kl到kj的一條路徑(Path)。一個結(jié)點的祖先是從根結(jié)點到該結(jié)點路徑上所經(jīng)過的所有結(jié)點，而一個結(jié)點的子孫則是以該結(jié)點為根的子樹中的所有結(jié)點。 結(jié)點的層數(shù)(Level)從根起算：根的層數(shù)為1，其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加1。 雙親在同一層的結(jié)點互為堂兄弟。 樹中結(jié)點的最大層數(shù)稱為樹的高度(Height)或深度(Depth)。 若將樹中每個結(jié)點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)；否則稱為無序樹(UnoderedTree)。若不特別指明，一般討論的樹都是有序樹。 森林(Forest)是m(m≥0)棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個森林；反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴?。：在有序樹中，雖然一個結(jié)點的孩子之間是有左右次序的，但是若該結(jié)點只有一個孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個孩子也有左右之分。二叉樹的性質(zhì)：性質(zhì)1 二叉樹第i層上的結(jié)點數(shù)目最多為2i1(i≥1)。例如5層的二叉樹，第5層上的結(jié)點數(shù)目最多為24=16性質(zhì)2 深度為k的二叉樹至多有2k1個結(jié)點(k≥1)。例如深度為5的二叉樹，至多有251=31個結(jié)點性質(zhì)3 在任意棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則no=n2+1。例如一棵深度為4的二叉樹（a），其終端結(jié)點數(shù)n0為8,度為2的結(jié)點樹為7，則8=7+1，no=n2+1成立（b）其終端結(jié)點數(shù)n0為6,度為2的結(jié)點樹為5，則6=5+1，no=n2+1成立滿二叉樹：一棵深度為k且有2k1個結(jié)點的二又樹稱為滿二叉樹。滿二叉樹的特點：（1）每一層上的結(jié)點數(shù)都達到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。（2）滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹：若一棵深度為k的二叉樹，其前k1層是一棵滿二叉樹，而最下面一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。特點： （1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。 （2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。 （3） 在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點。性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為。?logn?+1 或?log(n+1)?例，具有100個結(jié)點的完全二叉樹的深度為:?lg100?+1=7,26=64 27=128所以?lg100?=6 ,?lg(100+1)?=7 ：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點。每一層的結(jié)點個數(shù)恰好是上一層結(jié)點個數(shù)的2倍。從一個結(jié)點的編號就可推得其雙親，左、右孩子等結(jié)點的編號。編號從0開始①若i=0，則qi為根結(jié)點，無雙親；否則，qi的雙親編號為?(i1)/2?。②若2i+1n，則qi的左孩子的編號是2i+1；否則，qi無左孩子，即qi必定是葉子。③若2i+2n，則qi的右孩子的編號是2i+2；否則，qi無右孩子。對于完全二叉樹而言，使用順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。但對于一般二叉樹來說，采用順序存儲時，為了使用結(jié)點在數(shù)組中的相對位置來表示結(jié)點之間的邏輯關(guān)系，就必須增加一些虛結(jié)點使其成為完全二叉樹的形式。: 二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子。結(jié)點的結(jié)構(gòu)為：二叉鏈表是一種常用的二叉樹存儲結(jié)構(gòu)。建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結(jié)點是在左子樹上，而逗號右邊結(jié)點是在右子樹上。b、按完全二叉樹的層次順序建立結(jié)點。具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中有n1個用來指示結(jié)點的左、右孩子，其余的n+1個為空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。中序遍歷的遞歸算法定義：(1)遍歷左子樹； (2)訪問根結(jié)點； (3)遍歷右子樹。先序遍歷的遞歸算法定義：(1)訪問根結(jié)點； (2)遍歷左子樹； (3)遍歷右子樹。后序遍歷得遞歸算法定義：(1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結(jié)點。遞歸工作棧中包括兩項：一項是遞歸調(diào)用的語句編號，另一項則是指向根結(jié)點的指針。 已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下： 首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確定各子樹根的左右子樹。：n個結(jié)點的二叉鏈表必定存在n+1個空指針域，可以利用這些空指針域，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指針，這種指向前驅(qū)和后繼結(jié)點的指針稱為線索，這種加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。線索鏈表的結(jié)點結(jié)構(gòu)：其中:ltag和rtag是增加的兩個標(biāo)志域，用來區(qū)分結(jié)點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。圖中的實線表示指針，虛線表示線索。 線索二叉樹中，一個結(jié)點是葉結(jié)點的充要條件為：左、右標(biāo)志均是1。: 把對一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點的空指針域按照某種遍歷次序加線索的過程稱為線索化。和中序遍歷算法一樣，遞歸過程中對每結(jié)點僅做一次訪問。因此對于n個結(jié)點的二叉樹，線索化的算法時間復(fù)雜度為O(n)。、森林到二叉樹的轉(zhuǎn)換：樹中每個結(jié)點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。將樹轉(zhuǎn)換成二叉樹：①在所有兄弟結(jié)點之間加一道連線；②對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點的右子樹必為空。將一個森林轉(zhuǎn)換為二叉樹:將森林中的每棵樹轉(zhuǎn)化成二叉樹，然后再將二叉樹的根節(jié)點看做兄弟連在一起，形成一棵二叉樹、森林的轉(zhuǎn)換: 方式是：若二叉樹中結(jié)點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與y用連線連起