鏈結串列(Linked List)

鏈結串列是由許多相同資料型態的項目,所組成的有限序列,這邊使用單向鏈結串列,串列每個節點除了要儲存原本的資料,還必須要儲存下一筆資料的位址,大概為以下的流程:
1.建立新節點,並另一流動指標指向頭節點(ptr=head)。
2.建立另一個新節點,並把兩個節點串起來(ptr->next=newnode)。
3.將流動指標指向剛剛建立的節點(ptr=ptr->next)。
4.重複上面2和3的步驟。

#include <iostream> 
using namespace std;

struct List{
    char *name;
    int age;
    List *next;
};

List *createList(char*name, int age);
void addANode(List *&ptr, char*name, int age); //要用參考才能改變ptr引數的指向位址
void deleteList(List *head);
void printfList(List *head);

int main(){
    List *head = createList("Mike", 18);
    List *ptr = head;
    addANode(ptr, "Bill", 20);
    addANode(ptr, "Lisa", 15);

    ptr = head;
    printfList(ptr);

    deleteList(head);
    return 0;
}

List *createList(char*name, int age){
    List *head = new List;
    if (!head){
        cout << "配置記憶體失敗" << endl;
        exit(1);
    }
    head->name = name;
    head->age = age;
    head->next = NULL;
    return head;
}
void addANode(List *&ptr, char*name, int age){
    List *newnode = new List;
    if (!newnode){
        cout << "配置記憶體失敗" << endl;
        exit(1);
    }
    newnode->name = name;
    newnode->age = age;
    newnode->next = NULL;
    ptr->next = newnode;
    ptr = ptr->next;
}

void printfList(List *ptr){
    while (ptr != NULL){
        cout << "姓名:" << ptr->name << '\t' << "年齡:" << ptr->age << endl;
        ptr = ptr->next;
    }
}

void deleteList(List *head){
    while (head != NULL){
        List *delptr = head;
        head = head->next;
        delete delptr;
    }
}

陣列結構(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;
            }
        }
    }
}