Holt Software Books [Graphical Version] | [Printer Friendly Version]
![[Cover of Book]](img/data_structures_turing.gif) |
Data Structures: An Object Oriented Approach
|
| Title: |
Data Structures: An Object Oriented Approach |
| Authors: |
D.T. Barnard, R.C. Holt and J.N.P. Hume |
| ISBN: |
0-921598-24-6 |
| Publisher: |
Holt Software Associates Inc. |
| Binding: |
Softcover |
| Pages: |
548 pgs |
| Price: |
Bookstores & Schools: $30.00 Retail: $37.50 |
| Ordering Information: |
For bookstores and schools, click here for
ordering information.
For individuals click
here for ordering information. |
| Program Examples: |
Available [Click here for
information on obtaining program examples found in Holt Software
publications.] |
| Solutions Manual: |
Not Available |
This is a textbook for a second course in computer science emphasizing
data structures, abstract data types and algorithms. While it uses
object oriented programming as a theme, this is only one theme among
the many that are covered. Other themes include software-engineering,
recursion and efficiency. The language used by this book is Object
Oriented Turing. The book includes chapters on Basic Programming
Constructs, Algorithms, Correctness and Running Time, Data Abstraction,
Stacks, Queues, Priority Queues, Object Oriented Programming, Recursion,
Trees, Advanced Trees, Graphics and Sorting.
Preface to Data Structures: An Object Oriented Approach
This textbook, Data Structures: An Object-Oriented Approach, is
intended to be used in a second course in computer science emphasizing
data structures, abstract data types, and algorithms. While it uses
object-oriented programming as a theme, this is only one theme among
many that are covered. Other themes include software engineering, recursion,
and efficiency. The language used in this book is Object Oriented Turing,
which has an easy-to-learn syntax and is supported by student-friendly
programming environments.
Prerequisites
It is assumed that the student is knowledgeable about basic programming
material covered in a first course in computer science. Students should
already be familiar with:
- statements such as assignments, loops, and if statements,
- simple types including integers, reals, strings, and booleans,
- structured types including arrays, records, and unions, and
- procedures and functions.
Knowledge of pointers is not required; this material is covered in Chapter
2. The student who has taken a course using the Turing language should have
a sufficient introduction to language features. If the student is not
familiar with Turing, but has used another language such as Pascal or
C, he or she should learn the basic language constructs of Turing. These
constructs are covered in Chapter 2.
Overview
This book covers the material in standard curricula for second courses
in computer science. In particular, this book can be used in courses
described by the ACM's Curriculum '78 (revised in 1984) or Computing
Curriculum 1991. The listing of chapter titles outlines the arrangement
of material.
- Getting Started
- Basic Programming Constructs
- Algorithms: Correctness and Running Times
- Data Abstraction
- Stacks
- Queues
- Priority Queues and Dictionaries
- Object-Oriented Programming
- Recursion
- Trees
- Advanced Trees
- Graphs
- Sorting
Chapter 1 introduces recurring computer science themes and
software engineering. Software engineering concepts are emphasized
throughout the book. Chapter 2 is mostly review for those who have
already completed an introductory course using the Turing language.
Pointers, which are commonly not taught in a first course, are introduced
in this chapter.
Chapter 3 introduces fundamental material on algorithms, as well
as big O notation. The algorithms covered are: order n and log n searches
(serial and binary searches), and order n2 and n log n sorts (bubble and
merge sorts).
With Chapter 4, the book begins its emphasis on data structures
and data abstraction. Chapter 4 provides a carefully developed abstract
data type (an address book), which is implemented as a separate module
unit. This chapter teaches the student mechanisms and motivation for
information hiding.
The next three chapters (Chapters 5 through 7) use the ideas
developed in Chapter 4 to introduce standard data abstractions, such as
stacks and queues, along with data structures to represent them. With
most data abstractions, an extensive example of a typical usage is
developed. For example, an expression evaluator uses the stack, and
a bank simulation uses the queue. This approach is taken to ensure
that the student understands an abstraction and its usual implementations,
and also gains a good feel for the practical utility of the abstraction.
The examples developed in these chapters typically consist of a number of
separate units, some of which are re-usable modules implementing the
abstractions. These examples serve as case studies and allow further
emphasis of software engineering ideas.
Chapter 8 concentrates on object-oriented programming, or more
generally, the object-oriented paradigm. Classes and inheritance are
introduced, and their implications for software libraries, class
hierarchies, browsing, and software re-use are emphasized. The material
on classes and inheritance was deferred to this point in the book so that
the student could first appreciate the need for, and master the mechanisms
of, information hiding.
Chapter 9 gives standard examples of recursion and prepares the
student for the use of recursion in manipulating data structures such as
trees. Chapter 10 introduces trees, their common implementations, and
their common uses. Chapter 11 contains advanced material on trees.
Chapter 12 introduces graphs with their basic algorithms,
abstractions, and uses. Chapter 13 returns to the subject of
sorting, and surveys basic sorting methods. There is no separate chapter
on searching because basic searching methods are covered in various
chapters throughout the book.
Flexibility
Data Structures: An Object-Oriented Approach has been organized to
allow it to be used flexibly to meet the requirements of the instructor.
It is expected that the instructor may omit some chapters or parts of
chapters, and may insert additional material.
This book provides only an introduction to program correctness, so the
instructor may choose to add extra material on this subject. A good
insertion point for this material is just after Chapter 3, or just
after Chapter 9. Object Oriented Turing's assertion features
(preconditions, postconditions, and invariants), as well as its formal
semantics in terms of weakest preconditions, make this language particularly
suited for teaching correctness concepts.
This book covers linked lists chapter by chapter, as the need for using
the various kinds of linking arises. Chapter 2 and Chapters 4 through 7
introduce linked lists with this organization:
- 2. Basic Programming Constructs
Pointers used as links from nodes to nodes.
- 4. Data Abstraction
Linearly linked lists, used to implement an address book.
- 5. Stacks
Linearly linked lists, used to implement a stack.
- 6. Queues
Linearly linked lists, used to implement a queue.
Front and rear pointers for linked lists.
- 7. Priority Queues and Dictionaries
Linearly linked lists, used to implement a priority queue.
Circularly linked lists, used to implement a dictionary.
Doubly linked lists, used to implement a dictionary.
Sentinel nodes in a linked list.
Linearly linked lists, used to implement hashing buckets.
An instructor may prefer to present this material on linked lists as a unit.
A good insertion point for this unit would be just after chapter 2.
Alternatively, a summary unit on this material would fit well at the
end of Chapter 7.
Recursion is introduced as one of the basic programming constructs covered
in Chapter 2. Chapter 5 covers the relationship between recursion and stacks.
Chapter 9 concentrates on recursion. Chapters 10 and 11 make extensive use of
recursion as it relates to trees. Instructors who wish to emphasize recursion
may wish to introduce a unit on this subject. A good insertion point for this
unit would be just before or after Chapter 5.
D.T. Barnard
R.C. Holt
J.N.P. Hume
Table of Contents of Data Structures: An Object Oriented Approach
Preface xiii
Acknowledgments xx
Chapter 1 - Getting Started 1
1.1 Recurring Themes in Computer Science 2
1.2 A Guided Tour of this Book 5
1.3 Problems in Software Engineering 6
1.4 Programming in the Large 7
1.5 The Software Life Cycle 12
Iterative Model of Software Evolution 14
1.6 Documentation 14
1.7 Validation and Verification 16
1.8 Testing 18
1.9 Chapter Summary 19
Recurring Themes 19
Software Engineering 19
Programming in the Large 20
Software Life Cycle 20
Documentation 21
Validation and Verification 21
Testing 21
1.10 Exercises 21
Chapter 2 - Basic Programming Constructs 25
2.1 Simple Data Types 26
Numerical Types 27
String Type 27
Type Conversion 28
Boolean Type and Comparisons 28
Enumerated Type 29
2.2 Structured Data Types 30
Array Type 30
Record Type 31
Set Type 31
Union Type 33
2.3 Declarations 34
Variable Declarations 35
Constant Declarations 35
Type Declarations 36
2.4 Assignment Statements 36
2.5 Assertions and the Quit Statement 37
2.6 Standard Input and Output 38
Formatted Output 39
Input 40
2.7 Input and Output using Files 41
2.8 Control Constructs 43
Repetition Statements 43
Selection Statement 44
2.9 Subprograms 45
Parameters 46
Dynamic Parameters 46
Functions 47
Procedures 47
Recursive Subprograms 49
2.10 Pointers and Linked Lists 51
Declaring and Using Pointers 51
The Nil Pointer 52
Deallocation and the Heap 52
Pointers as Links 53
Dereferencing Pointers 54
Illegal Use of Pointers and Dangling Pointers 54
Heap Exhaustion 55
Linked Lists 56
A Simple Use of a Linked List 57
2.11 Chapter Summary 59
Types and Declarations 59
Assertions and the Quit Statement 60
Input and Output 60
Control Constructs and Subprograms 61
Pointers 61
2.12 Exercises 62
Chapter 3 - Algorithms: Correctness and Running Time 65
3.1 Specification using Pre and Postconditions 66
An Informal Specification 66
A Better Informal Specification 67
A Formal Specification 68
Tightening up the Formal Specification 69
Other Specifications for Searching 71
Observations about Specification 71
What is the Purpose of a Specification? 72
Non-Functional Specifications 73
3.2 Implementing a Sequential Search 73
Run-Time Enforcement of Pre and Postconditions 76
Using the Search Function in a Program 76
3.3 Mathematical Induction 79
Summing the Integers from 1 to n 79
A Proof Method: Mathematical Induction 80
3.4 Proving that a Subprogram is Correct 82
An Informal Proof 83
A Standard Form for Loops 84
A Four-Step Method for Proving a Loop Correct 86
Relationship to Mathematical Induction 87
Proving Loop Termination 87
Using the Method to Prove Sequential Search Correct 88
3.5 Binary Search 90
Binary Search Algorithm 90
Procedure for Binary Search 92
Proving Binary Search Procedure Correct 93
3.6 Specifying a Sort Procedure 96
3.7 Successive Refinement 97
Printing the List 99
3.8 Developing a Bubble Sort Procedure 100
Description of Bubble Sort Algorithm 100
Top Down Design of Bubble Sort 101
Improving Bubble Sort 104
3.9 Running Time for Algorithms 104
Running Time for Sequential Search 105
Running Time for Binary Search 107
Big O Notation 109
Running Time for Bubble Sort 110
Comparing Big O Classes for Searches and Sorts 112
Concentrating on Loops and Recursion 113
When do Constants Matter? 113
3.10 Chapter Summary 114
Program Specification 114
Mathematical Induction 115
Program Correctness 115
Successive Refinement 116
Searching and Sorting Algorithms 116
Running Time for Algorithms 116
3.11 Exercises 117
Chapter 4 - Data Abstraction 119
4.1 Abstract Data Types 120
4.2 Case Study: An Address Book as a Data Object 121
Using the AddressBook Data Object 123
Object Specification in a Module Stub 123
A Main Program that uses AddressBook 125
Sample Execution of Demonstration Program 128
4.3 Implementation of AddressBook using an Array 129
4.4 Implementation of AddressBook using a Linked List 133
4.5 Properties of Data Objects 139
Procedural Abstraction and Data Abstraction 139
Choosing Data Structures for Implementations 139
Running Time for the AddressBook Implementations 140
Re-Use of Data Objects 140
Persistent Objects 141
File Naming Conventions 141
Two Difficulties with Terminology 142
4.6 Chapter Summary 143
Abstract Data Types 143
Modules 143
Implementing an Object 143
Performance and Persistence 144
4.7 Exercises 144
Chapter 5 - Stacks 147
5.1 What is a Stack? 148
5.2 A Stack as an Abstract Data Type 149
5.3 Implementation of Stack Using an Array 150
5.4 A Main Program that Uses a Stack 153
5.5 Implementation of Stack Using a Linked List 154
5.6 Checking for Balanced Parentheses 157
5.7 Case Study: Using a Stack to Evaluate Expressions 161
The Shunting Algorithm 162
Two Examples of Using the Shunting Algorithm 162
Summary of the Actions of the Shunting Algorithm 165
Design of the Program 166
The Main Program 167
The Parser Module 168
The Scanner Module 173
The Evaluator Module 175
The Operator Stack and the Value Stack 178
The Globals Module 178
5.8 The Run Stack 179
5.9 Chapter Summary 182
The Stack ADT 182
The Stack as an ADT 182
Use of Stacks 183
Implementing Stacks 184
Software Engineering Concepts 184
5.10 Exercises 185
Chapter 6 - Queues 187
6.1 What is a Queue? 188
Queues in Operating Systems 189
6.2 Defining a Queue as an Abstract Data Type 189
6.3 Implementation of Queue using an Array 190
The Wrap-Around Implementation 191
Example using Implementation of Queue 194
6.4 Implementation of Queue using a Linked List 195
6.5 Case Study: Simulating a Queue in a Bank 199
Queuing Theory 200
Design of the Program 201
The Main Program 202
The Simulator Module 205
The NextCustomer Module 208
The CustomerQueue Module 210
The Servers Module 211
The Clock Module 214
The Customer Module 215
The Globals Module 216
The Tracer Module 217
6.6 Chapter Summary 219
The Queue ADT 219
Use of Queues 220
Software Engineering Concepts 220
6.7 Exercises 220
Chapter 7 - Priority Queues and Dictionaries 223
7.1 What is a Priority Queue? 224
7.2 Defining a Priority Queue as an Abstract Data Type 225
7.3 Implementation of PriorityQueue Using an Array 226
7.4 Implementation of PriorityQueue Using a Linked List 229
7.5 Example: Use of a Priority Queue to Schedule Repairs 233
7.6 What is a Dictionary? 236
7.7 Defining a Dictionary as an Abstract Data Type 237
7.8 Implementation of Dictionary Using a Linked List 242
Circularly Linked Lists 243
Using a Circularly Linked List 244
Using a Doubly Linked List 246
7.9 Implementation of Dictionary Using Hashing 251
Hashing 253
Frequency of Collisions 253
Finding an Alternative Space on Collision 254
Hashing into Buckets 254
7.10 Chapter Summary 259
An Abstract Data Type for Priority Queues 259
Implementations of the ADT PriorityQueue 259
An Abstract Data Type for Dictionaries 260
Implementations of the ADT Dictionary 260
Hashing 261
Linked Lists 261
7.11 Exercises 262
Chapter 8 - Object-Oriented Programming 263
8.1 What is a Class? 264
A Stack Class 265
Using the Stack Class 266
8.2 OOT's Graphics Procedures 269
8.3 The Face Class 272
8.4 What is Inheritance? 278
8.5 Using Inheritance to Add an Operation 279
8.6 Using Inheritance to Override an Operation 281
8.7 Using Inheritance to Change the Face 283
8.8 Polymorphism: Many Forms of Objects 286
8.9 A Polymorphic Stack 289
8.10 Class Hierarchies 290
8.11 AnyClass and Dynamic Genericity 292
8.12 The Object-Oriented Paradigm 297
Other Programming Paradigms 297
Adjusting to a New Paradigm 298
Concepts in Object Orientation 299
Non-Programming Uses of OO Concepts 300
Advantages of Object-Based Programming 300
Advantages of Classes and Inheritance 301
Matching the Program Structure to the Problem 301
Structural and Line-by-Line Programming 301
8.13 Chapter Summary 302
Objects 302
Classes 303
Graphics Procedures 304
Inheritance 304
Polymorphism 305
Class Hierarchies 306
Genericity 307
OO as a Paradigm 307
8.14 Exercises 308
Chapter 9 - Recursion 311
9.1 Merge Magic 312
9.2 The Nature of Recursion 316
9.3 Recursive Algorithms for Linked Lists 317
9.4 A Recursive Binary Search 322
Correctness of Function recBinarySearch 323
9.5 Iterative Versus Recursive Procedures 324
Improving a Recursive Solution 326
Towers of Hanoi 327
Mutual Recursion 329
9.6 Backtracking with Recursion 331
9.7 Chapter Summary 338
Recursive versus Iterative Solutions 338
Applications of Recursive Methods 339
9.8 Exercises 339
9.9 Project 340
Chapter 10 - Trees 341
10.1 What is a Tree? 342
10.2 Tree Concepts 345
10.3 Using Trees to Implement Abstract Data Types 348
10.4 Binary Search Trees 348
10.5 Implementation of Binary Search Tree using Pointers 353
10.6 Tree Operations 356
10.7 Iterative Implementations 365
10.8 What About Performance? 369
10.9 Chapter Summary 374
Trees 374
Binary Search Trees 375
10.10 Exercises 375
Chapter 11 - Advanced Trees 377
11.1 AVL Trees 378
11.2 What About Performance ? 393
11.3 Complexity 396
11.4 Tree Traversal 397
11.5 Threaded Trees 407
11.6 Chapter Summary 411
AVL Trees 411
Tree Traversal 411
11.7 Exercises 412
11.8 Projects 413
Chapter 12 - Graphs 415
12.1 What is a Graph? 416
Directed and Weighted Graphs 418
12.2 Defining a Graph as an Abstract Data Type 420
12.3 Implementation of Graph using an Adjacency Matrix 421
12.4 Implementation of Graph using Adjacency Lists 424
12.5 Graph Traversal 425
Depth-First Traversal 425
Breadth-First Traversal 426
Example Results of two Traversal Methods 427
12.6 Spanning Trees 428
Minimum Spanning Trees 430
Shortest Path Algorithm 430
12.7 Topological Ordering 430
Critical Path Problems 431
The Traveling Salesperson Problem and other Hard Problems 432
NP - Complete Graph Problems 433
12.8 Case Study: Hypertext 433
The Labelled Edge and Vertex Classes 434
The Graph Class 435
The HyperVertex Class 440
The HyperText Module 441
A Main Program to use Hypertext 445
The Hypertext Network 448
12.9 Chapter Summary 450
A Graph as an Abstract Data Type 450
Graph Traversal 451
Hypertext 452
12.10 Exercises 452
12.11 Project 454
Chapter 13 - Sorting 455
13.1 What is Sorting ? 456
Sequences of Values 457
13.2 Simple Exchange Sorts 460
Insertion Sort 461
Sort By Selection 467
Bubble Sort 470
13.3 Heap Sort 472
13.4 Quicksort 482
13.5 Merge Sort 488
13.6 Radix Sort 489
13.7 Sorting with Files 496
13.8 Chapter Summary 503
Exchange Sorts 503
Splitting and Recombining Sorts 504
Sorting with Files 505
13.9 Exercises 506
13.10 Projects 507
Appendices 509
Appendix A : Reserved Words 510
Appendix B : Predefined Subprograms by Module 511
Appendix C : Operators 526
Appendix D : Keyboard Codes for IBM PC 530
Appendix E : Character Set for IBM PC 532
INDEX 535
[ Holt Software Home ] *
[ Books (Graphical) ] *
[ Books (Text) ] *
[ Top of Page ] *
[ Feedback ]
