data structures and algorithms

好几年前就入手了《算法C++实现》，到现在都没看，断断续续在看《C++ Primer Plus》，一直没什么时间，只完成了一半。

最近学java，凭借着C++的基础，在网上看了点文档，就着手开始用java写代码。当我解Distances in Trees时，一如既往地简单粗暴去解决问题，写下了NWCK.java，当我写完程序之后，发现多半情况下是没有问题的，但在计算只有括号而没有逗号的树时，比如：

(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))Pagophila_viridis))Ovis_cavirostris))))))))))))))))))))))))))))))))))))))))))))))))))))));

距离会被少算了2，我花了很多时间，才发现问题出在这里，又花了很多时间，实在没看出代码有什么问题，于是判断一下，没有逗号，距离就+2，我自己都觉得这样的代码太tricky。

于是哥怒了，正如Linus Torvalds所说：

    Bad programmers worry about the code. Good programmers worry about data structures and their relationships.


为了存储树，我要学数据结构，在看了amazon上的书评，我选择了《data structures and algorithms in java》这本，港大图书馆有一堆java数据结构的书，偏偏就没有这本，于是我盯着电脑看电子版！花了一个月的时间，看完之后，并不后悔看瞎了狗眼，这本书总的来说，还是相当不错的，这类书通常看着都比较痛苦，但这本书一路看下来，还是蛮友好的，作者写了一些applet来演示，上面废话好多，我通常都是跳过，课后的题，我也没做。

看完了书，重新回到nwck的题上，于是有了NWCK2.java，使用了图来存储树，计算的代码更容易写了，逻辑也更加清晰了，这样有问题也容易debug，也容易扩展，而且程序的速度也提高了。

这里在定位节点的时候，实现了breadth first search，对于遍历的节点，使用Queue来存储，而Queue又是以之前写的LinkedList来实现。

有了这个数据结构，扩展起来也容易，加权树实现起来，也就是1个小时的事情。

始于nwck树解析的需求，到现在成功实现，希望这是告别屌丝码农的开始。

以上权当是《data structures and algorithms in java》的书评吧。

原文： http://ygc.name/2014/07/09/data_structures_algorithms/