特殊矩阵压缩与解压缩设计

数据结构课程设计

课程名称:《数据结构》课程设计 课程设计题目: 特殊矩阵压缩与解压 缩设计

姓名:XXX

院系:计算机学院

专业:10级计算机科学技术 学号:XXXXXXXXX

指导教师:XXX

2012年9月 21日

数据结构课程设计

目录

1 课程设计的目的 3

2需求分析 3

3 课程设计报告内容 3

3.1 概要设计 3

3.2 详细设计 4

3.3 调试分析 4

3.4 用户手册 4

3.5 程序清单 5

3.6 测试结果 9

4 小结 15

5 参考文献 15

数据结构课程设计

1.课程设计的目的

(1) 熟练使用 C 语言编写程序，解决实际问题;

(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;

(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;

(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;

2.需求分析

本系统主要实现对特殊矩阵的压缩与解压缩处理，特殊矩阵包括：对称矩阵、上三角矩阵、下三角矩阵、带状矩阵。

3.课程设计报告内容

3.1概要设计

1.函数

①主函数：main( )

②矩阵的输出函数：Print( )

③对称矩阵的压缩与解压缩函数：DuiMatrix( )

④上三角矩阵的压缩与解压缩函数：ShangMatrix( )

⑤下三角矩阵的压缩与解压缩函数：XiaMatrix( )

⑥带状矩阵的压缩与解压缩函数：DaiMatrix( )

3.2详细设计

数据结构课程设计

以对称矩阵为例：对称矩阵的特点是：aij=aji，即元素关于主对角线对称，因此只需存储上三角或下三角部分即可。这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元。对下三角部分以行为主序顺序存储到一个一维数组中，在下三角中共有n*(n+1)/2 个元素，因此，存储到数组a[n(n+1)/2]中，k=i*(i-1)/2+j-1 ，若i<j，则aij 是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij 时则去访问和它对应的下三角中的aji 即可。

3.3调试分析

程序的设计严格遵循模块化的程序设计思想，由简单到复杂，注意规范。

3.4用户手册

用户在使用程序时应按照提示执行，步骤如下：

①进入系统后，您将看到提示：

“请选择您要生成的矩阵类型:”

“1.对称矩阵!”

“2.上三角矩阵!”

“3.下三角矩阵!”

“4.带状矩阵!”

“输入其他键退出系统!”

②选择1号功能键：输入一个n阶对称矩阵，系统会先进行压缩操作，将此矩阵压缩到一个一维数组，然后再由此数组进行解压缩操作。 ③选择2号功能键：输入一个n阶上三角矩阵，系统会先进行压缩操

数据结构课程设计

作，将此矩阵压缩到一个一维数组，然后再由此数组进行解压缩操作。④选择3号功能键：输入一个n阶下三角矩阵，系统会先进行压缩操作，将此矩阵压缩到一个一维数组，然后再由此数组进行解压缩操作。 ⑤选择4号功能键：输入一个n阶带状矩阵，系统会先进行压缩操作，将此矩阵压缩到一个一维数组，然后再由此数组进行解压缩操作。 ⑥输入其他键系统退出系统。

3.5程序清单

#include<stdio.h>

#define MAX 100

int M[MAX][MAX],a[MAX];

void Print(int n)

{

int i,j;

printf("生成的矩阵如下:\n");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

printf("%-3d",M[i][j]);

printf("\n");

}

}

void DuiMatrix()

{

int i,j,k,n;

printf("请输入您要压缩矩阵的维数:\n");

scanf("%d",&n);

printf("请依次输入矩阵的元素:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

scanf("%d",&M[i][j]);

if(i>=j)

数据结构课程设计

k=i*(i-1)/2+j-1;

else

k=j*(j-1)/2+i-1;

a[k]=M[i][j];

}

Print(n);

printf("此对称矩阵压缩存储生成的一维数组如下:\n");

for(k=0;k<n*(n+1)/2;k++)

printf("a[%d]=%-3d\n",k,a[k]);

printf("元素的解压操作如下:\n");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

if(i>=j)

k=i*(i-1)/2+j-1;

else

k=j*(j-1)/2+i-1;

printf("T[%d][%d]=%-3d",i,j,a[k]);

}

printf("\n");

}

}

void ShangMatrix()

