第五章 数组和广义表(3)

WHILE(8) _DO

BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort}

【解答】本算法中，首先数组b中元素以逆置顺序放入d数组中，然后数组a和数组d的元素比较，将大者拷贝到数组c。第一个WHILE循环到数组a或数组d结尾，第二个和第三个WHILE语句只能执行其中的一个。 （1）b[m-i+1] （2）x:=a[i] （3）i:=i+1 （4）x:=d[j] （5）j:=j+1 （6）k:=k+1 （7）i<=l （8）j<=m

3．完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。 typedef struct glistnode {int tag;

struct glistnode *next; union{char data;

struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p;

{glist q,h,t,s; if(p==NULL) q=NULL; else

{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0; q->val.data=p->val.data; } else {(2) if (3)

{t=reverse(p->val.ptr.tp); s=t;

while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp; s->val.ptr.tp=(glist)malloc(sizeof(gnode)); s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL; s->val.ptr.hp=h; (4) __ }

else {q=(glist)malloc(sizeof(gnode));q->tag=1; q->val.ptr.tp=NULL; (5) ; } } }

return(q); }

【解答】逆置广义表的递归模型如下

11

上面append(a,b)功能是将广义表a和b作为元素的广义表连接起来。 （1）(p->tag==0) ∥处理原子 （2）h=reverse(p->val.ptr.hp) ∥处理表头

（3）(p->val.ptr.tp) ∥产生表尾的逆置广义表 （4）s->val.ptr.tp=t; ∥连接

（5）q->val.ptr.hp=h ∥头结点指向广义表

4．完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,?,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即 (示意圖编者略)。 #define NMAX 10 #include “stdio.h” main()

{ int i,j,n,k,p,q,m; int a [NMAX][NMAX]; scanf(“%d”,&n); m=1;

for(k=1；(1) ；k++) {if（k

{if(3) {i=q-p+1；j=p；} else{i=p；j=q-p+1；}

if(4) {i=i+n-q；j=j+n-q；} a[i][j]=m；(5) _; }

for（i=1；i<=n;i++） { for（j=1；j<=n；j++）

printf（“M”,a[i][j]）;printf(“\\n”); } } }

【解答】本题要求将1，2，...,n*n个自然数，按蛇形方式存放在二位数组A[n][n]中。“蛇型”方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放n2个整数。对角线共2n-1条，在副对角线上方的对角线，题目中用k表示第k条对角线（最左上角k=1），数组元素的x和y方向坐标之和为k+1（即题目中的i+j=k+1）。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。 (1)k<=2*n-1∥共填2*n-1条对角线

(2)q=2*n-k ∥副对角线以下的各条对角线上的元素数

12

(3)k%2！=0 ∥k为偶数时从右上到左下，否则从左下向右上填数(本处计算下标i和j）

(4)k>=n ∥修改副对角线下方的下标i和j。

(5)m++；或m=m+1 ∥为填下个数作准备，m变化范围1..n*n。 本题解法的另一种思路见本章算法设计题第9题。

5．约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1--n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去 ，直到所有的人都出圈为止。

PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer); BEGIN

FOR i:= 1 TO n DO A[i]:=i; sl:=s;

FOR i:=n DOWNTO 2 DO

BEGIN sl:= (1) __；//计算出圈人s1 IF sl=0 THEN (2) _； w:=A[sl]; //A[s1]出圈

FOR j:= (3) __ DO A[j]:=A[j+1]; A[i]:=w; END;

write('出圈序列为：’)；//输出出圈序列

FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END;

【解答】本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。

按题中要求，从第s个人开始报数，报到第m个人，此人出圈。n个人围成一圈，可看作环状，则下个出圈人，其位置是(s+m-1)%n。n是人数，是个变量，出圈一人后人数减1，算法中用i表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下标）存放到当时最后一个人的位置（下标）。算法最后打印出圈人的顺序。 (1)(s+m-1)MOD i∥计算出圈人s1

(2)s1:=i ∥若s1=0,说明是第i个人出圈（i%i=0）

(3)s1 TO i-1 ∥从s1到i依次前移,人数减1,出圈人放到当前最后一个位置A[i]=w

6．对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列，如n=4，程序输出为； 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1

test 是实现该功能的C程序段，请将未完成的部分补足，使之完整。test函数为一递归函数，参数n为被分解和式的数，k为当前的分解深度。算法思想是对n的所有合理的和式分解，将分解出的数（称为和数）存于数组a[]中。当其中一个分解已不再需要进一步进行时，即找到一个解，将存于a[] 中的一个完整

13

和式的和数输出。当还需要进一步分解的数及分解时，以要进一步分解的数及分解深度为参数，递归调用test函数。 #define MAXN 100 int a[MAXN]；

test(int n, int k) {int i,j;

for(j= ; j>=1;j--) (3分) {a[k]=j;

if( ) (3分) {printf(“%d= %d”,a[0],a[1]);

for (i=2;i<=k;i++) printf(“ + %d”,a[i]); printf(“\\n”);

}

else test( ;k+1); （4分） } } main()

{ test(4,1)； }

【解答】(1)n (2)j==n (3)n-j

七、算法设计题

1．设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。【东北大学 2000 六 (15分)】

[题目分析]本题是在向量D内插入元素问题。首先要查找插入位置，数据x插入到第i个数据组的末尾，即是第i+1个数据组的开始，而第i（1≤i≤n）个数据组的首地址由数组S（即数组元素S[i]）给出。其次，数据x插入后，还要维护数组S，以保持空间区D和数组S的正确的相互关系。 void Insert（int S[]，ElemType D[]，x，int i,m）

∥在m个元素的D数据区的第i个数据组末尾，插入新数据x，第i个数据组的首址由数组S给出

｛if（i<１|| i>n）｛printf（“参数错误\\n”）；exit（０）；｝

14

if（i==n） D[m]=x； ∥ 在第n个数据组末尾插入元素

else｛for（j=m-1;j>=S[i+1];j--）D[j+1]=D[j]; ∥ 第i＋１个数据组及以后元素后移

D[S[i+1]]=x; ∥ 将新数据x插入

for(j=i+1;j<=n;j++) S[j]++; ∥ 维护空间区D和数组S的的关系 } ∥结束元素插入

m++; ∥空间区D的数据元素个数增1 }∥ 算法Insert结束

