Objects, Abstraction, Data Structures and Design

Using C++

Häftad, Engelska, 2005

2 625 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt över 249 kr.

Beskrivning

Koffman and Wolfgang introduce data structures in the context of C++ programming. They embed the design and implementation of data structures into the practice of sound software design principles that are introduced early and reinforced by 20 case studies. Data structures are introduced in the C++ STL format whenever possible. Each new data structure is introduced by describing its interface in the STL. Next, one or two simpler applications are discussed then the data structure is implemented following the interface previously introduced. Finally, additional advanced applications are covered in the case studies, and the cases use the STL. In the implementation of each data structure, the authors encourage students to perform a thorough analysis of the design approach and expected performance before actually undertaking detailed design and implementation. Students gain an understanding of why different data structures are needed, the applications they are suited for, and the advantages and disadvantages of their possible implementations.Case studies follow a five-step process (problem specification, analysis, design, implementation, and testing) that has been adapted to object-oriented programming. Students are encouraged to think critically about the five-step process and use it in their problem solutions. Several problems have extensive discussions of testing and include methods that automate the testing process. Some cases are revisited in later chapters and new solutions are provided that use different data structures.The text assumes a first course in programming and is designed for Data Structures or the second course in programming, especially those courses that include coverage of OO design and algorithms. A C++ primer is provided for students who have taken a course in another programming language or for those who need a review in C++. Finally, more advanced coverage of C++ is found in an appendix.Course Hierarchy:Course is the second course in the CS curriculumRequired of CS majorsCourse names include Data Structures and Data Structures & Algorithms

Produktinformation

Utgivningsdatum:2005-11-11
Mått:191 x 234 x 33 mm
Vikt:1 247 g
Format:Häftad
Språk:Engelska
Antal sidor:832
Förlag:John Wiley & Sons Inc
ISBN:9780471467557

Utforska kategorier

Programspråk inom Data och IT

Mer om författaren

Elliot Koffman is currently Professor of Computer and Information Sciences at Temple University. He received his Ph.D. at Case Institute of Technology. He has authored and co-authored numerous textbooks and other publications. Paul Wolfgang is currently Professor of Computer and Information Sciences at Temple University. He received his B.S. in electrical engineering at University of Pennsylvania.

Innehållsförteckning

Preface iiiChapter P A C++ Primer 1P.1 The C++ Environment 2P.2 Preprocessor Directives and Macros 7P.3 C++ Control Statements 12P.4 Primitive Data Types and Class Types 16P.5 Objects, Pointers, and References 23P.6 Functions 29P.7 Arrays and C Strings 33P.8 The string Class 38P.9 Input/Output Using Streams 44Chapter Review, Exercises, and Programming Projects 59Chapter 1 Introduction to Software Design 631.1 The Software Life Cycle 641.2 Using Abstraction to Manage Complexity 731.3 Defining C++ Classes 751.4 Abstract Data Types, Interfaces, and Pre- and Postconditions 981.5 Requirements Analysis, Use Cases, and Sequence Diagrams 1021.6 Design of an Array-Based Phone Directory 1081.7 Implementing and Testing the Array-Based Phone Directory 1141.8 Completing the Phone Directory Application 121Chapter Review, Exercises, and Programming Projects 125Chapter 2 Program Correctness and Efficiency 1292.1 Program Defects and “Bugs” 1302.2 Exceptions 1382.3 Testing Programs 1482.4 Debugging a Program 1602.5 Reasoning about Programs: Assertions and Loop Invariants 1662.6 Efficiency of Algorithms 170Chapter Review, Exercises, and Programming Projects 179Chapter 3 Inheritance and Class Hierarchies 1853.1 Introduction to Inheritance and Class Hierarchies 1863.2 Member Function Overriding, Member Function Overloading, and Polymorphism 1933.3 Abstract Classes, Assignment, and Casting in a Hierarchy 2023.4 Multiple Inheritance 2103.5 Namespaces and Visibility 2133.6 A Shape Class Hierarchy 220Chapter Review, Exercises, and Programming Projects 225Chapter 4 Sequential Containers 2314.1 Template Classes and the Vector 2324.2 Applications of vector 2384.3 Implementation of a vector Class 2404.4 The Copy Constructor, Assignment Operator, and Destructor 2474.5 Single-Linked Lists and Double-Linked Lists 2524.6 The list Class and the Iterator 2644.7 Implementation of a Double-Linked List Class 2714.8 Application of the list Class 2854.9 Standard Library Containers 2924.10 Standard Library Algorithms and Function Objects 297Chapter Review, Exercises, and Programming Projects 307Chapter 5 Stacks 3115.1 The Stack Abstract Data Type 3125.2 Stack Applications 3155.3 Implementing a Stack 3255.4 Additional Stack Applications 332Chapter Review, Exercises, and Programming Projects 351Chapter 6 Queues and Deques 3576.1 The Queue Abstract Data Type 3586.2 Maintaining a Queue of Customers 3626.3 Implementing the Queue ADT 3656.4 The Deque 3766.5 Simulating Waiting Lines Using Queues 380Chapter Review, Exercises, and Programming Projects 398Chapter 7 Recursion 4037.1 Recursive Thinking 4047.2 Recursive Definitions of Mathematical Formulas 4127.3 Recursive Search 4207.4 Problem Solving with Recursion 4267.5 Backtracking 435Chapter Review, Exercises, and Programming Projects 440Chapter 8 Trees 4458.1 Tree Terminology and Applications 4478.2 Tree Traversals 4548.3 Implementing a Binary_Tree Class 4578.4 Binary Search Trees 4668.5 Heaps and Priority Queues 4848.6 Huffman Trees 496Chapter Review, Exercises, and Programming Projects 505Chapter 9 Sets and Maps 5119.1 Associative Container Requirements 5129.2 Maps and Multimaps 5219.3 Hash Tables 5309.4 Implementing the Hash Table 5429.5 Implementation Considerations for the hash_map 5559.6 Additional Applications of Maps 558Chapter Review, Exercises, and Programming Projects 564Chapter 10 Sorting 56910.1 Using C++ Sorting Functions 57010.2 Selection Sort 57210.3 Bubble Sort 57710.4 Insertion Sort 58110.5 Comparison of Quadratic Sorts 58610.6 Shell Sort: A Better Insertion Sort 58810.7 Merge Sort 59210.8 Heapsort 59910.9 Quicksort 60410.10 Testing the Sort Algorithms 61410.11 The Dutch National Flag Problem (Optional Topic) 616Chapter Review, Exercises, and Programming Projects 620Chapter 11 Self-Balancing Search Trees 62311.1 Tree Balance and Rotation 62411.2 AVL Trees 62811.3 Red-Black Trees 64311.4 2-3 Trees 65611.5 2-3-4 and B-Trees 663Chapter Review, Exercises, and Programming Projects 681Chapter 12 Graphs 69112.1 Graph Terminology 69212.2 The Graph ADT and Edge Class 69712.3 Implementing the Graph ADT 70112.4 Traversals of Graphs 71512.5 Applications of Graph Traversals 72712.6 Algorithms Using Weighted Graphs 734Chapter Review, Exercises, and Programming Projects 743Appendix A Advanced C++ Topics 755A.1 Source Character Set, Trigraphs, Digraphs, and Alternate Keywords 755A.2 The Allocator 756A.3 Traits 757A.4 Virtual Base Classes 759A.5 Smart Pointers 764Appendix B Overview of UML 769B.1 The Class Diagram 770B.2 Sequence Diagrams 776Appendix C The CppUnit Test Framework 779Glossary 783Index 795