Introduction to Computer Science With C++

by Lambert, Kenneth A.; Naps, Thomas L.; Nance, Douglas W.

• ISBN13: 9780534368937
• ISBN10: 053436893X
• Edition: 2nd
• Format: Paperback
• Copyright: 2000-02-11
• Publisher: Course Technology

Summary

This is the only C++ textbook on the market that provides complete coverage of CS1 and CS2 in one volume. This book focuses on traditional CS1 and CS2 topics, while developing object-oriented programs. The software life cycle is emphasized throughout, with numerous case studies of varying size and complexity. The first third of the book covers program design with calculation, functions, control structures, and the use of objects. Beginning in Chapter 8, the next third of the book covers user-defined classes, inheritance, polymorphism, arrays, complexity analysis, and the development of abstract data types (called ADTs). The last third of the book covers several standard ADTs - table, list, stack, queue, tree, and graph - including discussions of different implementations, applications, and the complexity of each ADT. Additional topics include recursion and advance sorting and searching techniques.

Table of Contents

Computer Science, Computer Architecture, and Computer Languages	1	(14)
Computer Science: A Preview	2	(3)
Computer Science as Computer Literacy	2	(1)
Computer Science as Mathematics and Logic	2	(1)
Computer Science as Science	3	(1)
Computer Science as Engineering	3	(1)
Computer Science as Communication	4	(1)
Computer Science as an Interdisciplinary Field	4	(1)
A Note of Interest: Ethics and Computer Science	5	(1)
Computer Architecture	5	(7)
Modern Computers	5	(3)
Computer Hardware	8	(4)
Computer Software	12	(1)
Computer Languages	12	(3)
A Note of Interest: Why Learn C++?	13	(1)
Summary	14	(1)
Problem-Solving Fundamentals: Data Types and Output	15	(33)
Program Development: Top-Down Design	16	(10)
Six Steps to Good Programming Habits	16	(1)
Developing Algorithms	17	(4)
Software Engineering	21	(1)
Software System Life Cycle	22	(1)
A Note of Interest: Software Verification	23	(1)
Object-Oriented Design	24	(2)
Writing Programs	26	(8)
The Vocabulary of C++	26	(1)
Case Sensitivity	27	(1)
Case Conventions	27	(1)
Reserved Words	27	(1)
Library Identifiers	27	(1)
Syntax	28	(1)
Identifiers	28	(1)
A Note of Interest: Program Libraries	29	(1)
Basic Program Components	29	(3)
Writing Code in C++	32	(1)
Program Comments	33	(1)
Data Types and Output	34	(14)
Type int	34	(1)
Type double	34	(1)
Type char	35	(1)
Strings	36	(1)
Output	37	(1)
Formatting Integers	38	(1)
Formatting Real Numbers	39	(1)
Formatting Strings	40	(1)
Test Programs	41	(3)
Summary	44	(2)
Programming Problems and Projects	46	(2)
More Problem-Solving Fundamentals: Calculation and Input	48	(46)
Arithmetic in C++	48	(6)
Basic Operations for Integers	48	(1)
Order of Operations for Integers	49	(1)
Using Modulus and Division	50	(1)
Representation of Integers	50	(1)
Basic Operations for Real Numbers	51	(1)
Representation of Real Numbers	52	(1)
Mixed-Mode Expressions	53	(1)
Using Variables	54	(9)
Memory Locations	54	(1)
Assignment Statements	55	(1)
A Note of Interest: Herman Hollerith	56	(1)
Expressions	57	(1)
Compound Assignment	58	(1)
Output	58	(2)
Software Engineering	60	(3)
Input	63	(6)
Input Statements	63	(1)
Interactive Input	64	(2)
Reading Numeric Data	66	(1)
Character Sets	66	(1)
Reading Character Data	66	(1)
Debugging Output Statements	67	(2)
String Variables	69	(7)
String Input with >>	69	(1)
String Input with getline	69	(2)
A Note of Interest: Computer Ethics: Copyright, Intellectual Property, and Digital Information	71	(1)
Memory for String Variables	72	(1)
The Empty String	73	(1)
String Concatenation	74	(1)
Compound Assignment with Strings	74	(2)
Using Constants	76	(2)
Rationale for Uses	76	(1)
Software Engineering	77	(1)
Library Constants	77	(1)
A Note of Interest: Defined Constants and Space Shuttle Computing	78	(1)
Formatting Constants	78	(1)
Library Functions	78	(5)
Using Functions	79	(1)
Member Functions	80	(1)
Random Numbers	81	(2)
Type Compatibility and Type Conversion	83	(11)
The Character Set Once Again	83	(2)
Type Casts	85	(2)
Communication and Style Tips	87	(1)
Case Study: Computing the Cost of Pizza	87	(3)
Summary	90	(1)
Programming Problems and Projects	91	(3)
Subprograms: Functions for Problem Solving	94	(59)
Program Design	94	(1)
Modularity	94	(1)
Structured Programming and Design	95	(1)
User-Defined Functions	95	(12)
Need for User-Defined Functions	96	(1)
Function Declarations	96	(1)
A Note of Interest: Structured Programming	97	(1)
Declaring Functions in a Program	98	(1)
Implementing Functions in a Program	98	(1)
Function Headings	99	(1)
Data and Executable Statements in a Function Implementation	100	(2)
Use in a Program	102	(1)
Using Stubs	102	(1)
Using Drivers	103	(1)
Functions Without Returned Values (void functions)	104	(1)
Functions Without Parameters	104	(1)
Functions with Strings	105	(2)
Parameters	107	(7)
Value Parameters	107	(2)
Reference Parameters	109	(3)
A Note of Interest: The History of Parameter Passing	112	(1)
Constant Reference Parameters	113	(1)
Functions as Subprograms	114	(7)
Using Subprograms	115	(1)
Cohesive Subprograms	115	(1)
Functional Abstraction	116	(1)
Information Hiding	116	(1)
Interface and Documentation	116	(1)
A Note of Interest: Computer Ethics: Hacking and Other Intrusions	117	(1)
Software Engineering	117	(4)
Scope of Identifiers	121	(12)
Global and Local Identifiers	121	(3)
Using Global Identifiers	124	(1)
Side Effects and Parameters	124	(3)
Name of Identifiers	127	(1)
Multiple Functions	128	(1)
Communication and Style Tips	129	(2)
A Note of Interest:	131	(2)
John Backus
Programmer-Defined Libraries	133	(20)
An Example Library Header File	133	(1)
An Example Library Implementation File	134	(1)
Example Use of a Programmer-Defined Library	135	(1)
Case Study: Subsidized Parking	136	(4)
Running, Testing, and Debugging Hints	140	(1)
Summary	141	(3)
Programming Problems and Projects	144	(9)
Selection Statements	153	(72)
Boolean Expressions	153	(11)
Defining Boolean Constants and a Boolean Data Type	154	(1)
Relational Operators and Simple Boolean Expressions	155	(2)
Comparing Strings	157	(1)
Confusing = and ==	158	(1)
Boolean Functions	159	(1)
Logical Operators and Compound Boolean Expressions	159	(2)
Short-Circuit Evaluation of Boolean Expressions	161	(1)
A Note of Interest: George Boole	162	(2)
if Statements	164	(9)
Compound Statements	166	(1)
Using Compound Statements	167	(1)
Confusing == and = Again	167	(1)
if Statements with Functions	167	(6)
if...else Statements	173	(6)
Form and Syntax	173	(1)
Using Compound Statements	174	(1)
Robust Programs	175	(1)
A Note of Interest: Artificial Intelligence	176	(1)
Guarding Against Overflow	177	(2)
Nested and Extended if Statements	179	(16)
Multiway Selection	179	(4)
Form and Syntax	183	(7)
Communication and Style Tips	190	(1)
Program Testing	191	(4)
switch Statements	195	(9)
Form and Syntax	195	(2)
Communication and Style Tips	197	(2)
A Note of Interest: A Software Glitch	199	(1)
Use in Problems	199	(1)
Equivalent of Extended if Statements	200	(4)
Assertions	204	(21)
Case Study: The Gas-N-Clean Service Station	206	(6)
Running, Testing, and Debugging Hints	212	(2)
Summary	214	(2)
Programming Problems and Projects	216	(9)
Repetition Statements	225	(63)
Classifying Loops	225	(1)
Pretest and Posttest Loops	225	(1)
Fixed Repetition Versus Variable Condition Loops	226	(1)
for Loops	226	(11)
The Increment and Decrement Operators	227	(1)
Accumulators	228	(1)
Scope of a Loop Control Variable	229	(1)
for Loops That Count Down	230	(1)
Loops That Count by Factors Other than 1	231	(1)
Writing Style for Loops	231	(2)
for Loops with Strings	233	(1)
A Note of Interest	234	(3)
Charles Babbage
while Loops	237	(7)
Sentinel Values	240	(1)
Writing Style	240	(1)
Using Counters	240	(1)
Compound Conditions	241	(2)
A Note of Interest: Ada Augusta Byron	243	(1)
do...while Loops	244	(6)
Compound Conditions	247	(1)
Choosing the Correct Loop	247	(1)
Data Validation	248	(2)
Loop Verification	250	(4)
Preconditions and Postconditions with Loops	250	(1)
Invariant and Variant Assertions	251	(3)
Nested Loops	254	(10)
Flow of Control	254	(3)
Communication and Style Tips	257	(2)
Writing Style	259	(1)
Statement Execution in Nested Loops	259	(3)
A Note of Interest: A Digital Matter of Life and Death	262	(2)
Repetition and Selection	264	(24)
Selection Within Repetition (Loops)	264	(1)
Repetition (Loops) Within Selection	264	(3)
Case Study 6.1: Prime Numbers	267	(7)
Case Study 6.2: A Sentence Analyzer	274	(3)
Running, Debugging, and Testing Hints	277	(1)
Summary	277	(2)
Programming Problems and Projects	279	(9)
Files	288	(29)
Streams and Stream Processing	288	(9)
The Standard Input and Output Streams	289	(1)
File Streams	289	(1)
Output File Streams	290	(1)
Detecting Errors Opening and Closing Files	291	(1)
Using Output File Streams	291	(1)
Loops with Output File Streams	292	(1)
Input File Streams	293	(1)
Using Input File Streams	293	(2)
Loops with Input File Streams	295	(2)
Using Functions with Files	297	(7)
Files and Strings	299	(2)
Buffered File Input	301	(3)
A Note of Interest: Computer Ethics: Viruses	304	(1)
Character Input and Output	304	(13)
Character Output with put	304	(1)
Character Input with get	305	(1)
Detecting the End of File at the Character Level	305	(3)
A Note of Interest: Digital Video Disks	308	(1)
Case Study: Analyzing a File of Sentences	309	(5)
Running, Debugging, and Testing Hints	314	(1)
Summary	314	(1)
Programming Problems and Projects	315	(2)
Building Structured Data: Structs and Classes	317	(48)
The Struct Data Type	317	(9)
Basic Idea and Notation	317	(4)
Using Structs with Functions	321	(2)
Data Abstraction and Abstract Data Types	323	(3)
Introduction to User-Defined Classes	326	(12)
Abstract Data Types and Data Security	326	(1)
Data Encapsulation, Classes, and Objects	326	(1)
User Requirements for a Bank Account Class	327	(2)
Specifying the Operations	329	(1)
Declaring a Bank Account Class	330	(2)
Using a Class and Using a Struct	332	(1)
Implementing a Bank Account Class	333	(1)
Creating Instances of a Bank Account Class with Constructors	333	(1)
Default Constructors	333	(1)
Constructors for Specifying Initial Values	334	(1)
Copy Constructors	334	(1)
Accessors and Modifiers	335	(1)
The Assignment Operator, Polymorphism, and Overloading	335	(2)
Using a Class with Functions	337	(1)
Object-Oriented Programming and Software Maintenance	338	(2)
The Problem of Software Maintenance	339	(1)
Reuse of Software	339	(1)
The Client/Server Relationship	339	(1)
Inheritance	340	(1)
Polymorphism and Overloading	340	(1)
A Rational Number Case	340	(10)
User Requirements	340	(1)
A Note of Interest: The Origins of the Object-Oriented Philosophy	341	(1)
Specifying the Operations	342	(2)
Declaring the Class	344	(1)
Implementing the Class	345	(3)
Mixed-Mode Operations	348	(2)
A Note of Interest: Pure and Hybrid Object-Oriented Languages	350	(1)
Derived Classes and Inheritance	350	(15)
Inheritance and Protected Members	355	(1)
Communication and Style Tips	356	(1)
Case Study: An ATM Machine	357	(4)
Running, Debugging, and Testing Hints	361	(1)
Summary	361	(1)
Suggestions for Further Reading	362	(1)
Programming Problems and Activities	362	(3)
Arrays	365	(72)
Arrays	365	(9)
Basic Idea and Notation	365	(1)
Declaring an Array	366	(2)
Other Element Types	368	(1)
Assignment Statements	369	(1)
Arithmetic	370	(1)
Reading and Writing	371	(1)
Out-of-Range Array References	371	(1)
A Note of Interest: Why Computer Scientists Number Things from 0 to N-10	372	(2)
Using Arrays	374	(7)
Loops for Input and Output	374	(1)
Loops for Assigning	375	(2)
Processing with Loops	377	(4)
Array Parameters and Functions	381	(4)
Sorting and Searching an Array	385	(5)
Sorting an Array	385	(3)
Searching an Array	388	(2)
Two-Dimensional Arrays	390	(10)
Basic Idea and Notation	390	(3)
Reading and Writing	393	(3)
Manipulating Components	396	(1)
Use with Functions	397	(2)
Communication and Style Tips	399	(1)
Safe Arrays: Vectors	400	(11)
User Requirements	401	(2)
Specifying the Operations for Vectors	403	(1)
Declaring the Vector Class	404	(1)
Class Templates	405	(1)
Pointers and Dynamic Memory	406	(1)
Constructing Vectors	406	(1)
The Destructor for Vectors	407	(1)
Copy Constructor and Assignment	408	(1)
Indexing	409	(1)
Including Libraries of Class Templates	410	(1)
Strings	411	(10)
User Requirements	411	(1)
Specifying the Operations for Strings	412	(2)
Declaring the String Class	414	(1)
Constructing Strings	415	(1)
Conversion to a C-Style String	416	(1)
Substrings	416	(2)
Assignment	418	(1)
Concatenation	418	(1)
Compound Assignment	419	(1)
Input and Output	419	(1)
String Comparisons	420	(1)
Safe Arrays: Matrices	421	(16)
User Requirements	421	(1)
Specifying the Operations for Matrices	422	(2)
Declaring the Matrix Class	424	(1)
Implementing the Matrix Class	425	(1)
Case Study: Word Frequencies	426	(3)
Summary	429	(2)
Programming Problems and Projects	431	(6)
Algorithm Analysis: Space and Time Considerations	437	(53)
Designing Programs: A Look Back and a Look Ahead	437	(1)
Simple Sorting Algorithms	438	(12)
Bubble Sort	439	(3)
Selection Sort Revisited	442	(3)
Insertion Sort	445	(5)
Which Sort Is Best? A Big-O Analysis	450	(12)
Big-O Analysis of Bubble Sort	456	(1)
A Note of Interest: Artificial Intelligence and the Complexity of Algorithms	457	(1)
Big-O Analysis of Insertion Sort	458	(1)
Big-O Analysis of Selection Sort	459	(3)
The Time/Space Trade-off: Pointer Sort and Radix Sort	462	(8)
Bubble Sort Implementation with Pointers	462	(3)
A Note of Interest: Virtual Memory and Program Performance	465	(1)
Radix Sort	466	(4)
Simple Search Algorithms	470	(20)
Sequential Search Algorithm	471	(1)
Binary Search Algorithm	472	(3)
Key-to-Address Transformations	475	(3)
Case Study: Empirically Measuring the Efficiency of an Algorithm	478	(6)
Running, Debugging, and Testing Hints	484	(1)
Summary	484	(1)
Programming Problems and Projects	485	(5)
Data Abstraction and Object-Oriented Software Engineering	490	(74)
The Ordered Collection Abstract Data Type	491	(1)
Motivation for the Ordered Collection	491	(1)
Defining the Ordered Collection ADT	491	(3)
Formally Specifying the Operations for Ordered Collections	494	(2)
Declaring the Ordered Collection Class in C++	496	(1)
Implementing the Operations for an Ordered Collection	497	(2)
Evaluating the Implementation	499
Sorted Collection	000	(507)
Abstract Data Type	501	(1)
User Requirements for a Sorted Collection	501	(2)
Formally Specifying the Operations for Sorted Collections	503	(1)
Declaring the Sorted Collection Class in C++	504	(2)
Implementing the Sorted Collection Class	506	(1)
The One-Key Table Abstract Data Type	507	(11)
Formally Specifying the Operations for One-Key Tables	508	(1)
A C++ Interface for the One-Key Table ADT	509	(2)
A Note of Interest: Association Lists and Dictionaries	511	(2)
Implementations of the One-Key Table ADT	513	(5)
The Two-Key Table Abstract Data Type	518	(8)
A Class Template for the Two-Key Table ADT	519	(1)
A Two-Dimensional Array Implementation	520	(3)
Using One-Key Tables to Implement Two-Key Tables	523	(2)
Comparing the Two Implementations	525	(1)
Revisiting the Analysis Phase of the Software Engineering Life Cycle	526	(5)
Revisiting the Design Phase of the Software Engineering Life Cycle	531	(7)
A Note of Interest: Object-Oriented Design and Productivity in Software Development	533	(5)
Revisiting the Implementation and Testing Phases of the Software Engineering Life Cycle	538	(26)
White Box/Black Box Testing	541	(2)
A Note of Interest: Software Reliability and Defense Systems	543	(1)
Case Study: Finishing the Registrar's System	544	(6)
A Note of Interest: The (Lack of) Responsibility of Software Developers	550	(8)
Running, Debugging, and Testing Hints	558	(1)
Summary	559	(1)
Programming Problems and Projects	560	(4)
Linked Lists	564	(48)
The Need for Linked Lists	564	(3)
The File Input Problem	565	(1)
The Data Movement Problem	566	(1)
The Concept of a Linked List	567	(11)
The Characteristics and Logical Structure of a Linked List	567	(2)
Linked List Operations	569	(5)
Removing Data from the List	574	(1)
Using a Linked List to Solve Problems	574	(4)
Defining the Linked List ADT As a C++ Class	578	(8)
Defining a Pointer to a Node	580	(1)
Declaring the getNodeFunction	580	(1)
Creating a Linked List	580	(1)
The Copy Constructor for a Linked List	581	(1)
The Destructor for Linked Lists	582	(1)
The first and next Operations	582	(1)
Accessing and Modifying Data in a Node	583	(1)
Testing for the End of the List	583	(1)
Testing for an Empty List	583	(1)
Inserting Data into a Linked List	584	(1)
Implementing getNode	584	(1)
Removing Data from a Linked List	585	(1)
Pointers and the Management of Computer Memory	586	(11)
Addresses and Values of Simple Variables	586	(1)
Addresses and Values of Array Variables	586	(1)
Addresses and Values of Pointer Variables	587	(2)
A Note of Interest: Garbage Collection	589	(1)
Pointers and Dynamic Allocation of Memory	589	(4)
The Costs of Using Linked Lists	593	(1)
The Benefits of Using Linked Lists	593	(4)
Using a Linked List to Implement a One-Key Table	597	(15)
Redefining the One-Key Table Class	597	(1)
Reimplementing the One-Key Table Class	598	(3)
A Note of Interest: Storage of Disk Files and Computer Security	601	(1)
Case Study: Optimizing Radix Sort with Linked Lists	601	(3)
Running, Debugging, and Testing Hints	604	(1)
Summary	605	(2)
Programming Problems and Projects	607	(5)
Stacks and Queues	612	(60)
The Stack Abstract Data Type and Its Implementation	612	(10)
Stacks and Function Calls	614	(1)
C++ Interface for the Stack Abstract Data Type	615	(1)
Array Implementation of a Stack	616	(3)
Linked List Implementation of a Stack	619	(3)
An Application of Stacks: Parsing and Evaluating Arithmetic Expressions	622	(11)
Infix, Postfix, and Prefix Notation	623	(1)
A Note of Interest: Logic Programming and Bactracking	624	(1)
Converting Infix Expressions to Postfix	625	(5)
Evaluating Postfix Expressions	630	(3)
The Queue Abstract Data Type: Its Use and Implementations	633	(39)
Application of a Queue in Computer Simulation	634	(2)
C++ Interface for the Queue ADT	636	(3)
Array Implementation of a Queue	639	(4)
Circular Implementation of a Queue	643	(2)
Linked List Implementation of a Queue	645	(1)
A Note of Interest: Computer Simulations: Blessing or Curse?	646	(2)
A Note of Interest: Operating Systems and Scheduling Resource Use in a Time-Sharing Environment	648	(1)
Priority Queues	649	(2)
Case Study: Integral Evaluation System	651	(2)
Modular Structure for the Integral Evaluation System	653	(2)
Data Structures for the Integral Evaluation System	655	(9)
Running, Debugging, and Testing Hints	664	(1)
Summary	665	(1)
Programming Problems and Projects	666	(6)
Recursion	672	(60)
Controlling Simple Iteration with Recursion	673	(11)
Linked Lists as Recursive Data Structures	674	(3)
How Is Recursion Implemented?	677	(7)
Weaving More Complex Recursive Patterns	684	(19)
Towers of Hanoi Problem	685	(1)
A Note of Interest: Recursion Need Not Be Expensive	686	(7)
Efficiency Analysis of the Recursive Towers of Hanoi Algorithm	693	(3)
Recursive Implementation of the Binary Search Algorithm	696	(2)
Efficiency Analysis of the Recursive Binary Search	698	(1)
Recursive Computation of "N Choose K"	699	(4)
Recursion, Trial-and-Error Backtracking, and Generalized Nested Loops	703	(1)
The Permutation Problem	703	(12)
A Note of Interest: Fractal Geometry and Recursive Patterns	709	(2)
A Note of Interest: Recursion, LISP, and the Practicality of Artificial Intelligence	711	(1)
The Eight Queens Problem	711	(4)
Recursive Descent Parsing	715	(17)
A Note of Interest: Language Definition and Natural Languages	717	(3)
Case Study: Implementing a Recursive Descent Parser from a Context-Free Grammar	720	(5)
Running, Debugging, and Testing Hints	725	(1)
Summary	726	(1)
Programming Problems and Projects	727	(5)
Binary Trees, General Trees, and Graphs	732	(78)
General Trees and Binary Trees and Abstract Data Types	734	(10)
C++ Interface for the Binary Trees ADT	739	(5)
Linked Implementation of a Binary Tree	744	(15)
Implementing Traversal Operations on a Binary Tree	750	(1)
Preorder Traversal of a Binary Tree	750	(2)
Inorder Traversal of a Binary Tree	752	(1)
Postorder Traversal of a Binary Tree	753	(1)
Copying and Destroying a Binary Tree	753	(6)
Binary Search Tree Implementation of a One-Key Table	759	(11)
Adding Nodes to the Binary Search Tree Implementation of a One-Key Table	759	(2)
Searching for Data in a Binary Search Tree Implementation of a One-Key Table	761	(1)
A Note of Interest: Hypertext	762	(1)
Deleting Data in a Binary Search Tree Implementation of a One-Key Table	762	(4)
Efficiency Considerations for Binary Search Tree Implementation of a One-Key Table	766	(4)
Linear Implementation of the Binary Tree Abstract Data Type	770	(5)
Efficiency Considerations of the Linear Representation	771	(1)
Using the Linear Implementation for a Heap	772	(2)
Efficiency Analysis of Insert for Linear Representation of Heap	774	(1)
General Trees	775	(5)
Traversals of a General Tree Implemented via a Binary Tree	777	(1)
A Note of Interest: Computer Security and Tree-Structured File Systems	778	(2)
Graphs and Networks: Bidirectional Trees	780	(30)
C++ Interface for the Graph ADT	785	(1)
The Network ADT	785	(1)
Implementation of Graphs and Networks	786	(1)
A Note of Interest: Computer Network---Their Use and Potential Abuse	787	(1)
Examples of Graph Algorithms: Depth-First and Breadth-First Traversals	787	(4)
A Note of Interest: The Traveling Salesperson and NP-complete Problems	791	(1)
Example of a Network Algorithm: Finding Shortest Paths	792	(4)
Case Study: A Concordance Problem	796	(3)
Running, Debugging, and Testing Hints	799	(1)
Summary	799	(2)
Pgogramming Problems and Projects	801	(9)
More Powerful Sorting Methods	810	(29)
The Shell Sort Algorithm	811	(4)
Efficiency of the Shell Sort	813	(2)
The Quick Sort Algorithm	815	(5)
Efficiency of the Quick Sort	818	(1)
A Note of Interest: Privacy Issues Kill Microsoft Registration System	819	(1)
The Heap Sort Algorithm	820	(6)
Efficiency of the Heap Sort	825	(1)
The Merge Sort Algorithm	826	(13)
Efficiency of the Merge Sort	828	(2)
A Note of Interest: Public-Key Cryptography	830	(1)
Case Study: Efficiently Sorting a Linked List	831	(2)
Running, Debugging, and Testing Hints	833	(1)
Summary	834	(1)
Programming Problems and Projects	835	(4)
More Powerful Search Methods	839	(50)
Density-Dependent Search Techniques	840	(17)
The Construction of Hashing Functions	840	(4)
Collision Processing	844	(1)
Linear Collision Processing	844	(3)
Quadratic and Rehashing Methods of Collision Processing	847	(2)
Linked Method of Collision Processing	849	(3)
A Note of Interest: The CYC Project: Capturing Human Knowledge in Electronic Dictionaries	852	(1)
Bucket Hashing	852	(5)
Two Abstract Data Types Revisited	857	(3)
The One-Key Table ADT Implemented by Hashing	857	(1)
The Two-Key Table ADT Implemented by Hashing	858	(2)
Indexed Search Techniques (Optional)	860	(29)
Indexed Sequential Search Technique	860	(4)
A Note of Interest: Data Integrity, Concurrent Updates, and Deadlock	864	(1)
Binary Search Tree Indexing	865	(1)
B-Tree Indexing	865	(4)
Trie Indexing	869	(6)
Case Study: Profiling Hash Table Operations	875	(9)
Running, Debugging, and Testing Hints	884	(1)
Summary	884	(2)
Programming Problems and Projects	886	(3)
Appendices	889	(50)
A Reserved Words	890	(1)
B Some Useful Library Functions	891	(2)
C Syntax Diagrams	893	(12)
D The ASCII Character Set	905	(1)
E The AP Classes	906	(33)
Glossary	939	(14)
Answers to Selected Exercises	953	(34)
Index	987