#include "string.h"
#include "ctype.h"
#include "malloc.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "mem.h"
#include "alloc.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 100
#define MAXRC 20
typedef int Status;
typedef int ElemType;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; /* 非零元三元组表,data[0]未用 */
int rpos[MAXRC+1]; /* 各行第一个非零元素的位置表*/
int mu,nu,tu; /* 矩阵的行数、列数和非零元个数*/
}RLSMatrix;
typedef struct OLNode
{
int i,j;
ElemType e;
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct
{
OLink *rhead,*chead;
int mu,nu,tu;
}CrossList;
Status CreateSMatrix(RLSMatrix *M);
void DestroySMatrix(RLSMatrix *M);
void PrintSMatrix(RLSMatrix M);
Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);
Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);
Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);
Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T);
int menu_select();
Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C);
Status Exchange(RLSMatrix M,CrossList *N);
Status Show(CrossList N);
Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M);
Status DestoryCrossList(CrossList *M);
void About();
main()
{
RLSMatrix A,B,C;
CrossList N;
clrscr();
About();
for(;;)
{
switch(menu_select()) /*调用主菜单函数，返回值做开关语句的条件*/
{
case 1:clrscr();
printf("\n\n\n\t-------------Create Sparse Matrix A-----------------");
CreateSMatrix(&A); break;
case 2:clrscr();
printf("\n\n\n\t-------------Create Sparse Matrix B-----------------");
CreateSMatrix(&B); break;
case 3:
Operate(A,B,&C);
break;
case 4:Change(A,B,C,&N); break;
case 5:About();break;
case 6:
DestroySMatrix(&A);
DestroySMatrix(&B);
DestroySMatrix(&C);
DestoryCrossList(&N);
exit(0);
}
}
}
int menu_select()
{
char *menu[]={
"",
"",
"",
" +--------------MENU--------------+", /*定义菜单字符串数组*/
" | |",
" | 1.Create Sparse Matrix A |",
" | 2.Create Sparse Matrix B |",
" | 3.Operate |",
" | 4.Change into CrossList |",
" | 5.About... |",
" | 6.Quit |",
" | |",
" | |",
" +--------------------------------+",
" By Zacard",
" 06 07 10",};
char s[3]; /*以字符形式保存选择号*/
int c,i; /*定义整形变量*/
gotoxy(1,25);
printf("Any key to enter menu......\n");
getch();
clrscr();
for(i=0;i<16;i++) /*输出主菜单数组*/
{ gotoxy(10,i+1);
cprintf("%s",menu[i]);
}
window(1,1,80,25); /*恢复原窗口大小*/
gotoxy(10,21);
do{printf("\n Enter your choice(1~6):");
scanf("%s",s);
c=atoi(s); /*将输入的字符串转化为整形数*/
}while(c<1||c>6);
return c; /*返回选择项，主程序根据该数调用相应的函数*/
}
Status CreateSMatrix(RLSMatrix *M) /* 创建稀疏矩阵M */
{
int i; /*用于暂存data域内容*/
Triple T;
int flag=0,mis; /*标志，输入正确为0*/
printf("\nPlease input the row,col,and nonzero element number of the Sparse Matrix.");
printf("\nForm:row num,col num,nonzero element num\n");
scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
(*M).data[0].i=0; /* 为以下比较做准备 */
for(i=1;i<=(*M).tu;i++)
{ mis=0;
do
{
if(flag)
{
printf("ERROR INPUT!\n");
flag=0;
mis++;}
if(mis==3)
{
printf("Fail Create !");
return OK;}
printf("Please input the row,col and value of the %dth nonzero element:",i);
scanf("%d,%d,%d",&T.i,&T.j,&T.e);
if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu) /* 行或列超出范围 */
flag=1;
if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j) /* 没有按顺序输入非零元素 */
flag=1;
}while(flag); /* 当输入有误,重新输入 */
(*M).data[i]=T;
}
for(i=1;i<=(*M).tu;i++) /* 计算rpos[] */
for(T.i=0;T.i<(*M).data[i].i-(*M).data[i-1].i;T.i++) /* (*M).data[i]为第一个非0元素 */
(*M).rpos[(*M).data[i].i-T.i]=i;
for(i=(*M).data[(*M).tu].i+1;i<=(*M).mu;i++) /* 给最后没有非零元素的几行赋值 */
(*M).rpos[i]=(*M).tu+1;
PrintSMatrix(*M);
return OK;
}
void PrintSMatrix(RLSMatrix M) /* 输出稀疏矩阵M */
{
int i,j,k;
printf("\n ");
for(i=1,k=1;i<=M.mu;i++)
{
for(j=1;j<=M.nu;j++)
{
if(M.data[k].i==i&&M.data[k].j==j)
{printf("%d\t",M.data[k].e); k++;}
else printf("0\t");
while(j==M.nu)
{printf("\n ");break;}
}
}
}
Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵的和Q=M+N */
{
int k,p,q;
if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;
(*Q).mu=M.mu;
(*Q).nu=M.nu;
(*Q).tu=0;
M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */
N.rpos[N.mu+1]=N.tu+1;
for(k=1;k<=M.mu;++k) /* 对于每一行，k指示行号 */
{
(*Q).rpos[k]=(*Q).tu+1;
p=M.rpos[k]; /* p指示M矩阵第k行当前元素的序号 */
q=N.rpos[k]; /* q指示N矩阵第k行当前元素的序号 */
/* 当某一行不存在非零元素时，它对应的非零位置表的值为下一个非零元素的位置*/
while(p<M.rpos[k+1]&&q<N.rpos[k+1]) /* 故当某行非零元位置等于下一行非零元位置时，它不存在非零元素*/
{ /* M,N矩阵均有第k行元素未处理 */
if(M.data[p].j==N.data[q].j) /* M矩阵当前元素和N矩阵当前元素的列相同 */
{
(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e; /* 位置相同*/
if((*Q).data[(*Q).tu+1].e!=0) /* 相加结果为0?*/
{
++(*Q).tu;
(*Q).data[(*Q).tu].i=k;
(*Q).data[(*Q).tu].j=M.data[p].j;
}
++p;
++q;
}
else if(M.data[p].j<N.data[q].j)
{ /* M矩阵当前元素的列<N矩阵当前元素的列 */
++(*Q).tu;
(*Q).data[(*Q).tu].e=M.data[p].e;
(*Q).data[(*Q).tu].i=k;
(*Q).data[(*Q).tu].j=M.data[p].j;
++p;
}
else /* M矩阵当前元素的列>N矩阵当前元素的列 */
{
++(*Q).tu;
(*Q).data[(*Q).tu].e=N.data[q].e;
(*Q).data[(*Q).tu].i=k;
(*Q).data[(*Q).tu].j=N.data[q].j;
++q;
}
}
while(p<M.rpos[k+1]) /* M矩阵还有k行的元素未处理 */
{
++(*Q).tu;
(*Q).data[(*Q).tu].e=M.data[p].e;
(*Q).data[(*Q).tu].i=k;
(*Q).data[(*Q).tu].j=M.data[p].j;
++p;
}
while(q<N.rpos[k+1]) /* N矩阵还有k行的元素未处理 */
{
++(*Q).tu;
(*Q).data[(*Q).tu].e=N.data[q].e;
(*Q).data[(*Q).tu].i=k;
(*Q).data[(*Q).tu].j=N.data[q].j;
++q;
}
}
return OK;
}
Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵的差Q=M-N */
{
int i;
if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;
for(i=1;i<=N.tu;++i) /* 对于N的每一元素,其值乘以-1 */
N.data[i].e*=-1;
ADD(M,N,Q); /* Q=M+(-N) */
return OK;
}
Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵乘积Q=M＊N*/
{
int arow,brow,p,q,ccol,ctemp[MAXRC+1]; /* ctemp[MAXRC+1]为列元素累加器*/
if(M.nu!=N.mu) return ERROR; /* 矩阵M的列数应和矩阵N的行数相等 */
(*Q).mu=M.mu; /* Q初始化 */
(*Q).nu=N.nu;
(*Q).tu=0;
M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */
N.rpos[N.mu+1]=N.tu+1;
if(M.tu*N.tu!=0) /* M和N都是非零矩阵 */
{
for(arow=1;arow<=M.mu;++arow)
{ /* 从M的第一行开始，到最后一行，arow是M的当前行 */
for(ccol=1;ccol<=(*Q).nu;++ccol)
ctemp[ccol]=0; /* Q的当前行的各列元素累加器清零 */
(*Q).rpos[arow]=(*Q).tu+1; /* Q当前行的第1个元素位于上1行最后1个元素之后 */
for(p=M.rpos[arow];p<M.rpos[arow+1];++p)
{ /* 对M当前行中每一个非零元 */
brow=M.data[p].j; /* 找到对应元在N中的行号(M当前元的列号) */
for(q=N.rpos[brow];q<N.rpos[brow+1];++q)
{
ccol=N.data[q].j; /* 乘积元素在Q中列号 */
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
} /* 求得Q中第arow行的非零元 */
for(ccol=1;ccol<=(*Q).nu;++ccol) /* 压缩存储该行非零元 */
if(ctemp[ccol])
{
if(++(*Q).tu>MAXSIZE) return ERROR;
(*Q).data[(*Q).tu].i=arow;
(*Q).data[(*Q).tu].j=ccol;
(*Q).data[(*Q).tu].e=ctemp[ccol];
}
}
}
return OK;
}
Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T)
{
int col,p,q,t,num[MAXRC+1],cpot[MAXRC+1];
(*T).mu=M.nu; /* num[]存M每列非0元个数 */
(*T).nu=M.mu; /* cpot[]存每列第一个非0元序号 */
(*T).tu=M.tu;
if((*T).tu){
for(col=1;col<=M.nu;++col) num[col]=0;
for(t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p){
col=M.data[p].j; q=cpot[col];
(*T).data[q].i=M.data[p].j;
(*T).data[q].j=M.data[p].i;
(*T).data[q].e=M.data[p].e;
++cpot[col];
}
}
PrintSMatrix(M);
printf("\nTranspose:\n");
PrintSMatrix(*T);
return OK;
}
Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C)
{
int c;
char t;
do{
clrscr();
printf("\nInput your choice:\n(ADD--1,SUB--2,MUL--3,Transpose A--4,Transpose B--5,QUIT--any except 1~5)\n");
scanf("%d",&c);
switch(c)
{
case 1:
if(A.mu!=B.mu||A.nu!=B.nu)
{
printf("Can't,condition misfit!\n");
break;
}
ADD(A,B,C);
PrintSMatrix(A);
printf("\n\t(+)\n");
PrintSMatrix(B);
printf("\n\t(=)\n");
PrintSMatrix(*C);break;
case 2:
if(A.mu!=B.mu||A.nu!=B.nu)
{
printf("Can't,condition misfit!\n");
break;
}
SubtS(A,B,C);
PrintSMatrix(A);
printf("\n\t(-)\n");
PrintSMatrix(B);
printf("\n\t(=)\n");
PrintSMatrix(*C);break;
case 3:
if(A.nu!=B.mu)
{
printf("Can't,condition misfit\n");
break;
}
Mult(A,B,C);
PrintSMatrix(A);
printf("\n\t(*)\n");
PrintSMatrix(B);
printf("\n\t(=)\n");
PrintSMatrix(*C);break;
case 4:
FastTransposeSMatrix(A,C);break;
case 5:
FastTransposeSMatrix(B,C);break;
default: return OK;
}/* switch */
printf("Want to continue? (y/n)?");
t=getch();
}while(t=='y');
return OK;
}
void DestroySMatrix(RLSMatrix *M) /* 销毁稀疏矩阵M(使M为0行0列0个非零元素的矩阵) */
{
(*M).mu=0;
(*M).nu=0;
(*M).tu=0;
}
