Universities Press

Fundamentals of Data Structures in C

Horowitz;Sahni;Anderson-Freed

ISBN: 9788173716058 | Year: 2008 | Paperback | Pages: 664 | Language : English

Book Size: 158 x 240 mm | Territorial Rights: Restricted

Price: 850.00

This new edition provides a comprehensive and technically rigorous introduction to data structures such as arrays, stacks, queues, linked lists, trees and graphs and techniques such as sorting hashing that form the basis of all software. In addition, this text presents advanced or specialized data structures such as priority queues, efficient binary search trees, multiway search trees and digital search structures. The book now discusses topics such as weight biased leftist trees, pairing heaps, symmetric min–max heaps, interval heaps, top-down splay trees, B+ trees and suffix trees. Red-black trees have been made more accessible. The section on multiway tries has been significantly expanded and discusses several trie variations and their application to Internet packet forwarding.

Ellis Horowitz is Professor of Computer Science and Electrical Engineering at the University of Southern California. Dr Horowitz is the author of ten books and numerous journal articles and refereed conference proceedings.

Sartaj Sahni is a Distinguished Professor and Chair of Computer and Information Sciences and Engineering at the University of Florida. Dr Sahni has published over 300 research papers and written 15 textbooks.

Susan Anderson-Freed is a Professor of Computer Science at Illinois Wesleyan University. Her areas of expertise are database management system and web design and development.

CHAPTER 1 BASIC CONCEPTS
1.1 Overview: System Life Cycle
1.2 Pointers and Dynamic Memory Allocation
	1.2.1 Pointers 1.2.2 Dynamic Memory Allocation 1.2.3 Pointers Can Be Dangerous
1.3 Algorithm Specification
	1.3.1 Introduction 1.3.2 Recursive Algorithms
1.4 Data Abstraction
1.5 Performance Analysis
	1.5.1 Space Complexity 1.5.2 Time Complexity 1.5.3 Asymptotic Notation 1.5.4 Practical Complexities
1.6 Performance Measurement
	1.6.1 Clocking
	1.6.2 Generating Test Data
1.7 Referenes And Selected Readings

CHAPTER 2 ARRAYS AND STRUCTURES
2.1 Arrays
	2.1.1 The Abstract Data Type
	2.1.2 Arrays in C
2.2 Dynamically Allocated Arrays
	2.2.1 One-dimensional Arrays
	2.2.2 Two-dimensional Arrays
2.3 Structures and Unions
	2.3.1 Strctures
	2.3.2 Unions
	2.3.3 Internal Representation of Structures
	2.3.4 Self-referential Structures
2.4 Polynomials
	2.4.1 The Abstract Data Type
	2.4.2 Polynomial Representation
	2.4.3 Polynomial Addition
2.5 Sparse Matrices
	2.5.1 The Abstract Data Type
	2.5.2 Sparse Matrix Representation
	2.5.3 Transposing a Matrix
	2.5.4 Matrix Multiplication
2.6 Representation of Multidimensional Arrays
2.7 Strings
	2.7.1 The Abstract Data Type
	2.7.2 Strings in C
	2.7.3 Pattern Matching
2.8 References and Selected Readings
2.9 Additional Exercises

CHAPTER 3 STACKS AND QUEUES
3.1 Stacks
3.2 Stacks Using Dynamic Arrays
3.3 Queues
3.4 Circular Queues Using Dynamic Arrays
3.5 A Mazing Problem
3.6 Evaluation of Expressions
	3.6.1 Expressions
	3.6.2 Evaluating Postfix Expressions
3.7 Multiple Stacks and Queues
3.7 Additional Exercises

CHAPTER 4 LINKED LISTS
4.1 Singly Linked Lists and Chains
4.2 Representing Chains in C
4.3 Linked Stacks and Queues
4.4 Polynomials
	4.4.1 Polynomial Representation
	4.4.2 Adding Polynomials
	4.4.3 Erasing Polynomials
	4.4.4 Circular List Representation of Polynomials
	4.4.5 Summary
4.5 Additional List Operations
	4.5.1 Operations for Chains
	4.5.2 Operations for Circularly Linked Lists
4.6 Equivalence Classes
4.7 Sparse Matrices
	4.7.1 Sparse Matrix Representation
	4.7.2 Sparse Matrix Input
	4.7.3 Sparse Matrix Output
	4.7.4 Erasing a Sparse Matrix
4.8 Doubly Linked Lists

