数据结构矩阵实验报告

1、一、实验目的和要求（1）掌握各种特殊矩阵如对称矩阵、上下三角矩阵和对角矩阵的压缩存储方法。（2）掌握稀疏矩阵的各种存储结构以及基本运算实现算法。（3）掌握广义表的递归特性、存储结构以及基本运算实现算法。二、实验环境、内容和方法实验内容： 打开Visual C+6.0并输入实验指导书上的程序，并进行调试和运行。 自行尝试编写第六个实验。实验方法：（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。（三）根据实验内容，编译程序。实验环境：Windows xp Visual C+6.0三、实验过程描述

2、实验 以下是一个5*5阶的螺旋方阵。设计一个程序输出该形式的n*n阶方阵。 1 2 3 4 5 16 17 18 19 6 15 24 25 20 714 23 22 21 813 12 11 10 9一、打开Visual C+6.0并输入如下程序#include #define MaxLen 10void fun(int aMaxLenMaxLen,int n)int i,j,k=0,m;if (n%2=0) m=n/2;elsem=n/2+1;for (i=0;im;i+)for (j=i;jn-i;j+)k+;aij=k;for (j=i+1;j=i;j-)k+;an-i-1j=k;fo

3、r (j=n-i-2;j=i+1;j-)k+;aji=k;void main()int n,i,j;int aMaxLenMaxLen;printf(n);printf(输入n(n10):);scanf(%d,&n); fun(a,n);printf(%d阶数字方阵如下:n,n);for (i=0;in;i+)for (j=0;jn;j+)printf(%4d,aij);printf(n);printf(n);二、,编译并连接此程序，如图三、运行此程序，如图实验 假设n*n的稀疏矩阵A采用三元组表示，设计一个程序实现如下功能：（1）生成如下两个稀疏矩阵的三元组a和b：a:1 0 3 0 b:

4、3 0 0 00 1 0 0 0 4 0 00 0 1 0 0 0 1 00 0 1 1 0 0 0 2(2)输出a转置矩阵的三元组(3)输出a+b的三元组(4) 输出a*b的三元组一、输入如图所示程序#include #define N 4typedef int ElemType;#define MaxSize 100typedef struct int r; int c; ElemType d; TupNode;typedef struct int rows; int cols; int nums; TupNode dataMaxSize; TSMatrix;void CreatMat(T

5、SMatrix &t,ElemType ANN)int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;iN;i+) for (j=0;jN;j+) if (Aij!=0) t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;void DispMat(TSMatrix t)int i;if (t.nums=0) return;printf(t%dt%dt%dn,t.rows,t.cols,t.nums);printf(t-n);for (i=0;it.nums;i+)printf(t%dt%d

6、t%dn,t.datai.r,t.datai.c,t.datai.d);void TranMat(TSMatrix t,TSMatrix &tb)int p,q=0,v;tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0) for (v=0;vt.cols;v+)for (p=0;pt.nums;p+)if (t.datap.c=v) tb.dataq.r=t.datap.c;tb.dataq.c=t.datap.r;tb.dataq.d=t.datap.d;q+;int MatAdd(TSMatrix a,TSMatrix b

7、,TSMatrix &c)int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows | a.cols!=b.cols)return 0;c.rows=a.rows;c.cols=a.cols;while (ia.nums & jb.nums)if (a.datai.r=b.dataj.r)if(a.datai.cb.dataj.c)c.datak.r=b.dataj.r; c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; k+;j+; else v=a.datai.d+b.dataj.d;if (v!=0)c.datak.r=

8、a.datai.r;c.datak.c=a.datai.c;c.datak.d=v;k+;i+;j+; else if (a.datai.rb.dataj.r)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;k+;i+; elsec.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;k+;j+; c.nums=k;return 1;int value(TSMatrix c,int i,int j) int k=0; while (kc.nums & (c.d

9、atak.r!=i | c.datak.c!=j) k+; if (kc.nums) return(c.datak.d); else return(0);int MatMul(TSMatrix a,TSMatrix b,TSMatrix &c) int i,j,k,p=0;ElemType s;if (a.cols!=b.rows)return 0;for (i=0;ia.rows;i+)for (j=0;jb.cols;j+) s=0; for (k=0;ka.cols;k+)s=s+value(a,i,k)*value(b,k,j); if (s!=0) c.datap.r=i; c.da

10、tap.c=j; c.datap.d=s; p+; c.rows=a.rows; c.cols=b.cols;c.nums=p;return 1;void main()ElemType a1NN=1,0,3,0,0,1,0,0,0,0,1,0,0,0,1,1;ElemType b1NN=3,0,0,0,0,4,0,0,0,0,1,0,0,0,0,2;TSMatrix a,b,c;CreatMat(a,a1);CreatMat(b,b1);printf(a的三元组:n);DispMat(a);printf(b的三元组:n);DispMat(b);printf(a转置为cn);TranMat(a,

11、c);printf(c的三元组:n);DispMat(c);printf(c=a+bn);MatAdd(a,b,c);printf(c的三元组:n);DispMat(c);printf(c=a*bn);MatMul(a,b,c);printf(c的三元组:n);DispMat(c);二、程序运行结果如图实验 编写一个程序实现广义表的各种运算，并在此基本上设计一个程序完成如下功能：（1）建立广义表g=“(b,(b,a,(#),d),(a,b),c,(#)”的链式存储结构；（2）输出广义表g的长度；（3）输出广义表g的深度；（4）输出广义表g的最大原子；一、输入如图所示程序#include #in

12、clude typedef char ElemType;typedef struct lnode int tag; union ElemType data; struct lnode *sublist;val; struct lnode *link; GLNode;GLNode *CreatGL(char *&s)GLNode *h;char ch;ch=*s+; if (ch!=0)h=(GLNode *)malloc(sizeof(GLNode); if (ch=()h-tag=1; h-val.sublist=CreatGL(s); else if (ch=) h=NULL; elseh

13、-tag=0; h-val.data=ch; else h=NULL; ch=*s+; if (h!=NULL) if (ch=,) h-link=CreatGL(s); else h-link=NULL; return h;int GLLength(GLNode *g) int n=0;g=g-val.sublist; while (g!=NULL) n+; g=g-link; return n;int GLDepth(GLNode *g) int max=0,dep;if (g-tag=0)return 0;g=g-val.sublist;if (g=NULL)return 1;while (g!=NULL) if (g-tag=1) dep=GLDepth(g); if (depmax) max=dep; g=g-link; return(max+1); void DispGL(GLNode *g)if (g!=NULL)if (g-tag=1)printf(); if (g-val.sublist=NULL) printf(); else DispGL(g-val.sublist); else printf(%c, g-val.data); if (g-tag=1) printf(); if (g-link