什麼是稀疏矩陣?
(最底下附完整程式碼)
簡單來講就是一個矩陣中有很多的零,或者是說非零的元素很少,下面這張圖是一個5*6的稀疏矩陣(Sparse Matrix)。
為什麼要用鏈結串列?
最大的好處就是節省空間,以上面的稀疏矩陣為例,有用的元素只有9個,如果用陣列來做需要5*6的空間,所以選擇鏈結串列只需要9個節點就可以搞定,但是缺點就是比較複雜。
建立鏈結串列的節點(Node)
1 2 3 4 5 |
typedef struct Sparse { int data, row, col; Sparse *next; }MAT; |
我建立的節點總共包含了4個元素分別是row、col、data、next。
row跟col就是用來記錄元素在矩陣中的位置,data用來記錄數值,next用來指向下一個,會以上到下左到右來記錄。
新增節點
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void add_Node(int row, int col, int data, Sparse *cu) { while(true) { if(cu->next == NULL) { cu->next = new Sparse; cu = cu->next; cu->row = row; cu->col = col; cu->data = data; cu->next = NULL; break; } cu = cu->next; } } |
建立過程跟這個一樣(點擊圖片到外部空間觀看)。
建立一個稀疏矩陣。
1 2 3 4 5 6 7 8 9 10 11 12 13 |
MAT *matrix; matrix = new Sparse; matrix->next = NULL; add_Node(0, 2, 1, matrix); add_Node(0, 4, 2, matrix); add_Node(1, 0, 1, matrix); add_Node(1, 3, 6, matrix); add_Node(2, 1, 1, matrix); add_Node(3, 3, 3, matrix); add_Node(3, 5, 1, matrix); add_Node(4, 2, 2, matrix); add_Node(4, 5, 6, matrix); |
查看節點
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
void check_Node(int row, int col, Sparse *cu) { Sparse *copy; copy = cu->next; std::cout<<"row"<<" "<<" col"<<" "<<" data"<<std::endl; while(true) { cu = cu->next; if(cu != NULL) std::cout<<" "<<cu->row<<"\t"<<cu->col<<"\t"<<cu->data<<std::endl; else break; } std::cout<<"-----------------------------"<<std::endl; for(int i=0;i<row; i++) { for(int j=0;j<col;j++) { if(copy != NULL) if(copy->row == i) if(copy->col == j) { std::cout<<" "<<copy->data<<" "; copy = copy->next; continue; } std::cout<<" 0 "; } std::cout<<std::endl; } } |
主程式:
1 |
check_Node(5, 6, matrix); |
如果有人對於上方的程式碼有疑慮可以點擊此圖片去觀看程式的運作流程。
插入節點
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
void insert_Node(int row, int col, int data, Sparse *cu) { Sparse *ne; while(true) { ne = cu; cu = cu->next; if(cu == NULL) { ne->next = new Sparse; ne = ne->next; ne->row = row; ne->col = col; ne->data = data; ne->next = NULL; break; } if(cu->row == row) { if(cu->col > col) { Sparse *in; in = new Sparse; in->row = row; in->col = col; in->data = data; ne->next = in; in->next = cu; break; } else if(cu->col == col) { cu->data = data; break; } } else if(cu->row > row) { Sparse *in; in = new Sparse; in->row = row; in->col = col; in->data = data; ne->next = in; in->next = cu; break; } } } |
主程式:
1 2 3 4 |
insert_Node(2, 4, 7, matrix); insert_Node(2, 4, 9, matrix); insert_Node(0, 1, 3, matrix); insert_Node(4, 5, 5, matrix); |
對於上方程式碼有疑慮的可以點擊此動畫參考。
矩陣相加
插入節點跟矩陣相加是很類似的東西,那矩陣相乘我也不做了,因為既然做得出相加就一定做得出相乘,而且結構都差不多。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
void add_up_Node(Sparse *first, Sparse *second) { Sparse *cu; second = second->next; while(true) { cu = first; first = first->next; if(second == NULL) break; if(first == NULL) cu->next = second; if(first->row == second->row) { if(first->col == second->col) { first->data = (first->data + second->data); second = second->next; }else if(first->col > second->col) { Sparse *in; in = new Sparse; in->row = second->row; in->col = second->col; in->data = second->data; cu->next = in; in->next = first; second = second->next; } }else if(first->row > second->row) { Sparse *in; in = new Sparse; in->row = second->row; in->col = second->col; in->data = second->data; cu->next = in; in->next = first; second = second->next; } } } |
主程式:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
MAT *matrix, *matrix2; matrix = new Sparse; matrix->next = NULL; matrix2 = new Sparse; matrix2->next = NULL; add_Node(0, 2, 1, matrix); add_Node(0, 4, 2, matrix); add_Node(1, 0, 1, matrix); add_Node(1, 3, 6, matrix); add_Node(2, 1, 1, matrix); add_Node(3, 3, 3, matrix); add_Node(3, 5, 1, matrix); add_Node(4, 2, 2, matrix); add_Node(4, 5, 6, matrix); add_Node(0, 0, 2, matrix2); add_Node(1, 4, 1, matrix2); add_Node(3, 5, 1, matrix2); add_Node(4, 1, 4, matrix2); add_up_Node(matrix, matrix2); |
完整程式碼:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 |
#include<iostream> #include<cstring> typedef struct Sparse { int data, row, col; Sparse *next; }MAT; void add_Node(int row, int col, int data, Sparse *cu) { while(true) { if(cu->next == NULL) { cu->next = new Sparse; cu = cu->next; cu->row = row; cu->col = col; cu->data = data; cu->next = NULL; break; } cu = cu->next; } } void check_Node(int row, int col, Sparse *cu) { Sparse *copy; copy = cu->next; std::cout<<"row"<<" "<<" col"<<" "<<" data"<<std::endl; while(true) { cu = cu->next; if(cu != NULL) std::cout<<" "<<cu->row<<"\t"<<cu->col<<"\t"<<cu->data<<std::endl; else break; } std::cout<<"-----------------------------"<<std::endl; for(int i=0;i<row; i++) { for(int j=0;j<col;j++) { if(copy != NULL) if(copy->row == i) if(copy->col == j) { std::cout<<" "<<copy->data<<" "; copy = copy->next; continue; } std::cout<<" 0 "; } std::cout<<std::endl; } } void insert_Node(int row, int col, int data, Sparse *cu) { Sparse *ne; while(true) { ne = cu; cu = cu->next; if(cu == NULL) { ne->next = new Sparse; ne = ne->next; ne->row = row; ne->col = col; ne->data = data; ne->next = NULL; break; } if(cu->row == row) { if(cu->col > col) { Sparse *in; in = new Sparse; in->row = row; in->col = col; in->data = data; ne->next = in; in->next = cu; break; } else if(cu->col == col) { cu->data = data; break; } } else if(cu->row > row) { Sparse *in; in = new Sparse; in->row = row; in->col = col; in->data = data; ne->next = in; in->next = cu; break; } } } void add_up_Node(Sparse *first, Sparse *second) { Sparse *cu; second = second->next; while(true) { cu = first; first = first->next; if(second == NULL) break; if(first == NULL) cu->next = second; if(first->row == second->row) { if(first->col == second->col) { first->data = (first->data + second->data); second = second->next; }else if(first->col > second->col) { Sparse *in; in = new Sparse; in->row = second->row; in->col = second->col; in->data = second->data; cu->next = in; in->next = first; second = second->next; } }else if(first->row > second->row) { Sparse *in; in = new Sparse; in->row = second->row; in->col = second->col; in->data = second->data; cu->next = in; in->next = first; second = second->next; } } } int main() { MAT *matrix, *matrix2; matrix = new Sparse; matrix->next = NULL; matrix2 = new Sparse; matrix2->next = NULL; add_Node(0, 2, 1, matrix); add_Node(0, 4, 2, matrix); add_Node(1, 0, 1, matrix); add_Node(1, 3, 6, matrix); add_Node(2, 1, 1, matrix); add_Node(3, 3, 3, matrix); add_Node(3, 5, 1, matrix); add_Node(4, 2, 2, matrix); add_Node(4, 5, 6, matrix); insert_Node(2, 4, 1, matrix); insert_Node(2, 4, 5, matrix); insert_Node(0, 1, 3, matrix); insert_Node(4, 5, 5, matrix); add_Node(0, 0, 2, matrix2); add_Node(1, 4, 1, matrix2); add_Node(3, 5, 1, matrix2); add_Node(4, 1, 4, matrix2); add_up_Node(matrix, matrix2); check_Node(5, 6, matrix); return 0; } |
執行結果:
row col data
0 0 2
0 1 3
0 2 1
0 4 2
1 0 1
1 3 6
1 4 1
2 1 1
2 4 5
3 3 3
3 5 2
4 1 4
4 2 2
4 5 5
-----------------------------
2 3 1 0 2 0
1 0 0 6 1 0
0 1 0 0 5 0
0 0 0 3 0 2
0 4 2 0 0 5
留言列表