P1: FCW
0521670152pre CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 20:59
D
ATA
S
TRUCTURES AND
A
LGORITHMS
U
SING
C#
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# imple-
mentation 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 nota-
tion to analyze the efficiency of an approach. Coverage includes array and
ArrayLists, linked lists, hash tables, dictionaries, trees, graphs, and sorting
and searching algorithms, as well as more advanced algorithms such as prob-
abilistic algorithms and dynamic programming. This is the perfect resource
for C# professionals and students alike.
Michael McMillan is Instructor of Computer Information Systems at Pulaski
Technical College, as well as an adjunct instructor at the University of
Arkansas at Little Rock and the University of Central Arkansas. Mike’s previ-
ous books include Object-Oriented Programming with Visual Basic.NET, Data
Structures and Algorithms Using Visual Basic.NET, and Perl from the Ground Up.
He is a co-author of Programming and Problem-Solving with Visual Basic.NET.
Mike has written more than twenty-five trade journal articles on programming
and has more than twenty years of experience programming for industry and

Information on this title: www.cambridge.org/9780521876919
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the
permission of Cambridge University Press.
ISBN-10 0-521-87691-5
ISBN-10 0-521-67015-2
Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
hardback
paperback
paperback
hardback
llausv
P1: FCW
0521670152pre CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 20:59
Contents
Preface page vii
Chapter 1
An Introduction to Collections, Generics, and the
Timing Class 1
Chapter 2
Arrays and ArrayLists 26
Chapter 3
Basic Sorting Algorithms 42
Chapter 4
Basic Searching Algorithms 55

Advanced Algorithms 314
References 339
Index 341
P1: FCW
0521670152pre CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 20:59
Preface
The study of data structures and algorithms is critical to the development
of the professional programmer. There are many, many books written on
data structures and algorithms, but these books are usually written as college
textbooks and are written using the programming languages typically taught
in college—Java or C++.C#isbecoming a very popular language and this
book provides the C# programmer with the opportunity to study fundamental
data structures and algorithms.
C# exists in a very rich development environment called the .NET Frame-
work. Included in the .NET Framework library is a set of data structure classes
(also called collection classes), which range from the Array, ArrayList, and
Collection classes to the Stack and Queue classes and to the HashTable and
the SortedList classes. The data structures and algorithms student can now see
how to use a data structure before learning how to implement it. Previously,
an instructor had to discuss the concept of, say, a stack, abstractly until the
complete data structure was constructed. Instructors can now show students
how to use a stack to perform some computation, such as number base con-
versions, demonstrating the utility of the data structure immediately. With
this background, the student can then go back and learn the fundamentals of
the data structure (or algorithm) and even build their own implementation.
This book is written primarily as a practical overview of the data struc-
tures and algorithms all serious computer programmers need to know and
understand. Given this, there is no formal analysis of the data structures and
algorithms covered in the book. Hence, there is not a single mathematical
formula and not one mention of Big Oh analysis (if you don’t know what this

chapter ends with an introduction to methods of measuring the performance
of the data structures and algorithms discussed in the book.
Chapter 2 provides a review of how arrays are constructed, along with
demonstrating the features of the Array class. The Array class encapsulates
many of the functions associated with arrays (UBound, LBound, and so on)
into a single package. ArrayLists are special types of arrays that provide
dynamic resizing capabilities.
Chapter 3 is an introduction to the basic sorting algorithms, such as the
bubble sort and the insertion sort, and Chapter 4 examines the most funda-
mental algorithms for searching memory, the sequential and binary searches.
Tw o classic data structures are examined in Chapter 5: the stack and the
queue. The emphasis in this chapter is on the practical use of these data
structures in solving everyday problems in data processing. Chapter 6 covers
the BitArray class, which can be used to efficiently represent a large number
of integer values, such as test scores.
Strings are not usually covered in a data structures book, but Chapter 7
covers strings, the String class, and the StringBuilder class. Because so much
P1: FCW
0521670152pre CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 20:59
PREFACE ix
data processing in C# is performed on strings, the reader should be exposed
to the special techniques found in the two classes. Chapter 8 examines the
use of regular expressions for text processing and pattern matching. Regular
expressions often provide more power and efficiency than can be had with
more traditional string functions and methods.
Chapter 9 introduces the reader to the use of dictionaries as data structures.
Dictionaries, and the different data structures based on them, store data as
key/value pairs. This chapter shows the reader how to create his or her own
classes based on the DictionaryBase class, which is an abstract class. Chap-
ter 10 covers hash tables and the HashTable class, which is a special type of

and provided excellent comments and criticism. I also have to thank my
department dean, David Durr, and my department chair, Bernica Tackett, for
supporting my writing endeavors. I also need to thank my family for putting
up with me while I was preoccupied with research and writing. Finally, many
thanks to my editors at Cambridge, Lauren Cowles and Heather Bergman, for
putting up with my many questions, topic changes, and habitual lateness.
P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
C
HAPTER
1
An Introduction to
Collections, Generics,
and the Timing Class
T
his book discusses the development and implementation of data structures
and algorithms using C#. The data structures we use in this book are found
in the .NET Framework class library System.Collections. In this chapter, we
develop the concept of a collection by first discussing the implementation of
our own Collection class (using the array as the basis of our implementation)
and then by covering the Collection classes in the .NET Framework.
An important addition to C# 2.0 is generics. Generics allow the C# pro-
grammer to write one version of a function, either independently or within a
class, without having to overload the function many times to allow for differ-
ent data types. C# 2.0 provides a special library, System.Collections.Generic,
that implements generics for several of the System.Collections data structures.
This chapter will introduce the reader to generic programming.
Finally, this chapter introduces a custom-built class, the Timing class, which
we will use in several chapters to measure the performance of a data structure
and/or algorithm. This class will take the place of Big O analysis, not because

from a collection), Clear (for removing all the elements from a collection),
Contains (for determining if a specified element is a member of a collec-
tion), and IndexOf (for determining the index of a specified element in a
collection).
C
OLLECTIONS
D
ESCRIBED
Within the two major categories of collections are several subcategories.
Linear collections can be either direct access collections or sequential access
collections, whereas nonlinear collections can be either hierarchical or
grouped. This section describes each of these collection types.
Direct Access Collections
The most common example of a direct access collection is the array. We define
an array as a collection of elements with the same data type that are directly
accessed via an integer index, as illustrated in Figure 1.1.
P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
Collections Described 3
Item ø Item 1 Item 2 Item 3
. . .
Item j Item n−1
F
IGURE
1.1. Array.
Arrays can be static so that the number of elements specified when the array
is declared is fixed for the length of the program, or they can be dynamic, where
the number of elements can be increased via the ReDim or ReDim Preserve
statements.
In C#, arrays are not only a built-in data type, they are also a class. Later

