文档介绍：+-----------------------------------------------------------------------------+
| |
| Sorting and Searching:
|
| A Cookbook
|
| |
| |
| |
| Thomas Niemann
|
| |
+-----------------------------------------------------------------------------+
***** Contents *****
1. Introduction 7
2. Sorting 11
Insertion Sort 11
Shell Sort 12
Quicksort 14
of Methods 17
3. Dictionaries 18
Hash Tables 18
Binary Search Trees 21
Red-Black Trees 24
Skip Lists 28
of Methods 29
4. Code Listings 32
Insertion Sort Code 32
Shell Sort Code 33
Quicksort Code 34
Qsort Code 36
Hash Table Code 37
Binary Search Tree Code 38
Red-Black Tree Code 41
Skip List Code 46
5. Bibliography 50
Preface
This booklet contains a collection of sorting and searching algorithms.
While many books on data structures describe sorting and searching algorithms,
most assume a background in calculus and probability theory. Although a formal
presentation and proof of asymptotic behavior is important, a more intuitive
explanation is often possible.
The way each algorithm works is described in easy-to-understand terms. It
is assumed that you have the knowledge equivalent to an introductory course in C
or Pascal. In particular, you should be familiar with arrays and have a basic
understanding of pointers. The material is presented in an orderly fashion,
beginning with easy concepts and progressing to plex ideas. Even though
this collection is intended for beginners, more advanced users may benefit from
some of the insights offered. In particular, the sections on hash tables and
skip
lists should prove interesting.
Santa Cruz, California
Thomas Niemann
March, 1995
1. Introduction
Arrays and linked lists are two basic data structures used to store
information. We may wish to search, insert or delete recor