CHAPTER 5 TREES
5.1 Introduction
	5.1.1 Terminology
	5.1.2 Representation of Trees
5.2 Binary Trees
	5.2.1 The Abstract Data Type
	5.2.2 Properties of Binary Trees
	5.2.3 Binary Tree Representations
5.3 Binary Tree Traversals
	5.3.1 Inorder Traversal
	5.3.2 Preorder Traversal
	5.3.3Postorder Traversal
	5.3.4 Iterative Inorder Traversal
	5.3.5 Level-Order Traversal
	5.3.6 Traversal Without a Stack
5.4 Additional Binary Tree Operations
	5.4.1 Copying Binary Trees
	5.4.2 Testing Equality
	5.4.3 The Satisfiability Problem
5.5 Threaded Binary Trees
	5.5.1 Threads
	5.5.2 Inorder Traversal of a Threaded Binary Tree
	5.5.3 Inserting a Node into a Threaded Binary Tree
5.6 Heaps
	5.6.1 Priority Ques
	5.6.2 Definition of a Max Heap
	5.6.3 Insertion into a Max Heap
	5.6.4 Deletion from a Max Heap
5.7 Binary Search Trees
	5.7.1 Definition
	5.7.2 Searching a Binary Search Tree
	5.7.3 Insertion into a Binary Search Tree
	5.7.4 Deletion from a Binary Search Tree
	5.7.5 Joining and Splitting Binary Search Trees
	5.7.6 Height of a Binary Search Tree
5.8 Selection Trees
	5.8.1 Introduction
	5.8.2 Winner Trees
	5.8.3 Loser Trees
5.9 Forests
	5.9.1 Transforming a Forest into a Binary Tree
	5.9.2 Forest Traversals
5.10 Representation of Disjoint Sets
	5.10.1 Introduction
	5.10.2 Union and find Operations
	5.10.3 Application to Equivalence Classes
5.11 Counting Binary Trees
	5.11.1 Distinct Binary Trees
	5.11.2 Stack Permutations
	5.11.3 Matrix Multiplication
	5.11.4 Number of Distinct Binary Trees
5.12 References and Selected Readings

CHAPTER 6 GRAPHS
6.1 The Graph Abstract Data Type
	6.1.1 Introduction
	6.1.2 Definitions
	6.1.3 Graph Representations
6.2 Elementary Graph Operations
	6.2.1 Depth First Search
	6.2.2 Breadth First Search
	6.2.3 Connected Components
	6.2.4 Spanning Trees
	6.2.5 Biconnected Components
6.3 Minimum Cost Spanning Trees
	6.3.1 Kruskal’s Algorithm
	6.3.2 Prim’s Algorithm
	6.3.3 Sollin’s Algorithm
6.4 Shortest Paths and Transitive Closure
	6.4.1 Single Source/All Destination: Nonnegative Edge Costs
	6.4.2 Single Source/all Destination: General Weights
	6.4.3 All Pairs Shortest Paths
	6.4.4 Transitive Closure
6.5 Activity Networks
	6.5.1 Activity-on-Vertex (AOV) Networks
	6.5.2 Activity-on-Edge (AOE) Networks
6.6 References and Selected Readings
6.7 Additional Exercises

CHAPTER 7 SORTING
7.1 Motivation
7.2 Insertion Sort
7.3 Quick Sort
7.4 How Fast Can We Sort?
7.5 Merge Sort
	7.5.1 Merging
	7.5.2 Interative Merge Sort
	7.5.3 Recursive Merge Sort
7.6 Heap Sort
7.7 Sorting on Several Keys
7.8 List and Table Sorts
7.9 Summary of Internal Sorting
7.10 External Sorting
	7.10.1 Introduction
	7.10.2 k-way Merging
	7.10.3 Buffer Handling for Parallel Operation
	7.10.4 Run Generation
	7.10.5 Optimal Merging of Runs
7.11 References and Selected Readings

CHAPTER 8 HASHING
8.1 Introduction
8.2 Static Hashing
	8.2.1 Hash Tables
	8.2.2 Hash Functions
	8.2.3 Overflow Handling
	8.2.4 Theoretical Evaluation of Overflow Techniques
8.3 Dynamic Hashing
	8.3.1 Motivation for Dynamic Hashing
	8.3.2 Dynamic Hashing using Directories
	8.3.3 Directoryless Dynamic Hashing
8.4 Bloom Filters
	8.4.1 An Application--Differential Files
	8.4.2 Bloom Filter Design
8.5 References and selected Readings

