vi Table of Contents
4. Analysis of Algorithms .......................................................................... 38
Worst-Case Analysis ....................................................................................... 39
O-Notation ...................................................................................................... 40
Computational Complexity ............................................................................ 42
Analysis Example: Insertion Sort ................................................................... 45
Questions and Answers ................................................................................. 47
Related Topics ................................................................................................ 48
II. Data Structures .................................................................................. 49
5. Linked Lists
............................................................................................... 51
Description of Linked Lists ............................................................................ 52
Interface for Linked Lists ............................................................................... 53
Implementation and Analysis of Linked Lists ............................................... 56
Linked List Example: Frame Management .................................................... 65
Description of Doubly-Linked Lists ............................................................... 68
Interface for Doubly-Linked Lists .................................................................. 68
Implementation and Analysis of Doubly Linked Lists ................................. 72
Description of Circular Lists .......................................................................... 82
Interface for Circular Lists .............................................................................. 82
Implementation and Analysis of Circular Lists ............................................. 84
Circular List Example: Second-Chance Page Replacement .......................... 91
Questions and Answers ................................................................................. 94
Related Topics ................................................................................................ 96
6. Stacks and Queues ................................................................................. 98
Description of Stacks ..................................................................................... 99
Interface for Stacks ....................................................................................... 100
Implementation and Analysis of Stacks ...................................................... 102
Description of Queues ................................................................................. 105
Interface for Queues .................................................................................... 105
Implementation and Analysis of Queues .................................................... 107
Queue Example: Event Handling ................................................................ 110
Questions and Answers ............................................................................... 113
Related Topics .............................................................................................. 114
7. Sets .............................................................................................................. 115
Description of Sets ....................................................................................... 116
Interface for Sets .......................................................................................... 119
评论2