二维数组的压缩存储矩阵

1/6数据结构实验报告学号：2015111898姓名：许明华专业：计算机科学与技术知识范畴：数组与广义表完成日期：2017年04月21日实验题目：基于压缩存储的半三角矩阵乘法运算的实现实验内容及要求：已知两个n阶下半三角矩阵的乘积仍为n阶下半三角矩阵。编程输入两个n阶下半三角矩阵，输出这两个矩阵的乘积。要求n阶下半三角矩阵采用一维数组压缩存储（即只存储下半三角）。程序先从键盘(或字符文件)输入n值，建立三个矩阵的一维数组动态存储结构，然后从键盘(或字符文件)输入两个半三角矩阵，最后输出计算结果到屏幕上(或另一个字符文件中)。例如：键盘输入为：3123456-1-2-3-4-5-6则输出为：-1-8-9-38-45-36实验目的：掌握半三角矩阵的顺序存储结构。数据结构设计简要描述：序言：这是本学期第五个实验，本实验是要求我们将两个二维半三角矩阵压缩存储为一维矩阵，并对其进行乘法操作，得到一个一维的压缩存储矩阵，并将其打印输出；数据结构简单设计：本实验主要可分为两个大的模块（压缩存储矩阵、压缩矩阵相乘）。第一，我们通过键盘键入一个数组的阶数，然后输入两个半三角矩阵，，但是这两个半三角矩阵要进行压缩存储为一维矩阵，关键操作即（m=（i*（i+1））/2+j），即可将二维下标转化为一维下标；第二，运用公式i]][[*]][[jjkbkia来进行相乘操作，求得两个下三角矩阵的乘积。算法设计简要描述：评分满分——5分2/61，通过（m=（i*（i+1））/2+j）将二维下标转化为一维下标进行输入，得到压缩存储矩阵；2，运用公式i]][[*]][[jjkbkia进行乘积操作，但是乘数矩阵下标和结果矩阵的下标并没有同步，所以运用三个公式来进行分离操作，m1=（i*（i+1））/2+k；m2=(k*（k+1））/2+j；m=（i*（i+1））/2+j；c[m]+=a[m1]*b[m2];这样即能实现相乘的操作，但是每一次的c[m]没有进行初始化，所以在每一次得到m值后，进行操作c[m]=0;输入/输出设计简要描述：输入：1，输入下三角存储矩阵的阶数n；2，输入第一个下三角矩阵，如123456；3，输入第二个下三角矩阵，如-1-2-3-4-5-6；输出：1，输入2操作后，按存储矩阵格式输出打印第一个下三角矩阵；2，输入3操作后，按存储矩阵格式输出打印第二个下三角矩阵，并输出打印两个矩阵的乘积矩阵编程语言说明：1，编程软件，CodeBlocks16.0；2，代码均用C语言实现；3，输入输出采用C语言的printf和scanf函数；4，程序注释采用C/C++规范；主要函数说明：voidinput_Arr(int,int);//输入半三角矩阵声明voidprint(int,int);//输出打印半三角矩阵声明intprint_Array(int,int,int,int);//两个半三角矩阵的乘法运算声明程序测试简要报告：见截图：3/6源程序代码：#includestdio.h//函数声明部分voidinput_Arr(int,int);//输入半三角矩阵声明voidprint(int,int);//输出打印半三角矩阵声明intprint_Array(int,int,int,int);//两个半三角矩阵的乘法运算声明//输入半三角矩阵voidinput_Arr(inta[],intn){intm;printf(请输入数组：\n);for(inti=0;in;i++){for(intj=0;j=i;j++)//这里在存储时我只存储了下三角对应的数组元素，，所以是j=i,而不是jn{m=(i*(i+1))/2+j;//这一步操作是关键所在，因为要将二维数组压缩存储为一维数组的话，我们来看，//二维数组的下标为i和j，但是一维数组的下标只有一个，怎么办呢，//这时候我们就可以根据公式来将二维数组的下标转化为对应的一维数组的下标，所得到的就是对应位置的对应下标scanf(%d,&a[m]);//输入对应的下三角矩阵4/6}}}//输出打印半三角矩阵voidprint(inta[],intn){intm=0;for(inti=0;in;i++){for(intj=0;j=i;j++){m=(i*(i+1))/2+j;//打印操作，同上面printf(%d,a[m]);}printf(\n);}}//两个半三角矩阵的乘法运算intprint_Array(inta[],intb[],intc[],intn){inti=0,j=0;intk,m,m1,m2;//k为进行乘法操作过程的中间变量，m为乘积过后的一维压缩数组的下标，m1为第一个数组的压缩存储的下标，m2为第二个数组的压缩存储的下标for(i=0;in;i++){for(j=0;j=i;j++)//限定在下三角元素中进行{m=(i*(i+1))/2+j;//将二维下标转化为压缩存储的一维下标c[m]=0;//这一步很重要，我想了很久才想到这一步的，就是每一次将c[m]的初值赋为0，因为后面要执行c[m]+=操作，如果不仅赋初值的话，每次的第一个c[m]就是没有进行初始化，//那它就是一个无穷大的数，得出来的乘积之和就是一个无穷大的数for(k=j;k=i;k++)//由于是下三角进行相乘，所以所有的上三角元素都为零，不需要再进行乘积操作，{5/6m1=(i*(i+1))/2+k;//第一个压缩存储的数组的一维下标m2=(k*(k+1))/2+j;//第二个压缩存储的数组的一维下标c[m]+=a[m1]*b[m2];//进行乘积操作}}}return0;}intmain(){intn;//数组长度ninta[100],b[100],c[100];//定义三个一维数组printf(请输入数组大小n：\n);scanf(%d,&n);input_Arr(a,n);//调用输入下三角矩阵函数printf(数组一为：\n);print(a,n);//输出下三角矩阵input_Arr(b,n);//同上printf(数组二为：\n);print(b,n);//同上print_Array(a,b,c,n);//调用下三角矩阵相乘函数printf(数组的乘积为：\n);print(c,n);//输出相乘之后的下三角矩阵6/6return0;}