数据结构-矩阵的压缩存储程序

实验报告

课程名：数据结构（实验名：矩阵的压缩存储姓 名：班 级：学 号：时 间：

Word 文档

C语言版）

2014.11.23

.

一 实验目的与要求

1. 掌握并实现稀疏矩阵的压缩存储的方法 2. 在该存储方法上实现矩阵的操作 二 实验内容

• 判断一个用二维数组存储的矩阵是不是稀疏矩阵 • 将其转化为压缩存储的形式

• 在压缩存储上实现矩阵的乘法和转置操作 三 实验结果与分析 压缩转置程序： #include

//判断该矩阵是否为稀疏矩阵

#define m 10 #define n 10 int a[m][n]={

{1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,7,0},

Word 文档

.

{0,0,0,0,0,0,8,0,0,0}, {0,0,0,0,0,0,0,0,0,0},

};

struct three { };

struct three stu[100];

struct three1 { };

struct three1 stu1[100];

int jiance() {

int x=0;//赋初值为0 for(x=0;x<=99;x++) { int i,j; int value; int i,j; int value;

Word 文档

Word 文档 .

stu[x].value=0;

}

float t=0; float v;

for(int i=0;it++;

}

}

if((v=t/(m*n))<=0.05) { printf(\"该矩阵为稀疏矩阵%f\\n\ return 1;

} else { printf(\"该矩阵不是稀疏矩阵\\n\"); return 0;

}

.

}

void yasuo() { }

void display() {

int t=0;

for(int r=0;rfor(int c=0;cif(a[r][c]!=0) { }

stu[t].i=r; stu[t].j=c;

stu[t].value=a[r][c]; t++;

Word 文档

.

}

int x=0;

printf(\"压缩矩阵的三元组为:\\n\"); for(x=0;x<=99;x++) { }

printf(\"\\n\");

if(stu[x].value==0) break;

printf(\"{%d,%d,%d} \

void zhuanzhi() {

int x=0;//赋初值为0 int t=0;

int num[10]={0,0,0,0,0,0,0,0,0,0};//每一列非0的数目 for(x=0;x<=99;x++) { }

for(int j=0;jfor(int i=0;istu1[x].value=0;

Word 文档

.

}

}

if(a[i][j]!=0) { }

num[j]++; t++;

int cpot[10]={0,0,0,0,0,0,0,0,0,0}; cpot[0]=0; for(j=1;jfor(int k=0;kcol=stu[k].j; q=cpot[col]; stu1[q].i=stu[k].j; stu1[q].j=stu[k].i;

stu1[q].value=stu[k].value; cpot[j]=cpot[j-1]+num[j-1];

Word 文档

.

}

}

++cpot[col];

void display1() { }

void display2() {

int d,b;

for(d=0;dfor(b=0;bprintf(\"转置以后的三元组为:\\n\"); for(x=0;x<=99;x++) { }

printf(\"\\n\");

if(stu1[x].value==0) break;

printf(\"{%d,%d,%d} \

Word 文档

.

}

}

}

printf(\"%d \

printf(\"\\n\");

void main() { }

display2(); if(jiance()==1) { }

yasuo(); display(); zhuanzhi(); display1();

Word 文档

.

图1：压缩转置程序运行结果

矩阵的乘法程序： #include #define m1 3 #define n1 4 #define m2 4 #define n2 2 int a1[m1][n1]={

{3,0,0,5}, {0,-1,0,0}, {2,0,0,0},

};

int a2[m2][n2]={

{0,2}, {1,0},

Word 文档

.

{-2,4}, {0,0},

};

struct three1 { };

struct three1 stu1[100];

struct three2 { };

struct three2 stu2[100];

struct three3 { };

int i,j; int value; int i,j; int value; int i,j; int value;

Word 文档

.

struct three3 stu3[100]; int ar1pos[m1]={0}; int ar2pos[m2]={0}; int Qrpos[m1];

int yasuo1() {

int t=0; ar1pos[0]=0; for(int r=0;rfor(int c=0;cif(a1[r][c]!=0) { }

stu1[t].i=r; stu1[t].j=c;

stu1[t].value=a1[r][c]; t++;

Word 文档

.

}

}

ar1pos[r+1]=t;

return t;

int yasuo2() {

int t=0; ar2pos[0]=0; for(int r=0;rfor(int c=0;car2pos[r+1]=t;

if(a2[r][c]!=0) { }

stu2[t].i=r; stu2[t].j=c;

stu2[t].value=a2[r][c]; t++;

Word 文档

.

}

} return t;

void chengfa(int x1,int x2) {

int a1m=0; int a2m=0; int tp,p,br,t,q,ccol; int qtu=0;

for(a1m=0;a1mint ctemp[m1]={0}; if(a1m<(m1-1))

tp=ar1pos[a1m+1];

else{tp=x1;}

for(p=ar1pos[a1m];pbr=stu1[p].j; if(br<(m2-1))

t=ar2pos[br+1];

else{t=x2;}

Word 文档

.

}

}

}

for(q=ar2pos[br];qccol=stu2[q].j;

ctemp[ccol]+=stu1[p].value*stu2[q].value;

for(ccol=0;ccolif(ctemp[ccol]!=0) { }

stu3[qtu].i=a1m; stu3[qtu].j=ccol;

stu3[qtu].value=ctemp[ccol]; ++qtu;

void display() {

int x=0;

printf(\"a1与a2乘积之后的三元组是：\\n\"); for(x=0;x<=99;x++) {

Word 文档

.

}

}

if(stu3[x].value==0) break;

printf(\"{%d,%d,%d} \

printf(\"\\n\");

void display1() {

int m,n;

printf(\"a1矩阵为：\\n\"); for(m=0;mprintf(\"a2矩阵为：\\n\"); for(m=0;mfor(n=0;nfor(n=0;nprintf(\"\\n\");

printf(\"%d \

Word 文档

.

}

}

}

printf(\"%d \

printf(\"\\n\");

void main() { }

int a; int x1,x2; display1(); x1=yasuo1(); x2=yasuo2(); chengfa(x1,x2); display();

图2：矩阵的乘法程序程序运行结果

Word 文档