Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition) / Edition 2 by Clifford A. Shaffer | 9780130284464 | Hardcover | Barnes & Noble
Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition) / Edition 2

Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition) / Edition 2

by Clifford A. Shaffer
     
 

ISBN-10: 0130284467

ISBN-13: 9780130284464

Pub. Date: 09/06/2000

Publisher: Prentice Hall

This practical text contains fairly “traditional” coverage of data structures with a clear and complete use of algorithm analysis, and some emphasis on file processing techniques as relevant to modern programmers. It fully integrates OO programming with these topics, as part of the detailed presentation of OO programming itself.

Chapter topics include

Overview

This practical text contains fairly “traditional” coverage of data structures with a clear and complete use of algorithm analysis, and some emphasis on file processing techniques as relevant to modern programmers. It fully integrates OO programming with these topics, as part of the detailed presentation of OO programming itself.

Chapter topics include lists, stacks, and queues; binary and general trees; graphs; file processing and external sorting; searching; indexing; and limits to computation.

For programmers who need a good reference on data structures.

Product Details

ISBN-13:
9780130284464
Publisher:
Prentice Hall
Publication date:
09/06/2000
Edition description:
REV
Pages:
512
Product dimensions:
7.30(w) x 9.46(h) x 1.27(d)

Table of Contents

(NOTE: Each chapter concludes with Further Readings, Exercises, and/or Projects.)

I. PRELIMINARIES.

1. Data Structures and Algorithms.

A Philosophy of Data Structures. Abstract Data Types and Data Structures. Problems, Algorithms, and Programs.

2. Mathematical Preliminaries.

Sets and Relations. Miscellaneous Notation. Logarithms. Recursion. Summations and Recurrences. Mathematical Proof Techniques. Estimating.

3. Algorithm Analysis.

Introduction. Best, Worst, and Average Cases. A Faster Computer, or a Faster Algorithm? Asymptotic Analysis. Calculating the Running Time of a Program. Analyzing Problems. Common Misunderstandings. Multiple Parameters. Space Bounds. Some Practical Considerations.

II. FUNDAMENTAL DATA STRUCTURES.

4. Lists, Stacks, and Queues.

Lists. The Dictionary ADT. Stacks. Queues.

5. Binary Trees.

Definitions and Properties. Binary Tree Traversals. Binary Tree Node Implementations. Binary Search Trees. Heaps and Priority Queues. Huffman Coding Trees.

6. Non-Binary Trees.

General Tree Definitions and Terminology. The Parent Pointer Implementation. General Tree Implementations. K -ary Trees. Sequential Tree Implementations.

III. SORTING AND SEARCHING.

7. Internal Sorting.

Sorting Terminology and Notation. Three …Q(n2) Sorting Algorithms. Shellsort. Quicksort. Mergesort. Heapsort. Binsort and Radix Sort. An Empirical Comparison of Sorting Algorithms. Lower Bounds for Sorting.

8. File Processing and External Sorting.

Primary versus Secondary Storage. Disk Drives. Buffers and Buffer Pools. The Programmer's View of Files. External Sorting. Simple Approaches to External Sorting. Replacement Selection. Multiway Merging.

9. Searching.

Searching Sorted Arrays. Self-Organizing Lists. Searching in Sets. Hashing.

10. Indexing.

Linear Indexing. ISAM. Tree Indexing. 2-3 Trees. B-Trees.

IV. APPLICATIONS AND ADVANCED TOPICS.

11. Graphs.

Terminology and Representations. Graph Implementations. Graph Traversals. Shortest-Paths Problems. Minimum-Cost Spanning Trees.

12. Lists and Arrays Revisited.

Skip Lists. Multilists. Matrix Representations. Memory Management.

13. Advanced Tree Structures.

Tries. Balanced Trees. Spatial Data Structures.

14. Analysis Techniques.

Summation Techniques. Recurrence Relations. Amortized Analysis.

15. Limits to Computation.

Reductions. Hard Problems. Impossible Problems.

V. APPENDIX.

Utility Functions.

Bibliography.

Index.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >