稀疏矩阵的操作.doc

完整word)稀疏矩阵的操作

《稀疏矩阵的操作》
数据结构课程设计报告

专 业： 计算机科学与技术
班 级：
姓 名：
学 号：
指导教师:

完成日期：2013-1-9

目录
1课程设计题目与要求 3
1。1课程设计的目的: 3
1.2课程设计的题目： 3
1.3题目要求: 3
2 总体设计 4
2。1程序结构与整体示意图 4
2.2各子模块功能介绍 4
3详细设计 5
3.1引入常量 5
3。2存储结构 5
3。3程序流程图 6
4运行结果： 9
5课程设计总结 12
6参考书目 12

1课程设计题目与要求
1。1课程设计的目的:
1．掌握多维数组的逻辑结构和存储结构。
2．掌握稀疏矩阵的压缩存储及基本操作。
1。2课程设计的题目:
稀疏矩阵的操作
1。3题目要求：
（1） 稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。
（2） 求出A的转置矩阵D，输出D用两种方法实现，原始算法和改进的算法）.
（3） 求两个稀疏矩阵A和B的相乘矩阵E，并输出E.
2 总体设计
2.1程序结构与整体示意图

函数的声明
void InitMatrix1(SMatrix＆ M)；//顺序存储结构 对稀疏矩阵的初始化
void InitMatrix2（LMatrix& M）；//链式存储结构 对稀疏矩阵的初始化
void InputMatrix1(SMatrix＆ M，int m,int n)；//顺序存储结构 输入函数
void InputMatrix2（LMatrix＆ M,int m,int n）;//链式存储结构 输入函数
void OutputMatrix1(SMatrix& M);//顺序存储结构 输出函数
void OutputMatrix2(LMatrix& M);//链式存储结构 输出函数
SMatrix Transpose（SMatrix& M)；//顺序存储结构 普通转置
SMatrix FastTranspose(SMatrix＆ M);//顺序存储结构 快速转置
LMatrix Add（LMatrix＆ M1,LMatrix& M2）;//链式存储结构 加法
void menu()；// 菜单函数

