稀疏矩阵基本操作-实验报告

稀疏矩阵基本操作实验报告一、实验内容稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相乘等算法二、实验目的1.熟悉数组、矩阵的定义和基本操作2.熟悉稀疏矩阵的储存方式和基本运算3.理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法三、实验原理1.使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数。2.稀疏矩阵的创建算法：第一步：根据矩阵创建一个二维数组，表示原始矩阵第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，重复该步骤。第三步：重复第二步，知道二维数组中所有的元素已经取出。3.稀疏矩阵倒置算法：第一步：判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。第二步：计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i]代表矩阵中第i列非零元素的个数）。以及倒置后矩阵每行首非零元的位置，存入cpot数组中（其中cpot表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第一个非零元的位置）。第三步：确定倒置后矩阵的行数和列数。第四步：取出表示要导致矩阵中三元组表元素{e,I,j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中确定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中。cpot[j]变量加一。第五步：重复第四步，直到三元组表中所有的元素都完成倒置。第六步：把完成倒置运算的三元组表输出。4.稀疏矩阵加法算法：第一步：检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否则输出错误信息。第二步：定义变量i和j，用于控制三元组表的遍历。第三步：比较变量矩阵M中第i个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。进入第五步第四步：如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第i个元素的行下标小于矩阵N中第j个元素的下标，则把M中第i个元素所在行的所有非零元素依次添加到三元组表中。第五步：重复第三步，直到矩阵M和矩阵N中所有元素都非零元素添加到三元组表中。第六步：输出运算结果5.稀疏矩阵乘法算法：第一步：检查矩阵M和矩阵N能否参与乘法运算（即矩阵M的列数等于矩阵N的行数），如果两个矩阵可以参与乘法运算，进入下一步，否则输出错误信息第二步：检查两个矩阵相乘以后是否为零矩阵，如果相乘结果是零矩阵，直接返回一个零矩阵。第三步：分别计算矩阵M和矩阵N中每行非零元的个数（分别存放到num_m和num_n数组中），并计算出每行首非零元的位置（分别存放到cpot_m和cpot_n中）。第四步：依次取矩阵M中的非零元（第一次取出矩阵M中的第一个非零元），求出该非零元所在行和所在列乘积的和，然后把值放到结果三元组表的特定位置。第五步：重复第四步，直到矩阵M中所有非零元都已经参与运算。第六步：输出结果四、程序流程图五、实验结果5.1程序主菜单5.2稀疏矩阵三元组的创建和倒置5.3稀疏矩阵的加法运算并以三元组输出结果5.4稀疏矩阵的乘法运算并以矩阵方式输出结果六、操作说明1.在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序会自动根据输入元素的个数对矩阵数据进行填充2.每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一个矩阵为空矩阵，或者分配不到临时空间），程序都会返回到主菜单。输入的数据都会被清空。七、附录：代码#includestdio.h#includestdlib.h#includewindows.h#defineMAXSIZE1000#defineOK0#defineMALLOC_FAIL-1//表示分配空间时发生错误#defineEMPTY_MATRIX-2//表示正尝试对一个空矩阵进行运算操作#defineMATRIX_NOT_MATCH-3//表示尝试对不符合运算条件的矩阵进行运算操作（例如非相同行数列数矩阵相加）/*-----------结构体声明部分----------------*/typedefstruct{introw;//非零元的行下标intcol;//非零元的列下标inte;//非零元的值}Triple;typedefstruct{Triple*data;//非零元素的元素表intrownum;//矩阵的行数intcolnum;//矩阵的列数intnum;//矩阵非零元的个数}TSMatrix,*PTSMatrix;/*-----------函数声明部分------------------*///初始化稀疏矩阵结构intTSMatrix_Init(TSMatrix*M);//以三元组的方式输出稀疏矩阵voidTSMatrix_PrintTriple(TSMatrix*M);//以矩阵的方式输出稀疏矩阵voidTSMartix_PrintMatrix(TSMatrix*M);//从一个二维数组（普通矩阵）创建一个稀疏矩阵TSMatrix*TSMatrix_Create(int*a,introw,intcol);//从键盘录入数据创建一个稀疏矩阵TSMatrix*TSMatrix_CreateFromInput();//求稀疏矩阵M的转置矩阵TintTSMatrix_FastTranspose(TSMatrixM,TSMatrix*T);//如果稀疏矩阵M和N的行数的列数相同，计算Q=M+NintTSMatrix_Add(TSMatrixM,TSMatrixN,TSMatrix*Q);//如果稀疏矩阵M的列数等于N的行数，计算Q=MxN;intTSMatrix_Multply(TSMatrixM,TSMatrixN,TSMatrix*Q);//把光标位置移动到该行行首voidResetCursor();/*-----------程序主函数--------------------*/intmain(void){intinfo;charch;//从一个二维数组创建一个系数矩阵TSMatrix*M;TSMatrix*N;//用来接收运算结果的空间TSMatrix*T=(TSMatrix*)malloc(sizeof(TSMatrix));while(1){fflush(stdin);system(cls);printf(稀疏矩阵基本操作演示\n);printf(1.矩阵的创建和转置\n);printf(2.矩阵的加法运算并以三元组输出结果\n);printf(3.矩阵的乘法运算并以矩阵输出结果\n);printf(\n);printf(Q.退出程序\n);printf(\n);printf(请输入选项：);scanf(%c,&ch);switch(ch){case'1':system(cls);M=TSMatrix_CreateFromInput();if(M!=NULL){printf(\n\n以三元组输出稀疏矩阵：\n);TSMatrix_PrintTriple(M);printf(\n倒置后稀疏矩阵的三元组输出：\n);TSMatrix_FastTranspose(*M,T);TSMatrix_PrintTriple(T);system(pause);}else{printf(创建矩阵过程发生错误);system(pause);}break;case'2':system(cls);M=TSMatrix_CreateFromInput();N=TSMatrix_CreateFromInput();if(M==NULL||N==NULL){printf(创建矩阵过程中发生错误！\n);system(pause);break;}info=TSMatrix_Add(*M,*N,T);if(info==MATRIX_NOT_MATCH){printf(这两个矩阵不能运算呢！！⊙﹏⊙\n);}elseif(info==OK){printf(\n运算结果：\n);TSMatrix_PrintTriple(T);}system(pause);break;case'3':system(cls);M=TSMatrix_CreateFromInput();N=TSMatrix_CreateFromInput();if(M==NULL||N==NULL){printf(创建矩阵过程中发生错误！\n);system(pause);break;}info=TSMatrix_Multply(*M,*N,T);if(info==MATRIX_NOT_MATCH){printf(这两个矩阵不能运算呢！！⊙﹏⊙\n);}elseif(info==OK){printf(\n运算结果：\n);TSMartix_PrintMatrix(T);}system(pause);break;case'q':case'Q':exit(0);}}return0;}//初始化稀疏矩阵结构intTSMatrix_Init(TSMatrix*M){M-data=(Triple*)malloc(MAXSIZE*sizeof(Triple));if(!M-data)returnMALLOC_FAIL;M-num=0;M-colnum=0;M-rownum=0;returnOK;}//从一个二维数组创建一个稀疏矩阵TSMatrix*TSMatrix_Create(int*a,introw,intcol){inti,j;TSMatrix*P=(TSMatrix*)malloc(sizeof(TSMatrix));TSMatrix_Init(P);//设置稀疏矩阵的行数和列数P-rownum=row;P-colnum=col;for(i=0;irow;i++){for(j=0;jcol;j++){//如果第i+1行第i+1列元素是非零元素if(0!=*(a+i*col+j)){//把非零元的元素和位置信息保存到稀疏矩阵中P-data[P-num].e=*(a+i*col+j);P-data[P-num].row=i+1;P-data[P-num].col=j+1;//把稀疏矩阵中的非零元个数加一P-num++;}}}returnP;}//以三元组的方式输出稀疏矩阵voidTSMatrix_PrintTriple(TSMatrix*M){inti;if(0==M-num){printf(稀疏矩阵为空！\n);return;}printf(ijv\n);printf(===============\n);for(i=0;iM-num;i++){printf(%3d%3d%3d\n,M-data[i].row,M-data[i].col,M-data[i].e);}printf(===============\n);}//求稀疏矩阵M的转置矩阵TintTSMatrix_FastTranspose(TSMatrixM,TSMatrix*T){int*num,*cpot,i,t;//如果矩阵M为空矩阵，返回错误信息if(M.num==0)returnEMPTY_MATRIX;//分配临时的工作空间num=(int*)malloc((M.colnum+1)*sizeof(int));cpot=(int*)malloc((M.colnum+1)*sizeof(int));//如果临时的工作空间分配不成功if(num==NULL||cpot==NULL)returnM