Data Structures Using C : For BPUT Subject Code BE-2106

Cover
Contents
Preface
Acknowledgements
About the Author
Roadmap to the Syllabus
Chapter 1: Introduction to Data Structures
	1.1 Introduction
	1.2 Data and Information
	1.3 Overview of Data Structures
	1.4 Types of Data Structures
	1.5 Primitive and Non-primitive Data Structures and Operations
		1.5.1 Primitive Data Structures
		1.5.2 Non-primitive Data Structures
	1.6 Binary and Decimal Integers
		1.6.1 One’s Complement
		1.6.2 Two’s Complement
		1.6.3 Binary Coded Decimals
		1.6.4 Integers
		1.6.5 Real Numbers
		1.6.6 Character String
	1.7 Logical Information
	1.8 Storage of Information
	1.9 Hardware and Software
	1.10 Concept of Data Types
	1.11 Data Types in C
	1.12 Abstract Data Types
	1.13 Pointers
		1.13.1 Computed Address
		1.13.2 Pointer Addressing
	1.14 Structures in C
	1.15 Unions
	1.16 Algorithms
		1.16.1 Analysing Algorithm
		1.16.2 Rate of Growth
		1.16.3 Space Requirement
		1.16.4 Time Requirement
	Summary
	Exercises
Chapter 2: Data Structures: Arrays
	2.1 Introduction
		2.1.1 Array Declaration and Initialization
		2.1.2 Array Terminology
	2.2 Characterstics of Arrays
	2.3 One-dimensional Arrays
	2.4 Operation with Arrays
		2.4.1 Deletion
		2.4.2 Insertion
		2.4.3 Searching
		2.4.4 Merging
		2.4.5 Sorting
	2.5 Two-dimensional Arrays
		2.5.1 Insert Operation with Two-dimensional Array
		2.5.2 Delete Operation with Two-dimensional Array
	2.6 Three-or Multi-dimensional Arrays
	2.7 Strings
	2.8 Array of Structures
	2.9 Drawbacks of Linear Arrays
	2.10 Sparse Matrices and Dense Matrices
		2.10.1 Upper Triangular Matrices
		2.10.2 Lower Triangular Matrices
	2.11 Row-major Arrays
	2.12 Column-major Arrays
	2.13 Pointers and Arrays
	2.14 Pointers and Two-dimensional Arrays
	2.15 Array of Pointers
	2.16 Pointers and Strings
	Summary
	Exercises
Chapter 3: Recursion
	3.1 Introduction
		3.1.1 Function Prototypes
		3.1.2 Function Definition
		3.1.3 Function Call
		3.1.4 Actual and Formal Argument
		3.1.5 The Return Statement
	3.2 Types of Recursions
	3.3 Rules for Recursive Function
	3.4 Direct Recursion
	3.5 Indirect Recursion
	3.6 Recursion Versus Iteration
	3.7 The Towers of Hanoi
	3.8 Advantages and Disadvantages of Recursion
	3.9 Tail Recursion
	3.10 Efficiency of Recursion
	Summary
	Exercises
Chapter 4: Stacks
	4.1 Introduction
	4.2 Stack-related Terms
		4.2.1 Representation of Stack
	4.3 Stack Implementation
		4.3.1 Static Implementation
		4.3.2 Dynamic Implementation
	4.4 Operations on Stack
	4.5 Pointers and Stack
	4.6 Representation of Arithmetic Expressions
	Summary
	Exercises
Chapter 5: Queues
	5.1 Introduction
	5.2 Various Positions of Queues
	5.3 Queue Implementation
		5.3.1 Static Implementation
	5.4 Operations on Queues
		5.4.1 Insertion of Element
		5.4.2 Deletion of Element
	5.5 Disadvantages of Simple Queues
	5.6 Dynamic Implementation (Pointers)
	5.7 Insertion and Deletion Operation
	5.8 Types of Queues
		5.8.1 Circular Queue
		5.8.2 Double Ended Queues
		5.8.3 Priority Queues
	5.9 Applications of Queues
		5.9.1 Round Robin Algorithm
		5.9.2 Simulation
	5.10 Types of Systems
	Summary
	Exercises
