close

什麼是稀疏矩陣?

(最底下附完整程式碼)

  簡單來講就是一個矩陣中有很多的零,或者是說非零的元素很少,下面這張圖是一個5*6的稀疏矩陣(Sparse Matrix)。

 

image

 

 

為什麼要用鏈結串列?

 

  最大的好處就是節省空間,以上面的稀疏矩陣為例,有用的元素只有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);

 

image

 

  如果有人對於上方的程式碼有疑慮可以點擊此圖片去觀看程式的運作流程。

 

插入節點

 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

arrow
arrow
    創作者介紹
    創作者 讀書小天地 的頭像
    讀書小天地

    書籍分享天地

    讀書小天地 發表在 痞客邦 留言(0) 人氣()