2。2各子模块功能介绍
1. 稀疏矩阵的存储结构的建立
以结构体为基础建立存储结构，分为顺序存储和链式存储的方式.采用三元组法，对系数矩阵中非零的元素进行存储，存储行号、列号以及元素的值（value)并记录下行，列及非零元素个数.
2. 稀疏矩阵的初始化函数
将矩阵的行、列以及非零元素的个数初始化零，保持程序的稳定性。
3. 稀疏矩阵的录入函数
将非零的元素值的行、列以及值录入创建的矩阵中。
4. 稀疏矩阵的输出函数
将进行操作后的稀疏矩阵输出。
5. 稀疏矩阵的转置、快速转置以及加法函数函数
对稀疏矩阵进行一系列的操作。
6. 菜单函数
对操作进行说明。
3详细设计
3.1引入常量
＃define MaxTerms 10
#define MaxRows 10
定义矩阵最大为10行10列
3.2存储结构
通过使用结构体来存储相关信息:
struct Triple//定义三元组 顺序存储
{
int row,col;//行号和列号
ElemType val;//元素值
｝;
struct SMatrix //定义稀疏矩阵的结构 顺序存储
{
int m，n,t；//行,列及非零元素个数
Triple sm[MaxTerms+1];
｝；
struct TripleNode//三元组结点 链式存储结构
｛
int row，col；
ElemType val；
TripleNode＊ next;
};
struct LMatrix//定义稀疏矩阵的结构 链式存储结构
{
int m，n,t；
TripleNode* vector［MaxRows+1]；
｝；

3.3程序流程图
输入函数
N
Y

普通转置
N
N
Y
Y

稀疏矩阵的加法

4运行结果:
主界面

顺序存储建立稀疏矩阵

稀疏矩阵的普通转置

稀疏矩阵的快速转置

三元组建立稀疏矩阵链式存储

稀疏矩阵的加法

5课程设计总结
在此课程设计中，实际对稀疏矩阵的操作。由于稀疏矩阵中存在大量的0值，对于程序来说，要把大量的0值存储起来再一个个的进行运算是非常浪费空间和时间的，为此,我们优化存储方式,通过三元组定义元素的行、列以及元素值来确定元素的基本属性。为0的则不进行定义。根据系数矩阵的定义,矩阵中有至少十分之九的元素值为0,通过三元组的存储， 我们至少节约了十分之九的存储的存储,在进行转置操作的操作中，可以近似的认为以直接访问的方式来访问元素的各个属性，即行、列以及元素的值.这样有大大减少了程序的运行时间.
在传统的普通二维矩阵中操作，必须通过双重甚至三重的for循环进行复制和操作，例如再赋值过程中，要通过双重的for进行赋值，时间复杂度为o（n^2），而在进行转置是，时间复杂度为 o（n^3），这种时间花费太大，而通过三元组，则大大减少时间。
数据结构是计算机专业必学的学习的课程，通过对数据结构的学习,我学到了对数据进行组织好操作的基本方法。一个好的程序员不仅仅熟悉各种语言,更重要的是学会各种算法并在存储的层次中对数据进行操作，通过好的结构,来缩短程序运行的时间复杂度，提高程序的运行效率。数据结构这门课程我感觉只是学了一点点而已,以后一定要加强对这门课程的深入学习，设计好的算法。
6参考书目
1. 谭浩强. C++程序设计。北京：清华大学出版社，2008.
2. 数据结构(C语言版) 人民邮电出版社，2011

源代码
＃include 〈iostream〉
#define MaxTerms 10
＃define MaxRows 10
using namespace std；
typedef int ElemType;
struct Triple//定义三元组 顺序存储
{
int row,col；//行号和列号
ElemType val；//元素值
｝
struct SMatrix //定义稀疏矩阵的结构 顺序存储
｛
int m,n，t;//行，列及非零元素个数
Triple sm[MaxTerms+1］;
｝；
struct TripleNode//三元组结点 链式存储结构
｛
int row,col；
ElemType val;
TripleNode* next；
};
struct LMatrix//定义稀疏矩阵的结构 链式存储结构
{
int m，n，t；
TripleNode* vector［MaxRows+1］；
｝；
//以上是对顺序和链式存储结构定义
//函数的声明
void InitMatrix1（SMatrix& M);//顺序存储结构 对稀疏矩阵的初始化
void InitMatrix2（LMatrix＆ M）;//链式存储结构 对稀疏矩阵的初始化
void InputMatrix1（SMatrix＆ M,int m，int n)；//顺序存储结构 输入函数
void InputMatrix2(LMatrix＆ M，int m,int n);//链式存储结构 输入函数
void OutputMatrix1（SMatrix& M）；//顺序存储结构 输出函数
void OutputMatrix2(LMatrix＆ M）;//链式存储结构 输出函数
SMatrix Transpose(SMatrix& M）;//顺序存储结构 普通转置
SMatrix FastTranspose(SMatrix& M）；//顺序存储结构 快速转置
LMatrix Add（LMatrix& M1,LMatrix& M2）；//链式存储结构 加法
void menu（);// 菜单函数
int main（)
｛
SMatrix S1; //顺序结构声明S1
LMatrix L1，L2；//链式存储结构声明L1L2
LMatrix L;//用来存储L1 L2的和
int c,m=1;
while（m==1)
{
menu(）;
cout<〈"请输入你需要的操作"〈

case 4:
InitMatrix2(L1);
InputMatrix2(L1,10，10）;
OutputMatrix2（L1);
break;
case 5：
InitMatrix2(L2)；
cout〈<”输入要相加的矩阵”〈 6：
cout<〈”再见"<〈endl；
exit（1);
｝
｝
return 0;
｝
void InitMatrix1（SMatrix＆ M)//顺序存储结构 对稀疏矩阵的初始化为0
{
M.m=0; M.n=0； M。t=0；
}
void InitMatrix2(LMatrix＆ M)//链式存储结构 对稀疏矩阵的初始化为0
｛
int i;
M。m=0；M。n=0；M。t=0；
for（i=1;i<=MaxRows;i++)
M。vector[i］=NULL;
｝
void InputMatrix1(SMatrix＆ M，int m,int n)//顺序存储结构 输入函数
｛
M.m=m;M。n=n;
int row，col,val；//row和col用来分别存储元素的行号和列号，val用来存储元素值，t为非零元素个数
int k=0;
cout<〈"输入顺序三元组的行号列号以及该位置的元素值,以0 0 0为结束标志”〈〈endl；
cin>>row>>col〉〉val;
while(row！=0＆＆col!=0&&val！=0)
｛
k++；
M.sm[k].row=row;
M。sm［k］。col=col;
M.sm[k］.val=val；
cin>>row〉>col>>val;
}
M。t=k;
｝
void InputMatrix2（LMatrix＆ M,int m，int n）//链式存储结构 输入函数
｛
M。m=m;M。n=n;
int row，col，val;
int k=0;
cout〈〈”输入链式三元组中的行、列和对应值，以0 0 0为结束标志”〈〉col>>val;
while（row!=0&&col！=0&＆val!=0）
｛
k++;
TripleNode *p;
TripleNode *newptr;

newptr=new TripleNode；//建立新结点
newptr-〉row=row；
newptr—〉col=col；
newptr-〉val=val;
newptr—>next=NULL;
p=M.vector［row］；
if（p==NULL)
｛
M.vector[row]=newptr；
｝
else
｛
while(p—>next!=NULL）
p=p—〉next；
p->next=newptr；
}
cin〉>row〉〉col>〉val;
}

