稀疏矩阵的存储实现

武汉理工大学 数据结构 课程设计说明书 课程设计任务书课程设计任务书 学生姓名 学生姓名 宋吉松宋吉松 专业班级 专业班级 软件软件 12021202 班班 指导教师 指导教师 李晓红李晓红 工作单位 工作单位 计算机科学与技术学院计算机科学与技术学院 题题 目目 稀疏矩阵的存储实现稀疏矩阵的存储实现 初始条件 初始条件 理论 学习了 数据结构 课程 掌握了一种计算机高级语言 实践 计算机技术系实验中心提供计算机及软件开发环境 要求完成的主要任务要求完成的主要任务 包括课程设计工作量及其技术要求 以及说明书撰 写等具体要求 1 系统应具备的功能 1 实现稀疏矩阵的三元组和十字链表两种存储结构 2 实现稀疏矩阵的基本运算 3 输出结果 2 数据结构设计 3 主要算法设计 4 编程及上机实现 5 撰写课程设计报告 包括 1 设计题目 2 摘要和关键字 中文和英文 3 正文 包括引言 需求分析 数据结构设计 算法设计 有关技 术的讨论 设计体会等 4 结束语 5 参考文献 时间安排 时间安排 2013 年 12 月 16 日 25 日 指导教师签名 指导教师签名 李晓红李晓红 20132013 年年 1212 月月 1414 日日 武汉理工大学 数据结构 课程设计说明书 系主任 或责任教师 签名 系主任 或责任教师 签名 年年 月月 日日 武汉理工大学 数据结构 课程设计说明书 摘摘 要要 本课程设计在学习数据结构的前提下 运用c语言 对稀疏矩阵进 行三元组存储和十字链表存储 并完成稀疏矩阵的转置 相加 相乘等基本运 算 关键词关键词 稀疏矩阵 三元组 十字链表 基本运算 武汉理工大学 数据结构 课程设计说明书 AbstractAbstract This course is designed on the premise of learning data structures using c language for sparse matrix triple store to store and cross linked and were achieved under the two storage sparse matrix transpose add multiply and other basic operations KeywordsKeywords sparse matrix triples Crusaders basic operations 武汉理工大学 数据结构 课程设计说明书 0 目录目录 引言引言 1 1 1 需求分析需求分析 1 1 稀疏矩阵三元组表和十字链表两种存储的实现 2 2 1 2稀疏矩阵转置 2 1 3稀疏矩阵的相加相乘 2 1 4输出结果 2 2 2 数据结构设计数据结构设计 2 1 三元组的结构体 2 2 2 十字链表的结构体 3 3 3算法设计算法设计 3 1三元组 3 1 1三元组的创建 3 3 1 2三元组的转置 5 3 1 3三元组的相加 5 武汉理工大学 数据结构 课程设计说明书 1 3 1 4三元组的相乘 8 3 1 5三元组的显示 10 3 2十字链表 3 2 1十字链表的创建 11 3 2 2十字链表的显示 12 3 3 主函数 13 4 4 设计体会设计体会 16 5 5 结束语结束语 16 附1 参考文献 16 附2 源代码 17 附3 运行结果 38 武汉理工大学 数据结构 课程设计说明书 2 武汉理工大学 数据结构 课程设计说明书 第 0 页 引言引言 什么是稀疏矩阵 人们无法给出确切的定义 它只是一个凭人们的直觉来了 解的概念 假设在 m n 的矩阵中 有 t 个元素不为零 令 q t m n 称 q 为 矩阵的稀疏因子 通常认为 q 0 05 时称为稀疏矩阵 按照压缩存储的概念 值存稀疏矩阵的非零元 因此 除了寻出非零元的值外 还必须同时记下它所在的行和列的位置 反之 一个三元组唯一确定了矩阵 A 的一个非零元 由此 稀疏矩阵可由表示非零元的三元组及其行列数唯一确定 其存储方法有三种 分别是三元组顺序表 行逻辑链接的顺序表 十字链表 分别是以顺序存储结构 带行连接信息的三元组表 及链式存储结构进行存储 表示 武汉理工大学 数据结构 课程设计说明书 第 1 页 1 1 需求分析需求分析 1 1 稀疏矩阵三元组表和十字链表两种存储的实现 三元组表的实现通过建立两个结构体 分别用来表示三元组的行数 列数 非零元数和元素的行 列坐标 值 然后通过 for 循环进行赋值 并求出每行 含有的非零元个数 十字链表与三元组的不同在于用链表来存储每一行 每一 列的元素信息 1 2 稀疏矩阵的转置 稀疏矩阵的转置即将行列值进行调换 将元素的行列值进行调换 重排每个 元素的次序 如何重排 三元组按照原矩阵 M 的列序进行转置 为了找到 M 的 每个元素 要对三元组表从第一行开始进行扫描 便可得到转置后矩阵的顺序 十字链表需要将元素的行指针和列指针调换 1 3 稀疏矩阵的相加相乘 两个矩阵相加及每个元素分别对应相加 两个矩阵的相乘 M N S 即 M 的行元素与 N 的列元素分别对应乘积的累加 得到的即为 S 以 M 的行 N 的列为坐标的元素的值 1 4 输出结果 可以用 for 或 while 循环 输出两种表示下的稀疏矩阵 武汉理工大学 数据结构 课程设计说明书 第 2 页 2 2 数据结构设计数据结构设计 2 1 三元组的结构体 typedef struct int i j 三元组每个元素的行坐标 列坐标 值 int e Triple typedef struct Triple data MAXSIZE 1 int rpos MAXSIZE 1 三元组各行第一个元素的位置 int mu nu tu 三元组矩阵的行数 列数 非零元个数 TSMatrix 三元组结构体定义 2 2 十字链表的结构体 typedef struct OLNode int i j int e 十字链表每个元素的行坐标 列坐标 值 struct OLNode right down OLNode OLink typedef struct int mu nu tu 矩阵的行数 列数 非零元个数 OLink rhead chead 行和列头指针 CrossList 十字链表结构体定义 武汉理工大学 数据结构 课程设计说明书 第 3 页 3 3 算法设计算法设计 3 1 1 三元组的创建 void CreateSMatrix TSMatrix scanf d d d if M mu 0 M nu 0 M tuM mu M nu 判断行值 列值 元素个数是否合法 printf 输入有误 for int i 1 i M tu i 输入稀疏矩阵元素 printf 请输入请输入非零元的行坐标 列坐标 值 scanf d d d if M data i i 0 M data i j 0 printf 输入错误 请重新输入 scanf d d d if for int num 100 if M tu int i for i 1 i M mu i num i 0 初始化 for int t 1 t M tu t num M data t i 求 M 中每 一行含非零元素个数 求 rpos M rpos 1 1 for i 2 i M mu i M rpos i M rpos i 1 num i 1 创建三元组 3 1 2 三元组的转置 void TransposeSMatrix TSMatrix M TSMatrix 通过三元组表示 将 M 转置为 T T mu M nu T tu M tu int q 1 for int col 1 col M nu col for int p 1 pa2 return 1 else if a1b2 return 1 if b1T mu M mu T mu 对 S 矩阵的行数赋值 S nu M nu T nu M nu T nu 对 S 矩阵的列数赋值 S tu 0 int ce int q 1 int mcount 1 tcount 1 while mcount M tu S data q i M data mcount i S data q j M data mcount j q mcount break case 1 S data q e T data tcount e S data q i T data tcount i S data q j T data tcount j q tcount break case 0 ce M data mcount e T data tcount e 其他情况下把两个矩阵的值相加 if ce S data q e ce S data q i M data mcount i S data q j M data mcount j q mcount tcount else mcount tcount 武汉理工大学 数据结构 课程设计说明书 第 5 页 break while mcount M tu S data q e M data mcount e S data q i M data mcount i S data q j M data mcount j q mcount 在 case 1 的情况下对 S 矩阵的非零值 行数 列数进行赋值 while tcount M tu S data q e T data tcount e S data q i T data tcount i S data q j T data tcount j q tcount 在 case 1 的情况下对 S 矩阵的非零值 行数 列数进行赋值 S tu q 1 三元组相加 3 1 4 三元组的相乘 int MultSMatrix TSMatrix M TSMatrix N TSMatrix 定义相乘函数中所需要用到 的变量 if M nu N mu return 0 如果第一个矩阵的行数不等于第二个矩阵的 列数 则退出 Q mu M mu Q nu N nu Q tu 0 三元组结构类型 Q 存放相乘后的 结果 if M tu N tu 0 如果两个矩阵元素相乘不为零 则进行运算 for arow 1 arow M mu arow 最外侧循环以矩阵行数作为 循环变量 for i 0 i N nu i ctemp i 0 Q rpos arow Q tu 1 if arow M mu tp M rpos arow 1 else tp M tu 1 for p M rpos arow p tp p 把每行与每列相乘 brow M data p j if brow N mu t N rpos brow 1 else t N tu 1 武汉理工大学 数据结构 课程设计说明书 第 6 页 for q N rpos brow q t q ccol N data q j ctemp ccol M data p e N data q e 值相乘 for ccol 1 ccol MAXSIZE return 1 Q data Q tu i arow Q data Q tu j ccol Q data Q tu e ctemp ccol return 1 三元组相乘 3 1 5 三元组的显示 void ShowTMatrix TSMatrix M for int col 1 col M mu col 通过双重循环 把稀疏矩阵中不为零的元素的 行数 列数和值显示出来 for int p 1 p M tu p if M data p i col printf 4d 4d 4d n M data p i M data p j M data p e 三元组显示 3 2 1 十字链表的创建 void CreateSMatix OL CrossList OLink p q printf 请输入稀疏矩阵的行数 列数 非零元素的个数 n 矩阵行数 列数下标均从开始 scanf d d d if M rhead OLink malloc M mu 1 sizeof OLNode exit 1 分配内存空间 if M chead OLink malloc M nu 1 sizeof OLNode exit 1 分配内存空间 for i 1 i M mu i M rhead i NULL 把矩阵 每个元素置空值 for i 1 ii i p j j p e e if M rhead i NULL M rhead i j j p right M rhead i M rhead i p else q M rhead i while q right p right q right q right p if M chead j NULL M chead j i i p down M chead j M chead j p else q M chead j while q down p down q down q down p scanf d d d 创建十字链表 3 2 2 十字链表的显示 int ShowMAtrix CrossList A int col OLink p for col 1 colmu col if A rhead col p A rhead col while p printf 3d 3d 3d n p i p j p e p p right return 1 十字链表显示 3 3 主函数 主函数 void main int n i TSMatrix M T S CrossList MM TT SS printf 稀疏矩阵的应用 n printf n1 用三元组创建稀疏矩阵 n2 用十字链表创建稀疏矩阵 n3 退出程序 printf n scanf d switch n case 1 武汉理工大学 数据结构 课程设计说明书 第 8 页 CreateSMatrix M printf 您输入的稀疏矩阵为 n 行 列 大小 n ShowTMatrix M printf 已经选择三元组创建稀疏矩阵 请继续选择 n1 稀疏矩阵转置 n2 稀 疏矩阵相加 n3 稀疏矩阵相乘 n4 退出程序 n scanf d switch i case 1 TransposeSMatrix M T printf 转置后的矩阵为 n 行 列 大小 n ShowTMatrix T break case 2 printf 请你输入另一个稀疏矩阵 CreateSMatrix T AddTMatix M T S printf 相加后的矩阵为 n 行 列 大小 n ShowTMatrix S break case 3 printf 请你输入另一个稀疏矩阵 CreateSMatrix T MultSMatrix M T S printf 相乘后的矩阵为 n 行 列 大小 n ShowTMatrix S break case 4 exit 0 break case 2 CreateSMatix OL MM printf 您输入的稀疏矩阵为 n 行 列 大小 n ShowMAtrix printf 已经选择十字链表创建稀疏矩阵 请选择操作 n1 稀疏矩 阵转置 n2 稀疏矩阵相加 n3 稀疏矩阵相乘 n4 退出程序 n scanf d switch i case 1 TurnSMatrix OL MM printf 转置后的矩阵为 n 行 列 大小 n ShowMAtrix break case 2 printf 请你输入另一个稀疏矩阵 CreateSMatix OL TT SMatrix ADD printf 相加后的矩阵为 n 行 列 大小 n ShowMAtrix break case 3 printf 请你输入另一个稀疏矩阵 武汉理工大学 数据结构 课程设计说明书 第 9 页 CreateSMatix OL TT MultSMatrix OL MM TT SS printf 相乘后的矩阵为 n 行 列 大小 n ShowMAtrix break case 4 exit 0 break case 3 exit 0 default printf 输入错误 武汉理工大学 数据结构 课程设计说明书 第 10 页 4 4 设计体会及结束语设计体会及结束语 通过设计本程序 加深了对矩阵存储的了解 掌握了稀疏矩阵三元组存储和 十字链表存储两种存储方法 课本上介绍的较简略 有的地方甚至有个错误 经过不断检查才最终发现 发现课本上的不一定是对的 同样的问题也许有更 好的方法 很多不懂的地方通过上网查资料 借鉴别人的设计经验 学习新的 函数最终完成了本设计 通过这次课程设计 丰富了自己的专业知识 增强了 自己解决问题的能力 有很大帮助 完成这次设计要感谢指导老师李晓红老师 及室友们的帮助 武汉理工大学 数据结构 课程设计说明书 第 11 页 附 1 参考文献 1 数据结构 c 语言版 严蔚敏 吴伟民 清华大学出版社 2007 2 C 程序设计教程 张蕊 吕涛 华中科技大学出版社 2012 9 3 C 面向对象程序设计教程 第 3 版 陈维兴 林小茶 清华大学出版社 2009 6 4 百度文库 稀疏矩阵十字链表运算 武汉理工大学 数据结构 课程设计说明书 第 12 页 附 2 源代码 include include define MAXSIZE 10000 typedef struct OLNode int i j int e 十字链表每个元素的行坐标 列坐标 值 struct OLNode right down OLNode OLink typedef struct int mu nu tu 矩阵的行数 列数 非零元个数 OLink rhead chead 行和列头指针 CrossList 十字链表结构体定义 typedef struct int i j 三元组每个元素的行坐标 列坐标 值 int e Triple typedef struct Triple data MAXSIZE 1 int rpos MAXSIZE 1 三元组各行第一个元素的位置 int mu nu tu 三元组矩阵的行数 列数 非零元个数 TSMatrix 三元组结构体定义 void CreateSMatrix TSMatrix scanf d d d if M mu 0 M nu 0 M tuM mu M nu 判断行值 列值 元素个数是否合法 printf 输入有误 for int i 1 i M tu i 输入稀疏矩阵元素 武汉理工大学 数据结构 课程设计说明书 第 13 页 printf 请输入请输入非零元的行坐标 列坐标 值 scanf d d d if M data i i 0 M data i j 0 printf 输入错误 请重新输入 scanf d d d if for int num 100 if M tu int i for i 1 i M mu i num i 0 初始化 for int t 1 t M tu t num M data t i 求 M 中每一行含 非零元素个数 求 rpos M rpos 1 1 for i 2 i M mu i M rpos i M rpos i 1 num i 1 创建三元组 void TransposeSMatrix TSMatrix M TSMatrix 通过三元组表示 将 M 转置为 T T mu M nu T tu M tu int q 1 for int col 1 col M nu col for int p 1 pa2 return 1 else if a1b2 return 1 if b1T mu M mu T mu 对 S 矩阵的行数赋 值 S nu M nu T nu M nu T nu 对 S 矩阵的列数赋值 S tu 0 int ce int q 1 int mcount 1 tcount 1 while mcount M tu 当 M data mcount i T data tcount i 或 M data mcount jT data tcount i 或 M data mcount j T data tcount j S data q i T data tcount i S data q j T data tcount j 把第二个矩阵的行数 i 列数 j 赋值给 S 矩阵的行 数 i 列数 j q tcount break case 0 ce M data mcount e T data tcount e 其他情况下把两个矩阵的值相加 if ce S data q e ce S data q i M data mcount i S data q j M data mcount j q mcount tcount else mcount tcount break while mcount M tu S data q e M data mcount e S data q i M data mcount i S data q j M data mcount j 武汉理工大学 数据结构 课程设计说明书 第 15 页 q mcount 在 case 1 的情况下对 S 矩阵的非零值 行数 列数进行赋值 while tcount M tu S data q e T data tcount e S data q i T data tcount i S data q j T data tcount j q tcount 在 case 1 的情况下对 S 矩阵的非零值 行数 列数进行赋值 S tu q 1 三元组相加 int MultSMatrix TSMatrix M TSMatrix N TSMatrix 定义相乘函数中所需要用到 的变量 if M nu N mu return 0 如果第一个矩阵的行数不等于第二个矩阵的 列数 则退出 Q mu M mu Q nu N nu Q tu 0 三元组结构类型 Q 存放相乘后的 结果 if M tu N tu 0 如果两个矩阵元素相乘不为零 则进行运算 for arow 1 arow M mu arow 最外侧循环以矩阵行数作为 循环变量 for i 0 i N nu i ctemp i 0 Q rpos arow Q tu 1 if arow M mu tp M rpos arow 1 else tp M tu 1 for p M rpos arow p tp p 把每行与每列相乘 brow M data p j if brow N mu t N rpos brow 1 else t N tu 1 for q N rpos brow q t q ccol N data q j ctemp ccol M data p e N data q e 值相乘 for ccol 1 ccol MAXSIZE return 1 Q data Q tu i arow Q data Q tu j ccol Q data Q tu e ctemp ccol return 1 三元组相乘 void ShowTMatrix TSMatrix M for int col 1 col M mu col 通过双重循环 把稀疏矩阵中不为零的元素的 行数 列数和值显示出来 for int p 1 p M tu p if M data p i col printf 4d 4d 4d n M data p i M data p j M data p e 三元组显示 void CreateSMatix OL CrossList OLink p q printf 请输入稀疏矩阵的行数 列数 非零元素的个数 n 矩阵行数 列数下标均从开始 scanf d d d M rhead OLink malloc M mu 1 sizeof OLink 分配内存空间 M chead OLink malloc M nu 1 sizeof OLink 分配内存空间 for i 1 i M mu i M rhead i NULL 把矩阵 每个元素置空值 for i 1 i M nu i M chead i NULL while ti i p j j p e e if M rhead i NULL M rhead i j j p right M rhead i M rhead i p else q M rhead i 武汉理工大学 数据结构 课程设计说明书 第 17 页 while q right p right q right q right p if M chead j NULL M chead j i i p down M chead j M chead j p else q M chead j while q down p down q down q down p t 创建十字链表 void TurnSMatrix OL CrossList M CrossList T nu M mu T mu M nu T tu M tu T rhead OLink malloc T mu 1 sizeof OLink 分配内存空间 T chead OLink malloc T nu 1 sizeof OLink 分配内存空间 for int i 1 i T mu i T rhead i NULL for int j 1 j T nu j T chead j NULL for j 1 i M mu j for i 1 ji M chead i j T rhead i j M chead i i T rhead i e M chead i e 十字链表转置 int SMatrix ADD CrossList A CrossList B OLNode pa pb pre p cp 100 定义 OLNode 类型的变量 int i j t t A tu B tu for j 1 jnu j cp j A chead j 将 A 矩阵的列表头指针赋给 cp 数组 for i 1 imu i pa A rhead i 武汉理工大学 数据结构 课程设计说明书 第 18 页 pb B rhead i 将 A B 矩阵的行表头指针分别赋 给 pa pb pre NULL while pb 当 pb 不等于零 if pa NULL pa j pb j p OLink malloc sizeof OLNode 给 p 动态分配空间 if pre A rhead i p else pre right p p right pa pre p p i i p j pb j p e pb e if A chead p j A chead p j cp p j p p down NULL 如果 A chead p j 不等于零 则把 p 赋给它及 cp p j else cp p j down p cp p j p pb pb right 否则把 p 赋给 cp p j else if pa jj pre pa pa pa right else if pa e pb e t pa e pb e pre pa pa pa right pb pb right else t t 2 if pre A rhead i pa right else pre right pa right p pa pa pa right if A chead p j p A chead p j cp p j p down else cp p j down p down free p pb pb right A mu A mu B mu A mu B mu A nu A nu B nu A nu B nu A 的行与列为 A 及 B 当中较大的一个 武汉理工大学 数据结构 课程设计说明书 第 19 页 return 1 十字链表相加 int MultSMatrix OL CrossList M CrossList N CrossList 中间变量 OLink p0 q0 p pl pla 中间变量 if M nu N mu 检查稀疏矩阵 M 的列数和 N 的行 数是否对应相等 printf 稀疏矩阵 A 的列数和 B 的行数不相等 不能相乘 n return 0 Q mu M mu Q nu N nu Q tu 0 if Q rhead OLink malloc Q mu 1 sizeof OLink exit 2 if Q chead OLink malloc Q nu 1 sizeof OLink exit 2 for i 1 i Q mu i Q rhead i NULL for i 1 i Q nu i Q chead i NULL 相乘 for i 1 i Q mu i for j 1 j j q0 i q0 q0 down M 的列大于 N 的行 则 N 的列指针后移 else if p0 j i p0 p0 right M 的列小于 N 的 行 则 M 的行指针右移 else M 的行等 于 N 的列 e p0 e q0 e 乘积累加 q0 q0 down p0 p0 right 移动指针 if e 乘积不 为 武汉理工大学 数据结构 课程设计说明书 第 20 页 if p OLink mallo