数据结构实验指导书05

1实验五数组5.1实验目的：（1）熟悉和掌握数组结构的实际应用，特别是多维数组的存储；（2）熟悉和掌握稀疏矩阵的存储及其应用。5.2实验要求：（1）复习课本中有关数组的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。5.3基础实验[实验1]实现稀疏矩阵(采用三元组表示)的基本运算实验内容与要求:假设n×n的稀疏矩阵a和b采用三元组表示,编写一个程序实现如下功能:a)生成两个稀疏矩阵的三元组a和b.。b)输出a转置矩阵的三元组。c)输出a+b的三元组。d)输出a×b的三元组。分析:在稀疏矩阵相乘的算法当中，关键是通过给定的行号i和列号j找出原矩阵的对应元素值，这里设计了一个函数value，当在三元组表示中找到时返回其元素值，找不到时说明该位置处的元素值为0，因此返回0。然后利用该函数进行矩阵相乘，若求出某个元素值不为0，则将其存入结果矩阵的三元组表示中，否则不存入。该算法实现包含一下函数：（1）CreatMat（TSMatrix&t，ElemTypea[N][N]）：产生稀疏矩阵a的三元组表示。（2）DispMat(TSMatrixt)：输出三元组表示。（3）TranMat(TSMatrixt,TSMatrix&tb)：求三元组表示t的转置tb。（4）MatAdd（TSMatrixa，TSMatrixb，TSMatrix&c）：求c=a+b.（5）Value（TSMatrixc，inti，intj）：返回三元组存储c中c[i][j]之值。（6）MatMul（TSMatrixa，TSMatrixb，TSMatrix&c）：求c=a×b。参考程序:#includestdio.h#defineN4typedefintElemType;#defineMaxSize100/*矩阵中非零元素最多个数*/typedefstruct{intr;/*行号*/intc;/*列号*/2ElemTyped;/*元素值*/}TupNode;/*三元组定义*/typedefstruct{introws;/*行数值*/intcols;/*列数值*/intnums;/*非零元素个数*/TupNodedata[MaxSize];}TSMatrix;/*三元组顺序表定义*/TSMatrixCreatMat(TSMatrixt,ElemTypeA[N][N]){inti,j;t.rows=N;t.cols=N;t.nums=0;for(i=0;iN;i++){for(j=0;jN;j++)if(A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}returnt;}voidDispMat(TSMatrixt){inti;if(t.nums=0)return;printf(\t%d\t%d\t%d\n,t.rows,t.cols,t.nums);printf(\t------------------\n);for(i=0;it.nums;i++)printf(\t%d\t%d\t%d\n,t.data[i].r,t.data[i].c,t.data[i].d);}TSMatrixTranMat(TSMatrixt,TSMatrixtb){intp,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.data[q]中的记录以c域的次序排列*/for(p=0;pt.nums;p++)/*p为t.data的下标*/if(t.data[p].c==v){tb.data[q].r=t.data[p].c;3tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}returntb;}}TSMatrixMatAdd(TSMatrixa,TSMatrixb,TSMatrixc){inti=0,j=0,k=0;ElemTypev;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.data[i].r==b.data[j].r)/*行号相等时*/{if(a.data[i].cb.data[j].c)/*a元素的列号小于b元素的列号*/{c.data[k].r=a.data[i].r;/*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}elseif(a.data[i].cb.data[j].c)/*a元素的列号大于b元素的列号*/{c.data[k].r=b.data[j].r;/*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}else/*a元素的列号等于b元素的列号*/{v=a.data[i].d+b.data[j].d;if(v!=0)/*只将不为0的结果添加到c中*/{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}4}elseif(a.data[i].rb.data[j].r)/*a元素的行号小于b元素的行号*/{c.data[k].r=a.data[i].r;/*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else/*a元素的行号大于b元素的行号*/{c.data[k].r=b.data[j].r;/*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}c.nums=k;}returnc;}intvalue(TSMatrixc,inti,intj){intk=0;while(kc.nums&&(c.data[k].r!=i||c.data[k].c!=j))k++;if(kc.nums)return(c.data[k].d);elsereturn(0);}TSMatrixMatMul(TSMatrixa,TSMatrixb,TSMatrixc){inti,j,k,p=0;ElemTypes;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.data[p].r=i;5c.data[p].c=j;c.data[p].d=s;p++;}}c.rows=a.rows;c.cols=b.cols;c.nums=p;returnc;}voidmain(){ElemTypea1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};ElemTypeb1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};TSMatrixa,b,c;a=CreatMat(a,a1);b=CreatMat(b,b1);printf(a的三元组:\n);DispMat(a);printf(b的三元组:\n);DispMat(b);printf(a转置为c\n);c=TranMat(a,c);printf(c的三元组:\n);DispMat(c);printf(c=a+b\n);c=MatAdd(a,b,c);printf(c的三元组:\n);DispMat(c);printf(c=a*b\n);c=MatMul(a,b,c);printf(c的三元组:\n);DispMat(c);}5.4提高实验[实验1]求一个矩阵的马鞍点实验内容与要求:如果矩阵A中存在这样一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个程序计算出m×n的矩阵A的所有马鞍点。分析:先求出每行的最小元素，放入min[m]中，再求出每列的最大元素，放入max[n]中，若某元素既在min[i]中，又在max[j]中，则该元素A[i][j]便是马鞍点，找出所有这样的元素，即找到了所有的马鞍点。参考程序:6#includestdio.h#defineM4#defineN4voidMinMax(intA[M][N]){inti,j,have=0;intmin[M],max[N];for(i=0;iM;i++)/*计算出每行的最小值元素,放入min[0..M-1]之中*/{min[i]=A[i][0];for(j=1;jN;j++)if(A[i][j]min[i])min[i]=A[i][j];}for(j=0;jN;j++)/*计算出每列的最大值元素,放入max[0..N-1]之中*/{max[j]=A[0][j];for(i=1;iM;i++)if(A[i][j]max[j])max[j]=A[i][j];}for(i=0;iM;i++)/*判定是否为马鞍点*/for(j=0;jN;j++)if(min[i]==max[j]){printf(A[%d,%d]=%d\n,i,j,A[i][j]);/*显示马鞍点*/have=1;}if(!have)printf(没有鞍点\n);}voidmain(){inti,j;intA[M][N]={{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,A[i][j]);printf(\n);}printf(A矩阵中的马鞍点:\n);MinMax(A);/*调用MinMax()找马鞍点*/7}[实验2]求5×5阶螺旋方阵实验内容与要求:对5×5阶螺旋方阵，设计一个算法输出该形式的n×n（n10）阶方阵(顺时针方向旋进)。分析:用二维数组存放n阶螺旋方阵。n阶螺旋方阵共有m圈，对于第i（0=i=m-1共执行m次）圈循环；产生该圈上横行的数字，产生该圈右竖行的数字，产生该圈下横行的数字，产生该圈左竖行的数字，最后输出该方阵。参考程序:#includestdio.h#defineMaxLen10voidfun(inta[MaxLen][MaxLen],intn){inti,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++;a[i][j]=k;}for(j=i+1;jn-i;j++){k++;a[j][n-i-1]=k;}for(j=n-i-2;j=i;j--){k++;a[n-i-1][j]=k;}for(j=n-i-2;j=i+1;j--){k++;a[j][i]=k;}}8}voidmain(){intn,i,j;inta