本节书摘来自异步社区《编程珠玑(续)(修订版)》一书中的第2章,第2.5节习题,作者【美】Jon Bentley,更多章节内容可以访问云栖社区“异步社区”公众号查看。
2.5 习题
1.选择本章的一个Awk程序,然后用另外一种语言重新编写。两个程序在源代码规模和运行时效率上相比如何?
2.用各种方式加强FSM模拟器。考虑加入错误(坏状态、坏输入等)检查、默认转换以及字符类(例如整数和字母)。编写程序对一个简单的程序设计语言进行词法分析。
3.本章的拓扑排序程序在输入图有回路的情况下给出报告。修改这个程序以打印回路,让它在出现错误时更健壮一些。
4.说明由三维场景导出的图可能包含回路。给出可以保证无回路的限制条件。
5.为下面的任务设计程序。怎样使用关联数组来简化这些程序?
a.树。编写程序创建并遍历二叉树。
b.图。用深度优先搜索重写拓扑排序程序。给定一个有向图和一个结点x,返回所有从x可以到达的结点。给定一个带权图和两个结点x、y,返回从x到y的最短路径。
c.文档。使用一个简单的字典把一种自然语言翻译成另外一种自然语言(英-法字典中的一行可能包含两个单词“hello bonjour”)。为课本或程序文件准备交叉引用表,每个单词的所有引用都要用行号列出。Awk程序员可以试着使用输入字段分隔符和替换命令来完成对单词的更现实的定义。
d.随机句子生成。本程序的输入是一个如下的上下文无关文法:
S → NP VP
NP → AL N | N
N → John | Mary
AL→ A | A AL
A → Big | Little | Tiny
VP → V AvL
V → runs | walks
AvL → Av | AvL Av
Av → quickly | slowly
程序应当生成随机的句子,如“John walks quickly”或“Big Little Mary runs slowly quickly slowly”。
e.过滤器。第二个“名字”程序从文件里过滤出重复的单词,而拼写检查程序则过滤出字典中的单词。编写其他的单词过滤器,比如删除不在“批准列表”中的单词,按原来的顺序留下批准的单词。(当输入排好序时这些任务更容易。)
f.棋盘游戏。实现Conway的“生存游戏”。你可能会用到Awk的delete x[i]语句来删除旧的棋盘位置。
6.描述关联数组的多种实现,并分析每个元素的访问时间和存储成本。