课程设计 稀疏矩阵应用.doc

数学与计算机学院 课程设计说明书 课 程 名 称 数据结构课程设计 课 程 代 码 8404181 题 目 稀疏矩阵应用 年级 专业 班 学 生 姓 名 学 号 开 始 时 间 2011 年 06 月 13 日 完 成 时 间 2011 年 06 月 21 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际 能力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 稀疏矩阵应用 目 录 1 1 引引 言言 1 1 1 1 问题的提出 1 1 2 国内外研究的现状 1 1 3 任务与分析 1 2 2 程序的主要功能程序的主要功能 1 1 2 1 三元组的转置 1 2 2 三元组的加法 1 2 3 三元组的减法 1 2 4 三元组的乘法 2 2 5 十字链表的转置 2 2 6 十字链表的加法 2 2 7 十字链表的减法 2 2 8 十字链表的乘法 2 3 3 程序运行平台程序运行平台 3 3 4 4 总体设计总体设计 3 3 5 5 程序类的说明程序类的说明 4 4 6 6 模块分析模块分析 5 5 稀疏矩阵应用 6 1 三元组的转置 5 6 2 三元组减法 6 6 3 三元组的减法 9 6 4 三元组的乘法 12 6 5 十字链表的转置 14 6 6 十字链表的加法 15 6 7 十字链表的减法 18 6 8 十字链表的乘法 22 7 7 系统测试系统测试 2525 7 1 三元组的转置 25 7 2 三元组的加法 26 7 3 三元组的减法 26 7 4 三元组的乘法 27 7 5 十字链表的转置 27 7 6 十字链表的加法 28 7 7 十字链表的减法 28 7 8 十字链表的乘法 29 7 9 总结 29 8 8 结论结论 2929 参考文献参考文献 2929 稀疏矩阵应用 摘摘 要要 随着计算机的普及 一句话引出题目 小四楷体 GB2312 分析了三元 组和十字链表的存储和各种运算的实现 利用 C 语言编程实现了稀疏矩阵的运算 系统 该系统具有三元组十字链表存储下的稀疏矩阵转置 加法 减法 乘法的 功能 关键词 关键词 稀疏矩阵 计算机 运算器 1 稀疏矩阵应用 1 引引 言言 1 1 问题的提出问题的提出 矩阵是很多科学与工程计算问题中研究的数学对象 因此 我们感兴趣的不是矩 阵本身 而是如何存储矩阵的元 从而使矩阵的各种运算能有效地进行 通常 用高级语言编制程序时 都是用二维数组来存储矩阵元 有的程序设计语 言中还提供了各种矩阵运算 用户使用时很方便 然而 在数值分析中 经常出现一些阶数很高的矩阵 同时在矩阵中有许多值相 同的元素或者是零元素 有时为了节省存储空间 可以对这类矩阵进行压缩存储 所 谓压缩存储 就是指 为多个值相同的元只分配一个存储空间 对零元不分配空间 1 2 国内外研究的现状国内外研究的现状 目前已经可以用于人脸识别 子空间方法预处理技术稀疏近似逆按模最小特征值修 正矩阵广义极小残余方法等方面 1 3 任务与分析任务与分析 1 给出算法并编程实现 2 任给实例并演示求解结果 3 给出时间复杂度分析 4 结合所完成题目 分析总结各算法所使用的算法设计技术 以及相应技术的 基本思想 2 程序的主要功能 2 1 三元组的转置三元组的转置 将一个按三元组存储的稀疏矩阵进行转置 2 2 三元组的加法三元组的加法 将两个按三元组存储的稀疏矩阵进行相加并得出结果 2 3 三元组的减法三元组的减法 将两个按三元组存储的稀疏矩阵进行相减并得出结果 2 稀疏矩阵应用 2 4 三元组的乘法三元组的乘法 将两个按三元组存储的稀疏矩阵进行相乘并得出结果 2 5 十字链表的转置十字链表的转置 将一个按十字链表存储的稀疏矩阵进行转置 2 6 十字链表的加法十字链表的加法 将两个按十字链表存储的稀疏矩阵进行相加并得出结果 2 7 十字链表的减法十字链表的减法 将两个按十字链表存储的稀疏矩阵进行相加并得出结果 2 8 十字链表的乘法十字链表的乘法 将两个按十字链表存储的稀疏矩阵进行相加并得出结果 3 稀疏矩阵应用 3 程序运行平台 VC 6 0 编译 链接 执行 4 总体设计 图 4 1 系统总体框架图 主 函 数 三 元 组 创 建 三 元 组 转 置 三 元 组 加 法 三 元 组 减 法 十 字 链 表 创 建 十 字 链 表 转 置 十 字 链 表 加 法 十 字 链 表 减 法 十 字 链 表 乘 法 4 稀疏矩阵应用 5 程序类的说明程序类的说明 OLNodeOLNode 结构声明结构声明 typedef struct OLNode int i j int e struct OLNode right down OLNode OLink CrosslistCrosslist 结构的声明结构的声明 typedef struct int mu nu tu OLink rhead chead CrossList TripleTriple 结构的声明结构的声明 typedef struct int i j int e Triple TSMatrixTSMatrix 结构的声明结构的声明 typedef struct Triple data maxsize int rpos maxsize 1 int nu mu tu TSMatrix 5 稀疏矩阵应用 6 模块分析 6 16 1 三元组的转置三元组的转置 将一个按三元组存储的稀疏矩阵进行转置 非快速转置 void TransposeSMatrix TSMatrix M TSMatrix 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 nu M nu T nu M nu T nu 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 8 稀疏矩阵应用 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 q mcount while tcountT mu M mu T mu S nu M nu T nu M nu T nu 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 11 稀疏矩阵应用 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 q mcount while tcount M tu 12 稀疏矩阵应用 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 S tu q 1 6 6 4 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 if M tu N tu 0 for arow 1 arow M mu arow for i 0 i N nu i 13 稀疏矩阵应用 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 ccolmaxsize return 1 Q data Q tu i arow Q data Q tu j ccol Q data Q tu e ctemp ccol return 1 6 56 5 十字链表的转置十字链表的转置 void TurnSMatrix OL CrossList OLink p q for col 1 coli 15 稀疏矩阵应用 p i p j p j row q p right p right p down p down q 6 66 6 十字链表的加法十字链表的加法 int SMatrix ADD CrossList A CrossList B 十字链表相加 OLNode pa pb pre p cp 100 int i j t t A tu B tu for j 1 jnu j cp j A chead j for i 1 imu i pa A rhead i pb B rhead i pre NULL while pb 16 稀疏矩阵应用 if pa NULL pa j pb j p OLink malloc sizeof OLNode 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 else cp p j down p cp p j p 17 稀疏矩阵应用 pb pb right 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 18 稀疏矩阵应用 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 return 1 6 76 7 十字链表的减法十字链表的减法 int SMatrix jian CrossList A CrossList B 十字链表相减 OLNode pa pb pre p cp 100 int i j t t A tu B tu for j 1 jnu j cp j A chead j 19 稀疏矩阵应用 for i 1 imu i pa A rhead i pb B rhead i pre NULL while pb if pa NULL pa j pb j p OLink malloc sizeof OLNode 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 20 稀疏矩阵应用 p down NULL else cp p j down p cp p j p pb pb right 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 21 稀疏矩阵应用 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 return 1 22 稀疏矩阵应用 6 86 8 十字链表的乘法十字链表的乘法 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 相乘 23 稀疏矩阵应用 for j 1 jj 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 乘积不为 0 if p OLink malloc sizeof OLNode exit 2 Q tu 非零元素增加 24 稀疏矩阵应用 p i i p j j p e e p right NULL p down NULL 赋值 指针后移 将 p 插入十字链表 行插入 if Q rhead i NULL 若 p 为该行的第 1 个结点 Q rhead i p p p 插在该行的表头且 pl 指向 p 该行的最 后一个结点 else pl right p pl p 插在