PREFACE
Data Structures in C++
Including Breadth and Laboratories
Angela B. Shiflet
Data Structures in C++, Including Breadth and Laboratories introduces CS2 or elementary data structures in a clear, visual, top-down manner. The text also offers a bridge from procedural programming to object-oriented programming in C++. The encapsulation, inheritance, and polymorphism available in C++ make it a better language for implementation of a data structure than C. The text assumes that the student has a background in programming with C or C++. For those students who had C in CS1, Appendix A covers the non-object-oriented features of C++ that are extensions to C.
After reviewing software engineering and such fundamental topics as recursion, the text discusses data abstraction from the perspectives of an abstract data type (ADT) or a set of data items and fundamental operations on this set and object-oriented programming. Chapter 3 examines ADTs for several types built into the language C++ (array, structure, pointer, and string). This chapter serves as a review and encourages the student to think in terms of data abstraction. We use C++ as "a better C" in code for Chapters 1-3. Chapter 4 presents the aspects of object-oriented programming in C++ that students need in studying data structures. The text does not attempt to be a comprehensive book on object-oriented programming or C++. Data Structures in C++ is foremost a data structures book, but one that uses the aspects of C++ that aid the study and application of the data structures.
The text first presents each data structure with an abstract data type definition description. Often with diagrams to clarify the words of the algorithms, the text develops applications using pseudocode and abstract operations. By first considering data structures on a high level without concern for the implementation details, the student obtains a powerful tool that simplifies the process of handling data and naturally extends the concept of structured programming. One of the major goals of data abstraction is to encapsulate the structure and hide the details of implementation from the user. With such information hidden, the programmer can consider applications on a higher plane with major operations as opposed to a lower level where there is danger of becoming lost in a sea of details.
After studying and using a data structure on the abstract data type level, the text examines how to encapsulate the structure and the operations into an object class in C++. Where advantageous, we employ polymorphism. Moreover, for data structures in later chapters, we inherit from classes of data structures in earlier chapters. Often, there are several ways to implement a particular ADT. The text also discusses the advantages and disadvantages of these implementations and the circumstances that make one more desirable than another.
Each chapter contains a laboratory section that is truly integrated with the topics in the text. The laboratories give a hands-on introduction to data structures with C++. They serve as tutorials to the material. Students can work through one or all the laboratory exercises in a self-paced fashion or in a closed laboratory environment. Each laboratory concentrates on the chapter's topics. For example, the laboratory for Chapter 3 leads the student through a procedural implementation of ADT rational number, while Chapter 4's laboratory shows its encapsulation in a C++ class. In Chapter 10, the students perform timing experiments with various sorting methods. Several laboratories, such as Chapter 6's laboratory to develop a program to simulate the line at a movie theater, have a team-work component. (The Instructor's Manual has suggestions for individual assignments as alternatives to the team assignments.) The laboratories break the work into simpler tasks that ensure student success. Hands-on computer work makes a student more confident and adventurous in the subject. Most laboratories have several exercises with multiple parts. Thus, to meet individual time requirements and needs, the instructor can assign one or all of these exercises. Data structure implementations, text program examples and data files, and laboratory files are available via West's home page on the World Wide Web. The instructor's disk contains these files and answers to laboratory exercises.
The professor can cover all or some of a variety of breadth sections. This material presents a broad range of topics from the discipline of computer science. For example, with the breadth material the student can study such topics as pattern matching in artificial intelligence, operating system job queues, a list processing language, compilers and parsing, and parallel processing. The Learning Features section below contains a complete list of the 17 breadth sections. These breadth sections enhance the subject material, help place topics in perspective, and give the students a preview of the richness of the discipline of computer science. Students like to see the relevance of the subject and what is ahead for them, and these sections give a good taste of the future.
The style of writing in the breadth material, laboratories, and text material is clear, direct, and readable. Students love examples, and there are numerous ones in the text. Concrete examples make abstract concepts come alive.
Numerous figures accompany the examples and explanations. These figures help today's visually oriented students to "see" what happens inside the computer as each instruction executes. A number of figures show the movement of data and the effects of operations in data structures. For example, Figure 5.9 of Section 5.2 follows each change in a stack through evaluation of a postfix expression. Boldface highlights these changes in the figures and emphasizes important segments of code. This visual orientation of the code and figures is important as the students study abstract ideas.
Figures and examples help to explain the material, but students learn by doing. Each section has a number of exercises that correlate directly to the material. Answers to problems with boxed numbers are in Appendix F. Some of the exercises, such as those related to searching and sorting, have the students perform the task by hand before coding it. This kind of drill makes these abstract concepts more concrete. The exercises are complete and thorough, and there is a good mix of easy and challenging questions. The text also includes questions from the Graduate Record Computer Science Examination. Among other features described below, the Instructor's Manual contains answers to the exercises. Code in the text, manual, anonymous FTP site, and disk has been computer tested.
Besides exercises, the chapters contain programming projects, which range in difficulty and topics. These projects provide an additional source of applications of the data structures. Several projects are from the Programming Contest sponsored by Fairleigh Dickinson University.
Along with projects and exercises, numerous features help the students concentrate on the important concepts. Each chapter begins with an introduction and list of goals. The closing material of each chapter also contains key terms and a summary. The list of key terms includes page numbers, which make this feature useful for reviewing. The chapter summary helps to focus the reader on the important points.
Appendices include a bridge from C to C++, random number generators, an ASCII table, text code on the World Wide Web, a glossary, and answers to selected exercises.
Learning Features
Breadth Material
The topics in the breadth sections mesh with the chapter's data structures material. The professor has the option of covering all, some, or none of these topics. As the following list reveals, the 17 breadth sections complement the chapters in which they occur:
1 Software Engineering
1.4 Responsibilities of the Computing Professional
3 Elementary Data Structures
3.2 Storage of Arrays in the Computer
3.7 Pattern Matching in Artificial Intelligence
5 Stacks
5.5 Backtracking in Artificial Intelligence
6 Queues
6.4 Operating System Job Queues
7 Lists
7.5 Numerical Computations Using Lists
7.6 A List Processing Language
8 Using Lists
8.2 Numerical Computation with Sparse Matrices
8.6 Computer Networks
9 Binary Trees
9.4 Compilers and Parsing
9.5 Decision and Game Trees in Artificial Intelligence
9.6 Huffman Codes
9.10 External Searching and B-Trees
10 Sorting
10.8 Parallel Processing
11 Tables
11.4 Symbol Tables
12 Graphs and Networks
12.4 An Application of Depth-First Search: The Maze
12.6 Finite-State Machines
Laboratories
Each chapter has a laboratory module with accompanying code available via West's home page on the World Wide Web. Some laboratories involve experimental methods. Others explore manipulation or implementation of a data structure. All reinforce the material in the text. For example, the laboratory in the binary trees chapter contains one exercise to increase understanding of tree traversals and another to perform experiments on search times for various trees. Several of the laboratories employ the team approach:
Chapter 1 Analysis and design phases of the software life cycle
Chapter 6 Development of a program to simulate the line at a movie theater
Chapter 7 Development of a program to manipulate a list of grocery items
The Instructor's Manual suggests variations for those instructors who prefer individual to team assignments. Moreover, the instructor can use a laboratory in a scheduled, supervised environment or can assign parts of the laboratory for independent exploration by the student.
Examples
The organized approach to examples¾particularly with accompanying diagrams¾aids understanding of the subject.
Numerous Diagrams
Diagrams help students visualize the actions of operations and algorithms. Boldface emphasizes changes. For example, figures in Section 7.1 on List Abstraction and Applications help to illuminate this topic.
Section Exercises
Exercises are at the end of each section, not just at the end of the chapter. These include short answer problems, diagrams of the execution of segments, design and coding of functions that use a data structure, alternative implementations of an ADT, applications, and questions from the Graduate Record Computer Science Examination. The text contains more than 1000 exercises in all.
Answers to Exercises
Answers in Appendix F to some exercises (those with boxed numbers) allow students to check their work for immediate reinforcement. The Instructor's Manual contains answers to the remaining exercises. Answers involving code have been computer tested.
Programming Projects
On the average, there are thirteen programming projects per chapter. These are major assignments for the students to design, code, and test applications. By completing such a project, the student enhances his or her understanding of the data structures and abilities in software development. For ease of assignment, projects are listed at the ends of the sections.
Historical Anecdotes
Such anecdotes add interest to the text and make history more real. Moreover, the historical anecdotes often present material that a computer science major should know about the history of the discipline.
Chapter Introductions
An introduction at the beginning of each chapter gives an overview of the material in the chapter.
Chapter Goals
A list of study goals for the chapter follows the introduction.
Key Terms
Using the Key Terms section, students can test their knowledge of the important terms in the chapter. Because page numbers accompany the terms, students can readily check their answers or consult the text to refresh their memories.
Summary
The Summary presents a concise overview of the chapter material.
Supplementary Materials
Instructor's Manual and Disk
An Instructor's Manual contains solutions to text exercises, answers to one project per chapter, and additional test problems with answers. The accompanying disk has laboratory exercises, their answers, data structure implementations, and program examples from the text. Code in the Instructor's Manual and on the disk has been computer tested.
Test Bank
A Test Bank on disk contains test questions and answers for each chapter.
Text Code
Laboratory programs and data files, data structure implementations, and program examples from the text will be available via West's home page on the World Wide Web.
Overhead Transparency Masters
A set of transparency masters of key figures and algorithms is available to the professor who adopts the text.
Testing of Code
The source code appearing in this textbook, Instructor's Manual, the accompanying disk, and the World Wide Web was prepared and tested on a Macintosh 840 AV using Symantec C++ compiler, Version 7.0, and on a Mitsuba 80386 MS-DOS PC using Borland's C++ compiler, Versions 3.1 and 4.0. Every effort was made to provide the student with portable example programs and code fragments. In all cases, the target execution environment is MS-DOS. These programs are not designed to be compiled or executed as MS Windows applications. Although these programs can be compiled using a Windows-based compiler or integrated development environment¾such as Borland's C++ for Windows¾the student must correctly specify the target environment and run the resulting programs within an MS-DOS shell.