当前位置:首页 >> IT/计算机 >>

数据结构与课程设计 稀疏矩阵


实验课程名称 专 学 学 指 业 班 级 生 姓 名 号 导 教 师

数据结构与课程设计 10 级计科(2)班 赵 腾 松

10410902044 冯 韵

2012 至 2013 学年第 1 学期第 4 至 5 周

目录 1 概述 ...............................................................................................................- 1 1 系统分析 .............................................................................. 错误!未定义书签。 2.1 设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值........................ - 1 2.2 造函数并输出最终稀疏矩阵 ....................................................................... 1 3 概要设计 ............................................................................................................ 1 3.1 存储结构设计 ............................................................................................. 1 3.2 系统功能设计 ............................................................................................. 1 4 详细设计 ........................................................................................................- 2 4.1 稀疏矩阵的存储 ................................................................................... - 2 4.2 稀疏矩阵的加法 ........................................................................................ 2 5 程序代码 ........................................................................................................- 4 6 运行与测试 .....................................................................................................- 7 7 总结与心得 ......................................................................................................... 7 8 参考文献 ............................................................................................................ 7

1 概述
掌握稀疏矩阵的加法运算,稀疏矩阵的存储方法,每一个元素可能有多个直接前驱和多个 直接后继。一般情况下都是采用顺序存储方法来表示数组,但有时在实际应用中,一般的顺序 存储方法已经不太实用。有时候用普通存储方法就会造成很大的空间浪费。为了节省存储单元, 用压缩方法只存储非零元素。

2 系统分析

2.1 设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值
本模块要求设计函数建立稀疏矩阵并初始化。在创建稀疏矩阵时需要设计稀疏矩阵的加法 和存储方法,出现错误时能够对错误进行判别处理初始化稀疏矩阵都为空值。在设计输出稀疏 矩阵的值的函数时也要针对两种不同的情况分别编制函数才能准确的输出稀疏矩阵。在对稀疏 矩阵进行初始化时只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时以矩 阵的完整形式输出。

2.2 造函数并输出最终稀疏矩阵
本模块要求设计加法函数对两个矩阵进行运算并输出最终的稀疏矩阵,操作后的结果矩阵 的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点需要灵活运用数组及指 针的特点。

3 概要设计

3.1 存储结构设计
以一维数组顺序存放非零元素的行号、列号和数值,行号-1 作为结束标志。稀疏矩阵的存 储类似于建立顺序存储稀疏矩阵的三元组表。假设 A 为一个稀疏矩阵,B 为一个存储对应于 A 矩阵生成的数组。用一个二重循环来判断每个矩阵元素是否为零,若不为零,则将其行、列下 标及其值存入到一维数组 B 中对应的元素中。

3.2 系统功能设计
设计稀疏矩阵的加法算法,假设两个稀疏矩阵 A 和 B,它们均为 m 行 n 列,分别存放在数组 A 和 B 中,编写矩阵的加法实现 C=A+B 的算法,C 矩阵存放在数组 C 中。根据设计要求,首先要将一 个稀疏矩阵对应存储到一个一维数组中,然后在进行矩阵加法时依次扫描矩阵 A 和 B 的行列值,
-1-

并以行优先,当行列相同时,将第三个元素值相加的和以及行列号三个元素存入结果数组 C 中; 不相同时,将 A 或 B 的三个元素直接存入结果数组中。

4 详细设计

4.1 稀疏矩阵的存储
void(CreateMatrix(int A[m][n],int B[50])) //转储稀疏矩阵的算法 { int i,j,k=0; for(i=0;i<m;i++) for(j=0;j<n;j++) if(A[i][j]!=0) { B[k]=i;k++; B[k]=j;k++; B[k]=A[i][j];k++; } B[k]=-1; //非零元素存储结束 }

4.2 稀疏矩阵的加法
void MatrixAdd(int A[max],int B[max],int C[max]) { int i=0,j=0,k=0; while(A[i]!=-1 && B[j]!=-1) { if(A[i]==B[j]) //行相等 { if(A[i+1]==B[j+1]) //列相等 { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]-B[j+2]; k=k+3; i=i+3; j=j+3; } else if(A[i+1]<B[j+1]) { //B 的列小于 A 的列,将 A 的三个元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2];
-2-

k=k+3; i=i+3; } else { //B 的列小于 A 的列,将 B 的三个元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } else if(A[i]<B[j]) { //A 的行小于 B 的行,将 A 的三个元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else { //B 的行小于 A 的行,将 B 的三个元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } //循环结束 if(A[i]==-1) while(B[j]!=-1) { //A 结束 B 还有元素,将 B 的所有元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } else while(A[i]!=-1) { //B 结束 A 还有元素,将 A 的所有元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2];

-3-

k=k+3; i=i+3; } C[k]=-1; }

5 程序代码
#include<stdio.h> #define m 3 //用户可根据需要定义原始矩阵行数 #define n 3 //定义原始矩阵 #define max 50 void(CreateMatrix(int A[m][n],int B[50])) //转储稀疏矩阵的算法 { int i,j,k=0; for(i=0;i<m;i++) for(j=0;j<n;j++) if(A[i][j]!=0) { B[k]=i;k++; B[k]=j;k++; B[k]=A[i][j];k++; } B[k]=-1; //非零元素存储结束 } void MatrixAdd(int A[max],int B[max],int C[max]) { int i=0,j=0,k=0; while(A[i]!=-1 && B[j]!=-1) { if(A[i]==B[j]) //行相等 { if(A[i+1]==B[j+1]) //列相等 { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]-B[j+2]; k=k+3; i=i+3; j=j+3; } else if(A[i+1]<B[j+1]) { //B 的列小于 A 的列,将 A 的三个元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1];
-4-

