Table of Contents
Preface xi
1 Introduction 1
1.1 Let's begin with programming 1
1.2 The data to be processed by the program 7
1.3 The introduction of data structures 17
1.4 Basic concepts of data structures 18
1.4.1 Basic terminologies of data structures 18
1.4.1.1 Data 18
1.4.1.2 Data element 18
1.4.1.3 Data item 18
1.4.1.4 Data structure 18
1.4.2 The three key elements of data structures 19
1.4.2.1 Logical structure 19
1.4.2.2 The storage structure of data 20
1.4.2.3 Operation on data 23
1.5 How to design algorithms 24
1.5.1 The definition of algorithm and representation methods 24
1.5.1.1 Algorithm 24
1.5.1.2 Features of algorithms 24
1.5.1.3 Representation of algorithm 25
1.5.1.4 Key elements to describing algorithms 25
1.5.2 The relation between algorithm design and function design 25
1.5.2.1 Concepts related to function 25
1.5.2.2 The relation between algorithm design and function design 26
1.5.3 Software design method 27
1.5.3.1 Test case design 27
1.5.3.2 Description of data structure 27
1.5.3.3 Function interface and function structure design 27
1.5.3.4 Pseudocode description of the algorithm 27
1.5.3.5 Program implementation 28
1.5.3.6 Algorithm efficiency analysis 28
1.5.4 General steps of algorithm design 28
1.6 How to evaluate algorithms 31
1.6.1 The design requirements of algorithms 31
1.6.1.1 Correctness 31
1.6.1.2 Readability 31
1.6.1.3 Robustness 32
1.6.1.4 Efficiency 32
1.6.2 Measurement methods of algorithm efficiency 32
1.6.2.1 The after-execution analysis of algorithm performance 32
1.6.2.2 The pre-execution analysis of algorithm efficiency 34
1.7 The pre-execution analysis methods of algorithm efficiency 34
1.7.1 The size of the problem and the strategy of the algorithm 35
1.7.2 The upper and lower bounds of algorithm efficiency 37
1.7.2.1 Best case 37
1.7.2.2 Worst case 37
1.7.2.3 Average case 37
1.7.3 The asymptotic upper bound - the time complexity of the algorithm 41
1.7.4 The comprehensive discussion on the time complexity of algorithms 43
1.7.4.1 The practical implications of the time complexity of algorithms 43
1.7.4.2 Function values with significant meanings to algorithm analysis 45
1.7.4.3 Computation rules for time complexity 47
1.7.4.4 General methods for algorithm efficiency analysis 48
1.7.5 The analysis methods on the space efficiency of the algorithm 49
1.8 Comprehensive evaluation of algorithm performance 55
1.9 Chapter summary 57
1.10 Exercises 58
1.10.1 Multiple-choice questions 58
1.10.2 Practical problems 59
2 The data structure whose nodes share a linear logical relation - linear list 61
2.1 Viewing the linear list from the perspective of logical structure 61
2.1.1 The sequential relations that exist in practical problems 61
2.1.1.1 The one-to-one correspondence relation that exists in queuing 61
2.1.1.2 The representation method of alphabetical table 61
2.1.1.3 The structure of phone number tables 62
2.1.2 The logical structure of linear lists 63
2.1.2.1 The definition of linear list 63
2.1.2.2 The logical features of the linear list 63
2.1.2.3 Major operations on the linear list 63
2.2 One of the storage structures of linear lists - sequential list 64
2.2.1 The design of storage structure of a sequential list 64
2.2.1.1 The definition of sequential list 64
2.2.1.2 The storage characteristics of sequential list 65
2.2.1.3 The design of the sequential list storage structure 65
2.2.1.4 Think and discuss on the application of "struct" 67
2.2.2 The operations on sequential list 69
2.2.2.1 The insertion operation of ordered list 69
2.2.2.2 Deletion operation on sequential list 73
2.2.2.3 Lookup operation of elements in sequential list 77
2.2.2.4 Accessing data element from sequential list 78
2.2.3 Discussion on the sequential storage structure 79
2.3 The second storage method for linear list - linked list 80
2.3.1 Introduction 1 - the story of word 80
2.3.2 Introduction 2 - linked lists in mobile phones 82
2.3.3 The storage of singly linked lists 84
2.3.3.1 The structural design of nodes of linked lists 84
2.3.3.2 How are the nodes in the linked list linked together in the storage space? 84
2.3.4 Operations on the singly linked list 90
2.3.4.1 Initialization of singly linked lists 91
2.3.4.2 Construction of singly linked lists 94
2.3.4.3 Lookup operation on singly linked list 101
2.3.4.4 The insertion operation on singly linked lists 106
2.3.4.5 Deletion operation on singly linked lists 111
2.3.5 Discussion of singly linked lists 115
2.3.6 Circular linked lists 115
2.3.6.1 Structural design of circular linked lists 115
2.3.6.2 Operations on circular linked lists 116
2.3.7 Doubly linked list 119
2.3.7.1 Structural design of doubly linked lists 119
2.3.7.2 Operations on doubly linked lists 121
2.3.8 Summary on linked lists 121
2.4 Examples of the application of linear lists 122
2.4.1 Algorithm design 122
2.4.2 Program implementation 122
2.5 Comparisons between sequential list and linked list 123
2.5.1 Considerations based on storage 124
2.5.2 Considerations based on operations 125
2.5.3 Considerations based on the environment 125
2.6 Summary of the chapter 125
2.7 Exercises 126
2.7.1 Multiple-choice questions 126
2.7.2 Algorithm design exercises 129
3 Linear list with restricted operations - stack and queue 133
3.1 Stack - a linear list managed in a first-in-last-out manner 133
3.1.1 Introduction to the operation pattern of stack 133
3.1.1.1 Introduction to stack 1 - erroneous operation in Word 133
3.1.1.2 Introduction to stack example 2 - bracket matching 134
3.1.1.3 Introduction to stack example 3 - the recursive invocation of functions 135
3.1.1.4 Introduction to stack example 4 - the embedded invocation of functions 136
3.1.2 The logic structure of stack 138
3.1.2.1 The definition of stack 138
3.1.2.2 The differences and connections between stack and linear list 140
3.1.2.3 Operations on stack 140
3.1.3 The design of the storage structure of stacks 140
3.1.3.1 Sequential stack - use a piece of continuous space to store stack elements 140
3.1.3.2 Linked stack - storing stack elements in noncontinuous space 141
3.1.4 Operations on stack 142
3.1.4.1 Basic operations on sequential stack 142
3.1.4.2 Basic operations on linked stack 157
3.1.5 Comparison of various stack structures 164
3.1.6 Examples of the application of stack 164
3.1.6.1 Base conversion 164
3.1.6.2 Implement recursive functions with stack 166
3.1.6.3 Evaluating expressions 171
3.1.7 Recursion - a "first-in-last-out" process 172
3.1.7.1 The concept of recursion and its key elements 172
3.1.7.2 Analysis of features of recursion 174
3.1.7.3 Summary of recursion 176
3.2 Queue - linear list managed in a "FIFO" manner 177
3.2.1 Introduction to the queue processing model 177
3.2.1.1 Introductory example to queue 1 - asynchronous processing of data in computer 177
3.2.1.1.1 Buffered queues in e-commerce systems 177
3.2.1.1.2 Mail queues in mail servers 178
3.2.1.2 Introductory example to queue 2 - solution to Pascal's triangle using queue 179
3.2.2 The logical structure of queue 181
3.2.3 The sequential storage structure of queue 182
3.2.3.1 Sequential queue 182
3.2.4 Basic operations on sequential queue 192
3.2.4.1 Basic operation on sequential queue - set queue as empty 192
3.2.4.2 Basic operation on sequential queue - check emptiness of queue 193
3.2.4.3 Basic operation on sequential queue - get the head element 194
3.2.4.4 Basic operation on sequential queue - insert element 195
3.2.4.5 Basic operation on sequential queue - delete element 196
3.2.5 Linked storage structure of queue 197
3.2.6 Basic operations on linked queue 199
3.2.6.1 Basic operations on linked queue - initialize and set the queue as empty 199
3.2.6.2 Basic operation on linked queue - checking emptiness of queue 200
3.2.6.3 Basic operation on linked queue - retrieve the head node 201
3.2.6.4 Basic operation on linked queue - enqueuing 202
3.2.6.5 Basic operation on linked queue - dequeuing 204
3.2.6.6 Destroying the linked queue 206
3.2.7 Comparison of different queue structures 208
3.2.8 Examples of the application of queue 209
3.2.8.1 Application of queue 1 - radix sort 209
3.2.8.2 Application of queue 2 - card game 213
3.3 Chapter summary 215
3.4 Exercises 217
3.4.1 Multiple choice questions 217
3.4.2 Practical questions 219
3.4.3 Algorithm design 219
4 Sequential list with special contents - multidimensional arrays and strings 221
4.1 Multidimensional arrays 221
4.1.1 The concept of arrays 222
4.1.2 The storage structure of arrays 223
4.2 The compressional storage of matrices 226
4.2.1 The compressional storage of symmetric matrix 228
4.2.2 The compressional storage of triangular matrix 230
4.2.3 The compressional storage of diagonal matrix 231
4.2.4 Compressional storage of sparse matrix 232
4.2.4.1 Definition of sparse matrix 232
4.2.4.2 The compressional storage of sparse matrix 235
4.2.4.2.1 Triple list 236
4.2.4.2.2 The linked list storage method of sparse matrix 236
4.3 String 238
4.3.1 The definition of string 240
4.3.1.1 Substring 240
4.3.1.2 The position of the substring 241
4.3.1.3 Equivalence of string 241
4.3.2 The storage structure of string 241
4.3.2.1 The sequential storage of string 241
4.3.2.2 The block link storage structure of string 243
4.3.2.3 The indexed storage method of string 245
4.3.3 Search on strings - pattern matching 248
4.3.3.1 BF algorithm 249
4.3.3.2 KMP algorithm 258
4.4 Chapter summary 268
4.5 Exercises 271
4.5.1 Multiple-choice questions 271
4.5.2 Applied problems 273
4.5.3 Algorithm design 273
Appendix A Relation graph of data 275
Appendix B How to add custom header files 277
Appendix C Format of software design manual 279
Appendix D Answers to selected exercises 283
References 285
Index 287
