212 Homework 2 Solutions 2014
--D. Thiebaut (talk) 10:16, 26 September 2014 (EDT)
</onlydft>
Contents
Homework #2 Solution Programs
Problem #1
PythonList.java
/**
* PythonList.java
* @author D. Thiebaut
* A crude implementation of a list as Python would support.
*/
public class PythonList {
public int[] array = null;
private int maxdim;
private int end = 0;
/**
* constructor builds a list with a capacity of m
*/
PythonList(int m) {
maxdim = m;
end = 0;
array = new int[maxdim];
}
/**
* constructor builds a list with a default capacity.
*/
PythonList() {
this(100);
}
/**
* tests if index passed is valid
* @return true if index is within bounds, false otherwise.
*/
private boolean isValid( int i ) {
return ( i >= 0 && i < end );
}
/**
* Sets item n at index i, if i is valid. Otherwise skips the insertion.
* @return true if index is within bounds, false otherwise.
*/
public void setAt( int i, int n ) {
if ( ! isValid( i ) )
return;
array[i] = n;
}
/**
* returns the location of an item in the list
* @return index of item, or -1 if not found.
*/
public int index( int n ) {
for ( int i=0; i < end; i++ ) {
//if ( array[i]==n )
if ( at(i) == n )
return i;
}
return -1;
}
/**
* returns the location of an item in the list starting from the right.
* @return index of item, or -1 if not found.
*/
public int rindex( int n ) {
for ( int i=end-1; i >= 0; i-- )
if ( array[i]==n )
return i;
return -1;
}
/**
* Adds n at the end of the list. Grow the list if necessary.
*
*/
public void append(int n) {
if (end <= array.length - 1) {
array[end++] = n;
return;
}
int[] temp = new int[maxdim * 2];
for (int i = 0; i < array.length; i++)
temp[i] = array[i];
array = temp;
array[end++] = n;
maxdim = maxdim * 2;
}
/**
* returns the number of items in the list.
* @return number of items. 0 if list is empty.
*/
public int length() {
return end;
}
/**
* returns the item at position i.
* @return item at position i if i is valid index. Else returns 0.
*/
public int at(int index) {
if (index >= 0 && index < array.length)
return array[index];
// this is bad... we'll fix it later...
else
return -1;
}
public static void main(String[] args) {
// --- Test List ---
PythonList L = new PythonList(5);
for (int i = 0; i < 11; i++)
L.append(i*2);
L.append( 2 );
for (int i = 0; i < L.length(); i++)
System.out.println(L.at(i));
System.out.println( " index("+ 2 +") = " + L.index(2) );
System.out.println( " rindex("+ 2 +") = " + L.rindex(2) );
}
}
PascalList.java
/**
* A class that prints a row of Pascal's triangle.
* @author D. Thiebaut
*/
public class PascalList {
static private final int ROW = 9; // the row we are interested in...
/**
* constructor. Doesn't do anything.
*/
public PascalList() {
}
/**
* Test program for the list.
*/
static public void main( String[] args ) {
PythonList row = new PythonList( 3 );
row.append( 1 );
for ( int i=1; i<ROW; i++ )
row.append( 0 );
for ( int i=1; i<ROW; i++ ) {
for ( int k=ROW-1; k>0; k-- )
row.setAt(k, row.at(k-1) + row.at(k) );
}
for ( int i=0; i<row.length(); i++ )
System.out.println( row.at(i) + " " );
System.out.println();
}
}
/**
* Computes the 9th row of Pascal's triangle. * @author D. Thiebaut */
public class PascalList {
static private final int ROW = 9;
/**
* Constructor. (Not really needed in this program, but could in more complex application.)
*/
public PascalList() {
}
static public void main( String[] args ) {
PythonList row = new PythonList( 3 );
row.append( 1 );
for ( int i=1; i<ROW; i++ )
row.append( 0 );
for ( int i=1; i<ROW; i++ ) {
for ( int k=ROW-1; k>0; k-- )
row.setAt(k, row.at(k-1) + row.at(k) );
}
for ( int i=0; i<row.length(); i++ )
System.out.println( row.at(i) + " " );
System.out.println();
}
}
</onlydft>
Problem #2
public class PythonList2 {
private String[] array = null;
private int maxdim;
private int end = 0;
PythonList2(int m) {
maxdim = m;
end = 0;
array = new String[maxdim];
}
PythonList2() {
this(100);
}
private boolean isValid( int i ) {
return ( i >= 0 && i < end );
}
public void setAt( int i, String n ) {
if ( ! isValid( i ) )
return;
array[i] = n;
}
public int index( String n ) {
for ( int i=0; i < end; i++ ) {
if ( at(i) == n )
return i;
}
return -1;
}
public int rindex( String n ) {
for ( int i=end-1; i >= 0; i-- )
if ( array[i]==n )
return i;
return -1;
}
public void append(String n) {
if (end <= array.length - 1) {
array[end++] = n;
return;
}
String[] temp = new String[maxdim * 2];
for (int i = 0; i < array.length; i++)
temp[i] = array[i];
array = temp;
array[end++] = n;
maxdim = maxdim * 2;
}
public int length() {
return end;
}
public String at(int index) {
if (index >= 0 && index < array.length)
return array[index];
else
return null;
}
public static void main(String[] args) {
// --- Test List ---
PythonList2 dwarves = new PythonList2(5);
dwarves.append("Blick2");
dwarves.append("Flick2");
dwarves.append("Glick2");
dwarves.append("Plick2");
dwarves.append("Quee2");
dwarves.append("Snick2");
dwarves.append("Whick2");
System.out.println("Snow White's friends:");
for (int i = 0; i < dwarves.length(); i++)
System.out.println(dwarves.at(i));
String dwarf;
dwarf = dwarves.at(-1);
if (dwarf != null)
System.out.println(dwarf);
dwarf = dwarves.at(20);
if (dwarf != null)
System.out.println(dwarf);
int n = dwarves.index( "Quee" );
if ( n != -1 )
System.out.println( "Quee found at Index: " + n );
else
System.out.println( "Quee not found" );
n = dwarves.rindex( "Quee" );
if ( n != -1 )
System.out.println( "Quee found at Index: " + n );
else
System.out.println( "Quee not found" );
n = dwarves.index( "Queen" );
if ( n != -1 )
System.out.println( "Queen found at Index: " + n );
else
System.out.println( "Queen not found" );
}
}
