|Data Structures and Algorithms in C++: Pocket Primer|
Author: Lee Wittenberg
This is a very thin book for a topic as big as data structures. This isn't necessarily a bad thing as there is room for something introductory and concise. The first thing that you need to know is that you do need to be a reasonable C++ programmer to get much from the book. You don't need to be an expert, however, as Chapter 1 takes the form of a C++ review. This isn't an introduction to C++ it is more a clarification of some of the trickier or advanced topics such as templates, inheritance and the Standard Template Library in particular.
This is where you first meet the unique feature of the book - its use of literate programming techniques originally developed by Donald Knuth. I've been a fan of literate programming for a long time - but only in theory. I have to admit that I've never made use of it beyond simply making my code as easy to read as possible. This book makes use of a tool called noweb to do the job properly. Rather than develop code stepwise by introducing small fragments and then putting it all together with the inevitable repetition this requires, noweb syntax is used to make the English-based examples compilable. For example, in:
it is clear that <given condition> and <do something> are placeholders for code that is yet to be defined. However, using noweb you can define <given condition> using:
When all of the placeholders have been defined in valid C++ then the tool can take them and spit out a C++ program. This makes the expression of the explanation of the program the same as the program. All of the programs are available on a bound in CD at the back so you can really make use of the programs as printed in the book.
I have to admit that I was really enthusiastic about the idea - I thought I might even use it in articles or other teaching material. The bad news is that when I started to read the book I found it increasingly confusing and irritating. The program might have no trouble constructing the final program, but I did. This might be just me, so don't let it put you off. It is not that it was bad, more that I was hoping it would work much better.
Most of the first chapter is taken up with explaining C++ and the STL. The big example is a Vector class, which is the first of the data structures. The second chapter is about big O notation. A very informal account without any deep math - which will please many readers.
From this point we move on to deal with some selected data structures. Chapter 3 is the linked list and Chapter 4 stacks and queues.
Chapter 5 takes time off to do recursion. This is mostly explanation by example and I've seen recursion explained better, but it does the job.
Chapters 6 and 7 are on binary trees and after going over simple trees we also have height balanced trees and heaps.
Chapter 8 moves on to sorting and all the well known algorithms are there including quick sort. The coverage is very brief, a paragraph and short program for each but it is enough for a first encounter. After sorting we have a chapter on hash tables. There is very little discussion of hash functions it is more about how you construct a simple hash table and deal with clashes.
The final chapter is on graphs - that is nodes and arcs not pie charts. It covers the basic representation of a network and traversals. Again a very brief introduction to the complicated world of graphs.
There is also an appendix which lists some must read books and for once I agree with the selection of classics - you really should read them all.
This is a pocket book and the brief coverage of the ideas and material fits this description. It is enough to get you started on the wider world of data structures and algorithms. There is hardly any math in the book and any big O analysis tends to simply state that the algorithm works like n or n2 without proof. The use of C++ tends to make things look more difficult than they are, but if you are learning C++ this isn't a negative point. The use of literate programming is an interesting experiment. For me it didn't work as well as I'd hoped, but it wasn't a disaster. If you are looking for a fairly shallow dive into the world of the most common data structures and their associated algorithms and you want to work in C++ this is a reasonable choice.
|Last Updated ( Saturday, 18 November 2017 )|