三元组表示稀疏矩阵的转置(般算法和快速算法).docVIP

PAGE  PAGE 17 一、设计要求 1．1 问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高计算效率。求一个稀疏矩阵A的转置矩阵B。 1．2需求分析 （1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置运算。 （2）稀疏矩阵的输入形式采用三元组表示，运算结果则以通常的阵列形式列出。 （3）首先提示用户输入矩阵的行数、列数、非零元个数，再采用三元组表示方法输入矩阵，然后进行转置运算，该系统可以采用两种方法，一种为一般算法，另一种为快速转置算法。 （4）程序需要给出菜单项，用户按照菜单提示进行相应的操作。 二、概要设计 2．1存储结构设计 采用“带行逻辑链接信息”的三元组顺序表表示矩阵的存储结构。三元组定义为： typedef struct { int i； //非零元的行下标 int j； //非零元的列下标 ElemType e; //非零元素值 }Triple; 矩阵定义为： Typedef struct { Triple data[MAXSIZE+1]; //非零元三元组表 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix; 例如有矩阵A，它与其三元组表的对应关系如图 2．2 系统功能设计 本系统通过菜单提示用户首先选择稀疏矩阵转置方法，然后提示用户采用三元组表示法输入数据创建一个稀疏矩阵，再进行矩阵的转置操作，并以通常的阵列形式输出结果。主要实现以下功能。 创建稀疏矩阵。采用带行逻辑连接信息的三元组表表示法，提示用户输入矩阵的行数、列数、非零元个数以及各非零元所在的行、列、值。 矩阵转置。1采用一般算法进行矩阵的转置操作，再以阵列形式输出转置矩阵B。 2采用快速转置的方法完成此操作，并以阵列形式输出转置矩阵B。 三、模块设计 3．1 模块设计 程序包括两个模块：主程序模块、矩阵运算模块。 3．2 系统子程序及其功能设计 系统共设置了8个子程序，各子程序的函数名及功能说明如下。 （1）CreateSMatrix(RLSMatrix M) //创建稀疏矩阵 （2）void DestroySMatrix(RLSMatrix M) //销毁稀疏矩阵 （3）void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵 （4）void print(RLSMatrix A) //打印矩阵函数，输出以阵列形式表示的矩阵 （5）TransposeSMatrix(RLSMatrix M,RLSMatrix T) //求稀疏矩阵的转置的一般算法 （6）FastTransposeSMatrix(RLSMatrix M,RLSMatrix T) //快速转置算法 （7）void showtip() //工作区函数，显示程序菜单 （8）void main() //主函数 3．3 程序主要调用关系图 8 main 1 2 3 4 5 6 7 四、详细设计 4．1 数据类型定义 采用矩阵“带行逻辑连接信息”的三元组顺序表存储结构。 4．2 系统主要子程序详细设计 （1）主函数： void main() { int result; int j; RLSMatrix A,B; COORD Co={0,0};DWORD Write; SetConsoleTitle(稀疏矩阵的转置); HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY); FillConsoleOutputAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY,100000000,Co,Write); ///windows的API函数，用来设置控制台标题及颜色。 do { showtip(); //调用菜单函数 int i; scanf(%d,i); switch(i) { case 1: