PREFACE

One must learn by doing the thing, for though you can think you know it you have no certainty until you try it.

Sophocles

Data Structures, Algorithms, and Program Style Using C is intended for use in a second programming course, such as CS2 of the ACM curriculum, as well as in a Data Structures course. It will also be invaluable for computer professionals who wish to develop applications using the C programming language. All programs appear in C, although the concepts and methods presented are independent of the language used. The book emphasizes current techniques for the creation and testing of programs and stresses the importance of writing programs that are general enough to be readily adapted for use in the solution of complex problems. Data abstraction and modularity are stressed throughout. Complex concepts are presented in a concise, informal way; theory is coupled with concrete examples.

The book is written to provide a significant amount of flexibility in the order in which the material is covered, as illustrated in the accompanying chart. For a second programming/introductory data structures class, the fundamental concepts of structured programming and data structures are presented in Chapters 1 through 7. These chapters, combined with selected topics from Chapters 8 and 9, provide a challenging course. Chapters 8 through 13 deal with the application of the concepts to more complex problems and also introduce some advanced data structures. Where data structures are taught after the second programming course, selected material from Chapters 1 through 8 can serve as a quick review of the basics, followed by an in-depth study of Chapters 9 through 13. Care has been taken throughout to include sets of exercises that are graduated by degree of difficulty and complexity. Also included are suggested assignments that incorporate the essential concepts of each chapter.

Just as knowing the grammar of a natural language does not ensure quality writing, knowing the grammar of a programming language does not ensure quality programs. Learning to program well entails utilizing principles of good style and requires skill in the use of a wide variety of tools. It is an advanced task, beyond simply learning the grammar of a language. A master mechanic, upon opening the hood of an automobile, does not see a jumble of wires and metal, but rather essential components linked together and aligned in a systematic fashion. A knowledgeable programmer must learn not only to write programs but to read them in the same fashion as a master mechanic looks at an automobile engine. He or she has to be able to see the major components and linkages of the program. Program structure can enhance or obscure a program's intelligibility.

This book explains and demonstrates the tools needed to craft good programs and to solve substantial problems. These tools, although few in number, must be used with care and forethought. The tools include the basic paradigms for problem solving, for structuring programs, and for structuring data. Their proper use involves data abstraction, modularization, and the appropriate choice of data structures. Because the book emphasizes the entire program development process, readers will learn how to write well-designed programs and how to recognize them. They will, at the same time, develop insight into program analysis and learn how to analyze programs in order to determine their correctness and efficiency.

* Heapsort requires Chapter 7.

Many individuals contributed to this book. Special thanks are due to Sharon Doherty, Mary Helen Fein, Giorgio Ingargiola, and Paul LaFollette for their help, as well as to the students who labored through the early versions of the manuscript. The staff of PWS-KENT Publishing Company, including Bob Prior and Elise Kaiser, all provided valuable support and guidance. We would also like to thank David Hoyt for help during the production process. It is also a delight to acknowledge the painstaking and helpful work of the reviewers: James Calhoun,Western Illinois University; Michael Driscoll, DePaul University; Terry Hamberger, York College of Pennsylvania; Marek Holynski, Boston University; Sam C. Hsu, Florida Atlantic University; Paul W. Ross, Millersville University of Pennsylvania; Shai Simonson, University of Illinois at Chicago; John B. Tappen, University of Southern Colorado; and Therril Valentine, McNeese State University. Finally, and certainly most important, we deeply appreciate and thank our wives Nina and Judy and our children, who suffered from us and with us, avoided us and supported us, during the time this book was being written.

James F. Korsh

Leonard J. Garrett