26-07-2012, 12:00 PM
Handbook of DATA STRUCTURES and APPLICATIONS
Handbook of data structures and applications.pdf (Size: 10.77 MB / Downloads: 277)
Preface
In the late sixties, Donald Knuth, winner of the 1974 Turing Award, published his landmark
book The Art of Computer Programming: Fundamental Algorithms. This book brought together
a body of knowledge that defined the data structures area. The term data structure,
itself, was defined in this book to be A table of data including structural relationships.
Niklaus Wirth, the inventor of the Pascal language and winner of the 1984 Turing award,
stated that “Algorithms + Data Structures = Programs”. The importance of algorithms
and data structures has been recognized by the community and consequently, every undergraduate
Computer Science curriculum has classes on data structures and algorithms. Both
of these related areas have seen tremendous advances in the decades since the appearance
of the books by Knuth and Wirth. Although there are several advanced and specialized
texts and handbooks on algorithms (and related data structures), there is, to the best of
our knowledge, no text or handbook that focuses exclusively on the wide variety of data
structures that have been reported in the literature. The goal of this handbook is to provide
a comprehensive survey of data structures of different types that are in existence today.
To this end, we have subdivided this handbook into seven parts, each of which addresses
a different facet of data structures. Although
this material is covered in all standard data structures texts, it was included to make the
handbook self-contained and in recognition of the fact that there are many practitioners and
theoretical in nature: they discuss the data structures, their operations and their complexities.
use of data structures in real programs. Many of the data structures discussed in previous
parts are very intricate and take some effort to program. The development of data structure
libraries and visualization tools by skilled programmers are of critical importance in reducing
the gap between theory and practice.
structures.
of applications is discussed. Some of the data structures discussed here have been invented
solely in the context of these applications and are not well-known to the broader community.
Some of the applications discussed include Internet Routing, Web Search Engines,
Databases, Data Mining, Scientific Computing, Geographical Information Systems, Computational
Geometry, Computational Biology, VLSI Floorplanning and Layout, Computer
Graphics and Image Processing.
For data structure and algorithm researchers, we hope that the handbook will suggest
new ideas for research in data structures and for an appreciation of the application contexts
in which data structures are deployed. For the practitioner who is devising an algorithm,
we hope that the handbook will lead to insights in organizing data that make it possible
to solve the algorithmic problem more cleanly and efficiently. For researchers in specific
application areas, we hope that they will gain some insight from the ways other areas have
handled their data structuring problems.
Although we have attempted to make the handbook as complete as possible, it is impossible
to undertake a task of this magnitude without some omissions. For this, we apologize
in advance and encourage readers to contact us with information about significant data
© 2005 by Chapman & Hall/CRC
Part I is a review of introductory material.
programmers who may not have had a formal education in Computer Science. Parts II, III,
and IV discuss Priority Queues, Dictionary Structures, and Multidimensional structures,
respectively. These are all well-known classes of data structures. Part V is a catch-all used
Part VI addresses mechanisms and tools that have been developed to facilitate the
Finally, Part VII examines applications of data
for well-known data structures that eluded easy classification. Parts I through V are largely
The deployment of many data structures from Parts I through V in a variety
structures or applications that do not appear here. These could be included in future editions
of this handbook. We would like to thank the excellent team of authors, who are at
the forefront of research in data structures, that have contributed to this handbook. The
handbook would not have been possible without their painstaking efforts. We are extremely
saddened by the untimely demise of a prominent data structures researcher, Professor G´ısli
R. Hjaltason, who was to write a chapter for this handbook. He will be missed greatly by
the Computer Science community. Finally, we would like to thank our families for their
support during the development of the handbook.
Dinesh P. Mehta
Sartaj Sahni
© 2005 by Chapman & Hall/CRC
About the Editors
Dinesh P. Mehta received the B.Tech. degree in computer science and engineering from
the Indian Institute of Technology, Bombay, in 1987, the M.S. degree in computer science
from the University of Minnesota in 1990, and the Ph.D. degree in computer science from
the University of Florida in 1992. He was on the faculty at the University of Tennessee
Space Institute from 1992-2000, where he received the Vice President’s Award for Teaching
Excellence in 1997. He was a Visiting Professor at Intel’s Strategic CAD Labs in 1996 and
1997. He has been an Associate Professor in the Mathematical and Computer Sciences
department at the Colorado School of Mines since 2000. Dr. Mehta is a co-author of the
text Fundamentals of Data Structures in C ++. His publications and research interests are
in VLSI design automation, parallel computing, and applied algorithms and data structures.
His data structures-related research has involved the development or application of diverse
data structures such as directed acyclic word graphs (DAWGs) for strings, corner stitching
for VLSI layout, the Q-sequence floorplan representation, binary decision trees, Voronoi
diagrams and TPR trees for indexing moving points. Dr. Mehta is currently an Associate
Editor of the IEEE Transactions on Circuits and Systems-I.
Sartaj Sahni
Sartaj Sahni is a Distinguished Professor and Chair of Computer and Information Sciences
and Engineering at the University of Florida. He is also a member of the European Academy
of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and
a Distinguished Alumnus of the Indian Institute of Technology, Kanpur. Dr. Sahni is the
recipient of the 1997 IEEE Computer Society Taylor L. Booth Education Award, the 2003
IEEE Computer Society W. Wallace McDowell Award and the 2003 ACM Karl Karlstrom
Outstanding Educator Award. Dr. Sahni received his B.Tech. (Electrical Engineering)
degree from the Indian Institute of Technology, Kanpur, and the M.S. and Ph.D. degrees
in Computer Science from Cornell University. Dr. Sahni has published over two hundred
and fifty research papers and written 15 texts. His research publications are on the design
and analysis of efficient algorithms, parallel computing, interconnection networks, design
automation, and medical algorithms.
Dr. Sahni is a co-editor-in-chief of the Journal of Parallel and Distributed Computing,
a managing editor of the International Journal of Foundations of Computer Science, and
a member of the editorial boards of Computer Systems: Science and Engineering, International
Journal of High Performance Computing and Networking, International Journal
of Distributed Sensor Networks and Parallel Processing Letters. He has served as program
committee chair, general chair, and been a keynote speaker at many conferences. Dr. Sahni
has served on several NSF and NIH panels and he has been involved as an external evaluator
of several Computer Science and Engineering departments.