{

int i,j,k,n;

printf("请输入您要压缩矩阵的维数:\n");

scanf("%d",&n);

printf("请依次输入矩阵的元素:\n");

for(i=1;i<n+1;i++)

for(j=1;j<n+1;j++)

{

scanf("%d",&M[i][j]);

if(i<=j)

k=j*(j-1)/2+i-1;

else

k=n*(n+1)/2;

a[k]=M[i][j];

}

Print(n);

printf("此上三角矩阵压缩存储生成的一维数组如下:\n");

for(k=0;k<n*(n+1)/2+1;k++)

数据结构课程设计

printf("a[%d]=%-3d\n",k,a[k]);

printf("元素的解压操作如下:\n");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

if(i<=j)

k=j*(j-1)/2+i-1;

else

k=n*(n+1)/2;

printf("T[%d][%d]=%-3d",i,j,a[k]);

}

printf("\n");

}

}

void XiaMatrix()

{

int i,j,k,n;

printf("请输入您要压缩矩阵的维数:\n");

scanf("%d",&n);

printf("请依次输入矩阵的元素:\n");

for(i=1;i<n+1;i++)

for(j=1;j<n+1;j++)

{

scanf("%d",&M[i][j]);

if(i>=j)

k=i*(i-1)/2+j-1;

else

k=n*(n+1)/2;

a[k]=M[i][j];

}

Print(n);

printf("此下三角矩阵压缩存储生成的一维数组如下:\n");

for(k=0;k<n*(n+1)/2+1;k++)

printf("a[%d]=%-3d\n",k,a[k]);

printf("元素的解压操作如下:\n");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

if(i>=j)

数据结构课程设计

k=i*(i-1)/2+j-1;

else

k=n*(n+1)/2;

printf("T[%d][%d]=%-3d",i,j,a[k]);

}

printf("\n");

}

}

void DaiMatrix()

{

int i,j,k=0,n,m;

int b[MAX],c[MAX],T[MAX][MAX];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

T[i][j]=0;

printf("请输入您要压缩矩阵的维数:\n");

scanf("%d",&n);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

T[i][j]=0;

printf("请依次输入矩阵的元素:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

scanf("%d",&M[i][j]);

if(M[i][j]!=0)

{

a[k]=M[i][j];

b[k]=i;

c[k]=j;

k++;

}

}

m=k;

Print(n);

printf("此带状矩阵压缩存储生成的一维数组如下:\n");

for(k=0;k<m;k++)

printf("a[%d]=%-3d\n",k,a[k]);

printf("元素的解压操作如下:\n");

for(k=0;k<m;k++)

{

i=b[k];

j=c[k];

数据结构课程设计

T[i][j]=a[k];

}

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

printf("T[%d][%d]=%-3d",i,j,T[i][j]);

printf("\n");

}

}

int main()

{

int n;

while(1)

{

printf("请选择您要生成的矩阵类型:\n\n");

printf("1.对称矩阵!\n");

printf("2.上三角矩阵!\n");

printf("3.下三角矩阵!\n");

printf("4.带状矩阵!\n");

printf("\n输入其他键退出系统!\n");

scanf("%d",&n);

if(n==1)

DuiMatrix();

else if(n==2)

ShangMatrix();

else if(n==3)

XiaMatrix();

else if(n==4)

DaiMatrix();

else

{printf("成功退出系统!\n");break;}

}

return 0;

}

3.6测试结果

测试数据如下：

对称矩阵： 1 2 3 4

2 5 6 7

数据结构课程设计

3 6 8 8

4 7 8 10

上三角矩阵：1 2 3 4 5

0 6 7 8 9

0 0 10 11 12

0 0 0 13 14

0 0 0 0 15

下三角矩阵：1 0 0 0 0

2 3 0 0 0

4 5 6 0 0

7 8 9 10 0

11 12 13 14 15

带状矩阵：1 2 0 0 0

3 4 5 0 0

0 6 7 8 0

0 0 9 10 0

0 0 0 0 11

①程序开始界面。

数据结构课程设计

②输入数字键1，生成一个4阶对称矩阵，先进行压缩操作，再进行解压缩操作。

数据结构课程设计

行解压缩操作。

数据结构课程设计

行解压缩操作。

数据结构课程设计

解压缩操作。

⑥输入其他键，退出系统。

。

数据结构课程设计

4.小结

在数据结构课程设计的过程中，我不仅认识到了学好解理论知识的必要性，更认识到了上机操作的重要性。上机操作能过培养我们解决实际问题的能力，通过对上机操作遇到的各种问题的解决，自己感到一丝成功的同时，更下决心努力学好专业课，为以后的学习及实践打下好的基础。

5.参考文献

①严蔚敏，吴伟民 编著. 数据结构(C 语言版)--北京: 清华大学出版社，2007.