/* bo5-4.c 稀疏矩阵的十字链表存储(存储结构由c5-4.h定义)的基本操作(9个) */
Status InitSMatrix(CrossList *M) /* 加 */
{ /* 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) */
(*M).rhead=(*M).chead=NULL;
(*M).mu=(*M).nu=(*M).tu=0;
return OK;
}
Status DestroySMatrix(CrossList *M)
{ /* 初始条件: 稀疏矩阵M存在。操作结果: 销毁稀疏矩阵M */
int i;
OLNode *p,*q;
for(i=1;i<=(*M).mu;i++) /* 按行释放结点 */
{
p=*((*M).rhead+i);
while(p)
{
q=p;
p=p->right;
free(q);
}
}
free((*M).rhead);
free((*M).chead);
(*M).rhead=(*M).chead=NULL;
(*M).mu=(*M).nu=(*M).tu=0;
return OK;
}
Status CreateSMatrix(CrossList *M)
{ /* 创建稀疏矩阵M,采用十字链表存储表示。算法5.4 */
int i,j,k,m,n,t;
ElemType e;
OLNode *p,*q;
if((*M).rhead)
DestroySMatrix(M);
printf("请输入稀疏矩阵的行数 列数 非零元个数: ");
scanf("%d%d%d",&m,&n,&t);
(*M).mu=m;
(*M).nu=n;
(*M).tu=t;
(*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));
if(!(*M).rhead)
exit(OVERFLOW);
(*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));
if(!(*M).chead)
exit(OVERFLOW);
for(k=1;k<=m;k++) /* 初始化行头指针向量;各行链表为空链表 */
(*M).rhead[k]=NULL;
for(k=1;k<=n;k++) /* 初始化列头指针向量;各列链表为空链表 */
(*M).chead[k]=NULL;
printf("请按任意次序输入%d个非零元的行 列 元素值:\n",(*M).tu);
for(k=0;k<t;k++)
{
scanf("%d%d%d",&i,&j,&e);
p=(OLNode*)malloc(sizeof(OLNode));
if(!p)
exit(OVERFLOW);
p->i=i; /* 生成结点 */
p->j=j;
p->e=e;
if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j) /* p插在该行的第一个结点处 */
{
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插在该列的第一个结点处 */
{
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;
}
Status PrintSMatrix(CrossList M)
{ /* 初始条件: 稀疏矩阵M存在。操作结果: 按行或按列输出稀疏矩阵M */
int i,j;
OLink p;
printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);
printf("请输入选择(1.按行输出 2.按列输出): ");
scanf("%d",&i);
switch(i)
{
case 1: for(j=1;j<=M.mu;j++)
{
p=M.rhead[j];
while(p)
{
printf("%d行%d列值为%d\n",p->i,p->j,p->e);
p=p->right;
}
}
break;
case 2: for(j=1;j<=M.nu;j++)
{
p=M.chead[j];
while(p)
{
printf("%d行%d列值为%d\n",p->i,p->j,p->e);
p=p->down;
}
}
}
return OK;
}
Status CopySMatrix(CrossList M,CrossList *T)
{ /* 初始条件: 稀疏矩阵M存在。操作结果: 由稀疏矩阵M复制得到T */
int i;
OLink p,q,q1,q2;
if((*T).rhead)
DestroySMatrix(T);
(*T).mu=M.mu;
(*T).nu=M.nu;
(*T).tu=M.tu;
(*T).rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink));
if(!(*T).rhead)
exit(OVERFLOW);
(*T).chead=(OLink*)malloc((M.nu+1)*sizeof(OLink));
if(!(*T).chead)
exit(OVERFLOW);
for(i=1;i<=M.mu;i++) /* 初始化矩阵T的行头指针向量;各行链表为空链表 */
(*T).rhead[i]=NULL;
for(i=1;i<=M.nu;i++) /* 初始化矩阵T的列头指针向量;各列链表为空链表 */
(*T).chead[i]=NULL;
for(i=1;i<=M.mu;i++) /* 按行复制 */
{
p=M.rhead[i];
while(p) /* 没到行尾 */
{
q=(OLNode*)malloc(sizeof(OLNode)); /* 生成结点 */
if(!q)
exit(OVERFLOW);
q->i=p->i; /* 给结点赋值 */
q->j=p->j;
q->e=p->e;
if(!(*T).rhead[i]) /* 插在行表头 */
(*T).rhead[i]=q1=q;
else /* 插在行表尾 */
q1=q1->right=q;
if(!(*T).chead[q->j]) /* 插在列表头 */
{
(*T).chead[q->j]=q;
q->down=NULL;
}
else /* 插在列表尾 */
{
q2=(*T).chead[q->j];
while(q2->down)
q2=q2->down;
q2->down=q;
q->down=NULL;
}
p=p->right;
}
q->right=NULL;
}
return OK;
}
Status AddSMatrix(CrossList M,CrossList N,CrossList *Q)
{ /* 初始条件: 稀疏矩阵M与N的行数和列数对应相等。 */
/* 操作结果: 求稀疏矩阵的和Q=M+N */
int i,k;
OLink p,pq,pm,pn;
OLink *col;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("两个矩阵不是同类型的,不能相加\n");
exit(OVERFLOW);
}
(*Q).mu=M.mu; /* 初始化Q矩阵 */
(*Q).nu=M.nu;
(*Q).tu=0; /* 元素个数的初值 */
(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));
if(!(*Q).rhead)
exit(OVERFLOW);
(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));
if(!(*Q).chead)
exit(OVERFLOW);
for(k=1;k<=(*Q).mu;k++) /* 初始化Q的行头指针向量;各行链表为空链表 */
(*Q).rhead[k]=NULL;
for(k=1;k<=(*Q).nu;k++) /* 初始化Q的列头指针向量;各列链表为空链表 */
(*Q).chead[k]=NULL;
col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink)); /* 生成指向列的最后结点的数组 */
if(!col)
exit(OVERFLOW);
for(k=1;k<=(*Q).nu;k++) /* 赋初值 */
col[k]=NULL;
for(i=1;i<=M.mu;i++) /* 按行的顺序相加 */
{
pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */
pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */
while(pm&&pn) /* pm和pn均不空 */
{
if(pm->j<pn->j) /* 矩阵M当前结点的列小于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
(*Q).tu++; /* 非零元素数加1 */
p->i=i; /* 给结点赋值 */
p->j=pm->j;
p->e=pm->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
}
else if(pm->j>pn->j) /* 矩阵M当前结点的列大于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
(*Q).tu++; /* 非零元素数加1 */
p->i=i; /* 给结点赋值 */
p->j=pn->j;
p->e=pn->e;
p->right=NULL;
pn=pn->right; /* pn指针向右移 */
}
else if(pm->e+pn->e) /* 矩阵M、N当前结点的列相等且两元素之和不为0 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
(*Q).tu++; /* 非零元素数加1 */
p->i=i; /* 给结点赋值 */
p->j=pn->j;
p->e=pm->e+pn->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
pn=pn->right; /* pn指针向右移 */
}
else /* 矩阵M、N当前结点的列相等且两元素之和为0 */
{
pm=pm->right; /* pm指针向右移 */
pn=pn->right; /* pn指针向右移 */
continue;
}
if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
(*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */
}
if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
(*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->]所指结点之后 */
{
col[p->j]->down=p; /* 完成列插入 */
col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
}
}
while(pm) /* 将矩阵M该行的剩余元素插入矩阵Q */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
(*Q).tu++; /* 非零元素
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
数据结构——殷人昆版习题答案 (285个子文件)
BO5-4.c 17KB
BO7-1.C 16KB
BO7-1.C 16KB
Bo7-4.c 12KB
Bo7-4.c 12KB
Bo7-2.c 11KB
Bo7-2.c 11KB
Bo7-3.c 11KB
Bo7-3.c 11KB
BO4-3.c 10KB
BO6-1.c 9KB
bo6-2.c 9KB
algo2-6.c 9KB
Bo6-5.c 9KB
Bo6-4.c 8KB
bo6-6.c 8KB
algo8-1.c 7KB
algo8-1.c 7KB
BO2-6.c 6KB
BO9-3.c 6KB
BO9-3.c 6KB
ALGO4-4.c 6KB
BO5-3.c 6KB
algo4-3.c 6KB
Bo5-6.c 6KB
algo11-2.C 5KB
algo11-2.C 5KB
Bo4-2.c 5KB
algo8-2.c 5KB
algo8-2.c 5KB
main6-6.c 5KB
BO2-8.C 5KB
BO2-5.c 5KB
alg10-11.c 5KB
alg10-11.c 5KB
bo2-7.c 5KB
BO5-2.c 5KB
Main6-2.c 5KB
BO2-4.c 4KB
BO2-2.C 4KB
Bo9-5.c 4KB
Bo9-5.c 4KB
algo12-1.c 4KB
algo12-1.c 4KB
bo2-1.c 4KB
Bo2-9.c 4KB
BO4-1.C 4KB
BO2-32.c 4KB
BO9-4.c 4KB
BO9-4.c 4KB
BO2-31.c 4KB
bo9-2.c 4KB
bo9-2.c 4KB
ALGO3-5.c 4KB
ALGO3-12.c 4KB
Bo9-7.c 4KB
Bo9-7.c 4KB
Algo3-7.c 3KB
Bo9-6.c 3KB
Bo9-6.c 3KB
algo8-3.c 3KB
algo8-3.c 3KB
Algo7-5.c 3KB
Algo7-5.c 3KB
ALGO3-11.c 3KB
MAIN2-6.c 3KB
BO5-5.c 3KB
algo11-1.c 3KB
algo11-1.c 3KB
ALGO3-6.c 3KB
ALGO4-5.c 3KB
MAIN2-1.c 3KB
Algo10-2.c 3KB
Algo10-2.c 3KB
algo6-2.c 3KB
Algo9-3.c 3KB
Algo9-3.c 3KB
Algo7-7.c 3KB
Algo7-7.c 3KB
BO9-1.c 3KB
BO9-1.c 3KB
Algo7-1.c 2KB
Algo7-1.c 2KB
BO6-3.c 2KB
ALGO6-1.c 2KB
MAIN2-32.C 2KB
BO5-1.C 2KB
ALGO3-9.c 2KB
bo10-1.c 2KB
bo10-1.c 2KB
Algo7-6.c 2KB
Algo7-6.c 2KB
Main4-3.c 2KB
Main7-2.c 2KB
Main7-2.c 2KB
Algo2-5.c 2KB
bo11-1.c 2KB
bo11-1.c 2KB
MAIN2-2.c 2KB
BO3-2.c 2KB
共 285 条
- 1
- 2
- 3
bloodyRomantic
- 粉丝: 5
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
前往页