Graphical data structures and algorithms: using C language

This book is an introductory book that comprehensively talks about data structures and their algorithms. It strives to be concise, clear, rigorous, and easy to learn and master. The book starts with the basic concepts of data structures, including array structures, queues, stacks, tree structures, sorting, searching, etc.; then introduces commonly used algorithms, including divide-and-conquer, recursive, greedy, dynamic programming, iteration, enumeration, backtracking, etc. Each classic algorithm provides a complete example program written in C programming language; finally, a large number of exercises are arranged at the end of each chapter. These questions include examples of various exams. It is hoped that readers can flexibly apply the various knowledge they have learned. This book is illustrated with pictures and texts, with concise and clear narration, rich examples, and strong operability. It is a popular textbook or self-study reference book on data structures for non-information professionals or students who have certain programming skills and want to improve the \"depth\" of programming. Chapter 1 Entering the World of Algorithms 1 1.1 Algorithms are everywhere in life 2 1.1.1 Definition of an algorithm 3 1.1.2 Conditions of an algorithm 4 1.1.3 Time complexity O(f(n)) 6 1.2 Introduction to common algorithms 8 1.2.1 Divide and conquer algorithm 8 1.2.2 Recursive algorithm 9 1.2.3 Greedy algorithm 12 1.2.4 Dynamic programming 13 1.2.5 Iterative algorithm 14 1.2.6 Enumeration algorithm 15 1.2.7 Backtracking algorithm 16 Homework 21 Chapter 2 Common Data Structures 23 2.1 Understanding Data Structures 23 2.2 Types of Data Structures 26 2.2.1 Arrays 26 2.2.2 Linked lists 28 2.2.3 Stacks 29 2.2.4 Queues 30 2.3 Tree structures 32 2.3.1 Basic concepts of trees 32 2.3.2 Introduction to tree structure terms 33 2.3.3 Binary tree 34 2.4 Introduction to graph theory 35 2.5 Hash table 37 Homework 38 Chapter 3 Sorting algorithm 40 3.1 Understanding sorting 41 3.2 Bubble sort 42 3.3 Selection sort 44 3.4 Insertion sort 47 3.5 Shell sort 49 3.6 Merge sort 52 3.7 Quick sort 53 3.8 Radix sort 56 Homework 58 Chapter 4 Search and hash algorithm 60 4.1 Introduction to common search algorithms 61 4.1.1 Sequential search 61 4.1.2 Binary search 63 4.1.3 Interpolation search 65 4.2 Introduction to common hash methods 67 4.2.1 Division and remainder method 67 4.2.2 Square median method 68 4.2.3 Folding method 69 4.2.4 Digital analysis method 70 4.3 Dealing with collision and overflow problems 71 4.3.1 Linear detection method 71 4.3.2 Square detection method 73 4.3.3 Rehashing method 73 Exercises 74 Chapter 5 Array and Linked List Algorithms 76 5.1 Matrix 76 5.1.1 Matrix addition 77 5.1.2 Matrix multiplication 78 5.1.3 Transpose matrix 80 5.2 Create a singly linked list 81 5.2.1 Concatenate singly linked lists 83 5.2.2 Deleting a singly linked list node 85 5.2.3 Reversing a singly linked list 89 Exercises 92 Chapter 6 Stack and Queue Algorithms 94 6.1 Implementing a stack with an array 94 6.2 Implementing a stack with a linked list 97 6.3 Algorithm for solving the Tower of Hanoi problem 100 6.4 The Eight Queens Problem 105 6.5 Implementing Queues with Arrays 108 6.6 Implementing Queues with Linked Lists 111 6.7 Bidirectional Queues 115 6.8 Priority Queues 119 Exercises 120 Chapter 7 Tree Structures and Algorithms 121 7.1 Implementing Binary Trees with Arrays 122 7.2 Implementing Binary Trees with Linked Lists 125 7.3 Traversing Binary Trees 128 7.4 Searching for Binary Tree Nodes 132 7.5 Inserting Binary Tree Nodes 134 7.6 Deleting Binary Tree Nodes 136 7.7 Stacked Tree Sorting 139 Exercises 145 Chapter 8 Graph Structures and Algorithms 147 8.1 Graph Traversal 147 8.1.1 Depth-First Traversal 148 8.1.2 Breadth-First Traversal 151 8.2 Minimum Spanning Tree 155 8.2.1 8.2.2 Prim\'s Algorithm 156 8.2.3 Kruskal\'s Algorithm 157 8.3 Shortest Path Methods for Graphs 161 8.3.1 Dijkstra\'s Algorithm and A* Algorithm 162 8.3.2 Floyd\'s Algorithm 168 Homework Problems 172 Appendix A Homework Problems and Solutions 174