[算法讨论] 数据在空间区D中从下标0开始，最后一个元素的下标是m-1。设空间区容量足够大，未考虑空间溢出问题。数组S随机存数，而向量D数据插入，引起数组元素向后移动，时间复杂度是O（n）。

2．设整数x1,x2,?,xn已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1,2,3,4,5,k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。【东南大学2001三(10分）】 [题目分析]从n个数中，取出所有k个数的所有组合。设数已存于数组A[1..n]中。为使结果唯一，可以分别求出包括A[n]和不包括A[n]的所有组合。即包括A[n]时，求出从A[1..n-1]中取出k-1个元素的所有组合，不包括A[n]时，求出从A[1..n-1]中取出k个元素的所有组合。 CONST n=10；k=3；

TYPE ARR=ARRAY[1..n] OF integer；

VAR A，B：ARR；∥ A中存放n个自然数，B中存放输出结果 PROC outresult；∥输出结果

FOR j：=1 TO k DO write（B[j]）；writeln； ENDP；

PROC nkcombination（i,j,k：integer）；

∥从i个数中连续取出k个数的所有组合，i个数已存入数组A中，j为结果数组B中的下标

IF k=0 THEN outresult

ELSE IF(i-k≥0）THEN [B[j]:=A[i]；j:=j+1；

nkcombination（i-1，k-1，j）； nkcombination（i-1，k，j-1）； ]

ENDP；

[算法讨论]本算法调用时，i是数的个数（题目中的n），k≤i，j是结果数组的下标。按题中例子，用nkcombination（5，1，3）调用。若想按正序输出，如123，124，?，可将条件表达式i-k≥0改为i+k-1≤n，其中n是数的个数，i初始调用时为1，两个调用语句中的i-1均改为i+1。 3．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 【上海大学 2000 三 （20分）】【中科院自动化所 1997】

[题目分析] 寻找马鞍点最直接的方法,是在一行中找出一个最小值元素,然后检查该元素是否是元素所在列的最大元素,如是,则输出一个马鞍点,时间复杂度

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第五章 数组和广义表(3)在线全文阅读。