第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和矩阵容量相比很小(tm×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］便是马鞍点，找出所有这样的元素并输出。对应的实验程序Exp22.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)。
对应的实验程序Exp23.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的执行结果