实验三 数组与广义表一、实验目的
1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址的计算方法。
2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。
掌握广义结构的特点及其存储方法。
二、验内容
1、鞍点问题
[问题描述] 若矩阵中的某个元素A[I,j]是第一行中的最小值，而又是第j列中的最大值，则称A[I,j]为矩阵A中的第一个鞍点.请写一个可确定此鞍点位置的算法（如果这鞍点存在），并给出着算法的时间复杂度。
[基本要求]要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。
[实现提示]可以用一位数组保存R[0..n-1]每一行中最小的元素，用一位数组C[0..n-1]来保存每一行中最大元素。如果R[I]=C[j]，则即A[I,j]为鞍点。
[程序实现]
基本思想可先求出每行的最小值元素，放入一个一维数组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[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);
}
阶魔阵问题
[问题描述] 给定一奇数n，构造一个n阶魔阵，阶魔阵是一个n阶方阵，其元素由自然数1，2，3……n2组成,魔阵的每行元素之和以及主副对角线元素之和均相等。即对于给的奇整数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,若遇到下列两种情况之一，则填写位置按以下规则调整。
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放第一行中间一列；
从“2”开始直到n*n止，个数一次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1；
如果上一数的列数为n时，下一个数的列数应为1，行数减1；
如果上一数行数为1，则下一个数行数为n(指向最下一行)；
如果按上面规则确定位置上的已有数，或上一个数是第一行第 n列时，则把下一个数放在上一个数的下面：
#define n 15
main()
{
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)
{
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”);
}
}
1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址的计算方法。
2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。
掌握广义结构的特点及其存储方法。
二、验内容
1、鞍点问题
[问题描述] 若矩阵中的某个元素A[I,j]是第一行中的最小值，而又是第j列中的最大值，则称A[I,j]为矩阵A中的第一个鞍点.请写一个可确定此鞍点位置的算法（如果这鞍点存在），并给出着算法的时间复杂度。
[基本要求]要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。
[实现提示]可以用一位数组保存R[0..n-1]每一行中最小的元素，用一位数组C[0..n-1]来保存每一行中最大元素。如果R[I]=C[j]，则即A[I,j]为鞍点。
[程序实现]
基本思想可先求出每行的最小值元素，放入一个一维数组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[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);
}
阶魔阵问题
[问题描述] 给定一奇数n，构造一个n阶魔阵，阶魔阵是一个n阶方阵，其元素由自然数1，2，3……n2组成,魔阵的每行元素之和以及主副对角线元素之和均相等。即对于给的奇整数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,若遇到下列两种情况之一，则填写位置按以下规则调整。
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放第一行中间一列；
从“2”开始直到n*n止，个数一次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1；
如果上一数的列数为n时，下一个数的列数应为1，行数减1；
如果上一数行数为1，则下一个数行数为n(指向最下一行)；
如果按上面规则确定位置上的已有数，或上一个数是第一行第 n列时，则把下一个数放在上一个数的下面：
#define n 15
main()
{
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)
{
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”);
}
}
