CiNii 図書 - Data structures & their algorithms

Using only practically useful techniques, this book teaches methods for organizing, reorganizing, exploring, and retrieving data in digital computers, and the mathematical analysis of those techniques. The authors present analyses that are relatively brief and non-technical but illuminate the important performance characteristics of the algorithms. Data Structures and Their Algorithms covers algorithms, not the expression of algorithms in the syntax of particular programming languages. The authors have adopted a pseudocode notation that is readily understandable to programmers but has a simple syntax.

I. INTRODUCTION PROGRAMMING AS AN ENGINEERING ACTIVITY. Computer Science Background. Memory and Data in Von Neuman Computers. Notation for Programs
Locatives. Abstract Data Types. Mathematical Background. Finite and Infinite Series. Logarithms, Powers, and Exponentials. Order Notation. Recurrence Relations. Naive Probability Theory. II. ALGORITHM ANALYSIS. Properties of an Algorithm. Effectiveness
Correctness. Termination
Efficiency. Program Complexity. Exact vs. Growth-Rate Analysis. Principles of Mathematical Analysis. Expected Case and Amortized Analysis. Algorithm Paradigms. Brute-Force and Exhaustive Search. Greedy Algorithms. Dynamic Programming. NP Completeness. III. LISTS. List Operations. Basic List Representations. Stack Representation in Contiguous Memory. Queue Representation in Contiguous Memory. Stack Representation in Linked Memory. Queue Representation in Linked Memory. Stacks and Recursions. List Representations for Traversals. Doubly Linked Lists. IV. TREES BASIC DEFINITIONS. Special Kinds of Trees. Tree Operations and Traversals. Tree Implementations. Representation of Binary Trees. Representation of Ordered Trees. Representation of Complete Binary Trees. Implementing Tree Traversals and Scans. Stack-Based Traversals. Link Inversion Traversal. Scanning a Tree in Constant Space. ThreadedTrees. Implementing Level-Order Traversal. Summary. V. ARRAYS AND STRINGS. Arrays as Abstract Data Types. Multidimensional Arrays. Contiguous Representation of Arrays. Constant Time Initialization. Sparse Arrays. List Representations. Hierarchical Tables. Arrays with Special Shapes. Representation of Strings. Huffman Encoding
Lempel Ziv Encoding. String Searching. The Knuth-Morris-Pratt Algorithm. The Boyer-Moore Algorithm. Fingerprinting and the Karp-Rabin Algorithm. VI. LIST AND TREE IMPLEMENTATION OF SETS. Sets and Dictionaries as Abstract Data Types. Unordered Lists. Ordered Lists. Binary Search
Interpolation Search
Skip Lists. Binary Search Trees. Insertion
Deletion. Static Binary Search Trees. Optimal Trees
Probability-Balanced. Trees
Median Split Trees. VII. TREE STRUCTURES FOR DYNAMIC DICTIONARIES. AVL Trees: Insertion
Deletion. 23 Trees and Btrees. 23 Trees
Red-Black Trees. (a,b)Trees and B Trees. Self-Adjusting Binary Search Trees. VIII. SETS OF DIGITAL DATA. Bit Vectors. Tries and Digital Search Trees. Hashing Techniques. Chaining Strategies
Open Addressing Strategies. Deletions
Extendable Hashing. Hashing Functions. Hashing by Division
Hashing by Multiplication. Perfect Hashing of Static Data
Universal Classes of Hash Functions. IX. SETS WITH SPECIAL OPERATIONS. Priority Queues. Balanced Tree Implementations. Heaps
Leftist Trees. Disjoint Sets with Union. Up-Trees
Path Compression. Range Searching: kdTrees for Multidimensional Searching. Quad Trees
Grid Files. X. MEMORY MANAGEMENT. The Problem of Memory Management. Records of a Single Size. Reference Counts
Mark and Sweep. Garbage Collection
Collecting by Copying. Final Cautions on Garbage Collection. Compaction of Records of Various Sizes. Managing A Pool of Blocks of Various Sizes. Allocation Strategies
Data Structures for Freeing
Buddy Systems. XI. SORTING. Kinds of Sorting Algorithms. Insertion and Shell Sort. Selection and Heap Sort. Quick Sort. The Information-Theoretic Lower Bound. Digital Sorting. Bucket Sort
Radix Sort
Radix Exchange Sort. External Sorting. Merge Sorts
Polyphase Merge Sort. Generating the Initial Runs. Finding the Median. XII. GRAPHS. Graphs and Their Representation. Trees. Graph Searching. Breadth-First Search
Depth-First Search. Greedy Algorithms on Graphs. Minimum Spanning Trees
Single-Source Least-Cost Paths. All Pairs Least-Cost Paths. Network Flow. Finding Maximum Flows. Implementing the Max Flow. Algorithm. Applications of Max Flow. XIII. ENGINEERING WITH DATA STRUCTURES. Locatives. 067339736XT04062001

「Nielsen BookData」より

Data structures & their algorithms

著者

書誌事項

大学図書館所蔵全6件

この図書・雑誌をさがす

注記

内容説明・目次

詳細情報

書き出し