P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
4 INTRODUCTION TO COLLECTIONS, GENERICS, AND TIMING CLASS
record consists of employee’ name (a string), salary (an integer), identification
number (a string, or an integer), as well as other attributes. Since storing each
of these data values in separate variables could become confusing very easily,
the language provides the struct for storing data of this type.
A powerful addition to the C# struct is the ability to define methods for
performing operations stored on the data in a struct. This makes a struct
somewhat like a class, though you can’t inherit or derive a new type from
a structure. The following code demonstrates a simple use of a structure
in C#:
using System;
public struct Name {
private string fname, mname, lname;
public Name(string first, string middle, string last) {
fname = first;
mname = middle;
lname = last;
}
public string firstName {
get {
return fname;
}
set {
fname = firstName;
}
}
public string middleName {
get {

fullName = myName.ToString();
inits = myName.Initials();
Console.WriteLine("My name is {0}.", fullName);
Console.WriteLine("My initials are {0}.", inits);
}
}
Although many of the elements in the .NET environment are implemented as
classes (such as arrays and strings), several primary elements of the language
are implemented as structures, such as the numeric data types. The Integer
data type, for example, is implemented as the Int32 structure. One of the
methods you can use with Int32 is the Parse method for converting the string
representation of a number into an integer. Here’s an example:
using System;
public class IntStruct {
static void Main() {
P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
6 INTRODUCTION TO COLLECTIONS, GENERICS, AND TIMING CLASS
int num;
string snum;
Console.Write("Enter a number: ");
snum = Console.ReadLine();
num = Int32.Parse(snum);
Console.WriteLine(num);
}
}
Sequential Access Collections
A sequential access collection is a list that stores its elements in sequential
order. We call this type of collection a linear list. Linear lists are not limited
by size when they are created, meaning they are able to expand and contract

Mike
Bernica
Pop
David
Raymond
Mike
Bernica
F
IGURE
1.3. Stack Operations.
Some types of linear lists restrict access to their data elements. Examples
of these types of lists are stacks and queues. A stack is a list where access is
restricted to the beginning (or top) of the list. Items are placed on the list
at the top and can only be removed from the top. For this reason, stacks are
known as Last-in, First-out structures. When we add an item to a stack, we
call the operation a push. When we remove an item from a stack, we call that
operation a pop. These two stack operations are shown in Figure 1.3.
The stack is a very common data structure, especially in computer systems
programming. Stacks are used for arithmetic expression evaluation and for
balancing symbols, among its many applications.
A queue is a list where items are added at the rear of the list and removed
from the front of the list. This type of list is known as a First-in, First-out struc-
ture. Adding an item to a queue is called an EnQueue, and removing an item
from a queue is called a Dequeue. Queue operations are shown in Figure 1.4.
Queues are used in both systems programming, for scheduling operating
system tasks, and for simulation studies. Queues make excellent structures
for simulating waiting lines in every conceivable retail situation. A special
type of queue, called a priority queue, allows the item in a queue with the
highest priority to be removed from the queue first. Priority queues can be
used to study the operations of a hospital emergency room, where patients

function, takes one data value and transforms the value (called the key) into
an integer index that is used to retrieve the data. The index is then used to
access the data record associated with the key. For example, an employee
record may consist of a person’s name, his or her salary, the number of years
the employee has been with the company, and the department he or she works
in. This structure is shown in Figure 1.5. The key to this data record is the
employee’s name. C# has a class, called HashTable, for storing data in a hash
table. We explore this structure in Chapter 10.
Another generalized indexed collection is the dictionary. A dictionary is
made up of a series of key–value pairs, called associations. This structure
is analogous to a word dictionary, where a word is the key and the word’s
definition is the value associated with the key. The key is an index into the
value associated with the key. Dictionaries are often called associative arrays
because of this indexing scheme, though the index does not have to be an
integer. We will examine several Dictionary classes that are part of the .NET
Framework in Chapter 11.
Hierarchical Collections
Nonlinear collections are broken down into two major groups: hierarchical
collections and group collections. A hierarchical collection is a group of items
divided into levels. An item at one level can have successor items located at
the next lower level.
One common hierarchical collection is the tree. A tree collection looks like
an upside-down tree, with one data element as the root and the other data
values hanging below the root as leaves. The elements of a tree are called
nodes, and the elements that are below a particular node are called the node’s
children. A sample tree is shown in Figure 1.6.
P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
Collections Described 9
Root

6
81012
11 3
AA intersection B A union B
2
157
246
81012
123
5711
16
3
5
7
2
11
4
8
10
12
F
IGURE
1.7. Set Collection Operations.
A graph is a set of nodes and a set of edges that connect the nodes. Graphs
are used to model situations where each of the nodes in a graph must be visited,
sometimes in a particular order, and the goal is to find the most efficient way
to “traverse” the graph. Graphs are used in logistics and job scheduling and
are well studied by computer scientists and mathematicians. You may have
heard of the “Traveling Salesman” problem. This is a particular type of graph
problem that involves determining which cities on a salesman’s route should

A
D
142
B
C
91
202
72
186
F
IGURE
1.9. A Network Collection.
are implemented in C#. We start by looking at how to build a Collection class
using an abstract class from the .NET Framework, the CollectionBase class.
T
HE
C
OLLECTION
B
ASE
C
LASS
The .NET Framework library does not include a generic Collection class
for storing data, but there is an abstract class you can use to build your
own Collection class—CollectionBase. The CollectionBase class provides the
programmer with the ability to implement a custom Collection class. The
class implicitly implements two interfaces necessary for building a Collection
class, ICollection and IEnumerable, leaving the programmer with having to
implement just those methods that are typically part of a Collection class.
A Collection Class Implementation Using ArrayLists

Let’s start with the Add method. This method has one parameter – an
Object variable that holds the item to be added to the collection. Here is the
code:
public void Add(Object item) {
InnerList.Add(item);
}
ArrayLists store data as objects (the Object data type), which is why we
have declared item as Object. You will learn much more about ArrayLists
in Chapter 2.
The Remove method works similarly:
public void Remove(Object item) {
InnerList.Remove(item);
}
The next method is Count. Count is most often implemented as a prop-
erty, but we prefer to make it a method. Also, Count is implemented in the
P1: IBE
0521670152c01 CUNY656/McMillan Printer: cupusbw 0 521 67015 2 February 17, 2007 21:2
The CollectionBase Class 13
underlying class, CollectionBase, so we have to use the new keyword to hide
the definition of Count found in CollectionBase:
public new int Count() {
return InnerList.Count;
}
The Clear method removes all the items from InnerList. We also have to use
the new keyword in the definition of the method:
public new void Clear() {
InnerList.Clear();
}
This is enough to get us started. Let’s look at a program that uses the
Collection class, along with the complete class definition:

names.Remove("Raymond");
Console.WriteLine("Number of names:"+names.
Count());
names.Clear();
Console.WriteLine("Number of names:"+names.
Count());
}
}
There are several other methods you can implement in order to create a
more useful Collection class. You will get a chance to implement some of
these methods in the exercises.
Generic Programming
One of the problems with OOP is a feature called “code bloat.” One type of
code bloat occurs when you have to override a method, or a set of methods,
to take into account all of the possible data types of the method’s parameters.
One solution to code bloat is the ability of one value to take on multiple data
types, while only providing one definition of that value. This technique is
called generic programming.
A generic program provides a data type “placeholder” that is filled in by a
specific data type at compile-time. This placeholder is represented by a pair
of angle brackets (< >), with an identifier placed between the brackets. Let’s
look at an example.
A canonical first example for generic programming is the Swap function.
Here is the definition of a generic Swap function in C#: