Data Structures (eBook)

Theory and Practice

A. T. Berztiss (Autor)

Werner Rheinboldt (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
458 Seiten
Elsevier Science (Verlag)
978-1-4832-6472-1 (ISBN)

Infos

Computer Science and Applied Mathematics: Data Structures: Theory and Practice focuses on the processes, methodologies, principles, and approaches involved in data structures, including algorithms, decision trees, Boolean functions, lattices, and matrices. The book first offers information on set theory, functions, and relations, and graph theory. Discussions focus on linear formulas of digraphs, isomorphism of digraphs, basic definitions in the theory of digraphs, Boolean functions and forms, lattices, indexed sets, algebra of sets, and order pair and related concepts. The text then examines strings, trees, and paths and cycles in digraphs. Topics include algebra of strings, Markov algorithms, algebraic structures, languages and grammars, decision trees and decision tables, trees as grammatic markers, shortest path problems, and representation of prefix formulas. The publication ponders on digraphs of programs, arrays, pushdown stores, lists, and list structures, and organization of files. Concerns include scatter storage techniques, files and secondary storage, representation of digraphs as list structures, storage of arrays, and sparse matrices. The text is a valuable reference for computer science experts, mathematicians, and researchers interested in data structures.

Inhalt

Front Cover 1
Data Structures: Theory and Practice 4
Copyright Page 5
Table of Contents 6
Preface 10
Acknowledgments 14
Part I: DISCRETE STRUCTURES IN MATHEMATICS 16
Chapter 1. Set Theory 18
1a. Basic Definitions 18
1b. Indexed Sets 22
1c. Complement of a Set 24
1d. Algebra of Sets 27
1e. Algebra of Sets as an Axiomatic Theory 30
1f. Venn Diagrams 38
1g. The Ordered Pair and Related Concepts 40
1h. Permutations and Combinations 43
Notes 54
Exercises 55
Chapter 2. Functions and Relations 58
2a. Functions 58
2b. Boolean Functions and Forms 62
2c. Applications of Boolean Functions 71
2d. Relations 85
2e. The Equivalence Relation 88
2f. Ordering Relations 91
2g. Lattices 97
2h. Abstract Algebras 101
Notes 108
Exercises 108
Chapter 3. Graph Theory 118
3a. Diagrams and Graphs 118
3b. Basic Definitions in the Theory of Digraphs 121
3c. Digraphs, Matrices, and Relations 127
3d. Connectedness in a Digraph 135
3e. Linear Formulas of Digraphs 138
3f. Trees 144
3g. Isomorphism of Digraphs 146
3h. Planar Graphs 150
Notes 155
Exercises 156
Chapter 4. Strings 160
4a. Algebraic Structures 160
4b. Algebra of Strings 166
4c. Markov Algorithms 168
4d. Languages and Grammars 174
4e. Languages and Automata 180
Notes 184
Exercises 184
Part II: APPLICATIONS OF STRUCTURES 188
Chapter 5. Trees 190
5a. Trees as Grammatic Markers 190
5b. Representation of Prefix Formulas 196
5c. Sort Trees and Dictionaries 200
5d. Decision Trees and Decision Tables 208
Notes 215
Exercises 216
Chapter 6. Paths and Cycles in Digraphs 220
6a. Shortest Path Problems 220
6b. Cycles 231
6c. A Scheduling Problem 238
6d. Critical Path Scheduling 241
Notes 245
Exercises 247
Chapter 7. Digraphs of Programs 252
7a. Flowchart Digraphs 252
7b. Detection of Programming Errors 255
7c. Segmentation of Programs 257
7d. Automatic Flowcharting 260
Notes 262
Exercises 263
Chapter 8. Other Applications of Graphs 266
8a. Flow Problems 266
8b. Graphs in Chemistry 273
8c. Graphs in Information Retrieval 278
Notes 281
Exercises 282
Part III: COMPUTER REPRESENTATION OF STRUCTURES 284
Chapter 9. Arrays 286
9a. Storage Media and Their Properties 286
9b. Storage of Arrays 289
9c. Sparse Matrices 291
9d. Storage Allocation at Execution Time 294
Notes 301
Exercises 302
Chapter 10. Pushdown Stores, Lists and List Structures 304
10a. Pushdown Stores 304
10b. Prefix, Postfix, and Infix Formulas 307
10c. Storage Levels for a Pushdown Store 310
10d. Lists—Introductory Concepts 311
10e. Formats of List Elements 317
10f. List Structures 320
10g. Threaded and Symmetric Lists 323
10h. Representation of Digraphs as List Structures 328
10i. Multiword List Elements 330
10j. Management of List Stores 331
10k. PL/I-Type Data Structures 334
Notes 338
Exercises 340
Chapter 11. Organization of Files 344
11a. Records and Files 344
11b. Indexed Files 347
11e. Scatter Storage Techniques 350
11d. Sorting 354
11e. Files and Secondary Storage 364
Notes 366
Exercises 367
Chapter 12. Programming Languages for Information Structures 370
12a. List Processing Languages 370
12b. String Processing Languages 381
12c. Extension of General Purpose Languages 392
Notes 402
Solutions to Selected Exercises 406
Bibliography 430
Index 446

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber ► Freizeit / Hobby ► Spielen / Raten
• Themenwelt: Schulbuch / Wörterbuch ► Lexikon / Chroniken
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-6472-6 / 1483264726
• ISBN-13: 978-1-4832-6472-1 / 9781483264721