稀疏矩阵快速转置.doc

xx大学 xx学院 算法与数据结构试验报告 设计名称： 算法与数据结构 设计题目： 稀疏矩阵的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）： 蔡琼（副教授） 课题工作时间： 2012年5月3日 说明： 实验课程类别：课程内实验 实验课程性质：必修 适用专业、年级：2010级计算机工程、计算机网络 开课院、系：计算机科学与工程学院计算机工程教研室 学时：18 编写依据：《算法与数据结构》实验教学大纲 修订时间：2012年2月 《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。 上机的工作环境要求：Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。 学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。 每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容： 学生基本情况：专业班级、学号、姓名 实验题目、实验内容 设计分析 源程序代码 测试用例（尽量覆盖所有分支） 实验总结 一．实验内容与学时分配 序次 实验 题目 实验 类型 基本技能训练 学时 一 线性结构综合应用 综合性 （1）掌握线性结构的常用操作； （2）能够应用线性结构解决比较简单的问题。 10 二 非线性结构综合应用 综合性 （1）掌握树形、图形结构的插入、删除、查找等算法； （2）能够应用二叉树解决比较简单的问题。 4 三 查找技术综合应用 综合性 （1）熟练熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。。m×n 的矩阵中，有t个非零元。令δ= t/(m*n),称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。 试验分析 引入两个数组作为辅助数据结构： num[nu]：表示矩阵A中某列的非零元素的个数； cpot[nu]：初始值表示矩阵A中某列的第一个非零元素在B中的位置。 num与cpot递推关系： 三元组表实现稀疏矩阵的转置（顺序取，直接存）算法伪代码如下： 源程序代码 #includestdio.h #define M 50 #define N 50 #define MaxSize 125 typedef struct { int r; //行号 int c; //列号 int d; //元素值 }TupNode; typedef struct { int rows; //行 int cols; //列 int nums; TupNode data[MaxSize]; }TSMatrix; void TranMat(TSMatrix a,TSMatrix b); void GetMat(TSMatrix a); void PriMat(TSMatrix a); void main() { TSMatrix a,b; GetMat(a); TranMat(a,b); printf(您输入的矩阵的为：\n); PriMat(a); printf(经过转置后得到的矩阵的为：\n); PriMat(b); } void TranMat(TSMatrix a,TSMatrix b) { int e; b.rows=a.cols; b.cols=a.rows; b.nums=a.nums; int n[N]={0}; //计算每一列a中的非零元素的个数 int cpot[N]={0}; //a中某列的非零元素在b中的位置 for(int j=0;ja.nums;j++) n[a.data[j].c]++; for(int i=2;i=a.cols;i++) cpot[i]=cpot[i-1]+n[i-1]; for(i=0;ia.nums;i++) {