關於對特殊矩陣的理解
概念:壓縮存儲的矩陣可以分為特殊矩陣和稀疏矩陣
對於那些具有相同元素或零元素在矩陣中分佈具有一定規律的矩陣,被稱之為特殊矩陣,而對於那些零元素數據遠遠多於非零元素數目,並且非零元素的分佈沒有規律的矩陣稱之為稀疏矩陣。
一、特殊矩陣
分類:
1、 對角矩陣(diagonal):M是一個對角矩陣當且僅當i!=j時有M(i,j)=0,如:
2 0 0 0
0 1 0 0
0 0 4 0
0 0 0 6
2、 三對角矩陣(tridiagonal):M是一個對三角矩陣當且僅當|i-j| >1時有M(i,j)= 0,如:
2 1 0 0
3 1 3 0
0 5 2 7
0 0 9 0
3、 下三角矩陣(lower tridiagonal):M是一個下三角矩陣當且僅當I <j時有m(i,j)=0.如:
2 0 0 0
5 1 0 0
4 3 1 0
4 2 7 0
4、 上三角矩陣(upper tridiagonal):M是一個上三角矩陣當且僅當I >j時有m(i,j)=0如:
2 1 3 1
0 1 3 8
0 0 1 6
0 0 0 7
5、 對稱矩陣(symmetric):M是一個下對稱矩陣當且僅當對於所有的i和j有m(i,j)=M(j,i)如:
2 4 6 0
4 1 9 5
6 9 4 7
0 5 7 0
註:對稱矩陣又叫對稱方陣:在一個n階方陣A中,若元素滿足Aij=Aji (0<=I,j<=n-1)則稱其為n階對稱方陣。
特殊矩陣的壓縮存儲:
矩陣中相同的元素隻分配一個存儲空間,零元素不存儲。
由於對稱矩陣中的元素是關於主對角線對稱的,為瞭節省空間,可以為每一對稱元素隻分配一個存儲空間,存儲時隻存儲對稱矩陣中的上三角或者下三角中的元素。這樣存儲單元的總數是:
n*(n+1)/2—————-包含對角線上的元素時
K=
n*(n-1)/2—————-不包含對角線上的元素時
可以以行序為主進行壓縮存儲,也可以以列徐為主進行壓縮存儲。假設以行序為主進行壓縮存儲,可以用一個一位數組b[n*(n+1)/2]或者b[n*(n-1)/2]作為n階對稱矩陣A的存儲結構,則b[k]和矩陣Aij之間存在如下對應關系:
i*(i+1)/2+j————–當i>=j時
K= —————存儲對角線上的元素時
j*(j+1)/2+i————–當I < j時
i*(i-1)/2+j————–當i>=j時
K= —————不存儲對角線上的元素時
j*(j-1)/2+i————–當I < j時
下面用特殊矩陣的壓縮存儲來解決一個實際問題:
[java]
package D0711;
/*
* 特殊矩陣的壓縮存儲—解決查詢城市間距離的問題
*
* 問題描述:六個城市分別為GN、JX、MI、OD、TL、TM
* 將這六個城市從1-6進行編號。任意兩個城市之間的距離可以用一個6*6的矩陣來表示。
* 矩陣的第i行和第i列代表第i個城市,distance(i,j)代表城市i和城市j之間的額距離。
* 由於對於所有的i和j有distance(i,j)=distance(j,i),所以該舉證是一個對稱矩陣。
* 根據該矩陣的特點,編程實現如下要求:
* 1、兩個城市之間的額距離隻存儲一次,自己到自己的距離不要存儲。
* 2、當用戶任意輸入兩個城市的名字,將顯示這兩個城市之間的距離。
* GN JX MI OD TL TM
* GN 0 73 333 114 148 129
* JX 73 0 348 140 163 194
* MI 333 348 0 229 468 250
* OD 114 140 229 0 251 84
* TL 148 163 468 251 0 273
* TM 129 194 250 84 273 0
*
*
*
* 分析:
* 城市距離矩陣不用存儲對角線元素,可用一個6*(6-1)/2 =15個數據元素的一位數組來存儲
* */
import java.util.*;
public class CityDistance {
public static void main(String[] args) {
int[] distance;
String[] cityName = new String[] { "GN", "JX", "MI", "OD", "TL", "TM" };
int n, k;
int i = 0, j = 0;
System.out.println("請輸入城市的數目:");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = n * (n – 1) / 2;// 不要存儲對角線元素
distance = new int[k];
System.out.println(" 請輸入城市矩陣的下三角矩陣");
for (int m = 0; m < k; m++) {
distance[m] = sc.nextInt();
}
String temp;
System.out.println(" 請輸入開始城市簡寫名稱:");
temp = sc.next();
for (int m = 0; m < n; m++) {
if (cityName[m].equals(temp)) {
i = m;
break;
}
}
String flag = "";
do {
System.out.println("請輸入目標城市簡寫名稱:");
temp = sc.next();
for (int m = 0; m < n; m++) {
if (cityName[m].equals(temp)) {
j = m;
break;
}
}
int dis = i > j ? distance[i * (i – 1) / 2 + j] : distance[j * (j – 1) / 2 + i];
System.out.println(cityName[i] + " 到" + cityName[j] + "的距離是:" + dis);
System.out.println("還要繼續查詢嗎?(Y/N)");
flag = sc.next();
} while (flag.equals("y") || flag .equals("Y"));
}
}
/* www.aiwalls.com
* 程序運行結果
*
請輸入城市的數目:
6
請輸入城市矩陣的下三角矩陣
73 333 348 114 140 229 148 163 468 251 129 194 250 84 273
請輸入開始城市簡寫名稱:
GN
請輸入目標城市簡寫名稱:
OD
GN 到OD的距離是:114
還要繼續查詢嗎?(Y/N)
Y
請輸入目標城市簡寫名稱:
GN
GN 到GN的距離是:73
還要繼續查詢嗎?(Y/N)
y
請輸入目標城市簡寫名稱:
TM
GN 到TM的距離是:129
還要繼續查詢嗎?(Y/N)
*
* */
作者:lhfightlhfight