Introducing Data Structures with Java

Introducing Data Structures with Java

by David Cousins
Released March 2013
Publisher(s): Pearson Education India
ISBN: 9788131758649

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Introducing Data Structures with Java sets out to provide a firm understanding of dealing with arrays, lists, queues, stacks, binary trees and graphs, and with algorithms for operations such as searching and sorting. Practical implementation, to promote sound understanding, is a key feature, and many example programs are developed, using a clear design process; full source code listings are supplied in each chapter and all of the programs are supplied on the CD-ROM.

Download Companion Content: http://www.pearsoned.co.in/prc/book/david-cousins-introducing-data-structures-with-java-1e--1/9788131758649

Table of contents

  1. Cover
  2. Title Page
  3. Contents
  4. Dedication
  5. About the Author
  6. Preface
  7. 1. Some Basic Ideas
    1. 1.1 Introduction
    2. 1.2 What is a computer program?
    3. 1.3 Advances in processing technology
    4. 1.4 Executing a program
    5. 1.5 High-level languages
    6. 1.6 Program control structures
    7. 1.7 Using pseudocode
    8. 1.8 Top-down design with stepwise refinement
    9. 1.9 O-O programming
      1. 1.9.1 What are objects?
      2. 1.9.2 Object classes
      3. 1.9.3 Programs as classes
      4. 1.10 Summary
      5. Exercises
  8. 2. Data Types
    1. 2.1 Introduction
    2. 2.2 Data types and variables
      1. 2.2.1 Operations on integers
      2. 2.2.2 Boolean operations
    3. 2.3 Conversion between data types
      1. 2.3.1 Cast operations
      2. 2.3.2 String conversions
    4. 2.4 Other data types
    5. 2.5 Summary
  9. 3. Using Java
    1. 3.1 Introduction
    2. 3.2 The Java language
      1. 3.2.1 A simple Java program
      2. 3.2.2 Input and output in Java
      3. 3.2.3 Loop control structures
      4. 3.2.4 Selection control structures
      5. 3.2.5 Functions and parameters
      6. 3.2.6 Creating objects in Java
    3. 3.3 Running the example programs
    4. 3.4 Using the Sun JDK
    5. 3.5 Compiling Java code
    6. 3.6 Running the programs
    7. 3.7 Summary
    8. Exercises
      1. Practical exercises
  10. 4. File Input and Output
    1. 4.1 Introduction
    2. 4.2 Text and binary files
    3. 4.3 Reading input from a file
    4. 4.4 Storing numerical data
    5. 4.5 Writing output to a file
    6. 4.6 Summary
    7. 4.7 Code listings
  11. 5. Array Data Structures
    1. 5.1 Introduction
    2. 5.2 What is an array?
    3. 5.3 A simple array application
    4. 5.4 Arrays of other data
    5. 5.5 Multidimensioned arrays
    6. 5.6 Populating the array—nested loops
    7. 5.7 Accessing an array column by column
    8. 5.8 Further uses for the application
    9. 5.9 Dynamically declaring arrays
    10. 5.10 Pointers/references
    11. 5.11 The ‘garbage’ problem
    12. 5.12 Summary
    13. 5.13 Code listing
    14. Exercises
      1. Practical exercises
  12. 6. Searching Arrays
    1. 6.1 Introduction
    2. 6.2 A simple search strategy
      1. 6.2.1 Unordered array
      2. 6.2.2 Ordered array
    3. 6.3 Algorithm efficiency and ‘Big-O’ expression
      1. 6.3.1 O(N)—linear search
      2. 6.3.2 O(log2N)—binary search
    4. 6.4 Summary
    5. Code listings
    6. Exercises
      1. Practical exercise
  13. 7. Hashing and Hash Tables
    1. 7.1 Introduction
    2. 7.2 An alternative array storage model
    3. 7.3 Hashing
      1. 7.3.1 A simple hash function
      2. 7.3.2 Collisions
      3. 7.3.3 Resolving collisions
      4. 7.3.4 Marking free locations
      5. 7.3.5 Table full condition
      6. 7.3.6 Retrieving items
      7. 7.3.7 Deleting keys
      8. 7.3.8 Table size and number of collisions
      9. 7.3.9 Non-integer keys
    4. 7.4 Efficiency of hash function
    5. 7.5 Implementing a hash table in Java
      1. 7.5.1 Operation: initialize table
      2. 7.5.2 Operation: insert an item
      3. 7.5.3 Operation: search for an item
      4. 7.5.4 Operation: delete an item
      5. 7.5.5 Operation: display table contents
    6. 7.6 File storage and access
    7. 7.7 Summary
      1. Code listing
      2. Exercises
  14. 8. Sorting Arrays—Selection, Bubble, Insertion, Merge and Quick Sorts
    1. 8.1 Introduction
    2. 8.2 General principles of sorting
      1. 8.2.1 Selection sort
      2. 8.2.2 Bubble sort
      3. 8.2.3 Insertion sort
      4. 8.2.4 Merge sort
      5. 8.2.5 Quick sort
    3. 8.3 Comparing sorting efficiencies
    4. 8.4 Summary
    5. 8.5 Code listings
    6. Exercises
      1. Practical exercises
  15. 9. Linked Lists
    1. 9.1 Introduction
    2. 9.2 An array implementation of a list
    3. 9.3 What is a dynamic linked list?
      1. 9.3.1 Operation: initialize the list
      2. 9.3.2 Operation: append a new item (unordered list)
      3. 9.3.3 Operation: output list contents
      4. 9.3.4 Operation: return number of list records
      5. 9.3.5 Operation: search the list
      6. 9.3.6 Operation: delete an item
      7. 9.3.7 Operation: check for empty list
      8. 9.3.8 Operation: insertion (to create an ordered list)
    4. 9.4 A list class
      1. 9.4.1 The constructor and the isEmpty function
      2. 9.4.2 The insert operation
      3. 9.4.3 The search method
      4. 9.4.4 The deleteltem method
    5. 9.5 Circular linked lists
    6. 9.6 Doubly linked lists
      1. 9.6.1 Insertion to a doubly linked list
      2. 9.6.2 Search
      3. 9.6.3 Deletion from a doubly linked list
      4. 9.6.4 Writing out the list
    7. 9.7 An array implementation
      1. 9.7.1 Insertion
      2. 9.7.2 Deletion
      3. 9.7.3 Searching for an item
      4. 9.7.4 Writing out the list contents
    8. 9.8 Conclusion
    9. 9.9 Summary
    10. 9.10 Code listings
    11. Exercises
      1. Practical exercise
  16. 10. Queues
    1. 10.1 Introduction
    2. 10.2 Queue examples
    3. 10.3 Implementing a queue dynamically
    4. 10.4 Queue operations
      1. 10.4.1 Operation: initialization
      2. 10.4.2 Operation: en-queue
      3. 10.4.3 Operation: check for empty queue
      4. 10.4.4 Operation: de-queue
    5. 10.5 A dynamic queue class
    6. 10.6 An alternative implementation
      1. 10.6.1 En-queue operation
      2. 10.6.2 De-queue operation
      3. 10.6.3 Alternative de-queueing strategy
    7. 10.7 Practical implementation
      1. 10.7.1 Operation: create an empty queue
      2. 10.7.2 Operation: test for empty queue
      3. 10.7.3 Operation: test for queue full condition
      4. 10.7.4 Operation: en-queue
      5. 10.7.5 Operation: de-queue
      6. 10.7.6 Operation: view the head item
    8. 10.8 Initializing the queue with a constructor method
      1. 10.8.1 The de-queue function
      2. 10.8.2 The view head item function
    9. 10.9 A test program
    10. 10.10 Priority queue
      1. 10.10.1 Creating a priority queue as a doubly linked list
      2. 10.10.2 Implementing the priority queue class
    11. 10.11 Summary
    12. 10.12 Code listings
    13. Exercises
      1. Practical exercises
  17. 11. Stacks
    1. 11.1 Introduction
    2. 11.2 Stacks and their operations
      1. 11.2.1 The stack abstract data type (ADT)
    3. 11.3 Practical implementation of the ADT
      1. 11.3.1 Stack—array implementation
      2. 11.3.2 Stack class implemented as an array
      3. 11.3.3 Stack implementation as a dynamic structure
    4. 11.4 Applications of stacks
      1. 11.4.1 Returning addresses from sub-programs, functions and procedures
      2. 11.4.2 Stacks and recursion
      3. 11.4.3 Evaluating expressions
    5. 11.5 Other stack applications
    6. 11.6 Summary
    7. 11.7 Code listings
    8. Exercises
      1. Practical exercises
  18. 12. Binary Trees
    1. 12.1 Introduction
    2. 12.2 A binary tree abstract data type (ADT)
    3. 12.3 Tree operations
    4. 12.4 Trees and sub-trees
    5. 12.5 Levels of a tree
      1. 12.5.1 Numbers of nodes at a level
    6. 12.6 Binary tree terminology
      1. 12.6.1 Full trees
      2. 12.6.2 Complete trees
      3. 12.6.3 Tree height
      4. 12.6.4 Balanced trees
      5. 12.6.5 Self-balancing trees
    7. 12.7 The ADT for a BST
    8. 12.8 Creating a BST
      1. 12.8.1 Tree node class
      2. 12.8.2 Operation: initialization
      3. 12.8.3 Operation: populating the tree by insertion
      4. 12.8.4 An alternative approach
      5. 12.8.5 Operation: searching the tree
      6. 12.8.6 Operation: tree traversal
      7. 12.8.7 Operation: deleting nodes
    9. 12.9 Implementing the tree class
    10. 12.10 Efficiency of BST search and retrieval
    11. 12.11 An alternative BST representation
      1. 12.11.1 A tree as an array
      2. 12.11.2 Unoccupied and leaf nodes
    12. 12.12 ‘Threaded’ binary trees
    13. 12.13 Expression trees
      1. 12.13.1 Evaluating an expression
      2. 12.13.2 Conversion from infix to postfix notation
    14. 12.14 ‘Heaps’
      1. 12.14.1 Applications of heaps
    15. 12.15 Summary
    16. 12.16 Code listings
    17. Exercises
      1. Practical exercise
  19. 13. Graphs
    1. 13.1 Introduction
    2. 13.2 An example of non-hierarchical data
    3. 13.3 Directed/undirected graphs
    4. 13.4 Complete/incomplete graphs
    5. 13.5 Paths
    6. 13.6 Digraphs
    7. 13.7 Weighted graphs
    8. 13.8 A graph abstract data type (ADT)
      1. 13.8.1 Initializing a graph
      2. 13.8.2 Graph traversal
    9. 13.9 Representing a graph
      1. 13.9.1 Method 1—a simple list
      2. 13.9.2 Method 2—an ‘adjacency list’
      3. 13.9.3 Method 3—an adjacency matrix
    10. 13.10 Implementing the example graph class
      1. 13.10.1 Operation: setting up and initializing the graph
      2. 13.10.2 Display the matrix values
      3. 13.10.3 Breadth-first traversal
      4. 13.10.4 Depth-first traversal
    11. 13.11 Displaying the contents of the adjacency matrix
    12. 13.12 Java code for breadth-first traversal
    13. 13.13 Java code for depth-first traversal
    14. 13.14 And now … a simple route finding illustration
      1. 13.14.1 Possible route from Much Snoring to Little Snoring 266
      2. 13.14.2 Another possible route from Much Snoring to Little Snoring 267
      3. 13.14.3 Removing vertices on cyclic paths
      4. 13.14.4 Implementing the search
    15. 13.15 The graph class test program
    16. 13.16 Limitations of the path-searching function
    17. 13.17 Shortest path identification (Dijkstra’s method)
      1. 13.17.1 Finding the shortest path
      2. 13.17.2 Examine the neighbours of the starting node
      3. 13.17.3 Establish distances from A through each neighbour of the starting point
      4. 13.17.4 Applications of the algorithm
    18. 13.18 ‘Spanning trees’
      1. 13.18.1 Constructing a spanning tree
    19. 13.19 ‘Minimum spanning trees’ (MSTs)
      1. 13.19.1 Kruskal’s algorithm
      2. 13.19.2 Prim’s algorithm
    20. 13.20 Summary
    21. 13.21 Code listings
    22. Exercises
      1. Practical exercises
  20. 14. Case Study 1—A Student Grades Program 298
    1. 14.1 Introduction
    2. 14.2 The application
    3. 14.3 A suitable data structure
    4. 14.4 The operations
      1. 14.4.1 Search by name
      2. 14.4.2 Search by grade
      3. 14.4.3 Display the list
    5. 14.5 Reading from the file
    6. 14.6 Implementation of the program
      1. 14.6.1 Populating the list
      2. 14.6.2 Displaying all data
      3. 14.6.3 Search by name
      4. 14.6.4 Search by grade
      5. 14.6.5 Application main function
      6. 14.6.6 Output screenshots
    7. 14.7 Summary
    8. 14.8 Code listings
  21. 15. Case Study 2—Rn Inventory Table
    1. 15.1 Introduction
    2. 15.2 The application
    3. 15.3 Storing and accessing the data
    4. 15.4 Initializing the arrays
    5. 15.5 Adding a new product’s data
    6. 15.6 Searching for a product
    7. 15.7 Deleting an item
    8. 15.8 Amending the instock value
    9. 15.9 Writing out the table contents
    10. 15.10 Implementing the system
    11. 15.11 The main function code
    12. 15.12 Populate the table for testing purposes
    13. 15.13 Inserting a new item
    14. 15.14 Displaying the table contents
    15. 15.15 Search and update
    16. 15.16 Deleting an item from the table
    17. 15.17 Summary
    18. 15.18 Code listings
  22. 16. Case Study 3—A Flight Departures Timetable
    1. 16.1 Introduction
    2. 16.2 The application
    3. 16.3 Choice of data types and structures
    4. 16.4 Array representation
    5. 16.5 Linked list representation
      1. 16.5.1 Search methods
      2. 16.5.2 Deleting a flight
    6. 16.6 Array version
      1. 16.6.1 Deleting a record
      2. 16.6.2 Insertion of records
    7. 16.7 Summary
    8. 16.8 Code listings
  23. 17. Case Study 4—A Queue Simulation
    1. 17.1 Introduction
    2. 17.2 The application
    3. 17.3 Choosing priority values
    4. 17.4 Design
      1. 17.4.1 Generating priority values
      2. 17.4.2 Refinement of the ‘build queue’ step
      3. 17.4.3 Refinement of ‘display boarding queue’
      4. 17.4.4 The enQueue function
      5. 17.4.5 The deQueue operation
      6. 17.4.6 The buildQueue function
      7. 17.4.7 Display the boarding order
      8. 17.4.8 The simulation main function
      9. 17.4.9 Screenshots for two program runs, 30 passengers in each case
    5. 17.5 An alternative version—output to a file
      1. 17.5.1 File output
    6. 17.6 Summary
    7. 17.7 And finally, reader …
    8. 17.8 Code listings
  24. Appendix A
  25. Appendix B
  26. Copyright

Product information

  • Title: Introducing Data Structures with Java
  • Author(s): David Cousins
  • Release date: March 2013
  • Publisher(s): Pearson Education India
  • ISBN: 9788131758649