实验三数组与广义表 实验目的 1、了解数组的两种存储表示方法,掌握数组在作为运行的存储结构中 的地址的计算方法 2、了解稀疏矩阵的两种压缩方法的特点和适用范围,领会稀疏矩阵运 算采用的处理方法。 3、掌握广义结构的特点及其存储方法 二、验内容 1、鞍点问题 问题描述]若矩阵中的某个元素A卩,是第一行中的最小值,而又是第 j列中的最大值,则称ALj为矩阵A中的第一个鞍点请写一个可确定此鞍 点位置的算法(如果这鞍点存在),并给出着算法的时间复杂度。 [基本要求]要求算法要考虑某行中具有多个相同的且又是该行中最小 的元素的情况 实现提示]可以用一位数组保存R[0.n-1每一行中最小的元素,用一位 数组C[0.n1].保存每一行中最大元素。如果R]=CL,则即A4j为鞍点 程序实现] (1)基本思想 可先求出每行的最小值元素,放入一个一维数组mn[m]中,在求出梅 列的最大元素,放入max[m中,若某个元素既在min中,又在max中, 则该R[LJ元素便是鞍点元素,找出这样的鞍点元素,即找到此处有鞍点 (2)程序实现 #include <stdio. h> #define m 4 *鞍点定位 void point (R) int R[mJn flag int min(m), max[n; flag=0 /找每行最小值放入min中 for(i=0; i<m; 1++) i min[i=ROJ[OT for(=l j<n: j++) if(R[O0]<min(i))
实验三 数组与广义表 一、实验目的 1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中 的地址的计算方法。 2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运 算采用的处理方法。 3、 掌握广义结构的特点及其存储方法。 二、验内容 1、鞍点问题 [问题描述] 若矩阵中的某个元素 A[I,j]是第一行中的最小值，而又是第 j 列中的最大值，则称 A[I,j]为矩阵 A 中的第一个鞍点.请写一个可确定此鞍 点位置的算法（如果这鞍点存在），并给出着算法的时间复杂度。 [基本要求]要求算法要考虑某行中具有多个相同的且又是该行中最小 的元素的情况。 [实现提示]可以用一位数组保存 R[0..n-1]每一行中最小的元素，用一位 数组 C[0..n-1]来保存每一行中最大元素。如果 R[I]=C[j]，则即 A[I,j]为鞍点。 [程序实现] （1） 基本思想 可先求出每行的最小值元素，放入一个一维数组 min[m]中，在求出梅 列的最大元素，放入 max[n]中，若某个元素既在 min[I]中，又在 max[j]中， 则该 R[I,j]元素便是鞍点元素，找出这样的鞍点元素，即找到此处有鞍点。 (2)程序实现 #include <stdio.h> #define m 4 #define n 5 /*鞍点定位 void point（R） int R[m][n]; {int I,j; int flag; int min[m],max[n]; flag=0; /*找每行最小值放入 min[i]中 for(i=0;i<m;i++) { min[i]=R[i][0]; for(j=1;j<n;j++) if(R[i][j]<min[i])
min=R[OII /找每行最大值放入max中 for(=0 j<n; j+ max[=R[OJ: if(r[Gmad) max[l=R[O0I for(i=0 i<m; 1++) or(=0; j<n: j++) if(mini==maxl print(%d,%d)%dn”ijR[U);/*输出鞍点 flag=1;/*置标志 (I flag printf("找不到鞍点n”); /*主函数 n i int r[m]n for(i=0 for(=0: j<n j++) scanf(&ROIOD) 2、阶魔阵问题 [问题描述]给定一奇数n,构造一个n阶魔阵,阶魔阵是一个n阶方阵 其元素由自然数1,2,3.nm2组成魔阵的每行元素之和以及主副对角线元 素之和均相等。即对于给的奇整数n以及1=1.n,魔阵a满足条件: ∑aik(k=1->n)=∑ak(k=1->n)=∑ak(k=1→n)=∑aknk+1(k=1-n) 基本要求]要求输出结果的格式要具有n阶方阵的形式 实现提示]依次将自然数添入方阵,共填n轮,每轮填n次。第一轮的 第一次将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是 (1)每轮中第2至第n次将数填入ai+ll,若遇到下列两种情况之
min[i]=R[i][j]; } /*找每行最大值放入 max[j]中 for(j=0;j<n;j++) { max[j]=R[0][j]; for(i=1;i<m;i++) if(R[i][j]>max[j]) max[j]=R[i][j]; } for(i=0;i<m;i++) for(j=0;j<n;j++) if(min[i]==max[j]) { prinft(“(%d,%d):%d\n”,i,j,R[i][j]); /*输出鞍点 flag=1; /*置标志 } if (!flag) printf(“找不到鞍点\n”); } /*主函数 main() { int R[m]}[n]; int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf(&R[i][j]); point(r); } 2、 阶魔阵问题 [问题描述] 给定一奇数 n，构造一个 n 阶魔阵，阶魔阵是一个 n 阶方阵， 其元素由自然数 1，2，3……n 2 组成,魔阵的每行元素之和以及主副对角线元 素之和均相等。即对于给的奇整数 n 以及 I=1…..n,魔阵 a 满足条件： ∑aik (k=1->n)=∑aki(k=1->n)=∑akk(k=1->n)=∑ak,n-k+1(k=1->n) [基本要求] 要求输出结果的格式要具有 n 阶方阵的形式。 [实现提示]依次将自然数添入方阵，共填 n 轮，每轮填 n 次。第一轮的 第一次将 1 填入方阵的中间一行的最后一列位置。设前一次填入的位置是 aij: （1）每轮中第 2 至第 n 次将数填入 ai+1,j+1,若遇到下列两种情况之一
则填写位置按以下规则调整。 a是最后一列(即j=n)位置,则将下一个数填入ai+1,n; 是最后一行(即i=n)位置,则将下一个数填入aj+1 (2)新一轮的第一次填入alj-1 [程序实现] /*N阶魔阵问题主函数 int r[m][n];设数组下标均从1开始 int n, j, I, k scanf(&n) *相除 J=n+1; if(k%n==1) J-", else j=j%j+1 r[0=k for(i=l; i<=n; i++) i for(=l: j<=n j++) printf(riD) 也可按下列方法给出n魔阵,其算法思想为:由魔方阵知其排列规律如 下: (1)将1放第一行中间一列 (2)从“2”开始直到nn止,个数一次按下列规则存放:每一个 数存放的行比前一个数的行数减1,列数加1: (3)如果上一数的列数为n时,下一个数的列数应为1,行数减1 (4)如果上一数行数为1,则下一个数行数为n(指向最下一行) (5)如果按上面规则确定位置上的已有数,或上一个数是第一行 第n列时,则把下一个数放在上一个数的下面: #define n 15
则填写位置按以下规则调整。 ◆ aij 是最后一列（即 j=n）位置，则将下一个数填入 ai+1,1; ◆ aij 是最后一行（即 i=n）位置，则将下一个数填入 a1,j+1. (2) 新一轮的第一次填入 a1,j-1. [程序实现] /*N 阶魔阵问题主函数 main() { int r[m][n]; /*设数组下标均从 1 开始 int n,j,I,k; scanf(&n); i=(n+1)%n; /*相除 J=n+1; For(k=1,k<=(n*n);k++) { if(k%n==1) j--; else { i=i%n+1; j=j%j+1; } r[i][j]=k; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf(r[i][j]); } } 也可按下列方法给出 n 魔阵，其算法思想为：由魔方阵知其排列规律如 下： （1） 将 1 放第一行中间一列； （2） 从“2”开始直到 n*n 止，个数一次按下列规则存放：每一个 数存放的行比前一个数的行数减 1，列数加 1； （3） 如果上一数的列数为 n 时，下一个数的列数应为 1，行数减 1； （4） 如果上一数行数为 1，则下一个数行数为 n(指向最下一行)； （5） 如果按上面规则确定位置上的已有数，或上一个数是第一行 第 n 列时，则把下一个数放在上一个数的下面： #define n 15 main() {
int r[mn] int.ckI k=0; for(l=1,1<=k;I++) for(=l;<=k; j++) r[U]=0 l=1 T=1 M=k*k J=(k+1)%2; RLI=t While(t<=m) x=l-1; if((x<1)&&(y<k) I=x+2: else if(y<k) J= if(I<1) I=k. if(r(xy =0)
int r[m][n]; int r, c,k,I,j; k=0; scanf(&k); for(I=1;I<=k;I++) for(j=1;j<=k;j++) r[I][j]=0; I=1; T=1 M=k*k; J=(k+1)%2; R[I,j]=t; T++; While(t<=m) { x=I-1; y=j+1; if((x<1)&&(y<k)) { I=x+2; J=-y-1; } else if(y<k) { I=x; J=1; } else if(I<1) { I=k; J=y; } else if(r[x][y]!=0) {
IJ {l=x; A-y, r[0=t; for(l=1: j<=k; 1++) for(=1: j<=k: j++) printf(rIOD printf("In”)
I=x+2; J=y-1; } else {I=x; j=y; } r[i][j]=t; } for(I=1;j<=k;I++) { for(j=1;j<=k;j++) printf(r[I][j]); printf(“\n”); } }