稀疏矩阵的相关操作..doc

数据结构课程设计 设计说明书 稀疏矩阵相关操作的实现 学生姓名 钟振凯 学号 1221024001 班级 信管1201 成绩 指导教师 余冬梅 数学与计算机科学学院 2014年 3月 7日 课程设计任务书 2013—2014学年第2 学期 评语： 指导教师签名： 年 月 日 摘 要 以VC++作为软件开发环境，十字链表作为存储结构，设计与实现了稀疏矩阵运算。该软件实现了对任意矩阵进行输入，对矩阵进行输入，输出，对稀疏矩阵压缩存储，对矩阵进行转置的操作。采用十字链表方法对稀疏矩阵进行压缩存储，相对于三元表插入更加方便，界面清晰，易于为用户所接受。 关键字：十字链表；稀疏矩阵；数据结构 目 录 1 课题描述.................................................................6 2 任务分析.................................................................7 2.1 问题分析.................................................................7 2.2 代码实例.................................................................7 3 逻辑设计.................................................................8 3.1 算法设计.................................................................8 3.2 主函数流程图............................................................12 4 代码示例.................................................................13 5 程序调试.................................................................24 6 总结.....................................................................30 7 参考文献.................................................................31 1课题描述 在现实生活中当人们运用矩阵对数据进行存储的时候，往往数据中包含一些不用但占用内存空间的零元素，即所说的稀疏矩阵，稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。在对稀疏矩阵进行存储的时候，如果采用数组将所有数据进行存储的时候，往往占用较大的内存空间，所以可以设计一种只将有用数据进行存储，即十字链表或者三元组。 2 任务分析 2.1问题分析 当采用十字链表对数据进行存储的时候，需要在节点中将非零元素的行标，列表，元素值，分别用i,j,e分别表示，然后用向下的指针down 和向右的指针 right 来指向下边和右边的元素。其物理表示可以用图2.1和图2.2表示。 图2.1十字链表节点 （a）稀疏矩阵 （b）存储表示 图2.2十字链表存储稀疏链表实例 2.2代码实例 对稀疏矩阵采用图2.2结构进行存储时可以将节点中的内容定义为一个结构体，并将节点再作为一个元素，和dowm ,right 指针再组成一个结构体，具体代码示例如下： typedef struct OLNode //十字链表中的节点类型 { int i,j; ElemType e; struct OLNode *right,*down; }OLink; typedef struct //十字链表类型 { OLink **rhead,**chead; //rhead与