数据结构简明教程
}
}
return max;
if (n>max) max=n;
上机实验题4
两个非空串s和t采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。
解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下：
#include
void main() {
SqString s,t,str;
Assign(s,\Assign(t,\SqString str;
int midx=0,mlen=0,tlen,i=0,j,k; while (i for (i=0;i str.length=mlen; return str; //返回最大公共子串 //将最大公共子串复制到str中 str.data[i]=s.data[midx+i]; j=0; { } i++; //继续扫描s中第i字符之后的字符 while (j if (s.data[i]==t.data[j]) //找一子串,在s中下标为i,长度为tlen { } else j++; tlen=1; for (k=1;i+k j+=tlen; //继续扫描t中第j+tlen字符之后的字符 && s.data[i+k]==t.data[j+k];k++) //将较大长度者赋给midx与mlen tlen++; midx=i; mlen=tlen; //用(midx,mlen)保存最大公共子串 //用i扫描串s //用j扫描串t //包含顺序串的基本运算函数 SqString maxcomstr(SqString s,SqString t) if (tlen>mlen) } printf(\printf(\ printf(\求s、t的最大公共子串str\\n\str=maxcomstr(s,t); printf(\ 练习题及参考答案 练习题5 1. 单项选择题 （1）假设有60行70列的二维数组a[1..60,1..70]（数组下标从1开始）以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ ）。 A.16902 B.16904 C.14454 D.以上都不对 答：A （2）对特殊矩阵采用压缩存储的目的主要是为了（ ）。 A.表达变得简单 B.对矩阵元素的存取变得简单 C.去掉矩阵中的多余元素 D.减少不必要的存储空间 答：D （3）一个n×n的对称矩阵，如果采用压缩存储以行或列为主序放入内存，则压缩存储的容量是（ ）。 A. n2 B. n2/2 C. n(n+1)/2 D. (n+1)2/2 答：C （4）设矩阵a是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组b[1..n(n-1)/2]中（数组下标均从1开始），对下三角部分中任一元素ai,j（i≤j）在一维数组b中下标k的值是（ ）。 A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j 答：B （5）有一个二维数组A，行下标的范围是0～8，列下标的范围是1～5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是（ ② ）和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是（ ④ ）和（ ⑤ ）。 A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 答：①H ②C ③E ④A ⑤F （6）有一个二维数组A，行下标的范围是1～6，列下标的范围是0～7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（ ① ）个字节。 27 数据结构简明教程 假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（ ② ）。若按行存储，则A[2,4]的第一个字节的地址是（ ③ ）。若按列存储，则A[5,7]的第一个字节的地址是（ ④ ）。 A.12 B.66 C.72 D.96 E.114 F.120 G.156 H.234 I.276 J.282 K.283 L.288 答：①L ②J ③C ④I （7）稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 答：C 2. 填空题 （1）三维数组A[c1..d1,c2..d2,c3..d3]（c1≤d1，c2≤d2，c3≤d3）共含有（ ）个元素。 答：(d1-c1+1)×(d2-c2+1)×(d3-c3+1)。 （2）已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是（ ）。 答：LOC(A[0][0])+(n×i+j)×k。 （3）二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（ ）。 答：326 （4）二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是（ ）。 答：1208 （5）有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储下三角部分，且A[0][0]存放在B[1]中），则A[8][5]在B中的地址是（ ）。 答：42 （6）设n阶下三角矩阵A[1..n][1..n]已压缩到一维数组S[1..n(n+1)/2]中，若按行序为主存储，则A[i][j]对应的S中的存储位置是（ ）。 答：i(i-1)/2+j。 （7）稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的（ ）。 答：行下标、列下标和元素值 3. 算法设计题 （1）假定数组A[0..n-1]的n个元素中有多个零元素，设计一个算法将A中所有的非零元素依次移到A的前端。 解：从前向后找为零的元素A[i]，从后向前找非零的元素A[j]，将A[i]和A[j]进行交换。对应的算法如下： void move(ElemType A[],int n) { } int i=0,j=n-1; ElemType tmp; while (i while (A[i]!=0) i++; while (A[j]==0) j--; if (i tmp=A[i]; A[i]=A[j]; A[j]=tmp; 练习题及参考答案 （2）已知一个n×n矩阵B按行优先存于一个一维数组A[0..n(n-1)]中，试给出一个就地算法将原矩阵转置后仍存于数组A中。 解：矩阵转置是将矩阵中第i行第j列的元素与第j行第i列的元素互换位置。因此先应确定矩阵与一维数组的映射关系：bi,j在一维数组A中的下标为i～n+j，bj,i在一维数组A中的下标为j×n+i。对应的算法如下： void trans(ElemType A[], int n) { } int i, j; ElemType tmp; for (i=0;i for (j=0;j tmp=A[i*n+j]; A[i*n+j]=A[j*n+i]; A[j*n+i]=tmp; （3）如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。设计一个算法求出m×n的矩阵A的所有马鞍点。 解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，则该元素A[i][j]便是马鞍点，找出所有这样的元素，即找到了所有马鞍点。实现程序如下： #include void minmax(int A[m][n]) { int i, j, have=0; int min[m], max[n]; for (i=0;i min[i]=A[i][0]; for (j=1;j 29 //计算出每行的最小值元素，放入min[m]之中 数据结构简明教程 } void main() { } int a[m][n]; int i, j; for (i=0;i for (j=0;j scanf(\ //调用minmax()找马鞍点 } for (j=0;j for (i=0;i for (j=0;j if (min[i]==max[j]) { } printf(\显示马鞍点 have=1; //判定是否为马鞍点 max[j]=A[0][j]; for (i=1;i if (A[i][j]>max[j]) max[j]=A[i][j]; //计算出每列的最大值元素，放入max[1..n]之中 if (A[i][j] min[i]=A[i][j]; if (!have) printf(\没有鞍点\\n\ minmax(a); （4）设有二维数组A[m][n]，其元素为整数，每行每列都按从小到大有序，试给出一个算法求数组中值为x的元素的行号i和列号j。设值x在A中存在，要求比较次数不多于m+n次。 解：由于算法要求比较次数不多于m+n次，因此不能按行扫描数组的每一元素，否则比较次数在最坏情况下可达m×n次。根据该数组的特点可从矩阵右上角按副对角线方向向左下角查找，算法如下： int find(int a[M][N],int x,int m,int n) { int i=0,j=n-1,flag=0; while (i if (a[i][j]!=x) { } if (a[i][j]>x) j--; else i++; flag=1; break; //修改列号 //修改行号 //a[i][j]==x else