河北工业大学计算机软件技术基础（VC）
课程设计任务书
一、题目：01稀疏矩阵压缩存储与转置 二、目的与要求
1． 目的：
（1）通过该题目的设计，培养学生综合利用C++语言解决问题的能力，使学生理解和掌握C++语言的结构体，自定义函数等设计方法，将所学知识转化为分析和设计简单实际问题的能力，并学会查资料和工具书,进行创新设计。
（2）提高学生建立程序文档、归纳总结的能力。
（3）继续和深化软件技术基础课程的学习，初步了解数据结构中对于稀疏矩阵的存储与操作。
2． 基本要求：
（1）要求用C++语言编程，在Visual C++环境下调试完成；
（2）要求使用C++的结构体和自定义函数完成设计；
（3）在VC++6.0环境中，学会调试程序的方法，及时查究错误，调试完成。 （4）程序调试通过后，完成程序文档的整理,加必要的注释。
三、设计方法和基本原理
1． 课题功能描述
本题目的功能是对稀疏矩阵采用三元组的形式进行压缩存储，并能够对压缩存储的矩阵还原显示和转置。
2． 基本原理和关键字
1）. 稀疏矩阵
矩阵中非零元素的个数较少（一般小于5%）。 2）. 压缩存储
只存储稀疏矩阵中的非零元素，同时存储这些元素的位置信息。 3）. 三元组
将每一个非零元素用（i，j，value）来表示，i表示非零元素所在的行，j表示非零元素所在的列，value是非零元素的值，这种方式表示称为三元组。
例如矩阵：
0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0
三元组形式的存储为：
i 6 1 1 3 3 4 5 6 6 j 6 2 3 1 5 3 2 1 4 Value 8 12 9 -3 14 24 18 15 -7 0 1 2 3 4 5 6 7 8 其中每行表示一个三元组，其中第0个元素表示矩阵的总行数、列数、非零元素的个数；从第1行到第8行表示矩阵中的非零元素，每行的值分别表示非零元素所在的行数、列数和值。
3． 问题解决方案（编程要求）：
1）编写程序，实现压缩矩阵的还原显示；
2）编写程序，实现压缩矩阵的转置，并将转置的矩阵以压缩矩阵的形式存储。
四、主要技术问题的描述：
1、定义三元组
使用结构体的形式定义三元组，结构体的分量包括非零元素所在的行、列和值。 struct Triple {
int i; //元素行号 int j; //元素列号 ElemType e; //元素值 };
使用结构体的形式定义稀疏矩阵，其分量包括三元组数组，矩阵总行数、总列数和非零元素总个数。 struct TsMatrix {
Triple data[MAXSIZE+1]; //三元组表，以行为主序存入一维向量 data[ ]中 int mu; //矩阵总行数 int nu; //矩阵总列数
int tu; //矩阵中非零元素总个数 };
2、压缩矩阵还原显示
自定义函数，将三元组中非零元素在矩阵中相应的位置显示出来，其余的位置显示0。 3、压缩矩阵转置
如下图所示，自定义函数，直接将原始矩阵三元组的存储形式，转化为转置矩阵的三元组存储形式。 具体方法：依次扫面原始矩阵三元组存储形式中的列数据，按扫描到的列号从小到大的顺序存入到转置后矩阵的三元组形式，因为原始矩阵的行就是转置后矩阵的列。
目的：M0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0(1, 2, 12)0 0 –3 0 0 15转置后12 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)11T三元组表a.data(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)三元组表b.data
五、创新要求
快速转置压缩矩阵，利用带辅助向量的三元组表，辅助向量的内容包括每列的非零元素个数 NUM(i)以及每列的第一个非零元素在三元组表中的位置POS(i) 。
如下表所示：
iNUM(i)POS( i )121203323415516627利用此表直接找到原始矩阵三元组的元素在转置矩阵三元组中的存储位置，不需逐个扫描从而节．．．．．．省系统时间。
六、课程设计的考核方式及评分方法
1．考核方式
（1） 学生要提交书面课程设计报告（A4纸打印）；并将设计报告的电子文档、.cpp源文件和.h头
文件放到一个文件夹里（如果是基于MFC的编程，另外还包括源程序的压缩包）上传到所对应班级的学生名称相应文件夹中。
（2） 课程设计结束时，在机房当场验收。教师提供测试数据，由学生运行所设计的系统，检查运行结果是否正确，并回答教师提出的有关问题。 2．评分方法
根据出勤率、课程设计期间纪律、课程设计运行结果、课程设计报告及答辩情况综合评分。
七、书写设计报告的要求（详细内容见“设计报告模板”）
八、说明：课程设计的有关文档，“设计报告模板”和“课程设计要求”请在下载任务书处下载。
出师表
两汉：诸葛亮
先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。
宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。
侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。
将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。
亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也
。
臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。
先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽忠言，则攸之、祎、允之任也。 愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。臣不胜受恩感激。 今当远离，临表涕零，不知所言。
