- ホーム
- > 洋書
- > 英文書
- > Computer / General
Full Description
Data Structures using Python provides an introduction to design, analysis, and implementation of data structures using the powerful language Python. This book is designed for a first course on the subject. It is written for the undergraduate engineering students of Computer Science, Information Technology and allied disciplines.
The book begins with an overview of the concept, need, nomenclature followed by discussion of Arrays, Stacks, Queues, Double Ended Queues, Linked List - all under a chapter on Linear Data Structures. This is followed by a chapter on Non-linear Data Structures where Heap, Hash Table, Trie, and Disjoint Sets are discussed. Trees, though a non-linear data structure, is discussed as a separate chapter to emphasize upon its importance. The last few chapters of the book discusses Graphs, Searching, and Sorting finally ending with an appendix on Python built-in class functions.
Contents
1. Data Structures-Introduction
1.1 Introduction
1.2 What is a Data Structure?
1.3 Why Do We Need Data Structures?
1.4 How to Study/Prepare Data Structures? Why Does It Appear Difficult?
1.5 Different Types of Data Structures
1.6 How to Select a Data Structure?
1.7 How are Data Structures Implemented?
1.8 Real-Life Scenarios for Data Structures
1.6 Difference Between Data Structures and Database Management Systems
2. Abstract Data Type and Analysis
2.1 Introduction- Abstract Data Type
2.2 Complexity
2.2.1 Time Complexity
2.2.2 Space Complexity
2.3 Asymptotic Notations
2.3.1 Big-O
2.3.2 Big-Omega
2.3.3 Big-Theta
2.3.4 Small-O
2.3.5 Small-Omega
2.4 Recursion
2.4.1 How does Recursion Work?
2.4.2 Inefficient Recursion
2.4.3 Tail Call Elimination
2.4.4 Analysis of Recursive Functions
2.5 Applications of Recursion
3. Linear Data Structures
3.1 Arrays-Introduction
3.2 Declaration of Arrays
3.3 Implementation
3.3.1 Insertion
3.3.2 Deletion
3.3.3 Merging
3.3.4 Some More Operations
3.3.5 Complexity Analysis
3.4 Applications
3.5 Python Sequences
4. Continuous Memory Based Linear Data Structures
4.1 Introduction
4.2 Stack
4.2.1 Working-Push Operation
4.2.2 Working-Pop Operation
4.2.3 Working-Top Operation
4.3 Implementation of Stack Using Pointers
4.4 Complex Operations
4.4.1 Searching
4.4.2 Sorting
4.4.3 Complexity Analysis
4.5 Applications of Stacks
4.5.1 Application: Infix-to-Postfix Conversion
4.5.2 Application: Evaluation of Prefix Expression
4.6 Queues
4.7 ingle-Ended Queues
4.7.1 Working-Enqueue Operation
4.7.2 Working-Dequeue Operation
4.7.3 Working-Front Operation
4.7.4 Implementation of Single-Ended
Queues using Lists
4.7.5 Complex Operations
4.7.6 Circular Array-based Implementation of Single-ended Queues
4.8 Double-Ended Queues
4.8.1 Working: Push_Front Operation
4.8.2 Working: Push_Back Operation
4.8.3 Working: Pop-Front Operation
4.8.4 Working: Pop_Back Operation
4.8.5 Working: Front Operation
4.8.6 Working: Rear Operation
4.8.7 Implementation of a Deque
4.8.8 Complex Operations
4.8.9 Complexity Analysis
4.9 Priority Queues
4.9.1 Implementation of Priority Queues
4.1 Applications of Queues
4.10.1 Application: Check if a Given String is a Palindrome
5. Pointer-Based Linear Data Structures
5.1 Introduction to Linked Lists
5.2 Singly Linked Lists
5.2.1 Working-Insert Node Operation
5.2.2 Working-Delete Node Operation
5.2.3 Working-ValueAt Operation
5.2.4 Implementation of Singly Linked Lists
5.2.5 Complex Operations-Searching
5.2.6 Complex Operations-Sorting
5.2.7 Complexity Analysis
5.3 Doubly Linked Lists
5.3.1 Working-Insert Node Operation
5.3.2 Working-Delete Node Operation
5.3.3 Working-ValueAt Operation
5.3.4 Implementation of Doubly Linked Lists
5.3.5 Complexity Analysis
5.4 Circular Linked Lists
5.4.1 Working-Insert Node Operation
5.4.3 Implementation of Circular Linked Lists
5.4.4 Complexity Analysis
5.5 Applications of Linked Lists
6. Pointer Based Hierarchical Data Structures
6.1 Introduction-Non-Linear Data Structures
6.2 TREES
6.2.1 Definitions
6.3 Binary Trees
6.3.1 Types of Binary Trees
6.4 Implementation of Binary Trees
6.4.1 Pointer-based Implementation
6.4.2 Array-based Implementation
6.4.3 Linked List-based Implementation
6.5 Traversal
6.5.1 In-order Traversal
6.5.2 Pre-order Traversal
6.5.3 Post-order Traversal
6.5.4 Level-ordered Traversal
6.6 Basic Operations
6.6.1 Inserting a Node
6.6.2 Deleting a Node
6.7 Threaded Binary Trees
6.8 Applications of Trees
7. Search Trees
7.1 Introduction
7.2 Binary Search Trees
7.2.1 Operation-Search Value
7.2.2 Operation-Insert a Node
7.2.3 Operation-Delete a Node
7.2.4 Implementation of Binary Search Trees
7.2.5 Complexity Analysis
7.3 Avl Trees
7.3.1 Operation-Search Value
7.3.2 Operation- Insert a Node
7.3.3 Operation-Deleting a Node
7.3.4 Implementation of AVL Trees
7.3.5 Complexity Analysis
7.4 Red-Black Trees
7.4.1 Operation-Insertion
7.4.2 Operation-Delete a Node
7.4.3 Implementation of Red-Black Trees
7.4.4 Complexity Analysis
7.5 Splay Trees
7.5.1 Operation-'Search a Value' or 'Splay a Value'
7.5.2 Operation-Insert a Node
7.5.3 Operation-Delete a Node
7.5.4 Implementation of Splay Trees
7.5.5 Complexity Analysis
7.6 B-TREES
7.6.1 In-order Traversal
7.6.2 Operation-Search a Node
7.6.3 Operation-Insert a Node
7.6.4 Operation-Delete a Node
7.6.5 Implementation of B-Trees
7.6.6 Complexity Analysis
7.7 Applications of Search Trees
8. Priority Queues and Heaps
8.1 Introduction-Heap
8.2 Binary Heaps
8.2.1 Operation-Insertion
8.2.2 Operation-Deletion
8.2.3 Implementation of Max Heap
8.2.4 Complexity Analysis
8.3 Leftist Heaps
8.3.1 Operation-Merging
8.3.2 Operation-Insertion
8.3.3 Operation-Deletion
8.3.4 Implementation of Leftist Heaps
8.3.5 Complexity Analysis
8.4 Priority Queues Using Heaps
8.5 Applications of Heaps
9. Other Non-Linear Data Structures
9.1 Introduction-Non-Linear, Non-Hierarchical Data Structures
9.2 Trie
9.2.1 Insertion of a Key
9.2.2 Searching a Key
9.2.3 Implementation
9.2.4 Complexity Analysis
9.2.5 Applications of Trie
9.3 Dictionary
9.3.1 Inserting a Key and its Value
9.3.2 Deleting a Key along with Value
9.3.3 Merging Dictionaries
9.3.4 Handling Tabular Data
9.3.5 Implementation
9.3.6 Complexity
9.3.7 Applications of Dictionary
9.4 Hash Table
9.4.1 Linear Probing
9.4.2 Chaining the Elements
9.4.3 Implementation
9.4.4 Complexity
9.4.5 Applications of Hash Tables
9.5 Sets
9.5.1 Operation-Insertion of an Element
9.5.2 Operation-Removal of Elements
9.5.3 Binary Set Operations
9.5.4 Other Utility Functions
9.5.5 Implementation
9.5.6 Complexity Analysis
9.5.7 Applications of Set
9.5.8 Variants of Set Data Structure
9.5 Counter/Multisets
9.5.1 Accessing
9.5.2 Binary Operations on Counters
10. Memory Management
10.1 Introduction-Memory Management
10.2 Data Structures in Memory Management
10.3 B+ Trees
10.3.1 Working
10.3 Memory Hierarchy and Caching
11. Graphs
11.1 Graph-Introduction
11.2 Components of a Graph
11.4 Graph Representation
11.4.1 Linked List Based Representation
11.4.2 Matrix Based Representation
11.2.3 Pointer Based Representation
11.2.4 Performance Comparison of Graph Representation
11.3 Types of Graph
11.4 Working
11.4.1 Insertion of a node
11.4.2 Insertion of an edge
11.4.3 Deletion of an edge
11.4.4 Deletion of a node
11.5 Traversal
11.5.1 Depth First Search
11.5.2 Breadth First Search
11.7 Implementation of Graph
11.7.1 Adjacency List Based Representation
11.7.2 Adjacency Matrix Based Representation
11.7.3 Incidence Matrix Based Representation
11.8 Complexity Analysis
11.9 Topological Sorting
11.9.1 Implementation
11.9.2 Complexity Analysis
11.1 Spanning Tree
11.10.1 Kruskal Algorithm
11.10.2 Prim's Algorithm
11.11 Shortest Distance
11.11.1 Dijkstra's Algorithm
11.11.2 Floyd-Warshall Algorithm
11.12 Graph Connectivity
11.12 Applications Of Graph
12. Sorting
12.1 Introduction to Sorting
12.2 Importance of Sorting Algorithms
12.3 Exchange Sort
12.3.1 Bubble Sort
12.4 Selection Sort
12.4.1 Straight Selection Sort
12.4.2 Heap Sort
12.5 Insertion Sort
12.5.1 Simple Insertion Sort
12.5.2 Shell Sort
12.6 Divide and Conquer
12.6.1 Merge Sort
12.6.2 Quick Sort
12.7 Distributed Sort
12.7.1 Bucket Sort
12.7.2 Counting Sort
12.7.3 Radix Sort
12.8 Comparison of Sorts
13. Searching
13.1 Introduction-What is Searching?
13.2 Linear Search
13.2.1 Working
13.2.2 Implementation
13.3.3 Complexity Analysis
13.3 Binary Search
13.3.1 Working
13.3.2 Implementation
13.3.3 Complexity Analysis
13.4 Tree-Based Search
13.5 Hashing
13.5.1 Working
13.5.2 Problem of Collision
13.5.4 Implementation
13.5.5 Complexity Analysis
13.6 Case Studies of Searching Techniques
ANNEXURE 1 - Python classes and built in Functions
