目前新聞群組：tw.bbs.comp.oop

220 28336 <4TA68P$0vw@bbs.mgt.ncu.edu.tw> article
Path: netnews!ctu-gate!news.nctu.edu.tw!news.ncu.edu.tw!news.mgt.ncu.edu.tw!bbs
From: brucetsao.bbs@bbs.mgt.ncu.edu.tw (肉腳布)
Newsgroups: tw.bbs.comp.oop
Subject: Re: 關於這樣的 c code
Date: 19 Mar 2007 04:55:55 GMT
Organization: 中央資管龍貓資訊天地
Lines: 97
Message-ID: <4TA68P$0vw@bbs.mgt.ncu.edu.tw>
NNTP-Posting-Host: bbs.mgt.ncu.edu.tw
Mime-Version: 1.0
Content-Type: text/plain; charset="big5"
Content-Transfer-Encoding: 8bit
X-Trace: news.mgt.ncu.edu.tw 1174280683 30757 140.115.83.240 (19 Mar 2007 05:04:43 GMT)
X-Complaints-To: usenet@news.mgt.ncu.edu.tw
NNTP-Posting-Date: Mon, 19 Mar 2007 05:04:43 +0000 (UTC)
X-Filename: OOP/M.1174280089.A
Xref: netnews tw.bbs.comp.oop:28336

==> elefans.bbs@bbs.cs.nthu.edu.tw (455) 提到:
:   如果想判別一個方陣(複數元數值的方陣)是否列(或行)線性獨立
:   或者是說想算出期行列式值看是否為0
:   這樣子的 source code (C語言)有哪邊可以取得嗎??
:   或者說如果想要找關於矩陣運算的 C 程式碼要去哪邊找??
:   有哪個版或哪個佔有相關的討論嗎??
:   謝謝
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/AlgorithmGossip.htm
Algorithm Gossip: 稀疏矩陣
說明
如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（sparse matrix），由於矩陣在程式中常使用二維陣列表示，二維陣列的大小與使用的記憶體空間成正比，如果多數的元素沒有資料，則會造成記憶體空間的浪費，為此，必須設計稀疏矩陣的陣列儲存方式，利用較少的記憶體空間儲存完整的矩陣資訊。

解法
在這邊所介紹的方法較為簡單，陣列只儲存矩陣的行數、列數與有資料的索引位置及其值，在需要使用矩陣資料時，再透過程式運算加以還原，例如若矩陣資料如下 ，其中0表示矩陣中該位置沒有資料：

0  0  0  0  0  0
0  3  0  0  0  0
0  0  0  6  0  0
0  0  9  0  0  0
0  0  0  0  12 0


這個矩陣是5X6矩陣，非零元素有4個，您要使用的陣列第一列記錄其列數、行數與非零元素個數：

5  6  4


陣列的第二列起，記錄其位置的列索引、行索引與儲存值：

1  1  3
2  3  6
3  2  9
4  4  12


所以原本要用30個元素儲存的矩陣資訊，現在只使用了15個元素來儲存，節省了不少記憶體的使用。

C
#include <stdio.h> #include <stdlib.h> int main(void) {     int num[5][3] = {{5, 6, 4},                      {1, 1, 3},                      {2, 3, 6},                      {3, 2, 9},                      {4, 4, 12}};     int i, j, k = 1;     printf("sparse matrix：\n");     for(i = 0; i < 5; i++) {         for(j = 0; j < 3; j++) {             printf("%4d", num[i][j]);         }         putchar('\n');     }     printf("\nmatrix還原：\n");     for(i = 0; i < num[0][0]; i++) {         for(j = 0; j <
num[0][1]; j++) {             if(k < num[0][2] &&                i == num[k][0] && j == num[k][1]) {                 printf("%4d ", num[k][2]);                 k++;             }             else                 printf("%4d ", 0);         }         putchar('\n');     }     return 0; }


