As an experienced JavaScript developer moving to server-side programming, you need to implement classic data structures and algorithms associated with conventional object-oriented languages like C# and Java. This practical guide shows you how to work hands-on with a variety of storage mechanisms—including linked lists, stacks, queues, and graphs—within the constraints of the JavaScript environment.
Determine which data structures and algorithms are most appropriate for the problems you’re trying to solve, and understand the tradeoffs when using them in a JavaScript program. An overview of the JavaScript features used throughout the book is also included.
Preface ix
1 The JavaScript Programming Environment 1 (12)
and Model
The JavaScript Environment 1 (1)
JavaScript Programming Practices 2 (8)
Declaring and Intializing Variables 3 (1)
Arithmetic and Math Library Functions 3 (1)
in JavaScript
Decision Constructs 4 (2)
Repetition Constructs 6 (1)
Functions 7 (1)
Variable Scope 8 (2)
Recursion 10 (1)
Objects and Object-Oriented Programming 10 (2)
Summary 12 (1)
2 Arrays 13 (22)
JavaScript Arrays Defined 13 (1)
Using Arrays 13 (4)
Creating Arrays 14 (1)
Accessing and Writing Array Elements 15 (1)
Creating Arrays from Strings 15 (1)
Aggregate Array Operations 16 (1)
Accessor Functions 17 (2)
Searching for a Value 17 (1)
String Representations of Arrays 18 (1)
Creating New Arrays from Existing Arrays 18 (1)
Mutator Functions 19 (4)
Adding Elements to an Array 19 (1)
Removing Elements from an Array 20 (1)
Adding and Removing Elements from the 21 (1)
Middle of an Array
Putting Array Elements in Order 22 (1)
Iterator Functions 23 (4)
Non--Array-Generating Iterator Functions 23 (2)
Iterator Functions That Return a New 25 (2)
Array
Two-Dimensional and Multidimensional 27 (3)
Arrays
Creating Two-Dimensional Arrays 27 (1)
Processing Two-Dimensional Array 28 (2)
Elements
Jagged Arrays 30 (1)
Arrays of Objects 30 (1)
Arrays in Objects 31 (4)
Exercises 33 (2)
3 Lists 35 (14)
A List ADT 35 (1)
A List Class Implementation 36 (5)
Append: Adding an Element to a List 37 (1)
Remove: Removing an Element from a List 37 (1)
Find: Finding an Element in a List 38 (1)
Length: Determining the Number of 38 (1)
Elements in a List
toString: Retrieving a List's Elements 38 (1)
Insert: Inserting an Element into a List 39 (1)
Clear: Removing All Elements from a List 39 (1)
Contains: Determining if a Given Value 40 (1)
Is in a List
Traversing a List 40 (1)
Iterating Through a List 41 (1)
A List-Based Application 42 (7)
Reading Text Files 42 (1)
Using Lists to Manage a Kiosk 43 (4)
Exercises 47 (2)
4 Stacks 49 (10)
Stack Operations 49 (1)
A Stack Implementation 50 (3)
Using the Stack Class 53 (6)
Multiple Base Conversions 53 (1)
Palindromes 54 (2)
Demonstrating Recursion 56 (1)
Exercises 57 (2)
5 Queues 59 (14)
Queue Operations 59 (1)
An Array-Based Queue Class Implementation 60 (3)
Using the Queue Class: Assigning Partners 63 (4)
at a Square Dance
Sorting Data with Queues 67 (3)
Priority Queues 70 (3)
Exercises 72 (1)
6 Linked Lists 73 (16)
Shortcomings of Arrays 73 (1)
Linked Lists Defined 74 (1)
An Object-Based Linked List Design 75 (6)
The Node Class 75 (1)
The Linked List Class 76 (1)
Inserting New Nodes 76 (2)
Removing Nodes from a Linked List 78 (3)
Doubly Linked Lists 81 (4)
Circularly Linked Lists 85 (1)
Other Linked List Functions 86 (3)
Exercises 86 (3)
7 Dictionaries 89 (8)
The Dictionary Class 89 (2)
Auxiliary Functions for the Dictionary 91 (2)
Class
Adding Sorting to the Dictionary Class 93 (4)
Exercises 94 (3)
8 Hashing 97 (16)
An Overview of Hashing 97 (1)
A Hash Table Class 98 (9)
Choosing a Hash Function 98 (3)
A Better Hash Function 101(2)
Hashing Integer Keys 103(3)
Storing and Retrieving Data in a Hash 106(1)
Table
Handling Collisions 107(6)
Separate Chaining 107(2)
Linear Probing 109(2)
Exercises 111(2)
9 Sets 113(8)
Fundamental Set Definitions, Operations, 113(1)
and Properties
Set Definitions 113(1)
Set Operations 114(1)
The Set Class Implementation 114(2)
More Set Operations 116(5)
Exercises 120(1)
10 Binary Trees and Binary Search Trees 121(18)
Trees Defined 121(2)
Binary Trees and Binary Search Trees 123(6)
Building a Binary Search Tree 124(2)
Implementation
Traversing a Binary Search Tree 126(3)
BST Searches 129(3)
Searching for the Minimum and Maximum 130(1)
Value
Searching for a Specific Value 131(1)
Removing Nodes from a BST 132(2)
Counting Occurrences 134(5)
Exercises 137(2)
11 Graphs and Graph Algorithms 139(20)
Graph Definitions 139(2)
Real-World Systems Modeled by Graphs 141(1)
The Graph Class 141(4)
Representing Vertices 141(1)
Representing Edges 142(1)
Building a Graph 143(2)
Searching a Graph 145(4)
Depth-First Search 145(3)
Breadth-First Search 148(1)
Finding the Shortest Path 149(2)
Breadth-First Search Leads to Shortest 149(1)
Paths
Determining Paths 150(1)
Topological Sorting 151(8)
An Algorithm for Topological Sorting 152(1)
Implementing the Topological Sorting 152(5)
Algorithm
Exercises 157(2)
12 Sorting Algorithms 159(28)
An Array Test Bed 159(2)
Generating Random Data 161(1)
Basic Sorting Algorithms 161(9)
Bubble Sort 162(3)
Selection Sort 165(2)
Insertion Sort 167(1)
Timing Comparisons of the Basic Sorting 168(2)
Algorithms
Advanced Sorting Algorithms 170(17)
The Shellsort Algorithm 171(5)
The Mergesort Algorithm 176(5)
The Quicksort Algorithm 181(5)
Exercises 186(1)
13 Searching Algorithms 187(20)
Sequential Search 187(9)
Searching for Minimum and Maximum Values 190(3)
Using Self-Organizing Data 193(3)
Binary Search 196(6)
Counting Occurrences 200(2)
Searching Textual Data 202(5)
Exercises 205(2)
14 Advanced Algorithms 207(14)
Dynamic Programming 207(10)
A Dynamic Programming Example: 208(3)
Computing Fibonacci Numbers
Finding the Longest Common Substring 211(3)
The Knapsack Problem: A Recursive 214(1)
Solution
The Knapsack Problem: A Dynamic 215(2)
Programming Solution
Greedy Algorithms 217(4)
A First Greedy Algorithm Example: The 217(1)
Coin-Changing Problem
A Greedy Algorithm Solution to the 218(2)
Knapsack Problem
Exercises 220(1)
Index 221
新书报道