import
java.awt.*;
import
java.util.*;
import java.io.*;
public class Class1
{
public static void main (String[] args)throws IOException
{
while(true)
{
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
String s=input.readLine();
System.out.println(s.length());
}
}
}
Fig 1.10 Java program to count number of input
characters.
public class ListNode{
Object data;
ListNode next;
ListNode(Object
o, ListNode nextNode)
{
data=o;
next=nextNode;
}
Fig 1.14 Java program of node class(A macro for defining
list cells).
public static void SelectionSort( int A[], int n )
{
int i, j, small, temp;
for( i = 0; i <A.length-1; i++ )
{
small = i;
for( j = i+1; j < A.length; j++ )
{
if( A[j] < A[small] )
small = j;
}
temp = A[small];
A[small] = A[i];
A[i] = temp;
}
}
Fig 2.2 A Java program for Iterative selection sort.
import java.io.*;
import java.util.StringTokenizer;
public class Class1
{
private static String input;
static int[] array;
private static int no=0;
public static void main (String[] args) throws IOException
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
String input = in.readLine();
StringTokenizer tokens = new StringTokenizer(input);
array = new int[tokens.countTokens()];
while(tokens.hasMoreTokens()){
array[no++] = Integer.parseInt(tokens.nextToken());
}
printarray( array );
SelectionSort( array, array.length );
System.out.println();
printarray( array );
System.in.read();
}
public static void printarray( int A[] )
{
for( int i = 0; i < A.length; i++ )
System.out.println( A[i] );
}
public static void SelectionSort( int A[] )
{
int i, j, small, temp;
for( i = 0; i < A.length-1; i++ )
{
small = i;
for( j = i+1; j < A.length; j++ )
{
if( A[j] < A[small] )
small = j;
}
temp = A[small];
A[small] = A[i];
A[i] = temp;
}
}
}
for (i = 0; i < A.length -1; i++) {
small = i ;
for(j = i+1; j< A.length; j++)
if(A[j]<A[small])
small = j;
temp = A[small];
A[small] = A[i] ;
A[i] = temp;
}
Fig 2.11 The body of the SelectionSort function.
BufferedReader input = new BufferedReader( new InputstreamReader( System.in ) );
int n = Integer.parseInt(input.readLine());
i = 2;
fact = 1;
while ( i <= n ) {
fact = fact * i ;
i++;
}
System.out.println( fact );
Fig 2.13 Factorial program fragment in Java.
sum = 0;
BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );
int x = Integer.parseInt(input.readLine());
while ( x >= 0) {
sum = sum + x ;
BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );
int x = Integer.parseInt(input.readLine());
}
Fig 2.14 Summing a list of integers terminated by a
negative integer.
public static void fact(int n)
{
if (n<=1)
return 1;
else
return n*fact(n-1);
}
public void recSS( int A[], int i)
{
int j, small, temp;
if (i< A.length – 1){ //basis is when i=A.length-1,in which case the function
//returns without changing A. Induction follows
small = i;
for(j = i + 1; j<A.length; j++)
if (A[j]<A[small])
small = j;
temp= A[small];
A[i] =temp;
recSS (A, i+1, A.length);
}
}
public class LIST{
int element;
LIST next;
LIST(int o, LIST nextNode)
{
element=o;
next=nextNode;
}
public LIST merge(LIST list1, LIST list2)
{
if (list1= =null)
list2;
else if (list2 = = null)
list1;
else if(list1.element<=list2.element){
list1.next=merge(list1.next, list2);
list1;
}
else{
list2.next = merge(list1, list2.next);
list2;
}
}
public LIST split (LIST list)
{
LIST pSecondCell = new LIST;
if (list = = null)
return null;
else if (list.next = = null)
returm null;
else {
pSecondCell = list.next;
list.next =pSecondCell.next;
pSecondCell.next = split (pSecondCell.next);
return pSecondCell;
}
}
Fig 2.27 Splitting a list into two equal pieces.
public LIST MergeSort(LIST list)
{
LIST SecondList = new LIST;
if (list = = null)
return null;
else if (list.next = = null)
return list;
else{
SecondList = split(list);
merge (MergeSort(list), MergeSort (SecondList));
}
}
public
class ms {
public static void main(String args[]) {
int[] x = {7,6,8,5,9,10,0,4,1,2,3};
Cell list1 = makelist(x,0);
printlist(list1);
list1 = mergesort(list1);
printlist(list1);
}
static Cell makelist(int[] arry,int loc) {
Cell temp;
if (loc >= arry.length) return null;
else {
temp = new Cell();
temp.element = arry[loc++];
temp.next = makelist(arry,loc);
}
return temp;
}
static void printlist(Cell list){
if (list == null) System.out.println();
else
{
System.out.print(list.element + " , ");
printlist(list.next);
}
}
static Cell mergesort(Cell list1) {
// System.out.print("Mergsort:
"); printlist(list1);
Cell list2 ;
if (list1 == null) return null;
else {
if (list1.next == null) return list1;
else {
list2
= split(list1);
return
merge(mergesort(list1),mergesort(list2));
}
}
}
static Cell merge(Cell list1, Cell list2)
{
// System.out.print("Merging
: "); printlist(list1);
// System.out.print(" and
: "); printlist(list2);
if( list1 == null) return list2;
else {
if( list2 == null) return list1;
else {
if
(list1.element <= list2.element) {
list1.next = merge(list1.next,list2);
return list1;
}
else
{
list2.next = merge(list1,list2.next);
return list2;
}
}
}
}
static Cell split(Cell list){
Cell list2;
if (list == null) return null;
else {
if (list.next == null) return null;
else {
list2
= list.next;
list.next
= list2.next;
list2.next
= split(list2.next);
return
list2;
}
}
}
}
class
Cell {
public int element;
public Cell next;
}
Fig 2.32 Two recursive functions, sum and find0
static int sum (Cell l)
if (l == null) return 0 ;
else return l.element + sum(l.next);
}
static boolean find0(Cell l) {
if (l == null) return false;
else if (l.element == 0) return true;
else return find0(l.next);
}
CHAPTER3
small = i ;
for (j= i+1;j < A.length; j++)
if (A[j] < A[small])
small = j;
Fig 3.1 Inner loop of selection sort.
public static int PowerofTwo( int n)
{
int i ;
i = 0;
while ( n%2 = = 0) {
n
= n/2 ;
i++ ;
}
return i ;
}
Fig 3.5 Counting factors of 2 in a positive integer n.
BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );
int n = Integer.parseInt(input.readLine());
for ( i =0; i<n; i++)
for (j =0; j<n; j++)
A[i] [j] = 0;
for ( i =0; i<n; i++)
A [i] [i] = 1;
Fig 3.7 Program fragment to make A an identity matrix.
for ( i =0; i<A.length-1; i++) {
small = i ;
for(j = i + 1; j<A.length; j++)
if (A[j]<A[small])
small = j;
temp= A[small];
A[i] =temp;
}
Fig 3.8 Selection Sort fragment.
if (A[1][1] = = 0)
for (i = 0; i<n; i++)
for (j = 0; j<n; j++)
A[i][j] = 0;
else
for (i = 0; i<n; i++)
A[i][i] =1;
Fig 3.9 Example of an if-else selection statement
i = 0 ;
while ( x ! =A[i] )
i++;
Fig 3.10 program fragment for linear search.
for (i=0; i< A.length-1; i++)
for (j = i+1; j< A.length; j++)
for (k= i; k< A.length; k++)
A[j] [k] = A[j] [k] – A[i] [k] * A[j] [i] / A[i] [i] ;
import java.io.*;
import java.util.StringTokenizer;
public class Class1 check this out later
{
private static String input;
static int[] array;
private static int no=0;
public static void main (String[] args) throws IOException
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
String input = in.readLine();
StringTokenizer tokens = new StringTokenizer(input);
array = new int[tokens.countTokens()];
while(tokens.hasMoreTokens()){
array[no++] = Integer.parseInt(tokens.nextToken());
}
printarray( array );
SelectionSort( array, array.length );
System.out.println();
printarray( array );
System.in.read();
}
Fig 3.17
for ( i = 1; i <= n; i++ ) {
m = 0;
j = i;
while ( j%2 = = 0 ) {
j = j / 2;
m ++;
}
}
public static void prime ( int n )
{
int i = 2;
while ( i * i <= n)
if (n%i = = 0 )
return FALSE;
else
i++;
return TRUE;
}
import java.io.*;
import java.util.*;
public bar (int x, int n);
public foo (int x, int n);
public class main( )
{
int a, n ;
BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );
int n = Integer.parseInt(input.readLine());
a = foo ( 0, n) ;
System.out.print ( bar (a, n));
}
public static void bar ( int x, int n)
{
int i ;
for (i = 1; i<=n; i++)
x += i ;
return x ;
}
public static void foo ( int x, int n)
{
int i ;
for (i = 1; i<=n; i++)
x += bar(i , n);
return x ;
}
Fig 3.21 Program illustrating nonrecursive function
calls.
public static int fact(int n)
{
if (n <= 1)
return 1;
else
n*fact(n-1);
}
Fig 3.23 Program to compute n!
public static int fibonacci (int n)
{
if (n<=2)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
Fig 3.24 Java function computing Fibonacci numbers.
public static LIST merge(LIST list1, LIST list2)
{
if (list1 = = null)
return list2;
else if (list2 = = null)
return list1;
else if (list1.element <= list2.element) {
list1.next = merge(list1.next,list2)
return list1;
}
else {
list2.next = merge(list1, merge list2.next);
return list2;
}
}
public static LIST split (LIST list)
{
LIST pSecondCell = new LIST( );
if (list = = null)
return null;
else if (list.next = = null)
return null;
else {
pSecondCell = list.next;
list.next = pSecondCell.next;
pSecondCell.next = split(pSecondCell.next);
return pSecondCell;
}
}
Fig 3.27 The function split.
public static LIST MergeSort(LIST list)
{
LIST SecondList = new LIST( );
if (list = = null)
return null;
else if (list.next = = null)
return list;
else{
SecondList = split(list);
Return merge(MergeSort(list), MergeSort(SecondList));
}
}
Fig 3.28 The mergesort algorithm.
if (i < A.length-1) {
small = i ;
for (j = i+1 ; j< A.length; j++)
if (A[j] < A[small] )
small = j ;
temp = A[small];
A[small] = A[i] ;
A[i] = temp ;
RecSS( A, i+1);
}
}
Fig 3.29 Recursive selection sort.
Chapter4
c = 1;
for (i = n; i > n-m; i--)
c *= i;
for (i=2 ; i <= m; i++)
c /= i;
Fig 4.9 Code to compute (n/m)
public static int choose(int n, int m)
{
int n, m ;
if (m < 0 | | m > n ) {
System.out.println( “invalid input”);
return 0 ;
}
else if ( m == 0 | | m = = n)
return 1;
else
(choose(n-1, m-1) + choose(n-1, m));
}
Fig 4.10 Recursive function to compute (n/m).
public BOOLEAN find (int x, int A[ ] )
{
int i ;
for (i = 0; i < A.length; i++)
if( A[i] = = x )
return TRUE;
return FALSE;
}
Fig 4.23 Finding an element x in an array A of size n.
Chapter 5
public class TreeNode
{
Object element;
TreeNode firstChild;
TreeNode nextSibling;
}
Node declaration for tree.
public class pNode
{
char letter;
int isword;
pNode leftmostChild;
pNode rightSibling;
}
public class pNode seek( char let, pNode n)
{
c = n.leftmostChild;
while ( c!= null)
if(c.letter = = let)
break;
else
c = c.rightSibling;
return c;
}
Fig 5.12 finding a child for a desired letter.
public void
preorder(pNode n )
{
pNode c ;
System.out.print(n.nodeLabel ) ;
while ( c != null ){
preorder(c);
c = c.rightSibling ;
}
}
Fig 5.15 Preorder traversal function.
public void postorder(pNode n)
{
pNode c ;
c = n.leftmostChild ;
while(c != null ) {
postorder(c) ;
c = c.rightSibling ;
}
System.out.print( n.nodeLabel) ;
}
Fig 5.17 Recursive postorder function
public void computeHt(pNode n)
{
pNode c ;
n.height = 0 ;
c = n.leftmostChild ;
while ( c != null ){
computeHt(c) ;
if (c.height >= n.height)
n.height = 1+c.height ;
c = c.rightSibling ;
}
}
Fig 5.22 Procedure to compute the height of all the nodes
of a tree.