第5章数组和稀疏矩阵
5.1问答题及其参考答案
5.1.1问答题
1. 为什么说数组是线性表的推广或扩展，而不说数组就是一种线性表呢？
2. 为什么数组一般不使用链式存储结构？
3. 如果某个一维整数数组A的元素个数n很大，存在大量重复的元素，且所有值相同的元素紧跟在一起，请设计一种压缩存储方式使得存储空间更节省。
4. 有一个5×6的二维数组a，起始元素a［1］［1］的地址是1000，每个元素的长度为4。
(1) 若采用按行优先存储，给出元素a［4］［5］的地址。
(2) 若采用按列优先存储，给出元素a［4］［5］的地址。
5. 一个n阶对称矩阵存入内存，在采用压缩存储和非压缩存储时占用的内存空间分别是多少？
6. 一个6阶对称矩阵A中主对角线以上部分的元素已按列优先顺序存放于一维数组B中，主对角线上的元素均为0。根据以下B的内容画出A矩阵。
01234567891011121314
B： 250340014263012
7. 设A［0..9,0..9］是一个10阶对称矩阵，采用按行优先将其下三角+主对角线部分的元素压缩存储到一维数组B中。已知每个元素占用两个存储单元，其第一个元素A［0］［0］的存储位置为1000，求以下问题的计算过程及结果：
(1) 给出A［4］［5］的存储位置。
(2) 给出存储位置为1080的元素的下标。
8. 设n阶下三角矩阵A［0..n-1,0..n-1］已压缩存储到一维数组B［1..m］中，若按行为主序存储，则A［i］［j］(i≥j)元素对应的B中存储位置为多少？给出推导过程。
9. 用十字链表表示一个有k个非零元素的m×n的稀疏矩阵，则其总的结点数为多少？
10. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取特性？为什么？
第5章数组和稀疏矩阵
数据结构教程（C++语言描述）(第2版)学习与上机实验指导
5.1.2问答题参考答案
1. 答： 从逻辑结构的角度看，一维数组是一种线性表，二维数组可以看成数组元素为一维数组的一维数组，所以二维数组可以看成线性表，三维及以上维的数组亦如此。数组的基本运算不同于线性表，数组的主要操作是存取元素，不含插入和删除等运算，所以数组可看作线性表的推广，但数组不等同于线性表。
2. 答： 因为数组的主要操作是存取元素，通常没有插入和删除操作，在使用链式存储结构时需要额外占用更多的存储空间，而且不具有随机存取特性，使得相关操作更复杂。
3. 答： 采用元素类型形如“{整数，个数}”的结构体数组压缩存储，例如，数组A为{1，1，1，5，5，5，5，3，3，3，3，4，4，4，4，4，4}，共有17个元素，对应的压缩存储为{{1，3}，{5，4}，{3，4}，{4，6}}。在压缩数组中只有8个整数。从中看出，重复元素越多，采用这种压缩存储方式越节省存储空间。
4. 答： (1) m×n的二维数组a(行、列下标从c1、c2开始)按行优先存储时元素a［i］［j］的地址计算公式是LOC(a［i］［j］)=d+((i-c1)×(n-c2+1)+(j-c2))×k。这里m=5，n=6，k=4，d=1000，c1=c2=1，所以有LOC(a［4］［5］)=1000+((4-1)×(6-1+1)+(5-1))×4=1000+88=1088。
(2) m×n的二维数组a(行、列下标从c1、c2开始)按列优先存储时元素a［i］［j］的地址计算公式是LOC(a［i］［j］)=d+((j-c2)×(m-c1+1)+(i-c1))×k。这里m=5，n=6，k=4，d=1000，c1=c2=1，所以有LOC(a［4］［5］)=1000+((5-1)×(5-1+1)+(4-1))×4=1000+92=1092。
5. 答： 若采用压缩存储，其容量为n(n+1)/2，若不采用压缩存储，其容量为n2。
6. 答： 对应的A对称矩阵如下。
A=
025306
200413
500040
340021
014202
630120
7. 答： (1) A［4］［5］元素前面有4行，元素个数为1+2+3+4=10，在第4行中，A［4］［5］元素前面有5个元素，则前面元素的总数=10+5=15。
LOC(A［4］［5］)=LOC(A［0］［0］)+15×2=1030。
(2) 存储位置为1080，则元素在压缩数组中的序号为(1080-1000)/2=40。设该元素为A［i］［j］，则有
i(i+1)/2+j=40且0≤i，j≤9，从而得到i=8，j=4，所以对应的元素为A［8］［4］或者A［4］［8］。
8. 答： A的下标从0开始，对于A［i］［j］(i≥j)元素，前面有0~i-1共i行，各行的元素个数分别为1、2、…、i，计i(i+1)/2个元素，在第i行中，A［i］［j］元素前面的元素有A［i,0..j-1］，计j个元素，所以在A中A［i］［j］元素之前共存储i(i+1)/2+j个元素。而B的下标从1开始，所以对应的B中存储位置是i(i+1)/2+j+1。
9. 答： 十字链表有一个十字链表表头结点，MAX(m，n)个行列表头结点。另外，每个非零元素对应一个结点，即k个元素结点，所以共有MAX(m，n)+k+1个结点。
10. 答： 特殊矩阵A指值相同的元素或常元素在矩阵中的分布有一定规律，可以将这些特殊值的元素压缩存储在一维数组B中，即将A［i］［j］元素值存放在B［k］中，下标k和下标i、j的关系用函数k=f(i，j)表示，该函数的计算时间为O(1)，因此对于A［i］［j］找到存储值B［k］的时间为O(1)，所以仍具有随机存取特性。
而稀疏矩阵是指非零元素个数t和矩阵容量相比很小(tm×n)，且非零元素分布没有规律。在用十字链表存储时自然失去了随机存取特性，即便用三元组顺序存储结构存储，存取下标为i和j的元素时也需要扫描整个三元组表，平均时间复杂度为O(t)。因此稀疏矩阵A无论采用三元组还是十字链表存储，查找A［i］［j］元素值的时间不再是O(1)，所以失去了随机存取特性。
5.2算法设计题及其参考答案
5.2.1算法设计题
1. 设计一个算法，将含有n个整数元素的数组a［0..n-1］循环右移m位，要求算法的空间复杂度为O(1)。
2. 有一个含有n个整数元素的数组a［0..n-1］，设计一个算法求其中最后一个最小元素的下标。
3. 设a是一个含有n个元素的double型数组，b是一个含有n个元素的整数数组，其值介于0~n-1，且所有元素不相同。现设计一个算法，要求按b的内容调整a中元素的顺序，比如当b［2］=11时，要求将a［11］元素调整到a［2］中。如n=5，a［］={1,2,3,4,5}，b［］={2,3,4,1,0}，执行本算法后a［］={3,4,5,1,2}。
4. 设计一个算法，实现m行n列的二维数组a的就地转置，当m≠n时返回false，否则返回true。
5. 设计一个算法，求一个m行n列的二维整型数组a的左上角右下角和右上角左下角两条主对角线元素之和，当m≠n时返回false，否则返回true。
5.2.2算法设计题参考答案
1. 解： 设a中元素为xy(x为前n-m个元素，y为后m个元素)。先将x逆置得到x-1y，再将y逆置得到x-1y-1，最后将整个x-1y-1逆置得到(x-1y-1)-1=yx。对应的算法如下：
void Reverse(int a［］,int i,int j) //逆置a［i..j］
{int i1=i,j1=j;
while (i1<j1)
{swap(a［i1］,a［j1］);
i1++; j1--;
}
}
void Rightmove(int a［］,int n,int m) //将a［0..n-1］循环右移m个元素
{if (m>n) m=m%n;
Reverse(a,0,n-m-1);
Reverse(a,n-m,n-1);
Reverse(a,0,n-1);
}
2. 解： 设最后一个最小元素的下标为mini，初值为0。i从1到n-1循环，当a［i］<=a［mini］时置mini=i，最后返回mini。对应的算法如下：
int FindMin(int a［］,int n)
{int mini=0;
for (int i=1;i<n;i++)
if (a［i］<=a［mini］)
mini=i;
return mini;
}
3. 解： 建立一个临时动态数组c，其大小为n。用i扫描b数组，将a［b［i］］放到c［i］中，再将数组c复制到a中。对应的算法如下：
void Rearrange(double a［］,int b［］,int n)
{double *c=new double［n］;
for (int i=0;i<n;i++) c［i］=a［b［i］］;
for (int i=0;i<n;i++) a［i］=c［i］; //将c复制到a中
delete ［］ c;
}
4. 解： 当m≠n时返回false。i从0到m-1、j从0到i-1循环，将a［i］［j］与a［j］［i］元素交换，最后返回true。对应的算法如下：
bool Trans(int a［M］［N］,int m,int n)
{if (m!=n) return false;
for (int i=0;i<m;i++)
for (int j=0;j<i;j++)
swap(a［i］［j］,a［j］［i］);
return true;
}
5. 解： 当m≠n时返回false。置s为0，用s累加a的左上角右下角元素a［i］［i］(0≤i<m)之和，再累加a的右上角左下角元素a［j］［n-j-1］(0≤j<n)之和。当m为奇数时，两条对角线有一个重叠的元素a［m/2］［m/2］，需从s中减去; 当m为偶数时,没有重叠的元素。最后返回true。对应的算法如下：
bool Diag(int a［M］［N］,int m,int n,int &s)
{if (m!=n) return false;
s=0;
for (int i=0;i<m;i++) s+=a［i］［i］;
for (int j=0;j<=n;j++) s+=a［j］［n-j-1］;
if (m%2==1) //m为奇数时
s-=a［m/2］［m/2］;
return true;
}
5.3基础实验题及其参考答案
5.3.1基础实验题
1. 编写一个实验程序，给定一个m行n列的二维数组a，每个元素的长度k，数组的起始地址d，该数组按行优先还是按列优先存储，数组的初始下标c1(假设a的行、列初始下标均为c1)，求元素a［i］［j］的地址，并用相关数据进行测试。
2. 编写一个实验程序，给定一个n阶对称矩阵A，采用压缩存储存储在一维数组B中，指出存储下三角+主对角部分的元素还是上三角+主对角部分的元素，按行优先还是按列优先，A的初始下标c1和B的初始下标c2，求元素A［i］［j］在B中的地址k，并用相关数据进行测试。
3. 编写一个实验程序，假设稀疏矩阵采用三元组压缩存储，设计相关基本运算算法，并用相关数据进行测试。
5.3.2基础实验题参考答案
1. 解： 二维数组a的存储结构参见《教程》第5章中的5.1.2节。对应的程序如下：
#include<iostream>
using namespace std;
int addr()
{int m,n,k,d,i,j,c1,c2,flag,loc;
printf("m n k: ");
scanf("%d%d%d",&m,&n,&k);
printf("起始地址: ");
scanf("%d",&d);
printf("1-按行优先2-按列优先: ");
scanf("%d",&flag);
printf("初始下标: ");
scanf("%d",&c1);
c2=c1;
printf("元素 i j: ");
scanf("%d%d",&i,&j);
if (flag==1)
loc=d+((i-c1)*(n-c2+1)+(j-c2))*k;
else
loc=d+((j-c2)*(m-c1+1)+(i-c1))*k;
printf("元素a［%d］［%d］的地址:%d＼n",i,j,loc);
}
int main()
{printf("＼n计算二维数组元素地址＼n");
addr();
return 0;
}
图5.1第5章基础实验题1
的执行结果
上述程序的一次执行结果如图5.1所示。
2. 解： 假设n阶对称矩阵A的行、列起始地址为c1，压缩存放的一维数组B的起始地址为c2，分4种情况讨论。
(1) 采用按行优先方式压缩存储下三角+主对角部分元素。
对于元素aij(i≥j)，前面存放c1~i-1的行元素，共i-c1行，第c1行有一个元素，第c1+1行有两个元素，…，第i-1行有i-c1个元素，共有(1+i-c1)(i-c1)/2个元素。在第i行中前面存放的元素是a［i］［c1..j-1］，共j-c1个元素，则k=(1+i-c1)(i-c1)/2+j-c1+c2。
对于元素aij(i<j)，对应的地址k=(1+j-c1)(j-c1)/2+i-c1+c2。
(2) 采用按列优先方式压缩存储下三角+主对角部分元素。
对于元素aij(i≥j)，前面存放c1~j-1的列元素，共j-c1列，第c1列有n个元素，第c1+1列有n-1个元素，…，第j-1列有n-j+c1+1个元素，共有(2n-j+c1+1)(j-c1)/2个元素。在第j行中前面存放的元素是a［i-1..j］［j］，共i-j个元素，则
k=(2n-j+c1+1)(j-c1)/2+i-j+c2。
对于元素aij(i<j)，对应的地址k=(2n-i+c1+1)(i-c1)/2+j-i+c2。
(3) 采用按行优先方式压缩存储上三角+主对角部分元素。
对于元素aij(i≤j)，前面存放c1~i-1的行元素，共i-c1行，第c1行有n个元素，第c1+1行有n-1个元素，…，第i-1行有n-i+c1+1个元素，共有(2n-i+c1+1)(i-c1)/2个元素。在第i行中前面存放的元素是a［i］［i..j-1］，共j-i个元素，则
k=(2n-i+c1+1)(i-c1)/2+j-i+c2。
对于元素aij(i>j)，对应的地址k=(2n-j+c1+1)(j-c1)/2+i-j+c2。
(4) 采用按列优先方式压缩存储上三角+主对角部分元素。
对于元素aij(i≤j)，前面存放c1~j-1的列元素，共j-c1列，第c1列有一个元素，第c1+1列有两个元素，…，第j-1列有j-c1个元素，共有(1+j-c1)(j-c1)/2个元素。在第j列中前面存放的元素是a［c1..i-1］［j］，共i-c1个元素，则
k=(1+j-c1)(j-c1)/2+i-c1+c2。
对于元素aij(i>j)，对应的地址k=(1+i-c1)(i-c1)/2+j-c1+c2。
对应的程序如下：
#include<iostream>
using namespace std;
int addr()
{int n,k,i,j,c1,c2,tag,flag;
printf("n: ");
scanf("%d",&n);
printf("1-下三角+主对角 2-上三角+主对角: ");
scanf("%d",&tag);
printf("1-按行优先2-按列优先: ");
scanf("%d",&flag);
printf("A的初始下标 B的初始下标: ");
scanf("%d%d",&c1,&c2);
printf("元素 i j: ");
scanf("%d%d",&i,&j);
if (tag==1)
{if (flag==1) //(1)
{if (i>=j) k=(1+i-c1)*(i-c1)/2+j-c1;
else k=(1+j-c1)*(j-c1)/2+i-c1;
}
else //(2)
{if (i>=j) k=(2*n-j+c1+1)*(j-c1)/2+i-j+c2;
else k=(2*n-i+c1+1)*(i-c1)/2+j-i+c2;
}
}
else
{if (flag==1) //(3)
{if (i<=j) k=(2*n-i+c1+1)*(i-c1)/2+j-i+c2;
else k=(2*n-j+c1+1)*(j-c1)/2+i-j+c2;
}
else //(4)
{if (i<=j) k=(1+j-c1)*(j-c1)/2+i-c1+c2;
else k=(1+i-c1)*(i-c1)/2+j-c1+c2;
}
}
printf("元素a［%d］［%d］的压缩存储地址k=%d＼n",i,j,k);
}
int main()
{printf("＼n计算对称矩阵压缩存储时元素地址＼n");
addr();
return 0;
}
上述程序执行的4种情况及其结果如图5.2所示。
图5.2第5章基础实验题2的执行结果
3. 解： 稀疏矩阵三元组压缩存储结构及其基本运算算法设计参见《教程》中的第5.3.1节。对应的程序如下：
#include<iostream>
using namespace std;
const int MAXR=20; //稀疏矩阵的最大行数
const int MAXC=20; //稀疏矩阵的最大列数
const int MaxSize=100; //三元组顺序表的最大元素个数
struct TupElem //单个三元组元素的类型
{int r; //行号
int c; //列号
int d; //元素值
TupElem() {} //构造函数
TupElem(int r1,int c1,int d1) //重载构造函数
r=r1;
c=c1;
d=d1;
}
};
class TupClass //三元组存储结构类
{int rows; //行数
int cols; //列数
int nums; //非零元素的个数
TupElem *data; //稀疏矩阵对应的三元组顺序表
public:
TupClass() //构造函数
{data=new TupElem［MaxSize］; //分配空间
nums=0;
}
~TupClass() //析构函数
{
delete ［］ data; //释放空间
}
void CreateTup(int A［］［MAXC］,int m,int n) //创建三元组
{rows=m; cols=n; nums=0;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
if (A［i］［j］!=0) //只存储非零元素
{data［nums］=TupElem(i,j,A［i］［j］);
nums++;
}
}
bool Setvalue(int i,int j,int x) //三元组元素赋值A［i］［j］=x
{if (i<0 || i>=rows || j<0 || j>=cols)
return false; //下标错误时返回false
int k=0,k1;
while (k<nums && i>data［k］.r)
k++; //查找第i行的第一个非零元素
while (k<nums && i==data［k］.r && j>data［k］.c)
k++; //在第i行中查找第j列的元素
if (data［k］.r==i && data［k］.c==j) //找到了这样的元素
data［k］.d=x;
else //不存在这样的元素时插入一个元素
{for (k1=nums-1; k1>=k;k1--) //后移元素以便插入
{data［k1+1］.r=data［k1］.r;
data［k1+1］.c=data［k1］.c;
data［k1+1］.d=data［k1］.d;
}
data［k］.r=i; data［k］.c=j; data［k］.d=x;
nums++;
}
return true; //赋值成功时返回true
}
bool GetValue(int i,int j,int &x) //将指定位置的元素值赋给变量x=A［i］［j］
{if (i<0 || i>=rows || j<0 || j>=cols)
return false; //下标错误时返回false
int k=0;
while (k<nums && data［k］.r<i)
k++; //查找第i行的第一个非零元素
while (k<nums && data［k］.r==i && data［k］.c<j)
k++; //在第i行中查找第j列的元素
if (data［k］.r==i && data［k］.c==j) //找到了这样的元素
x=data［k］.d;
else
x=0; //在三元组中没有找到表示是零元素
return true; //取值成功时返回true
}
void DispMat() //输出三元组
{if (nums<=0) return; //没有非零元素时返回
cout << "＼t" << rows << "＼t" << cols << "＼t" << nums << endl;
cout << "＼t------------------＼n";
for (int i=0;i<nums;i++)
cout << "＼t" << data［i］.r << "＼t" << data［i］.c << "＼t" << data［i］.d << endl;
}
};
int main()
{TupClass t,tb;
int x;
int a［MAXR］［MAXC］={{0,0,1,0,0,0,0},{0,2,0,0,0,0,0},{3,0,0,0,0,0,0},
{0,0,0,5,0,0,0},{0,0,0,0,6,0,0},{0,0,0,0,0,7,4}};
int m=6,n=7;
printf("＼n稀疏矩阵A:＼n");
for (int i=0;i<m;i++)
{for (int j=0;j<n;j++)
printf("%4d",a［i］［j］);
printf("＼n");
}
t.CreateTup(a,6,7);
cout << "三元组t表示:＼n"; t.DispMat();
cout << "执行A［4］［1］=8＼n";
t.Setvalue(4,1,8);
cout << "三元组t表示:＼n"; t.DispMat();
cout << "求x=A［4］［1］＼n";
t.GetValue(4,1,x);
cout << "x=" << x << endl;
return 0;
}
上述程序的执行结果如图5.3所示。
图5.3第5章基础实验题3的执行结果
5.4应用实验题及其参考答案
5.4.1应用实验题
1. 给定n(n≥1)个整数的序列用整型数组a存储，要求求出其中的最大连续子序列之和。例如序列(-2，11，-4，13，-5，-2)的最大连续子序列和为20，序列(-6，2，4，-7，5，3，2，-1，6，-9，10，-2)的最大连续子序列和为16。分析算法的时间复杂度。
2. 求马鞍点问题。如果矩阵a中存在一个元素a［i］［j］满足条件“a［i］［j］是第i行中值最小的元素，且又是第j列中值最大的元素”，则称之为该矩阵的一个马鞍点。设计一个程序，计算出m×n的矩阵a的所有马鞍点。
3. 对称矩阵压缩存储的恢复。一个n阶对称矩阵A采用一维数组a压缩存储，压缩方式是按行优先顺序存放A的下三角和主对角线部分的各元素。完成以下功能：
(1) 由A产生压缩存储a。
(2) 由一维数组b来恢复对称矩阵A。
通过相关数据进行测试。
5.4.2应用实验题参考答案
1. 解： 含有n个整数的序列为a［0..n-1］，这里提供3种解法求其中的最大连续子序列之和。
解法1： 枚举所有连续子序列a［i..j］(i≤j)，求出它的所有元素之和thisSum，并通过比较将最大值存放在maxSum中，最后返回maxSum。对应的程序如下：
#include<iostream>
using namespace std;
int maxSubSum(int a［］,int n)
{int maxSum=a［0］,thisSum;
for (int i=0;i<n;i++) //三重循环穷举所有的连续子序列
{for (int j=i;j<n;j++)
{thisSum=0;
for (int k=i;k<=j;k++)
thisSum+=a［k］;
if (thisSum>maxSum) //通过比较求最大连续子序列之和
maxSum=thisSum;
}
}
return maxSum;
}
void disp(int a［］,int n) //输出a
{for (int i=0;i<n;i++) printf(" %d",a［i］);
printf("＼n");
}
int main()
{int a［］={-2,11,-4,13,-5,-2};
int n=sizeof(a)/sizeof(a［0］);
int b［］={-6,2,4,-7,5,3,2,-1,6,-9,10,-2};
int m=sizeof(b)/sizeof(b［0］);
printf("＼na:"); disp(a,n);
printf("a的最大连续子序列和: %d＼n",maxSubSum(a,n));
printf("＼nb:"); disp(b,m);
printf("b的最大连续子序列和: %d＼n",maxSubSum(b,m));
return 0;
}
上述程序的执行结果如图5.4所示。maxSubSum()采用三重for循环，对应的时间复杂度为O(n3)。
图5.4第5章应用实验题1的执行结果
解法2： 设置前缀和数组sum，sum［i］=a［0］+a［1］+…+a［i］，枚举i和j(i≤j)求a［i..j］中的所有元素之和，即sum［j］-sum［i-1］，比较求出最大值ans，最后输出ans。对应的程序如下：
#include<iostream>
using namespace std;
int maxSubSum(int a［］,int n)
{int *sum= new int［n］; //存放前缀和
sum［0］=a［0］;
for(int i=1;i<n;i++)
sum［i］=a［i］+sum［i-1］;
int ans=a［0］; //ans保存最大子序列之和
for (int i=0;i<n;i++)
for(int j=i;j<n;j++)
{int s=sum［j］-sum［i-1］;
ans=max(ans,s);
}
delete ［］ sum;
return ans;
}
void disp(int a［］,int n) //输出a
{for (int i=0;i<n;i++) printf(" %d",a［i］);
printf("＼n");
}
int main()
{int a［］={-2,11,-4,13,-5,-2};
int n=sizeof(a)/sizeof(a［0］);
int b［］={-6,2,4,-7,5,3,2,-1,6,-9,10,-2};
int m=sizeof(b)/sizeof(b［0］);
printf("＼na:"); disp(a,n);
printf("a的最大连续子序列和: %d＼n",maxSubSum(a,n));
printf("＼nb:"); disp(b,m);
printf("b的最大连续子序列和: %d＼n",maxSubSum(b,m));
return 0;
}
上述maxSubSum()采用两重for循环，对应的时间复杂度为O(n2)。
解法3： 修改a［i］表示以位置i结尾的最大连续子序列之和。对于序列a，用ans表示其中的最大连续子序列之和，显然ans至少为0(因为0个元素也是其中的一个连续子序列，其和为0)，当a［0］<0的修改为a［0］=0，用i迭代，若a［i-1］≤0则舍弃前面的子序列，从a［i］开始计，若a［i-1］>0，则该连续子序列再加上a［i］称为更大连续子序列，即a［i］+a［i-1］。求出最大的a［i］为ans，最后输出ans。对应的程序如下：
#include<iostream>
using namespace std;
int maxSubSum(int a［］,int n)
{if (a［0］<0) a［0］=0; //修改a［i］表示以位置i结尾的最大连续子序列之和
int ans=a［0］;
for(int i=1;i<n;i++)
{if (a［i-1］>0) a［i］+=a［i-1］;
else a［i］+=0;
ans=max(ans,a［i］);
}
return ans;
}
void disp(int a［］,int n) //输出a
{for (int i=0;i<n;i++)
printf(" %d",a［i］);
printf("＼n");
}
int main()
{int a［］={-2,11,-4,13,-5,-2};
int n=sizeof(a)/sizeof(a［0］);
int b［］={-6,2,4,-7,5,3,2,-1,6,-9,10,-2};
int m=sizeof(b)/sizeof(b［0］);
printf("＼na:"); disp(a,n);
printf("a的最大连续子序列和: %d＼n",maxSubSum(a,n));
printf("＼nb:"); disp(b,m);
printf("b的最大连续子序列和: %d＼n",maxSubSum(b,m));
return 0;
}
上述maxSubSum()采用一重for循环，对应的时间复杂度为O(n)。
2. 解： 对于二维数组a［m］［n］，先求出每行的最小值元素放入min数组中，再求出每列的最大值元素放入max数组中。若min［i］=max［j］，则元素a［i］［j］便是马鞍点，找出所有这样的元素并输出。对应的实验程序Exp22.cpp如下：
#include<iostream>
#include<vector>
using namespace std;
#define MAXM 10
#define MAXN 10
vector<vector<int> > MinMax(int a［MAXM］［MAXN］,int m,int n) //求所有马鞍点
{int *mind=new int［m］; //存放每行的最小元素
int *maxd=new int［n］; //存放每列的最大元素
for (int i=0;i<m;i++) //计算每行的最小元素，放入mind［i］中
{mind［i］=a［i］［0］;
for (int j=1;j<n;j++)
if (a［i］［j］<mind［i］)
mind［i］=a［i］［j］;
}
for (int j=0;j<n;j++) //计算每列的最大元素，放入maxd［j］中
{maxd［j］=a［0］［j］;
for (int i=1;i<m;i++)
if (a［i］［j］>maxd［j］)
maxd［j］=a［i］［j］;
}
vector<vector<int> > ans;
for (int i=0;i<m;i++) //判定是否为马鞍点
for (int j=0;j<n;j++)
if (mind［i］==maxd［j］) //找到一个马鞍点
{vector<int> e;
e.push_back(i);
e.push_back(j);
e.push_back(a［i］［j］);
ans.push_back(e);
}
return ans;
}
void disp(int a［MAXM］［MAXN］,int m,int n) //输出二维数组
{for (int i=0;i<m;i++)
{for (int j=0;j<n;j++) printf("%4d",a［i］［j］);
printf("＼n");
}
}
int main()
{int a［MAXM］［MAXN］={{10,3,3,4},{15,10,1,3},{4,5,3,6}};
int m=3,n=4;
printf("＼n a:＼n"); disp(a,m,n);
printf(" 所有马鞍点:＼n");
vector<vector<int> > ans;
ans=MinMax(a,m,n);
for (int i=0;i<ans.size();i++)
printf(" (%d,%d): %d＼n",ans［i］［0］,ans［i］［1］,ans［i］［2］);
return 0;
}
图5.5第5章应用实验题2
的执行结果
上述程序的执行结果如图5.5所示。
3. 解： 设A为n阶对称矩阵，若其压缩数组a中的m个元素，则有n(n+1)/2=m，即n2+n-2m=0，求得n=(int)(-1+sqrt(1+8m))/2。
若A的下三角或者主对角线A［i］［j］(i≥j)元素值存放在b［k］中，则k=i(i+1)/2+j，显然i(i+1)/2≤k，可以求出i≤(-1+sqrt(1+8k))/2，则i=int((-1+sqrt(1+8k))/2)，j=k-i(i+1)/2。由此设计由k求出i、j下标的算法getij(k)。
对应的实验程序Exp23.cpp如下：
#include<iostream>
#include<cmath>
using namespace std;
#define MAXM 10
#define MAXN 10
void disp(int A［MAXM］［MAXN］,int n) //输出二维数组A
{for (int i=0;i<n;i++)
{for (int j=0;j<n;j++) printf("%4d",A［i］［j］);
printf("＼n");
}
}
void compression(int A［MAXM］［MAXN］,int n,int a［］) //将A压缩存储到a中
{for (int i=0;i<n;i++)
for (int j=0;j<=i;j++)
{int k=i*(i+1)/2+j;
a［k］=A［i］［j］;
}
}
void getij(int k,int &i,int &j) //由k求出i、j下标
{i=int((-1+sqrt(1+8*k))/2);
j=k-i*(i+1)/2;
}
void Restore(int b［］,int s,int C［MAXM］［MAXN］,int &n) //由b恢复成C
{int i,j;
n=int((-1+sqrt(1+8*s))/2);
for (int k=0;k<s;k++) //求主对角线和下三角部分元素
{getij(k,i,j);
C［i］［j］=b［k］;
}
for (i=0;i<n;i++) //求上三角部分元素
for (j=i+1;j<n;j++)
C［i］［j］=C［j］［i］;
}
int main()
{printf("＼n *********测试1**********＼n");
int n=3,s=n*(n+1)/2;
int A［MAXM］［MAXN］={{1,2,3},{2,4,5},{3,5,6}};
int C［MAXM］［MAXN］;
int *a=new int［s］;
printf(" A:＼n"); disp(A,n);
printf(" A压缩得到a＼n");
compression(A,n,a);
printf(" a:＼n");
for (int i=0;i<s;i++) printf("%d",a［i］);
printf("＼n");
printf(" 由a恢复得到C＼n");
Restore(a,s,C,n);
printf(" C:＼n"); disp(C,n);
printf("＼n *********测试2**********＼n");
n=4;
s=n*(n+1)/2;
int B［MAXM］［MAXN］={{1,2,3,4},{2,5,6,7},{3,6,8,9},{4,7,9,10}};
int D［MAXM］［MAXN］;
int *b=new int［s］;
printf(" B:＼n"); disp(B,n);
printf(" B压缩得到b＼n");
compression(B,n,b);
printf(" b:＼n");
for (int i=0;i<s;i++) printf("%d",b［i］);
printf("＼n");
printf(" 由b恢复得到D＼n");
Restore(b,s,D,n);
printf(" D:＼n"); disp(D,n);
return 0;
}
上述程序的执行结果如图5.6所示。
图5.6第5章应用实验题3的执行结果