References for Part Two

There are numerous introductory textbooks on data structures. For example, the book by Standish covers linked structures, data abstraction, stacks and queues, memory allocation, and software engineering concepts at a more leisurely pace than here. Summit’s book (and its source on the web) is an invaluable source of detailed information about C implementations, as is, of course, the Kernighan and Ritchie classic. The book by Plauger is a thorough explanation of C library functions.

The designers of PostScript perhaps did not anticipate that their language would be of interest to people learning basic algorithms and data structures. However, the language is not difficult to learn, and the reference manual is both thorough and accessible.

The technique for implementing ADTs with pointers to structures that are not specified was taught by Appel in the systems programming course at Princeton in the mid 1980s. It is described in full detail, with numerous examples, in the book by Hanson. The Hanson and Summit books are both outstanding references for programmers who want to write bugfree and portable code for large systems.

Knuth’s books, particularly Volumes 1 and 3, remain the authoritative source on properties of elementary data structures. Baeza-Yates and Gonnet have more up-to-date information, backed by an extensive bibliography. Sedgewick and Flajolet cover mathematical properties of trees in detail.

Adobe Systems Incorporated, PostScript Language Reference Manual, second edition, Addison-Wesley, Reading, MA, 1990.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

D. R. Hanson, C Interfaces and Implementations: Techniques for Creating Reusable Software, Addison-Wesley, 1997.

B. W. Kernighan and D. M. Ritchie, The C Programming Language, second edition, Prentice-Hall, Englewood Cliffs, NJ, 1988.

D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition, Addison-Wesley, Reading, MA, 1973; Volume 2: Seminumerical Algorithms, second edition, Addison-Wesley, Reading, MA, 1981; Volume 3: Sorting and Searching, second printing, Addison-Wesley, Reading, MA, 1975.

P. J. Plauger, The Standard C Library, Prentice-Hall, Englewood Cliffs, NJ, 1992.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

T. A. Standish, Data Structures, Algorithms, and Software Principles in C, Addison-Wesley, 1995.

S. Summit, C Programming FAQs, Addison-Wesley, 1996.