数据结构稀疏矩阵基本运算实验报告

课程：数据结构

题目：稀疏矩阵4 三元组单链表 结构体(行数、列数、头 矩阵运算 重载运算符 优

班级：

姓名：

学号：

设计时间：2010年1月17日——2010年5月XX日

成绩：

指导教师：楼建华

)

一、题目

题目 稀疏矩阵4 结构 三元组单链表 表示 结构体(行数、列数、头) 回传方式 重载运算符 操作 矩阵运算 二、概要设计

1.存储结构

typedef struct{ int row,col;//行，列

datatype v;//非0数值 }Node;

typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m行，n列，t非0数个数 }Matrix; 矩阵a 非零数值data[1] 非零数值data[2]

行数m 列数n 头h 行r 列c 值d 行r 列c 值d … m n Data[max] → row col v－→ row col v－→ …

2.基本操作

⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法

⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆

三、详细设计 （1）存储要点

position[col]=position[col-1]+num[col-1];

三元组表(row，col，v) 稀疏矩阵（（行数m，列数n，非零元素个数t），三元组，...，三元组）

row col v A->data[0] 0 4 8 1 1 0 1 2 1 2 3 3 2 1 2 4 3 0 6 … … … max-1

１

（2）乘法运算要点

已知稀疏矩阵A(m1× n1)和B(m2× n2)，求乘积C(m1× n2)。

稀疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图6所示。

由矩阵乘法规则知：

C(i，j)=A(i,1)×B(1,j)+A(i,2)×B(2,j)+…+A(i,n)×B(n,j)=

这就是说只有A(i,k)与B(k,p)(即A元素的列与B元素的行相等的两项)才有相乘的机会，且当两项都不为零时，乘积中的这一项才不为零。

矩阵用二维数组表示时，a11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，…，而同一行的非零元是相邻存放的，所以求c11和c12同时进行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，…，当然只有aik和bkj(列号与行号相等)且均不为零(三元组存在)时才相乘，并且累加到cij当中去。

（3）稀疏矩阵的快速转置要点：

矩阵A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data 。所以需引入两个向量来实现 ：num[n+1]和position [n+1]，num[col]表示矩阵A中第col列的非零元素的个数(为了方便均从1单元用起)，position [col]初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是position的初始值为：position [1]=1;

position [col]= position [col-1]+num[col-1]; 2≤col≤n

依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的position [col]位置上，position [col]加1，position [col]中始终是下一个col列元素在B.data中的位置。

A->row[0] 1 2 3

0 1 3 4 ２

（4）逆矩阵

⒈判断矩阵是否为方阵 ⒉逆矩阵的算法： ①求行列式的值

②求矩阵的伴随矩阵 ③用伴随矩阵除以行列式 ⒊ 求逆矩阵的流程：

３

四、源程序（测试结果） #include #include #include #include

using namespace std; #define max 100

#define datatype int typedef struct{

int row,col;//行，列 datatype v;//非0数值 }Node;

