#include
#include
#define MAXSIZE 1250
typedef struct
{
int i,j;
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int
mu,nu,tu,cnum[MAXSIZE+1],rnum[MAXSIZE+1],cpot[MAXSIZE+1],rpos[MAXSIZE+1 ];
}TSMatrix;
void getmatrix(TSMatrix &t);
void transpose(TSMatrix t,TSMatrix &s);
void print(TSMatrix t);
void addmatrix(TSMatrix t,TSMatrix s,TSMatrix &a);
int main()
{
int k; TSMatrix t,s,a;
printf("请输入需要执行的操作的序号：（1.矩阵转置 2.矩阵相加）\n");
scanf("%d",&k);
switch(k)
{
case(1):
{
getmatrix(t);
if(t.mu!=t.nu) printf("ERROR矩阵行不等于列");
else
{
printf("输入的矩阵为：\n");
print(t);
transpose(t,s);
printf("转置后的矩阵为：\n");
print(s);
}
}break;
case(2):
{ printf("请依次输入两个矩阵\n");
getmatrix(t);
printf("\n\n");
getmatrix(s);
printf("输入的两个矩阵分别为：\n");
printf("矩阵a：\n");
print(t);
printf("矩阵b：\n");
print(s);
if(t.mu!=s.mu||t.nu!=s.nu) printf("ERROR");
else
{
addmatrix(t,s,a);
printf("相加后的矩阵为：\n");
print(a);
}
}break;
}
return 0;
}
void getmatrix(TSMatrix &t)
{
int i,k;https://www.doczj.com/doc/a61064777.html,um[0]=0;t.cpot[0]=1;t.rnum[0]=0,t.rpos[0]=1;
printf("请输入矩阵的行数、列数以及非零元个数，用空格隔开：\n");
scanf("%d %d %d",&t.mu,&t.nu,&t.tu);
for (i=1;i<=t.tu;i++)
{
printf("请输入第%d个非零元的行数、列数以及非零元的值，用空格隔开：\n",i);
scanf("%d %d %d",&t.data[i].i,&t.data[i].j,&t.data[i].e);
}
for(i=1;i<=t.nu;i++)
{ t.cpot[i]=t.cpot[i-1]+https://www.doczj.com/doc/a61064777.html,um[i-1];
https://www.doczj.com/doc/a61064777.html,um[i]=0;
for(k=1;k<=t.tu;k++)
{
if(t.data[k].j==i) https://www.doczj.com/doc/a61064777.html,um[i]+=1;
}
}
for(i=1;i<=t.mu;i++)
{
t.rpos[i]=t.rpos[i-1]+t.rnum[i-1];
t.rnum[i]=0;
for(k=1;k<=t.tu;k++)
{
if(t.data[k].i==i) t.rnum[i]+=1;
}
}
}
void transpose(TSMatrix t,TSMatrix &s)
{
s.mu=t.mu;s.nu=t.nu;s.tu=t.tu;
int i,m,q;
for (i=1;i<=t.tu;i++)
{
m=t.data[i].j; q=t.cpot[m];
s.data[q].i=t.data[i].j;
s.data[q].j=t.data[i].i;
s.data[q].e=t.data[i].e;
t.cpot[m]++;
}
}
void print(TSMatrix t)
{
int i,j,k=1;
for (i=1;i<=t.mu;i++)
{
for(j=1;j<=t.nu;j++)
{
if(t.data[k].i==i&&t.data[k].j==j) {printf("%d\t",t.data[k].e);k++;}
else {printf("0\t");}
}
printf("\n");
}
}
void addmatrix(TSMatrix t,TSMatrix s,TSMatrix &a)
{
int i,k,j,q=1;
a.mu=t.mu;a.nu=t.nu;a.tu=0;
for(i=1;i<=t.mu;i++)
{
k=t.rpos[i];j=s.rpos[i];
if(i==t.mu)
{
t.rpos[i+1]=t.rpos[i]+t.tu-k+1;s.rpos[i+1]=s.rpos[i]+s.tu-j+1;
}
while(k { if(t.data[k].j!=s.data[j].j) { if(t.data[k].j { a.data[q].i=i;a.data[q].j=t.data[k].j;a.data[q].e=t.data[k].e; q++;k++;a.tu++; } else { a.data[q].i=i;a.data[q].j=s.data[j].j;a.data[q].e=s.data[j].e; q++;j++;a.tu++; } } else { a.data[q].i=i;a.data[q].j=t.data[k].j;a.data[q].e=t.data[k].e+s.data[j].e; q++;k++;j++;a.tu++; } } while(k {a.data[q].i=i;a.data[q].j=t.data[k].j;a.data[q].e=t.data[k].e; q++;k++;a.tu++;} while(j {a.data[q].i=i;a.data[q].j=s.data[j].j;a.data[q].e=s.data[j].e; q++;j++;a.tu++;} } } 实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （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; //非零元素个数 课程设计 所抽题目：采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。 要求：要检查有关运算的条件，并对错误的条件产生 报警。 问题分析和建立模型：本题目主要是运用所学知识，用十字链表的方法去表示稀疏矩阵，并使之可以在两矩阵间进行相加。而后，若有错误，则对错误进行警报。 框架搭建： 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 教学单位计算机科学与技术 学生学号 5 数据结构 课程设计报告书 题目稀疏矩阵运算器 学生豹 专业名称软件工程 指导教师志敏 实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。 需要分析：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。 软件平台：Windows 2000，Visual C＋＋ 6.0或WINTC 概要设计：ADT Array { 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = { 一、实验内容和要求 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={ 第 5 章数组和广义表 一、选择 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存 储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则 a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到 8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以 列为主存放时，元素A[5，8]的存储首地址为(B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 3. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设 每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。 A. 808 B. 818 C. 1010 D. 1020 4. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0 到8，列下标j的范围从0到9。从供选择的答案中选出应填入下列 关于数组存储叙述中（）内的正确答案。 （1）存放A至少需要（ E ）个字节； （2）A的第8列和第5行共占（ A ）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元 素（ B ）的起始地址一致。 供选择的答案： （1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[4,9] C. A[5,8] D. A[0,9] 5. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括 主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中， 则在B中确定aij（i 专业课程设计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的第一行。 课程设计 课程：数据结构 题目：稀疏矩阵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 数据结构课后习题及解析第五章 第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p 稀疏矩阵的相加 题目: 稀疏矩阵的相加 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<<" 该矩阵为空矩阵"< B(2.0) D(2.0) D(2.0) D(2.0) D(2.0) A(2.0) B(2.0) B(2.0) D(2.0) C(2.0) D(2.0) D(2.0) 2-1 广义表是一种（B）数据结构。(2分) 1.非递归的 2.递归的 3.树型 4.图状 作者: 严冰 单位: 浙江大学城市学院 2-2 一个广义表为( a, (b, c), d, (), ((f, g), h) )，则该广义表的长度与深度分别为（D）。(2分) 1.4和6 2.6和3 3.3和5 4.5和3 作者: 严冰 单位: 浙江大学城市学院 2-3 稀疏矩阵的快速转置算法的时间复杂度是（D）。(2分) 1.三次方时间 2.二次方时间 3.对数时间 4.线性时间 作者: 严冰 单位: 浙江大学城市学院 2-4 在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含（D）个域。(2分) 1. 4 2. 3 3. 6 4. 5 作者: 严冰 单位: 浙江大学城市学院 2-5 广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（D）。(2分) 1.都可以用链接结构与顺序结构存储 2.无共同点 3.都是递归结构 4.数据元素本身是一个数据结构 作者: 严冰 单位: 浙江大学城市学院 2-6 (neuDS_C++)以下叙述中正确的是(A )。(2分) 1.串是一种特殊的线性表 2.串的长度必须大于零 3.串中元素只能是字母 4.空串就是空白串 作者: 姚志军 单位: 广东东软学院 2-7 (neuDS_C++)串是一种特殊的线性表，其特殊性体现在(B )。(2分) 1.可以顺序存储 2.数据元素是一个字符 3.可以链接存储 4.数据元素可以是多个字符 作者: 姚志军 单位: 浙江大学 2-8 (neuDS_C++)设有两个串p和q，求q在p中首次出现的位置的运算称作( B)。(2分) 1.连接 2.模式匹配 3.求子串 4.求串长 作者: 姚志军 单位: 广东东软学院 2-9 (neuDS_C++)设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是 (D )。(2分) 1.BCDEF 2.BCDEFG 3.BCPQRST 4.BCDEFEF 专业课程设计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 ={ 课程设计任务书 学生姓名：专业班级： 指导教师：夏红霞工作单位：计算机科学与技术学院题目: 稀疏矩阵乘法的运算 课程设计要求: 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 设计目标：通过一定的数据结构，存储含有少量数据的矩阵，把他们存入一个稀疏矩阵中，然后实现稀疏矩阵的乘法运算。[基本要求]设计稀疏矩阵的存储结构；建立稀疏矩阵；实现稀疏矩阵的乘法 稀疏矩阵的乘法运算 程序代码： #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 韶关学院 学生实验报告册 实验课程名称：数据结构与算法 实验项目名称：实验五数组及其应用 稀疏矩阵运算器 实验类型（打√）：（基础、综合、设计√） 院系：信息工程学院计算机系专业：***** 姓名：*** 学号：***** 指导老师：陈正铭 韶关学院教务处编制 一、实验预习报告内容 二、实验原始（数据）记录 实验时间：2007 年 5 月30日（星期三第7，8 节）实验同组人： 三、实验报告内容 2007年 5 月30 日 注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。 2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。 【源程序】 #include实现稀疏矩阵(采用三元组表示)的基本运算实验报告
采用十字链表表示稀疏矩阵,并实现矩阵的加法运算
数据结构实验报告稀疏矩阵运算
矩阵转置及相加实验报告
第 5 章 数组和广义表答案
稀疏矩阵的运算(完美版)
稀疏矩阵的十字链表加法
数据结构稀疏矩阵基本运算实验报告
数据结构课后习题及解
稀疏矩阵的相加
PTA第四章串、数组和广义表练习题
稀疏矩阵的运算(完美版)
实现稀疏矩阵(采用三元组表示)的基本运算实验分析报告
稀疏矩阵乘法的运算
稀疏矩阵乘法运算
稀疏矩阵(实验报告)
数据结构实验报告(实验五 稀疏矩阵运算器)
相关主题
文本预览