数据结构实验指导书.doc

实验五 数组5.1实验目的：（1） 熟悉和掌握数组结构的实际应用，特别是多维数组的存储；（2） 熟悉和掌握稀疏矩阵的存储及其应用。5.2实验要求：（1） 复习课本中有关数组的知识；（2） 用C语言完成算法和程序设计并上机调试通过；（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。5.3基础实验实验1 实现稀疏矩阵(采用三元组表示)的基本运算实验内容与要求: 假设nn的稀疏矩阵a和b采用三元组表示,编写一个程序实现如下功能:a) 生成两个稀疏矩阵的三元组a和b.。b) 输出a转置矩阵的三元组。c) 输出a+b的三元组。d) 输出ab的三元组。分析: 在稀疏矩阵相乘的算法当中，关键是通过给定的行号i和列号j找出原矩阵的对应元素值，这里设计了一个函数value，当在三元组表示中找到时返回其元素值，找不到时说明该位置处的元素值为0，因此返回0。然后利用该函数进行矩阵相乘，若求出某个元素值不为0，则将其存入结果矩阵的三元组表示中，否则不存入。 该算法实现包含一下函数：（1） CreatMat（TSMatrix & t，ElemTypeaNN）：产生稀疏矩阵a的三元组表示。（2） DispMat(TSMatrix t)：输出三元组表示。（3） TranMat(TSMatrix t,TSMatrix & tb)：求三元组表示t的转置tb。（4） MatAdd（TSMatrix a，TSMatrix b，TSMatrix & c）：求c=a+b.（5） Value（TSMatrix c，int i，int j）：返回三元组存储c中cij之值。（6） MatMul（TSMatrix a，TSMatrix b，TSMatrix & c）：求c=ab。参考程序:#include #define N 4typedef int ElemType;#define MaxSize 100 /*矩阵中非零元素最多个数*/typedef struct int r; /*行号*/ int c; /*列号*/ ElemType d; /*元素值*/ TupNode; /*三元组定义*/typedef struct int rows; /*行数值*/ int cols; /*列数值*/ int nums; /*非零元素个数*/ TupNode dataMaxSize; TSMatrix; /*三元组顺序表定义*/TSMatrix CreatMat(TSMatrix 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+; return t;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%dt%dn,t.datai.r,t.datai.c,t.datai.d);TSMatrix TranMat(TSMatrix t,TSMatrix tb) int p,q=0,v; /*q为tb.data的下标*/ tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums; if (t.nums!=0) for (v=0;vt.cols;v+) /*tb.dataq中的记录以c域的次序排列*/ for (p=0;pt.nums;p+) /*p为t.data的下标*/ if (t.datap.c=v) tb.dataq.r=t.datap.c; tb.dataq.c=t.datap.r; tb.dataq.d=t.datap.d; q+; return tb; TSMatrix MatAdd(TSMatrix a,TSMatrix b,TSMatrix c) int i=0,j=0,k=0; ElemType v; if (a.rows!=b.rows | a.cols!=b.cols) return ; /*行数或列数不等时不能进行相加运算*/ c.rows=a.rows;c.cols=a.cols; /*c的行列数与a的相同*/ while (ia.nums & jb.nums) /*处理a和b中的每个元素*/ if (a.datai.r=b.dataj.r) /*行号相等时*/ if(a.datai.cb.dataj.c)/*a元素的列号大于b元素的列号*/ c.datak.r=b.dataj.r; /*将b元素添加到c中*/ c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; k+;j+; else /*a元素的列号等于b元素的列号*/ v=a.datai.d+b.dataj.d; if (v!=0) /*只将不为0的结果添加到c中*/ c.datak.r=a.datai.r; c.datak.c=a.datai.c; c.datak.d=v; k+; i+;j+; else if (a.datai.rb.dataj.r) /*a元素的行号小于b元素的行号*/ c.datak.r=a.datai.r; /*将a元素添加到c中*/ c.datak.c=a.datai.c; c.datak.d=a.datai.d; k+;i+; else /*a元素的行号大于b元素的行号*/ c.datak.r=b.dataj.r; /*将b元素添加到c中*/ c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; k+;j+; c.nums=k; return c;int value(TSMatrix c,int i,int j) int k=0; while (kc.nums & (c.datak.r!=i | c.datak.c!=j) k+; if (kc.nums) return(c.datak.d); else return(0);TSMatrix MatMul(TSMatrix a,TSMatrix b,TSMatrix c) int i,j,k,p=0; ElemType s; if (a.cols!=b.rows) /*a的列数不等于b的行数时不能进行相乘运算*/ return ; 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.datap.c=j; c.datap.d=s; p+; c.rows=a.rows; c.cols=b.cols; c.nums=p; return c;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; a=CreatMat(a,a1); b=CreatMat(b,b1); printf(a的三元组:n);DispMat(a); printf(b的三元组:n);DispMat(b); printf(a转置为cn); c=TranMat(a,c); printf(c的三元组:n);DispMat(c); printf(c=a+bn); c= MatAdd(a,b,c); printf(c的三元组:n);DispMat(c); printf(c=a*bn); c=MatMul(a,b,c); printf(c的三元组:n);DispMat(c);5.4 提高实验实验1 求一个矩阵的马鞍点实验内容与要求: 如果矩阵A中存在这样一个元素Aij满足条件：Aij是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个程序计算出mn的矩阵A的所有马鞍点。分析: 先求出每行的最小元素，放入minm中，再求出每列的最大元素，放入maxn中，若某元素既在mini中，又在maxj中，则该元素Aij便是马鞍点，找出所有这样的元素，即找到了所有的马鞍点。参考程序:#include #define M 4#define N 4void MinMax(int AMN)int i,j,have=0;int minM,maxN;for (i=0;iM;i+) /*计算出每行的最小值元素,放入min0.M-1之中*/mini=Ai0; for (j=1;jN;j+) if (Aijmini) mini=Aij;for (j=0;jN;j+) /*计算出每列的最大值元素,放入max0.N-1之中*/maxj=A0j;for (i=1;imaxj) maxj=Aij;for (i=0;iM;i+)/*判定是否为马鞍点*/for (j=0;jN;j+) if (mini=maxj) printf( A%d,%d=%dn,i,j,Aij);/*显示马鞍点*/ have=1; if (!have)printf(没有鞍点n);void main()int i,j;int AMN=9, 7, 6, 8,20,26,22,25,28,36,25,30,12,4, 2, 6;printf(A矩阵:n);for (i=0;iM;i+)for (j=0;jN;j+)printf(%4d,Aij);printf(n);printf(A矩阵中的马鞍点:n);MinMax(A);/*调用MinMax()找马鞍点*/实验2 求55阶螺旋方阵实验内容与要求: 对55阶螺旋方阵，设计一个算法输出该形式的nn（n10）阶方阵(顺时针方向旋进)。分析: 用二维数组存放n阶螺旋方阵。n阶螺旋方阵共有m圈，对于第i（0=i=m-1共执行m次）圈循环；产生该圈上横行的数字，产生该圈右竖行的数字，产生该圈下横行的数字，产生该圈左竖行的数字，最后输出该方阵。参考程序:#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;for (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;i