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# is becoming a very popular language and this
book provides the C# programmer with the opportunity to study fundamental
data structures and algorithms.
学习数据结构和算法对专业程序员来说很重要，大多数书包括大学教材上一般都用C++或java描述数据结构。
C#也开始流行了，介此机会，本书来研究一下数据结构和算法。
C# exists in a very rich development environment called the .NET Framework.
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 conversions,
demonstrating the utility of the data structure immediately.
C#运行在.net框架上，.net类库包括很多数据结构的类（也叫做集合类），涵盖了数组，泛型数组，集合类，栈，队列以及hashtable和链表等类。
数据结构和算法的学习者现在可以不知道如何实现的情况下使用它们，之前教授不得不讨论一下栈的概念，在整个数据结构构建之前都很抽象。
现在教授可以向学生演示如何使用栈做一些运算，比如数的转换，立即就展示了数据结构的用处。
Withthis 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 structures
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
means, look at any of the books mentioned in the bibliography). Instead, the
various data structures and algorithms are presented as problem-solving tools.
Simple timing tests are used to compare the performance of the data structures
and algorithms discussed in the book.
基于此背景，学生可以回顾和学习数据结构或算法的本质，甚至自己去实现。本书只对一些高级程序员需要了解和掌握的算法做了概览。
鉴于此，并没有对数据结构做正式的分析。所以，没有什么数学公式，也没有O分析（不知道O是什么的人，去看本书参考的其他书目）。
相反，只把各种数据结构和算法被作为解决问题的工具。用了简单的计时测试来比较各数据结构和算法的性能。
PREREQUISITES
The only prerequisite for this book is that the reader have some familiarity
with the C# language in general, and object-oriented programming in C# in
particular.
先决条件：唯一的先决条件是读者需要熟悉C#，面向对象。
CHAPTER-BY-CHAPTER ORGANIZATION
Chapter 1 introduces the reader to the concept of the data structure as a
collection of data. The concepts of linear and nonlinear collections are introduced.
The Collection class is demonstrated. This chapter also introduces the
concept of generic programming, which allows the programmer to write one
class, or one method, and have it work for a multitude of data types. Generic
programming is an important new addition to C# (available in C# 2.0 and
beyond), so much so that there is a special library of generic data structures
found in the System.Collections.Generic namespace. When a data structure
has a generic implementation found in this library, its use is discussed. The
chapter ends with an introduction to methods of measuring the performance
of the data structures and algorithms discussed in the book.
第一章介绍了数据结构做为数据集合的概念，线性和非线性集合，集合类，泛型编程（允许一个类或方法支持多种数据类型）。
泛型是C#2.0新特性，所以有System.Collections.Generic这个新的命名空间，章末介绍了计算算法效率的方法。
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 fundamental
algorithms for searching memory, the sequential and binary searches.
Two 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
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. Chapter
10 covers hash tables and the HashTable class, which is a special type of
dictionary that uses a hashing algorithm for storing data internally.
Another classic data structure, the linked list, is covered in Chapter 11.
Linked lists are not as important a data structure in C# as they are in a
pointer-based language such as C++, but they still have a role in C# programming.
Chapter 12 introduces the reader to yet another classic data structure—
the binary tree. A specialized type of binary tree, the binary search tree, is
the primary topic of the chapter. Other types of binary trees are covered in
Chapter 15.
Chapter 13 shows the reader how to store data in sets, which can be useful in
situations in which only unique data values can be stored in the data structure.
Chapter 14 covers more advanced sorting algorithms, including the popular
and efficient QuickSort, which is the basis for most of the sorting procedures
implemented in the .NET Framework library. Chapter 15 looks at three data
structures that prove useful for searching when a binary search tree is not
called for: the AVL tree, the red-black tree, and the skip list.
Chapter 16 discusses graphs and graph algorithms. Graphs are useful for
representing many different types of data, especially networks. Finally, Chapter
17 introduces the reader to what algorithm design techniques really are:
dynamic algorithms and greedy algorithms.
ACKNOWLEDGEMENTS
There are several different groups of people who must be thanked for helping
me finish this book. First, thanks to a certain group of students who first
sat through my lectures on developing data structures and algorithms. These
students include (not in any particular order): Matt Hoffman, Ken Chen, Ken
Cates, Jeff Richmond, and Gordon Caffey. Also, one of my fellow instructors
at Pulaski Technical College, Clayton Ruff, sat through many of the lectures
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.