C# programmers: no more translating data structures from C++ or Java to use in your programs! Mike McMillan provides a tutorial on how to use data structures and algorithms plus the first comprehensive reference for C# implementation of data structures and algorithms found in the .NET Framework library, as well as those developed by the programmer. The approach is very practical, using timing tests rather than Big O notation to analyze the efficiency of an approach. Coverage includes arrays and array lists, linked lists, hash tables, dictionaries, trees, graphs, and sorting and searching algorithms, as well as more advanced algorithms such as probabilistic algorithms and dynamic programming. This is the perfect resource for C# professionals and students alike.
Author(s): Michael McMillan
Edition: 1
Publisher: Cambridge University Press
Year: 2007
Language: English
Pages: 367
Contents......Page 7
Preface......Page 9
1 An Introduction to Collections, Generics, and the Timing Class ......Page 13
Direct Access Collections......Page 14
Sequential Access Collections......Page 18
Hierarchical Collections......Page 20
Group Collections......Page 21
A Collection Class Implementation Using ArrayLists......Page 23
Implementing the Collection Class......Page 24
Generic Programming......Page 26
An Oversimplified Timing Test......Page 29
Timing Tests for the .NET Environment......Page 30
A Timing Test Class......Page 33
Exercises......Page 36
Array Basics......Page 38
Declaring and Initializing Arrays......Page 39
Methods and Properties for Retrieving Array Metadata......Page 40
Multidimensional Arrays......Page 42
Jagged Arrays......Page 44
Members of the ArrayList Class......Page 47
Using the ArrayList Class......Page 48
Summary......Page 52
Exercises......Page 53
Sorting Algorithms......Page 54
An Array Class Test Bed......Page 55
Bubble Sort......Page 57
Examining the Sorting Process......Page 58
Selection Sort......Page 60
Insertion Sort......Page 62
Timing Comparisons of the Basic Sorting Algorithms......Page 63
Summary......Page 65
Exercises......Page 66
Sequential Searching......Page 67
Searching for Minimum and Maximum Values......Page 70
Making Sequential Search Faster: Self-Organizing Data......Page 71
Binary Search......Page 74
A Recursive Binary Search Algorithm......Page 76
Exercises......Page 78
Stacks, a Stack Implementation and the Stack Class......Page 80
Stack Operations......Page 81
A Stack Class Implementation......Page 82
The Stack Class......Page 84
The Stack Constructor Methods......Page 85
The Primary Stack Operations......Page 86
The Clear Method......Page 88
The CopyTo and ToArray Methods......Page 89
A Stack Class Example: Decimal to Multiple-Bases Conversion......Page 90
Queue Operations......Page 92
A Queue Implementation......Page 93
The Queue Class: A Sample Application......Page 94
Sorting Data With Queues......Page 98
Priority Queues: Deriving From the Queue Class......Page 102
Summary......Page 104
Exercises......Page 105
A Motivating Problem......Page 106
The Binary Number System......Page 108
Manipulating Binary Numbers: The Bitwise and Bit-shift Operators......Page 109
A Bitwise Operator Application......Page 111
The BitShift Operators......Page 115
An Integer-to-Binary Converter Application......Page 116
A Bit Shift Demonstration Application......Page 119
Using the BitArray Class......Page 122
More BitArray Class Methods and Properties......Page 125
Using a BitArray To Write the Sieve of Eratosthenes......Page 126
Summary......Page 129
Exercises......Page 130
Working with the String Class......Page 131
Creating String Objects......Page 132
Frequently Used String Class Methods......Page 133
The Split and Join Methods......Page 136
Methods for Comparing Strings......Page 138
Methods for Manipulating Strings......Page 142
The StringBuilder Class......Page 149
Obtaining and Setting Information about StringBuilder Objects......Page 150
Modifying StringBuffer Objects......Page 151
Comparing the Efficiency of the String Class to StringBuilder......Page 155
Summary......Page 157
Exercises......Page 158
An Introduction to Regular Expressions......Page 159
Working With Regular Expressions: An Overview......Page 160
Quantifiers......Page 163
Using Character Classes......Page 165
Modifying Regular Expressions Using Assertions......Page 168
Anonymous Groups......Page 169
Named Groups......Page 170
Zero-Width Lookahead and Lookbehind Assertions......Page 172
The CapturesCollection Class......Page 173
Regular Expression Options......Page 175
Exercises......Page 176
9 Building Dictionaries: The DictionaryBase Class and the SortedList Class ......Page 177
Fundamental DictionaryBase Class Methods and Properties......Page 178
Other DictionaryBase Methods......Page 181
The Generic KeyValuePair Class......Page 183
Using the SortedList Class......Page 184
Summary......Page 186
Exercises......Page 187
An Overview of Hashing......Page 188
Choosing a Hash Function......Page 189
Handling Collisions......Page 192
Bucket Hashing......Page 193
Double Hashing......Page 195
Instantiating and Adding Data to a Hashtable Object......Page 196
Retrieving the Keys and the Values Separately From a Hash Table......Page 197
Retrieving a Value Based on the Key......Page 198
Utility Methods of the Hashtable Class......Page 199
A Hashtable Application: Computer Terms Glossary......Page 201
Summary......Page 204
Exercises......Page 205
The Problem With Arrays......Page 206
Linked Lists Defined......Page 207
The Node Class......Page 208
The LinkedList Class......Page 209
The Doubly Linked List......Page 212
The Circularly Linked List......Page 215
Using An Iterator Class......Page 218
The New LinkedList Class......Page 220
Demonstrating the Iterator Class......Page 221
A Generic Linked List Example......Page 226
Summary......Page 228
Exercises......Page 229
The Definition of a Tree......Page 230
Binary Trees......Page 232
Building a Binary Search Tree......Page 233
Traversing a Binary Search Tree......Page 236
Finding a Node and Minimum/Maximum Values in a Binary Search Tree......Page 239
Removing a Leaf Node From a BST......Page 240
Deleting a Node With Two Children......Page 242
Exercises......Page 247
Fundamental Set Definitions, Operations and Properties......Page 249
Set Properties......Page 250
Class Data Members and Constructor Method......Page 251
The Remove and Size Methods......Page 252
The isSubset Method......Page 253
The Difference Method......Page 254
A Program to Test the CSet Implementation......Page 255
Overview of Using a BitArray Implementation......Page 256
The BitArray Set Implementation......Page 257
Exercises......Page 260
The ShellSort Algorithm......Page 261
The MergeSort Algorithm......Page 263
Building a Heap......Page 266
The QuickSort Algorithm Described......Page 271
Code for the QuickSort Algorithm......Page 272
Exercises......Page 274
AVL Tree Fundamentals......Page 275
The AVL Tree Implementation......Page 276
Red--Black Trees......Page 280
Red--Black Tree Insertion......Page 281
Red--Black Tree Implementation Code......Page 282
Skip List Fundamentals......Page 287
Skip List Implementation......Page 289
Exercises......Page 294
Graph Definitions......Page 295
Real World Systems Modeled by Graphs......Page 296
Representing Vertices......Page 297
Representing Edges......Page 298
Building a Graph......Page 299
An Algorithm for Topological Sorting......Page 301
Implementing the Algorithm......Page 302
Searching a Graph......Page 305
Depth-First Search......Page 306
Breadth-First Search......Page 308
A Minimum Spanning Tree Algorithm......Page 311
Weighted Graphs......Page 314
Dijkstra’s Algorithm for Determining the Shortest Path......Page 315
Code for Dijkstra’s Algorithm......Page 317
Exercises......Page 324
Dynamic Programming......Page 326
A Dynamic Programming Example: Computing Fibonacci Numbers......Page 327
Finding the Longest Common Substring......Page 331
The Knapsack Problem......Page 334
A First Greedy Algorithm Example: The Coin-Changing Problem......Page 336
Data Compression Using Huffman Coding......Page 338
A Greedy Solution to the Knapsack Problem......Page 345
Summary......Page 348
Exercises......Page 349
References......Page 351
Index......Page 353