دانلود کتاب Data Structures

فهرست مطالب :

Table of Contents Session 1: Basic Concepts 1.1: How do we solve a problem on a computer? 1.2: What is a data structure? 1.3: What is an algorithm? 1.4: Implementing ADT's 1.4.1: The contiguous or sequential design 1.4.2: The linked design 1.5: Putting it all together: formulating a solution to the ESP Summary Exercises Session 2: Mathematical Preliminaries 2.1: Mathematical notations and elementary functions 2.1.1: Floor, ceiling and mod functions 2.1.2: Polynomials 2.1.3: Exponentials 2.1.4: Logarithms 2.1.5: Factorials 2.1.6: Fibonacci numbers 2.2: Sets 2.3: Relations 2.4: Permutations and Combinations 2.4.1: Rule of sum and rule of product 2.4.2: Permutations 2.4.3: Combinations 2.5: Summations 2.5.1: Arithmetic series 2.5.2: Geometric series 2.5.3: Harmonic series 2.5.4: Miscellaneous sums 2.6: Recurrences 2.7: Methods of proof 2.7.1: Proof by mathematical induction 2.7.2: Proof by contradiction (reductio ad absurdum) 2.7.3: Proof by counterexample Summary Exercises Session 3: Algorithms 3.1: Communicating an algorithm 3.1.1: The EASY assignment statement 3.1.2: The EASY unconditional transfer statements 3.1.3: The EASY conditional transfer statements 3.1.4: The EASY iteration statements 3.1.5: The EASY input/output statements 3.1.6: The EASY declaration statements 3.1.7: The EASY control statements 3.1.8: EASY program structure 3.1.9: Sample EASY procedures 3.2: Analyzing an algorithm 3.2.1: Analysis of insertion sort 3.2.2: Asymptotic notations 3.2.3: The O-notation 3.2.4: The Ω-notation 3.2.5: The Θ-notation 3.2.6: The preponderance of the O-notation 3.2.7: Comparative growth of functions 3.2.8: Complexity classes Summary Exercises Session 4: Stacks 4.1: Sequential implementation of a stack 4.1.1: Implementing the auxiliary operations 4.1.2: Implementing the insert operation 4.1.3: Implementing the delete operation 4.1.4: A Pascal implementation of the array representation of a stack 4.1.5: A C implementation of the array representation of a stack 4.2: Linked list inplementation of a stack 4.2.1: Implementing the auxiliary stack operations 4.2.2: Implementing the insert operation 4.2.3: Implementing the delete operation 4.2.4: A Pascal implementation of the linked list representation of a stack 4.2.5: A C implementation of the linked list representation of a stack 4.3: Application of stacks 4.3.1: A simple pattern recognition problem 4.3.2: Conversion of arithmetic expressions from infix to postfix form 4.4: Sequential implementation of multiple stacks 4.4.1: The coexistence of two stacks in a single array 4.4.2: The coexistence of three or more stacks in a single array 4.4.3: Reallocating memory at stack overflow Summary Exercises Session 5: Queues and Deques 5.1: Sequential implementation of a straight queue 5.1.1: Implementing the insert operation 5.1.2: Implementing the delete operation 5.2: Sequential implementation of a circular queue 5.2.1: Implementing the insert and delete operations for a circular queue 5.2.2: A C implementation of the array representation of a circular queue 5.3: Linked list implementation of a queue 5.3.1: Implementing the insert operation 5.3.2: Implementing the delete operation 5.3.3: A C implementation of the linked list representation of a queue 5.4: Application of queues: topological sorting 5.5: The deque as an abstract data type 5.6: Sequential implementation of a straight deque 5.6.1: Implementing the insert operation 5.6.2: Implementing the delete operation 5.7: Sequential implementation of a circular deque 5.7.1: Implementing the insert and delete operations for a circular deque 5.8: Linked list implementation of a deque 5.8.1: Implementing the insert and delete operations Summary Exercises Session 6: Binary trees 6.1: Definitions and related concepts 6.2: Binary tree traversals 6.3: Binary tree representation in computer memory 6.4: Implementing the traversal algorithms 6.4.1: Recursive implementation of preorder and postorder traversal 6.4.2: Iterative implementation of preorder and postorder traversal 6.4.3: Applications of the traversal algorithms to other operations on binary trees 6.5: Threaded binary trees 6.5.1: Finding successors and predecessors in a threaded binary tree 6.5.2: Traversing inorder threaded binary trees 6.5.3: Growing threaded binary trees 6.5.4: Similarity and equivalence of binary trees 6.6: Traversal by link inversion 6.7: Siklossy traversal Summary Exercises Session 7: Applications of binary trees 7.1: Calculating conveyance losses in an irrigation network 7.2: Heaps and the heapsort algorithm 7.2.1: Sift-up: converting a complete binary tree into a heap 7.2.2: The heapsort algorithm of Floyd and Williams 7.3: Priority queues 7.3.1: Unsorted array implementation of a priority queue 7.3.2: Sorted array implementation of a priority queue 7.3.3: Heap implementation of a priority queue Summary Exercises Session 8: Trees and forests 8.1: Definition and related concepts 8.2: Natural correspondence 8.3: Forest traversal 8.4: Linked representation for trees and forests 8.5: Sequential representation for trees and forests 8.5.1: Representing trees and forests using links and tags 8.5.2: Arithmetic tree representations 8.6: Trees and the equivalence problem 8.6.1: The equivalence problem 8.6.2: Degeneracy and the weighting rule for union 8.6.3: Path compression: the collapsing rule for find 8.6.4: Analysis of the union and find operations 8.6.5: Final solution to the equivalence problem Summary Exercises Session 9: Graphs 9.1: Some pertinent definitions and related concepts 9.2: Representation of graphs 9.2.1: Adjacency matrix representation of a graph 9.2.2: Adjacency lists representation of a graph 9.3: Graph traversals 9.3.1: Depth first search 9.3.2: Breadth first search 9.4: Some classical applications of DFS and BFS 9.4.1: Identifying directed acyclic graphs 9.4.2: Topological sorting 9.4.3: Finding the strongly connected components of a digraph 9.4.4: Finding articulation points and biconnected components of a connected undirected graph 9.4.5: Determining whether an undirected graph is acyclic Summary Exercises Session 10: Applications of graphs 10.1: Minimum-cost spanning trees for undirected graphs 10.1.1: Prim's algorithm 10.1.2: Kruskal's algorithm 10.2: Shortest path problems for directed graphs 10.2.1: Dijkstra's algorithm for the SSSP problem 10.2.2: Floyd's algorithm for the APSP problem 10.2.3: Warshall's algorithm and transitive closure Summary Exercises Session 11: Linear lists 11.1: Linear Lists 11.2: Sequential representation of linear lists 11.3: Linked representation of linear lists 11.3.1: Straight singly-linked linear list 11.3.2: Straight singly-linked linear list with a list head 11.3.3: Circular singly-linked linear list 11.3.4: Circular singly-linked linear list with a list head 11.3.5: Doubly-linked linear lists 11.4: Linear lists and polynomial arithmetic 11.5: Linear lists and multiple-precision integer arithmetic 11.5.1: Integer addition and subtraction 11.5.2: Integer multiplication 11.5.3: Representing long integers in computer memory 11.5.4: EASY procedures for multiple-presicion integer arithmetic 11.6: Linear lists and dynamic storage management 11.6.1: The memory pool 11.6.2: Sequential-fit methods: reservation 11.6.3: Sequential-fit methods: liberation 11.6.4: Buddy-system methods: reservation and liberation 11.7: Linear lists and UPCAT processing 11.7.1: Determining degree program qualifiers within a campus 11.7.2: Implementation issues 11.7.3: Sample EASY procedures Summary Exercises Session 12: Generalized lists 12.1: Definitions and related concepts 12.2: Representing lists in computer memory 12.3: Implementing some basic operations on generalized lists 12.4: Traversing pure lists 12.5: Automatic storage reclamation 12.5.1: Algorithms for marking and gathering Summary Exercises Session 13: Sequential tables 13.1: The table ADT 13.2: Direct-address table 13.3: Static sequential tables 13.3.1: Linear serach in a static sequential table 13.3.2: Binary search in an ordered static sequential table 13.3.3: Multiplicative binary search 13.3.4: Fibonaccian search in an ordered sequential table Summary Exercises Session 14: Binary search trees 14.1: Binary search trees 14.1.1: Implementing some basic operations for dynamic tables 14.1.2: Analysis of BST search 14.2: Height-balanced binary search trees 14.3: Rotations on AVL trees 14.4: Optimum binary search trees Summary Exercises Session 15: Hash tables 15.1: Converting keys to numbers 15.2: Choosing a hash function 15.2.1: The division method 15.2.2: The multiplicative method 15.3: Collision resolution by chaining 15.3.1: EASY procedures for chained hash tables 15.3.2: Analysis of hashing with collision resolution by chaining 15.4: Collision resolution by open addressing 15.4.1: Linear probing 15.4.2: Quadratic probing 15.4.3: Double hashing 15.4.4: EASY procedures for open-address hash tables 15.4.5: Ordered open-address hash tables 15.4.6: Analysis of hashing with collision resolution by open addressing Summary Exercises Bibliography Index