稀疏矩阵的存储和运算
稀疏矩阵的存储和运算
一 目的
根据所学知识,编写指定题目的C语言程序,并规范地完成课程设计报告。通过课程设计,加深对《程序设计语言》和《软件技术基础》课程所学知识的理解,熟练掌握和巩固C语言的基本知识和语法规范,包括:数据类型(整形、实型、字符型、指针、数组、结构等);运算类型(算术运算、逻辑运算、自增自减运算、赋值运算等);程序结构(顺序结构、判断选择结构、循环结构);库函数应用等;复杂任务功能分解方法(自顶向下逐步求精、模块化设计、信息隐藏等),熟练掌握和巩固三种基本的数据结构(线性结构、树形结构、图形结构)的逻辑结构、存储结构以及相关运算和应用。
学会编制结构清晰、风格良好、数据结构适当的C语言程序,从而具备利用计算机编程分析解决综合性实际问题的初步能力。
二 需求分析
为了节约存储空间,稀疏矩阵通常采用压缩存储的方式。将给定的稀疏矩阵进行压缩存储,并实现矩阵的转置等运算。
将稀疏矩阵采用三元组顺序表进行存储,实现下列操作:
(1)任意给定一个稀疏矩阵M,压缩存储M;
(2)求M的转置矩阵N;
(3)在三元组存储矩阵中查找值为x的结点是否存在,如果存在,输出它的位置,否则输出“不存在”的提示信息;
(4)打印矩阵的形状;
(5)采用模块化设计,有菜单功能。
三 概要设计
1、本程序包含两个模块
(1)主函数模块
main()
{
定义及初始化;
调用创建、转置、查找函数 ,实现不同的逻辑功能;
调用打印函数,输出原矩阵以及转置矩阵;
}
(2)自定义函数模块:
创建函数Create();
转置函数Transmat();
查找函数searchhval(x);
打印函数Print_Pmatrix(X)
2、子程序类型定义:
Create();
操作结果:完成稀疏矩阵的输入
Transmat();
操作结果:完成稀疏矩阵的转置
searchhval(x);
操作结果:完成结点x的查找
Print_Pmatrix(X);
操作结果:完成稀疏矩阵
四 详细设计
1、主函数之前
#include
#define MaxSize 100//非零元个数的最大值
typedef int Elemtype;
// 稀疏矩阵的三元组顺序表存储表示
typedef struct
{
int i,j;// 行下标,列下标
Elemtype v;// 非零元素值
}Pnode;
typedef struct
{
int rows,cols,terms;// 矩阵的行数、列数和非零元个数
Pnode data[MaxSize+1];// 非零元三元组表,data[0]未用
}PMatrix;
PMatrix M;
PMatrix N;
PMatrix X;
void menu()
{
printf("*********************************&&&&&&&&&*******************************\n");
printf("* 本代码实现稀疏矩阵的如下几个基本功能并选择对应的功能选项进行相应操作: *\n");
printf("* 1.创建稀疏矩阵,压缩存储 *\n");
printf("* 2.稀疏矩阵的转置 *\n");
printf("* 3.在原三元组存储矩阵中查找值为x的结点是否存在 *\n");
printf("* 4.打印矩阵的形状 *\n");
printf("* 0.退出程序 *\n");
printf("********************************&&&&&&&&&&*******************************\n");
}
2、各函数详细设计
1、主函数
void main()
{
int choice=0,x;
menu();
printf("本代码实现顺序表的几个基本功能并选择对应的功能选项进行相应操作:\n");
fflush(stdin);
scanf("%d",&choice); while(1) { switch(choice) { { case 1: printf("创建矩阵M: ");
Create();//调用创建函数
break;
}
case 2:
{
printf("矩阵N(M的转置):\n");
Transmat();//调用转置函数
break;
}
case 3:
{
int x;
printf("请输入x=");
scanf("%d",&x);//输入要查找的结点
searchhval(x);//调用查找函数
break;
}
case 4:
{ printf("输入你需要打印的矩阵(输入0或者1):\n");
scanf("%d",&x);
if(x==0) //打印矩阵M
{
X=M;
printf("打印矩阵:\n");
Print_Pmatrix(X);//调用打印函数
}
else//打印矩阵N
{
X=N;
printf("打印矩阵:\n");
Print_Pmatrix(X);//调用打印函数
}
break;
}
case 0:
{ break; } break; } if(choice==0)//退出程序 break;
menu();
printf("本代码实现顺序表的几个基本功能,请选择对应的功能选项进行相应操作:\n");
fflush(stdin);
}
2、创建函数
Create()
{
int i; fflush(stdin); printf("请输入矩阵的行数,列数,非零元素个数(用逗号隔开):\n"); scanf("%d",&choice); }
scanf("%d,%d,%d",&M.rows,&M.cols,&M.terms);
printf("请按行序顺序输入非零元素所在的行号,列号和非零元数值(用逗号隔开):\n");
for(i=1; i
scanf("%d,%d,%d",&M.data[i].i,&M.data[i].j,&M.data[i].v);//输入M中的非零元素
}
3、转置函数
Transmat()
{
int i,j,col;//i,j分别是M.data和N.data中结点序号,col是M的列号,即N的行号
N.rows=M.cols;//将矩阵M的列数赋值给矩阵N的行数
N.cols=M.rows;//将矩阵M的行数赋值给矩阵N的列数 N.terms=M.terms;//将矩阵M的非零元个数赋值给矩阵N的非零元个数 if(N.terms>0) { i=1; for(col=1;col
{ N.data[i].i=M.data[j].j;
N.data[i].j=M.data[j].i;//行列号交换
N.data[i].v=M.data[j].v;//非零元素值交换
++i;
}
}
}
for(i=1;i
printf("%d %d %d\n",N.data[i].i,N.data[i].j,N.data[i].v);
}
4、查找函数
int searchhval(int x)
{
int flag=0,t=1;//t为非零元素的结点序号
while(t
{
if(M.data[t].v==x)//非零元素值为x查找成功
{printf("The %d is in rows:%2d\n and
cols:%2d\n",x,M.data[t].i,M.data[t].j);//输出查找的值为x的结点的行列号 flag=1;
}
t++;
}
if(flag)
return(1);//查找成功
else
{
printf("The %d is not in the M\n",x);
return(0);//查找失败
}
}
5、打印函数
Print_Pmatrix(PMatrix X)
{
int i,j,n=1;//i、j分别为行列号,n为非零元素的结点序
for(i=1;i
{
for(j=1;j
{
if(i==X.data[n].i&&j==X.data[n].j)
{
printf("%d\t",X.data[n].v);//输出非零元素值 n++;
}
else printf("%d\t",0);//输出0
}
printf("\n");
}
}
3、流程图
五 调试分析
1、程序的关键是掌握稀疏矩阵的压缩存储结构、转置算法、查找算法和输出标准形式矩阵的算法。在编程的过程中,出现了很多问题,如转置时我用的“按M得行序扫描”,结果转置后的矩阵不是按顺序存储,之后我改成按列序扫描,程序就运行正常了。即用如下设计:for(col=1;col
2、打印函数时,只能打印原函数,之后我加了下列语句:
printf("输入你需要打印的矩阵(输入0或者1):\n");
scanf("%d",&x); if(x==0) { X=M; printf("打印矩阵:\n");
Print_Pmatrix(X);
} else { X=N;
printf("打印矩阵:\n");
Print_Pmatrix(X);
之后,程序就实现了打印原矩阵和转置后的矩阵了。
3、文件的读取格式要熟练,即文件名.后缀名,才能准确地实现程序功能,达到目的
六 测试结果
1、测试数据
此次测试用例,我随便选取了一组测试数据用于程序的测试,按照程序的说明创建矩阵M,然后选择不同的功能选项,可以实现转置、查找、打印原矩阵和转置后的矩阵等功能。
输入矩阵M为
4.2测试结果及分析
输入1,创建矩阵M,采用三元组顺序表进行存储
输入2,对M进行转置
输入3,查找x=5的结点
再次输入3,查找x=1的结点
再次输入3,查找x=9的结点
输入4,输入0,打印原矩阵
M
输入4,输入1,打印原矩阵N
输入0,退出程序
七 用户使用说明
1、本程序在VC环境下运行。
2、输入行号列号时其间的要用逗号且必须用逗号隔开。
3、进入本系统之后,随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的数字并按回车,执行相应子菜单命令
八 课程设计总结
1、原来我对稀疏矩阵的存储以及运算的知识很模糊,通过此次课程设计,我加深了对稀疏矩阵的压缩存储方式、对求稀疏矩阵的转置矩阵及查找算法的了解。同时复习和巩固了对文件的基本操作。
2、 在做课程设计的过程中遇到了很多问题,让我知道了自己对很多知识点都掌握的不够。随着这些问题的解决,对之前掌握的不够好的知识点进行了巩固和复习。总之,这次课程设计让我明白了自己在很多方面的不足,也让我学到了很多。
3、模块设计。模块化的设计使得程序的可读性有了很大的提高。使程序更加有条理。对程序的运行效率也有积极的作用。菜单的编写,使得操作页面显得更正规,有利于操作者的操作。