图书简介

1 Fundamental Concepts 1; 1.1 Introduction to Programming 1; 1.2 Object-oriented Programming 3; 1.3 Introduction to Data Structures 3; 1.3.1 Data 4; 1.3.2 Data type 4; 1.3.3 Data object 5; 1.3.4 Data structure 5; 1.3.5 Abstract data type 6; 1.4 Types of Data Structures 9; 1.4.1 Primitive and non-primitive data structures 9; 1.4.2 Linear and non-linear data structures 9; 1.4.3 Static and dynamic data structures 10; 1.4.4 Persistent and ephemeral data structures 10; 1.4.5 Sequential access and direct access data structures 11; 1.5 Introduction to Algorithms 11; 1.5.1 Characteristics of algorithms 12; 1.5.2 Algorithmics 13; 1.5.3 Algorithm design tools: Pseudocode and fl owchart 13; 1.6 Pseudocode 14; 1.6.1 Pseudocode notations 14; 1.6.2 Algorithm header 14; 1.6.3 Purpose 15; 1.6.4 Condition and return statements 15; 1.6.5 Statement numbers 16; 1.6.6 Variables 16; 1.6.7 Statement constructs 17; 1.6.8 Subalgorithms 18; 1.7 Relationship among data, data structures, and algorithms 20; 1.8 Implementation of data structures 21; 1.9 Flowcharts 22; 1.10 Analysis of Algorithms 22; 1.10.1 Complexity of algorithms 22; 1.10.2 Space complexity 23; 1.10.3 Time complexity 24; 1.10.4 Computing time complexity of an algorithm 24; 1.10.5 Big-O notation 25; 1.11 From Problem to Program 26; 1.12 Software Engineering 27; 1.12.1 Analysis phase 27; 1.12.2 Design phase 28; 1.12.3 Implementation phase 28; 1.12.4 Testing phase 29; 1.12.5 Verifi cation 29; 2 Linear Data Structure Using Arrays 34; 2.1 Sequential Organization 34; 2.2 Linear Data Structure Using Sequential Organization: Arrays 35; 2.3 Array as an Abstract Data Type 37; 2.4 Memory Representation and Address Calculation 39; 2.5 The Class Array 41; 2.5.1 Inserting an element into an array 43; 2.5.2 Deleting an element 45; 2.6 Arrays Using Template 47; 2.7 Multidimensional Arrays 48; 2.7.1 Two-dimensional arrays 48; 2.7.2 n-dimensional arrays 53; 2.8 Concept of Ordered List 58; 2.9 Single Variable Polynomial 59; 2.9.1 Representation using arrays 59; 2.9.2 Polynomial as array of structure 61; 2.9.3 Polynomial evaluation 62; 2.9.4 Polynomial addition 63; 2.9.5 Polynomial multiplication 67; 2.10 Array for Frequency Count 70; 2.11 Sparse Matrix 71; 2.11.1 Sparse matrix representation 73; 2.11.2 Sparse matrix addition 74; 2.11.3 Transpose of sparse matrix 78; 2.12 String Manipulation Using Array 85; 2.13 Pros and Cons of Arrays 90; 2.13.1 Characteristics 90; 2.13.2 Advantages 90; 2.13.3 Disadvantages 91; 2.13.4 Applications of arrays 91; 3 Stacks 96; 3.1 Concept of Stacks and Queues 96; 3.2 Stacks 97; 3.2.1 Primitive operations 98; 3.3 Stack Abstract Data Type 101; 3.4 Representation of Stacks Using Sequential Organization (Arrays) 102; 3.4.1 Create 104; 3.4.2 Empty 104; 3.4.3 GetTop 104; 3.4.4 Push 105; 3.4.5 Pop 105; 3.5 Stacks Using Template 107; 3.6 Multiple Stacks 109; 3.7 Applications of Stack 112; 3.8 Expression Evaluation and Conversion 112; 3.8.1 Polish notation and expression conversion 114; 3.8.2 Need for prefi x and postfi x expressions 115; 3.8.3 Postfi x expression evaluation 115; 3.9 Processing of Function Calls 139; 3.10 Reversing a String with a Stack 141; 3.11 Checking Correctness of Well-formed Parentheses 142; 3.12 Recursion 143; 3.13 Parsing Computer Programs 144; 3.14 Backtracking Algorithms 144; 3.15 Converting Decimal Numbers to Binary 144; 4 Recursion 151; 4.1 Introduction 151; 4.2 Recurrence 154; 4.3 Use of Stack in Recursion 155; 4.4 Variants of Recursion 156; 4.4.1 Direct recursion 157; 4.4.2 Indirect recursion 157; 4.4.3 Tail recursion 158; 4.4.4 Linear recursion 159; 4.4.5 Tree recursion 159; 4.5 Execution of Recursive Calls 160; 4.6 Recursive Functions 161; 4.6.1 Writing recursive code 163; 4.6.2 Tower of hanoi: An example of recursion 163; 4.6.3 Checking for correctness 165; 4.6.4 Things to remember 166; 4.7 Iteration Versus Recursion 166; 4.7.1 Demerits of recursive algorithms 166; 4.7.2 Demerits of iterative methods 167; 4.8 Simulating Recursion Using Stack (Eliminating Recursion) 167; 4.9 Applications of Recursion 168; 5 Queues 174; 5.1 Concept of Queues 174; 5.2 Queue as Abstract Data Type 175; 5.3 Realization of Queues Using Arrays 176; 5.4 Circular Queue 182; 5.4.1 Advantages of using circular queues 186; 5.5 Multi-queues 186; 5.6 Deque 187; 5.7 Priority Queue 188; 5.7.1 Array implementation of priority queue 191; 5.8 Applications of Queues 191; 5.8.1 Josephus problem 192; 5.8.2 Job scheduling 193; 5.8.3 Simulation 194; 5.9 Queues Using Templates 195; 6 Linked Lists 202; 6.1 Introduction 202; 6.2 Linked List 203; 6.2.1 Comparison of sequential and linked organizations 206; 6.2.2 Linked list terminology 207; 6.2.3 Primitive operations 208; 6.3 Realization of Linked Lists 208; 6.3.1 Realization of linked list using arrays 209; 6.3.2 Linked list using dynamic memory management 210; 6.4 Dynamic Memory Management 211; 6.4.1 Dynamic memory management in C++ with new and; delete operators 212; 6.5 Linked List Abstract Data Type 214; 6.5.1 Data structure of node 216; 6.5.2 Insertion of a node 219; 6.5.3 Linked list traversal 225; 6.5.4 Deletion of a node 228; 6.6 Linked List Variants 231; 6.6.1 Head pointer and header node 231; 6.6.2 Types of linked list 232; 6.6.3 Linear and circular linked lists 233; 6.7 Doubly Linked List 234; 6.7.1 Creation of doubly linked list 235; 6.7.2 Deletion of a node from a doubly linked list 238; 6.7.3 Insertion of a node in a doubly linked list 241; 6.7.4 Traversal of DLL 243; 6.8 Circular Linked List 244; 6.8.1 Singly circular linked list 245; 6.8.2 Circular linked list with header node 246; 6.8.3 Doubly circular linked list 247; 6.9 Polynomial Manipulations 248; 6.9.1 Polynomial evaluation 250; 6.9.2 Polynomial addition 251; 6.9.3 Multiplication of two polynomials 254; 6.10 Representation of Sparse Matrix Using Linked List 257; 6.11 Linked Stack 259; 6.11.1 Class for linked stack 259; 6.11.2 Operations on linked stack 261; 6.12 Linked Queue 263; 6.12.1 Erasing a linked queue 267; 6.13 Generalized Linked List 267; 6.13.1 Defi nition 268; 6.13.2 Applications 269; 6.13.3 Representation of polynomials using generalized linked list 272; 6.13.4 Representation of sets using generalized linked list 277; 6.14 More on Linked Lists 279; 6.14.1 Copying a linked list 279; 16.4.2 Computing the length of a linked list 280; 6.14.3 Reversing singly linked list without temporary storage 281; 6.14.4 Concatenating two linked lists 282; 6.14.5 Erasing the linked list 282; 6.15 Application of Linked List-Garbage Collection 283; 7 Trees 289; 7.1 Introduction 289; 7.1.1 Basic terminology 290; 7.1.2 General trees 295; 7.1.3 Representation of a general tree 298; 7.2 Types of Trees 299; 7.3 Binary Tree 302; 7.3.1 Properties of a binary tree 303; 7.4 Binary Tree Abstract Data Type 306; 7.5 Realization of a Binary Tree 308; 7.5.1 Array implementation of binary trees 308; 7.5.2 Linked implementation of binary trees 311; 7.6 Insertion of a Node in Binary Tree 315; 7.7 Binary Tree Traversal 316; 7.7.1 Preorder traversal 317; 7.7.2 Inorder traversal 318; 7.7.3 Postorder traversal 319; 7.7.4 Non-recursive implementation of traversals 320; 7.7.5 Formation of binary tree from its traversals 326; 7.7.6 Breadth- and depth-fi rst traversals 330; 7.8 Other Tree Operations 333; 7.8.1 Counting nodes 333; 7.8.2 Counting leaf nodes 333; 7.8.3 Computing height of binary tree 333; 7.8.4 Getting mirror, replica, or tree interchange of binary tree 334; 7.8.5 Copying binary tree 334; 7.8.6 Equality test 334; 7.9 Conversion of General Tree to Binary Tree 335; 7.10 Binary Search Tree 339; 7.10.1 Inserting a node 341; 7.10.2 Searching for a key 346; 7.10.3 Deleting a node 348; 7.10.4 Binary tree and binary search tree 354; 7.11 Threaded Binary Tree 355; 7.11.1 Threading a binary tree 358; 7.11.2 Right-threaded binary tree 364; 7.11.3 Inorder traversal 364; 7.11.4 Preorder traversal 366; 7.11.5 Insert to right of a node 366; 7.11.6 Deleting a node 368; 7.11.7 Pros and cons 368; 7.12 Applications of Binary Trees 369; 7.12.1 Expression tree 369; 7.12.2 Decision tree 373; 7.12.3 Huffman’s coding 375; 7.12.4 Game trees 378; 8 Graphs 388; 8.1 Introduction 388; 8.2 Graph Abstract Data Type 389; 8.3 Representation of Graphs 391; 8.3.1 Adjacency matrix 391; 8.3.2 Adjacency list 394; 8.3.3 Adjacency multilist 399; 8.3.4 Inverse adjacency list 400; 8.3.5 Comparison of sequential and linked representations 401; 8.4 Graph Traversal 401; 8.4.1 Depth-fi rst search 401; 8.4.2 Breadth-fi rst search 408; 8.5 Spanning Tree 412; 8.5.1 Connected components 413; 8.5.2 Prim’s algorithm 413; 8.5.3 Kruskal’s algorithm 418; 8.5.4 Biconnected components 423; 8.5.5 Disjoint set operations 424; 8.6 Shortest Path Algorithm 424; 9 Searching and Sorting 438; 9.1 Searching 438; 9.2 Search Techniques 439; 9.2.1 Sequential search 439; 9.2.2 Binary search 444; 9.2.3 Fibonacci search 447; 9.2.4 Indexed sequential search 450; 9.2.5 Hashed search 454; 9.3 Sorting 455; 9.3.1 Types of sorting 455; 9.3.2 General sort concepts 457; 9.3.3 Bubble sort 458; 9.3.4 Insertion sort 462; 9.3.5 Selection sort 466; 9.3.6 Quick sort 469; 9.3.7 Heap sort 474; 9.3.8 Shell sort 478; 9.3.9 Bucket sort 479; 9.3.10 Radix sort 481; 9.3.11 File sort 483; 9.3.12 Merge sort 484; 9.4 Multiway Merge and Polyphase Merge 487; 9.4.1 Comparison of ordinary merge sort and polyphase sort 487; 9.5 Comparison of All Sorting Methods 489; 10 Search Trees 498; 10.1 Symbol Table 498; 10.1.1 Representation of symbol table 499; 10.2 Optimal Binary Search Tree 500; 10.3 AVL Tree (Height-balanced Tree) 519; 10.3.1 Implementation of AVL technique 528; 10.3.2 Insertions and deletions in AVL tree 533; 11 Hashing 547; 11.1 Introduction 547; 11.2 Key Terms and Issues 549; 11.3 Hash Functions 551; 11.3.1 Good hash function 552; 11.3.2 Division method 552; 11.3.3 Multiplication method 552; 11.3.4 Extraction method 553; 11.3.5 Mid-square hashing 554; 11.3.6 Folding technique 554; 11.3.7 Rotation 555; 11.3.8 Universal hashing 555; 11.4 Collision Resolution Strategies 555; 11.4.1 Open addressing 556; 11.4.2 Chaining 566; 11.5 Hash Table Overfl ow 569; 11.5.1 Open addressing for overfl ow handling 570; 11.5.2 Overfl ow handling by chaining 570; 11.6 Extendible Hashing 571; 11.7 Dictionary 573; 11.8 Skip List 573; 11.9 Comparison of Hashing and Skip Lists 574; 12 Heaps 578; 12.1 Basic Concepts 578; 12.1.1 Min-heap and max-heap 579; 12.2 Implementation of Heap 581; 12.3 Heap as Abstract Data Type 582; 12.3.1 Operations on heaps 583; DETAILED CONTENTS ix; DSUC Detailed_Contents V2 November 18, 2011 5:59 PM Page ix; 12.4 Heap Applications 594; 12.5 Heap Sort 595; 12.6 Binomial Trees and Heaps 601; 12.6.1 Binomial trees 601; 12.6.2 Binomial heap 602; 12.6.3 Representation of binomial heap 603; 12.6.4 Operations on binomial heaps 604; 12.7 Fibonacci Heap 604; 12.7.1 Representation of Fibonacci heap 604; 12.7.2 Operations on Fibonacci heaps 606; 13 Indexing and Multiway Trees 612; 13.1 Introduction 612; 13.2 Indexing 613; 13.2.1 Indexing techniques 614; 13.3 Types of Search Trees 616; 13.3.1 Multiway search tree 616; 13.3.2 B-tree 617; 13.3.3 B+ tree 647; 13.3.4 Trie tree 651; 13.3.5 Splay tree 653; 13.3.6 Red-black tree 654; 13.3.7 K-dimensional tree 656; 13.3.8 AA Tree 657; 14 Files 662; 14.1 Introduction 662; 14.2 External Storage Devices 663; 14.2.1 Magnetic tape 664; 14.2.2 Magnetic drum 664; 14.2.3 Magnetic disk 664; 14.3 File Organization 665; 14.3.1 Schemes of fi le organization 665; 14.3.2 Factors affecting fi le organization 666; 14.3.3 Factors involved in selecting fi le organization 666; 14.4 Files Using C++ 667; 14.4.1 File I/O classes 667; 14.4.2 Primitive functions 667; 14.4.3 Binary and text fi les 672; 14.5 Sequential File Organization 675; 14.5.1 Primitive operations 676; 14.5.2 Advantages 679; 14.5.3 Drawbacks 679; 14.6 Direct Access File Organization 679; 14.6.1 Primitive operations 680; 14.7 Indexed Sequential File Organization 686; 14.7.1 Types of indices 686; 14.7.2 Structure of indexed sequential fi le 687; 14.7.3 Characteristics of indexed sequential fi le 688; 14.8 Linked Organization 693; 14.8.1 Multilist fi les 693; 14.8.2 Coral rings 695; 14.8.3 Inverted fi les 695; 14.8.4 Cellular partitions 696; 15 Standard Template Library 703; 15.1 Abstract Data Type 703; 15.1.1 Abstract data type and data structures 704; 15.1.2 Creating abstract data types 704; 15.1.3 Stack abstract data type 705; 15.2 Survey of Programming Techniques 706; 15.3 Standard Template Library 718; 15.3.1 Containers 718; 15.3.2 Algorithms 730; 15.3.3 Iterators 733; 15.3.4 Function Objects 737; 16 Algorithm Analysis and Design 741; 16.1 Introduction 741; 16.1.1 Algorithm analysis 742; 16.1.2 Asymptotic notations ( , q, O) 742; 16.2 Divide-and-Conquer 743; 16.2.1 Unique characteristics and use 743; 16.2.2 General method 744; 16.2.3 Binary search 745; 16.2.4 Merge sort 747; 16.2.5 Quick sort 750; 16.2.6 Strassen’s algorithm for matrix multiplication 756; 16.3 Greedy Method 758; 16.3.1 General greedy method 758; 16.3.2 Knapsack problem 759; 16.4 Dynamic Programming 762; 16.4.1 The General method 762; 16.4.2 Elements of dynamic programming 763; 16.4.3 Principle of optimality 764; 16.4.4 Limitations of dynamic programming 765; 16.4.5 Knapsack problem 766; 16.5 Pattern Matching 770; 16.5.1 Brute-force approach 771; 16.5.2 Boyer-Moore algorithm 774; 16.5.3 Knuth-Morris-Pratt algorithm 775; 16.6 Tries 781; 16.6.1 Standard tries 782; 16.6.2 Compressed tries 783; 16.6.3 Suffi x tries 783; Appendix 788; Index 827

Trade Policy 买家须知