M。t=k；
}
void OutputMatrix1（SMatrix＆ M)//顺序存储结构 输出函数
{
int i=1；
cout〈<”矩阵为”〈〈endl；
for(i=1；i〈=M.t;i++）
{
cout〈〈M。sm[i]。row〈〈" ”;
cout〈〈M。sm［i］.col〈〈” ”;
cout<cout<<"矩阵为"<row<〈" "〈〈p—>col<<" ”〈val；
cout〈数和非零元素的个数
S。m=n; S.n=m; S.t=t;//分别置S的行数域、列数域和非零元素的个数域为n,m和t
if(t==0）//若是零矩阵则转换完毕返回
return S；
int k=1;//用k指示S.sm数组中待存元素的下标
for（int col=1;col〈=n； col++)
for（int i=1；i<=t；i++)
if(M.sm［i］。col==col）
｛
S.sm［k].row=col;
S.sm[k］。col=M.sm[i].row;
S.sm［k].val=M。sm[i]。val；

k++;
｝
return S;//返回转置矩阵S
｝
SMatrix FastTranspose（SMatrix＆ M）//快速转置，不必考虑大量的0元素
{
SMatrix S；
InitMatrix1(S);
int m，n，t;
m=M。m; n=M。n； t=M.t；//用m,n，t分别暂存M的行数、列数和非零元素的个数
S.m=n； S.n=m； S。t=t；//分别置S的行数域、列数域和非零元素的个数域为n，m和t
if(t==0)//若是零矩阵则转换完毕返回
return S;
int* num=new int［n+1］；//为num向量动态分配存储空间
int＊ pot=new int［n+1］；//为pot向量动态分配存储空间
int col,i;
for(col=1；col<=n;col++)//对num向量进行初始化，置每个分量为0
num[col]=0；
for（i=1;i<=t;i++)//第1遍扫描数组M。sm，统计出每一列非零元素的个数
｛
int j=M。sm[i］.col;
num[j］++;
}
pot［1］=1;
for（col=2;col<=n;col++)//计算每一列的第1个非零元素在S。sm中存储位置
pot［col]pot[col—1]+num[col-1];
for(i=1；i<=t；i++)//对M.sm进行第2遍扫描，把每个元素行、列值互换写入到S.sm的确定位置
｛
int j=M.sm[i]。col；
int k=pot［j]；
S。sm［k]。row=j；
S。sm[k］。col=M.sm［i］。row;
S.sm[k］。val=M。sm[i］.val；
pot［j］++；
}
delete[］ num;//删除动态分配的数组
delete［］ pot;
return S;
｝
LMatrix Add（LMatrix＆ M1,LMatrix＆ M2）//矩阵加法
{
LMatrix M;//暂存运算结果，以便返回
InitMatrix2（M)；
if(（M1.n!=M2。n)｜｜(M1。n!=M2.n)）
{
cout〈〈"两个矩阵规格不同”〈〈endl；
exit（1);
}
M.m=M1。m； M.n=M1.n；//把其中一个加数矩阵的尺寸赋给结果矩阵
if（(M1.t==0） && (M2.t==0））
return M;
//进行两矩阵相加产生和矩阵
int k=0；//用k统计结果矩阵中结点的个数
for（int i=1；i<=M.m；i++）//循环的次数相当于矩阵的行数
{
TripleNode ＊p1,＊p2，*p;
p1=M1.vector[i］；//p1指向M1矩阵中第i行单链表的待相加的结点
p2=M2.vector[i];//p2指向M2矩阵中第i行单链表的待相加的结点
p=M。vector[i］;//p指向M矩阵中第i行单链表的待相加的结点
while(（p1！=NULL) && （p2！=NULL）)
{
TripleNode＊ newptr=new TripleNode；
if(p1—〉colcol）//赋值新结点，p1指针后移
｛
＊newptr=*p1;
p1=p1-〉next;
}
else if(p1->col〉p2-〉col）//赋值新结点,p2指针后移
{
*newptr=＊p2；
p2=p2—〉next;
}
else//对具有相同列号的结点进行处理
if(p1—〉val+p2->val==0)//不建立新结点和链接
｛
p1=p1—>next；
p2=p2—>next；//p1和p2指针后移
continue;
｝
else //新结点值为两结点值之和，p1和p2指针后移
{
＊newptr=*p1；
newptr->val+=p2—>val;
p1=p1—>next;
p2=p2—〉next；
}
newptr—>next=NULL；//将新结点的指针域置空
//把新结点链接到结果矩阵的第i行单链表的表尾
if(p==NULL)
M.vector[i]=newptr;
else
p—>next=newptr；
p=newptr；
k++;
}
while（p1!=NULL）
{
TripleNode* newptr=new TripleNode；
*newptr=*p1；
newptr-〉next=NULL;
if(p==NULL）
M.vector[i］=newptr;
else
p-〉next=newptr；
p=newptr;
p1=p1-〉next;
k++;
}
//若p2不为空，则把剩余结点复制链接到结果矩阵中
while（p2！=NULL)
{
TripleNode＊ newptr=new TripleNode;
*newptr=*p2；
newptr->next=NULL；
if（p==NULL）
M.vector[i]=newptr；
else
p—〉next=newptr;
p=newptr；
p2=p2—〉next;
k++;
}
}
M.t=k;//置和矩阵中结点数
cout<〈"相加后得矩阵”〈〈endl；
return M;//返回和矩阵
}
void menu()// 菜单函数
｛
cout〈〈" 稀疏矩阵运算 "〈〈endl;
cout〈<” *＊＊＊＊＊**＊***＊＊*＊*＊＊***＊＊＊*****＊*＊*＊”<〈endl；
cout〈〈" ** 1。用三元组（顺序存储)建立矩阵 **”〈〈endl;
cout〈〈" ＊* 2.矩阵普通转置 ＊＊”<