Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com

Study guide: Datastructures and algorithms, Part 2

Brush up on Java terms, learn tips and cautions, review homework assignments, and read answers to student questions

By Jeff Friesen, JavaWorld.com, 06/06/03

  • Print
  • Feedback
.

Glossary of terms

binary trees
Trees based on nodes that each reference a maximum of two children.


child node
In a tree, a node referenced from a node above.


circular linked list
A linked list where the last node links to the first node.


doubly linked list
A linked list of nodes, where each node has a pair of link fields.


insertion sort
An algorithm that builds either a singly linked list or a doubly linked list in order of some nonlink field by identifying the insert position for each new node and inserting that node at the insert position.


leaf nodes
In a tree, nodes without children.


link
The reference in a link field.


link field
A field whose reference type is the class name.


linked list
A sequence of nodes that interconnect via the links in their link fields.


node
An object you create from a self-referential class.


parent node
In a tree, a node that references a node below.


pop
Retrieve/delete.


push
Insert.


queue
A datastructure where data-item insertions are made at one end (the queue's rear) and data-item retrievals/deletions are made at the other end (the queue's front).


recursion
The act of a method repeatedly calling itself.


root
The top node in a tree.


self-referential class
A class with at least one field whose reference type is the class name.


singly linked list
A linked list of nodes, where each node has a single link field.


stack
A datastructure where data-item insertions and retrievals/deletions are made at one end, which is known as the top of the stack.


tree
A finite group of nodes, where one of those nodes serves as the root and remaining nodes organize below the root in a hierarchical fashion.


Tips and cautions

These tips and cautions will help you write better programs and save you from agonizing over why the compiler produces error messages.

Tips

  • Think of a doubly linked list as a pair of singly linked lists that each interconnect the same nodes.

Cautions

  • Because Java initializes an object's reference fields to null during that object's construction, it isn't necessary to explicitly assign null to a link field. Don't ignore those null assignments in your source code; their absence reduces your code's clarity.
  • Ensure a recursive method has a stopping condition (such as if (limit == 1) return 1;). Otherwise, the recursion will continue until the method-call stack overflows.


Answers to last month's homework

Last month, I presented you with three exercises. Here are my answers.

  • Draw a flowchart that expresses the binary-search algorithm's flow-of-control.

    The binary-search algorithm as a flowchart. Click on thumbnail to view full-size image.">

    The binary-search algorithm as a flowchart. Click on thumbnail to view full-size image.

  • A magic square is an n x n matrix of integers from 1 to n2, such that the sum is the same for every row, column, and diagonal. If n equals 5, for example, we end up with the following matrix (where the common sum is 65):

    ==========================
| 15 |  8 |  1 | 24 | 17 |
|------------------------|
| 16 | 14 |  7 |  5 | 23 |
|------------------------|
| 22 | 20 | 13 |  6 |  4 | 
|------------------------|
|  3 | 21 | 19 | 12 | 10 |
|------------------------|
|  9 |  2 | 25 | 18 | 11 |
==========================


    A simple algorithm for generating a magic square when n is odd:

    • Begin with 1 in the top row
    • Move up and left, assigning numbers in increasing order to empty squares
    • If you fall off the square, imagine the same square as tiling the plane and continue
    • If a square is occupied, move down instead and continue


    Express the algorithm above in pseudocode and as a Java application for any odd n.

  • Below is the source code to a Java application that implements the algorithm above:

    // MagicSquare.java
class MagicSquare
{
   final static int N = 5; // N must be odd
   static int [][] square;
   static
   {
      // Terminate the program if N is even. Determine "evenness" by
      // checking if the least-significant bit is 0. If so, N is even.
      if ((N & 1) == 0)
      {
          System.out.println ("Error: N is even.");
          System.exit (0);
      }
      // Create an N x N matrix to hold the magic square.
      square = new int [N][];
      for (int i = 0; i < N; i++)
           square [i] = new int [N];
   }
   public static void main (String [] args)
   {
      // Store 1 in the middle of the first row.
      square [0][(N - 1) / 2] = 1;
      // key contains the next value to store. (i, j) contains the
      // current (row, column) position.
      int key = 2, i = 0, j = (N - 1) / 2;
      // Continue to build the magic square.
      while (key <= N * N)
      {
         int k = i - 1; // Look up.
         if (k < 0)
             k += N;
         int l = j - 1; // Look to the left.
         if (l < 0)
             l += N;
         if (square [k][l] != 0)
             i = (i + 1) % N; // Move down if square is occupied.
         else
         {
             i = k; // square [k][l] needs to be assigned.
             j = l;
         }
         square [i][j] = key; // Assign value to square.
         key++; // Obtain next value to store.
      }
      // Output magic square.
      for (i = 0; i < N; i++)
      {
           for (j = 0; j < N; j++)
                System.out.print (square [i][j] + " ");
           System.out.println ();
      }
   }
}


    Your pseudocode should express the essential concepts shown in the Java source code.

  • What does int [] x = { }; accomplish (assuming that code fragment is legal)?

    int [] x = { }; creates a zero-length one-dimensional array. In other words, there are no elements.



  • Print
  • Feedback