对称矩阵压缩算法的实现

数据结构课程设计数据结构课程设计 设设计计说说明明书书 对称矩阵压缩算法的实现对称矩阵压缩算法的实现 学生姓名 学号 班级 成绩 指导教师 数学与计算机科学学院数学与计算机科学学院 20152015 年年 1 1 月月 2 2 日日 课程设计任务书 2014 2015 学年第一学期学年第一学期 专业 网络工程 学号 姓名 课程设计名称 数据结构课程设计 设 计 题 目 对称矩阵压缩算法的实现 完 成 期 限 自 2014 年 12 月 22 日至 2015 年 1 月 2 日共 2 周 设计内容及要求设计内容及要求 矩阵是一个在科学计算与工程问题中常见的数学对象 在程序设计中这种数学对象常 常采用二维数组来存储 然而 有些矩阵具有某些特殊性 如对称矩阵 若用数组存储对 称矩阵其空间代价较高 为了降低对称矩阵存储代价 常常采用一维数组只存储对称矩阵 中的对角线及其以上或以下元素值 此过程需要进行二维数组 矩阵 下标到一维数组下标 的存储变换 请用 C C 语言编写一个程序实现对称矩阵的一维数组压缩存储 设计过程以及写作要求如下 设计过程以及写作要求如下 1 要针对本题目 认真研究所设计的内容 用简明扼要的语言描述课题 给出课题 的基本内容及要求 2 根据数据结构的相关知识给出实现对任意矩阵的输入 对称性的判断 对称矩阵 压缩存储的转换 及对转换后的一维数组元素以数学形式打印输出原矩阵的算法基本策略 及思路 3 给出较为详尽数据结构与算法 算法可以用流程图 伪代码等描述手段进行描述 4 给出一个完整的算法实现的 C C 程序 算法中的各子算法要力求用函数来实现 5 对编写的程序要进行详尽的测试分析 6 对本课题的设计工作要进行一个完整深刻的总结 最终设计成果形式为 最终设计成果形式为 1 设计软件一套 2 撰写一份课程设计说明书一份 打印并装订成册 指导教师 签字 教研室主任 签字 批准日期 年 月 日 数据结构数据结构 课程设计评阅书课程设计评阅书 题 目对称矩阵压缩算法的实现 学生姓名学 号 指导教师评语及成绩 成 绩 教师签名 年 月 日 教研室意见 总成绩 室主任签名 年 月 日 摘要摘要 本课程设计是以 vc 语言编程软件功能和相关数据结构的知识实现的 借助 Visual C 6 0 工具实现对称矩阵压缩算法功能的源代码 将矩阵以二维数组的形式存放 通过对 称矩阵的压缩存储 从而达到节省存储空间的目的 关键词 关键词 VC 对称矩阵 压缩存储 节省空间 目目 录录 1 课题描述 1 2 设计要求 2 2 1 设计要求 2 2 2 各模块程序的伪码算法 2 2 2 各模块之间的调用关系图 2 3 模块内的核心算法及流程图 3 3 1 构建任意矩阵 3 3 1 1 构建矩阵代码 4 3 2 判断矩阵是否对称 4 3 2 1 判断矩阵是否对称代码 6 3 3 对对称矩阵进行压缩存储 6 3 3 1 对对称矩阵进行压缩存储代码 8 3 4 将存储后的矩阵按照数学形式输出 8 3 4 1 将存储后的矩阵按照数学形式输出的代码 10 4 详细代码 11 5 程序测试 16 5 1 合法输入 16 5 1 1 菜单 16 5 1 2 构建任意矩阵 16 5 1 3 成功构建矩阵对其进行判断是否为对称矩阵 17 5 1 4 对对称矩阵进行压缩存储 18 5 1 5 按照数学形式输出所压缩的矩阵 19 5 1 6 退出程序 20 5 2 非法输入 20 5 2 1 非法操作菜单 20 5 2 2 n 值的非法输入 21 总结 22 参考资料 23 0 1 1 课题描述课题描述 矩阵是很多科学与工程计算问题中研究的数学对象 在此 人们感兴趣的不是矩阵本 身 而是如何存储矩阵的元 从而使矩阵的各种运算能有效的进行 通常 用高级语言编制程序时 都是用二维数组来存储矩阵元 有的程序设计语言中 还提供了各种矩阵运算 用户使用时都很方便 然而 在数值分析中经常出现一些阶数很 高的矩阵 同时在矩阵中有许多值相同的元素或者是零元素 有时为了节省存储空间 可 以对这类矩阵进行压缩存储 压缩矩阵 为多个值相同的元止分配一个存储空间 对零元不分配空间 开发工具 开发工具 Visual C 6 0 1 2 2 设计要求设计要求 2 12 1 设计要求设计要求 本次课程设计采用结构化程序设计方法 从整体到模块 逐步细化 模块化设计 结 构化编码的算法只适合特殊矩阵中的对称矩阵 面对一般矩阵 不进行压缩存储 存储时 采用的顺序存储结构主要为数组 包括一维数组和二维数组 程序中定义了一个结构体 Array s 其成员为两个数组 具体设计过程如下 2 22 2 各模块程序的伪码算法各模块程序的伪码算法 1 构建矩阵 CreatMatrix Array 操作结果 创建任意 n n 矩阵 2 判断矩阵是否对称 JudgeMatrix Array 初始条件 矩阵 M 存在 操作结果 判断 M 是否为对称矩阵 若不是 则重新构建 最终得到对称矩阵 3 压缩存储 CompMatrix Array 初始条件 矩阵 M 为对称矩阵 操作结果 将 M 压缩存储到一维数组中 4 输出所压缩的对称矩阵 OutputMatrix Array 初始条件 矩阵 M 已被压缩存储到一维数组中 操作结果 将 M 按照数学形式输出 2 22 2 各模块之间的调用关系图各模块之间的调用关系图 各模块之间的调用关系如图 2 1 所示 main CreatMatrix JudgeMatrix CompMatrix OutputMatrix CreatMatrix 图 2 1 各模块之间的调用关系 2 3 3 模块内的核心算法及流程图模块内的核心算法及流程图 3 13 1 构建任意矩阵构建任意矩阵 在构建任意 n n 矩阵这个模块中 利用了二维数组来接收所构建矩阵的元 CreatMatrix 函数 在构建矩阵时 首先要得到 n 值 将 n 值带入构建矩阵中 而输 入部分用 for 循环控制输入格式及元素个数 输入前已规定建立任意矩阵并且元素个数为 n n 个 接收时以二维数组的形式来存储从键盘输入的任意元素 输出所构建的矩阵时仍 用 for 循环来输出 输入流程图如图 3 1 所示 输出流程图如图 3 2 所示 其中 n 为行下表或列下标 开始 开始 输入 n 值 i 1 行下标初始化为 1 n 是非零自然数 N 判断非法输入 n 0 或者 n 为字符 判断 i 值与 Y i n 行下标 输入矩阵 系统提示 N n 值的关系 Y i 1 行下标初始化为 1 j 1 列下标初始化为 1 N i n 判断 i 值与行下标 n 值的关系 Y j n 判断 j 值 j 1 列下标初始化为 1 N 与列下标 n 值的关系 Y j n 判断 j 值与列下标 输出元素 NY n 值的关系 s M i j 存入元素 j j i i 结束 结束 图 3 1 输入流程图 图 3 2 输出流程图 3 3 1 13 1 1 构建矩阵代码构建矩阵代码 int CreatMatrix Array printf t 请输入您需要构建 n 阶矩阵中的 n 值 n scanf d if n0 n scanf d fflush stdin printf t 请输入数组中各元素 输入时请注意 s M i j s M j i n for i 1 i n i for j 1 j n j scanf d printf t t 您构建的矩阵为 n printf n for i 1 i n i for j 1 j n j printf t 2d s M i j printf n return ok 3 23 2 判断矩阵是否对称判断矩阵是否对称 由于矩阵的压缩只针对对称矩阵 因此在创建任意矩阵后要判断是否符合压缩要求 JudgeMatrix 函数 函数包括两个小部分 判断部分和判断结果输出部分 在对称矩 阵中 M i j M j i 为判断矩阵是否对称的依据 因此 要判断第一步输入的矩阵是否 是对称矩阵 就是要判断这一条件是否成立 如果成立 则程序结束 若不成立 则调用 函数 CreatMatrix 重新输入 构建矩阵并再次判断 直到输入的矩阵为对称矩阵结束 判断流程图如图 3 3 所示 判断结果流程图如图 3 4 所示 4 开始 开始 i 1 行下标初始化为 1 调用判断 函数 N i n 判断 i 值与行下 得到 k 值 标 n 值的关系 Y k 0 j 1 列下标初始 N 化为 1 Y N 对称矩阵 构建的不 j n 判断 j 值与 构建成功 是对称矩阵 列下标 n 值 Y 的关系 调用 CreatMatrix s M i j s M j i 函数 沿对称线元素不对称 矩阵构建成功 N Y k 结束 j 图 3 4 判断结果流程图 i 结束 图 3 3 判断流程图 5 3 2 13 2 1 判断矩阵是否对称代码判断矩阵是否对称代码 int JudgeMatrix Array s 判断矩阵是否为对称矩阵 int i j k k 0 for i 1 i n i for j 1 j n j if s M i j s M j i k printf t t 判断得到不相等元素的对数 k d k printf n if k 0 printf n printf t tM i j M j i n printf n t t 对称矩阵构建正确 请您选择其他服务 n else printf n printf t t 您构建的矩阵不是对称矩阵 return 1 return 0 3 33 3 对对称矩阵进行压缩存储对对称矩阵进行压缩存储 当判断得到对称矩阵后 便可对其进行压缩存储 将一维数组作为对称矩阵的存储结 构从而实现存储过程 CompMatrix 函数 此函数功能是对对称矩阵进行压缩存储 即就是将二维数组压缩 存储到一维数组中 压缩存储的元素为下三角元 再将压缩后的数组元素进行输出 压缩部分 通过赋值语句 s m k s M i j 将矩阵进行压缩存储 压缩流程图如图 3 5 所示 输出流程图如图 3 6 所示 6 开始 开始 i 1 k 0 初始化行下标 i 1 压缩时元素个数 k 一维数组下标 k 0 N i n 判断行下标 k n n 1 2 i 值与 N 值的 下三角元素个数 Y 关系 N 初始化 Y j 1 列下标 j 输出压缩后 矩阵元素 s M k N j i 列下标 与行下标 Y 的比较 结束 s m k s M i j 图 3 6 输出流程图 下三角元素赋值给 s m k k j i 结束 图 3 5 压缩流程图 7 3 3 13 3 1 对对称矩阵进行压缩存储代码对对称矩阵进行压缩存储代码 int CompMatrix Array for i 1 i n i for j 1 j i j s m k s M i j k printf t t 压缩后的矩阵存入一维数组后各元素为 n printf n for k 0 k j 时 k i i 1 2 j 1 当 i j 时 k j j 1 2 i 1 赋值流程图如图 3 7 所示 输出流程图如图 3 8 所示 8 开始 开始 i 1 初始化 i 1i 1 初始化 i 1 NN 判断 i 值与 i n 判断 i 值与 i n 行下标 n 值 行下标 n 值的的关系 Y 关系Y j 1 初始化 j 1 j 1 初始化 j 1 N 判断列下 判断列下标 j j i 标 j 值 j n 与 n 值的 与行下标 大小关系 Y i 值得大小Y k i i 1 2 j 1 输出矩阵 k j j 1 2 i 1 j s M i j s m k i j 结束 i 图 3 8 输出流程图 结束 图 3 7 赋值流程图 9 3 4 13 4 1 将存储后的矩阵按照数学形式输出的代码将存储后的矩阵按照数学形式输出的代码 int OutputMatrix Array s 按照数学形式输出矩阵 int i j k 0 for i 1 i n i for j 1 j j k i i 1 2 j 1 s M i j s m k else k j j 1 2 i 1 s M i j s m k printf t t 您压缩存储的矩阵按照数学形式输出为 n printf n for i 1 i n i for j 1 j n j printf t 2d s M i j printf n return ok 10 4 4 详细代码详细代码 include include include define OVERFLOW 2 define UNDERFLOW 1 define ok 1 typedef struct int M 100 100 int m 100 Array Array s int n int CreatMatrix Array printf t t 请输入数组中各元素 输入时请注意 s M i j s M j i n printf t 请输入您需要构建 n 阶矩阵中的 n 值 n scanf d if n0 n scanf d fflush stdin printf t 请输入数组中各元素 输入时请注意 s M i j s M j i n for i 1 i n i for j 1 j n j scanf d printf t t 您构建的矩阵为 n printf n 11 for i 1 i n i for j 1 j n j printf t 2d s M i j printf n return ok int JudgeMatrix Array s 判断矩阵是否为对称矩阵 int i j k k 0 for i 1 i n i for j 1 j n j if s M i j s M j i k printf t t 判断得到不相等元素的对数 k d k printf n if k 0 printf n printf t tM i j M j i n printf n t t 对称矩阵构建正确 请您选择其他服务 n else printf n printf t t 您构建的矩阵不是对称矩阵 return 1 return 0 int CompMatrix Array for i 1 i n i for j 1 j i j 12 s m k s M i j k printf t t 压缩后的矩阵存入一维数组后各元素为 n printf n for k 0 k n n 1 2 k printf 2d s m k return ok int OutputMatrix Array s 按照数学形式输出矩阵 int i j k 0 for i 1 i n i for j 1 j j k i i 1 2 j 1 s M i j s m k else k j j 1 2 i 1 s M i j s m k printf t t 您压缩存储的矩阵按照数学形式输出为 n printf n for i 1 i n i for j 1 j n j printf t 2d s M i j printf n return ok int menu select 菜单 13 char c do printf t t n printf t t 对称矩阵压缩算法的实现 n printf t t 1 构建任意 N N 个元素的矩阵 n printf t t 2 判断所建矩阵是否为对称矩阵 n printf t t 3 对对称矩阵进行压缩存储 n printf t t 4 按照数学形式输出所压缩的矩阵 n printf t t 5 退出程序 n printf t t n printf t t 请您输入选项 1 5 n fflush stdin c getchar while c 5 return c 返回选择 void main 主函数 char n 1 int m for switch menu select case 1 printf n printf t t t n printf n CreatMatrix s printf n printf t t 您已经成功构建 任意 矩阵 请您选择其他服务 n printf n printf t t t system pause break case 2 14 printf n printf t t t n printf n m JudgeMatrix s printf n if m 1 CreatMatrix s printf n printf t t t system pause break case 3 printf n printf t t t n printf n printf t t 只存储其下三角各元素 n printf n CompMatrix s printf n printf t t t system pause break case 4 printf n printf t t t n printf n OutputMatrix s printf n printf t t t system pause break case 5 printf n printf t t t 祝您好运 n printf t t t exit 0 15 5 5 程序测试程序测试 5 15 1 合法输入合法输入 5 1 15 1 1 菜单菜单 为了使程序界面能够美化 使用 对其进行框圈 并且使用 t 使其跳到下一个制表 位置 菜单的使用 使程序的操作简单明了 如图 5 1 所示 图 5 1 菜单 5 1 25 1 2 构建任意矩阵构建任意矩阵 在对矩阵进行构建时 先确定矩阵的阶数 n 然后对矩阵中的元素进行录入 录入时 用空格键区分两个数字 即使输入元素超过 n n 个 也只取前 n n 个元素 并将其以矩阵 的形式输出 如图 5 2 所示 图 5 2 构建任意矩阵 16 5 1 35 1 3 成功构建矩阵对其进行判断是否为对称矩阵成功构建矩阵对其进行判断是否为对称矩阵 该矩阵是否为对称矩阵 是通过 k 值进行判断 对于上述矩阵 对角线为 1 7 3 9 5 如若对称则 s M i j s M j i 但通过矩阵的输出 我们发现 6 2 1 3 6 4 1 5 2 8 7 9 10 组数据中 没有一组内的数据相同 则 不相等的元素数为 k 20 所以该矩阵不是对称矩阵 如图 5 3 所示 图 5 3 矩阵的对称判断 不对称矩阵 在矩阵输入时 必须是对称矩阵才可以进行第三步第四步操作 否则在判断对称矩阵 不是对称矩阵之后 系统提示重新输入数据 在输入并对其判断为对称矩阵之后 该矩阵 是对称矩阵 因为对角线为 1 3 5 7 9 如若对称则 s M i j s M j i 通过矩阵 的输出 我们发现 2 2 3 3 4 4 4 4 5 5 6 6 10 组数据中 括号内 的元素都相同 则不相等的元素数为 k 0 所以该矩阵是对称矩阵 如图所示 5 4 17 图 5 4 矩阵的对称判断 对称矩阵 5 1 45 1 4 对对称矩阵进行压缩存储对对称矩阵进行压缩存储 对对称矩阵进行压缩存储 其存储的元素为下三角 包括对角线 中的元 即 1 2 3 3 4 5 4 5 6 7 5 6 7 8 9 存储元素的个数为 k n n 1 2 即 15 如图 5 5 所示 18 图 5 5 对称矩阵的压缩 5 1 55 1 5 按照数学形式输出所压缩的矩阵按照数学形式输出所压缩的矩阵 矩阵是很多科学与工程计算问题中研究的数学对象 因此 程序编写的最终目的是使 其能够以数学形式输出 方便人们的研究 如图 5 6 所示 图 5 6 数学形式输出矩阵 19 5 1 65 1 6 退出程序退出程序 退出程序按钮使得程序更加完整 礼貌的结束语 使得程序更加文明 如图 5 7 所示 图 5 7 退出程序 5 25 2 非法输入非法输入 5 2 15 2