Data Structures throw Java Lab Programs
Meerja
Maqbul Baig
M.tech
Computer science
----------------------------------------------------------------------------------------------------
Contents
Prg Program Statement Page
1 Write a Java program that prints all real
solutions to the quadratic equation
ax2
+ bx + c = 0.
Read in a, b, c and use the quadratic formula. If the
discriminant (b2
– 4ac) is negative; display a message stating that
there are no
real solutions.
1
2 The Fibonacci sequence is defined by the following
rule: The first two values
in the sequence are 0 and 1. Every subsequent value
is the sum of the two
values preceding it. Write a Java program that uses
both recursive and nonrecursive
functions to print the nth value in the Fibonacci
sequence.
3
3 Write a Java program that prompts the user for an
integer and then prints out
all prime numbers up to that integer.
4
4 Write a Java program that checks whether a given
string is a palindrome or
not. For example, “MADAM” is a palindrome.
6
5 Write a Java program for sorting a given list of
names in ascending order. 7
6 Write a Java program to multiply two given
matrices. 8
7 Write a Java Program that reads a line of
integers, and then displays each
integer, and the sum of all the integers (use
StringTokenizer class).
9
8 Write a Java program that reads a file name from
the user then displays
information about whether the file exists, whether
the file is readable, whether
the file is writable, the type of file and the
length of the file in bytes.
11
9 Write a Java program that reads a file and
displays the contents of the file on
the screen, with a line number before each line.
12
10 Write a Java program that displays the number of
characters, lines and words
in a text file.
13
11 Write a Java program for creating multiple threads.
(a) Using Thread class
(b) Using Runnable interface
14
12 Write a Java program that illustrates how run
time polymorphism is achieved. 16
13 Write a java program that illustrates the
following:
(a) Creation of simple package.
(b) Accessing a package.
(c) Implementing interfaces.
17
14 Write a java program that illustrates the
following
(a) Handling predefined exceptions
(b) Handling user defined exceptions
19
15 Write Java programs that use both recursive and
non-recursive functions for
implementing the following searching methods:
(a) Linear search
(b) Binary search
22
16 Write Java programs to implement the List ADT
using arrays and linked lists. 25
17 Write Java programs to implement the following
using an array.
(a) Stack ADT
(b) Queue ADT
32
18 Write a java program that reads an infix
expression, converts the expression
to postfix form and then evaluates the postfix
expression (use stack ADT).
37
19 Write a java program that determines whether
parenthetic symbols ( ), { } and
[ ] are nested correctly in a string of
characters(use stack ADT).
40
20 Write a java program that uses both stack and
queue to test whether the given
string is a palindrome.
41
21 Write Java programs to implement the following
using a singly linked list.
(a) Stack ADT
(b) Queue ADT
43
22 Write Java programs to implement the deque
(double ended queue) ADT
using
(a) Array
(b) Doubly linked list.
47
23 Write a Java program to implement priority queue
ADT. 53
24 Write Java programs that use recursive and
non-recursive functions to
traverse the given binary tree in
(a) Preorder
(b) Inorder and
(c) Postorder.
56
25 Write a Java program that displays node values in
a level order traversal
(Traverse the tree one level at a time, starting at
the root node) for a binary
tree.
60 26 Write a Java program that uses recursive
functions.
(a) To create a binary search tree.
(b) To count the number of leaf nodes.
(c) To copy the above binary search tree.
63
27 Write a Java program to perform the following
operations:
(a) Insert an element into a binary search tree.
(b) Delete an element from a binary search tree.
(c) Search for a key element in a binary search
tree.
63
28 Write a Java program to perform the following
operations
(a) Insertion into an AVL-tree
(b) Deletion from an AVL-tree
66
29 Write a Java program to perform the following
operations:
(a) Insertion into a B-tree
(b) Deletion from a B-tree
71
30 Write a Java program to implement all the
functions of a dictionary (ADT)
using Hashing.
76
31 Write Java programs for the implementation of bfs
and dfs for a given graph. 81
32 Write Java programs for implementing the
following sorting methods:
(a) Bubble sort
(b) Selection sort
(c) Insertion sort
(d) Quick sort
(e) Merge sort
(f) Heap sort
(g) Radix sort
(h) Binary tree sort
85
33 Write a Java program for implementing KMP pattern
matching algorithm. 98 Overview of Java
This section introduces the students to elementary
Java. Java is a vast computer language and programming
environment, it is not possible to touch upon all
Java-related issues. This section introduces only those
aspects of Java that are necessary for understanding
the Java code offered in this book. Java program
examples presented in this section give you to
implement data structures.
Quadratic equation
1. Write a Java program that prints all real
solutions to the quadratic equation ax2
+ bx + c = 0.
Read in a, b, c and use the quadratic formula. If
the discriminant (b2
– 4ac) is negative; display
a message stating that there are no real solutions.
The roots of the quadratic equation, ax2
+ bx + c = 0
are given by:
x = [–b ± √(b2
– 4ac) ]/2a
The discriminant, d = (b2
– 4ac)
Case (1): When d is greater than zero, the two roots
are real.
x1 = (–b + √d )/2a and x2 = (–b – √d )/2a
Case (2): When d is equal to zero, the two roots are
equal.
x1 = x2 = – b /2a
Case (3): When d is less than zero, the two roots
are imaginary. Each of the two roots has two
parts:
real-part-1, imaginary-part-1 and real-part-2, imaginary-part-2.
real-part-1, xr1 = –b/2a imaginary-part-1, xi1 = +√d
/2a
real-part-2,
xr2 = –b/2a imaginary-part-2, xi2 = –√d /2a
Program 1: Roots of a quadratic equation
import java.lang.Math;
import java.util.Scanner;
class QuadraticEquation
{
double a, b,
c; // coefficients
QuadraticEquation( double a, double b, double
c)
{
this.a = a;
this.b = b;
this.c = c;
}
public void
roots()
{
if( a == 0.0
)
{
System.out.println("One root = " + (-c/b));
return;
}
double d =
b*b - 4.0*a*c; 2 Lab Manual Data Structures through Java
if(d < 0)
// Roots are imaginary
{
System.out.println("There are no real
solutions.");
return;
}
if(d == 0) //
Roots are equal
{
System.out.println("Two roots are equal:
" + (-b /(2.0*a)));
return;
}
// Roots are
real
double x1 =
(-b + Math.sqrt(d))/(2.0*a);
double x2 =
(-b - Math.sqrt(d))/(2.0*a);
System.out.println("Roots are: " +
x1 + ", " + x2);
}
}
//////////////////// QuadraticEquationDemo.java
/////////////////
class QuadraticEquationDemo
{
public static
void main(String[] args)
{
Scanner scr =
new Scanner(System.in);
System.out.print(" a = ");
double a =
scr.nextDouble();
System.out.print(" b = ");
double b =
scr.nextDouble();
System.out.print(" c = ");
double c =
scr.nextDouble();
QuadraticEquation qe = new
QuadraticEquation(a, b, c);
qe.roots();
}
}
Output of this program is as follows (for different
values of a, b, and c):
a = 0
b = 4
c = 1
One root = -0.25
a = 1
b = 4
c = 4
Two roots are equal: -2.0
a = 1
b = 4
c = 8
There are no real solutions
a = 1
b = 4
c = 3 1.
Overview of Java
3
Roots are: -1.0, -3.0
Fibonacci sequence
2. The Fibonacci sequence is defined by the
following rule: The first two values in the sequence
are 0 and 1. Every subsequent value is the sum of
the two values preceding it. Write a Java
program that uses both recursive and non-recursive
functions to print the nth value in the
Fibonacci sequence.
The Fibonacci sequence (denoted by f0, f1, f2 …) is
as follows:
0, 1, 1, 2,
3, 5, 8, 13, 21, 34, 55 …
That is, f0 = 0 and f1 = 1 and each succeeding term
is the sum of the two preceding terms. For example,
the next two terms of the sequence are
34 + 55 = 89
and 55 + 89 = 144
Many algorithms have both iterative and recursive
formulations. Typically, recursion is more elegant
and requires fewer variables to make the same
calculations. Recursion takes care of its book-keeping
by stacking arguments and variables for each method
call. This stacking of arguments, while invisible
to the user, is still costly in time and space.
Fibonacci sequence is recursively defined by
f0 = 0, f1 = 1, fi+1 = fi + fi-1 for i = 1, 2 …
Fibonacci class is implemented in Program 2, with
iterative and recursive methods, and tested by
main() driver.
Program 2: Fibonacci sequence
import java.io.*;
class Fibonacci
{
public int fibonacciSeq(int n) // Iterative method
{
int term1 =
0, term2 = 1, nextTerm = 0;
if( n == 0 ||
n == 1) return n;
int count =
2;
while( count
<= n )
{
nextTerm =
term1 + term2;
term1 =
term2;
term2 =
nextTerm;
count++;
}
return
nextTerm;
}
public int
recFibonacciSeq(int n) // Recursive method4 Lab Manual Data Structures through
Java
{
if( n == 0 ||
n == 1) return n;
else
return(
recFibonacciSeq(n-1) + recFibonacciSeq(n-2) );
}
}
/////////////////// FibonacciDemo.java
////////////////////////
class FibonacciDemo
{
public static
void main(String[] args) throws IOException
{
Fibonacci fib
= new Fibonacci();
BufferedReader kb = new
BufferedReader(new
InputStreamReader(System.in));
// nth value
in the Fibonacci sequence System.out.print("Enter n: ");
int n =
Integer.parseInt(kb.readLine());
System.out.println("Iterative method:
Fibonacci number "
+ n + " is " + fib.fibonacciSeq(n) );
System.out.println("Recursive method:
Fibonacci number "
+ n + " is " + fib.recFibonacciSeq(n) );
}
}
Output of this program is:
Enter n: 12
Iterative
method: Fibonacci number 12 is 144
Recursive
method: Fibonacci number 12 is 144
Prime numbers
3. Write a Java program that prompts the user for an
integer and then prints out all prime
numbers up to that integer.
A prime number is a positive integer that is exactly
divisible only by 1 and itself. The first few prime
numbers are:
2 3 5 7 11 13
17 23 29 31 37 …
All primes apart from 2 are odd.
As a starting point in developing the prime number
generator let us explore how we can establish
whether or not a particular number is a prime. To do
this, let us consider a number 13. The definition
of prime number suggests that to determine whether
or not 13 is prime, we need to divide it in turn by
the set of numbers 2, 3, 4, 5 …12. If any of these
numbers divide into 13 without remainder we will
know it cannot be prime number. Therefore, to test
an integer n for prime, n-2 calls to the mod
operation are required. As our n is 13, we need 11
calls. As n grows, the cost of making these divisions
and tests is going to get very expensive. We must
therefore look for ways of improving the efficiency
of the algorithm. Firstly, we can try to keep to a
minimum the number of numbers that we have to test
for primes, and secondly we can try to improve the
efficiency of testing a number for prime.
1. Overview of Java
5
Following up these suggestions, we know that apart
from 2, we do not need to examine any of the
even numbers, and only first half of the numbers is
enough for testing prime. That is, we can test for
mod operation with numbers, from 3 to n/2. Hence,
the following set of numbers is sufficient to test 13
for prime.
3 4 5 6
Program 3: Prime numbers
import java.io.*;
class PrimeNumber
{
public void
primes(int n)
{
int k, m;
System.out.print("Prime numbers up to
" + n + ": 2 3");
for(m=3; m
<= n; m = m+2)
{
boolean
isPrime = false;
for(k=2; k
<= m/2; k++)
{
if(m % k ==
0) { isPrime = false; break; }
else isPrime
= true;
}
if(isPrime)
System.out.print(" " + m);
}
}
}
////////////////////////// PrimeNumberDemo.java
/////////////////
class PrimeNumberDemo
{
public static
void main(String[] args) throws IOException
{
PrimeNumber
pn = new PrimeNumber();
BufferedReader kb = new
BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter n: ");
int n =
Integer.parseInt(kb.readLine());
pn.primes(n);
}
}
Output:
Enter n: 50
Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31
37
41 43 476 Lab Manual Data Structures through Java
Palindrome
4. Write a Java program that checks whether a given
string is a palindrome or not. For example,
“MADAM” is a palindrome.
A string is an array of characters. For example, the
string “MADAM” is stored as follows:
[0] [1] [2] [3] [4]
M A D A M
Java supports the manipulation of character data
through the primitive data type char and the
associated operations for the input, output,
assignment, and comparison of characters. Most
applications of character data require character
sequences - or strings - rather than individual
characters. In Java a string is represented by the
built-in class String. However, manipulating a
String data type in Java is quite different from
manipulating a set (or array) of characters. In the
Java, strings are objects. The Java platform provides
the String class to create and manipulate
strings. The most direct way to create a string is
to write:
String str = "MADAM";
In this case, "MADAM" is a string literal
- a series of characters that is enclosed in double quotes. The
String class provides the method length(), which
returns as an int value the number of
characters in the String object. The method of the
String class
char charAt(int n)
returns the nth character in a string (where n must
be less than string length);
If the first
character is equal to the last character of the string, second character is
equal to the
second one from the last character of the string,
and so on, then the string is a palindrome.
Program 4: Palindrome
class Palindrome
{
public
boolean isPalindrome(String str)
{
System.out.print("Given string: " +
str);
int n =
str.length();
boolean flag
= true;
for( int i=0;
i < n/2; i++ )
if(
str.charAt(i) != str.charAt(n-i-1) ) flag = false;
return flag;
}
}
////////////////////////// PalindromeDemo.java ////////////////////
class PalindromeDemo
{
public static
void main(String[] args)
{ 1. Overview of Java
7
Palindrome
pal = new Palindrome();
String str =
"MADAM";
if(
pal.isPalindrome(str))
System.out.print(" is a
palindrome.");
else
System.out.print("
is not a palindrome.");
}
}
Output of this program is: (Note: You may test the
program for different character strings).
Given string: MADAM is a palindrome.
Sorting names
5. Write a Java program for sorting a given list of
names in ascending order.
Bubble sort algorithm is used to sort the names.
Program 5: Sorting strings
class SortNames
{
public void
sort(String[] a)
{
int i, pass,
n = a.length;
String tmp;
for( pass =
0; pass < n; pass++ )
{
for( i = 0; i
< n-pass-1; i++ )
if( ((Comparable)a[i]).compareTo(a[i+1])
> 0)
{
tmp = a[i];
// Swap a[i], a[i+1]
a[i] =
a[i+1];
a[i+1] = tmp;
}
}
}
}
////////////////////////// SortNamesDemo.java
////////////////////
class SortNamesDemo
{
public static
void main(String[] args)
{
SortNames sn
= new SortNames();
String[]
names =
{"Ramu", "John",
"Anu", "Priya", "Basha", "Prem"};
int i;
System.out.println("Unsorted
names:"); 8 Lab Manual Data Structures through Java
for(i=0; i
< names.length; i++)
System.out.println(names[i]);
sn.sort(names);
System.out.println("Sorted names:");
for(i=0; i
< names.length; i++)
System.out.println(names[i]);
}
}
Output of this program is:
Unsorted names:
Ramu
John
Anu
Priya
Basha
Prem
Sorted names:
Anu
Basha
John
Prem
Priya
Ramu
Matrix multiplication
6. Write a Java program to multiply two given
matrices.
If the order of matrix A is m x n and of matrix B is
n x p (number of columns of A = number of rows
of B = n), then the order of matrix C is m x p,
where C = A x B.
k=n-1
cij = ∑aikbkj for i = 0 to m, and j = 0 to p
k=0
Example: The following two matrices A and B are used
in the program to multiply A by B.
3 2 0
A = 1 5 1
2 3 4
2 0 1 1
B = 1 3 0 3
2 2 2 1
Program 6: Matrix multiplication
class MatrixMultiplication
{
public void
matrixMult( int[][] a, int[][] b, int[][] c)
{
int i, j,
k; 1. Overview of Java
9
for ( i = 0;
i < 3; i++ )
for ( j = 0;
j < 4; j++ )
{ c[i][j] =
0;
for ( k = 0;
k < 3; k++ )
c[i][j] =
c[i][j] + a[i][k] * b[k][j];
}
}
}
////////////////////////// MatrixMultiplicationDemo.java
//////////
class MatrixMultiplicationDemo
{
public static
void main(String[] args)
{
int[][] a = {
{3, 2, 0}, {1, 5, 1}, {2, 3, 4} };
int[][] b = {
{2, 0, 1, 1}, {1, 3, 0, 3}, {2, 2, 2, 1} };
int[][] c;
c = new
int[3][4];
int i, j;
MatrixMultiplication mm = new
MatrixMultiplication();
mm.matrixMult(a,b,c);
System.out.println("matrix C (3 x 4)= A x
B :");
for( i = 0; i
< 3; i++ )
{
System.out.println();
for( j = 0; j
< 4; j++ )
System.out.print( c[i][j] + "\t" );
}
}
}
This program generated the following output:
matrix C (3 x 4)= A x B :
8 6 3 9
9 17 3 17
15 17 10 15
StringTokenizer
7. Write a Java Program that reads a line of
integers, and then displays each integer, and the
sum of all the integers (use StringTokenizer class).
The processing of data often consists of parsing a
formatted input data (or string). The string
tokenizer class allows an application to break a
string into tokens. The discrete parts of a string are
called tokens. The StringTokenizer methods do not
distinguish among identifiers, numbers, and
quoted strings, nor do they recognize and skip
comments. The set of delimiters (the characters that
separate tokens) may be specified either at creation
time or on a per-token basis. StringTokenizer
implements the Enumeration interface. Therefore,
given an input string, we can enumerate the
individual tokens contained in it using
StringTokenizer. The default delimiters are whitespace 10 Lab Manual Data
Structures through Java
characters: space, tab, newline, and carriage
return. Other than default delimiters, each character in the
delimiters string is considered a valid delimiter.
A StringTokenizer object internally maintains a
current position within the string to be
tokenized. Some operations advance this current
position past the characters processed. A token is
returned by taking a substring of the string that
was used to create the StringTokenizer object. The
following is one example of the use of the
tokenizer. The code:
StringTokenizer st = new
StringTokenizer("this is a test");
while
(st.hasMoreTokens())
{
System.out.println(st.nextToken());
}
prints the following output: (Here, space is the
default delimiter)
this
is
a
test
StringTokenizer is a legacy class that is retained
for compatibility reasons although its use is
discouraged in new code.
StringTokenizer constructors are:
StringTokenizer(String str)
StringTokenizer(String str, String delimiters)
Program 7: StringTokenizer
import java.util.StringTokenizer;
import java.io.*;
class StringTokenizerDemo
{
public static
void main(String[] args) throws IOException
{
BufferedReader kb = new
BufferedReader(new
InputStreamReader(System.in));
System.out.print("Enter a string of
digits: ");
String str =
kb.readLine();
StringTokenizer st = new StringTokenizer(str);
int a, sum =
0;
String s;
while
(st.hasMoreTokens())
{
s =
st.nextToken();
a =
Integer.parseInt(s);
sum = sum +
a;
System.out.println(a);
}
System.out.println("Sum of these integers
= " + sum); 1. Overview of Java
11
}
}
This program prints the following output:
Enter a string of digits: 45 100 750 5
45
100
750
5
Sum of these integers = 900
File class
8. Write a Java program that reads a file name from
the user then displays information about
whether the file exists, whether the file is
readable, whether the file is writable, the type of file
and the length of the file in bytes.
Most of the classes defined by java.io operate on
streams. The File class deals directly with
files and the file system. That is, the File class
does not specify how data is retrieved from or stored
in files; it describes the properties of a file
itself. A File object is used to get information or
manipulate the information associated with a disk
file; such as the permissions, time, date, directory
path, is it readable or writable, file size, and so
on.
Files are a primary source and destination for data
within many programs. Files are central
resource for storing persistent and shared
information.
The following two constructors can be used to create
File objects (we have two more
constructors):
File(String directoryPath)
File(String directoryPath, String fileName)
Here,
directoryPath is the path name of the file, fileName is the name of the file.
File class defines many methods that obtain the
standard properties of a File object. For
example, getName() returns the file name, and
exists() returns true if the file exists, false if it
does not. The File class has many methods that allow
us to examine the properties of a sample file
object. Program 8 illustrates some of the File
methods. In this example program, an existing
“HashSetDemo.java” file is used.
Many times a program will be developed that requires
the user to enter a small amount of
information at the terminal keyboard. The information
may consist of number of data elements to be
used in an array. Rather than having the program
request this type of data from the user, we can supply
the information to the program at the time of
program execution. This capability is provided by what is
known as command line arguments.
The main(String[] args) is a method that has
arguments. The parameter args stands for
argument vector. It is an array of strings. The
successive elements of the array refer to successive
words in the command line. We can pass arguments to
main() method. Java provides a connection to
the arguments on the command line. We illustrate
“passing command line arguments to main()”
through the following example. 12 Lab Manual Data
Structures through Java
D:\Java>java FileDemo HashSetDemo.java
The string “HashSetDemo.java” is stored in args[0].
If we supply second string on command line,
it will be stored in args[1], and so on.
Program 8: Demonstration of File class
import java.io.File;
class FileDemo
{
public static
void main(String[] args)
{
File f = new
File(args[0]);
System.out.println("File name: " +
f.getName());
System.out.println(f.exists() ?
"exists" : "does not exist");
System.out.println(f.canWrite() ? "is
writable" : "is not writable");
System.out.println(f.canRead() ? "is
readable" : "is not readable");
System.out.println(f.isFile()? "is normal
file" : "might be a pipe");
System.out.println("File size (in bytes):
" + f.length());
}
}
This program, FileDemo is executed as follows:
D:\Java>java FileDemo HashSetDemo.java
Output of this program is:
File name: HashSetDemo.java
exists
is writable
is readable
is normal file
File size (in bytes): 258
Note: Most of the File methods are self-explanatory.
FileInputStream class
9. Write a Java program that reads a file and displays
the contents of the file on the screen, with
a line number before each line.
The FileInputStream class creates an InputStream
that we can use to read bytes from a file. The
most common constructors are:
FileInputStream(String filePath)
FileInputStream(String fileObject)
Here, filePath is the full path name of a file, and
fileObject is a File object that describes the file.
When a FileInputStream is created, it is opened for
reading. For example, 1. Overview of
Java
13
InputStream f = new FileInputStream("HashSetDemo.java");
creates a File object, f for reading. This object
refers to the file: "HashSetDemo.java". The
following program demonstrates the FileInputStream.
Program 9: FileInputStream
import java.io.*;
class FileInputStreamDemo
{
public static
void main(String[] args) throws IOException
{
InputStream f
= new FileInputStream("HashSetDemo.java");
int size =
f.available(); // file size in bytes
int lineNo =
0;
char ch;
System.out.print(++lineNo + ": ");
// print line 1:
ch =
(char)f.read(); // read first character of line 1
System.out.print(ch); // print first character
of line 1
for(int i=1;
i < size; i++) // read next character & print
{
if( ch ==
'\n' ) // if it is a newline,
System.out.print(++lineNo + ": ");
// print line number
ch =
(char)f.read(); // read next character
System.out.print(ch); // print next character
}
}
}
Output of this program is:
1: import java.util.*;
2: public class HashSetDemo
3: { public static void main(String[] args)
4: {
5: HashSet<Integer> hs = new
HashSet<Integer>();
6:
7: for( int k = 1; k <= 5; k++ )
8: hs.add(11*k);
9:
10: System.out.println("HashSet: " + hs);
11: }
12: }
Counting characters, words, and lines in a text file
10. Write a Java program that displays the number of
characters, lines and words in a text file. 14 Lab Manual Data Structures
through Java
Program 10: Number of characters, lines and words in
a text file
import java.io.*;
class TextFileDemo
{
public static
void main(String[] args) throws IOException
{
InputStream f
= new FileInputStream("MYDATA.TXT");
int size =
f.available();
int nLines =
0;
int nWords =
0;
char ch;
System.out.println("Data file: MYDATA.TXT
contains the following text:\n");
for(int i=0;
i < size; i++)
{
ch =
(char)f.read();
System.out.print(ch);
if( ch == ' '
) nWords++;
if( ch ==
'\n' ) nLines++;
}
nWords++; //
to count the last word in the text file
System.out.println("\nNo: of characters =
" + size);
System.out.println("No: of words = "
+ nWords);
System.out.println("No: of lines = "
+ nLines);
}
}
The following output is generated by this program:
Data file: MYDATA.TXT contains the following text:
Real-life applications require that the data be
written to or read
from secondary storage devices. The secondary
storage devices are
also called auxiliary storage devices such as hard
disk, compact disk,
floppy, and magnetic tape. The data is permanently
stored on these
devices in the form of data files. Once data is
available on these
devices, we can access and change it whenever
required.
No: of characters = 405
No: of words = 64
No: of lines = 6
Multiple Threads
11. Write a Java program for creating multiple
threads.
(a) Using Thread class
(b) Using Runnable interface 1. Overview of Java
15
Refer Chapter 6: Multi-Threading to understand
thread class, Runnable interface and multiple
threads.
Program 11: Multiple threads using Runnable
interface
// create multiple threads
class AThread implements Runnable
{ String name;
Thread th;
AThread(
String threadName)
{ name = threadName;
th = new
Thread(this, name);
System.out.println("A Thread: " +
th);
th.start();
}
public void
run() // entry point for the thread
{ try
{ for(int k =
3; k > 0; k--)
{
System.out.println(name + ":" + k);
Thread.sleep(1000);
}
}
catch(InterruptedException e)
{
System.out.println(name + "Interrupted"); }
System.out.println(name + "
exiting");
}
}
/////////////////// MultiThreadDemo.java
////////////////////
class MultiThreadDemo
{ public static void main(String[] args)
{ new
AThread("One"); // start threads
new
AThread("Two");
new
AThread("Three");
try
{
Thread.sleep(10000); // wait for others to end
}
catch(InterruptedException e)
{
System.out.println("Main thread Interrupted"); }
System.out.println("Main thread exiting");
}
}
Output:
A Thread: Thread[One,5,main]
A Thread: Thread[Two,5,main]
One:3
Two:3
A Thread: Thread[Three,5,main]
Three:3
One:2
Two:2
Three:2
One:1
Two:1
Three:1
One exiting
Two exiting
Three exiting
Main thread exiting 16 Lab Manual Data Structures through
Java
Run-time Polymorphism
12. Write a Java program that illustrates how run
time polymorphism is achieved.
In a class hierarchy, when a method in a subclass
has the same name and type signature as a method in
its superclass, then the method in the subclass is
said to override the method in the superclass. When
an overridden method is called from within a
subclass, it will always refer to the version of that
method defined by the subclass. The version of the
method defined by the superclass will be hidden.
Method overriding forms the basis for one of Java’s
most powerful concepts: dynamic method
dispatch. Dynamic method dispatch is the mechanism
by which a call to an overridden method is
resolved at run-time, rather than compile-time.
Dynamic method dispatch is important because this is
how Java implements run-time polymorphism.
A superclass reference variable can refer to a
subclass object. Java uses this fact to resolve calls to
overridden methods at run-time. When an overridden
method is called through a superclass reference,
Java determines which version of that method to
execute based upon the type of object being referred
to at run-time the call occurs. When different types
of objects are referred to, different versions of an
overridden method will be called. Here is an example
that illustrates dynamic method dispatch:
Program 12: Run-time polymorphism through dynamic
dispatch
class Animal
{ void callme()
{
System.out.println("It is an Animal."); }
}
class Cat extends Animal
{ void callme()
{
System.out.println("It is a Cat."); }
}
class Dog extends Animal
{ void callme()
{
System.out.println("It is a Dog."); }
}
class DynamicDispatch
{
public static void main(String[] args)
{
Animal a =
new Animal(); // create Animal object, a
Cat c = new
Cat(); // create Cat object, c
Dog d = new
Dog(); // create Dog object, d
Animal ref;
// obtain a reference of type Animal
ref = a; //
“ref” refers to Animal object
ref.callme(); // calls Animal’s version of callme()
ref = c; //
“ref” refers to Cat object
ref.callme(); // calls Cat’s version of callme()
ref = d; //
“ref” refers to Dog object
ref.callme(); // calls Dog’s version of callme()
}
}
Output of this program is: 1. Overview of Java
17
It is an Animal.
It is a Cat.
It is a Dog.
Packages and Interfaces
13. Write a java program that illustrates the
following:
(a) Creation of simple package.
(b) Accessing a package.
(c) Implementing interfaces.
Packages are a feature of Java that helps you to
organize and structure your classes and their
relationships to one another. A package is a
grouping of related types providing access protection and
name space management. Note that types refer to
classes, interfaces and others. The types that are part
of the Java platform are members of various packages
that bundle classes by function: fundamental
classes are in java.lang, classes for reading and
writing (input and output) are in java.io, and so
on. You can put your types in packages too.
For example,
consider the following package specification:
package
MyPack;
In order for
a program to find MyPack, we use one of the two alternatives:
1. Program is executed from a directory immediately
above MyPack, or
2. CLASSPATH must be set to include the path to
MyPack.
SET CLASSPATH
=C:\MyPack\
We create a
directory, MyPack below the current development directory, put the .class files
into
the MyPack directory, and then execute the program
from the development directory.
Program 13(a): A simple package example
package MyPack; // A simple package
class Balance
{
String name;
double bal;
Balance(String s, double b) // constructor
{ name = s;
bal = b;
}
void show()
// method
{ if(bal <
0)
System.out.print("-->> ");
System.out.println(name + ": Rs" +
bal);
}
}
class AccountBalance
{
public static
void main(String args[])
{ Balance
current[] = new Balance[3]; 18 Lab Manual Data Structures through Java
current[0] =
new Balance("R. Lepakshi", 15230.50);
current[1] =
new Balance("K. Siva Kumar", 350.75);
current[2] =
new Balance("Michael Jackson", -120.30);
for(int i =
0; i < 3; i++) current[i].show();
}
}
Let the current development directory be C:\java
Create (make directory: md) MyPack directory as
follows:
C:\java>md MyPack
Edit the AccountBalance.java program and compile it
from current development directory as
follows:
C:\java>edit AccountBalance.java
C:\java>javac AccountBalance.java
Then, copy Balance.class and AccountBalance.class
files from the directory C:\java to
the directory C:\java\MyPack
Execute the AccountBalance class, using the
following command line:
C:\java>java MyPack.AccountBalance
AccountBalance is now part of the package MyPack.
This means that it cannot be executed by itself.
That is, we cannot use this command line:
C:\java>java AccountBalance
AccountBalance must be qualified with its package
name.
In Java, an interface is a reference type, similar
to a class that can contain only constants, method
signatures, and nested types. There are no method
bodies. Interfaces cannot be instantiated - they can
only be implemented by classes or extended by other
interfaces.
Here is an example of an interface definition
(defining an interface is similar to creating a new
class). Program 13(b) declares an interface called
Items which contains four methods. Note that the
method signatures have no braces and are terminated
with a semicolon.
Program 13(b): Defining an interface Items
interface Items
{ boolean equal(); // test whether two numbers are
equal
int add(); //
sum of two numbers
int max(); //
maximum of two numbers
void
display(); // print two numbers
}
To declare a class that implements an interface, you
include an implements clause in the class
declaration. Your class can implement more than one
interface, so the implements keyword is
followed by a comma-separated list of the interfaces
implemented by the class. When an instantiable
class implements an interface, it provides a method
body for each of the methods declared in the
interface. Here is an example class Client that
implements the Items interface.
Program 13(c): Implementing an interface Items
class Client implements Items
{
int a,
b; 1. Overview of Java
19
Client( int
i, int j) // constructor
{ a = i; b =
j; }
public
boolean equal()
{ return (a
== b); }
public int
add()
{ return(a +
b); }
public int
max()
{ if( a >
b ) return a;
else return
b;
}
public void
display()
{
System.out.println(a + " " + b); }
public int
multiply() // non-interface method
{ return(a *
b); }
}
Program 13(d): Testing a class which implements an
interface
class ClientDemo
{ public static void main(String[] srgs)
{
Client ob = new Client(5, 7);
ob.display();
if(
ob.equal())
System.out.println("Two numbers are
equal");
else
System.out.println("Two numbers are not
equal");
System.out.println("Sum
of two numbers is " + ob.add());
System.out.println("Max of two numbers is
" + ob.max());
System.out.println("Product of two
numbers is " + ob.multiply());
}
}
Output of this program is:
5 7
Two numbers are not equal
Sum of two numbers is 12
Max of two numbers is 7
Product of two numbers is 35
Exception Handling
14. Write a java program that illustrates the
following
(a) Handling predefined exceptions
(b) Handling user defined exceptions
(a) Java uses exceptions to handle errors and other
exceptional events. An exception (error) is an
event, which occurs during the execution of a
program, which disrupts the normal flow of the program
instructions. When an error occurs within a method,
the method creates an object and hands it off to 20 Lab Manual Data Structures
through Java
the runtime system. The object, called an exception
object, contains information about the error,
including its type and the state of the program when
the error occurred. Creating an exception object
and handing it to the runtime system is called
throwing an exception.
The first step in constructing an exception handler
is to enclose the code that might throw an
exception within a try block. To illustrate how this
can be done, the following program includes a
try block and a catch clause which processes the
ArithmeticException generated by “divisionby-zero”
error. This is a RuntimeException, predefined in
java.lang.
Program 14(a): Handling predefined exceptions
class ExceptionDemo
{
public static
void main(String args[])
{
int a = 25, c
= 3, d = 0;
try
{
a = 25 / d;
System.out.println(a);
}
catch(ArithmeticException ae)
{
System.out.println(ae);
}
System.out.println(a*c);
}
}
This program generates the following output:
java.lang.ArithmeticException: / by zero
75
Notice that the call to println(a) inside the try
block is never executed. Once an exception is
thrown, program control transfers out of the try
block into the catch block. After displaying error
message, it executes the println(a*c).
(b) Although there are a number of exceptions in the
Java class library that you can use in your own
methods; but you might need to create your own
exceptions to handle the different kinds of errors in
your program. Creating new exceptions is easy.
Your new
exception should inherit from some other exception in the Java hierarchy. All
usercreated
exceptions should be part of the Exception
hierarchy. Look for an exception that is close to
the one you are creating. For example, an exception
for a bad file format would logically be an
IOException. If you cannot find a closely related
exception for your new exception, consider
inheriting from Exception, which forms the top of
exception hierarchy.
The Exception
class does not define any methods of its own. It inherits those methods
provided
by Throwable. One such method is the toString()
which returns a String object containing a
description of the exception (notice the MyException
class in the following program).
The following
program illustrates the user-defined exception.
Program 14(b): Handling user defined exceptions
class MyException extends Exception
{
public String
toString() 1. Overview of Java
21
{
String str =
"MyException (a/d): division by zero";
return str;
}
}
class MyExceptionDemo
{
public static
void main(String args[]) throws MyException
{
int a = 20, b
= 3, d = 2;
System.out.println("a = " + a +
", b = " + b + ", d = " + d);
try
{
if( d != 0)
System.out.println( "a/d = " + a/d
);
else
throw new
MyException();
System.out.println("Normal
exit");
} catch
(MyException e)
{
System.out.println(e); }
System.out.println( "a*b = " + a*b
);
}
}
Output of this is as follows,
when d = 0:
a = 20, b = 3, d = 0
MyException (a/d): division by zero
a*b = 60
when d = 2:
a = 20, b = 3, d = 2
a/d = 10
Normal exit
a*b = 60 Searching
15. Write Java programs that use both recursive and
non-recursive functions for implementing
the following searching methods:
(a) Linear search
(b) Binary search
Linear search
(a) The simplest form of a search is the linear
search. This technique is meant for searching a
particular item in an unsorted data set in a
sequential manner until the desired data item is found.
Linear search is easy to write and efficient for
short lists, but inefficient for long ones. To find any
element in a long array (list), there are far more
efficient methods, provided that the array is sorted. A
program for linear search is as follows.
Program 15(a): Iterative Linear search
class LinearSearchDemo
{
static
Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 };
static Object
key = 126;
public static
void main(String args[])
{
if(
linearSearch() )
System.out.println(key + " found in the
list");
else
System.out.println(key + " not found in
the list");
}
static
boolean linearSearch()
{
for( int i=0;
i<a.length; i++)
if(key ==
a[i]) return true;
return false;
}
}
Program 15(b): Recursive Linear search
class RecursiveLinearSearchDemo
{
static
Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 };
static Object
key = 43;
public static
void main(String args[])
{
if(
linearSearch(a.length-1) )
System.out.println(key + " found in the
list");
else
System.out.println(key + " not found in
the list");
}
static
boolean linearSearch(int n)
{
if( n < 0
) return false; 2. Searching
23
if(key ==
a[n])
return true;
else
return linearSearch(n-1);
}
}
Binary search
(b) Binary search is a simple method of accessing a
particular item in a sorted (ordered) data set. A
search for a particular item with a certain key
value resembles the search for a name in telephone
directory or a word in a dictionary. The approximate
middle item of the data set is located, and its key
value is examined. If its value is too high, then
the key of the middle element of the first half of the set
is examined and procedure is repeated on the first
half until the required item is found. If the value is
too low, then the key of the middle entry of the
second half of the data set is tried and the procedure is
repeated on the second half. This process continues
until the desired key is found or search interval
becomes empty. The binary search algorithm is based
on binary search tree.
Program 15(c): Iterative Binary search
class BinarySearchDemo
{
static Object[] a = { "AP",
"KA", "MH", "MP", "OR", "TN",
"UP", "WB"};
static Object
key = "UP";
public static
void main(String args[])
{
if(
binarySearch() )
System.out.println(key + " found in the
list");
else
System.out.println(key + " not found in
the list");
}
static
boolean binarySearch()
{
int c, mid,
low = 0, high = a.length-1;
while( low
<= high)
{
mid = (low +
high)/2;
c =
((Comparable)key).compareTo(a[mid]);
if( c < 0)
high = mid-1;
else if( c
> 0) low = mid+1;
else return
true;
}
return false;
}
} 24 Lab Manual Data Structures through Java
Program 15(d): Recursive Binary search
class RecursiveBinarySearchDemo
{
static
Object[] a = { "AP", "KA", "MH", "MP",
"OR", "TN", "UP", "WB"};
static Object
key = "XP";
public static
void main(String args[])
{
if(
binarySearch(0, a.length-1) )
System.out.println(key + " found in the
list");
else
System.out.println(key + " not found in
the list");
}
static
boolean binarySearch(int low, int high)
{
if( low >
high ) return false;
int mid = (low + high)/2;
int c =
((Comparable)key).compareTo(a[mid]);
if( c < 0)
return binarySearch(low, mid-1);
else if( c
> 0) return binarySearch(mid+1, high);
else return
true;
}
} Linked Lists
16. Write Java programs to implement the List ADT
using arrays and linked lists.
List ADT
The elements in a list are of generic type Object.
The elements form a linear structure in which list
elements follow one after the other, from the
beginning of the list to its end. The list ADT supports the
following operations:
createList(int n): Creates (initially) a list with n
nodes.
Input:
integer; Output: None
insertFirst(obj): Inserts object obj at the
beginning of a list.
Input:
Object; Output: None
insertAfter(obj, obj p): Inserts object obj after
the obj p in a list.
Input: Object
and position; Output: None
obj
deleteFirst(): Deletes the object at the beginning of a list.
Input: None;
Output: Deleted object obj.
obj deleteAfter(obj p): Deletes the object after the
obj p in a list.
Input:
Position; Output: Deleted object obj.
boolean isEmpty(): Returns a boolean indicating if
the list is empty.
Input: None;
Output: boolean (true or false).
int size():
Returns the number of items in the list.
Input: None;
Output: integer.
Type Object may be any type that can be stored in
the list. The actual type of the object will be
provided by the user. The ADT is translated into a
Java interface in the following program.
Program 16(a): A List Interface
public interface List
{
public void
createList(int n);
public void
insertFirst(Object ob);
public void
insertAfter(Object ob, Object pos);
public Object
deleteFirst();
public Object
deleteAfter(Object pos);
public
boolean isEmpty();
public int
size();
}
Array Implementation of List
Program 16(b): An ArrayList Class
class ArrayList implements List
{
class Node
{ Object
data;
int next; 26
Lab Manual Data Structures through Java
Node(Object
ob, int i) // constructor
{ data = ob;
next = i;
}
}
int MAXSIZE;
// max number of nodes in the list
Node list[];
// create list array
int head,
count; // count: current number of nodes in the list
ArrayList(
int s) // constructor
{ MAXSIZE =
s;
list = new
Node[MAXSIZE];
}
public void
initializeList()
{ for( int p
= 0; p < MAXSIZE-1; p++ )
list[p] = new
Node(null, p+1);
list[MAXSIZE-1] = new Node(null, -1);
}
public void
createList(int n) // create ‘n’ nodes
{ int p;
for( p = 0; p
< n; p++ )
{
list[p] = new
Node(11+11*p, p+1);
count++;
}
list[p-1].next = -1; // end of the list
}
public void
insertFirst(Object item)
{
if( count ==
MAXSIZE )
{
System.out.println("***List is FULL");
return;
}
int p =
getNode();
if( p != -1 )
{
list[p].data
= item;
if( isEmpty()
) list[p].next = -1;
else
list[p].next = head;
head = p;
count++;
}
}
public void
insertAfter(Object item, Object x)
{
if( count ==
MAXSIZE )
{
System.out.println("***List is FULL");
return;
}
int q =
getNode(); // get the available position to insert new node
int p =
find(x); // get the index (position) of the Object x
if( q != -1 )
{
list[q].data = item;
list[q].next
= list[p].next;
list[p].next
= q; 3. Linked Lists
27
count++;
}
}
public int
getNode() // returns available node index
{ for( int p
= 0; p < MAXSIZE; p++ )
if(list[p].data == null) return p;
return -1;
}
public int
find(Object ob) // find the index (position) of the Object ob
{ int p =
head;
while( p !=
-1)
{ if(
list[p].data == ob ) return p;
p =
list[p].next; // advance to next node
}
return -1;
}
public Object
deleteFirst()
{ if(
isEmpty() )
{ System.out.println("List
is empty: no deletion");
return null;
}
Object tmp =
list[head].data;
if(
list[head].next == -1 ) // if the list contains one node,
head = -1; //
make list empty.
else
head =
list[head].next;
count--; //
update count
return tmp;
}
public Object
deleteAfter(Object x)
{ int p =
find(x);
if( p == -1
|| list[p].next == -1 )
{
System.out.println("No deletion");
return null;
}
int q =
list[p].next;
Object tmp =
list[q].data;
list[p].next
= list[q].next;
count--;
return tmp;
}
public void
display()
{ int p =
head;
System.out.print("\nList: [ " );
while( p !=
-1)
{
System.out.print(list[p].data + " "); // print data
p =
list[p].next; // advance to next node
}
System.out.println("]\n");//
}
public
boolean isEmpty()
{ if(count ==
0) return true;
else return
false;
} 28 Lab
Manual Data Structures through Java
public int
size()
{ return
count; }
}
Program 16(c): Testing ArrayList Class
class ArrayListDemo
{
public static void main(String[] args)
{
ArrayList
linkedList = new ArrayList(10);
linkedList.initializeList();
linkedList.createList(4); // create 4 nodes
linkedList.display(); // print the list
System.out.print("InsertFirst 55:");
linkedList.insertFirst(55);
linkedList.display();
System.out.print("Insert 66 after
33:");
linkedList.insertAfter(66, 33); // insert 66
after 33
linkedList.display();
Object item =
linkedList.deleteFirst();
System.out.println("Deleted node: "
+ item);
linkedList.display();
System.out.print("InsertFirst 77:");
linkedList.insertFirst(77);
linkedList.display();
item =
linkedList.deleteAfter(22); // delete node after node 22
System.out.println("Deleted node: "
+ item);
linkedList.display();
System.out.println("size(): " +
linkedList.size());
}
}
The following output is generated by this program:
List: [ 11 22 33 44 ]
InsertFirst 55:
List: [ 55 11 22 33 44 ]
Insert 66 after 33:
List: [ 55 11 22 33 66 44 ]
Deleted node: 55
List: [ 11 22 33 66 44 ]
InsertFirst 77:
List: [ 77 11 22 33 66 44 ]
Deleted node: 33
List: [ 77 11 22 66 44 ]
size(): 5
3. Linked
Lists
29
Linked Implementation of List
LinkedList class implemented by List interface is
given Program 16(d) and it is tested in Program
16(e).
Program 16(d): A LinkedList Class
class LinkedList implements List
{
class Node
{ Object data; // data item
Node next; //
refers to next node in the list
Node( Object
d ) // constructor
{ data = d; }
// ‘next’ is automatically set to null
}
Node head; //
head refers to first node
Node p; // p
refers to current node
int count; //
current number of nodes
public void
createList(int n) // create 'n' nodes
{
p = new
Node(11); // create first node
head = p; //
assign mem. address of 'p' to 'head'
for( int i =
1; i < n; i++ ) // create 'n-1' nodes
p = p.next =
new Node(11 + 11*i);
count = n;
}
public void
insertFirst(Object item) // insert at the beginning of list
{
p = new
Node(item); // create new node
p.next =
head; // new node refers to old head
head = p; //
new head refers to new node
count++;
}
public void
insertAfter(Object item,Object key)
{
p =
find(key); // get “location of key item”
if( p == null
)
System.out.println(key + " key is not
found");
else
{ Node q =
new Node(item); // create new node
q.next =
p.next; // new node next refers to p.next
p.next = q;
// p.next refers to new node
count++;
}
}
public Node
find(Object key)
{
p = head;
while( p !=
null ) // start at beginning of list until end of list
{
if( p.data ==
key ) return p; // if found, return key address30 Lab Manual Data Structures
through Java
p = p.next;
// move to next node
}
return null;
// if key search is unsuccessful, return null
}
public Object
deleteFirst() // delete first node
{
if( isEmpty()
)
{ System.out.println("List
is empty: no deletion");
return null;
}
Node tmp =
head; // tmp saves reference to head
head =
tmp.next;
count--;
return
tmp.data;
}
public Object
deleteAfter(Object key) // delete node after key item
{ p =
find(key); // p = “location of key node”
if( p == null
)
{
System.out.println(key + " key is not found");
return null;
}
if( p.next ==
null ) // if(there is no node after key node)
{
System.out.println("No deletion");
return null;
}
else
{ Node tmp =
p.next; // save node after key node
p.next =
tmp.next; // point to next of node deleted
count--;
return
tmp.data; // return deleted node
}
}
public void
displayList()
{ p = head;
// assign mem. address of 'head' to 'p'
System.out.print("\nLinked List: ");
while( p !=
null ) // start at beginning of list until end of list
{
System.out.print(p.data + " -> "); // print data
p = p.next;
// move to next node
}
System.out.println(p); // prints 'null'
}
public boolean isEmpty() // true if list is empty
{ return
(head == null); }
public int size()
{ return
count; }
} // end of LinkeList class 3. Linked Lists
31
Program 16(e): Testing LinkedList Class
class
LinkedListDemo
{ public static void main(String[] args)
{ LinkedList
list = new LinkedList(); // create list object
list.createList(4); // create 4 nodes
list.displayList();
list.insertFirst(55); // insert 55 as first
node
list.displayList();
list.insertAfter(66, 33); // insert 66 after
33
list.displayList();
Object item =
list.deleteFirst(); // delete first node
if( item !=
null )
{
System.out.println("deleteFirst(): " + item);
list.displayList();
}
item =
list.deleteAfter(22); // delete a node after node(22)
if( item !=
null )
{
System.out.println("deleteAfter(22): " + item);
list.displayList();
}
System.out.println("size(): " +
list.size());
}
}
Here is the output from LinkedListDemo.java:
Linked List: 11 -> 22 -> 33 -> 44 ->
null
Linked List: 55 -> 11 -> 22 -> 33 -> 44
-> null
Linked List: 55 -> 11 -> 22 -> 33 -> 66
-> 44 -> null
deleteFirst(): 55
Linked List: 11 -> 22 -> 33 -> 66 -> 44
-> null
deleteAfter(22): 33
Linked List: 11 -> 22 -> 66 -> 44 ->
null
size(): 4 Stacks and Queues
No comments:
Post a Comment