实验报告----数据结构课程设计稀疏矩阵的应用.doc

稀疏矩阵的应用

数学与计算机学院
课程设计说明书

课 程 名 称: 数 据 结 构 课 程 设 计
课 程 代 码: 6014279
题 目: 稀疏矩阵的应用
年级/专业/班: 2010级 软件工程 2班
学 生 姓 名: 尹 龙 海
学　　 号: 312010080611228
开 始 时 间: 2011 年 12 月 08 日
完 成 时 间: 2011 年 12 月 16 日
课程设计成绩：
学习态度及平时成绩（30）
技术水平与实际能力（20）
创新（5）
说明书（计算书、图纸、分析报告）撰写质量（45）
总 分（100）

指导教师签名： 年 月 日

数据结构课 程 设 计 任 务 书

学院名称： 数学与计算机学院 课程代码：__ 8404181______

专 业： 软件工程（Web方向） 年 级： 2010级2班

一、设计题目
稀疏矩阵应用
二、 主要内容
主要完成稀疏矩阵的加、转、乘的实现。
三、具体要求及应提交的材料
以三元组、十字链表为存储形式，分别实现两个稀疏矩阵的加法运算、两个稀疏矩阵的乘法运算，以及对任意稀疏矩阵的转置运算。稀疏矩阵要求可为键盘录入的任意矩阵。
用C/C++语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：
1)课程设计说明书打印稿一份
2)课程设计说明书电子稿一份；
3)源程序电子文档一份。
四、主要技术路线提示
注意合理地设计三元组及十字链表，结合稀疏矩阵的压缩存储方式和特点，将每一功能模块以函数形式分别实现。在此基础上用C/C++实现其操作。
五、进度安排
按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下：

