Problem Solving, Data Abstraction and Design using C++

Problem Solving, Data Abstraction,and Design Using C++

Frank L. Friedman, Elliot B. Koffman

Addison Wesley

1994

0-201-52649-2

This is actually a school book that i was forced to go through. It takes the reader from knowing nothing at all, to using double linked lists and pointers. I really liked looking at the Case Studies and following how they actually implemented the new code. This not only trains the reader in how the new code is used, but most importantly, how to apply the new ideas to solve a problem! Having the reader go through examples and doing the chapter review is an excellent technique to have them acquire the differen't aspects of C++ programming. Another big plus for this book is its section on Common Programming Errors that follows almost every chapter. It's also good because after the reader is finished with this book, they will be ready to handle some advanced topics in C++. Very complete.

1	Introduction to Computers and Programming

	1.1	Electronic Computers Then/Now					2
	1.2	Components of a Computer					7
	1.3	Problem-Solving, Abstraction and Program Engineering		12
	1.4	Programming Languages						14
	1.5	Processing a High-Level Language Program			18
	1.6	Using the Computer						20
		Chapter Review							26

2	Program Design

	2.1	The Software Development Method					30
		CASE STUDY: Converting Units of Measurement			34
	2.2	Overview of C++							37
	2.3	Declarations of variables and constants				41
	2.4	Executable Statements						44
	2.5	Recapitulation: The General Form of a C++ Program		52
	2.6	Abstraction: Data Types and Expressions				56
		CASE STUDY: Finding the Value of a Coin Collection		59
	2.7	Interactive Mode, Batch Mode, and Data Files			71
	2.8	Common programming Errors					74
		Chapter Review							80

3	Top Down Design

	3.1	Problem Solving and Program Development				86
		CASE STUDY: Finding the area and circumference of a Circle	89
	3.2	Subproblems and Independent Modules				93
		CASE STUDY: Drawing Simple Figures				93
	3.3	Functions Without Arguments					96
	3.4	Functions with Input Arguments and Return Values		108
	3.5	How we use functions						111
	3.6	Functions as Program Building Blocks; C++ Libraries		124
	3.7	Some Comments on the Software Engineering Process		132
	3.8	Common Programming Errors
		Chapter Review							136

4	Selection Structues: if AND switch Statemtents

	4.1	Control Structures						142
	4.2	Logical Expressions						143
	4.3	Introduction to the if Control Statement			151
	4.4	if Statements with COmpound Alternatives			155
	4.5	Decision Steps in Algorythms					158
		CASE STUDY: Payroll Problem					158
	4.6	Formatted Output: Introduction to Manipulators and Flags	165
	4.7	Checking Correctness of an Algorithm				169
		CASE STUDY: Finding the Alphabetically First Letter		169
	4.8	More Problem Solving Strategies					173
		CASE STUDY: Computing Overtime Pay				174
		CASE STUDY:  Computing Insurance Dividends			177
	4.9	Nested if Statements and Multiple Alternative Decisions		182
	4.10	The switch Control Statement					189
	4.11	Common Programming Errors					194
		Chapter Review							195

5	Repetition: while, for, and do-while statements	

	5.1	Repetition in programs: Thw while statement			204
	5.2	Accumulating a Sum or Product in a Loop				209
	5.3	Counting Loops and Conditional Loops				215
	5.4	Loop Design							218
	5.5	The for statement						227
	5.6	More for statement Examples					233
	5.7	The do while Statement						237
	5.8	Review of while, for and do while Loops				240
	5.9	Nested Loops							242
	5.10	Debugging and Testing Porgrams					246
	5.11	Common Programming Errors					249
		Chapter Review							251

6	Program Design and Functions revisited

	6.1	Functions in the Design Process					260
	6.2	Using Function Return Values for Decision and Loop Control	265
	6.3	Output Arguments						269
		CASE STUDY: Sorting Three Numbers				277
	6.4	Syntax Rules for Functions with Argument Lists			283
	6.5	Stepwise Design with Functions					287
		CASE STUDY: General Sum and Average Problem			287
	6.6	Solving a More Complex Problem					302
		CASE STUDY: Checking Account Balance Problem			303
	6.7	More Aspects of Software Engineering				316
	6.8	Debugging and Testing a Program System				318
	6.9	Common Programming Errors					320
		Chapter Review							321

7	Simple data types

	7.1	Contants Revisited						330
	7.2	Internal Representations of Integer, Floating Point,
		and Character Data Types					332
	7.3	Logical Expressions						346
	7.4	Character Variables and Fucntions				348
	7.5	Enumeration Types						353
	7.6	Common Programming Errors					362
		Chapter Review							365

