Add NoteAdd Note

HighlightHighlight

CopyCopy

ZoomZoom

PrintPrint

HelpHelp

PreviousPrevious

NextNext

« Back to My CourseSmart

ADTs, Data Structures, and Problem Solving with C++, Second Edition

by Larry R. Nyhoff - Calvin College, Department of Computer Science, Grand Rapids, MI

eTextbook digital rental: 180 days

Our Price: $60.99

Regular Price: $153.00

You save: $92.01

Available Online Only

Add to Cart

Free Trial

Access sample pages from your bookshelf. Take notes, highlight, print and more!

Start Free Trial

Tabs for Contents, notes, highlights

Contents
Notes
Highlights

Detailed Table of Contents

Hide Contents, Notes, and Highlights

Search TermsShow Hide

« Back to eTextbook

Copyright, ii
Preface, iii
1. Software Development, 1
1.1. Problem Analysis and Specification, 4
1.2. Design, 6
1.3. Coding, 17
1.4. Testing, Execution, and Debugging, 30
1.5. Maintenance, 38
Summary, 41
2. Introduction to Abstract Data Types, 45
2.1. A First Look at ADTs and Implementations, 46
2.2. C++’s Simple Data Types, 46
2.3. Programmer-Defined Data Types, 59
2.4. Pointers, 63
Summary, 75
3. Data Structures and Abstract Data Types, 81
3.1. Data Structures, Abstract Data Types, and Implementations, 82
3.2. Static Arrays, 85
3.3. Multidimensional Arrays (optional), 97
3.4. Dynamic Arrays, 107
3.5. C-Style Structs (optional), 123
3.6. Procedural Programming, 128
Summary, 135
4. More about OOP and ADTs—Classes, 143
4.1. Procedural vs. Object-Oriented Programming, 144
4.2. Classes, 145
4.3. Example: A First Version of a User-Defined Time Class, 150
4.4. Class Constructors, 158
4.5. Other Class Operations, 165
Summary, 188
5. Standard C++ Input/Output and String Classes, 193
5.1. The C++ Standard I/O Classes, 194
5.2. The C++ String Types, 211
5.3. Case Study: Text Editing, 230
5.4. Introduction to Pattern Matching (optional), 240
5.5. Introduction to Data Encryption (optional), 243
Summary, 247
6. Lists, 253
6.1. List as an ADT, 254
6.2. An Array-Based Implementation of Lists, 257
6.3. An Array-Based Implementation of Lists with Dynamic Allocation, 269
6.4. Introduction to Linked Lists, 287
6.5. A Pointer-Based Implementation of Linked Lists in C++, 295
6.6. An Array-Based Implementation of Linked Lists (optional), 303
Summary, 309
7. Stacks, 315
7.1. Introduction to Stacks, 316
7.3. Linked Stacks, 353
7.4. Use of Stacks in Function Calls, 366
7.5. Case Study: Postfix (RPN) Notation, 371
Summary, 386
8. Queues, 389
8.1. Introduction to Queues, 389
8.2. Designing and Building a Queue Class—Array-Based, 400
8.3. Linked Queues, 412
8.4. Application of Queues: Buffers and Scheduling, 426
8.5. Case Study: Information Center Simulation, 429
Summary, 441
9. ADT Implementations: Templates and Standard Containers, 445
9.1. Introduction: The Evolution of Reusability and Genericity, 446
9.2. Function Genericity—Overloading and Templates, 448
9.3. Class Genericity—Templates, 457
9.4. The vector Container, 475
9.5. Case Study: Counting Computer Logins, 494
9.6. Multidimensional vectors (Optional), 499
9.7. Other Standard Containers—deque, stack, and queue, 503
9.8. Bitsets and Valarrays (optional), 511
Summary, 516
10. ADT Implementation: Recursion, Algorithm Analysis, and Standard Algorithms, 521
10.1. Recursion, 522
10.2. Examples of Recursion: Towers of Hanoi; Parsing, 538
10.3. Implementing Recursion, 548
10.4. Algorithm Efficiency, 551
10.5. Standard Algorithms in C++, 564
10.6. Proving Algorithms Correct (optional), 573
Summary, 579
11. More Linking Up with Linked Lists, 585
11.1. Some Variants of Singly-Linked Lists, 586
11.2. Linked Implementation of Sparse Polynomials, 593
11.3. Doubly-Linked Lists and the Standard C++ list, 602
11.4. Case Study: Large-Integer Arithmetic, 621
11.5. Other Multiply-Linked Lists, 631
Summary, 639
12. Searching: Binary Trees and Hash Tables, 645
12.1. Review of Linear Search and Binary Search, 646
12.2. Introduction to Binary Trees, 651
12.3. Binary Trees as Recursive Data Structures, 660
12.4. Binary Search Trees, 667
12.5. Case Study: Validating Computer Logins, 698
12.6. Threaded Binary Search Trees (Optional), 702
12.7. Hash Tables, 707
Summary, 715
13. Sorting, 721
13.1. Some O(n2) Sorting Schemes, 722
13.2. Heaps, Heapsort, and Priority Queues, 735
13.3. Quicksort, 753
13.4. Mergesort, 762
13.5. Radix Sort, 770
Summary, 774
14. OOP and ADTs, 779
14.1. A Brief History and Overview of OOP and ADTs, 780
14.2. Inheritance and Object-Oriented Design, 784
14.3. Building Derived Classes, 794
14.4. Case Study: Payroll, 801
14.5. Polymorphism, Virtual Functions, and ADTs, 810
14.6. Case Study: A Heterogeneous Data Structure, 823
Summary, 828
15. Trees, 831
15.1. Case Study: Huffman Codes, 832
15.2. Tree Balancing: AVL Trees, 839
15.3. 2-3-4 Trees, Red–Black Trees, B-Trees, and Other Trees, 855
15.4. Associative Containers in STL—maps (optional), 874
Summary, 880
16. Graphs and Digraphs, 883
16.1. Directed Graphs, 883
16.2. Searching and Traversing Digraphs, 892
16.3. Graphs, 911
Summary, 926
A. ASCII Character Set, A1
B. Number Systems, B1
Exercises, B3
C. Basic C++, C1
C.1. C++ Program Structure, C1
C.2. Compiler Directives, C2
C.3. Standard Libraries, C2
C.4. Comments, C5
C.5. Identifiers and Keywords, C6
C.6. Fundamental Data Types, C9
C.7. Literals, C9
C.8. Declarations, C10
C.9. Operators and Expressions, C10
C.10. Control Structures, C16
C.11. Functions, C22
C.12. Lifetimes, Scopes, and Namespaces, C28
C.13. Files, C30
D. Other C++ Features, D1
D.1. Stream Operations, D1
D.2. String Operations, D5
D.3. Exceptions, D14
D.4. More About Function Templates, D17
E. From Java to C++, E1
E.1. Program Structure, E1
E.2. using and Compiler Directives, E1
E.3. Input and Output (§C.9, §C.13, & §D.1), E2
E.4. Data Types, E5
E.5. Variables and Constants, E6
E.6. Functions, E7
E.7. Operator Overloading, E9
E.8. Things the Same in Both C++ and Java, E10
E.9. More Differences Between C++ and Java, E11
F. Answers to Quick Quizzes, F1
Quick Quiz 1.5, F1
Quick Quiz 2.2, F1
Quick Quiz 2.3, F2
Quick Quiz 2.4, F2
Quick Quiz 3.2, F2
Quick Quiz 3.3, F3
Quick Quiz 3.4, F3
Quick Quiz 3.5, F3
Quick Quiz 4.1, F3
Quick Quiz 4.2, F3
Quick Quiz 4.5, F4
Quick Quiz 5.1, F4
Quick Quiz 5.2, F4
Quick Quiz 6.3, F5
Quick Quiz 6.4, F5
Quick Quiz 7.2, F5
Quick Quiz 7.4, F6
Quick Quiz 7.5, F6
Quick Quiz 8.2, F6
Quick Quiz 8.3, F6
Quick Quiz 8.4, F7
Quick Quiz 9.3, F7
Quick Quiz 9.4, F7
Quick Quiz 9.7, F8
Quick Quiz 10.1, F8
Quick Quiz 10.4, F8
Quick Quiz 10.5, F9
Quick Quiz 11.1, F9
Quick Quiz 12.2, F9
Quick Quiz 12.3, F9
Quick Quiz 12.4, F9
Quick Quiz 12.6, F11
Quick Quiz 12.7, F11
Quick Quiz 13.1, F12
Quick Quiz 13.2, F12
Quick Quiz 13.3, F13
Quick Quiz 13.4, F13
Quick Quiz 14.1, F13
Quick Quiz 14.2, F13
Quick Quiz 14.5, F14
Quick Quiz 15.2, F14
Quick Quiz 15.3, F14
Quick Quiz 15.4, F16
Quick Quiz 16.1, F16
Quick Quiz 16.2, F17
Quick Quiz 16.3, F17
Index, I-1-1

Search Results

« Back to eTextbook


PAGE	Description

128	...