Chapter 6: Linked List
	6.1 Introduction
	6.2 Linked List
	6.3 Illustration of Linked List for Storing a String
	6.4 Important Terms
		6.4.1 Static List Versus Linked List
		6.4.2 Types of Linked List
	6.5 Memory Allocation and De-allocation
	6.6 Operations on Linked Lists
	6.7 Singly Linked List
	6.8 Linked List with Header
		6.8.1 Traverse a List with Header
	6.9 Linked List Without Header
		6.9.1 Traverse a List Without Header
	6.10 Insertion in the Linked List
	6.11 Insertion of Node at Start
	6.12 Insertion of Node at End
	6.13 Insertion of Node at a Given Position
		6.13.1 Counting Nodes
		6.13.2 Deletion
	6.14 Representation of Stacks Using Linked Lists
	6.15 Representation of Queues Using Linked Lists
	6.16 Reversing the Singly Linked List
	6.17 Concatenation of Two Lists
	6.18 Splitting of a Linked List
	6.19 Circular Linked List
	6.20 Method for Detecting End
		6.20.1 Detecting End with Counter
		6.20.2 Detecting End with Pointer
		6.20.3 Insertion in Circular Linked List
		6.20.4 Deletion in Circular Linked List
	6.21 Doubly Linked List
		6.21.1 Insertion and Deletion with Doubly Linked List
		6.21.2 Advantages of Doubly Linked List
		6.21.3 Disadvantages of Doubly Linked List
	6.22 Circular Doubly Linked List
		6.22.1 Insertion and Deletion Operation
	6.23 Applications of Linked List
		6.23.1 Polynomial Manipulation
		6.23.2 Linked Dictionary
		6.23.3 Addition of Long Positive Integers
		6.23.4 Searching in a Linked List
		6.23.5 Sorting a Linked List
	Summary
	Exercises
Chapter 7: Storage Management
	7.1 Introduction
	7.2 Allocation Techniques
	7.3 Memory Representation
		7.3.1 Fixed Block Storage
		7.3.2 Variable Block Storage
	7.4 Boundary Tag System
	7.5 Storage Allocations
		7.5.1 First-fit Allocation
		7.5.2 Best-fit Storage Allocation
		7.5.3 Worst-fit Storage Allocation
		7.5.4 Next-fit Storage Allocation
		7.5.5 External Fragmentation
		7.5.6 Internal Fragmentation
	7.6 Storage Release
	7.7 Buddy System
	7.8 Binary Buddy System
	7.9 Compaction
		7.9.1 Memory (Storage) Allocation
		7.9.2 Storage Pools
	7.10 Garbage Collection
	Summary
	Exercises
Chapter 8: Applications of Stacks
	8.1 Introduction
	8.2 Infix, Prefix and Postfix Notations
	8.3 Evaluation of Postfix Expression
	8.4 Conversion of Expression from Infix to Postfix
	8.5 Reverse String
	8.6 Stack Frames
	8.7 Conversion of Number System
	8.8 Recursion
	8.9 Activation Record Organization
	8.10 Scope Rules
	8.11 Scope Rules Through Stack
	Summary
	Exercises
Chapter 9: Trees
	9.1 Introduction
	9.2 Basic Terms
	9.3 General Tree
	9.4 Binary Trees
	9.5 Complete Binary Tree
	9.6 Strictly Binary Tree
	9.7 Extended Binary Tree
	9.8 Binary Tree Representation
		9.8.1 Array Representation of Binary Tree
		9.8.2 Linked Representation of Binary Tree
	9.9 Operations on Binary Trees
	9.10 Traversal of a Binary Tree
		9.10.1 Inorder Traversal
		9.10.2 Preorder Traversal
		9.10.3 Postorder Traversal
		9.10.4 Creation of a Binary Tree from its Traversals
	9.11 Conversion of Expression into Postfix
	9.12 Binary Search Tree
		9.12.1 Searching an Element in Binary Search Tree
		9.12.2 Insertion of an Element in Binary Search Tree
		9.12.3 Traversing the Binary Search Tree
	9.13 Threaded Binary Tree
	9.14 B-Tree (Balanced Multi-way Tree)
		9.14.1 B-Tree Insertion
		9.14.2 B-Tree Deletion
	9.15 B-Tree of Order 5
	9.16 B+ Tree
	9.17 AVL Tree
		9.17.1 Balance Factor (BF)
		9.17.2 Characteristics of AVL Tree
	Summary
	Exercises
Chapter 10: Graphs
	10.1 Introduction
	10.2 Graphs
	10.3 Terminologies of Graph
	10.4 Graph Representation
		10.4.1 Adjacency List
	10.5 Traversal in Graph
	10.6 Spanning Trees
		10.6.1 Breadth First Search
		10.6.2 Depth First Search
		10.6.3 Indegree and Outdegree of Vertex
		10.6.4 Topological Sorting
		10.6.5 Path Matrix
		10.6.6 Transitive Relation
		10.6.7 Warshall’s Algorithm
	Summary
	Exercises
Chapter 11: Sorting
	11.1 Introduction
	11.2 Sorting
	11.3 Insertion Sort
	11.4 Selection Sort
	11.5 Bubble Sort
	11.6 Quick Sort
	11.7 Tree Sort
	11.8 Merge Sort
	11.9 Heap Sort
	11.10 Radix Sort
	11.11 Partition Exchange Sort
	Summary
	Exercises
Chapter 12: Searching
	12.1 Introduction
	12.2 Searching
	12.3 Linear (Sequential) Search
	12.4 Binary Search
	12.5 Hashing Method
	12.6 Hashing Function
	12.7 Division Method
	12.8 Mid-square Method
	12.9 Folding Method
	12.10 Length-dependent Method
	12.11 Multiplicative Hashing Function
	12.12 Digit Analysis Method
	Summary
	Exercises
Solved Question Papers
	Solutions