8	Formattting and Files

	8.1	The Standard Input/Output Streams				372
	8.2	Streams and External Files					381
	8.3	Accessing and Using External Files				382
	8.4	Using External File Functions : An example			391
		CASE STUDY: Preparing a Payroll File				391
	8.5	Putting It All Together						398
		CASE STUDY: Preparing Semester Grade Reports			398
	8.6	Stream I/O Manipulator Functions and Flags			422
	8.7	Common Programming Errors 					424
		Chapter Review							426

9	Arrays and structures 

	9.1	The Array Data type						434
	9.2	Selecting Array Elements for Processing				439
	9.3	Arrays as Arugments						444
	9.4	Reading Part of an Array					452
	9.5	Searching and Sorting Arrays					456
	9.6	Character Strings						463
	9.7 	The truct Data Type						473
	9.8	Structs as Operands and Arguments				476
	9.9	Heirarchical Structs						480
	9.10	Unions								483
	9.11	Common Programming Errors					487
		Chapter Review							489

10	Introduction to software engineering 

	10.1	The Software Challenge						498
	10.2	The Software Life Cyle						500
		CASE STUDY: Telephone Directory Program				504
	10.3	Procedural Abstraction Revisted					507
	10.4	Data Abstraction and Abstract Data Types: Program Objects	511
	10.5	Analysis of Algorithm Efficiency: Big O Notation		516
	10.6	Software Testing						519
	10.7	Formal Methods of Program Verification				522
	10.8	Professional Ethics and Responsibilities			530
		Chapter Review							531

11	Data Abstraction C++: the C++ Class

	11.1	The C++ Class							538
	11.2	Classes Vesus Structs						547
	11.3	The Absract Data Type Day					548
	11.4	Automatic Initilization: Class Constructors			553
	11.5	Problem Analysis and Design Using Classes			555
		CASE STUDY: Areas and Perimeter of Different
		Figures Revisted						555
	11.6	A Complex Number Class						566
	11.7	Defining and Using Functions and Classes:
		Summary of Rules and Restrictions				573
	11.8	Common Programming Errors					576
		Chapter Review							578

12	Software engineering : Bulding absract data types

	12.1	The Indexed Collection as an Abstract Data Type			587
	12.2	Class Extensions : An Introduction to Inheritance		596
		CASE STUDY: Home Budget Problem					596
	12.3	Extending Reuse: An Introduction to Templates			611
	12.4	Using Old Components to Solve New Problems			618
		CASE STUDY: Cryptogram Generator Problem			625
	12.5	Common Programming Errors					637
		Chapter Review							640

13	The String Data Type

	13.1	String Functions in the String.h Library			650
	13.2	An Illustration of Character String Processing			663
		CASE STUDY: Printing a Form Letter				663
	13.3	Variable Length Strings						676
	13.4	Common Programming Errors					685
		Chapter Review							688

14	Arrays with Structured Elements

	14.1	Arrays of Arrays: Multidemensional Arrays			698
	14.2	Creating Arrays of Arrays					700
	14.3	Arrays of Structs						703
	14.4	Arrays of Class Elements					706
	14.5	Abstraction and Generalization: Triangle and Polygon Classes	708
	14.6	Modeling the Triangle: Illustrating Alternative Approaches	709
	14.7	Design and Use of Abstract Data Types				727
		CASE STUDY: Assigning Final Grades for a Semester		727
	14.8	Common Programming Errors					746
		Chapter Review							747

15	Recursion 

	15.1	The Nature of Recursion						756
	15.2	Tracing Recursive Functions					761
	15.3	Recursive Mathematical Functions				767
	15.4	Recursive Functions with Array Arguments			773
		CASE STUDY: Recursive Selection Sort				773
	15.5	Problem Solving with Recursion					776
		CASE STUDY: Towers of Hanoi Problem				776
	15.6	Picture Processing with Recursion				780
		CASE STUDY: Counting Cells in a Blob				780
	15.7	Common Programming Errors					784
		Chapter Review							785

16	Dynamic Data Structures 

	16.1	Review of Pointers and the new Operator				792
	16.2	Manipulating the Heap						799
	16.3	Linked Lists							801
	16.4	The Stack as an Abstract Data Type				809
		CASE SUTDY: Evaluating the Postfix Expressions			813
	16.5	Implementing a Stack Using an Array				820
	16.6	Linked List Reprsesentation of a Stack				824
	16.7	The Queue Abstract Data Type					830
	16.8	Queue Application 						833
		CASE STUDY: Maintaining a Queue of passengers			833
	16.9	Implementing a Queue Using an Array				841
	16.10	Linked List Representation of a Queue				846
	16.11	Common Programming Errors					850
		Chapter Review							852

Appendixes

	A 	Character Sets
	B 	Reserved Words and Special Characters
	C	Selected C++ Library Facilities
	D	Operators
	E	A brief Introduction to Inheritance and Polymorphism

Answers
Index