文章目录
题目:数组及其应用
1.设计并实现稀疏矩阵运算器。
要求
(1) 以三元组顺序表存储稀疏矩阵,实现两个矩阵的相加、相减与转置。
(2) 根据屏幕菜单的选择,可以进行稀疏矩阵的相加、相减与转置,且能进行输入数据出错的处理,例如参与相加运算的两个矩阵行数和列数不同,等等。
(3) 矩阵的输入、输出均为矩阵形式。
本程序中用到的所有抽象数据类型的定义
typedef struct{//三元组
int i,j;//行列
int e;//矩阵元素
}trupe;
typedef struct{//稀疏矩阵
trupe data[max+1];
int nu,mu,tu;
}xishu;
算法思路
1.主要包括相加减,转置两个算法
相加减算法
A,B相加,对于每一行,如果A和B中都有在此行的元素且A,B中还有非零元,那么比较他们的列;如果列相等,令ce等于A,B此行此列的和(差),如果和(差)不为零,就把行,列,ce放入C,如果列A大于B,那么B点放入C,B列大于A同理;比完之后如果A或B有剩余也直接加入C。
int pa,pb,pc;pa=pb=pc=0;int ce;
for(int row=0;row<A.mu;row++){//对于每一行
while(A.data[pa].i==row&&B.data[pb].i==row&&pa<=A.tu&&pb<=A.tu){//如果A和B中都有在此行的元素且A,B中还有非零元
if(A.data[pa].j==B.data[pb].j){//如果列相等,令ce等于A,B此行此列的和(差)
if(x==1)
ce=A.data[pa].e+B.data[pb].e;
else
ce=A.data[pa].e-B.data[pb].e;
if(ce){//如果和(差)不为零,就把行,列,ce放入C
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++,pb++,pc++;
}
}
else if(A.data[pa].j>B.data[pb].j){//如果列A大于B,那么B点放入C
C.data[pc].i=row;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++,pc++;
}
else{//B列大于A同理
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++,pc++;
}
}
//比完之后如果A或B有剩余也直接加入C
while(A.data[pa].i==row&&pa<=A.tu){
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++,pc++;
}
while(B.data[pb].i==row&&pb<=B.tu){
C.data[pc].i=row;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++,pc++;
}
}
转置算法
循环遍历一遍表中的列,找到A中列等于1的放入T(交换行列),对于行从0到行数nu都执行这个操作
int p=0;T.mu=A.nu,T.nu=A.mu,T.tu=A.tu;
for(int i=0;i<A.nu;i++)//对于行从0到行数nu都执行这个操作
for(int j=0;j<A.tu;j++){//循环遍历一遍表中的列,找到A中列等于1的放入T(交换行列)
if(A.data[j].j==i){
T.data[p].i=A.data[j].j;
T.data[p].j=A.data[j].i;
T.data[p].e=A.data[j].e;
p++;
}
}
详细代码
#include<stdio.h>
#define max 10000
typedef struct{
int i,j;
int e;
}trupe;
typedef struct{
trupe data[max+1];
int nu,mu,tu;
}xishu;
int print(xishu A);
xishu turn(){
int n,m;
printf("请输入行数");
scanf("%d",&m);
printf("请输入列数");
scanf("%d",&n);
printf("请输入%d行%d列矩阵\n",m,n);
xishu A;A.mu=m,A.nu=n,A.tu=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int a;scanf("%d",&a);
if(a != 0){
A.data[A.tu].i=i;
A.data[A.tu].j=j;
A.data[A.tu].e=a;
A.tu++;
}
}
}
printf("\n");
print(A);
return A;
}
int print(xishu A){
int pa=0;
for(int i=0;i<A.mu;i++){
for(int j=0;j<A.nu;j++){
if(i==A.data[pa].i&&j==A.data[pa].j){
printf("%d ",A.data[pa].e);
pa++;
}
else
printf("0 ");
}
printf("\n");
}
}
void zhuanzhi(xishu A,xishu &T){
int p=0;T.mu=A.nu,T.nu=A.mu,T.tu=A.tu;
for(int i=0;i<A.nu;i++)
for(int j=0;j<A.tu;j++){
if(A.data[j].j==i){
T.data[p].i=A.data[j].j;
T.data[p].j=A.data[j].i;
T.data[p].e=A.data[j].e;
p++;
}
}
}
int fun(xishu A,xishu B,xishu &C,int x)
{
C.mu=A.mu,C.nu=A.nu,C.tu=0;
if(A.mu!=B.mu||A.nu!=B.nu)
return 0;
int pa,pb,pc;pa=pb=pc=0;int ce;
for(int row=0;row<A.mu;row++){
while(A.data[pa].i==row&&B.data[pb].i==row&&pa<=A.tu&&pb<=A.tu){
if(A.data[pa].j==B.data[pb].j){
if(x==1)
ce=A.data[pa].e+B.data[pb].e;
else
ce=A.data[pa].e-B.data[pb].e;
if(ce){
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++,pb++,pc++;
}
}
else if(A.data[pa].j>B.data[pb].j){
C.data[pc].i=row;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++,pc++;
}
else{
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++,pc++;
}
}
while(A.data[pa].i==row&&pa<=A.tu){
C.data[pc].i=row;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++,pc++;
}
while(B.data[pb].i==row&&pb<=B.tu){
C.data[pc].i=row;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++,pc++;
}
}
return 1;
}
void menu(){
printf("\t*********\t\n");
printf("\t1.输入矩阵A\n");
printf("\t2.输入矩阵B\n");
printf("\t3.转置矩阵A\n");
printf("\t4.转置矩阵B\n");
printf("\t5.矩阵相加\n");
printf("\t6.矩阵相减\n");
printf("\t7.退出\n");
}
int choice(){
int x;
xishu A,B,C,T;
while(1){
menu();
scanf("%d",&x);
switch(x){
case 1:
A=turn();
break;
case 2:
B=turn();
break;
case 3:
zhuanzhi(A,*&T);
A=T;print(T);
break;
case 4:
zhuanzhi(B,*&T);
B=T;print(T);
break;
case 5:
if(fun(A,B,C,1))
print(A),print(B),print(C);
else
printf("两矩阵的行列数不一致\n");
break;
case 6:
if(fun(A,B,C,0))
print(A),print(B),print(C);
else
printf("两矩阵的行列数不一致\n");
break;
case 7:
return 0;
default:
printf("请输入1~7");
break;
}
}
}
int main()
{
choice();
return 0;
}