CHAPTER 9 PRIORITY QUEUES
9.1 Single- and Double-Ended Priority Queues
9.2 Leftist Trees
	9.2.1 Height-Biased Leftist Trees
	9.2.2 Weight-Biased Leftist Trees
9.3 Binomial Heaps
	9.3.1 Cost Amortization
	9.3.2 Definition of Binomial Heaps
	9.3.3 Insertion into a Binomial Heap
	9.3.4 Melding Two Binomial Heaps
	9.3.5 Deletion of Min Element
	9.3.6 Analysis
9.4 Fibonacci Heaps
	9.4.1 Definition
	9.4.2 Deletion from an f-heap
	9.4.3 Decrease Key
	9.4.4 Cascading Cut
	9.4.5 Analysis
	9.4.6 Application to The Shortest Paths Problem
9.5 Pairing Heaps
	9.5.1 Definition
	9.5.2 Meld and Insert
	9.5.3 Decrease Key
	9.5.4 Delete Min
	9.5.5 Arbitrary Delete
	9.5.6 Implementation Considerations
	9.5.7 Complexity
9.6 Symmetric Min-Max Heaps
	9.6.1 Definition and Properties
	9.6.2 SMMH Representation
	9.6.3 Inserting into an SMMH
	9.6.4 Deleting from an SMMH
9.7 Interval Heaps
	9.7.1 Definition and Properties
	9.7.2 Inserting into an Interval Heap
	9.7.3 Deleting the Min Element
	9.7.4 Initializing an Interval Heap
	9.7.5 Complexity of Interval Heap Operations
	9.7.6 The Complementary Range Search Problem
9.8 References and Selected Readings

CHAPTER 10 EFFICIENT BINARY SEARCH TREES
10.1 Optimal Binary Search Trees
10.2 AVL Trees
10.3 Red-Black Trees
	10.3.1 Definition
	10.3.2 Representation of a Red-Black Tree
	10.3.3 Searching a Red-Black Tree
	10.3.4 Inserting to a Red-Black Tree
	10.3.5 Deletion from a Red-Black Tree
	10.3.6 Joining Red-Black Trees
	10.3.7 Splitting a Red-Black Tree
10.4 Splay Trees
	10.4.1 Bottom-Up Splay Trees
	10.4.2 Top-Down Splay Trees
10.5 References and Selected Readings

CHAPTER 11 MULTIWAY SEARCH TREES
11.1 m-way Search Trees
	11.1.1 Definition and Properties
	11.1.2 Searching an m-way Search Tree
11.2 B-Trees
	11.2.1 Definition and Properties
	11.2.2 Number of Elements in a B-Tree
	11.2.3 Insertion into a B-tree
	11.2.4 Deletion from a B-tree
11.3 B-Trees
	11.3.1 Definition
	11.3.2 Searching a B____________Tree
	11.3.3 Insertion into a B____________Tree
	11.3.4 Deletion from a B____________Tree
11.4 References and Selected Readings

CHAPTER 12 DIGITAL SEARCH STRUCTURES
12.1 Digital Search Trees
	12.1.1 Definition
	12.1.2 Search, Insert and Delete
12.2 Binary Tries and Patricia
	12.2.1 Binary Tries
	12.2.2 Compressed Binary Tries
	12.2.3 Patricia
12.3 Multiway Tries
	12.3.1 Definition
	12.3.2 Searching a Trie
	12.3.3 Sampling Strategies
	12.3.4 Insertion into a Trie
	12.3.5 Deletion from a Trie
	12.3.6 Keys with Different Length
	12.3.7 Height of a Trie
	12.3.8 Space Required and Alternative Node Structures
	12.3.9 Prefix Search and Applications
	12.3.10 Compressed Tries
	12.3.11 Compressed Tries with Skip Fields
	12.3.12 Compressed Tries with Labeled Edges
	12.3.13 Space Required by a Compressed Trie
12.4 Suffix Trees
	12.4.1 Have you Seen this String?
	12.4.2 The Suffix Tree Data Structure
	12.4.3 Let’s Find That Substring (Searching a Suffix Tree)
	12.4.4 Other Nifty Things You Can Do with a Suffix Tree
12.5 Tries and Internet Packet Forwarding
	12.5.1 IP Routing
	12.5.2 I-Bit Tries
	12.5.3 Fixed-Stride Tries
	12.5.4 Variable-Stride Tries
12.6 References and Selected Readings

Resources

https://www.universitiespress.com/hrwitzsahniandrsn/fdsc?isbn=9788173716058