稀疏矩阵十字链表存储结构下实现两个矩阵的加法很乘法

谁告诉我

告诉你什么？不也就是差不多

#define TEST 2 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef struct lnode { int col; ElemType val; struct lnode *next; }LNode; /*/邻接表定义*/ typedef struct { LNode **rv; /*/采用动态分配的算法，目的当然是节省空间，想用多少就用多少*/ int m,n; }LinkMatrix; /*/邻接表操作及算法定义*/ LinkMatrix * InitMatrixL(); /*/初始化邻接表*/ void CreateMatrixL(LinkMatrix *h); /*/创建邻接表*/ void DestroyMatrixL(LinkMatrix *h); /*/销毁邻接表*/ int GetElemL(LinkMatrix *h,int i,int j,ElemType *e); /*/取得第i,j列元素并放在*e中*/ int SetElemL(LinkMatrix *h,int i,int j,ElemType e); /*/修改第i,j列元素的值*/ int InsertElemL(LinkMatrix *h,int r,int c,ElemType v); void DisplayMatrixL(LinkMatrix *A); int MatrixAddL(LinkMatrix *A,LinkMatrix *B,LinkMatrix *C); /*/矩阵加法A+B->C*/ int MatrixMultiL(LinkMatrix *A,LinkMatrix *B,LinkMatrix *C); /*/矩阵乘法A*B->C*/ LinkMatrix *InitMatrixL() { LinkMatrix *h; h=(LinkMatrix*)malloc(sizeof(LinkMatrix)); h->m=h->n=0; h->rv=NULL; return h; } /*---------------------------------------------------*/ void CreateMatrixL(LinkMatrix *h) { int r,c; ElemType v; printf("Please input row,col and number of unZero Element:\n"); /*/输入合法的m,n,t*/ do {scanf("%d%d%d",&h->m,&h->n,&r); }while(h->m<=0||h->n<=0); h->rv=(LNode**)malloc(sizeof(LNode*)*(h->m+1)); for(r=0;r<=h->m;r++) h->rv[r]=NULL; for(;;) { scanf("%d%d%d",&r,&c,&v); if(r<=0&&c<=0&&v<=0) break; if(InsertElemL(h,r,c,v)); /*/插入一个三元组素索,插入成功，准备插入下一个元素*/ else printf("Insert Failed!\n"); } /*/free(cnum);*/ } /*-------------------------------------------------*/ int InsertElemL(LinkMatrix *h,int r,int c,ElemType v) { LNode *p,*q,*s; if(r>h->m||r<=0||v==0||c>h->n||c<=0||h->rv==NULL) return 0; p=h->rv[r]; /*找到行单链表所在位置*/ q=NULL; while(p) { if(p->col>=c)break; q=p; p=p->next; } if(p&&p->col==c) /*存在相同的元素，退出*/ return 0; s=(LNode*)malloc(sizeof(LNode)); s->col=c;s->val=v;s->next=NULL; if(s==NULL) return 0;

