search for books and compare prices
Tables of Contents for Data Structures Using C and C++
Chapter/Section Title
Page #
Page Count
Preface
xiii
1 Introduction to Data Structures
1
76
1.1 Information and Meaning
1
23
Binary and Decimal Integers
2
2
Real Numbers
4
1
Character Strings
5
1
Hardware and Software
6
2
Concept of Implementation
8
1
Example
8
5
Abstract Data Types
13
4
Sequences as Value Definitions
17
1
ADT for Varying-length Character Strings
18
2
Data Types in C
20
1
Pointers in C
20
2
Data Structures and C
22
2
Exercises
24
1
1.2 Arrays in C
24
18
The Array as an ADT
26
1
Using One-Dimensional Arrays
27
1
Implementing One-Dimensional Arrays
28
3
Arrays as Parameters
31
1
Character Strings in C
32
1
Character String Operations
33
1
Two-Dimensional Arrays
34
3
Multidimensional Arrays
37
3
Exercises
40
2
1.3 Structures in C
42
21
Implementing Structures
46
2
Unions
48
3
Implementation of Unions
51
1
Structure Parameters
52
2
Representing Other Data Structures
54
1
Rational Numbers
55
3
Allocation of Storage and Scope of Variables
58
4
Exercises
62
1
1.4 Classes in C++
63
14
The Class Rational
64
1
Using the Class Rational
65
2
Implementing the Methods
67
5
Overloading
72
1
Inheritance
72
2
Constructors
74
2
Exercises
76
1
2 The Stack
77
40
2.1 Definition and Examples
77
9
Primitive Operations
80
1
Example
81
3
The Stack as an Abstract Data Type
84
1
Exercises
85
1
2.2 Representing Stacks in C
86
9
Implementing the pop Operation
90
1
Testing for Exceptional Conditions
91
1
Implementing the Push Operation
92
3
Exercises
95
1
2.3 Example: Infix, Postfix, and Prefix
95
22
Basic Definitions and Examples
95
3
Evaluating a Postfix Expression
98
1
Program to Evaluate a Postfix Expression
99
3
Limitations of the Program
102
1
Converting an Expression from Infix to Postfix
102
4
Program to Convert an Expression from Infix to Postfix
106
3
Stacks in C++ Using Templates
109
6
Exercises
115
2
3 Recursion
117
57
3.1 Recursive Definition and Processes
117
10
Factorial Function
117
3
Multiplication of Natural Numbers
120
1
Fibonacci Sequence
121
1
Binary Search
122
3
Properties of Recursive Definitions or Algorithms
125
1
Exercises
126
1
3.2 Recursion in C
127
13
Factorial in C
127
4
Fibonacci Numbers in C
131
1
Binary Search in C
132
2
Recursive Chains
134
1
Recursive Definition of Algebraic Expressions
135
3
Exercises
138
2
3.3 Writing Recursive Programs
140
13
The Towers of Hanoi Problem
142
4
Translation from Prefix to Postfix Using Recursion
146
4
Exercises
150
3
3.4 Simulating Recursion
153
19
Return from a Function
155
1
Implementing Recursive Functions
156
1
Simulation of Factorial
157
4
Improving the Simulated Routine
161
2
Eliminating gotos
163
2
Simulating the Towers of Hanoi
165
5
Exercises
170
2
3.5 Efficiency of Recursion
172
2
Exercises
173
1
4 Queues and Lists
174
75
4.1 The Queue and Its Sequential Representation
174
12
The Queue as an Abstract Data Type
176
1
C Implementation of Queues
176
4
insert Operation
180
2
Priority Queue
182
1
Array Implementation of a Priority Queue
183
1
Exercises
184
2
4.2 Linked Lists
186
17
Inserting and Removing Nodes from a List
187
4
Linked Implementation of Stacks
191
2
getnode and freenode Operations
193
1
Linked Implementation of Queues
194
1
Linked List as a Data Structure
195
3
Examples of List Operations
198
2
List Implementation of Priority Queues
200
1
Header Nodes
200
2
Exercises
202
1
4.3 Lists in C
203
17
Array Implementation of Lists
203
3
Limitations of the Array Implementation
206
1
Allocating and Freeing Dynamic Variables
207
4
Linked Lists Using Dynamic Variables
211
2
Queues as Lists in C
213
2
Examples of List Operations in C
215
1
Noninteger and Nonhomogeneous Lists
216
1
Comparing the Dynamic and Array Implementations of Lists
217
1
Implementing Header Nodes
218
1
Exercises
219
1
4.4 Example: Simulation Using Linked Lists
220
8
Simulation Process
221
1
Data Structures
222
1
Simulation Program
223
4
Exercises
227
1
4.5 Other List Structures
228
17
Circular Lists
229
1
Stack as a Circular List
229
1
Queue as a Circular List
230
1
Primitive Operations on Circular Lists
231
1
The Josephus Problem
232
2
Header Nodes
234
1
Addition of Long Positive Integers Using Circular Lists
235
2
Doubly Linked Lists
237
2
Addition of Long Integers Using Doubly Linked Lists
239
5
Exercises
244
1
4.6 The Linked List in C++
245
4
Exercises
248
1
5 Trees
249
80
5.1 Binary Trees
249
12
Operations on Binary Trees
254
1
Applications of Binary Trees
255
5
Exercises
260
1
5.2 Binary Tree Representations
261
22
Node Representation of Binary Trees
261
3
Internal and External Nodes
264
1
Implicit Array Representation of Binary Trees
265
4
Choosing a Binary Tree Representation
269
1
Binary Tree Traversals in C
270
3
Threaded Binary Trees
273
4
Traversal Using a father Field
277
3
Heterogeneous Binary Trees
280
1
Exercises
281
2
5.3 Example: The Huffman Algorithm
283
9
The Huffman Algorithm
287
1
C Program
288
3
Exercises
291
1
5.4 Representing Lists as Binary Trees
292
13
Finding the kth Element
294
2
Deleting an Element
296
3
Implementing Tree-Represented Lists in C
299
2
Constructing a Tree-Represented List
301
2
The Josephus Problem Revisited
303
1
Exercises
304
1
5.5 Trees and Their Applications
305
16
C Representations of Trees
307
2
Tree Traversals
309
3
General Expressions as Trees
312
3
Evaluating an Expression Tree
315
2
Constructing a Tree
317
2
Exercises
319
2
5.6 Example: Game Trees
321
8
Exercises
327
2
6 Sorting
329
55
6.1 General Background
329
10
Efficiency Considerations
331
3
O Notation
334
2
Efficiency of Sorting
336
2
Exercises
338
1
6.2 Exchange Sorts
339
12
Bubble Sort
339
3
Quicksort
342
6
Efficiency of Quicksort
348
2
Exercises
350
1
6.3 Selection and Tree Sorting
351
14
Straight Selection Sort
352
1
Binary Tree Sorts
353
3
Heapsort
356
1
Heap as a Priority Queue
357
2
Sorting Using a Heap
359
3
Heapsort Procedure
362
2
Exercises
364
1
6.4 Insertion Sorts
365
8
Simple Insertion
365
1
Shell Sort
366
4
Address Calculation Sort
370
2
Exercises
372
1
6.5 Merge and Radix Sorts
373
11
Merge Sorts
373
4
The Cook-Kim Algorithm
377
1
Radix Sort
377
4
Exercises
381
3
7 Searching
384
131
7.1 Basic Search Techniques
384
17
Dictionary as an Abstract Data Type
385
1
Algorithmic Notation
386
1
Sequential Searching
387
2
Efficiency of Sequential Searching
389
1
Reordering a List for Maximum Search Efficiency
390
2
Searching an Ordered Table
392
1
Indexed Sequential Search
392
2
Binary Search
394
3
Interpolation Search
397
1
Exercises
398
3
7.2 Tree Searching
401
22
Inserting into a Binary Search Tree
404
1
Deleting from a Binary Search Tree
404
3
Efficiency of Binary Search Tree Operations
407
2
Efficiency of Nonuniform Binary Search Trees
409
2
Optimum Search Trees
411
2
Balanced Trees
413
8
Exercises
421
2
7.3 General Search Trees
423
45
Multiway Search Trees
423
3
Searching a Multiway Tree
426
1
Implementing a Multiway Tree
427
1
Traversing a Multiway Tree
428
2
Insertion in a Multiway Search Tree
430
5
B-Trees
435
4
Algorithms for B-Tree Insertion
439
6
Computing father and index
445
4
Deletion in Multiway Search Trees
449
4
Efficiency of Multiway Search Trees
453
3
Improving the B-Tree
456
4
B(+) -Trees
460
1
Digital Search Trees
461
4
Tries
465
2
Exercises
467
1
7.4 Hashing
468
47
Resolving Hash Clashes by Open Addressing
470
3
Deleting Items from a Hash Table
473
1
Efficiency of Rehashing Methods
474
2
Hash Table Reordering
476
1
Brent's Method
477
3
Binary Tree Hashing
480
2
Improvements with Additional Memory
482
3
Coalesced Hashing
485
3
Separate Chaining
488
3
Hashing in External Storage
491
2
Separator Method
493
1
Dynamic Hashing and Extendible Hashing
494
5
Linear Hashing
499
6
Choosing a Hash Function
505
3
Perfect Hash Functions
508
4
Universal Classes of Hash Functions
512
1
Exercises
513
2
8 Graphs and Their Applications
515
64
8.1 Graphs
515
14
Application of Graphs
517
3
C Representation of Graphs
520
1
Transitive Closure
521
4
Warshall's Algorithm
525
1
Shortest-Path Algorithm
526
2
Exercises
528
1
8.2 A Flow Problem
529
12
Improving a Flow Function
531
4
Example
535
2
Algorithm and Program
537
4
Exercises
541
1
8.3 Linked Representation of Graphs
541
19
Dijkstra's Algorithm Revisited
547
2
Organizing the Set of Graph Nodes
549
1
Application to Scheduling
550
4
C Program
554
3
Exercises
557
3
8.4 Graph Traversal and Spanning Forests
560
19
Traversal Methods for Graphs
560
3
Spanning Forests
563
3
Undirected Graphs and Their Traversals
566
2
Depth-First Traversal
568
3
Applications of Depth-First Traversal
571
1
Efficiency of Depth-First Traversal
572
1
Breadth-First Traversal
573
1
Minimum Spanning Trees
574
2
Kruskal's Algorithm
576
1
Round-Robin Algorithm
577
1
Exercises
577
2
9 Storage Management
579
68
9.1 General Lists
579
20
Operations That Modify a List
582
1
Examples
583
1
Linked List Representation of a List
584
3
Representation of Lists
587
1
crlist Operation
588
3
Use of List Headers
591
2
Freeing List Nodes
593
1
General Lists in C
594
3
Programming Languages and Lists
597
2
Exercises
599
1
9.2 Automatic List Management
599
22
Reference Count Method
599
6
Garbage Collection
605
1
Algorithms for Garbage Collection
606
7
Collection and Compaction
613
6
Variations of Garbage Collection
619
1
Exercises
620
1
9.3 Dynamic Memory Management
621
26
Compaction of Blocks of Storage
622
3
First Fit, Best Fit, and Worst Fit
625
6
Improvements in the First-Fit Method
631
1
Freeing Storage Blocks
632
1
Boundary Tag Method
633
3
Buddy System
636
7
Other Buddy Systems
643
2
Exercises
645
2
Bibliography and References
647
16
Index
663