【文件属性】：
文件名称：Data Structures Succinctly Part 1
文件大小：1.89MB
文件格式：PDF
更新时间：2016-11-03 22:40:25
Data Structures, Algorithm
Data Structures Succinctly Part 1
Table of Contents
The Story behind the Succinctly Series of Books ................................................................................... 9
Chapter 1 Algorithms and Data Structures ........................................................................................... 11
Why Do We Care? ................................................................................................................................. 11
Asymptotic Analysis ............................................................................................................................... 11
Rate of Growth ..................................................................................................................................... 11
Best, Average, and Worst Case .......................................................................................................... 13
What are we Measuring? ..................................................................................................................... 13
Code Samples ..................................................................................................................................... 13
Chapter 2 Linked List ............................................................................................................................... 14
Overview ................................................................................................................................................ 14
Implementing a LinkedList Class ........................................................................................................... 16
The Node ............................................................................................................................................. 16
The LinkedList Class ........................................................................................................................... 18
Add ....................................................................................................................................................... 19
Remove ................................................................................................................................................ 20
Contains ............................................................................................................................................... 22
GetEnumerator .................................................................................................................................... 23
Clear .................................................................................................................................................... 24
CopyTo ................................................................................................................................................ 24
Count ................................................................................................................................................... 25
IsReadOnly .......................................................................................................................................... 25
Doubly Linked List .................................................................................................................................. 25
Node Class .......................................................................................................................................... 26
Add ....................................................................................................................................................... 26
5
Remove ................................................................................................................................................ 28
But Why? ............................................................................................................................................. 31
Chapter 3 Array List ................................................................................................................................. 33
Overview ................................................................................................................................................ 33
Class Definition ...................................................................................................................................... 33
Insertion ................................................................................................................................................. 35
Growing the Array ................................................................................................................................ 35
Insert .................................................................................................................................................... 37
Add ....................................................................................................................................................... 38
Deletion .................................................................................................................................................. 39
RemoveAt ............................................................................................................................................ 39
Remove ................................................................................................................................................ 40
Indexing.................................................................................................................................................. 40
IndexOf ................................................................................................................................................ 40
Item ...................................................................................................................................................... 41
Contains ............................................................................................................................................... 42
Enumeration ........................................................................................................................................... 42
GetEnumerator .................................................................................................................................... 42
Remaining IList Methods ................................................................................................................. 43
Clear .................................................................................................................................................... 43
CopyTo ................................................................................................................................................ 43
Count ................................................................................................................................................... 43
IsReadOnly .......................................................................................................................................... 44
Chapter 4 Stack and Queue .................................................................................................................... 45
Overview ................................................................................................................................................ 45
Stack ...................................................................................................................................................... 45
6
Class Definition .................................................................................................................................... 46
Push ..................................................................................................................................................... 47
Pop ....................................................................................................................................................... 47
Peek ..................................................................................................................................................... 48
Count ................................................................................................................................................... 48
Example: RPN Calculator .................................................................................................................... 49
Queue .................................................................................................................................................... 51
Class Definition .................................................................................................................................... 51
Enqueue ............................................................................................................................................... 52
Dequeue .............................................................................................................................................. 52
Peek ..................................................................................................................................................... 53
Count ................................................................................................................................................... 53
Deque (Double-Ended Queue) .............................................................................................................. 53
Class Definition .................................................................................................................................... 54
Enqueue ............................................................................................................................................... 55
Dequeue .............................................................................................................................................. 55
PeekFirst .............................................................................................................................................. 56
PeekLast .............................................................................................................................................. 57
Count ................................................................................................................................................... 57
Example: Implementing a Stack .......................................................................................................... 58
Array Backing Store ............................................................................................................................. 59
Class Definition .................................................................................................................................... 62
Enqueue ............................................................................................................................................... 62
Dequeue .............................................................................................................................................. 65
PeekFirst .............................................................................................................................................. 66
PeekLast .............................................................................................................................................. 66
Count ................................................................................................................................................... 67
7
Chapter 5 Binary Search Tree ................................................................................................................. 68
Tree Overview ........................................................................................................................................ 68
Binary Search Tree Overview ................................................................................................................ 69
The Node Class ..................................................................................................................................... 70
The Binary Search Tree Class ............................................................................................................... 71
Add ....................................................................................................................................................... 72
Remove ................................................................................................................................................ 74
Contains ............................................................................................................................................... 79
Count ................................................................................................................................................... 81
Clear .................................................................................................................................................... 81
Traversals .............................................................................................................................................. 82
Preorder ............................................................................................................................................... 82
Postorder ............................................................................................................................................. 83
Inorder .................................................................................................................................................. 84
GetEnumerator .................................................................................................................................... 86
Chapter 6 Set ............................................................................................................................................ 87
Set Class ................................................................................................................................................ 87
Insertion ................................................................................................................................................. 89
Add ....................................................................................................................................................... 89
AddRange ............................................................................................................................................ 89
Remove .................................................................................................................................................. 90
Contains ................................................................................................................................................. 90
Count ...................................................................................................................................................... 91
GetEnumerator ...................................................................................................................................... 91
Algorithms .............................................................................................................................................. 92
Union .................................................................................................................................................... 92
8
Intersection .......................................................................................................................................... 93
Difference ............................................................................................................................................. 94
Symmetric Difference .......................................................................................................................... 95
IsSubset ............................................................................................................................................... 96
Chapter 7 Sorting Algorithms ................................................................................................................. 98
Swap ...................................................................................................................................................... 98
Bubble Sort ............................................................................................................................................ 98
Insertion Sort ........................................................................................................................................ 100
Selection Sort ....................................................................................................................................... 103
Merge Sort ........................................................................................................................................... 105
Divide and Conquer ........................................................................................................................... 105
Merge Sort ......................................................................................................................................... 106
Quick Sort ............................................................................................................................................ 108
