Newsletter sign-up

View all newsletters

Sign up for our technology specific newsletters.

Enterprise Java

Email Address:

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

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 n², 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.

 

About Us | Advertise | Contact Us | Terms of Service/Privacy

Copyright, 2006-2008 Network World, Inc. All rights reserved.