Data structures with C / Seymour Lipschutz

1. INTRODUCTION AND OVERVIEW
1.1 Introduction 1.1
1.2 Basic Terminology.^iementary Data Organization 1.1
1.3 Data Structures 1.3
1.4 Data Structure Operations 1.9
1.5 Abstract Data Types (ADT) 1.10
1.6 Algorithms: Complexity, Time-Space Tradeoff 1.12
Solved Problems 1.14
Multiple Choice Questions 1.20
Answers to Multiple Choice Questions 1.20
2. PRELIMINARIES
2.1 Introduction 2.1
2.2 Mathematical Notations and Functions 2.2
2.3 AigoritKhiic Notations 2.6
2.4 Control Structures 2.9
2.5 Complexity of Algorithms 2.15
2.6 Other Asymptotic Notations for Complexity of Algorithms Q, 0, O 2.19
2.7 Subalgorithms 2.20
2.8 Variables, Data Types 2.22
Solved Problems 2.25
Supplementary Problems 2.35
Programming Problems 2.36
Multiple Choice Questions 2.37
Answers to Multiple Choice Questions 2.37
3. STRING PROCESSING
3.1 Introduction 3.1
3.2 Basic Terminology 3.1
3.3 Storing Strings 3.2
3.4 Character Data Type 3.6
3.5 Strings as ADT 3.7
3.6 String Operations 3.8
3.7 Word/Text Processing 3.13
3.8 Pattern Matching Algorithms 3.20
Solved Problems 3.28
Siipplenientiiiy Problems 3.39
Programming Problems 3.40
Multiple Choice Questions 3.41
Answers to Multiple Choice Questions 3.42
4. ARRAYS, RECORDS AND POINTERS .
4.1 Introduction 4.1
4.2 Linear Arrays 4.2 .
4.3 Arrays as ADT 4.4
4.4 Representation of Linear Arrays in Memory 4.6
4.5 Traversing Linear Arrays 4.8
4.6 Inserting and Deleting 4./0
4.7 Sorting; Bubble Sort 4.15
4.8 Searching; Linear Search 4.J9
4.9 Binary Search 4.22
4.10 Multidimensional Arrays 4.27
4.11 Representation of Polynomials Using Arrays 4.36
4.12 Pointers; Pointer Arrays
4.13 Dynamic Memory Management
4.14 Records; Record Structures
4.15 Representation of Records in Memory; Paralfel Arrays 4.52
4.16 Matrices' 4.54, U -i.
4.17 Sparse Matrices 4.60 \ Z
Solved Problems 4.65 .-tH iii.)
Supplementary Problems 4.80
Progran'ming Problems 4.81
^ Mi{ltiple Choice Questions 4.85
Answers to Multiple Choice Questions 4.85 i
5. LINKED LISTS
5.1 Introduction 5.1 ?
5.2 Linked Lists 5.2
5.3 Representation of Linked Lists in Memory 5.4 .
5.4 ^Traversing a Linked List 5.8
5.5 Searching a Linked List 5.12
5.6 Memory Allocation; Garbage Collection 5.17
5.7 Insertion into a Linked List 5.22
5.8 Deletion from a Linked List 5.32
5.9 Header Linked Lists 5.38
5.10 Circularly Linked Lists 5.47 • i ,
5.11 Two-way Lists (or Doubly Linked Lists) 5.52
5.12 Josephus Problem and its Solution 5.63
5.13 Buddy Systems 5.65
Solved Problems 5.6)7
Supplementary Problems 5.76
Programming Problems 5.80
. ''jT- I '"A I
Multiple Choice Questions 5.82
Answers to Multiple Choice Questions 5.83
6. STACKS, QUEUES, RECURSION
6.1 Introduction 6.1
6.2 Stacks 6.2
6.3 Array Representation of Stacks 6.4
6.4 Linked Representation of Stacks 6.8
6.5 Stack as ADT 6.11
6.6 Arithmetic Expressions; Polish Notation 6.15
6.7 Application of Stacks 6.25
6.8 Recursion 6.33
6.9 Towers of Hanoi 6.39
6.10 Implementation of Recursive Procedures by Stacks 6.44
6.11 Queues 6.50
6.12 Linked Representation of Queues 6.57
6.13 Queue as ADT 6.64
6.14 Circular Queues 6.67
6.15 Deques 6.78
6.16 Priority Queues 6.79
6.17 Applications of Queues 6.92
Solved Problems 6.101
Supplementary Problems 6.119
Programming Problems 6.123
Multiple Choice Questions 6.124
Answers to Multiple Choice Questions 6.125
7. TREES
7.1 Introduction 7.1
7.2 Binary Trees 7.1
7.3 Representing Binary Trees in Memory 7.5
7.4 Traversing Binary Trees 7.9
7.5 Traversal Algorithms Using Stacks 7.12
7.6 Header Nodes; Threads 7.23
7.7 Threaded Binary Trees 7.27
7.8 Binary Search Trees 7.28
7.9 Searching and Inserting in Binary Search Trees 7.29
7.10 Deleting in a Binary Search Tree 7.38
7.11 Balanced Binary Trees 7.49
7.12 AVL Search TREes 7.50
7.13 Inseftion in an AVL Search Tree 7.51
7.14 Deletion in an AVL Search Tree 7.57
7.15 m-way Search Trees 7.61
7.16. Searching, Insertion and Deletion in an m-way Search Tree 7.63
7.17 B-Trees 7.66
7.18 Searching, Insertion and Deletion in a B-tree 7.67
7.19 B+-Trees 7.7i
1.2Q Red-Black Trees 7.78
7.21 Heap; Heap.sort 7.90
7.22 Path Lengths; Huffman's Algorithm 7.103
7.23 General Trees 7.109
7.24 Applications of Trees 7.112
Solved Problems 7.114
Supplementary Problems 7.13Z'
Programming Problems 7.139
Multiple Choice Questions 7.142
Answers to Multiple Choice Questions 7.143
8. GRAPHS AND THEIR APPLICATIONS
8.1 Introduction 8.1
8.2 Graph Theory Terminology 8.1
8.3 Sequential Representation of Graphs; Adjacency Matrix; Path Matrix 8 5
8.4 Warshall's Algorithm; Shortest Paths 8.9
8.5 Linked Representation of a Graph 8.17
8.6 Operations on Graphs 8.20
8.7 Traversing a Graph 8.31
8.8 Posets; Topological Sorting 8.40
8.9 Spanning Trees 8.47
Solved Problems 8.59
Supplementary Problems 8.71
Programming Problems 8.74 .
Multiple Choice Questions 8.76
Answers to Multiple Choice Questions 8.77
9. SORTING AND SEARCHING
9.1 Introduction 9.1
9.2 Sorting 9.1
9.3 Insertion Sort 9.6
9.4 Selection Sort 9.10
9.5 Merging 9.14
9.6 Merge-Sort 9.19
9.7 Shell Sort 9.31 ^
9.8 Radix Sort 9.34
9 9 Searching and Data Modification 9.38
9.10 Hashing 9.41
Solved Problems 9.53
Supplementaiy Problems 9.54
Programming Problems 9.55
Multiple Choice Questions 9.55
Answers to Multiple Choice Questions 9.56
Index