Java
public class SparseMatrix {    public static int[][] restore(int[][] sparse) {        int row = sparse[0][0];        int column = sparse[0][1];                int[][] array = new int[row][column];                int k = 1;        for(int i = 0; i < row; i++) {             for(int j = 0; j < column; j++) {                 if(k <= sparse[0][2] &&                     i == sparse[k][0] && j == sparse[k][1]) {                     array[i][j] = sparse[k][2];                     k++;
}                 else                     array[i][j] = 0;             }          }                 return array;    }    public static void main(String[] args) {        int[][] sparse = {{5, 6, 4},                           {1, 1, 3},                           {2, 3, 6},                           {3, 2, 9},                           {4, 4, 12}};                int[][] array = SparseMatrix.restore(sparse);                for(int i = 0; i < array.length; i++) {             for(int j = 0; j <
array[i].length; j++) {                 System.out.print(array[i][j] + " ");            }              System.out.println();        }     }}







Algorithm Gossip: 多維矩陣轉一維矩陣
說明
有的時候，為了運算方便或資料儲存的空間問題，使用一維陣列會比二維或多維陣列來得方便，例如上三角矩陣、下三角矩陣或對角矩陣，使用一維陣列會比使用二維陣列來得節省空間。

解法
以二維陣列轉一維陣列為例，索引值由0開始，在由二維陣列轉一維陣列時，我們有兩種方式：「以列（Row）為主」或「以行（Column）為主」。由於 C/C++、Java等的記憶體配置方式都是以列為主，所以您可能會比較熟悉前者（Fortran的記憶體配置方式是以行為主）。

以列為主的二維陣列要轉為一維陣列時，是將二維陣列由上往下一列一列讀入一維陣列，此時索引的對應公式如下所示，其中row與column是二維陣列索引，loc表示對應的一維陣列索引：

loc = column + row*行數


以行為主的二維陣列要轉為一維陣列時，是將二維陣列由左往右一行一行讀入一維陣列，此時索引的對應公式如下所示：

loc = row + column*列數


公式的推導您畫圖看看就知道了，如果是三維陣列，則公式如下所示，其中i（個數u1）、j（個數u2）、k（個數u3）分別表示三維陣列的三個索引：

以列為主：loc = i*u2*u3 + j*u3 + k
以行為主：loc = k*u1*u2 + j*u1 + i


更高維度的可以自行依此類推，但通常更高維度的建議使用其它資料結構（例如物件包裝）會比較具體，也不易搞錯。

在C/C++中若使用到指標時，會遇到指標運算與記憶體空間位址的處理問題，此時也是用到這邊的公式，不過必須在每一個項上乘上資料型態的記憶體大小。


實作
C
#include <stdio.h> #include <stdlib.h> int main(void) {     int arr1[3][4] = {{1, 2, 3, 4},                      {5, 6, 7, 8},                      {9, 10, 11, 12}};     int arr2[12] = {0};     int row, column, i;     printf("原二維資料：\n");     for(row = 0; row < 3; row++) {         for(column = 0; column < 4; column++) {             printf("%4d", arr1[row][column]);         }         printf("\n");     }     printf("\n以列為主：");     for(row = 0; row < 3; row++) {         for(column = 0; column <
4; column++) {             i = column + row * 4;             arr2[i] = arr1[row][column];         }     }     for(i = 0; i < 12; i++)         printf("%d ", arr2[i]);     printf("\n以行為主：");     for(row = 0; row < 3; row++) {         for(column = 0; column < 4; column++) {             i = row + column * 3;             arr2[i] = arr1[row][column];         }     }     for(i = 0; i < 12; i++)         printf("%d ", arr2[i]);     printf("\n");     return 0; }


Java
public class TwoDimArray {    public static int[] toOneDimByRow(int[][] array) {        int[] arr = new int[array.length * array[0].length];        for(int row = 0; row < array.length; row++) {             for(int column = 0;                        column < array[0].length; column++) {                 int i = column + row * array[0].length;                 arr[i] = array[row][column];             }         }        return arr;    }        public static int[] toOneDimByColumn(int[][] array) {
int[] arr = new int[array.length * array[0].length];        for(int row = 0; row < array.length; row++) {             for(int column = 0;                         column < array[0].length; column++) {                 int i = i = row + column * array.length;                arr[i] = array[row][column];             }         }        return arr;    }}



--
◎龍貓資訊天地(bbs.mgt.ncu.edu.tw)
◎[brucetsao]From: 140.115.82.88