本文共 6580 字，大约阅读时间需要 21 分钟。
特殊矩阵的存储压缩及解压
#define _CRT_SECURE_NO_WARNINGS#define EMPTY_QUEUE_ERROR -999999#include#include #include #include #include #define MAXLEN 100typedef int ElemType;//形如对称矩阵、三角矩阵等特殊形式的矩阵，只需保存其中的部分元素即可，称为“压缩存储”。关键是建立矩阵中元素的 行列 索引与 一维数组 存储空间 索引之间的关联关系。//（17）对称矩阵//（18）矩阵结构体的定义//定义一个压缩矩阵的结构体类型，用一维数组来存储矩阵中的元素。为了简单起见，令矩阵为DIM* DIM的方阵。其中，DIM为一确定的整数大小。#define MAXLEN 100#define DIM 4typedef struct { int elem[MAXLEN]; // 用来存 特殊矩阵 里的元素的 一维数组}intCompressedMatrix;/*压缩矩阵就是由一个矩阵压缩成一维数组,而非一般意义的矩阵*//*matrix /'meɪtrɪks/n.矩阵*//*（19）对称矩阵的初始化与读取用一个对称矩阵(定义为m[DIM][DIM]) 来初始化(填充) 该压缩矩阵压缩:*/void InitSMatrix(intCompressedMatrix* pMat, int m[DIM][DIM]){ /********************************************************** 将存放于二维数组m中的对称矩阵下三角元素存放到pMat中 *********************************************************/ int index = 0; for (int i = 1; i <= DIM; i++) // 对每一行 for (int j = 1; j <= i; j++) // 对每一列中的部分元素(下三角,包括对角线上的元素) pMat->elem[index++] = m[i - 1][j - 1];/*注意,指示行和列的视情况而定,一定要转化为从0开始计数的来访问数组元素*/}//该函数正确.// 读取(对称矩阵的压缩矩阵中解压出来(一次一个元素),将值保存到x中.)int Get(intCompressedMatrix* pMat, int i, int j, int* x){ // 判断i, j是否合法 if ((i<1 || i> DIM) || (j<1 || j> DIM)) { printf("行或列索引非法，赋值失败\n"); return 0; } /* 给x赋值 由于只保存了i>=j的下三角，如果欲读取j>i的上三角元素，怎么读取？*/ if (i >= j) *x = pMat->elem[(i-1) * ((i-1) + 1) / 2 + j - 1]; else *x = pMat->elem[(j - 1) * ((j - 1) + 1) / 2 + i - 1]; return 1;}//函数已修正./*（20）三角矩阵的存取(重复元素集中在某一侧)("三角"分为上三角和下三角)对三角矩阵进行压缩存储，写出与上述对称矩阵类似的 结构体和操作函数。*/int InitSMatrix_triangle_down(intCompressedMatrix* pMat, int(*m)[DIM]){ int index = 1;/*index = 0 的位置保留用于存储重复的元素,一般时三角矩阵的某个顶点)*/ for (int i = 1; i <= DIM; i++) { for (int j = 1; j <= i; j++)/*这个二重循环扫描下三角矩阵.((三角遍历)*/ { pMat->elem[index++] = m[i - 1][j - 1]; printf("%d ", pMat->elem[index-1]); } printf("\n"); } pMat->elem[0] = m[0][DIM - 1];}/*传入原始矩阵的任意位置(i,j)*/int Get_triangle_down(intCompressedMatrix* pMat,int i,int j,int *x){ /*编写前先设计好算法:而框架则可以编码搭建*/ /*判断要解压的元素位置是否合法*/ if ((i<1 || i> DIM) || (j<1 || j> DIM)) { printf("行或列索引非法，赋值失败\n"); return 0; } int subscript_row = i - 1, subscript_col = j - 1; if (i >= j) { *x = pMat->elem[subscript_row * (subscript_row + 1) / 2 + subscript_col + 1]; } else { *x = pMat->elem[0]; } return 1;/*读取成功*/}/*分析上三角:(内存循环收缩左边界)*//*将上三角矩阵压缩到pMat矩阵(或者说一维数组)中*/int InitSMatrix_triangle_up(intCompressedMatrix* pMat, int m2_2[][DIM]){ int index = 1;/*保留elem[0]*/ /*上三角遍历*/ for (int i = 1; i <= DIM; i++) { for (int j = i; j <= DIM; j++) { pMat->elem[index++] = m2_2[i - 1][j - 1]; printf("%d ", pMat->elem[index-1]); } printf("\n"); } pMat->elem[0] = m2_2[DIM-1][0];}/*解压公式:F(i,j) = (i-1)*row+j -(i-1)*((i-1) + 1) / 2;*//*参数变量x是原矩阵中的元素,映射F(i,j)求得的是原矩阵中(i,j)位置的元素在压缩矩阵中的下标值.*/int Get_triangle_up(intCompressedMatrix* pMat, int i, int j, int* x){ /*请求解压的位置合法性(分为行与列)*/ if ((i<1 || i>DIM) || (j<1 || j>DIM)) { printf("行或列索引非法，赋值失败\n"); return 0; } if(i<=j) { *x = pMat->elem[(i - 1) * DIM + j - (i - 1) * i / 2]; } else { *x = pMat->elem[0]; } return 1;}/*（21）对角矩阵的存取(重复元素分布在对角线两侧)(一般说明是n对角矩阵) 对 对角矩阵进行压缩存储，写出与上述对称矩阵类似的结构体和操作函数。*/ //对角矩阵的重复元素保存在数组的第[0]位置上./*对角矩阵的压缩没有涉及公式*/int InitSMatrix_tri_diagonal(intCompressedMatrix* pMat, int(*m3)[DIM])/*diagonal /daɪ'æɡənl/ adj.对角线的, 斜的,*/{ /*对角遍历*/ int index = 1; for (int i = 1; i <= DIM; i++) { for (int j = i - 1; j <= i+1; j++)//默认每行读取三个元素 { if (j<1 || j > DIM) { continue; } pMat->elem[index++] = m3[i - 1][j - 1];/*i,j的取值控制由两重循环实现控制,到访问数组元素前,位置参量i,j都是从1开始,在访问时均减去1再访问.*/ printf("%d ", pMat->elem[index -1]); }//for printf("\n"); }//for pMat->elem[0] = m3[0][DIM - 1];}/*解压对三角矩阵,从elem[]数组中解压出来.(访问指定的原矩阵中的第i行,第j列位置上的元素.)涉及两个基础公式,合并成第三个公式.:前i-1行的元素个数:3(i-1)-1 (其中因子3是n对角矩阵n=3时的特例)a(i,j)是第i行对角线区域的第 (j-i)+2 个元素(2是n对角矩阵n=3下的线性关系的修正因子)*/int Get_tri_diagonal(intCompressedMatrix* pMat, int i, int j, int* x){ if ((i<1 || i > DIM) || (j<1 || j > DIM)) { printf("行或列索引非法，赋值失败\n"); return 0; } if (j >= i - 1 && j <= i + 1)/*只访问对角线和他相邻的两条平行线上的元素,其余元素由else统一处理.*/ { *x = pMat->elem[2*(i) + (j) - 2];//这里的公式已经时按i,j从1计数的方式计算的 } else { *x = pMat->elem[0];/*重复部分的矩阵填充*/ } return 1;}/*（22）调试根据上述压缩矩阵定义，完成下面代码，运行并调试程序。*//*填充二维数组函数fill_two_dimenssion_array(int (*arr_2)[DIM])*/void fill_two_dimenssion_array(int(*arr_2)[DIM]){ printf("创建并填充二维数组:\n"); for (int i = 0; i < DIM; i++) { for (int j = 0; j < DIM; j++) { scanf("%d", &arr_2[i][j]); } }}/*（22）调试根据上述压缩矩阵定义，完成下面代码，运行并调试程序。*//*填充二维数组函数fill_two_dimenssion_array(int (*arr_2)[DIM])*/void fill_two_dimenssion_array(int(*arr_2)[DIM]){ printf("创建并填充二维数组:\n"); for (int i = 0; i < DIM; i++) { for (int j = 0; j < DIM; j++) { scanf("%d", &arr_2[i][j]); } }}int main(){ int x = 0; // 定义一个二维数组m1并初始化为对称矩阵形式 int m1[DIM][DIM] /*= {{1,0,0,6},{0,2,7,0},{0,7,3,8},{6,0,8,4} }*/;//初始化而非赋值,如果不直接初始化的话,第一个乃至每个维数都不可省略; int m2[DIM][DIM] /*= {{1,0,0,0},{0,2,0,0},{0,7,3,0},{6,0,8,4} }*/; int m2_2[DIM][DIM] /*= {{1,4,5,7},{0,2,0,3},{0,0,3,5},{0,0,0,4} }*/; int m3[DIM][DIM] /*= {{1,4,0,0},{4,2,9,0},{0,6,3,5},{0,0,1,4} }*/; // 定义一个 压缩矩阵mat，并用m1初始化mat intCompressedMatrix mat;/*压缩处理后的数组保存于此*/ printf("执行压缩处理:\n"); /* */ fill_two_dimenssion_array(m1); printf("压缩对称矩阵:\n"); InitSMatrix(&mat, m1); /* fill_two_dimenssion_array(m2); printf("压缩三角矩阵:\n"); InitSMatrix_triangle_down(&mat, m2);*/ /*fill_two_dimenssion_array(m2_2); printf("压缩上三角矩阵:\n"); InitSMatrix_triangle_up(&mat, m2_2);*/ /* fill_two_dimenssion_array(m3); printf("压缩对三角矩阵:\n"); InitSMatrix_tri_diagonal(&mat, m3);*/ // 打印该mat printf("解压并打印mat矩阵\n"); /*解压并打印:(全遍例)*/ for (int i = 1; i <= DIM; i++) { for (int j = 1; j <= DIM; j++) { /*根据mat压缩矩阵 解压*/ Get(&mat, i, j, &x);//对称矩阵 // Get_triangle_down(&mat, i, j, &x);//下三角矩阵 //Get_triangle_up(&mat, i,j,&x); //Get_tri_diagonal(&mat, i, j, &x); printf("%d ", x); } printf("\n"); }}
转载地址：http://jnzt.baihongyu.com/