特殊矩阵的压缩与解压缩【特选材料】

课程名称: 数据结构课程设计课程设计题目: 特殊矩阵压缩与解压缩姓 名:院系: 计算机科学与技术学院 专 业: 计算机科学与技术 年 级: 2011级 学 号:指导教师: 王爱平2013 年 9月 14 日 目 录1 课程设计的目的32 需求分析3 3 课程设计报告内容3 3.1概要设计33.2详细设计33.3调试分析4 3.4用户手册4 3.5测试结果4 4 小结 4 5程序清单4 6 参考文献 157 程序截图 15 1.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析（1）对对称、三角、带状等特殊矩阵进行压缩，以节省存储空间。（2）对压缩后的矩阵进行解压缩3 特殊矩阵的压缩与解压缩的设计3.1概要设计压缩矩阵数据结构：typedef struct ElemType *elem;int amount;int bound;int w;int kind;SpecialMatrix;3.2详细设计int RandomArray(int aMAX, int kind, int *bound, int *w)/函数功能:随机生成一个特殊矩阵int InitMatrix(SpecialMatrix *Matrix, int kind, int bound, int w)/函数功能:压缩矩阵初始化void DestoryMatrix(SpecialMatrix *Matrix)/函数功能:销毁压缩矩阵void ArrayToMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:矩阵压缩void ArrayToSMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:对称矩阵压缩void ArrayToTMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:三角矩阵压缩void ArrayToBMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:带状矩阵压缩void MatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:特殊矩阵解压缩void SMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:对称矩阵解压缩void TMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:三角矩阵解压缩void BMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:带状矩阵解压缩void ShowMatrix(SpecialMatrix Matrix)/函数功能:显示压缩矩阵void ShowArray(int aMAX, int bound)/函数功能:显示初始矩阵3.3调试分析(略)3.4用户手册(略)3.5测试结果(略)4总结（略）5、程序清单:#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAX 18typedef int ElemType;typedef struct /压缩矩阵数据结构ElemType *elem;int amount;int bound;int w;int kind;SpecialMatrix;int RandomArray(int aMAX, int, int *, int *);int InitMatrix(SpecialMatrix *, int, int, int);void DestoryMatrix(SpecialMatrix *);void ArrayToMatrix(SpecialMatrix *, int aMAX);void ArrayToSMatrix(SpecialMatrix *, int aMAX);void ArrayToTMatrix(SpecialMatrix *, int aMAX);void ArrayToBMatrix(SpecialMatrix *, int aMAX);void ShowMatrix(SpecialMatrix);void ShowArray(int aMAX, int);void MatrixToArray(int aMAX, SpecialMatrix);void SMatrixToArray(int aMAX, SpecialMatrix);void TMatrixToArray(int aMAX, SpecialMatrix);void BMatrixToArray(int aMAX, SpecialMatrix);int main()int MMAXMAX, bound, w, kind, choase;SpecialMatrix Matrix;while(1)printf("*特殊矩阵压缩与解压缩*n");printf("1.压缩n");printf("2.解压缩n");printf("3.退出n");printf("请选择:");scanf("%d", &choase);switch(choase)case 1:printf("1.对称矩阵n");printf("2.三角矩阵n");printf("3.带状矩阵n");printf("4.退出n");printf("请选择:");scanf("%d", &kind);if(4 = kind)break;RandomArray(M, kind, &bound, &w);printf("随机生成的矩阵为:n");ShowArray(M, bound);InitMatrix(&Matrix, kind, bound, w);ArrayToMatrix(&Matrix, M);printf("矩阵压缩后:n");ShowMatrix(Matrix);printf("n");break;case 2:if(!Matrix.elem)printf("不存在Matrixn");break;printf("矩阵压缩内容为:n");ShowMatrix(Matrix);MatrixToArray(M, Matrix);printf("n解压后为:n");ShowArray(M, Matrix.bound);printf("n");break;case 3:exit(1);default: break;DestoryMatrix(&Matrix);return 0;int RandomArray(int aMAX, int kind, int *bound, int *w)/函数功能:随机生成一个特殊矩阵int i, j, r;time_t t;srand(unsigned)time(&t);if(kind < 1 | kind > 3)printf("输入有误!n");return 0;*w = 1;*bound = 0;while(1)*bound = rand()%MAX;if(*bound> 2)break;switch(kind)case 1:for(i=0; i<*bound; i+)for(j=0; j<=i; j+)r = rand()%20;aij = aji = r;break;case 2:*w = rand()%2+1;/生成随机数以控制上三角或下三角switch(*w)case 1:for(i=0; i<*bound; i+)for(j=0; j<*bound; j+)if(i >= j)r = rand()%20+1;aij = r;elseaij = 0;break;case 2:for(i=0; i<*bound; i+)for(j=0; j<*bound; j+)if(i <= j)r = rand()%20+1;aij = r;elseaij = 0;break;break;case 3:*w = rand()%(*bound)+1;while(0 = (*w)%2)*w = rand()%*bound+1;for(i=0; i<*bound; i+)for(j=0; j<*bound; j+)if(j>=(i-(*w/2) && j<=(i+(*w/2)r = rand()%20+1;aij = r;elseaij = 0;break;return 1;int InitMatrix(SpecialMatrix *Matrix, int kind, int bound, int w)/函数功能:压缩矩阵初始化if(kind<1 | kind>3 | bound<1 | bound >100 | w<1 | w>bound)printf("输入有误, 重新输入n");return 0;elseMatrix->kind = kind;Matrix->bound = bound;Matrix->w = w;switch(kind)case 1:Matrix->amount = (bound*(bound+1)/2;break;case 2:Matrix->amount = (bound*(bound+1)/2;break;case 3:Matrix->amount = bound*bound-(bound-1-w/2)*(bound-w/2);printf("%d", Matrix->amount);break;if(!(Matrix->elem = (ElemType *)malloc(Matrix->amount*sizeof(ElemType)return 0;return 1;void DestoryMatrix(SpecialMatrix *Matrix)/函数功能:销毁压缩矩阵free(Matrix->elem);Matrix->bound = 0;Matrix->amount = 0;Matrix->kind = 0;Matrix->w = 0;void ArrayToMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:矩阵压缩switch(Matrix->kind)case 1:ArrayToSMatrix(Matrix, a);break;case 2:ArrayToTMatrix(Matrix, a);break;case 3:ArrayToBMatrix(Matrix, a);break;void ArrayToSMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:对称矩阵压缩int i, j, k;for(i=1; i<=Matrix->bound; i+)for(j=1; j<=i; j+)k = (i-1)*i/2+j-1;Matrix->elemk = ai-1j-1;void ArrayToTMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:三角矩阵压缩int i, j, k;switch(Matrix->w)case 1:for(i=1; i<=Matrix->bound; i+)for(j=1; j<=i; j+)k = (i-1)*i/2+j-1;Matrix->elemk = ai-1j-1;break;case 2:for(j=1; j<=Matrix->bound; j+)for(i=1; i<=j; i+)k = (j-1)*j/2+i-1;Matrix->elemk = ai-1j-1;break;void ArrayToBMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:带状矩阵压缩int i, j, k = 0;for(i=1; i<=Matrix->bound; i+)for(j=1; j<=Matrix->bound; j+)if(j>=(i-Matrix->w/2) && j<=(i+Matrix->w/2)Matrix->elemk+ = ai-1j-1;void MatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:特殊矩阵解压缩switch(Matrix.kind)case 1:SMatrixToArray(a, Matrix);break;case 2:TMatrixToArray(a, Matrix);break;case 3:BMatrixToArray(a, Matrix);break;void SMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:对称矩阵解压缩int i, j, k, flag;for(k=0; k<Matrix.amount; k+)for(i=1; i<=Matrix.bound; i+)flag = 0;for(j=1; j<=i; j+)if(k = (i-1)*i/2+j-1)ai-1j-1 = aj-1i-1 = Matrix.elemk;flag = 1;break;if(1 = flag)break;void TMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:三角矩阵解压缩int i, j, k = 0;switch(Matrix.w)case 1:for(i=1; i<=Matrix.bound; i+)for(j=1; j<=Matrix.bound; j+)if(i>=j)ai-1j-1 = Matrix.elemk+;elseai-1j-1 = 0;break;case 2:for(j=1; j<=Matrix.bound; j+)for(i=1; i<=Matrix.bound; i+)if(i<=j)ai-1j-1 = Matrix.elemk+;elseaj-1i-1 = 0;break;void BMatrixToArray(int aMAX, SpecialMatrix Matrix)/函数功能:带状矩阵解压缩int i, j, k = 0;for(i=1; i<=Matrix.bound; i+)for(j=1; j<=Matrix.bound; j+)if(j>=(i-Matrix.w/2) && j<=(i+Matrix.w/2)ai-1j-1 = Matrix.elemk+;elseai-1j-1 = 0;void ShowMatrix(SpecialMatrix Matrix)/函数功能:显示压缩矩阵int i;for(i=0; i<Matrix.amount; i+)printf("%-3d", Matrix.elemi);if(i%Matrix.bound = Matrix.bound-1)printf("n");void ShowArray(int aMAX, int bound)/函数功能:显示初始矩阵int i, j;for(i=0; i<bound; i+)for(j=0; j<bound; j+)printf("%3d", aij);printf("n");6、参考文献1 严蔚敏，吴伟民 编著. 数据结构(C 语言版)-北京: 清华大学出版社，2007.2 严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)-北京: 清华大学出版社， 2007.3网上搜索相关程序作为参考7、程序运行结果运行截图18材料a