当前位置:首页 >> 信息与通信 >>

数据结构稀疏矩阵基本运算实验报告


课 程 设 计
课程: 课程:数据结构

题目: 结构体(行数,列数, 题目:稀疏矩阵 4 三元组单链表 结构体(行数,列数,头) 矩阵运算 重载运算符 优

班级: 班级:

姓名: 姓名:

学号: 学号:

设计时间:2010 年 1 月 17 日——2010 年 5 月 XX 日 设计时间:2010 2010 20 成绩: 成绩:

指导教师: 指导教师:楼建华

一,题目 题目 表示 操作 稀疏矩阵 4 结构体(行数,列数,头) 矩阵运算 结构 回传方式 三元组单链表 重载运算符

二,概要设计 1.存储结构 typedef struct{ int row,col;//行,列 datatype v;//非 0 数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行,n 列,t 非 0 数个数 }Matrix; 矩阵 a 非零数值 data[1] 非零数值 data[2] 行数 m 列数 n 头h 行r 列c 值d 行r 列c 值d … m n Data[max]→ row col v-→ row col v-→ …

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) ,三元组,...,三元组)

A->data[0] 1 2 3 4 max-1

row 0 1 1 2 3 …

col 4 0 2 1 0 …

v 8 1 3 2 6 …

1

(2)乘法运算要点
已知稀疏矩阵 A(m1× n1)和 B(m2× n2),求乘积 C(m1× n2). 稀疏矩阵 A,B,C 及它们对应的三元组表 A.data,B.data,C.data 如图 6 所示.

由矩阵乘法规则知:

C(i,j)=A(i,1)×B(1,j)+A(i,2)×B(2,j)+…+A(i,n)×B(n,j)= 这就是说只有 A(i,k)与 B(k,p)(即 A 元素的列与 B 元素的行相等的两项)才有相乘的机会,且当两项都不为零 时,乘积中的这一项才不为零. 矩阵用二维数组表示时,a11 只有可能和 B 中第 1 行的非零元素相乘,a12 只有可能和 B 中第 2 行的非零元 素相乘,…,而同一行的非零元是相邻存放的,所以求 c11 和 c12 同时进行:求 a11*b11 累加到 c11,求 a11*b12 累加到 c12,再求 a12*b21 累加到 c11,再求 a12*b22 累加到 c22.,…,当然只有 aik 和 bkj(列号与行号相等)且均 不为零(三元组存在)时才相乘,并且累加到 cij 当中去.

(3)稀疏矩阵的快速转置要点: 矩阵 A 中三元组的存放顺序是先行后列,对同一行来说,必定先遇到列号小的元素,这样只需扫 描一遍 A.data .所以需引入两个向量来实现 :num[n+1]和 position [n+1],num[col]表示矩阵 A 中第 col 列的非零元素的个数(为了方便均从 1 单元用起),position [col]初始值表示矩阵 A 中的第 col 列的第一个非零元素在 B.data 中的位置.于是 position 的初始值为:position [1]=1; position [col]= position [col-1]+num[col-1]; 2≤col≤n

依次扫描 A.data,当扫描到一个 col 列元素时,直接将其存放在 B.data 的 position [col]位置 上,position [col]加 1,position [col]中始终是下一个 col 列元素在 B.data 中的位置.

A->row[0] 1 2 3

0 1 3 4

2

(4)逆矩阵 ⒈判断矩阵是否为方阵 ⒉逆矩阵的算法: ①求行列式的值 ②求矩阵的伴随矩阵 ③用伴随矩阵除以行列式 ⒊ 求逆矩阵的流程:

3

四,源程序(测试结果) #include<iostream> #include<string> #include<iomanip> #include<cmath> using namespace std; #define max 100 #define datatype int typedef struct{ int row,col;//行,列 datatype v;//非 0 数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行,n 列,t 非 0 数个数 }Matrix; /*求逆矩阵存储*/ typedef struct{ //存储结构 int m, n; //行,列数 double *p; //矩阵基址 }nMatrix; void In(nMatrix a){ //求逆输入 cout<<"请将矩阵 a 的行,列数再次输入:"; cin >>a.m>>a.n; int m = a.m, n = a.n; int i, j; double *p = a.p = new double[m * n]; //p 是行指针 cout<<"请按行优先输入矩阵 a 的全部数值:\n"; for (i = 0; i < m; p += n, i++) { for (j = 0; j < n; j++) cin>>p[j]; //即 a.p[i*n+j] } } void Out(nMatrix a){ //求逆输出 int m = a.m, n = a.n; int i, j; double *p = a.p; for (i = 0; i < m; p += n, i++) { for (j = 0; j < n; j++) cout<<p[j]<<'\t'; cout<<endl; } } istream& operator >>(istream& input,Matrix &A){ int i; cout<<"请输入行数:"; input>>A.m;
4

