SORTED LIST DATA TYPE
IMPLEMENTED IN ANSI C
Version 1.1
8/25/93
by Walt Karas
This document accompanies several ANSI C source files that implement
the "sorted list" data structure. This implementation can be used
whenever the set of possible elements of the sorted list have the
following characteristics:
1. All elements are of a single fixed size.
2. Each element is associated with a unique key value.
3. The set of key values has a well-defined "less than, greater than"
relation.
A symbol table would be a typical application for the sorted list data
structure.
The sorted list data structure is implemented as an AVL tree. AVL
trees were invented by Adelson-Velskii and Landis. The reference from
which I obtained the algorithms is Horowitz and Sahni, "Fundamentals
of Data Structures" (Computer Science Press). The add, find, and
delete operations on an AVL tree have worst-case O(log n) time
complexity.
USAGE
The sorted list data type is initialized by calling init_sort_list().
Elements are added to the sorted list by calling add_sort_list(). The
function find_sort_list() is called to search for an element in the
list using its associated key value. Calling the function
apply_sort_list() causes another function (passed as a parameter) to
be called for an (in order) series of elements in the list. A sorted
list can be created from an ascendingly sorted sequence of elements by
calling the function build_sort_list(). Elements are deleted from the
list by calling delete_sort_list(). The function clear_sort_list()
deletes all elements in the list. For detailed information about how
to call these functions, please see the function prototypes and
associated comments in the file SORTLIST.H. An example of how to use
the sorted list data type is provided in the file EXAMPLE.C.
The functions delete_sort_list(), apply_sort_list() and
build_sort_list() are recursive functions. The stack space complexity
for these functions is O(log n).
FILES
align.h - definitions related to address alignment.
sortlist.h - header file for code using sorted lists.
