陣列結構(Array)

陣列是一排緊密相鄰的記憶體,我們這邊用陣列來儲存矩陣,以及進行矩陣的相加、轉置、相乘等操作。
稀疏矩陣是一種很多內部元素為0的矩陣,我們可以用傳統的方式儲存,但是比較浪費記憶體,這邊示範改良的三項式儲存方式,共有n列3行,第一列分別表示陣列的列數、行數、非零的元素個數,隨後每列分別表示某個非零元素的列數、行數、實際值,以下為實際的程式碼。

#include <iostream> 
using namespace std; 

void createMatrix(int *a, int dimX, int dimY);
void printfMatrix(int *a, int dimX, int dimY);
void addMatrix(int *a, int *b, int *c, int dimX, int dimY);
void transMatrix(int *a, int *b, int dimX, int dimY);
void multiplyMatrix(int *a, int *b, int *c, int m, int n, int p);
void compressMatrix(int *a, int *b, int m, int n, int p);

int main(){
    int a[12], b[12], add[12], trans[12], multiply[16];
    createMatrix(a, 4, 3);
    createMatrix(b, 4, 3);
    addMatrix(a, b, add, 4, 3);
    transMatrix(a, trans, 4, 3);
    multiplyMatrix(a, trans, multiply, 4, 3, 4);

    printfMatrix(a, 4, 3);
    printfMatrix(b, 4, 3);
    printfMatrix(add, 4, 3);
    printfMatrix(trans, 3, 4);
    printfMatrix(multiply, 4, 4);

    int sparse[36], compress[9];
    int size=6;
    for(int i=0; i < size; i++){
        for(int j=0; j < size; j++){
            sparse[i*size+j] = 0;
        }
    }
    sparse[14] = 9;
    sparse[25] = 3;
    compressMatrix(sparse, compress, size, size, 2);
    printfMatrix(sparse, 6, 6);
    printfMatrix(compress, 3, 3);

    system("PAUSE");
    return 0;
}

void createMatrix(int *a, int dimX, int dimY){
    //每個矩陣值範圍都從0~9
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            a[row*dimY+col] = rand()%10;
        }
    }
}

void printfMatrix(int *a, int dimX, int dimY){
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            cout << a[row*dimY+col] << '\t';
        }
        cout << '\n';
    }
    cout << '\n';
}

void addMatrix(int *a, int *b, int *c, int dimX, int dimY){
    if(dimX<=0 || dimY<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            c[row*dimY+col] = a[row*dimY+col] + b[row*dimY+col];
        }
    }
}

void transMatrix(int *a, int *b, int dimX, int dimY){
    if(dimX<=0 || dimY<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            b[col*dimX+row] = a[row*dimY+col];
        }
    }
}

void multiplyMatrix(int *a, int *b, int *c, int m, int n, int p){
    //matrix(m*n) * matrix(n*p) =  matrix(m*p)
    if(m<=0 || n<=0 || p<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < m; row++){
        for(int col=0; col < p; col++){
            int temp = 0;
            for(int k=0; k < n; k++){
                temp = temp + a[row*n+k] * b[k*p+col];
            }
            c[row*p+col] = temp;
        }
    }
}

void compressMatrix(int *a, int *b, int m, int n, int p){
    //m*n的矩陣共有p個元素不為0
    if(m<=0 || n<=0){
        cout << "維度必須大於0" << endl;
        return;
    }

    b[0] = m;
    b[1] = n;
    b[2] = p;
    int temp = 3;
    for(int row=0; row < m; row++){
        for(int col=0; col < n; col++){
            if(a[row*n+col]!=0){
                b[temp] = row;
                b[temp+1] = col;
                b[temp+2] = a[row*n+col];
                temp += 3;
            }
        }
    }
}

陣列(array)

陣列:
1、陣列資料型態可以是int、float、char等等,以下是宣告的範例。

int iarr[10];     // 宣告10個元素的整數陣列
char carr[10];    // 宣告10個元素的字元陣列

2、下面是靜態陣列的宣告方式,靜態陣列長度必須事先決定,不可以使用變數來事後決定陣列的長度。

int arr1[10];   //正確
const int size = 10;
int arr2[size];   //正確
int size2 = 10;
int arr3[size2];  //錯誤

3、可以使用 sizeof()運算子來得知陣列的長度

int iarr[] = {1, 2, 3, 4, 5, 6};
int length = sizeof(iarr) / sizeof(iarr[0]);  //length=6

4、定義於函式主體外的內建型array元素會被初始化為0,定義於函式主體內的內建型array元素不會被初始化。
5、不可以將陣列直接指定給另一個陣列,或是直接比較兩個陣列是否相同。

int arr1[5];
int arr2[5];
...
arr1 = arr2;    // 錯誤
if(arr1 == arr2){  // 錯誤
    ...
}

6、如果要將陣列指定給另一個陣列,只能循序一個一個元素進行複製,同樣的,如果想比較兩個陣列元素內容是否相同,也要用一個個元素進行比對。

int arr1[5];
int arr2[5];
for(int i=0; i<5; i++) {
    arr1[i] = arr2[i];
}

動態配置array:
1、以下兩種情況下,必須時使用動態的方式來配置記憶體:
a:必須到執行期,才能知道要分配多少空間給變數。
b:需要很多記憶體(可能是大量要計算的資料),由於靜態陣列的空間在stack上,因此無法分配過於大量的記憶體。
2、動態陣列使用new運算子,選擇型態以及所需要的空間,並傳回該空間的位址,程式結束前必須使用delete將空間釋放,否則會有記憶體洩漏的問題。

int *ptr = new int;
int *ptr2 = new int[1000];
delete ptr
delete [] ptr2

3、如果陣列內的元素為class物件時,會用default建構式來初始化每個元素,如果是內建型別則元素不會初始化。

string *psa = new string[10]; //這array有10個空字串
int *pia = new int[10];       //這10個int未初始化(不會等於0)

4、可在array尺寸後加一對空小括號來初始化,但不像靜態配置可以初始化為不同值。

int *pia2 = new int[10](1024); //這10個int初始化為1024

二維陣列:
1、二維陣列使用陣列名稱與兩個索引值來指定存取陣列元素,其宣告方式與一維陣列類似,下面配置5*10=50個整數的記憶體空間給陣列來使用:

int iarr[5][10];

2、二維陣列使用兩個索引值來指定存取陣列,這兩個索引值都是由0開始,下面簡單的示範二維陣列的賦值和存取:

#include <cstdio>
#include <cstdlib>

#define ROW 3
#define COLUMN 5

int main(void) {
    int iarr[ROW][COLUMN]; 
    int count = 0;

    for(int i=0; i

3、也可以在宣告二維陣列的同時指定二維陣列的值,以下宣告了一個2列3行的陣列:

int iarr[2][3] = {{1, 2, 3}, {4, 5, 6}};