|
|
About
|
The famous mathematician, physicist, theologian, and philosopher Sir Isaac Newton (1642 – 1727) once wrote, "If I have seen further [than certain other people], it is by standing on the shoulders of giants." This is very true in computer programming as well. Imagine if all programmers had to discover for themselves by trial and error how to solve common problems in programming! It is much better to learn the solutions that other programmers have already discovered and build upon that foundation.
This book is about those foundational solutions. It describes how to structure data and build algorithms to solve common programming tasks. Some of these techniques have names that come from ordinary non-computer life – e.g. stacks, queues, and sorting – and others have names that might be completely unfamiliar to a new student of programming – e.g. recursion, backtracking, and arrays – but they are all standards in the programmer's tool chest. Occasionally, a new tool is discovered – or at least, refined – and we include one which was just discovered in 1999 – introspective sort. But most of them have been part of the standard programmer's tool chest for decades.
Unlike the majority of textbooks in this field, this book takes a "code-first" approach. After a brief introduction of the concepts, a short complete ANSI-C program is presented for students to analyze. A number of questions arising from the code are then posed and answered in the Socratic format. In this way, we hope that the reader will not only become fluent in the concepts but also in the "nuts and bolts" of translating these concepts into functioning, efficient standard C code. Variable-Pointer (VP) diagrams are developed and used extensively to aid understanding of the more complex data structures and their manipulation.
You might be asking, why are we using such an old and established language as C instead of more modern languages like C++, Java, or Smalltalk? First of all, C is still the language of choice for many engineering tasks (i.e. there are reasons why an old language is still used), for example, device control, and in applications where speed is a prime concern. For example, the Linux operating system, although originally written in C++, was rewritten in C in order to increase its execution efficiency. For this reason, there are many engineering libraries available in C. Furthermore, many so-called "object-oriented" programs are actually not object-oriented at all, but rather " super-C " programs – programs with a procedural and not object-oriented structure that simply uses C++ as an extension of C. C++ has C at its heart. Even Java, which is a truly object-oriented language, still deliberately maintains syntax almost identical to C. Secondly, ANSI-C (American National Standards Institute version of C) is the universally accepted standard for the C language. For example, no matter what compiler you use Microsoft, Borland, GNU gcc if your coding compiles and runs on one compiler, it should compile and run using all these compilers. In contrast, if you write a program in Microsoft C, it may or may not compile in GNU gcc. The reason is that companies design their compilers to accept ANSI-C plus additional commands unique to the given compiler. In conclusion, learning and writing code according to the ANSI-C standard will produce portable, easy to read programs. Thirdly, if we used an object-oriented language, it would seem unnatural to rebuild most of the data structures covered from scratch, as they would already exist in the class library provided with the language. Object-oriented class libraries are a good facility for reuse of robust implementations of many of the data structures and algorithms presented in this book, but if you simply use the class libraries, you would not learn how they work in the first place.
It is essential for programmers to understand the underlying structures of the algorithms and data structures they use, to properly utilize them. Therefore, this book aims to teach you how things workinside the black box. For this purpose, C is an excellent language to use as we look at the structuring data and building algorithms.