特殊矩阵的压缩与解压缩

1、课程名称: 数据结构课程设计课程设计题目: 特殊矩阵压缩与解压缩姓 名:院系: 计算机科学与技术学院 专 业: 计算机科学与技术 年 级: 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) 初步掌握软件开发过程的问

2、题分析、系统设计、程序编码、测试等基本方法和技能;(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)/函数功能:随机生成一个特殊矩阵i

3、nt 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, in

4、t 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 aM

5、AX, SpecialMatrix Matrix)/函数功能:带状矩阵解压缩void ShowMatrix(SpecialMatrix Matrix)/函数功能:显示压缩矩阵void ShowArray(int aMAX, int bound)/函数功能:显示初始矩阵3.3调试分析(略)3.4用户手册(略)3.5测试结果(略)4总结（略）5、程序清单:#include #include #include #define MAX 18typedef int ElemType;typedef struct /压缩矩阵数据结构ElemType *elem;int amount;int bound;i

6、nt 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

7、 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 MMA

8、XMAX, 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,

9、 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);Sho

10、wArray(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 3)printf(输入有误!n);return 0;*w = 1;*bound = 0;while(1)*bound = rand()%MAX;if

11、(*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= 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

12、= 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=(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

13、(kind3 | bound100 | wbound)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-

14、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)/函数功能:矩阵压缩swit

15、ch(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; ibound; i+)for(j=1; jelemk = ai-1j-1;void ArrayToTMatrix(SpecialMatrix *Matrix, int

16、 aMAX)/函数功能:三角矩阵压缩int i, j, k;switch(Matrix-w)case 1:for(i=1; ibound; i+)for(j=1; jelemk = ai-1j-1;break;case 2:for(j=1; jbound; j+)for(i=1; ielemk = ai-1j-1;break;void ArrayToBMatrix(SpecialMatrix *Matrix, int aMAX)/函数功能:带状矩阵压缩int i, j, k = 0;for(i=1; ibound; i+)for(j=1; jbound; j+)if(j=(i-Matrix-w

17、/2) & jw/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)/函数功能:对称矩阵解压缩in

18、t i, j, k, flag;for(k=0; kMatrix.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=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+;els