cout<<"请输入列数:"; input>>A.n; cout<<"请输入非 0 值个数:"; input>>A.t; for(i=1;i<=A.t;i++){ cout<<"请输入行数,列数,非 0 值:"<<"("<<i<<")\n"; input>>A.data[i].row>>A.data[i].col>>A.data[i].v; } return input; } ostream& operator <<(ostream& output,Matrix &A){ int i,j,t=1,k=0; for(i=1;i<=A.m;i++){ for(j=1;j<=A.n;j++){ if(A.data[t].row==i&&A.data[t].col==j){ output<<A.data[t].v<<'\t'; t++;} else output<<k<<'\t'; } cout<<"\n"; } return output; } Matrix operator +(Matrix A,Matrix B){//加法 int i,j,k; Matrix C; if(A.m!=B.m||A.n!=B.n){ cout<<"这两个矩阵不能相加"<<endl; exit(0);} C.m=A.m;C.n=A.n; C.t=0; if(A.t==0&&B.t==0) exit(0); i=j=k=1; while(i<=A.t&&j<=B.t){ if(A.data[i].row<B.data[j].row){ C.data[k]=A.data[i]; i++;k++; } else{ if(A.data[i].row>B.data[j].row){ C.data[k]=B.data[j]; j++;k++; } else{ if(A.data[i].col<B.data[j].col){ C.data[k]=A.data[i]; i++;k++; } else{ if(A.data[i].col>B.data[j].col){
5

C.data[k]=B.data[j]; j++;k++; } else{ if(A.data[i].v+B.data[j].v!=0){ C.data[k].row=A.data[i].row; C.data[k].col=A.data[i].col; C.data[k].v=A.data[i].v+B.data[j].v; k++; } i++;j++; } } } } } while(i<A.t){ C.data[k]=A.data[i]; i++;k++; } while(j<B.t){ C.data[k]=B.data[j]; j++;k++; } C.t=k; return C; } Matrix operator -(Matrix A,Matrix B){ Matrix C; int i,j,k; if(A.m!=B.m||A.n!=B.n) { cout<<"这两个矩阵不能相减";exit(0);} C.m=A.m;C.n=A.n; C.t=0; if(A.t==0&&B.t==0) exit(0); i=j=k=1; while(i<=A.t&&j<=B.t) { if(A.data[i].row<B.data[j].row) { C.data[k]=A.data[i]; i++;k++; } else { if(A.data[i].row>B.data[j].row) { C.data[k]=B.data[j]; j++;k++; } else { if(A.data[i].col<B.data[j].col) { C.data[k]=A.data[i]; i++;k++; }
6

else { if(A.data[i].col>B.data[j].col) { C.data[k]=B.data[j]; j++;k++; } else { if(A.data[i].v-B.data[j].v!=0) { C.data[k].row=A.data[i].row; C.data[k].col=A.data[i].col; C.data[k].v=A.data[i].v-B.data[j].v; k++; } i++;j++; } } } } } while(i<A.t) { C.data[k]=A.data[i]; i++;k++; } while(j<B.t) { C.data[k]=B.data[j]; j++;k++; } C.t=k; return C; } Matrix operator *(Matrix A,Matrix B){ Matrix C; int k,p,crow,brow,q,ccol; int num[max],pos[max],ctemp[max]; if (A.n==B.m){ for(k=1;k<=B.m;k++) num[k]=0; for(k=1;k<=B.t;k++) num[B.data[k].row]++; pos[1]=1; for(k=2;k<=B.t;k++) pos[k]=pos[k-1]+num[k-1]; pos[1+B.t]=pos[B.t]+1; C.m=A.m; C.n=B.n; C.t=0; p=1; while(p<=A.t){ crow=A.data[p].row; for(k=1;k<=C.n;k++) ctemp[k]=0; while (p<=A.t&&A.data[p].row==crow){ brow=A.data[p].col; for(q=pos[brow];q<=pos[brow+1]-1;q++){ ccol=B.data[q].col;
7

ctemp[ccol]=ctemp[ccol]+A.data[p].v*B.data[q].v; } p=p+1; } for(ccol=1;ccol<=B.n;ccol++) if(ctemp[ccol]!=0){ C.t=C.t+1; C.data[C.t].row=crow; C.data[C.t].col=ccol; C.data[C.t].v=ctemp[ccol]; } } } else cout<<"这两个矩阵不能相乘"; return C; } Matrix operator ~(Matrix A){ Matrix B; int col,i,p,q; int num[max],position[max]; B.t=A.t;B.m=A.n; B.n=A.m; if(B.t){ for(col=1;col<=A.n;col++) num[col]=0; for(i=1;i<=A.t;i++) num[A.data[i].col]++; position[1]=1; for(col=2;col<=A.n;col++) position[col]=position[col-1]+num[col-1]; for(p=1;p<=A.t;p++){ 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].v=A.data[p].v; position[col]++; } } return B; } nMatrix Trs(nMatrix a){ //求逆矩阵的先转置 nMatrix trs; trs.m = a.n; trs.n = a.m; trs.p = new double[a.m * a.n]; for (int i = 0; i < a.m; i++) { for (int j = 0; j < a.n; j++) { trs.p[j * a.m + i] = a.p[i * a.n + j];
8

} } return trs; } nMatrix Adjunct(nMatrix a, int indexm, int indexn){ //求第 indexm 行 indexn 列元素的 代数余子式 nMatrix adj; adj.m=a.m - 1; adj.n=a.n - 1; adj.p = new double[(a.n - 1) * (a.n - 1)]; for (int i = 0; i < indexm; i++) { for (int j = 0; j < indexn; j++) { adj.p[i * (a.n - 1) + j] = a.p[i * a.n + j]; } for (int k = indexn + 1; k < a.n; k++) { adj.p[i *(a.n - 1) + k -1] = a.p[i * a.n + k]; } } for (int m = indexm + 1; m < a.n; m++) { for (int j = 0; j < a.n - 1; j++) { adj.p[(m - 1) * (a.n - 1) + j] = a.p[m * a.n + j]; } for (int k = indexn + 1; k < a.n; k++) { adj.p[(m - 1) * (a.n - 1) + k - 1] = a.p[m * a.n + k]; } } return adj; } double Det(nMatrix a) //递归求行列式 { double det = 0; if (a.m != a.n) { cout<<"不是方阵,没有行列式!"<<endl; cout<<"求行列式退出"<<endl; } if (a.n == 1) { det = a.p[0]; return det; } else { for (int i = 0; i < a.n; i++)
9

{ if (i % 2 == 0) det += a.p[i * a.n] * Det(Adjunct(a, i, 0)); else det -= a.p[i * a.n] * Det(Adjunct(a, i, 0)); } } return det; } nMatrix operator !(nMatrix a) { //求矩阵的逆 nMatrix temp; temp.m=a.n; temp.n=a.m; temp.p = new double[a.m * a.n]; //矩阵的逆 = 伴随矩阵 / 行列式 double det = Det(a); if (det == 0) //如果行列式的值为 0,则没有逆 { cout<<"此矩阵没有逆!"<<endl; cout<<"求矩阵逆退出!"<<endl; } for (int i = 0; i < temp.m; i++) { for (int j = 0; j < temp.n; j++) { if ((i +j) % 2 == 0) temp.p[i * temp.m + j] = Det(Adjunct(a, i, j)) / det; else temp.p[i * temp.m + j] = -Det(Adjunct(a, i, j)) / det; } } return Trs(temp); } void main(){ Matrix C={0},A={0},B={0};nMatrix a={0}, b={0},temp={0}; cin>>A; cout<<"a=\n"<<A; cin>>B; cout<<"b=\n"<<B; C=A+B;cout<<"a+b=\n"<<C; C=A-B;cout<<"a-b=\n"<<C; C=A*B;cout<<"a*b=\n"<<C; C=~A;cout<<"~a=\n"<<C; In(a); cout<<"矩阵的行列式为:"<<endl; cout<<Det(a)<<endl; cout<<"矩阵的逆为:"<<endl; temp=!a;cout<<"!a=\n"<<Trs<<endl; }

10

五,测试 请输入行数:2 请输入列数:2 请输入非 0 值个数:2 请输入行数,列数,非 0 值:(1) 111 请输入行数,列数,非 0 值:(2) 121 a= 1 1 0 0 请输入行数:2 请输入列数:2 请输入非 0 值个数:2 请输入行数,列数,非 0 值:(1) 221 请输入行数,列数,非 0 值:(2) 212 b= 0 0 0 1 a+b= 1 1 0 1 a-b= 1 1 0 1 a*b= 0 1 0 0 ~a= 1 0 1 0 请将稀疏矩阵 a 的行,列数再次输入:2 2 请按行优先输入稀疏矩阵 a 的全部数值: 11 00 矩阵的行列式为: -1 矩阵的逆为: !a= 1 0 1 0 Press any key to continue

11

六,总结 这次数据结构课程设计的制作使我对数据结构和 C 语言的理解更加深刻,也使我认识到了自 己很多不足之处. 我发现自己在处理稍微具体的程序时显得无从下手,以前学习的知识只是理论性的知识,并 没有真正实践过, 当我通过网上查询, 请教学生老师, 复习知识后才对编写程序有了初步的思路. 后来编写程序时也碰到了许多错误,我对于指针的掌握程度较差导致了我在使用的时候产生了很 多错误,请教了学习较好的同学后才逐步完成.最后还有很多细节方面难以修改,于是就改进算 法,使自己的程序有了雏形. 这次程序设计使我认识到,要做成编写一个完整的程序绝对不是一件简单的事情,不单要掌 握基础知识更要勇于实践,不单要舍得花费时间更要用心去完成它.无论是编写程序还是完成现 实生活中的其他事情,我们都必须按部就班地从点滴做起,逐步完成.不但要完成更要做到尽善 尽美. 学习数据结构的历程不会因为完成本次课程设计而停止,我是为了用知识武装大脑而学习, 通过学习充实自己的生活,我一定会努力学习,争取以后能够完成规模更大的程序.

12


相关文章:
数据结构实验报告稀疏矩阵运算
数据结构实验报告稀疏矩阵运算 - 教学单位 计算机科学与技术 学生学号 012301714315 数据结构 课程设计报告书 题 目 稀疏矩阵运算器 秦豹 学生姓名 专业名称 软件...
数据结构实验报告-特殊矩阵和稀疏矩阵
数据结构实验报告-特殊矩阵和稀疏矩阵 - 《数据结构与算法》实验指导 V2014 实验五 【实验目的】 特殊矩阵和稀疏矩阵 1、掌握数组的结构类型(静态的内存空间配置)...
数据结构稀疏矩阵运算器
数据结构稀疏矩阵运算器 - 实习 4 4.1 稀疏矩阵运算器 实习报告 题目:设计一个能实现稀疏矩阵基本运算的运算器。 班级:软件工程 11-1 姓名:张艳艳 学号:...
数据结构实验稀疏矩阵计算器
数据结构实验稀疏矩阵计算器_计算机软件及应用_IT/计算机_专业资料。‘ 实验报告题目:稀疏矩阵运算器 班级:14 电子商务平台建设班 学号:20141103468 学号:20141103421 ...
数据结构实验报告(实验五_稀疏矩阵运算器)
享专业文档下载特权 赠共享文档下载特权 10W篇文档免费专享 每天抽奖多种福利 立即开通 意见反馈 下载客户端 网页 新闻 贴吧 知道 音乐 图片 视频 地图 文库 | ...
数据结构课程设计(稀疏矩阵运算器)
数据结构课程设计(稀疏矩阵运算器) - 【问题描述】 稀疏矩阵是指那些多数元素为零的矩阵。利用 稀疏 特点进行存储和计算可以大大 节省存储空间 , 提高计算效率。...
《数据结构 课程设计》稀疏矩阵实验报告
数据结构 课程设计》稀疏矩阵实验报告_电脑基础知识_IT/计算机_专业资料。《...9 一、概述稀疏矩阵的加法运算,既将稀疏矩阵 A 和 B,他均为 m 行 n 列,...
【数据结构算法】实验4 稀疏矩阵基本操作-链接结构...
浙江大学城市学院实验报告课程名称 实验项目名称 实验成绩 实验四 数据结构与算法...包括:①初始化稀疏矩阵;②输入稀疏矩阵;③输出稀疏矩阵; ④稀疏矩阵的转置运算...
数据结构实验报告 稀疏矩阵
数据结构实验报告 稀疏矩阵 - 信息学院 数据结构实验报告 学号: 姓名: 班级: 实验名称:编写程序,使用三元组表存储一 课程名称:数据结构稀疏矩阵, 并用一次...
数据结构_实验四_字符串、稀疏矩阵实验
实验编号:4 四川师大《数据结构实验报告 实验四 字符串、稀疏矩阵实验_ 2016...一些基本操作; (2) 掌握稀疏矩阵的三元组顺序表存储表示,并实现矩阵的转置运算...
更多相关标签: