Java: Data Structures and Programming

ISBN-13: 9783642958533 / Angielski / Miękka / 2014 / 484 str.

Liwu Li

Opis

This book is written for practitioners of software development and for students of computer science who are interested in using the Java language to construct data structures. The book assumes general knowledge of computer programming but no experience of Java programming or object modeling for the readers. It intro duces the Java language and object model by going through examples of data modeling. The book emphasizes programming skills for developing various types of data structure and fundamental techniques for complexity analysis. The program ming skills are necessary for software development. The analysis techniques are needed to ensure performance of programs. The author has been responsible for teaching a data structure course for years. The book carries out his expectations for proficiency in both programming and complexity analysis from students. Several features of the book distinguish it from other books on data struc tures. A challenge for the book is relating the complexity analysis to the Java Virtual Machine, which isolates Java programmers from platform issues. The book devotes a chapter to discuss the structure of Java class files and the Java Virtual Machine. The book presents the problem of maximum flow and imple ments algorithms in Java to evaluate maximum flow for networks. It introduces persistent data structures, which may be included by some practitioners in their projects."

Spis treści

I Java Programming.- 1 Data Modeling in Java.- 1.1 Objects and Classes.- 1.1.1 The Notion of Object.- 1.1.2 Methods.- 1.1.3 Objects and Classes.- 1.2 Classes.- 1.2.1 Members of Classes.- 1.2.2 Object Creation.- 1.3 Class Inheritance.- 1.3.1 Java Subclassing Mechanism.- 1.3.2 Access Control.- 1.3.3 Abstract Method, Abstract Class, and Interface.- 1.3.4 Polymorphism.- 1.4 A Supermarket Application.- 1.5 Summary.- Assignment.- 2 The Java Language.- 2.1 Basic Elements of Java Program.- 2.1.1 White Space and Comment.- 2.1.2 Token.- 2.2 Flow of Control.- 2.2.1 Statement.- 2.2.2 Exception Handling.- 2.2.3 Thread and Multithread Programming.- 2.3 Standard Java Classes.- 2.3.1 Class Object.- 2.3.2 Class String.- 2.3.3 Input/Output Streams.- 2.3.4 Wrapper Classes.- 2.4 Reflection Model.- 2.4.1 Java Core Reflection API.- 2.4.2 Class Class.- 2.4.3 Classes Field, Method, and Constructor.- 2.5 Inner Classes.- 2.5.1 Scopes of Classes.- 2.5.2 Data Organization and Adapter Classes.- 2.6 Summary.- Assignment.- 3 Programming in Java.- 3.1 Java Programs.- 3.1.1 Applet Programming.- 3.1.2 Application Programming.- 3.2 Graphics Programming in Java.- 3.2.1 Class Graphics.- 3.2.2 Graphics Attributes.- 3.2.3 Graphical Operations.- 3.3 GUI Construction.- 3.3.1 GUI Components.- 3.3.2 Layout Classes.- 3.3.3 Event Delegation Model.- 3.4 Utility Classes and Object Reflection.- 3.4.1 Utility Classes — System, Math, and Random.- 3.4.2 Method Benchmarking.- 3.5 Summary.- Assignment.- 4 Java Data Structure Classes.- 4.1 Arrays.- 4.1.1 Array Objects.- 4.1.2 Multi-Dimensional Array.- 4.2 Vectors.- 4.2.1 Class Vector.- 4.2.2 Interface Enumeration.- 4.2.3 Queues.- 4.3 Class Stack.- 4.3.1 Class Stack.- 4.3.2 Construction and Operations of Stacks.- 4.4 Dictionary and Hash Tables.- 4.4.1 Class Dictionary.- 4.4.2 Hash Code.- 4.4.3 Class Hashtable.- 4.4.4 Hash Table Creation.- 4.4.5 Accessers and Mutaters of Hashtables.- 4.5 Class BitSet.- 4.5.1 Bit Sets.- 4.5.2 Accessers and Mutaters.- 4.6 Summary.- II Computation Analysis.- 5 Java Virtual Machine.- 5.1 Java Class Files.- 5.1.1 Class File Structure.- 5.1.2 Constants in Constant Pool.- 5.1.3 The code Attribute in method_inf? Structure.- 5.2 Java Compilation.- 5.2.1 Instructions of the JVM.- 5.2.2 Arithmetic Operations.- 5.2.3 Flow Controls.- 5.2.4 Method Invocations.- 5.3 Java Virtual Machine — An Abstract Machine.- 5.3.1 Java Runtime Systems.- 5.3.2 Objects and Types.- 5.3.3 Methods and Method Invocations.- 5.4 Summary.- 6 Complexity Analysis.- 6.1 Execution of Java Statements.- 6.1.1 Java Virtual Machine — A Model of Computation.- 6.1.2 Object Creation and Initialization.- 6.1.3 Arithmetic Operations.- 6.1.4 Branch Statements.- 6.1.5 Object Field Access.- 6.1.6 Local Variables.- 6.1.7 Method Invocation.- 6.1.8 Java Program Analysis.- 6.2 Asymptotic Analysis of Programs.- 6.2.1 Time and Space Functions.- 6.2.2 Dominance.- 6.2.3 Big-O and Big-? Notations.- 6.2.4 Complexity Categories.- 6.3 An Analysis of Binary Search.- 6.3.1 Linear Search.- 6.3.2 Binary Search.- 6.3.3 Recursion.- 6.3.4 Complexity of Recursive Methods.- 6.3.5 Space Complexity Analysis.- 6.4 Summary.- III Data Structures.- 7 Linear Data Structures.- 7.1 Linear Data Structure Sorting.- 7.1.1 Internal Sort.- 7.1.2 External Merge Sort.- 7.2 Searching Linear Data Structures.- 7.2.1 Searching.- 7.2.2 Fibonaccian Search.- 7.2.3 Interpolation Search.- 7.3 Linked Lists.- 7.3.1 Node Links.- 7.3.2 Doubly Linked List.- 7.4 Summary.- Assignment.- 8 Trees.- 8.1 Trees.- 8.1.1 General Trees.- 8.1.2 m-ary Trees.- 8.1.3 Binary Trees.- 8.2 Traversal of Trees.- 8.2.1 Traversal of General Trees.- 8.2.2 Traversal of Binary Trees.- 8.3 Binary Search Trees.- 8.3.1 The Notion of Binary Search Tree.- 8.3.2 AVL-Tree.- 8.4 B-Trees.- 8.4.1 B-Tree as m-ary Tree.- 8.4.2 Class B_Tree.- 8.4.3 Analysis of Class B_Tree.- 8.5 Summary.- 9 Graphs.- 9.1 Graphs.- 9.1.1 The Notion of Graph.- 9.1.2 Graphs with Adjacency Matrix.- 9.1.3 Graphs with Adjacency Vectors.- 9.2 Traversais of Graphs.- 9.2.1 The Traversal Problem.- 9.2.2 Traversing Graph with Adjacency Matrix.- 9.2.3 Traversing Graph with Adjacency Vectors.- 9.3 Computing Distances between Vertices.- 9.3.1 Single-Source Distances.- 9.3.2 All Distances in a Graph.- 9.4 Summary.- Assignment.- 10 Network Flows.- 10.1 Network and Network Flows.- 10.1.1 Networks.- 10.1.2 Flows in Networks.- 10.2 Maximum Flow in Networks.- 10.2.1 Network Representations.- 10.2.2 Preflowed Networks.- 10.2.3 Residual Networks.- 10.2.4 Maximizing Flows.- 10.3 Minimum Cuts.- 10.3.1 The Notion of Minimum Cut.- 10.3.2 Computing Minimum Cuts.- 10.4 Summary.- IV Data Persistence.- 11 Object Serialization.- 11.1 Serial Representation of Objects.- 11.1.1 Object Stream Format.- 11.1.2 Object Output Streams.- 11.2 Java Serialization Mechanism.- 11.2.1 Overview of Java Serialization.- 11.2.2 Java Serialization Classes and Interfaces.- 11.3 Externalizable Classes.- 11.3.1 Interface Externalizable.- 11.3.2 Externalizing Vectors.- 11.4 Summary.- 12 Data Structure Serialization.- 12.1 List Serialization.- 12.1.1 Output Format.- 12.1.2 Class SerializableList.- 12.2 Tree Serialization.- 12.2.1 Output Format.- 12.2.2 Class SerializableTree.- 12.3 Graph Serialization.- 12.3.1 Output Format.- 12.3.2 Class SerializableGraph.- 12.4 Summary.- Assignment.- Appendix A Binary File Dumping.- Al. Hexadecimal Convertion of Binary Files.- A2. Reading Utf8 Strings.- Appendix B References.

Blurb

This book is a methodical introduction to programming in Java that takes advantage of object-oriented data structures. It presents the Java Virtual Machine together with the analysis of algorithms and data structures in Java. The book applies the latest features of Java to develop various data structures, including linked lists, trees, graphs, and networks. An approach to efficient serialization for data structures is included.
The book shows how to incorporate advanced data structures in object-oriented programs, and thus promotes understanding of object-orientation and how it improves program efficiency. No prior knowledge of Java programming is presupposed, as the book is self-contained with full coverage of data modeling and object-oriented programming in Java.
The accompanying CD-ROM includes the source code of all the Java classes presented in the book.