在程式設計語言中大都提供了陣列作為構造資料型別，本章重點討論陣列以及特殊矩陣的存盤與尋址，
目錄
陣列
陣列的定義
陣列的特點
陣列的基本操作
陣列的存盤結構與尋址
一維陣列
二維陣列
按行優先存盤的尋址
矩陣的壓縮存盤
特殊矩陣和稀疏矩陣
壓縮存盤的基本思想
對稱矩陣
三角矩陣
下三角矩陣：
上三角矩陣：
對角矩陣
稀疏矩陣
轉置操作：
十字鏈表
本章總結
陣列
陣列的定義
陣列是由一組型別相同的資料元素構成的有序集合，每個資料元素稱為一個陣列元素（簡稱為元素），每個元素受n(n≥1)個線性關系的約束，每個元素在n個線性關系中的序號i1、i2、…、in稱為該元素的下標，并稱該陣列為 n 維陣列，
如上圖表示的二維陣列中，元素a22受兩個線性關系的約束，在行上有一個行前驅a21和一個行后繼a23，在列上有一個列前驅a12和和一個列后繼a32，
陣列的特點
- 元素本身可以具有某種結構，屬于同一資料型別；
- 陣列是一個具有固定格式和數量的資料集合，
陣列的基本操作
- 讀操作：給定一組下標，讀出對應的陣列元素；
-
寫操作：給定一組下標，存盤或修改與其相對應的陣列元素，
讀操作和寫操作本質上只對應一種操作——尋址
在陣列上一般不能做插入和洗掉元素的操作，所以不用預留空間，適合采用順序存盤，
陣列的存盤結構與尋址
一維陣列
設一維陣列的下標的范圍為閉區間［l，h］，每個陣列元素占用 c 個存盤單元，則其任一元素 ai 的存盤地址可由下式確定：
Loc(ai)＝Loc(al)＋(i－l)×c
二維陣列
常用的映射方法有兩種：
- 按行優先：先行后列，先存盤行號較小的元素，行號相同者先存盤列號較小的元素，
- 按列優先：先列后行，先存盤列號較小的元素，列號相同者先存盤行號較小的元素，
按行優先存盤的尋址
aij前面的元素個數=陰影部分的面積=整行數×每行元素個數+本行中aij前面的元素個數
=(i -l1)×(h2 -l2＋1)＋(j -l2)
矩陣的壓縮存盤
特殊矩陣和稀疏矩陣
特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規律：對稱矩陣、三角矩陣、對角矩陣 …
稀疏矩陣：矩陣中有很多零元素，
壓縮存盤的基本思想
⑴ 為多個值相同的元素只分配一個存盤空間；
⑵ 對零元素不分配存盤空間，
對稱矩陣
壓縮存盤：存盤下三角部分的元素，由于下三角中共有n×(n+1)/2個元素，可將這些元素按行存盤到一個陣列SA[n×(n+1)/2]中，
aij在一維陣列中的序號=陰影部分的面積=[(i-1)(i-1)+(i-1)]/2 + j = i×(i-1)/2+ j
∵一維陣列下標從0開始 ∴aij在一維陣列中的下標 k= i×(i-1)/2+ j-1
對于下三角中的元素aij（i≥j），在陣列SA中的下標k與i、j的關系為：k＝i×(i-1)/2＋j -1，
上三角中的元素aij（i＜j），因為aij＝aji，則訪問和它對應的元素aji即可，即：k＝j×(j-1)/2＋i -1
三角矩陣
壓縮存盤：只存盤上三角（或下三角）部分的元素，
下三角矩陣：
矩陣中任一元素aij在陣列中的下標k與i、j的對應關系：
上三角矩陣：
矩陣中任一元素aij在陣列中的下標k與i、j的對應關系：
對角矩陣
所有非零元素都集中在以主對角線為中心的帶狀區域中，除了主對角線和它的上下方若干條對角線的元素外，所有其他元素都為零，
尋址計算方法：
元素aij在一維陣列中的序號 =2 + 3(i－2)+( j－i + 2) =2i+ j -2
∵一維陣列下標從0開始 ∴元素aij在一維陣列中的下標 k = 2i+ j -3
稀疏矩陣
由于稀疏矩陣中的非零元素的分布沒有規律，因此將稀疏矩陣中的每個非零元素表示為：(行號，列號，非零元素值)——三元組
三元組表：將稀疏矩陣的非零元素對應的三元組所構成的集合，按行優先的順序排列成一個線性表，
轉置操作：
演算法1：直接取，順序存（時間復雜度較高）
在A的三元組順序表中依次找第0列、第1列、…直到最后一列的三元組，并將找到的每個三元組的行、列交換后順序存盤到B的三元組順序表中，
偽代碼：
1. 設定轉置后矩陣B的行數、列數和非零元個數；
2. 在B中設定初始存盤位置pb；
3. for (col=最小列號; col<=最大列號; col++)
3.1 在A中查找列號為col的三元組；
3.2 交換其行號和列號，存入B中pb位置；
3.3 pb++；
演算法2：順序取，直接存，即在A中依次取三元組，交換其行號和列號放到B 中適當位置，
引入兩個陣列作為輔助資料結構：
num[nu]：存盤矩陣A中某列的非零元素的個數；
cpot[nu]：初值表示矩陣A中某列的第一個非零元素在B中的位置，
num與cpot存在如下遞推關系：
cpot[0]=0； cpot[col]=cpot[col-1]+num[col-1]； 1≤col＜nu
將矩陣A中col列元素存放在B中下標為cpot[col]的位置
偽代碼：
1. 設定轉置后矩陣B的行數、列數和非零元素的個數；
2. 計算A中每一列的非零元素個數；
3. 計算A中每一列的第一個非零元素在B中的下標；
4. 依次取A中的每一個非零元素對應的三元組；
4.1 確定該元素在B中的下標pb；
4.2 將該元素的行號列號交換后存入B中pb的位置；
4.3 預置該元素所在列的下一個元素的存放位置；
十字鏈表
采用鏈接存盤結構存盤三元組表，每個非零元素對應的三元組存盤為一個鏈表結點，結構為：
row：存盤非零元素的行號
col：存盤非零元素的列號
item：存盤非零元素的值
right：指標域，指向同一行中的下一個三元組
down：指標域，指向同一列中的下一個三元組
稀疏矩陣的壓縮存盤——十字鏈表的具體存盤方法
（1） 每一行的非零元素按其列號由right域鏈成一個帶頭結點的回圈鏈表，
（2）每一列的非零元素按其行號由down域鏈成一個帶頭結點的回圈鏈表，
（3）由于各行列鏈表頭結點row域、col域和item域均為空，行鏈表頭結點只用right域，列鏈表頭結點只用down域，故這兩組鏈表頭結點可以合用，
（4）為了實作對某一行（或某一列）頭指標的快速查找，將指向這些頭結點的頭指標存在一個陣列中，
本章總結
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348373.html
標籤：其他
下一篇：二叉樹的三種非遞回遍歷方式