It looks like you're offline.

An edition of Fundamentals of data structures in C (2008)

Fundamentals of data structures in C

2nd ed.

by Ellis Horowitz

★★★★★ 5.0 (1 rating)
9 Want to read
1 Currently reading
2 Have read

Cover of: Fundamentals of data structures in C by Ellis Horowitz, Ellis Horowitz

Preview

Borrow

My Reading Lists:

Use this Work

Create a new list

★★★★★ 5.0 (1 rating)
9 Want to read
1 Currently reading
2 Have read

Check nearby libraries

WorldCat

Buy this book

Last edited by ImportBot

October 28, 2021 | History

Edit

An edition of Fundamentals of data structures in C (2008)

Fundamentals of data structures in C

2nd ed.

by Ellis Horowitz

★★★★★ 5.0 (1 rating)
9 Want to read
1 Currently reading
2 Have read

The classic data structure textbook 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, it presents advanced of 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 several trie variations and their application to Interner packet forwarding have been disused.

Publish Date

2008

Publisher

University Press

Language

English

Pages

617

Check nearby libraries

WorldCat

Buy this book

Previews available in: English

Edition	Availability
1 Fundamentals of data structures in C 2008, University Press in English - 2nd ed. 8173716056 9788173716058	aaaa Borrow Listen Locate

Add another edition?

Book Details

Table of Contents

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. References and Selected Readings

Chapter 2. Arrays and Structures

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. Structures

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.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.2. Stacks Using Dynamic Arrays

3.4. Circular Queues Using Dynamic Arrays

3.5. Amazing Problem

3.6. Evaluation of Expressions

3.6.1. Expressions

3.6.2. Evaluating Postfix Expressions

3.6.3. Infix to Postfix

3.7. Multiple Stacks and Queues

3.8. 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.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.3. Postorder 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.2. Inorder Traversal of a Threaded Binary Tree

5.5.3. Inserting a Node into a Threaded Binary Tree

5.6.1. Priority Queues

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.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.2. Iterative Merge Sort

7.5.3. Recursive Merge 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 into 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.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.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. 1-Bit Tries

12.5.3. Fixed-Stride Tries

12.5.4. Variable-Stride Tries

12.6. References and Selected Readings

Edition Notes

Includes bibliographical references and index.

Published in: Hyderabad

Classifications

Dewey Decimal Class: 001.6424

The Physical Object

Pagination: xvii, 617 pages
Number of pages: 617

Edition Identifiers

Open Library: OL35367221M
Internet Archive: fundamentalsofda0002edhoro_l1t6
ISBN 10: 8173716056
ISBN 13: 9788173716058
OCLC/WorldCat: 880367630
Amazon ID (ASIN): B00D52P708

Work Identifiers

Work ID: OL26212173W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

History

Created October 28, 2021
1 revision

Download catalog record: RDF / JSON

October 28, 2021

Created by ImportBot

import new book