search for books and compare prices
Tables of Contents for Data Structures Using Java
Chapter/Section Title
Page #
Page Count
Preface
XV
CHAPTER 1 Introduction to Data Structures
1
67
1.1 Information and Meaning
1
23
Binary and Decimal Integers
3
1
Real Numbers
4
1
Character Strings
5
1
Hardware and Software
6
1
Concept of Implementation
7
1
Example
8
5
Abstract Data Types
13
3
Sequences as Value Definitions
16
2
ADT for Varying-Length Character Strings
18
1
Data Types in Java
19
1
Objects and Java
20
1
Value and Reference Semantics
21
1
Data Structures and Java
22
2
Exercises
24
1
1.2 Arrays, Strings, and Vectors in Java
24
20
The Array as an ADT
26
1
Using One-Dimensional Arrays
27
2
Implementing One-Dimensional Arrays
29
3
Arrays as Parameters
32
1
Two-Dimensional Arrays
32
3
Multidimensional Arrays
35
3
Character Strings in Java
38
2
Character String Operations
40
1
Vectors in Java
40
2
Exercises
42
2
1.3 Classes and Objects in Java
44
24
Constructors
46
1
Representing Other Data Structures
47
1
Rational Numbers
47
6
Using the class Rational
53
4
Allocation of Storage and Scope of Classes
57
7
Vectors in Java
64
2
Exercises
66
2
CHAPTER 2 The Stack
68
51
2.1 Definition and Examples
68
8
Primitive Operations
69
3
Example
72
3
The Stack as an Abstract Data Type
75
1
Exercises
75
1
2.2 Representing Stacks in Java
76
9
Implementing the pop Operation
79
2
Testing for Exceptional Conditions
81
1
Implementing the Push Operation
82
3
Exercises
85
1
2.3 Example: Infix, Postfix, and Prefix
85
16
Basic Definitions and Examples
85
3
Evaluating a Postfix Expression
88
1
Program to Evaluate a Postfix Expression
89
3
Limitations of the Program
92
1
Converting an Expression from Infix to Postfix
92
5
Program to Convert an Expression from Infix to Postfix
97
2
Exercises
99
2
2.4 Stack of Objects of Varying Types
101
18
Stacks in Java Using Vectors
104
2
Dealing with Heterogeneous Data
106
5
The Class Class and the java. lang. reflect Package
111
2
The Predefined Stack Class
113
4
Exercises
117
2
CHAPTER 3 Recursion
119
60
3.1 Recursive Definition and Processes
119
9
Factorial Function
119
3
Multiplication of Natural Numbers
122
1
Fibonacci Sequence
123
1
Binary Search
124
3
Properties of Recursive Definitions or Algorithms
127
1
Exercises
127
1
3.2 Recursion in Java
128
13
Factorial in Java
128
4
The Fibonacci Numbers in Java
132
2
The Binary Search in Java
134
1
Recursive Chains
135
1
Recursive Definition of Algebraic Expressions
136
3
Exercises
139
2
3.3 Writing Recursive Programs
141
14
The Towers of Hanoi Problem
143
5
Translation from Prefix to Postfix Using Recursion
148
4
Exercises
152
3
3.4 Simulating Recursion
155
22
Return from a Method
157
1
Implementing Recursive Methods
158
1
Simulation of Factorial
159
3
Improving the Simulated Routine
162
2
Eliminating gotos
164
5
Simulating the Towers of Hanoi
169
9
Exercises
175
2
3.5 Efficiency of Recursion
177
2
Exercises
178
1
CHAPTER 4 Queues and Lists
179
79
4.1 The Queue and Its Sequential Representation
179
11
The Queue as an Abstract Data Type
180
1
Java Implementation of Queues
181
5
Priority Queue
186
1
Array Implementation of a Priority Queue
187
2
Exercises
189
1
4.2 Linked Lists
190
16
Inserting and Removing Nodes from a List
192
4
Linked Implementation of Stacks
196
600
getnode and freenode Operations
796
Linked Implementation of Queues
198
1
The Linked List as a Data Structure
199
2
Examples of List Operations
201
2
List Implementation of Priority Queues
203
1
Header Nodes
204
1
Exercises
205
1
4.3 Lists in Java
206
15
Array Implementation of Lists
206
5
Limitations of the Array Implementation
211
1
Linked Lists Using Dynamic Variables
212
2
Queues as Lists in Java
214
2
Examples of List Operations in Java
216
3
Comparing the Dynamic and Array Implementations of Lists
219
1
Implementing Header Nodes
219
1
Exercises
220
1
4.4 An Example: Simulation Using Linked Lists
221
10
Simulation Process
222
1
Data Structures
223
3
Simulation Program
226
3
Exercises
229
2
4.5 Other List Structures
231
27
Circular Lists
231
1
Stack as a Circular List
232
1
Queue as a Circular List
233
1
Primitive Operations on Circular Lists
233
2
The Josephus Problem
235
6
Addition of Long Positive Integers Using Circular Lists
241
4
Doubly Linked Lists
245
3
Addition of Long Integers Using Doubly Linked Lists
248
7
Exercises
255
3
CHAPTER 5 Trees
258
83
5.1 Binary Trees
258
12
Operations on Binary Trees
263
1
Applications of Binary Trees
263
6
Exercises
269
1
5.2 Binary Tree Representations
270
25
Node Representation of Binary Trees
270
4
Internal and External Nodes
274
1
Implicit Array Representation of Binary Trees
275
6
Choosing a Binary Tree Representation
281
1
Binary Tree Traversals in Java
281
3
Threaded Binary Trees
284
4
Traversal Using a father Field
288
3
Heterogeneous Binary Trees
291
1
Exercises
292
3
5.3 An Example: The Huffman Algorithm
295
10
The Huffman Algorithm
298
1
Java Application
299
5
Exercises
304
1
5.4 Representing Lists as Binary Trees
305
13
Finding the kill Element
306
3
Deleting an Element
309
3
Implementing Tree-Represented Lists in Java
312
3
Constructing a Tree-Represented List
315
1
The Josephus Problem Revisited
316
2
Exercises
318
1
5.5 Trees and their Applications
318
15
Java Representations of Trees
320
5
"Tree Traversals
325
1
General Expressions as Trees
325
3
Evaluating an Expression Tree
328
2
Constructing a Tree
330
9
Exercises
332
1
5.6 Example: Game Trees
333
8
Exercises
339
2
CHAPTER 6 Sorting
341
54
6.1 General Background
341
10
Efficiency Considerations
343
2
O Notation
345
2
Efficiency of Sorting
347
2
Exercises
349
2
6.2 Exchange Sorts
351
12
Bubble Sort
351
2
Quicksort
353
6
Efficiency of Quicksort
359
3
Exercises
362
1
6.3 Selection and Tree Sorting
363
13
Straight Selection Sort
364
1
Binary Tree Sorts
365
2
Heapsort
367
1
Heap as a Priority Queue
368
2
Sorting Using a Heap
370
3
Heapsort Method
373
2
Exercises
375
1
6.4 Insertion Sorts
376
9
Simple Insertion
376
1
Shell Sort
377
3
Address Calculation Sort
380
3
Exercises
383
2
6.5 Merge and Radix Sorts
385
10
Merge Sorts
385
3
The Cook-Kim Algorithm
388
1
Radix Sort
388
4
Exercises
392
3
CHAPTER 7 Searching
395
126
7.1 Basic Search Techniques
395
16
Dictionary as an Abstract Data Type
396
1
Algorithmic Notation
397
1
Sequential Searching
398
1
Efficiency of Sequential Searching
399
1
Reordering a List for Maximum Search Efficiency
400
2
Searching an Ordered Table
402
1
Indexed Sequential Search
403
1
Binary Search
404
3
Interpolation Search
407
1
Exercises
408
3
7.2 Tree Searching
411
22
Inserting into a Binary Search Tree
414
1
Deleting from a Binary Search Tree
414
2
Efficiency of Binary Search Tree Operations
416
3
Efficiency of Nonuniform Binary Search Trees
419
2
Optimum Search Trees
421
1
Balanced Trees
422
9
Exercises
431
2
7.3 General Search Trees
433
42
Multi way Search Trees
433
2
Searching a Multiway Tree
435
1
Implementing a Multiway Tree
436
2
Traversing a Multiway Tree
438
2
Insertion in a Multiway Search Tree
440
4
B-Trees
444
6
Algorithms for B-Tree Insertion
450
4
Computing father and index
454
3
Deletion in Multiway Search Trees
457
10
Efficiency of Multiway Search Trees
467
Improving the B-Tree
464
4
B+-Trees
468
1
Digital Search Trees
469
3
Tries
472
2
Exercises
474
1
7.4 Hashing
475
46
Resolving Hash Clashes by Open Addressing
477
3
Deleting Items from a Hash Table
480
1
Efficiency of Rehashing Methods
480
3
Hash Table Reordering
483
1
Brent's Method
484
2
Binary Tree Hashing
486
3
Improvements with Additional Memory
489
3
Coalesced Hashing
492
2
Separate Chaining
494
4
Hashing in External Storage
498
2
Separator Method
500
1
Dynamic Hashing and Extendible Hashing
501
5
Linear Hashing
506
5
Choosing a Hash Function
511
3
Perfect Hash Functions
514
4
Universal Classes of Hash Functions
518
1
Exercises
519
2
CHAPTER 8 Graphs and their Applications
521
67
8.1 Graphs
521
15
An Application of Graphs
524
2
Java Representation of Graphs
526
2
Transitive Closure
528
3
Warshall's Algorithm
531
1
Shortest-Path Algorithm
532
3
Exercises
535
1
8.2 Flow Problem
536
12
Improving a Flow Function
538
3
Example
541
2
Algorithm and Program
543
4
Exercises
547
1
8.3 Linked Representation of Graphs
548
21
Dijkstra's Algorithm Revisited
556
2
Organizing the Set of Graph Nodes
558
1
Application to Scheduling
559
4
Java Program
563
3
Exercises
566
3
8.4 Graph Traversal and Spanning Forests
569
19
Traversal Methods for Graphs
569
4
Spanning Forests
573
2
Undirected Graphs and Their Traversals
575
2
Depth-First Traversal
577
3
Applications of Depth-First Traversal
580
1
Efficiency of Depth-First Traversal
581
1
Breadth-First Traversal
582
1
Minimum Spanning Trees
583
2
Kruskal's Algorithm
585
1
Round-Robin Algorithm
586
1
Exercises
586
2
CHAPTER 9 Storage Management
588
61
9.1 General Lists
588
17
Operations That Modify a List
590
1
Examples
591
1
Linked List Representation of a List
592
3
Representation of Lists
595
1
crList Operation
596
2
Use of List Headers
598
2
Freeing List Nodes
600
1
General Lists in Java
601
2
Programming Languages and Lists
603
2
Exercises
605
1
9.2 Automatic List Management
605
21
Reference Count Method
606
5
Garbage Collection
611
1
Algorithms for Garbage Collection
612
6
Collection and Compaction
618
6
Variations of Garbage Collection
624
1
Exercises
625
1
9.3 Dynamic Memory Management
626
23
Compaction of Blocks of Storage
627
2
First-Fit, Best-Fit, and Worst-Fit
629
4
Improvements in the First-Fit Method
633
1
Freeing Storage Blocks
634
2
Boundary Tag Method
636
2
Buddy System
638
7
Other Buddy Systems
645
2
Exercises
647
2
Index
649