typedef struct{

Node data[max];//稀疏矩阵

int m,n,t;//m行，n列，t非0数个数 }Matrix;

/*求逆矩阵存储*/

typedef struct{ //存储结构 int m, n; //行、列数 double *p; //矩阵基址 }nMatrix;

void In(nMatrix a){ //求逆输入

cout<<\"请将矩阵a的行、列数再次输入：\"; cin >>a.m>>a.n;

int m = a.m, n = a.n; int i, j;

double *p = a.p = new double[m * n]; //p是行指针 cout<<\"请按行优先输入矩阵a的全部数值：\\n\"; for (i = 0; i < m; p += n, i++) {

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

cin>>p[j]; //即a.p[i*n+j] } }

void Out(nMatrix a){ //求逆输出 int m = a.m, n = a.n; int i, j;

double *p = a.p;

for (i = 0; i < m; p += n, i++) {

for (j = 0; j < n; j++) cout<istream& operator >>(istream& input,Matrix &A){ int i;

cout<<\"请输入行数:\"; input>>A.m;

４

cout<<\"请输入列数:\"; input>>A.n;

cout<<\"请输入非0值个数:\"; input>>A.t;

for(i=1;i<=A.t;i++){

cout<<\"请输入行数，列数，非0值:\"<<\"(\"<>A.data[i].row>>A.data[i].col>>A.data[i].v; }

return input; }

ostream& operator <<(ostream& output,Matrix &A){ int i,j,t=1,k=0; for(i=1;i<=A.m;i++){ for(j=1;j<=A.n;j++){

if(A.data[t].row==i&&A.data[t].col==j){ output<output<cout<<\"\\n\"; }

return output; }

Matrix operator +(Matrix A,Matrix B){//加法 int i,j,k; Matrix C;

if(A.m!=B.m||A.n!=B.n){

cout<<\"这两个矩阵不能相加\"<if(A.t==0&&B.t==0) exit(0); i=j=k=1;

while(i<=A.t&&j<=B.t){

if(A.data[i].rowif(A.data[i].row>B.data[j].row){ C.data[k]=B.data[j]; j++;k++; } else{

if(A.data[i].colif(A.data[i].col>B.data[j].col){

５

C.data[k]=B.data[j]; j++;k++; } else{

if(A.data[i].v+B.data[j].v!=0){ C.data[k].row=A.data[i].row; C.data[k].col=A.data[i].col;

C.data[k].v=A.data[i].v+B.data[j].v; k++; }

i++;j++; } } } } }

while(iC.data[k]=A.data[i]; i++;k++; }

while(jC.data[k]=B.data[j]; j++;k++; }

C.t=k; return C; }

Matrix operator -(Matrix A,Matrix B){ Matrix C; int i,j,k;

if(A.m!=B.m||A.n!=B.n) {

cout<<\"这两个矩阵不能相减\";exit(0);} C.m=A.m;C.n=A.n; C.t=0;

if(A.t==0&&B.t==0) exit(0); i=j=k=1;

while(i<=A.t&&j<=B.t)

{ if(A.data[i].row{ if(A.data[i].row>B.data[j].row) { C.data[k]=B.data[j]; j++;k++; } else

{ if(A.data[i].col６

else

{ if(A.data[i].col>B.data[j].col) { C.data[k]=B.data[j]; j++;k++; } else

{ if(A.data[i].v-B.data[j].v!=0) { C.data[k].row=A.data[i].row; C.data[k].col=A.data[i].col;

C.data[k].v=A.data[i].v-B.data[j].v; k++; }

i++;j++; } } } } }

while(i{ C.data[k]=A.data[i]; i++;k++; }

while(j{ C.data[k]=B.data[j]; j++;k++; }

C.t=k; return C; }

Matrix operator *(Matrix A,Matrix B){ Matrix C;

int k,p,crow,brow,q,ccol;

int num[max],pos[max],ctemp[max]; if (A.n==B.m){

for(k=1;k<=B.m;k++) num[k]=0;

for(k=1;k<=B.t;k++)

num[B.data[k].row]++; pos[1]=1;

for(k=2;k<=B.t;k++)

pos[k]=pos[k-1]+num[k-1]; pos[1+B.t]=pos[B.t]+1;

C.m=A.m; C.n=B.n; C.t=0; p=1; while(p<=A.t){

crow=A.data[p].row; for(k=1;k<=C.n;k++) ctemp[k]=0;

while (p<=A.t&&A.data[p].row==crow){ brow=A.data[p].col;

for(q=pos[brow];q<=pos[brow+1]-1;q++){ ccol=B.data[q].col;

７

ctemp[ccol]=ctemp[ccol]+A.data[p].v*B.data[q].v; }

p=p+1; }

for(ccol=1;ccol<=B.n;ccol++) if(ctemp[ccol]!=0){ C.t=C.t+1;

C.data[C.t].row=crow; C.data[C.t].col=ccol;

C.data[C.t].v=ctemp[ccol]; } } } else

cout<<\"这两个矩阵不能相乘\"; return C; }

Matrix operator ~(Matrix A){ Matrix B;

int col,i,p,q;

int num[max],position[max]; B.t=A.t;B.m=A.n; B.n=A.m; if(B.t){

for(col=1;col<=A.n;col++) num[col]=0; for(i=1;i<=A.t;i++)

num[A.data[i].col]++; position[1]=1;

for(col=2;col<=A.n;col++)

position[col]=position[col-1]+num[col-1]; for(p=1;p<=A.t;p++){

col=A.data[p].col;q=position[col]; B.data[q].row=A.data[p].col; B.data[q].col=A.data[p].row; B.data[q].v=A.data[p].v; position[col]++; } } return B; }

nMatrix Trs(nMatrix a){ //求逆矩阵的先转置 nMatrix trs; trs.m = a.n; trs.n = a.m;

trs.p = new double[a.m * a.n];

for (int i = 0; i < a.m; i++) {

for (int j = 0; j < a.n; j++) {

trs.p[j * a.m + i] = a.p[i * a.n + j];

８

} }

return trs; }

nMatrix Adjunct(nMatrix a, int indexm, int indexn){ //求第indexm行indexn列元素的代数余子式

nMatrix adj; adj.m=a.m - 1; adj.n=a.n - 1;

adj.p = new double[(a.n - 1) * (a.n - 1)];

for (int i = 0; i < indexm; i++) {

for (int j = 0; j < indexn; j++) {

adj.p[i * (a.n - 1) + j] = a.p[i * a.n + j]; }

for (int k = indexn + 1; k < a.n; k++) {

adj.p[i *(a.n - 1) + k -1] = a.p[i * a.n + k]; } }

for (int m = indexm + 1; m < a.n; m++) {

for (int j = 0; j < a.n - 1; j++) {

adj.p[(m - 1) * (a.n - 1) + j] = a.p[m * a.n + j]; }

for (int k = indexn + 1; k < a.n; k++) {

adj.p[(m - 1) * (a.n - 1) + k - 1] = a.p[m * a.n + k]; } }

return adj; }

double Det(nMatrix a) //递归求行列式 {

double det = 0; if (a.m != a.n) {

cout<<\"不是方阵，没有行列式!\"<if (a.n == 1) {

det = a.p[0]; return det; } else {

for (int i = 0; i < a.n; i++)

９

{

if (i % 2 == 0)

det += a.p[i * a.n] * Det(Adjunct(a, i, 0)); else

det -= a.p[i * a.n] * Det(Adjunct(a, i, 0)); } }

return det; }

nMatrix operator !(nMatrix a) { //求矩阵的逆 nMatrix temp; temp.m=a.n; temp.n=a.m;

temp.p = new double[a.m * a.n]; //矩阵的逆 = 伴随矩阵 / 行列式

double det = Det(a);

if (det == 0) //如果行列式的值为0，则没有逆 {

cout<<\"此矩阵没有逆!\"<for (int i = 0; i < temp.m; i++) {

for (int j = 0; j < temp.n; j++) {

if ((i +j) % 2 == 0)

temp.p[i * temp.m + j] = Det(Adjunct(a, i, j)) / det; else

temp.p[i * temp.m + j] = -Det(Adjunct(a, i, j)) / det; } }

return Trs(temp); }

void main(){

Matrix C={0},A={0},B={0};nMatrix a={0}, b={0},temp={0}; cin>>A; cout<<\"a=\\n\"<>B; cout<<\"b=\\n\"<cout<<\"矩阵的行列式为:\"<cout<<\"矩阵的逆为:\"<temp=!a;cout<<\"!a=\\n\"<１０

五、测试 请输入行数:2 请输入列数:2 请输入非0值个数:2 请输入行数，列数，非0值:(1) 1 1 1 请输入行数，列数，非0值:(2) 1 2 1 a= 1 1 0 0 请输入行数:2 请输入列数:2 请输入非0值个数:2 请输入行数，列数，非0值:(1) 2 2 1 请输入行数，列数，非0值:(2) 2 1 2 b= 0 0 1 0 a+b= 1 1 0 1 a-b= 1 1 1 0 a*b= 1 0 0 0 ~a= 1 0 1 0 请将稀疏矩阵a的行、列数再次输入：2 2 请按行优先输入稀疏矩阵a的全部数值： 1 1 0 0 矩阵的行列式为: -1 矩阵的逆为: !a= 0 1 0 1 Press any key to continue

１１

六、总结

这次数据结构课程设计的制作使我对数据结构和C语言的理解更加深刻，也使我认识到了自己很多不足之处。

我发现自己在处理稍微具体的程序时显得无从下手，以前学习的知识只是理论性的知识，并没有真正实践过，当我通过网上查询、请教学生老师、复习知识后才对编写程序有了初步的思路。后来编写程序时也碰到了许多错误，我对于指针的掌握程度较差导致了我在使用的时候产生了很多错误，请教了学习较好的同学后才逐步完成。最后还有很多细节方面难以修改，于是就改进算法，使自己的程序有了雏形。

这次程序设计使我认识到，要做成编写一个完整的程序绝对不是一件简单的事情，不单要掌握基础知识更要勇于实践，不单要舍得花费时间更要用心去完成它。无论是编写程序还是完成现实生活中的其他事情，我们都必须按部就班地从点滴做起，逐步完成。不但要完成更要做到尽善尽美。

学习数据结构的历程不会因为完成本次课程设计而停止，我是为了用知识武装大脑而学习，通过学习充实自己的生活，我一定会努力学习，争取以后能够完成规模更大的程序。

１２