数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_基于三元组表的储存结构实现稀疏矩阵操作_课程设计_实验报告
设计题目：基于三元组表的储存结构实现稀疏矩阵操作
1
课题名称基于三元组表的储存结构实现稀疏矩阵的基本操作院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的：其目的是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相减等基本操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。2、课题设计意义：让我们更加熟悉算法，提高我们的动手能力，熟练的掌握算法的运行与程序的实际。领会程序设计的意义。指导教师：年月日
目录一、实验目的及意义....................................................................................................11.1实验目的..........................................................................................................11.11了解多维数组存储方式和存储特点。.................................................11.12熟悉稀疏矩阵的存储方式。.................................................................11.13用三元组法实现稀疏矩阵的转置、相加、相减的操作。.................11.2实验意义.........................................................................................................1二、需求分析................................................................................................................12.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值..........................12.2构造函数进行稀疏矩阵的转置并输出结果.................................................12.3构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵.............22.4退出系统..........................................................................................................2三、项目设计................................................................................................................2
3.1设计思路及方案.............................................................................................23.11设计思路........................................................................................................23.2模块图..............................................................................................................43.3流程图.............................................................................................................5四、系统实现................................................................................................................64.1主调函数..........................................................................................................64.2三元组表的建立..............................................................................................64.3矩阵的建立......................................................................................................74.4矩阵相加减及转置........................................................................................10五、系统调试..............................................................................................................155.1系统输入........................................................................................................155.2矩阵转置........................................................................................................165.4矩阵相减........................................................................................................17六、实验总结..............................................................................................................18
七、附录......................................................................................................................187.1参考文献.........................................................................................................18
1
一、实验目的及意义1.1实验目的1.11了解多维数组存储方式和存储特点。1.12熟悉稀疏矩阵的存储方式。1.13用三元组法实现稀疏矩阵的转置、相加、相减的操作。
1.2实验意义空非零元素分布没有规律，在存储非零元素的同时还要存储辅助信息，才能确定非零元素的位置，利用稀疏矩阵大大节省存储空间。二、需求分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和
十字链表结构下。在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化时，只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时，以矩阵的完整形式输出。2.2构造函数进行稀疏矩阵的转置并输出结果本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。
2
2.3构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵本模块要求设计相加、减和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，定义相应的矩阵类型用于存放两个矩阵操作后的结果矩阵，这个结果矩阵的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点，需要灵活运用数组及指针的特点。2.4退出系统本模块要求设置选项能随时结束程序的运行，本程序中采用do-while循环。程序在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。
三、项目设计3.1设计思路及方案3.11设计思路1）主界面的设计定义两个矩阵a=100b=104
023020003003定义两个数组A和B，用于存储矩阵a和矩阵b的值；定义一个数组C，用于存放数组A和数组B相加后的结果。2）实现方式稀疏矩阵的存储比较浪费空间，所以我们可以定义两个数组A、B，采用压缩存储的方式来对上面的两个矩阵进行存储。具体的方法是，将非零元素的值和它所在的行号、列号作为一个结点存放在一起，这就唯一确定一个非零元
3
素的三元组（i、j、v）。将表示稀疏矩阵的非零元素的三元组按行优先的顺序排列，则得到一个其结点均为三元组的线性表。即：以一维数组顺序存放非零元素的行号、列号和数值，行号-1作为结束标志。例如，上面的矩阵a，利用数组A存储后内容为：A[0]=0，A[1]=2,A[2]=3,A[3]=1,A[4]=6,A[5]=5,A[6]=3,A[7]=4,A[8]=7,A[9]=5,A[10]=1,A[11]=9,A[12]=-1同理，用数组B存储矩阵b的值。稀疏矩阵的加法实现：3、主要算法结构分析：1)voidCreateMatrix(int
A[m][n],intB[50]),这是一个将稀疏矩阵转存的函数，类似于顺序存储三元组表。在这个方法中，只要用一个二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入到一维数组B中对应的元素。在定义函数的过程中，我们需要定义一个for循环，以完成行和列的转换及存储。在函数的末尾我们定义一个B[K]=-1，用于结束非零元素的存储。2)voidMatrixAdd(intA[max],intB[max],intC[max]),这个函数用于实现数组A和数组B的相加，并将其相加的结果存入数组C。这个函数讨论了数组在相加的过程中的几种情况：
a、A数组和B数组的行相等且列相等，两者直接相加后存入数组C中。
4
3.2模块图建立主调
函数建立三元组表建立矩阵函数矩阵相加减矩阵相减输出稀疏矩阵的基本操作
5
3.3流程图开用户选
择加法运算转置运算显示结果等待用户输入
结束运算继续计算
输入输入
6
四、系统实现4.1主调函数#include#definesmax16typedefintdatatype;typedefstruct{inti,j;datatypev;
}node;typedefstruct(){intm,n,t;nodedata[smax];}spmatrix;4.2三元组表的建立voidprint(spmatrixa){
intk;for(k=0;kt;k++)printf("%d\t%d\t%d\n",a->data[k].i,a->data[k].j,a->data[k].v);}voidprintjuzhen(spmatrixa){intk,p,l;intc[5][5]={{0},{0},{0},{0},{0}};
7
for(k=0;kt;k++)c[a->data[k].i][a->data[k].j]=a->data[k].v;for(p=0;pm;p++){for(l=0;ln;l++)printf("%d\t",c[p][l]);printf("\n");}}4.3矩阵的建立voidprintjuzhen(spmatrixa)
{intk,p,l;intc[5][5]={{0},{0},{0},{0},{0}};for(k=0;kt;k++)c[a->data[k].i][a->data[k].j]=a->data[k].v;for(p=0;pm;p++){for(l=0;ln;l++)printf("%d\t",c[p][l]);printf("\n");}}spmatrixxiangjia(spmatrixa,spmatrixb)
{spmatrixc;intpa=0,pb=0,pc=0,sum=0;c=(spmatrix)malloc(sizeof(spmatrix));if((a->m==b->m)&&(a->n==b->n)){c->m=a->m;c->n=a->n;while(pat&&pbt){if(a->data[pa].i==b->data[pb].i){
8
if(a->data[pa].j==b->data[pb].j){sum=a->data[pa].v+b->data[pb].v;if(sum){c->data[pc].v=sum;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;}pa++;pb++;
}else{if(a->data[pa].jdata[pb].j){if(a->data[pa].v){c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}
}elseif(b->data[pb].v){c->data[pc].v=b->data[pb].v;c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;pc++;pb++;}}}else
9
{if(a->data[pa].idata[pb].i){if(a->data[pa].v){c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}}else
if(b->data[pb].v){c->data[pc].v=b->data[pb].v;c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;pc++;pb++;}}}}elsereturn(0);
while(pat){c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}while(pbt){c->data[pc].v=b->data[pb].v;c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;
10
pc++;pb++;}c->t=pc;return(c);}4.4矩阵相加减及转置spmatrixxiangjian(spmatrixa,spmatrixb){spmatrixc;
intpa=0,pb=0,pc=0,sum=0;c=(spmatrix)malloc(sizeof(spmatrix));if((a->m==b->m)&&(a->n==b->n)){c->m=a->m;c->n=a->n;while(pat&&pbt){if(a->data[pa].i==b->data[pb].i){if(a->data[pa].j==b->data[pb].j){
sum=a->data[pa].v-b->data[pb].v;if(sum){c->data[pc].v=sum;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;}pa++;pb++;}else
11
{if(a->data[pa].jdata[pb].j){if(a->data[pa].v){c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}}else
if(b->data[pb].v){c->data[pc].v=-(b->data[pb].v);c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;pc++;pb++;}}}else{if(a->data[pa].idata[pb].i)
{if(a->data[pa].v){c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}}elseif(b->data[pb].v){
12
c->data[pc].v=-(b->data[pb].v);c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;pc++;pb++;}}}}elsereturn(0);while(pat){
c->data[pc].v=a->data[pa].v;c->data[pc].i=a->data[pa].i;c->data[pc].j=a->data[pa].j;pc++;pa++;}while(pbt){c->data[pc].v=-(b->data[pb].v);c->data[pc].i=b->data[pb].i;c->data[pc].j=b->data[pb].j;pc++;pb++;}
c->t=pc;return(c);}spmatrixtransmat(spmatrixa){intpa,pb,col;spmatrixb;b=(spmatrix)malloc(sizeof(spmatrix));b->m=a->n;b->n=a->m;b->t=a->t;if(b->t>0)
13
{pb=0;for(col=0;coln;col++)for(pa=0;pat;pa++)if(a->data[pa].j==col){b->data[pb].i=a->data[pa].j;b->data[pb].j=a->data[pa].i;b->data[pb].v=a->data[pa].v;pb++;}}
return(b);}voidmain(){spmatrixa,b,c;inti,j;while(i){printf("\n\t\t\t\thello!kugou!!\n\n");printf("欢迎进入......\n\t\t\t基于三元组表实现稀疏矩阵的基本操作\n\n");printf("\t\t\t\t矩阵转置请按1\n\t\t\t\t矩阵相加请按2\n\t\t\t\t矩阵相减请按3\n");
scanf("%d",&j);switch(j){case1:{a=(spmatrix)malloc(sizeof(spmatrix));c=(spmatrix)malloc(sizeof(spmatrix));creat(a);printf("你输入的三元组表的信息如下\n");print(a);printf("三元组表对应的矩阵如下\n");printjuzhen(a);printf("转置后的三元组表的信息如下:\n");
14
c=transmat(a);print(c);printf("转置后的三元组表对应的矩阵如下\n");printjuzhen(c);break;}case2:{a=(spmatrix)malloc(sizeof(spmatrix));b=(spmatrix)malloc(sizeof(spmatrix));c=(spmatrix)malloc(sizeof(spmatrix));creat(a);creat(b);
c=xiangjia(a,b);printf("相加后的三元组表为:\n");print(c);printf("相加后的三元组表对应的矩阵为:\n");printjuzhen(c);break;}case3:{a=(spmatrix)malloc(sizeof(spmatrix));b=(spmatrix)malloc(sizeof(spmatrix));c=(spmatrix)malloc(sizeof(spmatrix));creat(a);
creat(b);c=xiangjian(a,b);printf("相减后的三元组表为:\n");print(c);printf("相减后的三元组表对应的矩阵为:\n");printjuzhen(c);break;}}printf("\t\t\t\t继续请按1\n\t\t\t\t退出请按0\n");scanf("%d",&i);}
15
}五、系统调试5.1系统输入
图1.输入
16
5.2矩阵转置
图2.转置5.3矩阵相加
17
图3.相加5.4矩阵相减
图4.相减
18
六、实验总结在存储稀疏矩阵时，为了节省储存单元，所以很自然的压缩储存方法是指储存非零元素。但由于非零元素的分布一般是没有规律的，因此，在储存非零元素的同时，还必须储存适当的辅助信息，所以就要利用三元组表进行储存,所我们就可以节约空间，从这次课程设计让我更加熟悉了稀疏矩阵，对稀疏矩阵的储存有了更深的了解，也加深了我对数据结构这么课的兴趣。自己感觉很有收获。七、附录
7.1参考文献[1]黄刘生.数据结构.高等教育出版社.1994.12[2]许卓群等.数据结构.高等教育出版社，1987
|
|
