安徽省巢湖学院计算机与信息工程学院
课程设计报告
课程名称 《数据结构》
课题名称用三元组实现稀疏矩阵的转置、相加、相乘
专 业 计算机科学与技术
班 级 11网络工程1班
学 号 AA
姓 名 AAA
联系方式 136XXXXXXXX
指导教师 武彬
20 年 月 日
目 录
1、数据结构课程设计任务书... １
1.1、题目... １
1.2、要求... １
2、总体设计... １
2.1、功能模块设计... １
2.2、所有功能模块的流程图... １
3、详细设计... １
3.1、程序中所采用的数据结构及存储结构的说明... １
3.2、算法的设计思想... ２
3.3、稀疏矩阵各种运算的性质变换... ２
4、调试与测试：... ２
4.1、调试方法与步骤：... ２
4.2、测试结果的分析与讨论：... ３
4.3、测试过程中遇到的主要问题及采取的解决措施：... ３
5、时间复杂度的分析：... ４
6、源程序清单和执行结果... ４
7、C程序设计总结... ８
8、致谢... ８
9、参考文献... ８
1、数据结构课程设计任务书
1.1、题目
【示例】用三元组实现稀疏矩阵的转置、相加、相乘
1.2、要求
【示例】
（1）用creat函数创建三元组；
（2）用print函数打印计算结果；
（3）用add函数实现稀疏矩阵的相加运算；
（4）用mult 函数实现稀疏矩阵的相乘运算；
（5）用 Transm函数实现稀疏矩阵的转置运算；
（6）用menu函数创建一个菜单
2、总体设计
2.1、功能模块设计
根据课程设计题目的功能要求，各个功能模块的组成框图如下：
【示例】
2.2、所有功能模块的流程图
【示例1】略
3、详细设计
模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；
【示例1】
3.1、程序中所采用的数据结构及存储结构的说明
以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。
//-----------稀疏矩阵的三元组顺序存储表示-------------
#define MAXSIZE 100 /*假设非零元个数的最大值为20*/
typedef struct
{
int i,j; /*该非零元的行下标和列下标*/
int v;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int mu,nu,tu; /*矩阵的行数,列数和非零元个数*/
}TSMastrix;
在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。
3.2、算法的设计思想
a) 相加运算
对于两个稀疏矩阵相加，即行与行，列与列相加
b）相乘运算
若设Q=M*N 其中M是m1*n1矩阵，N是m2*n2矩阵，只有当n1=m2时才可以相乘。
乘积矩阵Q中元素
Q（i，j）=∑M（i，k）*N（k，j） 1≤i≤m1，1≤j≤n2
在算法中，不论M（i，k）和 N（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，只需在M.data和N.data中找到相应的各对元素(即M.data中的j值和 N.data中的i值相等的各对元素)相乘即可。
c) 转置运算
对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i），
1≤i≤n，1≤j≤m。完成一个稀疏矩阵的转置分为三步：
（1）将矩阵的行列值相互交换；
（2）将每个三元组中的i和j相互调换；
（3）重排三元组之间的次序便可实现矩阵的转置；
3.3、稀疏矩阵各种运算的性质变换
a)加法运算
两个稀疏矩阵的加和矩阵仍然是稀疏矩阵
b）乘法运算
两个稀疏矩阵的乘积矩阵不是稀疏矩阵
c）转置运算
一个稀疏矩阵的转置矩阵仍然是稀疏矩阵
4、调试与测试：
4.1、调试方法与步骤：
【示例1】简述测试步骤
第一步：测试矩阵加法：
过程（略）
第二步：测试矩阵乘法：
过程（略）
第三步：测试矩阵转置：
过程（略）
4.2、测试结果的分析与讨论：
（测试要写出测试用例及每个用例结果的的截图）
4.3、测试过程中遇到的主要问题及采取的解决措施：
（略）
5、时间复杂度的分析：
a)加法运算
由于两矩阵行列相等，故时间复杂度为O（行*列）
b）乘法运算
设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）
c）转置运算
时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu）
6、源程序清单和执行结果
(清单中应有足够的注释)
【示例1】
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#define MAXSIZE 100 /*假设非零元个数的最大值为20*/
typedef struct
{int i,j; /*该非零元的行下标和列下标*/
int v;
}Triple;
typedef struct
{Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int mu,nu,tu; /*矩阵的行数,列数和非零元个数*/
}juzheng;
void creat(juzheng &T)/*创建三元组*/
{ int k,i,j;
printf("\n 请输入矩阵\n");
do{
printf("\n请输入矩阵的行数，列数，非零元素个数\n");
scanf("%d%d%d",&T.mu,&T.nu,&T.tu); if((T.mu<0||T.mu>20)||(T.nu<0||T.nu>20)||((T.tu/(T.mu*T.nu))>0.05)||((T.tu>T.mu*T.nu)||T.tu>MAXSIZE))
printf("\n 不满足，请重新输入!!\n");
}while((T.mu<0||T.mu>20)||(T.nu<0||T.nu>20)||((T.tu/(T.mu*T.nu))>0.05)||((T.tu>T.mu*T.nu)||T.tu>MAXSIZE));
for(k=1;k<=T.tu;k++)
{
do{
printf("\n请输入非零元素的行数i，列数j，数值v\n");
scanf("%d%d%d",&T.data[k].i,&T.data[k].j,&T.data[k].v); if((T.data[k].i<0||T.data[k].i>T.mu)||(T.data[k].j<0||T.data[k].j>T.nu)||(T.data[k].v==0))
printf("\n 不满足，请重新输入!\n");
} while((T.data[k].i<0||T.data[k].i>T.mu)||(T.data[k].j<0||T.data[k].j>T.nu)||(T.data[k].v==0));
}
return;}
void print(juzheng A) /*打印计算结果*/
{int q,n,k,a=0;
printf("\n\n矩阵为：\n");
for(n=1;n<=A.mu;n++)
{
for(k=1;k<=A.nu;k++)
{
for(q=1;q<=A.tu;q++)
{if(A.data[q].i==n&&A.data[q].j==k){printf("\t%-3d",A.data[q].v);break;}
}
if(q>A.tu)printf("\t%-3d",a);
}
printf("\n");
}
}
void add(juzheng A,juzheng B)/*加法运算*/
{ int n,k;
if(A.mu!=B.mu||A.nu!=B.nu)
{ printf("\n 不满足相加条件");
printf("\n 两矩阵行列各自相等才可加");
}
else {for(n=1;n<=A.tu;n++)
for(k=1;k<=B.tu;k++)/*将矩阵T的非零元接至M中*/
{if(A.data[n].i==B.data[k].i&&A.data[n].j==B.data[k].j)
{A.data[n].v+=B.data[k].v;
B.data[k].v=0;}
}
for(k=1;k<=B.tu;k++)
if(B.data[k].v!=0)
{A.data[A.tu+1].i=B.data[k].i;
A.data[A.tu+1].j=B.data[k].j;
A.data[A.tu+1].v=B.data[k].v;
A.tu++;
}
print(A);
}
}
void mult(juzheng A,juzheng B)/*乘法运算*/
{int z,n1,k1,n2,k2,s,sum,count=0;
juzheng Z;
int b1[100][100],b2[100][100],b3[100][100];
if(A.nu!=B.mu)printf("矩阵列数与行数不等，不能进行乘法运算");
else{
Z.mu=A.mu;
Z.nu=B.nu;
for(n1=1;n1<=A.mu;n1++)/*初始化为零*/
for(k1=1;k1<=A.nu;k1++){b1[n1][k1]=0;}
for(n1=1;n1<=A.mu;n1++)
for(k1=1;k1<=A.nu;k1++){b2[n1][k1]=0;}
for(n1=1;n1<=A.tu;n1++)/*装载三元组数据*/
{b1[A.data[n1].i][A.data[n1].j]=A.data[n1].v;}
for(n1=1;n1<=B.tu;n1++)
{b2[B.data[n1].i][B.data[n1].j]=B.data[n1].v;}
for(n1=1;n1<=Z.mu;n1++)
{ for(k2=1;k2<=Z.nu;k2++)
{sum=0;
for(k1=1;k1<=Z.nu;k1++)
{sum+=b1[n1][k1]*b2[k1][k2];
}
if(sum!=0)
{count++;
Z.data[count].i=n1;
Z.data[count].j=k2;
Z.data[count].v=sum;
Z.tu=count; }
}
}
print(Z);
}
}
void Transm(juzheng A)/*转置运算*/
{ juzheng B;
int p,q,col;
B.mu=A.nu;
B.nu=A.mu;
B.tu=A.tu;
if(B.tu)
{
q=1;
for(col=1;col<=A.nu;col++)
for(p=1;p<=A.tu;p++)
if(A.data[p].j==col)
{
B.data[q].i=A.data[p].j;
B.data[q].j=A.data[p].i;
B.data[q].v=A.data[p].v;
q++; }
}
print(B);
}
char menu()//菜单
{
char n;
printf("\n ");
printf("稀疏矩阵运算器\n");
printf("\n");
printf("实现运算\n");
printf("\n");
printf("1:矩阵相加\n");
printf("2:矩阵相乘\n");
printf("3:矩阵转置\n");
printf("4:退出\n");
printf("\n");
printf("\n你要选择的操作是: ");
n=getchar();
return n;
}
main()
{ juzheng A,B;
for(;;)
switch(menu())
{case '1':creat(A);
print(A);
creat(B);
print(B);
printf("\n");
add(A,B);
getch();
break;
case '2':creat(A);
print(A);
creat(B);
print(B);
printf("\n");
mult(A,B);
getch();
break;
case '3': creat(A);
print(A);
printf("\n");
Transm(A);
getch();
break;
case '4': exit(0);
}
system("PAUSE");
return EXIT_SUCCESS;
}
7、C程序设计总结
【示例1】本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。
在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。
8、致谢
【示例1】能够完成这次课程设计必须感谢数据结构课程老师×××、×××同学（她帮我修改了几处重要错误，同时启发我完善了该程序的功能）。
9、参考文献
【示例1】
[1] 贾宗璞、许合利，C语言程序设计，江苏：中国矿业大学出版社，2007.6
[2] 谭浩强，C程序设计（第二版），北京：清华大学出版社，2001.1
[3] http://www.baidu.com