Data Structures and Algorithms Analysis, Volume 1: Data structures based on linear relations

Title Page
Copyright
Contents
Preface
    My experience in teaching and learning data structures
    The cruxes in learning data structures
    The relationship between program design and data structures
    The relationship between data structures and other courses
    The importance of data structures
    Will data structures be outdated
    Additional contents in this book about the implementation of algorithms and programs
    Description of the algorithms
    A brief introduction to the course “data structures”
    Basic aims
    Organizational structure of this book
    Acknowledgments
1 Introduction
    1.1 Let’s begin with programming
    1.2 The data to be processed by the program
    1.3 The introduction of data structures
    1.4 Basic concepts of data structures
        1.4.1 Basic terminologies of data structures
        1.4.2 The three key elements of data structures
    1.5 How to design algorithms
        1.5.1 The definition of algorithm and representation methods
        1.5.2 The relation between algorithm design and function design
        1.5.3 Software design method
        1.5.4 General steps of algorithm design
    1.6 How to evaluate algorithms
        1.6.1 The design requirements of algorithms
        1.6.2 Measurement methods of algorithm efficiency
    1.7 The pre-execution analysis methods of algorithm efficiency
        1.7.1 The size of the problem and the strategy of the algorithm
        1.7.2 The upper and lower bounds of algorithm efficiency
        1.7.3 The asymptotic upper bound – the time complexity of the algorithm
        1.7.4 The comprehensive discussion on the time complexity of algorithms
        1.7.5 The analysis methods on the space efficiency of the algorithm
    1.8 Comprehensive evaluation of algorithm performance
    1.9 Chapter summary
    1.10 Exercises
        1.10.1 Multiple-choice questions
        1.10.2 Practical problems
2 The data structure whose nodes share a linear logical relation – linear list
    2.1 Viewing the linear list from the perspective of logical structure
        2.1.1 The sequential relations that exist in practical problems
        2.1.2 The logical structure of linear lists
    2.2 One of the storage structures of linear lists – sequential list
        2.2.1 The design of storage structure of a sequential list
        2.2.2 The operations on sequential list
        2.2.3 Discussion on the sequential storage structure
    2.3 The second storage method for linear list – linked list
        2.3.1 Introduction 1 – the story of word
        2.3.2 Introduction 2 – linked lists in mobile phones
        2.3.3 The storage of singly linked lists
        2.3.4 Operations on the singly linked list
        2.3.5 Discussion of singly linked lists
        2.3.6 Circular linked lists
        2.3.7 Doubly linked list
        2.3.8 Summary on linked lists
    2.4 Examples of the application of linear lists
        2.4.1 Algorithm design
        2.4.2 Program implementation
    2.5 Comparisons between sequential list and linked list
        2.5.1 Considerations based on storage
        2.5.2 Considerations based on operations
        2.5.3 Considerations based on the environment
    2.6 Summary of the chapter
    2.7 Exercises
        2.7.1 Multiple-choice questions
        2.7.2 Algorithm design exercises
3 Linear list with restricted operations – stack and queue
    3.1 Stack – a linear list managed in a first-in–last-out manner
        3.1.1 Introduction to the operation pattern of stack
        3.1.2 The logic structure of stack
        3.1.3 The design of the storage structure of stacks
        3.1.4 Operations on stack
        3.1.5 Comparison of various stack structures
    3.1.6 Examples of the application of stack
        3.1.6.1 Base conversion
        3.1.6.2 Implement recursive functions with stack
        3.1.6.3 Evaluating expressions
    3.1.7 Recursion – a “first-in–last-out” process
        3.1.7.1 The concept of recursion and its key elements
        3.1.7.2 Analysis of features of recursion
        3.1.7.3 Summary of recursion
    3.2 Queue – linear list managed in a “FIFO” manner
        3.2.1 Introduction to the queue processing model
    3.2.2 The logical structure of queue
    3.2.3 The sequential storage structure of queue
        3.2.3.1 Sequential queue
    3.2.4 Basic operations on sequential queue
        3.2.4.1 Basic operation on sequential queue – set queue as empty
        3.2.4.2 Basic operation on sequential queue – check emptiness of queue
        3.2.4.3 Basic operation on sequential queue – get the head element
        3.2.4.4 Basic operation on sequential queue – insert element
        3.2.4.5 Basic operation on sequential queue – delete element
    3.2.5 Linked storage structure of queue
    3.2.6 Basic operations on linked queue
        3.2.6.1 Basic operations on linked queue – initialize and set the queue as empty
        3.2.6.2 Basic operation on linked queue – checking emptiness of queue
        3.2.6.3 Basic operation on linked queue – retrieve the head node
        3.2.6.4 Basic operation on linked queue – enqueuing
        3.2.6.5 Basic operation on linked queue – dequeuing
        3.2.6.6 Destroying the linked queue
    3.2.7 Comparison of different queue structures
    3.2.8 Examples of the application of queue
        3.2.8.1 Application of queue 1 – radix sort
        3.2.8.2 Application of queue 2 – card game
    3.3 Chapter summary
    3.4 Exercises
        3.4.1 Multiple choice questions
        3.4.2 Practical questions
        3.4.3 Algorithm design
4 Sequential list with special contents – multidimensional arrays and strings
    4.1 Multidimensional arrays
        4.1.1 The concept of arrays
        4.1.2 The storage structure of arrays
    4.2 The compressional storage of matrices
        4.2.1 The compressional storage of symmetric matrix
        4.2.2 The compressional storage of triangular matrix
        4.2.3 The compressional storage of diagonal matrix
        4.2.4 Compressional storage of sparse matrix
    4.3 String
        4.3.1 The definition of string
        4.3.2 The storage structure of string
        4.3.3 Search on strings – pattern matching
    4.4 Chapter summary
    4.5 Exercises
        4.5.1 Multiple-choice questions
        4.5.2 Applied problems
        4.5.3 Algorithm design
Appendix A Relation graph of data
Appendix B How to add custom header files
Appendix C Format of software design manual
    Steps to writing huge and complex applications
    Aspects to consider for program implementation
    Format of software design manual
Appendix D Answers to selected exercises
    Chapter 1 Introduction
    Chapter 2 The data structure whose nodes share a linear logical relation – linear list
    Chapter 3 Linear list with restricted operations – stack and queue
    Chapter 4 Sequential list with special contents – multidimensional arrays and strings
References
Index