Data Structures and Algorithms Analysis Volume 2: Data Structures Based on Non-Linear Relations and Data Processing Methods

Title Page
Copyright
Contents
Preface
1 Nonlinear structure with layered logical relations between nodes – tree
    1.1 Tree in actual problems
        1.1.1 Introductory example to tree 1 – tree-like structures in our daily life
        1.1.2 Introductory example of tree 2 – the directory structure of computer
        1.1.3 Introductory example of tree 3 – tree-structured website
    1.2 Logical structure of tree
        1.2.1 The definition and basic terminologies of tree
        1.2.2 Definition of operations on trees
    1.3 The storage structure of tree
        1.3.1 The continuous storage method of trees
        1.3.2 Linked storage method of trees
    1.4 The logical structure of binary trees
        1.4.1 The concept of binary tree
        1.4.2 Basic properties of binary trees
        1.4.3 Definition of operations on binary tree
    1.5 The storage structure of binary tree and its implementation
        1.5.1 The sequential structure of binary trees
        1.5.2 The linked storage structure of binary tree – binary linked list
        1.5.3 Constructing dynamic binary linked lists
    1.6 Search operation on nodes of binary tree – traversal of tree
        1.6.1 Introductory example 1 of traversal – simple model of self-check of electrical devices
        1.6.2 Introductory example 2 of traversal – management of goods in e-commerce
        1.6.3 Introductory example 3 of traversal – the efficient searching strategy for nodes in the tree
        1.6.4 The breadth-first-search traversal of trees
        1.6.5 The depth-first-search traversal of trees
        1.6.6 Applications of tree traversal
    1.7 Application of trees
        1.7.1 Expression tree
        1.7.2 Threaded binary tree
        1.7.3 Huffman tree and Huffman encoding
    1.8 Generalized lists
        1.8.1 Definition of generalized List
        1.8.2 The storage of generalized list
    1.9 Chapter summary
    1.10 Exercises
        1.10.1 Multiple-choice questions
        1.10.2 Practical problems
        1.10.3 Algorithm design questions
2 Nonlinear structure with arbitrary logical relations between nodes – graph
    2.1 Graph in actual problems and its abstraction
        2.1.1 Introductory example of graph 1 – coloring problem of map
        2.1.2 Introductory example of graph 2 – search engine and the structure of website
        2.1.3 Introductory example of graph 3 – shortest flight connection
    2.2 The logical structure of graph
        2.2.1 The definition and basic terminologies of graph
        2.2.2 Definitions of operations on graph
    2.3 The storage structure for graph and its implementations
        2.3.1 Array representational method of graph 1 – adjacency matrix
        2.3.2 Array representational method of graph 2 – array for set of edges
        2.3.3 The linked list representational method of graph
        2.3.4 Summary and comparison of various storage structures of graph
    2.4 Basic operations on graph
        2.4.1 Operations on adjacency matrix
        2.4.2 Operations on adjacency list
    2.5 Lookup of the vertices of graph – traversal of graph
        2.5.1 Introductory example for lookup on graph – the search of web crawlers
        2.5.2 The breadth-first traversal of graph BFS
        2.5.3 Depth-first traversal of graph DFS
    2.6 Classic application of graph – tree problem in graph
        2.6.1 Introductory example of application of graph 1 – minimal cost for setting up communication network
        2.6.2 Introductory example of application of graph 2 – transmission of information in network
        2.6.3 Spanning tree
        2.6.4 Minimum spanning tree
        2.6.5 Algorithm for minimum spanning tree 1 – Prim’s algorithm
        2.6.6 Algorithm for minimum spanning tree 2 – Kruskal’s algorithm
        2.6.7 Summary of spanning tree algorithm
    2.7 Classical application of graph – shortest path problems
        2.7.1 Introduction to shortest path problems
        2.7.2 Single-source shortest path algorithm – Dijkstra’s algorithm
        2.7.3 All-pair shortest path algorithm – Floyd’s algorithm
        2.7.4 Summary of shortest path problems
    2.8 Classical application of graph – problems of moving vertices and moving edges
        2.8.1 Introduction to the problem of ordering of moving vertices of graph
        2.8.2 AOV network and topological ordering – ordering of moving vertices
        2.8.3 AOE network and critical path – longest activity edge
        2.8.4 Summary of activity vertices and activity edges
    2.9 Chapter summary
    2.10 Exercises
        2.10.1 Multiple-choice questions
        2.10.2 Long-form questions
        2.10.3 Algorithm design questions
3 Data processing methods – sorting technologies
    3.1 Introduction
        3.1.1 The basic concepts of sorting
        3.1.2 Classification of sorting algorithms
    3.2 Insertion sort
        3.2.1 Direct insertion sort
        3.2.2 Shell sort
    3.3 Exchange sort
        3.3.1 Bubble sort
        3.3.2 Quick sort
    3.4 Selection sort
        3.4.1 Simple selection sort
        3.4.2 Heap sort
    3.5 Merge sort
    3.6 Distribution sort
        3.6.1 Bucket sort
        3.6.2 Radix sort
    3.7 Comparison of various sorting algorithms
        3.7.1 Quick sort
        3.7.2 Merge sort
        3.7.3 Heap sort
        3.7.4 Shell sort
        3.7.5 Insertion sort
        3.7.6 Bubble sort
        3.7.7 Selection sort
        3.7.8 Bucket sort
        3.7.9 Radix sort
    3.8 Chapter summary
    3.9 Exercises
        3.9.1 Multiple-choice questions
        3.9.2 Cloze test
        3.9.3 Open-ended questions
4 Data processing – index and search technologies
    4.1 Basic concepts of index
        4.1.1 Definition of index
        4.1.2 The logical characteristics of index
        4.1.3 Major operations on index
    4.2 Linear indexing technology
        4.2.1 Dense index
        4.2.2 Block index
        4.2.3 Multilist
        4.2.4 Inverted list
    4.3 Tree-like index
        4.3.1 Binary search tree
        4.3.2 B-tree
    4.4 Overview of searching
        4.4.1 Basic concept of searching
        4.4.2 Performance of the lookup algorithm
    4.5 The lookup technology of linear list
        4.5.1 Sequential lookup
        4.5.2 Lookup on an ordered list
        4.5.3 Indexed search
    4.6 Search techniques on tree lists
        4.6.1 Search on binary search tree
        4.6.2 Search on B-tree
        4.6.3 Search on nonnumerical ordered list – dictionary tree
    4.7 Search techniques on hash table
        4.7.1 Introductory example – idea derived from drawing lots and queuing
        4.7.2 Introductory example – the search on words and pictures in the search engine
        4.7.3 Introduction to hash table
        4.7.4 The design of hash function
        4.7.5 Conflict resolution methods
        4.7.6 Performance analysis of hash table lookup
    4.8 Chapter summary
    4.9 Exercises
        4.9.1 Multiple-choice questions
        4.9.2 Closure
        4.9.3 Practical questions
        4.9.4 Algorithm design questions
Appendix A Answers to selected exercises
    Chapter 1 Nonlinear structure with layered logical relations between nodes – tree
    Chapter 2 Nonlinear structure with arbitrary logical relations between nodes – graph
    Chapter 3 Data processing methods – sorting technologies
        3.9.1 Multiple-choice questions
        3.9.2 Cloze test
    Chapter 4 Data processing – index and search technologies
        4.9.1 Multiple-choice questions
        4.9.2 Cloze test
References
Index
    Notes