严蔚敏《数据结构C语言习题集》详解与答案
需积分: 0 143 浏览量
更新于2024-08-02
收藏 370KB PDF 举报
严蔚敏的《数据结构(C语言版)习题集》是一本针对计算机科学中重要概念——数据结构的经典教材，该书习题集的答案详细且全面地覆盖了书中算法设计部分。作者以kaoyan.com计算机版版主一具为主导，汇集了网友siice、龙抬头、iamkent、zames、birdthinking等人的贡献，共同完成了答案的修订和完善。
答案部分注重实用性，所有算法采用类C语言进行描述，目的是便于交流和阅读理解，但需要注意的是，由于教学性质，作者并不保证提供的代码可以直接在所有环境下正常运行。对于复杂或独特思路的问题，答案可能包含源代码和简要分析，而对于未解决的题目如5.20和10.40，仅提供必要的讨论。
章节1.16中，`print_descending`函数用于按从大到小的顺序输出三个整数。通过嵌套的条件判断和交换操作，实现了冒泡排序算法，最后打印出排序后的结果。1.17题是关于求解k阶斐波那契序列的第m项，`fib`函数采用了记忆化搜索的方法，通过保存中间计算结果，显著减少了重复计算，提高了效率。该函数首先检查输入的合理性，然后使用两层循环计算斐波那契数列，并在循环结束后返回第m项的值。
值得注意的是，该解答鼓励读者在尝试解决问题和深入思考后再查阅答案，以增强自我学习的效果。同时，作者也提醒读者，由于作者的知识和技能有限，可能存在错误和不足，鼓励读者在阅读时积极发现并提出改进建议，共同提升解题技巧。
总结来说，这本习题集答案集不仅提供了实用的编程技巧，还包含了对算法设计思想的讲解，是学习数据结构与C语言实践的好参考资料。
分析:本算法采用了类似于图的广度优
先遍历的思想,用两个队列保存相邻同
色点的横坐标和纵坐标.递归形式的算
法该怎么写呢?
3.21
void NiBoLan(char *str,char *new)//把
中缀表达式 str 转换成逆波兰式 new
{
p=str;q=new; //为方便起见,设 str 的两
端都加上了优先级最低的特殊符号
InitStack(s); //s 为运算符栈
while(*p)
{
if(*p 是字母)) *q++=*p; //直接输出
else
{
c=gettop(s);
if(*p 优先级比 c 高) push(s,*p);
else
{
while(gettop(s)优先级不比*p 低)
{
pop(s,c);*(q++)=c;
}//while
push(s,*p); //运算符在栈内遵循越
往栈顶优先级越高的原则
}//else
}//else
p++;
}//while
}//NiBoLan //参见编译原理教材
3.22
int GetValue_NiBoLan(char *str)//对逆
波兰式求值
{
p=str;InitStack(s); //s 为操作数栈
while(*p)
{
if(*p 是数) push(s,*p);
else
{
pop(s,a);pop(s,b);
r=compute(b,*p,a); //假设 compute
为执行双目运算的过程
push(s,r);
}//else
p++;
}//while
pop(s,r);return r;
}//GetValue_NiBoLan
3.23
Status NiBoLan_to_BoLan(char
*str,stringtype &new)//把逆波兰表达式
str 转换为波兰式 new
{
p=str;Initstack(s); //s 的元素为
stringtype 类型
while(*p)
{
if(*p 为字母) push(s,*p);
else
{
if(StackEmpty(s)) return ERROR;
pop(s,a);
if(StackEmpty(s)) return ERROR;
pop(s,b);
c=link(link(*p,b),a);
push(s,c);
}//else
p++;
}//while
pop(s,new);
if(!StackEmpty(s)) return ERROR;
return OK;
}//NiBoLan_to_BoLan
分析:基本思想见书后注释.本题中暂
不考虑串的具体操作的实现,而将其看
作一种抽象数据类型 stringtype,对其可
以进行连接操作:c=link(a,b).
3.24
Status g(int m,int n,int &s)//求递归函数
g 的值 s
剩余78页未读，继续阅读
2022-07-14 上传
2013-08-05 上传
点击了解资源详情
346 浏览量
2009-09-27 上传
