稀疏矩阵的应用Word格式.docx
《稀疏矩阵的应用Word格式.docx》由会员分享，可在线阅读，更多相关《稀疏矩阵的应用Word格式.docx（25页珍藏版）》请在冰点文库上搜索。
程序设计；
稀疏矩阵；
三元组；
十字链表
引言
1需求分析
其目的是让我们在学习完C++、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
1.1任务与分析
本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。
稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个稀疏矩阵A和B的和为矩阵C，并输出C；
求出A的转置为矩阵D，输出D；
求两个稀疏矩阵A和B的相乘为矩阵E，并输出E。
1.2测试数据
545
113147
23-1312
54-8
5410
131142222
231241343
411426
441512
2概要设计
2.1存储结构设计
三元组结构体定义:
structelement
{
inti,j;
ElemTypeitem;
};
constintMaxTerm=100;
structSparsematrix
elementdata[MaxTerm];
intmu,nu,tu;
//行数、列数、非零元个数
十字链表结构体定义:
typedefstructMLnode
inti;
//结点的行下标
intj;
//结点的列下标
ElemTypee;
//非零元的值
structMLnode*right,*down;
//该非零元所在行表和列表的后继元素
}MLnode;
2.2程序模块结构
2.2.1 结构体定义
2.3 各功能模块
本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。
稀疏矩阵的建立及初始化在三元组存储结构下，由函数voidcreatT（）实现，在十字链表存储结构下，由函数voidCreateL（Sparsematrix&
X）依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。
4个子功能的设计描述如下。
（1）稀疏矩阵的转置：
此功能在三元组存储结构下，有两种方法：
按行转置和按列转置，分别由函数voidzhuanzT（SparsematrixX,Sparsematrix&
b）和sqmatrixtransmattwo（）实现，在十字链表存储结构下，由函数voidzhuanzhi（）实现。
当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。
（2）稀疏矩阵的加法：
此功能在三元组存储结构下，由函数voidaddT（Sparsematrixa,Sparsematrixb,Sparsematrix&
c）实现，在十字链表存储结构下，由函数voidaddL（CrossList&
a,CrossList&
b）实现。
当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。
然后进行加法，最后输出结果。
（3）稀疏矩阵的乘法：
此功能在三元组存储结构下，由函数voidcheng（sqmatrixa,sqmatrixb）实现。
在十字链表存储结构下，由函数voidchengfa（）实现。
当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。
然后进行相乘，最后得到结果。
（4）退出：
即退出稀疏矩阵的应用系统，由switch语句实现。
当用户选择相应序号，则退出该稀疏矩阵的应用系统。
3详细设计
3.1结构体定义
…三元组结构体定义:
3.2插入操作
A.主程序模块设计：
Sparsematrixs1,s2,s3;
CrossListc1,c2;
//两个链表储存的矩阵
intk;
do{
cout<
<
endl;
"
***********稀疏矩阵应用**************"
<
endl<
请你选择创建两个稀疏矩阵的方法"
1、用三元组顺序表创建稀疏矩阵"
2、用十字链表创建稀疏矩阵"
3、退出程序"
请选择：
"
;
cin>
>
k;
cout<
switch（k）{
case1:
{
createT（s1）;
//三元组顺序表创建矩阵
printT（s1）;
createT（s2）;
printT（s2）;
}break;
case2:
createL（c1）;
//十字链表创建矩阵
printL（c1）;
createL（c2）;
printL（c2）;
}break;
}
switch（k）
{
cout<
**********欢迎进入《三元组操作》矩阵系统**********"
\n1、两矩阵求和"
cout<
\n2、两矩阵相乘"
\n3、矩阵按行转置"
\n4、退出程序"
intkk=0;
cin>
kk;
switch（kk）
{
case1:
{addT（s1,s2,s3）;
printT（s3）;
case2:
break;
case3:
{cout<
转置第一个矩阵"
Sparsematrixs4;
zhuanzT（s1,s4）;
printT（s4）;
case4:
}
}break;
**********欢迎进入《十字链表操作》矩阵系统**********"
\n4、矩阵按列转置"
\n5、退出程序"
switch（kk）{
{addL（c1,c2）;
printL（c1）;
}break;
}while（k==1||k==2）;
cout<
}
B.稀疏矩阵操作各子函数的定义：
（1）建立与初始化稀疏矩阵：
采用三元组建立稀疏矩阵，输入非零元素的行号、列号和值，关键代码如下：
请输入稀疏矩阵的行数、列数、非零元值个数:
endl;
X.mu>
X.nu>
X.tu;
行号i列号j非零元素值item"
for（intp=0;
p<
X.tu;
p++）
intii,jj,element;
ii>
jj>
element;
X.data[p].i=ii;
X.data[p].j=jj;
X.data[p].item=element;
}
采用十字链表建立稀疏矩阵，输入非零元素的行号、列号和值，给新结点申请空间，按列循环链表和行循环链表形式插入到十字链表中关键代码如下：
voidcreateL（CrossList&
X）
inti,j,e,k;
MLnode*p,*q;
//if（X）deleteX;
请输入矩阵的行数、列数和非零元素个数：
X.m>
X.n>
X.t;
X.rhead=（MLnode**）newMLnode[X.m+1];
//按行数申请动态MLnode*类型的数组；
并赋值全为空
for（k=1;
k<
=X.m;
k++）
X.rhead[k]=0;
X.chead=（MLnode**）newMLnode[X.n+1];
//按列数申请动态MLnode*类型的数组；
=X.n;
k++）
X.chead[k]=0;
intr=X.t;
请输入结点的行号、列号和非零元素值"
i>
j>
e;
while（i）
--r;
p=newMLnode;
p->
i=i;
p->
j=j;
e=e;
if（X.rhead[i]==0||X.rhead[i]->
j>
j）//若链表为空或者该行头头指针所在列大于输入的非零元所在列号小于号，前插，后移动头指针
p->
right=X.rhead[i];
X.rhead[i]=p;
else//否则如果该行头指针所在列小于或等于输入的非零元所在列号，后插，不移动头指针
for（q=X.rhead[i];
（q->
right）&
&
q->
right->
j<
j;
q=q->
right）;
//寻找插入点
right=q->
right;
right=p;
if（X.chead[j]==0||X.chead[j]->
i>
i）{p->
down=X.chead[j];
X.chead[j]=p;
else{
for（q=X.chead[j];
down）&
down->
i<
i;
down）;
down=q->
down;
down=p;
if（r==0）break;
}
（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<
0"
用十字链表输出矩阵元素时，若稀疏矩阵所对应的元素在十字链表中有该元素，则输出三元组中的这个元素的值，同时指针指向下一个结点，否则，输出零。
for（intk=1;
p=X.rhead[k];
for（ints=1;
s<
s++）{
if（（p）&
s==p->
j）{cout<
e;
p=p->
else
cout<
setw（5）<
（3）实现矩阵的转置：
用三元组和十字链表实现矩阵转置，都采用元素所对应的行号变为新矩阵的列号，所对应的列号变为新矩阵的行号，所对应的值不变，在这个过程中采用一个for循环使待转置的元素所对应的列号较小者先转置到新矩阵中，其关键代码如下：
voidzhuanzT（SparsematrixX,Sparsematrix&
b）
intk=1;
for（inti=1;
i<
=X.mu;
i++）
for（intj=1;
j<
=X.nu;
j++）
boolisfound=false;
intfoundindex;
for（intp=0;
p<
if（X.data[p].i==i&
X.data[p].j==j）
{
isfound=true;
foundindex=p;
break;
}
if（isfound==true）{
b.data[k].i=j;
b.data[k].j=i;
b.data[k].item=X.data[foundindex].item;
++k;
b.mu=X.nu;
b.nu=X.mu;
b.tu=k;
（4）实现两个矩阵的相加：
采用三元组实现两矩阵相加时，先判断被加的两矩阵所对应的位置是否有非零元素，若没有或两矩阵元素相加为零，则新三元组表中不进行任何操作，若只有一个为非零元素，则新三元组表中对应位置元素值就为该非零元素的值，若两矩阵相同位置元素和k不为零，则新三元组表中对应应位置元素值就为k。
//三元组顺序表矩阵的相加
voidaddT（Sparsematrixa,Sparsematrixb,Sparsematrix&
c）
inti=1,j=1,k=1;
while（i<
=a.tu&
j<
b.tu）
if（a.data[i].i==b.data[j].i）
if（a.data[i].j==b.data[i].j）
c.data[k].i=a.data[i].i;
c.data[k].j=a.data[i].j;
c.data[k].item=a.data[i].item+b.data[j].item;
j++;
k++;
if（a.data[i].j<
b.data[i].j）
c.data[k].i=a.data[i].i;
c.data[k].j=a.data[i].j;
c.data[k].item=a.data[i].item;
i++;
if（a.data[i].j>
c.data[k].i=b.data[j].i;
c.data[k].j=b.data[j].j;
c.data[k].item=b.data[j].item;
elseif（a.data[i].i<
b.data[j].i）
c.data[k].i=a.data[i].i;
c.data[k].j=a.data[i].j;
c.data[k].item=a.data[i].item;
i++;
elseif（a.data[i].i>
b.data[j].i）
c.data[k].i=b.data[j].i;
c.data[k].j=b.data[j].j;
c.data[k].item=b.data[j].item;
j++;
c.mu=a.mu;
c.nu=a.nu;
c.tu=k;
}采用十字链表实现两矩阵相加时，和三元组实现两矩阵相加类似，不同点就是元素相加后转向被加的两个元素结点向下移动，新三元组的指针也向下移动其关键代码如下：
voidaddL（CrossList&
b）//矩阵a与矩阵b相加，用b插入a
intmax=a.n;
MLnode**hl;
hl=（MLnode**）newMLnode[max];
MLnode*pa,*pb,*pre,*insert,*keep;
for（inti=1;
=a.m;
pa=a.rhead[i];
//初始化指向首结点，以后逐个向后移动
pb=b.rhead[i];
pre=NULL;
max;
j++）//n为矩阵列数,hl的作用是等同于pre指针，追踪竖向上新插入的结点
hl[j]=a.chead[j];
while（pb!
=NULL）
if（pa==NULL||pa->
j>
pb->
j）//横插
insert=newMLnode;
insert->
i=pb->
j=pb->
e=pb->
e;
if（pre==NULL）a.rhead[i]=insert;
elsepre->
right=insert;
right=pa;
pre=insert;
//pre用于最终新插入的结点
if（a.chead[insert->
j]==NULL||a.chead[insert->
j]->
i>
insert->
i）//竖插（拿新插入结点的所在列的头结点行数与新插入结点行数比较）
insert->
down=a.chead[insert->
j];
a.chead[insert->
j]=insert;
down=hl[insert->
hl[insert->
down=insert;
hl[insert->
pb=pb->
elseif（pa->
j==pb->
j）
pa->
e+=pb->
if（pa->
e==0）//如果相加不为0，不用操作，pa已经改动；
keep=pa;
if（pre==NULL）{a.rhead[i]=pa->
}//pre不一定一定等于0当前一种情况的时候pre指向有可能改变
else{pre->
right=pa->
}//pre指向行首结点?
pa=pa->
deletekeep;
升级会员 