当前位置：文档之家› 数据结构课程设计-稀疏矩阵运算器

数据结构课程设计-稀疏矩阵运算器

嘉应学院计算机学院

实验报告

课程名称：数据结构课程设计

开课学期：2017-2018学年第2学期

班级：

指导老师：

实验题目：稀疏矩阵运算器

学号：

姓名：

上机时间：

【实验目的】深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。

【需要分析】稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。

【软件平台】

Windows 2000，Visual C＋＋6.0或WINTC

【概要设计】

ADT Array {

数据对象:

D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}

数据关系:

R = { ROW, COL }

ROW = {| 0≤i≤b1-2, 0≤j≤b2-1}

COL = {| 0≤i≤b1-1, 0≤j≤b2-2}

基本操作：

CreateSMatrix(&M); //操作结果:创建稀疏矩阵M.

Print SMatrix(M);

//初始化条件: 稀疏矩阵M存在.

//操作结果:输出稀疏矩阵M.

AddSMatrix(M,N,&Q);

//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.

//操作结果:求稀疏矩阵的和Q=M+N.

SubSMatrix(M,N,&Q);

//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.

//操作结果:求稀疏矩阵的差Q=M-N.

MultSMatrix(M,N,&Q);

//初始化条件: 稀疏矩阵M的列数等于N的行数.

//操作结果:求稀疏矩阵的乘积Q=M*N.

} ADT Array

【主程序模块】：

void main()

{

初始化;

do{

接受命令;

处理命令;

}while(命令!=“退出”)；

}

【功能模块调用关系图】

【详细设计】

typedef struct{

int row; //行数

int col; //列数

int v; //非零元素值

}triplenode;

typedef struct{

triplenode data[maxsize+1]; //非零元三元组

int rowtab[maxrow+1]; //各行第一个非零元的位置表

int mu,nu,tu; //矩阵的行数、列数和非零元个数

}rtripletable;

void creat(rtripletable &A) //创建稀疏矩阵

void print(rtripletable A) //输出稀疏矩阵

int addsmatrix(rtripletable M, rtripletable N) //矩阵相加

int subsmatrix(rtripletable M, rtripletable N) //稀疏矩阵相减

void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) //稀疏矩阵相乘

【调试分析】

1、由于开始对顺序存储的知识还不熟识，在三元组的存储和运用会导致算法低效。

2、做到存储的时候，开始时不知道怎样存储三元组，和不知如何去运用它的行数，

列数，非零元素。

3、在使用选择和循环时，有时因为自己的粗心，把循环的条件弄错了。

4、做本程序用到了数组的知识，有时一有不懂的东西又只能打开书来看。

5、开始时没有把矩阵的加法和减法的情况考虑全面，导致输出的时候会出现简单的错

误。

【用户手册】

1、本程序的运行环境为Windows me下的Microsofe VC++ 6.0,执行文件为：

xishujuzhen.cpp。

2、进入演示程序后即显示文本方式的用户界面：

3、进入界面后，只要选择数字命令按“回车键”就行。

4、接受其他命令后即执行相应的操作和相应的结果。

完整代码如下：

#include

#define maxsize 100

#define maxrow 100

#define OK 1

#define ERROR -1

typedef struct{

int row; //行数

int col; //列数

int v; //非零元素值

}triplenode;

typedef struct{

triplenode data[maxsize+1]; //非零元三元组

int rowtab[maxrow+1];

//各行第一个非零元的位置表

int mu,nu,tu; //矩阵的行数、列数和非零元个数

}rtripletable;

void creat(rtripletable &A) //创建稀疏矩阵

{

int k=1,sum=1,loop,p,t;

int num[maxrow+1];

cout<<"请输入矩阵的行数和列数:"<

cout<<"行数:";cin>>A.mu;

cout<<"列数:";cin>>A.nu;

cout<<"非零元素个数:";cin>>A.tu;

cout<<"请按行,列和值的形式输入该矩阵的非零元.并以全零为结束标记!"<

{

cin>>A.data[loop].row>>A.data[loop].col>>A.data[loop].v;

//输入三元组的行数，列数和非零元素值

}

for(p=1;p<=A.mu;p++) num[p]=0;

//A三元组每一列的非零元素个数

for(t=1;t<=A.tu;t++) ++num[A.data[t].row];

//求A中每一列含非零元个数

A.rowtab[1]=1;

//求第p列中第一个非零元在A.data中的序号

for(t=2;t<=A.mu;t++) A.rowtab[t]=A.rowtab[t-1]+num[t-1]; return;

}

