Contents 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 Summar