ADTs, Data Structures, and Problem Solving with C++ (2nd Edition) (Alan R. Apt Books)
Editorial Reviews
Book Description
The first edition of this text grew out of the author's experience teaching an introductory data structures course (commonly referred to as CS2) for nearly two decades. It has served as a sequel to the widely used C++: An Introduction to Computing by Joel Adams and Larry Nyhoff, which grew out of their many years of teaching a first programming course (CS1) in C++. But computer science curricula change as do teaching pedagogy and methodology. In keeping with these changes, the introductory C++ text underwent revisions and has recently appeared in a third edition. The content of the second course in computing also has changed, with the broadening of the traditional study of data structures to a study of abstract data types (ADTs) being one of the major trends. Consequently, there is an increased emphasis on ADTs in this new edition and a name change thus seemed appropriate: ADTs, Data Structures, and Problem Solving with C++. And as one might expect, there is a corresponding increased emphasis on object-oriented design. In addition, the author's pedagogy has been honed over many years of successful teaching. Reflecting this, the presentation in this new edition has been improved by reordering some topics, rewriting several sections, and adding new material. Many suggestions also came from those who diligently and thoroughly reviewed the manuscript and its several revisions. Their constructive comments and positive evaluations were very encouraging and much appreciated. If you used the first edition and liked it, I trust you will like this new edition even more. Scan the overview and list of new features that appear later in this preface to see what some of the improvements are. Those of you who haven't used or who stopped using the first edition and are looking at this edition as one of several candidates for your course will, I hope, give it serious consideration. I have tried to preserve the best features of the first edition and made changes based on feedback from many CS2 teachers and users of the previous edition. Approach. As an illustration of the approach that has worked well in my classes, take a look at Chapter 7 on stacks. Some examples of real-world phenomena that are best modeled by a LIFO structure lead to abstracting from these examples the common features, yielding a stack ADT. But ADTs must be implemented with data structures provided in some language, and so we build a stack class. (Incidentally, while we are doing this in class, my students are working on building a queue class in their lab period.) Once this new Stack type has been created and tested, we use it to solve one or more of the original problems and usually at least one new application. I also believe in starting with a simple implementation e.g., using a static C-style array and get a working version. Then, emphasizing the need to preserve the public interface of an ADT, we refine it e.g., use a dynamic array so the user can specify the stack's capacity; then use a linked list so an a priori capacity specification is not needed; and finally, convert it to a template so the ADT can be used with arbitrary type elements. This spiral/successive-refinement approach demonstrates clearly the "abstract" part of an ADT that it is independent of the implementation. I also cover many of the containers provided in the C++ Standard Template Library (STL), because several of them such as vector are very useful and powerful, and it does not make sense to reinvent the wheel by building our own versions. Others, however, such as STL's stacks and queues, are adapters of other containers and waste a lot of the horsepower of these inner containers. For these it makes sense to build our own "lean and mean" implementations, using lower-level data structures such as arrays and linked lists. It also provides practice for students with building customized container types for problems for which none of the standard containers is really suitable. How to Use this Book. There is considerable flexibility in the kind of course that can be taught from this text. In particular, many of the topics can be covered in an order different from that used in the text. The diagram on the next page shows the major dependencies of the various chapters. An arrow running from one box to another indicates a significant dependence of the material in the second box on that in the first; for example, the material in Chapter 9 draws on the material in both Chapters 7 and 8. A dashed arrow indicates that the material in the first box may have been covered in a first course and might be omitted or assigned for review. Boxes not connected are, for the most part, independent of each other (for example, Chapters 7 and 8). To Students (and Other Users of this Text) You probably don't read prefaces of most textbooks unless your instructor assigns them and then perhaps only if you will be quizzed on it. For this text, however, you should at least read the section "Overview of the Text," because it is intended to provide an orientation to what the book is about, what its major themes are, and how they fit together. And you should also look through the Table of Contents for this same reason. The topics covered in this text are typical of those in a course that follows a first course in programming. The aim of these two courses together is to provide you with a solid introduction to computing. You develop the skills to write substantial programs for solving non-trivial problems but are also introduced to important concepts and techniques in computing. These two courses should provide you with a solid base for using the computer as a problem-solving tool in whatever areas of study you pursue. If you do more coursework in computer science, it is important that you work hard at mastering the material of this second course, because the topics covered are fundamental to several upper-level courses. In fact, at many colleges and universities, this course is a prerequisite for intermediate and advanced courses in computer science. This text assumes that you have had an introduction to programming, preferably using C++ or Java. Appendix C ( Basic C++ ) reviews the basic features of C++ that are typically covered in a first programming course, and Appendix D ( Other C++ Features ) covers some features that are more advanced. Students in my classes have found these two appendixes to be handy references when they need to look up something about the C++ language. If your first course was in Java, you should study Appendix E ( From Java to C++ ), which provides a comparison of the main features of the two languages. It has been used successfully in my classes to get students with a background in Java up to speed with the basic features of C++ in the first couple of weeks. As you read through the text, you should by all means use the Quick Quizzes to check your understanding of some of the main ideas from the reading. The answers to these can be found in Appendix F. These self-test quizzes are usually followed by sets of exercises, some of which your instructor may assign for homework. You are encouraged to try some of these on your own, even if it isn't required, because it will increase your mastery of the material. The same is true of the programming problems at the end of each chapter. All of the C++ code in the program examples of this text can be downloaded from the author's website for the book: http://cs.calvin.edu/books/c++/ds. So if you see a particular function in an example that you can use in a program or class library you are writing, feel free to download and use it-unless your instructor forbids it, of course! Hopefully, you will enjoy reading and learning from the text. Several hundreds of my students have used earlier versions of this text with very few complaints. But they do enjoy finding errors and informing me about them! I hope that you too will report any that you run across; they are there, in spite of long hours of "debugging" the manuscript before it goes into print. I can't offer you bonus points on your course grade for finding them, but I will recognize your contribution to the improvement of the book by adding your name to the list of other error detectors on the book's website. Overview of the Text As the title suggests, there are three main themes in this text: Abstract data types (ADTs) Data structures Problem solving Abstract data types consist of collections of data elements together with basic operations on the data. Nearly every chapter of this text deals with some aspect of ADTs defining an ADT such as a list, stack, or queue; studying some application of it; implementing the ADT or studying its implementation in some library; looking at ways to improve the implementation. Classes play a key role in implementing ADTs because they make it possible to encapsulate the data and the operations so that objects not only store data but also have built-in operations. This is one of the key properties of object-oriented programming and is emphasized from the beginning. Data structures provided in C++ (such as arrays) or that can be built in C++ (e.g., linked lists) play important roles in providing structures to store the data elements of an ADT. These key data structures along with the up-to-date and powerful containers from the Standard Template Library (STL) are studied for this purpose. The third theme is problem solving. Chapter 1 describes some of the software engineering methodologies used to develop a solution to a problem, and the text emphasizes the use of object-oriented design (OOD) in the design phase. This is a natural continuation of the object-centered design (OCD) approach used in C++: An Introduction to Computing and which is similar to that used in many other introductory programming texts. The text has many examples, including several case studies, that show the roles that ADTs play in problem solving. Implementing the operations of an ADT involves designing algorithms to carry out the operations. This means that the study of algorithms must also play a significant role in a...
From the Back Cover
Abstract data types (ADT's) and data structures are key elements in unlocking the power of object-oriented programming. Designed for CS2 course; this popular book thoroughly covers ADTs (Abstract Data Types), data structures, and their use in problem solving. The text guides the student through the development of ADTs such as stacks, queues, and binary trees, the use of key data structures such as arrays, classes and linked lists to implement ADTs, and problem solving using Object-Oriented Design (OOD) methodologies. Algorithms required to design arid implement ADTs in C++ are given thorough treatment along with a solid introduction to the Standard Template Library (STL). C++ topics such as recursion, inheritance, and polymorphism are introduced and some C-style topics relative to data structures are also provided. Using examples, case studies and exercises from various areas of computer science, author Larry Nyhoff offers the student a solid foundation for further studies in CS while providing concrete tools for unlocking the power of C++. New to the Second Edition
ADTs, Data Structures, and Problem Solving with C++ (2nd Edition) (Alan R. Apt Books),Larry R. Nyhoff,Prentice Hall,0131409093,C++ (Computer program language,C++ (Computer program language),Computer Bks - General Information,Computer Books: General,Computer Science,Computers,Data Structures,Data structures (Computer scie,Data structures (Computer science)
Hot Books:
Recommended Books