void print(rtripletable A) //输出稀疏矩阵

{

int result[maxrow+1][maxrow+1];

//定义一个二维数组

int loop1,loop2;

for(loop1=1;loop1<=A.mu;loop1++)

for(loop2=1;loop2<=A.nu;loop2++)

result[loop1][loop2]=0; //初始化为0

for(loop1=1;loop1<=A.tu;loop1++)

result[A.data[loop1].row][A.data[loop1].col]=A.data[loop1].v; for(loop1=1;loop1<=A.mu;loop1++)

{

cout<<"|";

for(loop2=1;loop2<=A.nu;loop2++)

cout<

//输出所做运算的结果

cout<<"|"<

}

int addsmatrix(rtripletable M, rtripletable N)

//矩阵相加

{

if(M.mu!=N.mu) //行数相等才能相加

cout<<"出错";

rtripletable Q;Q.mu=M.mu;Q.nu=N.nu;

int p,q,k;

p=1;q=1;k=1;

while(p<=M.tu&&q<=N.tu) //两个稀疏矩阵存在

{

if(M.data[p].row==N.data[q].row)

//两个稀疏矩阵的行数相等

{

if(M.data[p].col==N.data[q].col)

//两个稀疏矩阵的列数相等

{

if(M.data[p].v+N.data[q].v!=0)

//两个稀疏矩阵相加的结果不为0

{

Q.data[k].row=M.data[p].row;

Q.data[k].col=M.data[p].col;

Q.data[k].v=M.data[p].v+N.data[q].v;++k;

}

++q;++p;

}

else if(M.data[p].col

//第一个稀疏矩阵列数小于第二个稀疏矩阵列数{

Q.data[k]=M.data[p];

//把M中的所有信息都赋给Q

++p;++k;

}

else

//第一个稀疏矩阵列数大于第二个稀疏矩阵的列数{

Q.data[k]=N.data[q];++q;++k;

}

else if(M.data[p].row

//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{

Q.data[k]=M.data[p];++p;++k;

}

else

//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{

Q.data[k]=N.data[q];++q;++k;

}

while(p<=M.tu) //只有M并且符合条件

{

Q.data[k]=M.data[p];++p;++k;

}

while(q<=N.tu) //只有N并且符合条件

{

Q.data[k]=N.data[q];

++q;++k;

}

Q.tu=k-1;

cout<<"加法结果为:"<

print(Q); //调用print()

return OK;

}

int subsmatrix(rtripletable M, rtripletable N)

//稀疏矩阵相减

{

if(M.mu!=N.mu) //行数相等才能相加

cout<<"出错";

rtripletable Q;

Q.mu=M.mu;

Q.nu=N.nu;

int p,q,k;

p=1;q=1;k=1;

while(p<=M.tu&&q<=N.tu) //两个稀疏矩阵存在{

if(M.data[p].row==N.data[q].row)

//两个稀疏矩阵的行数相等

{

if(M.data[p].col==N.data[q].col)

//两个稀疏矩阵的列数相等

{

if(M.data[p].v-N.data[q].v!=0)

//两个稀疏矩阵相减的结果不为0

{Q.data[k].row=M.data[p].row;

Q.data[k].col=M.data[p].col;

Q.data[k].v=M.data[p].v-N.data[q].v;

++k;

}

++q;++p;

}

if(M.data[p].col

//第一个稀疏矩阵列数小于第二个稀疏矩阵的列数{

Q.data[k]=M.data[p];

++p;++k;

}

if(M.data[p].col>N.data[q].col)

//第一个稀疏矩阵列数大于第二个稀疏矩阵的列{

Q.data[k].row=N.data[q].row;

Q.data[k].col=N.data[q].col;

Q.data[k].v=-N.data[q].v;

++q;++k;

}

if(M.data[p].row

//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数

{

Q.data[k]=M.data[p];

++p;++k;

}

if(M.data[p].row>N.data[q].row)

//第一个稀疏矩阵行列数大于第二个稀疏矩阵行数

{

Q.data[k].row=N.data[q].row;

Q.data[k].col=N.data[q].col;

Q.data[k].v=-N.data[q].v;++q;++k;

}

while(p<=M.tu) //只有M并且符合条件

{

Q.data[k]=M.data[p];++p;++k;

}

while(q<=N.tu) //只有N并且符合条件

{

Q.data[k].row=N.data[q].row;

Q.data[k].col=N.data[q].col;

Q.data[k].v=-N.data[q].v;

++q;++k;

}

Q.tu=k-1;

cout<<"减法结果为:"<

print(Q); //调用print()

return OK;

}

void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) //稀疏矩阵相乘{

int arow,brow;

int p,q,tp,t;

int ccol;

int ctemp[maxrow+1]; //定义累加器

if(M.nu!=N.mu)return;

Q.mu=M.mu;Q.nu=N.nu;Q.tu=0; //Q初始化

if(M.tu*N.tu!=0){ //Q是非零矩阵

for(arow=1;arow<=M.mu;arow++)

//处理M的每一行

{

for(p=1;p<=Q.nu;p++) //处理M的每一列

ctemp[p]=0; //当前行各元素累加器清零

Q.rowtab[arow]=Q.tu+1;

if(arow

else tp=M.tu+1;

for(p=M.rowtab[arow];p

//对当前行中每一个非零元

{

brow=M.data[p].col; //找到对应元N中的行号

if(brow

else t=N.tu+1;

for(q=N.rowtab[brow];q

{

ccol=N.data[q].col; //乘积元素在Q中列数

ctemp[ccol]+=M.data[p].v*N.data[q].v;

}

} //求得Q中第crow(=arow)行的非零元

for(ccol=1;ccol<=Q.nu;ccol++)

//压缩存储该行非零元

{

if(ctemp[ccol])

{

if(++Q.tu>maxsize)return ;

Q.data[Q.tu].row=arow; //行数

Q.data[Q.tu].col=ccol; //列数

Q.data[Q.tu].v=ctemp[ccol];

//累加非零元素值

}

cout<<"乘法结果为:"<

print(Q); //调用print()

}

void main()

{

char choice;

rtripletable A,B,Q;

cout<<"-------------------------------------------------- \n"; cout<<"|*****欢迎使用稀疏矩阵运算器******| \n"; cout<<"|=============================|\n";

cout<<"\n | F、退出本系统| \n";

cout<<"\n|-----------------------------------------------| \n";

cout<<"请选择所需要的操作功能(A，B，C，D，E，F):"; do{

cin>>choice;

switch(choice){

case'A':creat(A);break;

case'B':creat(B);break;

case'C':addsmatrix(A,B);break;

case'D':subsmatrix(A,B);break;

case'E':multsmatrix(A,B,Q);break;

case'F':exit(0);

}cout<<"请选择所需要的操作功能(A，B，C，D，E，F):"; }while(1);

}

计算器课程设计报告

课设报告福建工程学院软件学院题目：汇编计算器班级： 1301 姓名学号：指导老师：日期：

目录 1、设计目的 (3) 2、概要设计 (3) 2.1 系统总体分析 (3) 2.2 主模块框图及说明 (3) 3、详细设计 (4) 3.1 主模块及子模块概述 (4) 3.2各模块详运算 (4) 4、程序调试 (7) 4.1 运行界面分析 (7) 算法分析 (7) 4.2 调试过程与分析 (9) 5、心得体会 (11) 5.1 设计体会 (11) 5.2 系统改进 (11) 附录： (11)

1、设计目的本课程设计是一次程序设计方法及技能的基本训练，通过实际程序的开发及调试，巩固课堂上学到的关于程序设计的基本知识和基本方法，进一步熟悉汇编语言的结构特点和使用，达到能独立阅读、设计编写和调试具有一定规模的汇编程序的水平。 2、概要设计用8086汇编语言编写一个能实现四则混合运算、带括号功能的整数计算器程序。程序能实现键盘十进制运算表达式的输入和显示（例如输入：“1+2*(3-4)”），按“=”后输出十进制表示的运算结果。 2.1 系统总体分析在8086的操作环境下，该计算器分成输入，数据存储，运算功能，输出几个大模块，实现了使用者使用该计算器时输入一个算式，能让系统进行计算。此计算器的实现功能是基本的数学的四则运算，结果范围在0~65535。 2.2 主模块框图及说明此流程图简要的表现出了所要实现的功能以及一些功能的大概算法，同时也是我编写的一个总体的框架。程序流程图说明：通过流程图，可以看出程序运行时，首先输出提示语气，当用户输入后，程序根据所输入内容进行判断，通过判断的结果来决定调用哪个功能模块，首要先要要判断的是否为0-9，“+”“-”“*”“/”这些字符，若不是就会报错，实则根据运算符号调用其功能模块完成运算。最后将运算的结果显示在主频幕上，返回主程序，使用户可以重新输入。

C++课程设计报告--小型特殊计算器

课程设计报告课程：面向对象程序设计学号：姓名：班级：教师：

课程设计名称：小型特殊计算器 1.设计内容：实现一个特殊的计算器，可以实现复数、有理数、矩阵和集合的特殊计算。程序可以实现复数、有理数的加、减、乘、除，可以实现矩阵的加法、减法和乘法运算，也可以实现集合的求交集、并集、子集的运算。 2.设计目的与要求： 2.1设计目的达到熟练掌握C++语言的基本知识和技能；基本掌握面向对象程序设计的基本思路和方法；能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。 2.2设计要求要求利用面向对象的方法以及C++的编程思想来完成系统的设计；要求在设计的过程中，建立清晰的类层次；在系统的设计中，至少要用到面向对象的一种机制。 3.系统分析与设计 3.1主要知识点运算符重载增加了C++语言的可扩充性。运算符的重载实际上就是一种函数调用的形式，可以用成员函数重载运算符，就是将运算符重载定义为一个类的成员函数的形式；也可以用友元函数重载。用友元重载运算符的友元函数是独立于类以外的一般函数。 3.2关键技术程序中每一种数据类型用一个类来实现，共设计了4个类。复数类complex，矩阵类matrix，有理数类rational以及集合类set。每一种类都定义了相应的运算符重载函数。具体定义如下所示：（1）类complex 类complex中，成员变量image表示虚部，real表示实部。成员函数print()用来显示数据。运算符重载函数都是用友元函数来实现的。分别重载+、-、*、/运算符。（2）类matrix 类matrix中，成员变量elems用来存放矩阵的所有元素，rows表示矩阵的行，cols表示矩阵的列。成员函数SetElems()用来给矩阵中的每一个元素赋值，Disp()用来显示矩阵中的所有元素。其它友元函数分别重载+、-、*、/运算符。（3）类rational 类rational中，有两个成员变量：denominator用来表示有理数的分母，numerator表示有理数的分子。有理数成员函数print()用来显示有理数，optimization()用来优化有理数函数。友元函数real()用来将有理数转换为实数，其它友元函数分别重载+、-、*、/运算符。（4）类set

稀疏矩阵的计算概论

#include #include #include typedef int ElemType;// 稀疏矩阵的十字链表存储表示 typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值 struct OLNode *right,*down; // 该非零元所在行表和列表的后继链域}OLNode, *OLink; typedef struct// 行和列链表头指针向量基址,由CreatSMatrix_OL()分配{ OLink *rhead, *chead; int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元个数 }CrossList; // 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) int InitSMatrix(CrossList *M) { (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; } // 销毁稀疏矩阵M int DestroySMatrix(CrossList *M) { int i; OLNode *p,*q; for(i=1;i<=(*M).mu;i++) // 按行释放结点 { p=*((*M).rhead+i); while(p) { q=p; p=p->right; free(q); } } free((*M).rhead); free((*M).chead); (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; }

实现稀疏矩阵(采用三元组表示)的基本运算实验报告

实现稀疏矩阵（采用三元组表示）的基本运算实验报告一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；（3）输出a + b 的三元组；（4）输出 a * b 的三元组；三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={ | 1≤i≤m , 1≤j ≤n-1} Col ={| 1≤i≤m-1,1≤j ≤n} 基本操作:

CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在