稀疏矩阵转换
#include
#include
#define MAXSIZE 1000 /*非零元素的个数最多为1000*/
/*稀疏矩阵三元组表的类型定义*/
typedef struct
{
int row,col; /*该非零元素的行下标和列下标*/
int e; /*该非零元素的值*/
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; /* 非零元素的三元组表。data[0]未用*/
int m,n,len; /*矩阵的行数、列数和非零元素的个数*/
}TSMatrix;
/*"列序"递增转置法*/
void TransposeTSMatrix(TSMatrix A,TSMatrix *B)
{ /*把矩阵A转置到B所指向的矩阵中去。矩阵用三元组表表示*/
int i,j,k;
B->m=A.n;
B->n=A.m;
B->len=A.len;
if(B->len>0)
{
j=1; /*j为辅助计数器，记录转置后的三元组在三元组表B中的下标值*/
for(k=1; k<=A.n; k++) /*扫描三元组表A共k次，每次寻找列值为k的三元组进行转置*/
for(i=1; i<=A.len; i++)
if(A.data[i].col==k)
{
B->data[j].row=A.data[i].col;/*从头至尾扫描三元组表A,寻找col值为k的三元组进行转置*/
B->data[j].col=A.data[i].row;
B->data[j].e=A.data[i].e;
j++; /*计数器j自加，指向下一个存放转置后三元组的下标*/ }/*内循环中if的结束*/
}/* if(B->len>0)的结束*/
}/* end of TransposeTSMatrix */
/*"按位快速转置"法*/
void FastTransposeTSMatrix(TSMatrix A,TSMatrix *B)
{
/*基于矩阵的三元组表示，采用"按位快速转置"法，将矩阵A转置为矩阵B*/
int col,t,p,q;
int num[MAXSIZE], position[MAXSIZE];
B->len=A.len;
B->n=A.m;
B->m=A.n;
if(B->len)
{
for(col=1;col<=A.n;col++)
num[col]=0;
for(t=1;t<=A.len;t++)
num[A.data[t].col]++; /*计算每一列的非零元素的个数*/
position[1]=1;
for(col=2;col<=A.n;col++) /*求col列中第一个非零元素在B.data[ ]中的正确位置*/
position[col]=position[col-1]+num[col-1];
for(p=1;p<=A.len;p++)/*将被转置矩阵的三元组表A从头至尾扫描一次，实现矩阵转置*/
{
col=A.data[p].col;
q=position[col];
B->data[q].row=A.data[p].col;
B->data[q].col=A.data[p].row;
B->data[q].e=A.data[p].e;
position[col]++;/* position[col]加1，指向下一个列号为col的非零元素在三元组表B中的下标值*/
}/*end of for*/
}
}
void main()
{
int i;
int a[8]={1,1,3,3,4,5,6,6};
int b[8]={2,3,1,6,3,2,1,4};
int c[8]={12,9,-3,14,24,18,15,-7};
TSMatrix A;
TSMatrix *B;
A.n=8;
A.m=1;
A.len=8;
B=(TSMatrix *)malloc(sizeof(TSMatrix));
for(i=0;i<8;i++)
{
A.data[i+1].row=a[i];
A.data[i+1].col=b[i];
A.data[i+1].e=c[i];
}
TransposeTSMatrix(A,B);
for(i=1;i<=8;i++)
{
printf("%3d",B->data[i].row);
}
printf("\n");
for(i=1;i<=8;i++)
{
printf("%3d",B->data[i].col);
}
printf("\n");
for(i=1;i<=8;i++)
{
printf("%3d",B->data[i].e);
}
printf("\n");
getchar();
}
折半查找法
#include
#include
#define LIST_SIZE 20
typedef char KeyType;
typedef int OtherType;
typedef struct
{
KeyType key;
OtherType other_data;
}RecordType;
typedef struct
{
RecordType r[LIST_SIZE+1]; /* r[0]为工作单元*/ int length;
}RecordList;
void createlist(RecordList *l)
{
int i;
int len;
KeyType ch;
printf("请输入线性表的长度:");
scanf("%d",&len);
l->length = len;
for(i=1; i<=len; i++)
{
printf("请输入线性表的第%d个元素:",i);
fflush(stdin);
scanf("%c",&ch);
l->r[i].key = ch;
}
}
int BinSrch(RecordList l, KeyType k)
/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/
{
int low,high,mid;
low=1;
high=l.length;/*置区间初值*/
while( low <= high)
{
mid=(low+high) / 2;
if (k==l.r[mid]. key)
return (mid);/*找到待查元素*/
else
if (k high=mid-1;/*未找到，则继续在前半区间进行查找*/ else low=mid+1;/*继续在后半区间进行查找*/ } return (0); } void main() { RecordList l; int locate; KeyType k; createlist(&l); printf("请输入要查找的元素:"); fflush(stdin); scanf("%c",&k); locate = BinSrch(l,k); if(locate == 0) printf("未找到!\n"); else printf("该元素在表中的位置为%d\n",locate); } 实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组a 和b；（上机实验指导P92 ）（2）输出a 转置矩阵的三元组； （3）输出a + b 的三元组； （4）输出a * b 的三元组； 三实验内容: 3.1 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数 } 数据关系 : R={ Row , Col } Row ={ 操作结果：创建稀疏矩阵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已经存在 操作结果：求矩阵的积Q=M*N }ADT SparseMatrix 3.2存储结构的定义 #define N 4 typedef int ElemType; #define MaxSize 100 //矩阵中非零元素最多个数typedef struct { int r; //行号 int c; //列号 ElemType d; //元素值 } TupNode; //三元组定义 typedef struct { int rows; //行数值 int cols; //列数值 int nums; //非零元素个数 矩 阵 分 析 实 验 报 告 学院：电气学院 专业：控制工程 姓名：XXXXXXXX 学号：211208010001 矩阵分析实验报告 实验题目 利用幂法求矩阵的谱半径 实验目的与要求 1、 熟悉matlab 矩阵实验室的功能和作用； 2、 利用幂法求矩阵的谱半径； 3、 会用matlab 对矩阵分析运算。 实验原理 理念 谱半径定义：设n n A C ?∈，1λ，2λ，3λ， ，j λ， n λ是A 的n 个特征值，称 ()max ||j j A ρλ= 为关于A 的谱半径。 关于矩阵的谱半径有如下结论： 设n n A C ?∈，则 （1）[]()()k k A A ρρ=； （2）2 2()()()H H A A AA A ρρ==。 由于谱半径就是矩阵的主特征值，所以实验换为求矩阵的主特征值。 算法介绍 定义：如果1λ是矩阵A 的特征值，并且其绝对值比A 的任何其他特征值的绝对值大，则称它为主特征值。相应于主特征值的特征向量1V 称为主特征向量。 定义：如果特征向量中最大值的绝对值等于单位值（例如最大绝对值为1），则称其为是归一化的。 通过形成新的向量' 12=c n V （1/）[v v v ]，其中c=v 且1max {},j i n i ≤≤=v v 可将特 征向量 '12n [v v v ]进行归一化。 设矩阵A 有一主特征值λ，而且对应于λ有唯一的归一化特征向量V 。通过下面这个称为幂法（power method ）的迭代过程可求出特征对λ，V ，从下列向量开始： []' 0=111X （1） 用下面递归公式递归地生成序列{}k X ： k k Y AX = k+11 1 k k X Y c += （2） 其中1k c +是k Y 绝对值最大的分量。序列{}k X 和{}k c 将分别收敛到V 和λ： 1lim k X V =和lim k c λ= （3） 注：如果0X 是一个特征向量且0X V ≠，则必须选择其他的初始向量。 幂法定理：设n ×n 矩阵A 有n 个不同的特征值λ1，λ2，···，，λn ，而且它们按绝对 值大小排列，即： 123n λλλλ≥≥≥???≥ (4) 如果选择适当的X 0，则通过下列递推公式可生成序列{[() ()( ) ]}12k k k k n X x x x '=???和 {}k c ： k k Y AX = (5) 和： 11 1k k k X Y c ++= (6) 其中： () 1k k j c x +=且{} ()()1max k k j i i n x x ≤≤= (7) 这两个序列分别收敛到特征向量V 1和特征值λ1。即： 1lim k k X V →∞ =和1lim k k c λ→∞ = (8) 算法收敛性证明 证明：由于A 有n 个特征值，所以有对应的特征向量V j ，j=1，2，···n 。而且它们是 课程设计 所抽题目：采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。 要求：要检查有关运算的条件，并对错误的条件产生 报警。 问题分析和建立模型：本题目主要是运用所学知识，用十字链表的方法去表示稀疏矩阵，并使之可以在两矩阵间进行相加。而后，若有错误，则对错误进行警报。 框架搭建： 1选择File|New菜单项，弹出New对话框，选择Files标签，选中C++ Source File项，在File编辑器中输入项目名称“十字链表表示稀疏矩阵实现加法”，在Location编辑框中输入项目所在目录，按下OK 按钮即可。 2在操作界面中输入，程序代码。 （1）结构体和共用体的定义 #include struct lnode *next; datatype v; }uval; }link; int flag=0; 建立十字链表头结点 head=(link *)malloc(sizeof(link)); 建立头结点循环链表 for(i=1;i<=s;i++) （3）插入结点函数 p=(link *)malloc(sizeof(link)); p->i=0;p->j=0; p->rptr=p;p->cptr=p; cp[i]=p; cp[i-1]->uval.next=p; } cp[s]->uval.next=head; for(k=1;k<=t;k++) { printf("\t 第%d个元素(行号i 列号j 值v，数字间用空格分隔):",k); scanf("%d%d%d",&i,&j,&v); p=(link *)malloc(sizeof(link)); p->i=i;p->j=j;p->uval.v=v; q=cp[i]; while((q->rptr!=cp[i])&&(q->rptr->j 一、课题名称 Malab矩阵特征值 二、目的和意义 1、求矩阵的部分特征值问题具有重要实际意义，如求矩阵谱半径()Aρ=maxλ，稳定性问题往往归于求矩阵按模最小特征值； 2、进一步掌握冪法、反冪法及原点平移加速法的程序设计技巧； 3、问题中的题（5），反应了利用原点平移的反冪法可求矩阵的任何特征值及其特征向量。 三、实验要求 1、掌握冪法或反冪法求矩阵部分特征值的算法与程序设计； 2、会用原点平移法改进算法，加速收敛；对矩阵B=A-PI取不同的P值，试求其效果； 3、试取不同的初始向量，观察对结果的影响；()0υ 4、对矩阵特征值的其它分布，如如何计算。 四、问题描述 五、实验程序设计 幂法 function [lamdba,v]=power_menthod(a,x,epsilon,maxl) k=0; y=a*x; while(k 一、实验内容和要求 1、稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相 加得到矩阵C的算法。 （1）从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。 （2）设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。 （3）设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。 （4）输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。 二、实验过程及结果 一、需求分析 1、将随机生成的数定义为int型（为方便起见设定范围为-20至20（不含0），可 修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。 2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列 排列形式输出）。 3、程序能实现的功能包括： ①随机产生稀疏矩阵；②输出阵列形式的矩阵；③输出三元组顺序 表；④将矩阵快速转置；⑤将两个稀疏矩阵相加生成新的矩阵。 二、概要设计 1、稀疏矩阵的抽象数据类型定义： ADT TSMatrix{ 数据对象：D={ aij|i=1,2,…,m,j=1,2,…,n; Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}数据关系：R={Row，Col} Row={ 南京林业大学 实验报告 基于AT89C51 单片机4x4矩阵键盘接口电路设计 课程机电一体化设计基础 院系机械电子工程学院 班级 学号 姓名 指导老师杨雨图 2013年9月26日 一、实验目的 1、掌握键盘接口的基本特点，了解独立键盘和矩 阵键盘的应用方法。 2、掌握键盘接口的硬件设计方法，软件程序设计 和贴士排错能力。 3、掌握利用Keil51软件对程序进行编译。 4、用Proteus软件绘制“矩阵键盘扫描”电路，并用测试程序进行仿真。 5、会根据实际功能，正确选择单片机功能接线，编制正确程序。对实验结果 能做出分析和解释，能写出符合规格的实验报告。 二、实验要求 通过实训，学生应达到以下几方面的要求： 素质要求 1.以积极认真的态度对待本次实训，遵章守纪、团结协作。 2.善于发现数字电路中存在的问题、分析问题、解决问题，努力培养独立 工作能力。 能力要求 1.模拟电路的理论知识 2.脉冲与数字电路的理念知识 3.通过模拟、数字电路实验有一定的动手能力 4.能熟练的编写8951单片机汇编程序 5.能够熟练的运用仿真软件进行仿真 三、实验工具 1、软件：Proteus软件、keil51。 2、硬件：PC机，串口线，并口线，单片机开发板 四、实验内容 1、掌握并理解“矩阵键盘扫描”的原理及制作，了解各元器件的参数及格 元器件的作用。 2、用keil51测试软件编写AT89C51单片机汇编程序 3、用Proteus软件绘制“矩阵键盘扫描”电路原理图。 4、运用仿真软件对电路进行仿真。 五．实验基本步骤 1、用Proteus绘制“矩阵键盘扫描”电路原理图。 2、编写程序使数码管显示当前闭合按键的键值。 3、利用Proteus软件的仿真功能对其进行仿真测试，观察数码管的显示状 态和按键开关的对应关系。 4、用keil51软件编写程序，并生成HEX文件。 5、根据绘制“矩阵键盘扫描”电路原理图，搭建相关硬件电路。 6、用通用编程器或ISP下载HEX程序到MCU。 7、检查验证结果。 六、实验具体内容 使用单片机的P1口与矩阵式键盘连接时，可以将P1口低4位的4条端口线定义为行线，P1口高4位的4条端口线定义为列线，形成4*4键盘，可以配置16个按键，将单片机P2口与七段数码管连接，当按下矩阵键盘任意键时，数码管显示该键所在的键号。 1、电路图 专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主 控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输 目录 前言 (1) 正文 (1) 1.课程设计的目的和任务 (1) 2.课程设计报告的要求 (1) 3.课程设计的内容 (2) 4.稀疏矩阵的十字链表存储 (2) 5.稀疏矩阵的加法思想 (4) 6.代码实现 (5) 7.算法实现 (5) 结论 (8) 参考文献 (9) 附录 (10) 前言 采用三元组顺序表存储稀疏矩阵，对于矩阵的加法、乘法等操作，非零元素的插入和删除将会产生大量的数据移动，这时顺序存储方法就十分不便。稀疏矩阵的链接存储结构称为十字链表，它具备链接存储的特点，因此，在非零元素的个数及位置都会发生变化的情况下，采用链式存储结构表示三元组的线性更为恰当。 正文 1.课程设计的目的和任务 (1) 使我我们进一步理解和掌握所学的程序的基本结构。 (2) 使我们初步掌握软件开发过程的各个方法和技能。 (3) 使我们参考有关资料，了解更多的程序设计知识。 (4) 使我们能进行一般软件开发，培养我们的能力并提高我们的知识。 2.课程设计报告的要求 (1)课程设计目的和任务，为了达到什么要求 (2)课程设计报告要求 (3)课程设计的内容，都包含了什么东西 (4)稀疏矩阵和十字链表的基本概念，稀疏矩阵是怎么用十字链表存储 (5)十字链表矩阵的加法 (6)代码实现 (7)算法检测 3.课程设计的内容 (1)根据所学知识并自主查找相关资料 (2)进行算法设计与分析 (3)代码实现，组建并运行结果查看是否正确 (4)书写课程设计说明书 4.稀疏矩阵的十字链表存储 稀疏矩阵是零元素居多的矩阵，对于稀疏矩阵，人们无法给出确切的概念，只要非零元素的个数远远小于矩阵元素的总数，就可认为该矩阵是稀疏的。 十字链表有一个头指针hm ，它指向的结点有五个域，如图1所示。row 域存放总行数m ，col 域存放总列数n ，down 和right 两个指针域空闲不用，next 指针指向第一个行列表头结点。 c o l r o w 图1 总表点结点 有S 个行列表头结点h[1]，h[2]，......h[s]。结点结构与总表头结点相同。Row 和col 域置0，next 指向下一行列表头结点，right 指向本行第一个非零元素结点，down 指向本列第一个非零元素结点如图2所示。当最后一个行列表头结点的next 域指向总表头结点的hm 时，就形成循环链表，见图4的第一行。 教学单位计算机科学与技术 学生学号 5 数据结构 课程设计报告书 题目稀疏矩阵运算器 学生豹 专业名称软件工程 指导教师志敏 实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。 需要分析：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。 软件平台：Windows 2000，Visual C＋＋ 6.0或WINTC 概要设计：ADT Array { 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = { 北京科技大学计算机与通信工程学院 实验报告 实验名称： 学生姓名： 专业： 班级： 学号： 指导教师： 实验成绩：________________________________ 实验地点： 实验时间：2015年05月 一、实验目的与实验要求 1、实验目的 1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；2观察并行算法不同进程数运行结果，分析得出结论； 2、实验要求 1编写矩阵乘法的串行程序，多次运行得到结果汇总； 2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。 二、实验设备（环境）及要求 《VS2013》C++语言 MPICH2 三、实验内容与步骤 实验1，矩阵乘法的串行实验 （1）实验内容 编写串行程序，运行汇总结果。 （2）主要步骤 按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。 实验2矩阵乘法的并行化实验 3个总进程 5个总进程 7个总进程 9个进程 16个进程 四：实验结果与分析（一）矩阵乘法并行化 矩阵并行化算法分析： 并行策略：1间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程1：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此O(n)=(n); 2间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程3：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此T(n)=O(n); 课程设计 课程：数据结构 题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优 班级： 姓名： 学号： 设计时间：2010年1月17日——2010年5月XX日 成绩： 指导教师：楼建华 一、题目 二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆 三、详细设计 （1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1 稀疏矩阵的相加 题目: 稀疏矩阵的相加 1、问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 2、设计 2.1. 存储结构设计 稀疏矩阵的行逻辑连接的顺序表存储结构表示如下: #define MAXSIZE 20 /* 非零元个数最大值*/ 最大值*/#defi ne MAXRC 10 /* 各行第一个非零元总数 typedef struct{ , 列下标*/ int i,j; /* 行下标 int e; /* 非零元值*/ }Triple; typedef struct { /* 行逻辑链接的顺序表*/ Triple data[MAXSIZE+1]; /* 非零元三元组表,data[0] 未用*/ int rpos[MAXRC+1]; /* 各行第一个非零元的位置表*/ int mu,nu,tu; /* 阵的行数、列数和非零元个数*/ }TSMatrix; 2.2. 主要算法设计 对 2 个矩阵相加的算法如下: bool AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) /* 求稀疏矩阵的和Q=M+N*/ { int p=1,q=1,k=1; if(M.tu==0&&N.tu==0) /* 为空矩阵的情况*/ { cout<<" 该矩阵为空矩阵"< 专业课程设计I报告（ 2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始 实现稀疏矩阵(采用三元组表示)的基本运算实验报告 ————————————————————————————————作者：————————————————————————————————日期： 2 实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组； （3）输出a + b 的三元组； （4）输出 a * b 的三元组； 三实验内容: 3.1 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数 } 数据关系 : R={ Row , Col } Row ={ 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：软件12K1 学生姓名：吴旭 学号：121909020124 成绩： 指导老师：刘老师实验日期：2014.11.14 一、实验内容 矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。 二、主要思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号 的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计 算结果相乘得到A[1:n]。 2、建立递归关系 设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。 当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。 当i 课程设计任务书 学生姓名：专业班级： 指导教师：夏红霞工作单位：计算机科学与技术学院题目: 稀疏矩阵乘法的运算 课程设计要求: 1、熟练掌握基本的数据结构； 2、熟练掌握各种算法； 3、运用高级语言编写质量高、风格好的应用程序。 课程设计任务: 1、系统应具备的功能： （1）设计稀疏矩阵的存储结构 （2）建立稀疏矩阵 （3）实现稀疏矩阵的乘法 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排：2010年7月5日－9日（第19周） 7月5日查阅资料 7月6日系统设计，数据结构设计，算法设计 7月7日 -8日编程并上机调试 7月9日撰写报告 7月10日验收程序，提交设计报告书。 指导教师签名： 2010年7月4日系主任（或责任教师）签名： 2010年7月4日 目录 1.摘要 (1) 2.关键字 (1) 3.引言 (1) 4. 问题描述 (1) 5. 系统设计 (1) 6. 数据结构 (3) 7. 算法描述 (3) 8. 测试结果与分析 (4) 9. 源代码 (12) 10. 总结 (29) 11.参考文献 (29) 稀疏矩阵乘法的运算 1.摘要：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。因此需要采取其他的方法来解决这个问题，由于0在乘法中其结果总是0，所以可以考虑采用三元组的方式去存储稀疏矩阵中的非零元，这样在计算过程中不仅需要的内存空间减少了，而且运算的速率也提高了。 2.关键字：稀疏矩阵乘法二维矩阵算法复杂度 3.引言：随着科学技术的发展，人们对矩阵的运算的几率越来越大，特别是高新科技研究中对矩阵的运算更是常见。但是如何高效的并占内存少的进行矩阵运算就是一个急需解决的问题。本文主要对稀疏矩阵的存储以及稀疏矩阵的乘法运算进行了研究和探讨。 4.问题描述：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。为了减少空间和时间复杂度，可以根据给定的二维数组的数据设计稀疏矩阵的存储结构，然后根据设计的稀疏矩阵存储结构建立一个稀疏矩阵，最后获得两个二维数组得到他们各自的稀疏矩阵，计算这两个稀疏矩阵的乘积。 5.系统设计： 5.1 设计目标：通过一定的数据结构，存储含有少量数据的矩阵，把他们存入一个稀疏矩阵中，然后实现稀疏矩阵的乘法运算。[基本要求]设计稀疏矩阵的存储结构；建立稀疏矩阵；实现稀疏矩阵的乘法 MATLAB 程序设计实验 班级：电信1104班 姓名：龙刚 学号：1404110427 实验内容：了解MA TLAB 基本使用方法和矩阵的操作 一．实验目的 1.了解MA TLAB 的基本使用方法。 2.掌握MA TLAB 数据对象的特点和运算规则。 3.掌握MA TLAB 中建立矩阵的方法和矩阵的处理方法。 二．实验内容 1. 浏览MATLAB 的start 菜单，了解所安装的模块和功能。 2. 建立自己的工作目录，使用MA TLAB 将其设置为当前工作目录。使用path 命令和工作区浏览两种方法。 3. 使用Help 帮助功能，查询inv 、plot 、max 、round 等函数的用法和功能。使用help 命令和help 菜单。 4. 建立一组变量，如x=0:pi/10:2*pi ，y=sin(x)，在命令窗口显示这些变量；在变量窗口打开这些变量，观察其值并使用绘图菜单绘制y 。 5. 分多行输入一个MA TLAB 命令。 6. 求表达式的值 ()6210.3424510w -=+? ()22tan b c a e abc x b c a ππ++ -+=++，a=3.5，b=5，c=-9.8 ()220.5ln 1t z e t t =++，21350.65i t -??=??-?? 7.已知 1540783617A --????=??????，831253320B -????=????-?? 求 A+6B ，A 2-B+I A*B ，A.*B ，B*A A/B ，B/A [A,B]，[A([1,3], :); B^2] 8.已知 23100.7780414565532503269.5454 3.14A -????-??=????-?? 输出A 在[10,25]范围内的全部元素 取出A 的前三行构成矩阵B ，前两列构成矩阵C ，右下角3x2子矩阵构成矩阵D ，B 与C 的乘积构成矩阵E 分别求表达式E 稀疏矩阵的乘法运算 程序代码： #include void insert_row(Crosslist &M,OLnode *t,int row) { OLnode *p; int col=t->j; if(M.rhead[row]==NULL||M.rhead[row]->j>col) { t->right=M.rhead[row]; M.rhead[row]=t; } else { for(p=M.rhead[row];p->right&&p->right->j 《数据结构课程设计》实验报告 一、实验目的： 理解稀疏矩阵的加法运算，掌握稀疏矩阵的存储方法，即顺序存储的方式，利用顺序存储的特点——每一个元素都有一个直接前驱和一个直接后继，完成相关的操作。 二、内容与设计思想： 1、设计思想 1）主界面的设计 定义两个矩阵a= 0 0 3 0 0 0 0 0 b= 0 2 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 定义两个数组A和B，用于存储矩阵a和矩阵b的值；定义一个数组C，用于存放数组A 和数组B相加后的结果。 2）实现方式 稀疏矩阵的存储比较浪费空间，所以我们可以定义两个数组A、B，采用压缩存储的方式来对上面的两个矩阵进行存储。具体的方法是，将非零元素的值和它所在的行号、列号作为一个结点存放在一起，这就唯一确定一个非零元素的三元组（i、j、v）。将表示稀疏矩阵的非零元素的三元组按行优先的顺序排列，则得到一个其结点均为三元组的线性表。即：以一维数组顺序存放非零元素的行号、列号和数值，行号-1作为结束标志。例如，上面的矩阵a，利用数组A存储后内容为： A[0]=0，A[1]=2, A[2]=3, A[3]=1, A[4]=6, A[5]=5, A[6]=3, A[7]=4, A[8]=7, A[9]=5, A[10]=1, A[11]=9, A[12]=-1 同理，用数组B存储矩阵b的值。 2、主要数据结构 稀疏矩阵的转存算法： void CreateMatrix(int A[m][n],int B[50]) { int i,j,k=0; for(i=0;i实现稀疏矩阵(采用三元组表示)的基本运算实验报告
矩阵分析实验报告
采用十字链表表示稀疏矩阵,并实现矩阵的加法运算
矩阵特征值实验报告
矩阵转置及相加实验报告
矩阵键盘设计实验报告
稀疏矩阵的运算(完美版)
稀疏矩阵的十字链表加法
数据结构实验报告稀疏矩阵运算
矩阵乘法的并行化 实验报告
数据结构稀疏矩阵基本运算实验报告
稀疏矩阵的相加
稀疏矩阵的运算(完美版)
实现稀疏矩阵(采用三元组表示)的基本运算实验分析报告
矩阵连乘实验报告
稀疏矩阵乘法的运算
MATLAB矩阵实验报告
稀疏矩阵乘法运算
稀疏矩阵(实验报告)
相关主题
文本预览