二维数组的压缩存储矩阵

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