Data Structures (SOS) (Revised 1st Edition) by Lipschutz, Seymour -- Read -- Imperial Library of Trantor

Index

Cover About the Authors Title page Copyright Dedication Contents Preface to the Adapted Edition Preface 1. INTRODUCTION AND OVERVIEW

1.1 Introduction 1.2 Basic Terminology; Elementary Data Organization 1.3 Data Structures 1.4 Data Structure Operations 1.5 Algorithms: Complexity, Time-Space Tradeoff Solved Problems

2. PRELIMINARIES

2.1 Introduction 2.2 Mathematical Notation and Functions 2.3 Algorithmic Notation 2.4 Control Structures 2.5 Complexity of Algorithms 2.6 Other Asymptotic Notations for Complexity of Algorithms Ω, θ, O 2.7 Subalgorithms 2.8 Variables, Data Types Solved Problems Supplementary Problems Programming Problems

3. STRING PROCESSING

3.1 Introduction 3.2 Basic Terminology 3.3 Storing Strings 3.4 Character Data Type 3.5 String Operations 3.6 Word Processing 3.7 Pattern Matching Algorithms Solved Problems Supplementary Problems Programming Problems

4. ARRAYS, RECORDS AND POINTERS

4.1 Introduction 4.2 Linear Arrays 4.3 Representation of Linear Arrays in Memory 4.4 Traversing Linear Arrays 4.5 Inserting and Deleting 4.6 Sorting; Bubble Sort 4.7 Searching; Linear Search 4.8 Binary Search 4.9 Multidimensional Arrays 4.10 Pointers; Pointer Arrays 4.11 Records; Record Structures 4.12 Representation of Records in Memory; Parallel Arrays 4.13 Matrices 4.14 Sparse Matrices Solved Problems Supplementary Problems Programming Problems

5. LINKED LISTS

5.1 Introduction 5.2 Linked Lists 5.3 Representation of Linked Lists in Memory 5.4 Traversing a Linked List 5.5 Searching a Linked List 5.6 Memory Allocation; Garbage Collection 5.7 Insertion into a Linked List 5.8 Deletion from a Linked List 5.9 Header Linked Lists 5.10 Two-way Lists Solved Problems Supplementary Problems Programming Problems

6. STACKS, QUEUES, RECURSION

6.1 Introduction 6.2 Stacks 6.3 Array Representation of Stacks 6.4 Linked Representation of Stacks 6.5 Arithmetic Expressions; Polish Notation 6.6 Quicksort, an Application of Stacks 6.7 Recursion 6.8 Towers of Hanoi 6.9 Implementation of Recursive Procedures by Stacks 6.10 Queues 6.11 Linked Representation of Queues 6.12 Deques 6.13 Priority Queues Solved Problems Supplementary Problems Programming Problems

7. TREES

7.1 Introduction 7.2 Binary Trees 7.3 Representing Binary Trees in Memory 7.4 Traversing Binary Trees 7.5 Traversal Algorithms using Stacks 7.6 Header Nodes; Threads 7.7 Binary Search Trees 7.8 Searching and Inserting in Binary Search Trees 7.9 Deleting in a Binary Search Tree 7.10 AVL Search Trees 7.11 Insertion in an AVL Search Tree 7.12 Deletion in an AVL Search Tree 7.13 m-way Search Trees 7.14 Searching, Insertion and Deletion in an m-way Search Tree 7.15 B Trees 7.16 Searching, Insertion and Deletion in a B-tree 7.17 Heap; Heapsort 7.18 Path Lengths; Huffman’s Algorithm 7.19 General Trees Solved Problems Supplementary Problems Programming Problems

8. GRAPHS AND THEIR APPLICATIONS

8.1 Introduction 8.2 Graph Theory Terminology 8.3 Sequential Representation of Graphs; Adjacency Matrix; Path Matrix 8.4 Warshall’s Algorithm; Shortest Paths 8.5 Linked Representation of a Graph 8.6 Operations on Graphs 8.7 Traversing a Graph 8.8 Posets; Topological Sorting 8.9 Spanning Tree Solved Problems Supplementary Problems Programming Problems

9. SORTING AND SEARCHING

9.1 Introduction 9.2 Sorting 9.3 Insertion Sort 9.4 Selection Sort 9.5 Merging 9.6 Merge-Sort 9.7 Radix Sort 9.8 Searching and Data Modification 9.9 Hashing Supplementary Problems

Appendix Index