序号
设计内容
天数
1
分析问题，给出数学模型，选择数据结构
2
2
设计算法，给出算法描述
1
3
给出源程序清单
2
4
编辑、编译、调试源程序
2
5
编写课程设计报告
3
总 计
10
六、推荐参考资料
[1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。
[2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。
[3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年9月
[4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004年4月
[5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月
[6] 徐孝凯 等著.数据结构（C语言描述）.清华大学出版社.2004

指导教师 签名日期 年 月 日

系 主 任 审核日期 年 月 日

目 录

摘要………………………………………………………………………………5
引言………………………………………………………………………………5
1 需求分析………………………………………………………………………6
2 概要设计………………………………………………………………………6
3详细设计………………………………………………………………………8
4调试分析………………………………………………………………………15
5用户使用说明…………………………………………………………………15
6测试结果………………………………………………………………………15
7结论……………………………………………………………………………19
致谢………………………………………………………………………………20
参考文献…………………………………………………………………………21

摘 要
本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘等操作，最后输出运算后的结果。考虑到难易程度，先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘等操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。
关键词：程序设计；稀疏矩阵；三元组；十字链表
引 言
1.1 课程设计任务
本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个稀疏矩阵A和B的和为矩阵C，并输出C； 求出A的转置为矩阵D，输出D； 求两个稀疏矩阵A和B的相乘为矩阵E，并输出E。
1.2 课程设计性质
数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。
1.3课程设计目的
其目的是让我们在学习完C++、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
需求分析
2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值
本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化时，只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时，以矩阵的完整形式输出。
2.2构造函数进行稀疏矩阵的转置并输出结果
本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。
2.3构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵
本模块要求设计相加、减和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，定义相应的矩阵类型用于存放两个矩阵操作后的结果矩阵，这个结果矩阵的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点，需要灵活运用数组及指针的特点。
2.4退出系统
本模块要求设置选项能随时结束程序的运行，本程序中采用do-while循环。程序在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。
概要设计
3.1存储结构设计
三元组结构体定义:
struct mat
{int i;//非零元素的行位置
int j;//非零元素的列位置
int v;//非零元素的值
};
class sqmatrix
{private:
int m;//矩阵的行数
int n;//矩阵的列数
int t;//矩阵中非零元素的个数
mat data[max];//三元组表
int rpos[max];//存储矩阵中第max行以前所有非零元素的个数
public:
};
十字链表结构体定义:
typedef struct OLNode
{int i,j; //该非零元的行、列下标
int e; //非零元值
struct OLNode *right,*down; // 该非零元所在行表和列表的 后继元素
}OLNode,*OLink;
// 定义十字链表对象结构体
typedef struct
{OLink *rhead,*chead; //OLink类型 结点数组
int a,b,c; // 系数矩阵的行数，列数，和非零元素个数
}CrossList;
3.2系统功能设计
本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储结构下，由函数 void creat()实现，在十字链表存储结构下，由函数void CreateSMatix_OL(CrossList &M)依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。
（1）稀疏矩阵的转置：
此功能在三元组存储结构下，有两种方法：按行转置和按列转置，分别由函数sqmatrix transmatone()和sqmatrix transmattwo()实现，在十字链表存储结构下，由函数void zhuanzhi( )实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。
（2）稀疏矩阵的加法：
此功能在三元组存储结构下，由函数void add(sqmatrix a,sqmatrix b)实现，在十字链表存储结构下，由函数void add()实现。当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。
（3）稀疏矩阵的乘法：
此功能在三元组存储结构下，由函数void cheng(sqmatrix a,sqmatrix b)实现。在十字链表存储结构下，由函数void chengfa()实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。
（4）退出：
即退出稀疏矩阵的应用系统，由switch语句实现。当用户选择相应序号，则退出该稀疏矩阵的应用系统。
详细设计
4.1 数据类型定义
三元组结构体定义:
struct mat
{int i;//非零元素的行位置
int j;//非零元素的列位置
int v;//非零元素的值
};
class sqmatrix
{private:
int m;//矩阵的行数
int n;//矩阵的列数
int t;//矩阵中非零元素的个数
mat data[max];//三元组表
int rpos[max];//存储矩阵中第max行以前所有非零元素的个数
public:
};
十字链表结构体定义:
typedef struct OLNode
{int i,j; //该非零元的行、列下标
int e; //非零元值
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct
{OLink *rhead,*chead; //OLink类型 结点数组
int a,b,c; // 系数矩阵的行数，列数，和非零元素个数
}CrossList;

4.2系统主要子程序详细设计
A. 主程序模块设计：
采用一个do-while语句执行各个功能的操作循环，并用switch语句控制选择三元组或十字链表进行相关的操作，在采用的操作界面中，再用switch语句控制各功能的实现，主要代码如下：
do{cout<<endl;
cout<<"\n ***稀疏矩阵应用***"<<endl<<endl;
cout<<"\n 请你选择创建稀疏矩阵的方法 "<<endl;
cout<<"\n 1、用三元组创建稀疏矩阵"<<endl;
cout<<"\n 2、用十字链表创建稀疏矩阵"<<endl;
cout<<"\n 3、退出程序"<<endl<<endl;
cout<<"请选择：";cin>>k; cout<<endl;
switch(k)
{case 1: {cout<<" 欢迎进入《三元组操作》矩阵系统"<<endl<<endl;
switch(kk)
{case 1: 两矩阵求和}break;
case 2: {两矩阵相乘}break;
case 3: {矩阵按行转置}break;
case 4: {矩阵按行转置}break;
case 5: {退出该程序}break;
}cout<<endl; }break;
case 2: {cout<<" 欢迎进入《十字链表操作》矩阵系统"<<endl<<endl;
switch(kk) {case 1: {两矩阵求和}break;
case 2: {两矩阵相乘}break;
case 3: {两矩阵相减}break;
case 4: {矩阵转置}break;
case 5: {退出该程序}break;
}cout<<endl; }break; }
}while(k==1||k==2); cout<<endl; return 0; }
B. 稀疏矩阵操作各子函数的定义：
(1)建立与初始化稀疏矩阵：
采用三元组建立稀疏矩阵，输入非零元素的行号、列号和值，关键代码如下：
cout<<"行号i 列号j 非零元素值v"<<endl;
for(int p=0;p<t;p++)
{cout<<" ";cin>>ii;data[p].i=ii;cout<<" ";
cin>>jj;data[p].j=jj;cout<<" ";
cin>>element;data[p].v=element; cout<<endl; }
采用十字链表建立稀疏矩阵，输入非零元素的行号、列号和值，给新结点申请空间，按列循环链表和行循环链表形式插入到十字链表中关键代码如下：
{int x,y,m; cout<<"请输入稀疏矩阵的行，列，及非零元素个数"<<endl; cin>>M.a>>M.b>>M.c;
cout<<"请按三元组的格式输入数组："<<endl;
for(int i=1;i<=M.c;i++)
{ cin>>x>>y>>m; cout<<endl; OLink p,q;
p->i=x; p->j=y; p->e=m;
if(M.rhead[x]==NULL||M.rhead[x]->j>y) {
p->right=M.rhead[x]; M.rhead[x]=p; }
else{ for(q=M.rhead[x];(q->right)&&(q->right->j<y);q=q->right);
p->right=q->right; q->right=p; }
if(M.chead[y]==NULL||M.chead[y]->i>x)
{p->down=M.chead[y]; M.chead[y]=p; }
else{for(q=M.chead[y];(q->down)&&(q->down->i<x);
q=q->down); p->down=q->down; q->down=p; } }
（2）输出稀疏矩阵：
用三元组输出矩阵元素时，若稀疏矩阵所对应的元素在三元组中有该元素，则输出三元组中的这个元素的值，否则，输出零。其关键代码如下：
if(data[p].i==i&&data[p].j==j)
{isfound=true;foundindex=p; }
if(isfound==true) cout<<setw(5)<<data[foundindex].v;
else
cout<<setw(5)<<"0";}
用十字链表输出矩阵元素时，若稀疏矩阵所对应的元素在十字链表中有该元素，则输出三元组中的这个元素的值，同时指针指向下一个结点，否则，输出零。其关键代码如下：
{if((p)&&(j==p->j)) {cout<<p->e<<" "; p=p->right; }
else
cout<<"0"<<" "; } cout<<endl<<endl; } }
（3）实现矩阵的转置：
用三元组和十字链表实现矩阵转置，都采用元素所对应的行号变为新矩阵的列号，所对应的列号变为新矩阵的行号，所对应的值不变，在这个过程中采用一个for循环使待转置的元素所对应的列号较小者先转置到新矩阵中，其关键代码如下：
b.m=n;b.n=m;b.t=t;
if(t!=0) {int q=0; for(int col=1;col<=n;col++)
for(int p=0;p<t;p++)
{if(data[p].j==col) {b.data[q].j=data[p].i;
b.data[q].i=data[p].j; b.data[q].v=data[p].v;
q++;}}}cout<<endl<<endl; return b; }
（4）实现两个矩阵的相加：
采用三元组实现两矩阵相加时，先判断被加的两矩阵所对应的位置是否有非零元素，若没有或两矩阵元素相加为零，则新三元组表中不进行任何操作，若只有一个为非零元素，则新三元组表中对应位置元素值就为该非零元素的值，若两矩阵相同位置元素和k不为零，则新三元组表中对应应位置元素值就为k。其关键代码如下：
while(pa<=a.t&&pb<b.t) {ka=(a.data[pa].i-1)*n+a.data[pa].j; kb=(b.data[pb].i-1)*n+b.data[pb].j;
if(ka<kb){pc++;data[pc]=a.data[pa];pa++;}
else if(ka>kb){pc++;data[pc]=b.data[pb];pb++;}
else{s=a.data[pa].v+b.data[pb].v; if(s==0){pa++;pb++;}
else{pc++;data[pc]=a.data[pa]; data[pc].v=s; pa++;pb++;}}
}while(pa<a.t){pc++;data[pc]=a.data[pa];pa++;}
while(pb<b.t){pc++;data[pc]=b.data[pb];pb++;} t=pc+1; }
采用十字链表实现两矩阵相加时，和三元组实现两矩阵相加类似，不同点就是元素相加后转向被加的两个元素结点向下移动，新三元组的指针也向下移动其关键代码如下：
OLink pa,pb,pre ,hl[MAXROW+1];
for(int x=1;x<=M.b;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.a;k++) { pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb) { OLink p;
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j) { if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p; if(NULL==M.chead[p->j]) {
M.chead[p->j]=p; p->down=NULL; }
else{ p->down=hl[p->j]->down; hl[p->j]->down=p; }
hl[p->j]=p; pb=pb->right; }
else
if((NULL!=pa)&&pa->j<pb->j) {
pre=pa; pa=pa->right; }
else
if(pa->j==pb->j)
{ pa->e += pb->e; if(!pa->e) {
if(NULL==pre) M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right; if(M.chead[p->j]==p)
M.chead[p->j]=hl[p->j]=p->down;
else
hl[p->j]->down=p->down;
free(p); pb=pb->right; }
else{ pa=pa->right; pb=pb->right; } } } }shuchu(M); }
（5）实现两个矩阵的相乘：
三元组实现两矩阵相乘和三元组实现两矩阵相加类似，不同就是新矩阵非零元素所在行和列的值是两矩阵所对应行元素与所对应列元素相乘后相加，其主要代码如下：
int ctemp[max]; t=0; m=a.m; n=a.n;
if(a.t*b.t!=0) {for(arow=1; arow<=a.m; arow++)
{for(ii=1; ii<=a.n; ii++) ctemp[ii]=0;
rpos[arow]=t;Mlim=arow<a.m?a.rpos[arow+1] : a.t+1;
for( Mcol=a.rpos[arow]; Mcol<Mlim; Mcol++ ){
Mj=a.data[Mcol].j; Nlim = Mj<b.m ? b.rpos[Mj+1] : b.t+1;
for(Nrow=b.rpos[Mj];Nrow<Nlim;Nrow++) ctemp[b.data[Nrow].j] += a.data[Mcol].v * b.data[Nrow].v;
}
十字链表实现矩阵相乘和十字链表实现矩阵相加类似，都要判断相乘后是否为零，在操作时要注意指针的指向。其关键代码如下：
for(int x=1;x<=M.b;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.a;k++)
{ pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb)
{ OLink p;
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j) {
if(NULL==pre) M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){ M.chead[p->j]=p;
p->down=NULL; }
else { p->down=hl[p->j]->down; hl[p->j]->down=p; }
hl[p->j]=p; pb=pb->right; }
else
if((NULL!=pa)&&pa->j<pb->j)
{ pre=pa; pa=pa->right; }
else
if(pa->j==pb->j) { pa->e *= pb->e;
if(!pa->e) {if(NULL==pre)
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p)
M.chead[p->j]=hl[p->j]=p->down;
else
hl[p->j]->down=p->down;
free(p); pb=pb->right; }
else{ pa=pa->right; pb=pb->right; }
调试分析
用C++语言写代码实现所要求的功能过程中，用三元组实现矩阵相乘，有一定的难度，我通过多次调试，系统始终提示出错，通过参考网友的代码和同学的提示，原来两矩阵的第i行非零元素个数不一定等于另一矩阵的第i列非零元素个数，最后，我通过控制一矩阵的非零元素所在的i行、j列位置与另一个矩阵所对应的i列j行元素相乘，然后在相加。通过测试，功能能够实现了；在用十字链表实现各功能时，由于指针很多，写出的代码最初基本上都是指针指向出错，通过自己经验以及老师的指导、朋友的帮助，最后解决了各个问题。
　用户使用说明
该系统具有简单、明了、使用等特点，能够方便、准确的计算出矩阵的部分操作，适用于学校老师、同学对矩阵方面的研究。当使用该系统时，系统会给出相关的提示信息，用户只需根据提示信息，即可完成系统提供的所有功能。
　测试结果
7.1系统运行主界面
系统运行主界面如图7.1所示：

图7.1 主界面图

7.2 各子功能测试运行结果
（1）稀疏矩阵的相加：
在主菜单下，用户输入1回车，是用三元组对矩阵的操作，用户再按1回车，根据屏幕提示操作，运行结果如图7.2所示。

图7.2 三元组创建并初始化矩阵
在主菜单下，用户输入2回车，是用十字链表对矩阵的操作，根据屏幕提示操作，运行结果如图7.3所示。

图7.3 十字链表创建并初始化矩阵
（2）稀疏矩阵的转置：
用三元组创建稀疏矩阵后，用户在三元组操作下输入3或4回车，便显示该矩阵的转置矩阵，运行结果如图7.4所示。

图7.4 三元组稀疏矩阵转置结果示意图
用十字链表创建稀疏矩阵后，用户在十字链表操作下输入4回车，便显示该矩阵的转置矩阵，运行结果如图7.5所示。

图7.5 十字链表稀疏矩阵转置结果示意图
（3）稀疏矩阵的相乘：
在三元组或十字链表操作下输入2回车，按屏幕提示操作，运行结果如图7.6所示。

图7.6 三元组稀疏矩阵相加结果示意图
（5）退出：
在主菜单下，用户输入3回车，或者在下级菜单中输入5回车，退出程序。运行结果如图7.7。

图7.7 下级菜单退出程序图

结 论

由于本程序要求用两种办法对稀疏矩阵进行运算，特别是用十字链表这种形式来对稀疏矩阵进行运算，是实现起来有很多困难，主要包括：
1、书上这种方面的东西不多，资料少，可以参考的东西不是很多；
2、用十字链表进行运算比较复杂，难度较大，需要对指针掌握较好；
3、在书写课程设计报告时，没有具体的详细的模板，感觉有一点无从下手，害怕写错。
针对上述困难，自己对症下药，通过网络，图书馆找资料，请老师指点，借鉴别人的已往的优秀的课程设计报告，以及老师给的报告要求书，和同学们一起讨论，逐步地解决自己的问题。
在做这个课程设计的过程我也学到了许多知识。懂得了用三元组表和十字链表存储稀疏矩阵的元素不仅可以操作数组能操作的大部分重要功能外，他们还能避免空间浪费。而采用十字链表和采用三元组各有各的优缺点。三元组在实现各功能时操作简单、易懂，但算法的时间复杂度较十字链表的要大（例如：用三元组实现行转置的算法时间复杂度大于O（m*n），而用十字链表来实现时间复杂度则接近O(m+n)）。当矩阵非零元素的位置或个数经常变动时，采用十字链表可以避免大量移动数据元素，但用十字链表算法复杂、难懂，很容易把指针的指向弄错。除此之外，我也懂得了一个软件实验报告的大概写法。
通过此次课程设计，使我对本学期学的《数据结构》有了更深的了解，也使自己的所学更加牢固，并能够把更多方面的知识综合起来运用。

致 谢
在本次课程设计过程中，首先感谢学校相关领导给了我一次提升实力的机会。其次要感谢监督我完成该实验的陈红红老师，是她在我需要必要帮助时，申出了援助之手。还要感谢教过我C++语言和数据结构的各位老师，是他们的授课，让我打下了完成该实验的基础。最后，感谢身边的同学们、朋友们以及网友们，是你们给了我完成该实验的思路、方法。
参考文献
［1］杨宝刚.开展企业管理信息化工作的步骤［J］.企业管理.2002.（11）.12~15
［2］Islamabad. Software tools for forgery detection［J］. Business line.2001. (5）. 29~32
[3] 王立柱.C/C++与数据结构.北京：清华大学出版社，2002
[4] 顾元刚.数据结构简明教程.南京：东南大学出版社等，2003
[5] 郭福顺，王晓芬，李莲治《数据结构》（修订本），大连理工大学出版社，1997
[6] [美]Mark Allen Weiss，数据结构与算法分析——C语言描述(英文版•第2版)，人民邮电出版社，2005.8
[7] 李春葆著，数据结构教程，清华大学出版社，2005.1