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

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

主講：周翔回顧請簡述一下串的KMP算法思想。預習檢查請簡述一下稀疏矩陣的十字鏈表存儲什么是廣義表本章目標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ù)下標進行訪問修改：給定一個數(shù)組，根據(jù)其下標對相應位置的數(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之間存在著如下的一一對應關(guān)系：矩陣的壓縮存儲——特殊矩陣

對角矩陣：若n階方陣的元素滿足：方陣中所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中，則稱之為n階對角矩陣。若方陣主對角線上下方各有b條次對角線，則稱b為矩陣半帶寬，(2b+1)為矩陣帶寬。矩陣的壓縮存儲——特殊矩陣b=1半帶寬為1帶寬為3稀疏矩陣的定義：矩陣的非零元素較零元少，且分布沒有規(guī)律，通常稱這樣的矩陣為稀疏矩陣。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的壓縮存儲與特殊矩陣的壓縮存儲不同：第一，其數(shù)據(jù)元素分布沒有規(guī)律，無法根據(jù)下標直接獲得數(shù)組中某個位置對應的元素，所示無法實現(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)先的原則，首先將當前元素的行值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中合適的位置。矩陣的壓縮存儲——稀疏矩陣稀疏矩陣的十字鏈表表示：