专升本数据结构试题解析(16)
时间:2025-07-10
时间:2025-07-10
数据结构上机实验与习题解析 亱店↘打烊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);