if(q==NULL) /*插入在第一个位置*/ { s->next=h->rv[r]; h->rv[r]=s; } else { if(p!=NULL) /*中间插入*/ {s->next=p;q->next=p;} else /*前插入*/ q->next=s; } return 1; } /*-----------------------------------------------------*/ void DisplayMatrixL(LinkMatrix *A) { int i; LNode *p; if(!A||!A->rv) /*不存在矩阵不能显示*/ return; printf("rows=%5d,cols=%5d\n",A->m,A->n); printf("---------------------\n"); for(i=1;i<=A->m;i++) { p=A->rv[i]; while(p) { printf("%5d %5d %5d\n",i,p->col,p->val); p=p->next; } } printf("---------------------\n\n"); } /*------------------------------------------------*/ void DestroyMatrixL(LinkMatrix *A) { int i; LNode *p,*q; if(!A) /*不存在矩阵不能删除*/ return; for(i=1;i<=A->m;i++) { p=A->rv[i]; while(p) { q=p; p=p->next; free(q); } } free(A); } /*-------------------------------------------------*/ int GetElemL(LinkMatrix *h,int i,int j,ElemType *e) /*/取得第i,j列元素并放在*e中*/ { LNode *p; if(i>h->m||i<1||j>=h->m||j<1||!h||!h->rv) return 0; p=h->rv[i]; while(p) { if(p->col==j)break; p=p->next; } if(p) *e=p->val; else return 0; return 1; } /*-----------------------------------------------*/ int SetElemL(LinkMatrix *h,int i,int j,ElemType e) /*/修改第i,j列元素的值*/ { LNode *p,*q; if(i>h->m||i<1||j>=h->m||j<1||!h||!h->rv) return 0; p=h->rv[i];q=NULL; while(p) { if(p->col==j)break; q=p; p=p->next; } if(!p) return 0; if(e) p->val=e; else { if(q==NULL) h->rv[i]=p->next; else q=p->next; free(p); } return 1; } /*--------------------------------------------*/ int MatrixAddL(LinkMatrix *A,LinkMatrix *B,LinkMatrix *C) /*/矩阵加法A+B->C*/ { int i; ElemType re; LNode *p,*q,*r,*qr; if(!A||!B||!C)return 0; /*不存在它些矩阵的定义*/ if(A->m!=B->m||A->n!=B->n) /*不是可以相加的矩阵*/ return 0; C->m=A->m; C->n=A->n; C->rv=(LNode**)malloc(sizeof(LNode*)*(A->m+1)); if(!C->rv) return 0;

for(i=0;i<=A->m;i++) C->rv[i]=NULL; for(i=1;i<=A->m;i++) { p=A->rv[i]; q=B->rv[i]; qr=r=NULL; while(p&&q) { if(p->col<q->col) { /*InsertElemL(C,i,p->col,p->val);直接调用该操作也可以，但是效率不高*/ r=(LNode*)malloc(sizeof(LNode)); r->col=p->col; r->val=p->val; r->next=NULL; if(!r) return 0; if(qr==NULL) /*第一个结点*/ C->rv[i]=r; else qr->next=r; qr=r; p=p->next; } else if(p->col>q->col) { /*InsertElemL(C,i,q->col,q->val);*/ r=(LNode*)malloc(sizeof(LNode)); r->col=q->col; r->val=q->val; r->next=NULL; if(!r) return 0; if(qr==NULL) /*第一个结点*/ C->rv[i]=r; else qr->next=r; qr=r; q=q->next; } else { re=p->val+q->val; /*InsertElemL(C,i,p->col,re);*/ if(re) { r=(LNode*)malloc(sizeof(LNode)); r->col=p->col; r->val=re; r->next=NULL; if(!r) return 0; if(qr==NULL) /*第一个结点*/ C->rv[i]=r; else qr->next=r; qr=r; } p=p->next;q=q->next; } }/*while*/ /*以下用InsertElemL函数的目的是求代码简短，但会牺牲速度*/ while(p){InsertElemL(C,i,p->col,p->val);p=p->next;} while(q){InsertElemL(C,i,q->col,q->val);q=q->next;} } return 1; } /*-------------------------------------------*/ int MatrixMultiL(LinkMatrix *A,LinkMatrix *B,LinkMatrix *C) /*/矩阵乘法A*B->C*/ { int i,j; /*ElemType re;*/ LNode *p,*q;/*,*r1,*qr*/; int *col,r;

if(!A||!B||!C)return 0; /*不存在它些矩阵的定义*/ if(A->n!=B->m) /*不是可以相乘的矩阵*/ return 0; C->m=A->m; C->n=B->n; C->rv=(LNode**)malloc(sizeof(LNode*)*(A->m+1)); if(!C->rv) return 0; col=(int*)malloc(sizeof(int)*(C->n+1)); for(i=0;i<=C->m;i++) C->rv[i]=NULL; for(i=1;i<=C->m;i++) { for(j=1;j<=C->n;j++) col[j]=0; p=A->rv[i]; while(p) { r=p->col; q=B->rv[r]; while(q) { col[q->col]+=p->val*q->val; q=q->next; } p=p->next; }/* 处理一行，结果放在col中*/ /*qr=NULL;//下面的注释代码会用到*/ for(j=1;j<=C->n;j++) { if(col[j]!=0) InsertElemL(C,i,j,col[j]); /*为了简便，直接调用，实际上就是几个元素的单链表插入*/ /* { r1=(LNode*)malloc(sizeof(LNode)); r1->col=j; r1->val=col[j]; if(qr==NULL) C->rv[i]=r1; else qr->next=r1; qr=r1; } */ }

} free(col); return 1; ***************************************************************** 这是邻接表的操作,谁会十字链表的操作

struct CrossNode
{
    int row, col;
    ElemType val;
    CrossNode *right, *down
};

struct CLMatrix
{
    int m, n, t;
    CrossNode* rv[MaxRows + 1];
    CrossNode* cv[MaxColumns + 1];
};

想问一句，楼主到底知不知道十字链接的原理？

[此贴子已经被作者于2005-7-12 11:32:58编辑过]

不太明白 请教

我看完都要两个小时

楼主的程序从哪里整的，看的我眼都花了。。。。。。。。。。