特殊矩陣 – JAVA編程語言程序開發技術文章

          關於對特殊矩陣的理解
概念:壓縮存儲的矩陣可以分為特殊矩陣和稀疏矩陣
      對於那些具有相同元素或零元素在矩陣中分佈具有一定規律的矩陣,被稱之為特殊矩陣,而對於那些零元素數據遠遠多於非零元素數目,並且非零元素的分佈沒有規律的矩陣稱之為稀疏矩陣。
一、特殊矩陣
  分類:
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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *