[求助]着段程序怎么改？求助！ - 数据结构与算法

楼主

问题点数：0 回复次数：0

[求助]着段程序怎么改？求助！

设计题目！
稀疏矩阵的算法设计，设计矩阵为N*M的
1 选用邻接表结构存储！
2 实现矩阵的转置运算
3 实现2个矩阵的加法，乘法运算
4 矩阵的输出按普通矩阵列输出！

（只因老师要求用C++编写，小弟C++ 很才所以求各位大侠帮忙改为C++ 小弟拜谢！还有最后1段 main函数不会写了希望大侠顺便帮忙添加！！！！！！！！！也就是矩阵的输出没能实现）

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
/*类型定义*/
typedef int ElemType;
//邻接表结点定义*/
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;
}