C[k+2]=A[i+2]; k=k+3; i=i+3; } else { //B 的列小于 A 的列,将 B 的三个元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } else if(A[i]<B[j]) { //A 的行小于 B 的行,将 A 的三个元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else { //B 的行小于 A 的行,将 B 的三个元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } //循环结束 if(A[i]==-1) while(B[j]!=-1) { //A 结束 B 还有元素,将 B 的所有元素直接存入 C 中 C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } else while(A[i]!=-1) { //B 结束 A 还有元素,将 A 的所有元素直接存入 C 中 C[k]=A[i]; C[k+1]=A[i+1];

-5-

C[k+2]=A[i+2]; k=k+3; i=i+3; } C[k]=-1; } void main() { int E[m][n],F[m][n],A[max],B[max],C[max]; int i,j,k; for(i=0;i<m;i++) //输入 E 矩阵的所有元素 for(j=0;j<n;j++) scanf("%d",&E[i][j]); for(i=0;i<m;i++) //输入 F 元素的所有元素 for(j=0;j<n;j++) scanf("%d",&F[i][j]); CreateMatrix(E,A); //E 矩阵的非零元素存储到一维数组 A 中 CreateMatrix(F,B); //F 矩阵的非零元素存储到一维数组 B 中 MatrixAdd(A,B,C); //A,B 相加存入 C 中 i=0;j=0;k=0; printf("A 数组内容如下:\n"); while(A[i]!=-1) { //输出 A 中内容 printf("%5d,%5d,%5d\n",A[i],A[i+1],A[i+2]); i=i+3; } printf("B 数组内容如下:\n"); while(B[j]!=-1) { //输出 B 中内容 printf("%5d,%5d,%5d\n",B[j],B[j+1],B[j+2]); j=j+3; } printf("C 数组内容如下:\n"); while(C[k]!=-1) { //输出 C 中内容 printf("%5d,%5d,%5d\n",C[k],C[k+1],C[k+2]); k=k+3; } }

-6-

6 运行与测试

7 总结与心得
在本次实验中遇到了很多问题,一开始的时候程序有很多错误,花了很多时间才调试成功。 慢慢的把一些错误找出来并改正了。我认为学习最重要的是发现问题,解决问题。自己解决不 了的和同学一起解决,这样才能学到更多东西。本次试验让我对稀疏矩阵的认识进一步加深了。

8 参考文献
[1] 《数据结构课程设计》 苏仕华 等编著 机械工业出版社 [2] 《数据结构》 语言版) 严蔚敏 吴伟民 编著 清华大学出版社 (C [3] 《C 程序设计》 (第三版) 谭浩强 著 清华大学出版社

-7-


相关文章:
数据结构课程设计之稀疏矩阵实现与应用_图文
数据结构课程设计稀疏矩阵实现与应用 - ##大学 数据结构课程设计报告 题目:稀疏矩阵实现与应用 院(系): 学生姓名: 班级: 学号: 计算机工程学院 起迄日期: ...
数据结构课程设计-稀疏矩阵
数据结构课程设计-稀疏矩阵 - 数据结构 课程设计报告 设计题目:稀疏矩阵 专业:计算机科技 院系:计算机学院 姓名:xxxxxxx 学号:xxxxxxxx 时间:2013 年 9 月 22...
数据结构稀疏矩阵课程设计报告
数据结构稀疏矩阵课程设计报告_工学_高等教育_教育专区。数据结构课程设计报告:稀疏矩阵的应用包括三元组表下稀疏矩阵的创建,以及加、乘、转置的算法 ...
数据结构课程设计-稀疏矩阵运算器
数据结构课程设计-稀疏矩阵运算器 - 成绩评定 教师签名 嘉应学院 计算机学院 实验报告 课程名称: 数据结构课程设计 2017-2018 学年第 2 学期 开课学期: 班级: ...
数据结构课设报告—稀疏矩阵转置和乘法
数据结构课设报告—稀疏矩阵转置和乘法_理学_高等教育_教育专区。数据结构课程设计,稀疏矩阵转置和乘法 燕山大学课 程设计说明书 题目:稀疏矩阵的转置和乘法 学院(...
稀疏矩阵的操作 --课程设计
稀疏矩阵的操作 --课程设计_工学_高等教育_教育专区。课程设计 数据结构 攀枝花学院 学生课程设计(论文)题目: 稀疏矩阵的操作学 号: 学生姓名: 所在院(系):专...
数据结构--稀疏矩阵课程设计
数据结构--稀疏矩阵课程设计 - 数据结构 课程设计说明书 目录 1 问题描述 ... 1 2 需求...
稀疏矩阵(算法与数据结构课程设计)
稀疏矩阵(算法与数据结构课程设计)_工学_高等教育_教育专区。算法与数据结构课程设计 论文 稀疏矩阵 一、问题描述假若在 m × n 阶中,有 t 个元素不为零,令...
数据结构与算法 特殊矩阵和稀疏矩阵
数据结构与算法 特殊矩阵和稀疏矩阵 - 《数据结构与算法》实验指导 V2017 常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018___学年 第__1__ ...
数据结构-稀疏矩阵-实验报告与代码
数据结构-稀疏矩阵-实验报告与代码 - 一.需求分析 输入要求:稀疏矩阵的行、列非零元素个数 输出要求:稀疏矩阵的转置、加法、减法、乘法 二.算法设计 本程序中...
更多相关标签: