T10-數(shù)組與廣義表(矩陣)

矩陣第五章：數(shù)組與廣義表

主講：周翔回顧請簡述一下串的KMP算法思想。預(yù)習(xí)檢查請簡述一下稀疏矩陣的十字鏈表存儲什么是廣義表本章目標(biāo)3特殊矩陣廣義表的遞歸運算重點了解掌握2稀疏矩陣數(shù)組的存儲原理廣義表的存儲原理1數(shù)組數(shù)組是具有相同數(shù)據(jù)元素的有序集合，與線性表相似，數(shù)組中元素的個數(shù)就是數(shù)組的長度。一個二維數(shù)組的邏輯結(jié)構(gòu)：Ele代表數(shù)組中的一個數(shù)據(jù)Row_Col代表數(shù)組元素行列關(guān)系Row代表數(shù)組元素的行間關(guān)系Col代表數(shù)組元素的列間關(guān)系A(chǔ)rray=(Ele,Row_Col)二維數(shù)組中有(p-m+1)(q-n+1)個數(shù)據(jù)元素。數(shù)組中的元素分別受行列關(guān)系的約束，在行關(guān)系約束中，ai,j+1是aij的直接后繼元素，ai,j-1是aij的直接前驅(qū)元素；在列關(guān)系中，ai+1,j是aij的直接后繼元素，ai-1,j是aij的直接前驅(qū)元素。數(shù)組二維數(shù)組也可以看作是一個一維數(shù)組，只不過這個一維數(shù)組的元素，也是一維數(shù)組。同樣的，三維數(shù)組可以看作是元素為二維數(shù)組的一維數(shù)組，或者是元素為一維數(shù)組的二維數(shù)組?！璑維數(shù)組可以看作是元素為m維數(shù)組的N-m維數(shù)組（m>0,N>0,m,N∈N+）。數(shù)組對于數(shù)組，通常只有兩種操作：查詢：將一組類型相同的元素放入一個數(shù)組，根據(jù)下標(biāo)進行訪問修改：給定一個數(shù)組，根據(jù)其下標(biāo)對相應(yīng)位置的數(shù)據(jù)元素進行修改數(shù)組存儲結(jié)構(gòu)有兩種：行序優(yōu)先存儲和列序優(yōu)先存儲（1）所謂行序優(yōu)先，就是按行號遞增的順序一行一行地存取數(shù)據(jù)（2）列序優(yōu)先就是按列號遞增的順序一列一列地存取數(shù)據(jù)數(shù)組特殊矩陣的元素分布有一定規(guī)律，常見的特殊矩陣分為對稱矩陣、三角矩陣和對角矩陣。矩陣的壓縮存儲——特殊矩陣對稱矩陣：若n階方陣中的元素滿足：aij=aji，1≤i，j≤n。則稱其為對稱矩陣。如果按照行序優(yōu)先存儲的存儲方式，將n階對稱矩陣M下三角中的元素（i>j）或者上三角中的元素（i<j）存儲到一維數(shù)組A[0]~A[n(n+1)/2]中（A[0]不存儲數(shù)據(jù)），那么A[k]與矩陣元素aij之間存在著如下的一一對應(yīng)關(guān)系：矩陣的壓縮存儲——特殊矩陣

對角矩陣：若n階方陣的元素滿足：方陣中所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中，則稱之為n階對角矩陣。若方陣主對角線上下方各有b條次對角線，則稱b為矩陣半帶寬，(2b+1)為矩陣帶寬。矩陣的壓縮存儲——特殊矩陣b=1半帶寬為1帶寬為3稀疏矩陣的定義：矩陣的非零元素較零元少，且分布沒有規(guī)律，通常稱這樣的矩陣為稀疏矩陣。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的壓縮存儲與特殊矩陣的壓縮存儲不同：第一，其數(shù)據(jù)元素分布沒有規(guī)律，無法根據(jù)下標(biāo)直接獲得數(shù)組中某個位置對應(yīng)的元素，所示無法實現(xiàn)隨機存儲。第二，它只存儲非零元素，因此，除了存儲非零元素的數(shù)值(value)之外，還要存儲元素在矩陣中的行列數(shù)據(jù)(row,col)，所以我們需要可以唯一確定矩陣中一個非零元素的三元組(row,col,value)。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的創(chuàng)建：創(chuàng)建稀疏矩陣與線性表或者堆棧的思路都大同小異：（1）定義一個struct來存儲結(jié)點信息；（2）創(chuàng)建頭結(jié)點，初始化稀疏矩陣容量；（3）將頭結(jié)點地址返回。矩陣的壓縮存儲——稀疏矩陣TSMatrixNewMatrix(intm,intn){

//新建一個三元組表示的稀疏矩陣

TSMatrixM; M.rows=m; M.cols=n; M.nums=0; returnM;}稀疏矩陣的創(chuàng)建：上述代碼創(chuàng)建的只是一個空矩陣，需要住其中插入非0元素。為了判斷插入元素的位置，根據(jù)行序優(yōu)先的原則，首先將當(dāng)前元素的行值M->data[p].row與三元組數(shù)組的row進行比較，找到合適的插入位置。然后再對列值進行比較，找到合適的插入位置不同的比較結(jié)果流向不同的分支。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的轉(zhuǎn)置：矩陣的壓縮存儲——稀疏矩陣

稀疏矩陣的轉(zhuǎn)置：方案1：根據(jù)矩陣M中的列序進行轉(zhuǎn)置。每查找M中的一列，都要完整地掃描其三元組數(shù)組A。因為A中存儲的數(shù)據(jù)行列是有序的，所以得到的B也是有序的。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的轉(zhuǎn)置：方案2：此方案需要事先知道M中每一列非零元素的個數(shù)，進而求得每一列的第一個元素在數(shù)組B中的位置，然后按照數(shù)組A中數(shù)據(jù)元素的順序進行轉(zhuǎn)置，將數(shù)據(jù)放到B中合適的位置。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的十字鏈表表示：