数据结构 | 十字链表完成稀疏矩阵相加
文章目录
十字链表的实现
- 当稀疏矩阵的非零元数量和位置在操作过程中变化较大时(如矩阵相加),便不再适宜采用顺序存储,此时使用链式存储更为恰当。
- 十字链表的实现
typedef struct{
int i,j;
ElemType e;
OLNode *right,*down;
//right指示同一行下一个非零元,down指示同一列下一个非零元
}OLNode,*OLink;
typedef struct
{
OLink *rhead,*chead;
//两个一维数组,分别指示行链表的头指针和列链表的头指针
int mu,nu,tu;
}CrossList;
十字链表的创建
Status CreateMatrix(CrossList *M){
int m,n,t;
int i,j;
ElemType e;
OLNode *q,*p;
if(M){
free(M);
}
printf("输入矩阵的行数、列数和非零元素个数:");
scanf("%d%d%d",m,n,t);
M->mu=m;
M->nu=n;
M->tu=t;
//确定M的行列数和个数
M->rhead=(OLink*)malloc((m+1)*sizeof(OLink));
M->chead=(OLink*)malloc((n+1)*sizeof(OLink));
if(!M->rhead||!M->chead){
return OVERFLOW;
}
for(int i=1;i<=m;i++){
M->rhead[i]=NULL;
}
for(int j=1;j<=n;j++){
M->chead[j]=NULL;
}
//初始化行指针和列指针
for(scanf("%d%d",&i,&j,&e);i!=0;scanf("%d%d",&i,&j,&e)){
p=(OLNode*)malloc(sizeof(OLNode));
if(!p){
return OVERFLOW;
}
p->i=i;
p->j=j;
p->e=e;
if(M->rhead[i]==NULL||M->rhead[i]->j>j){
p->right=M->rhead[i];
M->rhead[i]=p;
}
else{
for(q=M->rhead[i];q->right&&q->right->j<j;q=q->right);
p->right=q->right;
q->right=p;
}
if(M->chead[j]==NULL||M->chead[j]->i>i){
p->down=M->chead[j];
M->chead[j]=p;
}
else{
for(q=M->chead[j];q->down&&q->down->i<i;q=q->down);
p->down=q->down;
q->down=p;
}
}
return OK;
}
实现矩阵相加
int Insert(CrossList M,OLink p)`//把p所指向的节点插入到十字链表中`
{
int i,j,e;
OLink q,q1;
i=p->i;
j=p->j;
e=p->e;
if`(i<1||i>M.mu||j<1||j>M.nu||0==e) cout<<"该元素插入错误!";`
if`(!M.rhead[i]||M.rhead[i]->j>j)`
{
p->right=M.rhead[i];
M.rhead[i]=p;
}
else
{
q=M.rhead[i];
q1=q->right;
if`(!q1) { q->right=p;p->right=NULL;}`
else
{
while`(q1->j<j)`
{
q=q->right;
q1=q1->right;
if`(!q1) break`;
}
if`(q1)`
{
q->right=p;
p->right=q1;
}
else { q->right=p;p->right=NULL;}
}
}
//判断纵行插入的位置
if`(!M.chead[j]||M.chead[j]->i>i)`
{
p->down=M.chead[j];
M.chead[j]=p;
}
else
{
q=M.chead[j];
q1=q->down;
if`(!q1) { q->down=p;p->down=NULL;}`
else
{
while`(q1->i<i)`
{
q=q->down;
q1=q1->down;
if`(!q1) break`;
}
if`(q1)`
{
q->down=p;
p->down=q1;
}
else { q->down=p;p->down=NULL;}
}
}
return 0;
}
int Delete(CrossList M,OLink p)`//把p所指向的节点从十字链表中删除`
{
int i,j;
OLink q,q1;
i=p->i;
j=p->j;
q=M.rhead[i];
q1=q->right;
if`(j==q->j)`
{
M.rhead[i]->right=q->right;
free`(q);`
}
else
{
while`(q1->j!=j)`
{
q=q->right;
q1=q1->right;
}
q->right=q1->right;
free`(q1);`
}
return 0;
}
OLink IsExist(CrossList M,OLink p)`//判断p所指向的节点是否存在于M十字链表中`
{
int i,j;
OLink q;
i=p->i;
j=p->j;
q=M.rhead[i];
while`(q)`
{
if`(j==q->j) return q;`
else q=q->right;
}
return 0;
}
int SMatrix_Add(CrossList &M1,CrossList M2)
{
int k;
OLink p,pr=NULL;
if`(M1.mu!=M2.mu||M1.nu!=M2.nu) return 0;`
for`(k=1;k<=M2.mu;k++)`//按M2逐行进行
{
p=M2.rhead[k];
while`(p)`//每行用指针逐个后移
{
pr=IsExist(M1,p);
if`(!pr) Insert(M1,p);`//如果p所指向的节点在M1中不存在,则直接插入M1
else
{
pr->e+=p->e;
if`(!pr->e) Delete(M1,pr);`
}
Display(M1);
p=p->right;
}
}
return 0;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论