专升本数据结构试题解析(16)

数据结构上机实验与习题解析 亱店↘打烊oO

free(s);

}

3．设整数序列a1，a2，…，an，给出求解最大值的递归程序。

【算法分析】根据题意，本题的函数定义为：

a[1] n=1 a[n]>maxvalue(a,n-1)

maxvalue(a,n-1) a[n]<maxvalue(a,n-1)

【算法源代码】

int MaxValue (int a[],int n)

/*设整数序列存于数组a中，共有n个，本算法求解其最大值*/

{int max;

if (n==1) max=a[1];

else if (a[n]>MaxValue(a,n-1)) max=a[n];

else max=MaxValue(a,n-1);

return(max);

}

4．试将下列递归函数改写为非递归函数。

void test(int *sum)

{

int x;

scanf("%d",&x);

if(x==0) *sum=0 ;

else {test(&sum); (*sum)+=x;}

printf("%5d",*sum);

}

【算法分析】

该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。

【算法源代码】

int test()

{

int x,sum=0,top=0,s[30];

scanf("%d",&x);

while (x!=0)

{s[++top]=a; scanf("%d",&x); }

printf("%5d",sum);

while (top)

{sum+=s[top--]; printf("%5d",sum); }

}

5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

【算法分析】

利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。

【算法源代码】

reverse(SqStack *s)

{SqStack *s1,*s2; /*s,s1,s2均为栈类型

ElemType x; /*栈中元素的类型，用于存储从栈中取出元素的临时变量*/

initstack(s1); /*栈的初始化*/

initstack(s2);

while(!stackempty(s)) /*如果栈不空，将s栈中的内容移到s1栈中*/

{pop(s,x); /*取栈顶元素放入变量x中*/

push(s1,x); /*将变量x入栈*/

}

while(!stackempty(s1)) /*如果栈不空，将s1栈中的内容移到s2栈中*/

{pop(s1,x);