使用三元組實現稀疏矩陣的建立、逆轉、乘法。
乘法沒有使用附加向量，是自己想得。有錯誤請諒解。性能可能沒有書上介紹的好。
代碼如下：（本代碼只經過本人的簡單測試，可能存在問題。請相信自己的能力，敢於質疑。歡迎提供更好的、更快、更簡潔的代碼或者方法和指出錯誤。在ubuntu12.04使用gcc4.6.3版本編譯，在vc中如出現錯誤，請諒解。）
[cpp]
/*
*created by Reage at 2012 November 29
*description: 稀疏矩陣實現，包含乘法、逆轉
*
*blog:http://blog.csdn.net/rentiansheng
*/
#include <stdio.h>
#include <stdlib.h>
#define LINE print_split(20)
typedef struct triple{
int i,j;//行列
int value;
}triple;
typedef struct matrix{
triple * head;
int row,column,count;//矩陣的行、列、稀疏矩陣的元素個數
}matrix;
/*
*description:判斷某一個位置是否已經存在元素
*parameter:
* x:行坐標
* y:列坐標
* count:要查找的元素個數，如果為0表示全部，否則是count的值
*result:找到返回1，未找到返回0
*/
int find_ item (matrix *m, int x, int y, int count ){
triple *tp = m->head;
if ( !count || count > m->count ) count =m->count;
int i;
for (i = 0; i < count - 1; i++){
if ( tp->i == x && tp->j == y) return 1;
tp++;
}
return 0;
}
/*
*初始化稀疏矩陣
*/
void init_matrix (matrix *m, int row, int column, int count){
// if (m->head) free(m->head);//如果矩陣已經存在，釋放原有的數據空間
m->head = (triple *) malloc ( count * sizeof (triple));
if (!m->head){
printf("Allocate memory failed!application will exit.");
exit(0);
}
m->row = row;
m->column = column;
m->count = count;
}
/*
*輸入的稀疏矩陣的可能沒有按照指定的排列順序，用此來整理
*首先按行從小到大，當行等時候按列從小到大
*/
void sort_matrix (matrix *m){
int i, j, count = m->count;
int loc;
triple * tp = m->head;
triple tmp;
for ( i = 0; i < count-1; i++){
loc = i;
for (j = i+1; j < count; j++){
if ( tp[loc].i > tp[j].i){//按行排序
loc = j;
}
else if (tp[loc].i == tp[j].i && tp[loc].j > tp[j].j){
loc = j;
}
}
memcpy (&tmp, &tp[loc], sizeof(triple));
memcpy (&tp[loc], &tp[i], sizeof(triple));
memcpy (&tp[i], &tmp, sizeof(triple));
}
}
/*
*創建一個使用數組存儲的稀疏矩陣
*/
void creat_matrix (matrix *m){
int row,column,count;//存儲稀疏矩陣的行、列、非零元素的個數
int i;
int x,y;
triple * use_triple;
int value;
printf ("please enter sparse matrix row,column:\n");
scanf ("%d%d", &row, &column);
printf ("please enter a number as the number of non-zero elements of the sparse matrix:\n");
scanf ("%d", &count);
init_matrix (m, row, column, count);
use_triple = m->head;
for (i = 0; i < count; i++){
repeat:printf ("please enter %d elements x and y coordinate values:", i+1);
printf ("and a number as element value:");
scanf ("%d%d%d", &x, &y, &value);
if ( find_item (m, x, y, i+1) ) {printf("The position has been there exists an elemetn.\n");goto repeat;}
use_triple->i = x;
use_triple->j = y;
use_triple->value = value;
use_triple ++;
}
sort_matrix (m);
}
/*
*起到分割符的作用，輸出count個‘—’符號
*/
void print_split (int count){
int i;
for (i = 0; i < count; i++)
printf("-");
printf("\n");
}
/*
*數據稀疏矩陣中的內容
*/
void print_matrix (matrix m){
int len = m.count;
int i;
printf("\n");
triple * sm = m.head;
LINE;
for (i = 0; i < len; i++){
printf("%4d | %4d | %d\n", sm->i, sm->j, sm->value);
sm++;
LINE;
}
}
/*
*description: 對稀疏矩陣逆轉了，想將矩陣逆轉，然後進行排序。
*paramtere：
* sm：源稀疏矩陣
* dm：目的稀疏矩陣
*/
void transpose_matrix1 (matrix *sm, matrix *dm){
int i, j, count = sm->count;
triple *dt, *st = sm->head;
init_matrix (dm, sm->row, sm->column, sm->count);//對目的稀疏矩陣進行初始化。
dt = dm->head
;for (i = 0; i < count; i++){
dt->i = st->j;
dt->j = st->i;
dt->value = st->value;
sm++;
dt++;
}
sort_matrix (dm);
}
/*
*description: 對稀疏矩陣逆轉了，
*paramtere：
* sm：源稀疏矩陣
* dm：目的稀疏矩陣
*/
void transpose_matrix (matrix *sm, matrix *dm){
int i, j;
triple *dt, *st;
init_matrix (dm, sm->row, sm->column, sm->count);//對目的稀疏矩陣進行初始化。
dt = dm->head;
for (i = 0; i < sm->column; i++){
st = sm->head;
for (j = 0; j < sm->count; j++){
if ( st->j == i){
dt->i = i;
dt->j = st->i;
dt->value = st->value;
dt++;
}
st++;
}
}
}
/*
*description:向稀疏矩陣中插入一個元素，將元素個數加一
*parameter：
* i,j,value:要插入元素位置的行、列、值
*/
void insert_matrix (matrix *m, int i, int j, int value){
m->count++;
if(1 == m->count)
m->head = (triple *) malloc (sizeof(triple));
else
m->head = (triple *) realloc (m->head, m->count * sizeof(triple));
(m->head)[m->count-1].i = i;
(m->head)[m->count-1].j = j;
(m->head)[m->count-1].value = value;
}
/*
*description:矩陣的乘法
*pararmeter:
* m1,m2:乘數和被乘數
* result:成績結果
*/
void multi_matrix (matrix *m1, matrix *m2, matrix *result){
int tmp ; //保存臨時計算的結果
int i, j; //i表示計算到m2矩陣的第幾列了。
int use = 0; //表示m1正在計算當前行的第幾個非零位置
triple *tp = m1->head;//m1中非零元素的首地址
triple *tp2 = m2->head;//m2中非零元素的首地址
init_matrix (result, 0, 0, 0);//初始化矩陣
if (m1->column != m2->row) return ;//無法做運算的,不滿組運算條件
if ( m1->column > m1->count || m2->row > m2->count){
//有矩陣的成績關系可以知，m1中的一行與m2中的一列做運算。
//如果m1中的非零個數不滿足一行，m2中的非零個數不滿足一列。沒有做運算的必要
return ;
}
/*
*1.首先找本行中的一個m1中非零元素tp[usue]，
*2.查找m2[tp[use].j][i]元素是否存，存在轉到第3步，否則轉到第4步
*3.計算兩者的成績加入到到tmp中。
*4.查找同行的下一個非零元素。如存在轉到第2不，不存在轉到第5步
*5.清空臨時數據，進入下一個行，轉到第1步。
*/
while ( tp < &tp[m1->count] ){//判斷m1中是否還有未計算的元素，沒有的話，計算結束
for (i = 0; i < m2->column; i++){//用來控制與m2中的第幾列做運算
use = 0;//計算本行中的第一個非零元素
tmp = 0;//計算的結果
for (j = 0; j < m2->count; j++){//遍歷m2中的所有元素，差找目標元素
if(tp2[j].j == i && tp2[j].i == tp[use].j ){
tmp += tp2[j].value * tp[use].value;
if( tp[use].j == m1->column){
break;
}
if (tp >= &((m1->head)[m1->count]) || tp[use].i != tp[use+1].i ) break;
use ++;
}
}
if (tmp > 0) insert_matrix (result ,i ,j ,tmp);
}
//轉到下一行
while ( tp->i == tp[1].i){
tp++;
if ( tp >= &((m1->head)[m1->count]) ) return ;
}
tp++;
}
}
void destroy_matrix (matrix *m){
m->row = 0;
m->column = 0;
m->count = 0;
free (m->head);
