Lecture 7  Home

Readings

• On the course Web page look at:
• Errors in the text
•  Spring CSC108 page
•  Course announcements

- about the Midterm
• The Sorting Algorithm Demo
•  Assignment deadlines for all courses
• In the text read
• Chapters 6-7, Appendix 'O'.

Inheritance from Object class provides

• default constructor
•  toString method - write your own toString method for a class

public String toString() {
  return <instanceVariable(s)>;

then you can print information about it

MyClass myobj = new MyClass();
System.out.println(myobj); // myobj.toString()

• finalize method

Objects for Organizing Data

• defining and initializing arrays
•  arrays and array elements as parameters
•  arrays and objects
•  Vector class
•  StringTokenizer class
•  String and StringBuffer classes
•  find maximum element

Arrays

Arrays are objects

Stored in contiguous memory

once size is set it is fixed

accessed by index from 0 to length - 1

int[] list;         // list is type integer array
list = new int[10]; // reserve memory for 10 integers
for (int i = 0; i < list.length;i++)
  list[i] = 0; // assignment

OR

int[] list = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};

Arrays of Objects

using new allocates space for references to objects only

String[] words = new String[25];

using new allocates memory for each object

word[0] = new String("this");

// OR special case for String

word[0] = "this";

Arrays as Parameters

when you pass the entire array the
formal parameter references the array object

so elements values can be changed but
references can't be changed.

public static void main (String[] args) {}

Reverse_Numbers

int[] numbers = new int[10];
DataInputStream stdin = new DataInputStream (System.in));

System.out.println ("The size of the array is: " + 
                     numbers.length);

for (int index = 0; index < numbers.length; index++) {
   System.out.print ("Number " + index + ": ");
   System.out.flush();
   numbers[index] = Integer.parseInt (stdin.readLine());
}

System.out.println ("Numbers in reverse:");

for (int index = numbers.length-1; index >= 0; index--)
   System.out.print (numbers[index] + "  ");

System.out.println ();

Find Maximum value

int max = Integer.parseInt(stdin.readLine());
for (int i=0;i<10;i++) {
  int number = Integer.parseInt(stdin.readLine());
  if (max < number)
    max = number;
}

Sales_Analysis

public int highest_month () {

int highest = JANUARY;

for (int month = JANUARY+1;
                       month <= DECEMBER; month++)
   if (revenue[highest] < revenue[month])
      highest = month;
return highest;

}

Multidimensional Arrays

int[][] matrix = {{1,0},
                  {0,1}};

OR

int[][] matrix = new int[2][2];
for (int i = 0;i < matrix.length;i++) {
  for (int j = 0;j < matrix.length;j++) {
    matrix[i,j] = 0;
  }
  matrix[i,i] = 1;
}

The Vector Class

Vector class is in java.util

allows dynamically changing size

Methods

• addElement(Object)
•  removeElement(Object)
•  contains(Object)
•  firstElement(Object)
•  lastElement(Object)
•  size()
•  insertElementAt(Object, int)
•  setElementAt(Object, int)

- implemented with arrays
- Vector class is an inefficient black box
- insertion by shifting entire array: one
element at a time See Beatles, ZZ_top

Strings

The String class allows literal assignment
without the new operator

Methods

char charAt(int)
int indexOf(char)
int lastIndexOf(char)
boolean endsWith(String suffix)
boolean startsWith(String)
boolean equals(Object)
boolean equalsIgnoreCase(String)
int compareTo(String)
String toLowerCase()
String toUpperCase()
int length()

StringTokenizer

Constructors

StringTokenizer(String)
StringTokenizer(String, String delimiters)
StringTokenizer(String, String delimiters,
                boolean returnDelimitors)

Methods

boolean hasMoreTokens() // returns boolean
String nextToken()     // default last delimiters
String nextToken(String delimiters) // persistent
int countTokens()

See Voltaire and URL_Tokens

Voltaire

String quote = "Use, do not abuse; neither abstinence " +
               "nor excess renders a man happy.";

StringTokenizer words = new StringTokenizer (quote);

System.out.println ("Characters: " + quote.length());
System.out.println ("Tokens: " + words.countTokens());

while (words.hasMoreTokens()) {
   System.out.println (words.nextToken());
}
System.out.println (words.countTokens());

StringBuffer Class

StringBuffer size can change dynamically

Does the Basic String operations and more

Constructors

StringBuffer(), default 16
StringBuffer(int)
StringBuffer(String)

Methods

String append(char)
String insert(int, char)
char charAt(int)
void setLength(int)
String reverse()
int length()

Sorting: Insertion sort

Consider the first element of a list. It is sorted.

5	2	6	1	3	4	7	value
0	1	2	3	4	5	6	index

For instance we can consider 5 at index 0 as a sorted list. So we can get started.

Assume we have a partially sorted array so that elements 0, ... i - 1 are sorted and elements i ... list.length - 1 are unsorted. We can increase the number of sorted elements to include element i by doing the following

• save the ith element (value or reference)
•  shift elements larger than the ith down (stops?)
•  put the ith element in the available position j

[sorted list]

(ith element)

unsorted list

After each application of the induction step

[5]

(2)

6

1

3

4

7

 

[2

5]

(6)

1

3

4

7

 

[2

5

6]

(1)

3

4

7

 

[1

2

5

6]

(3)

4

7

 

[1

2

3

5

6]

(4)

7

 

[1

2

3

4

5

6]

(7)

 

[1

2

3

4

5

6

7]

Given an array ``item'' of the String class
implement the Insertion sort in Java

for (int i = 1; i < item.length; i++) {

// SAVE THE ITH ELEMENT
   String ith = item[i];

// SHIFT ELEMENTS LARGER THAN THE ith DOWN
   int j = i-1;
        // j in list  && ith < item[j]
   while (j > -1 && ith.compareTo(item[j]) < 0){
     item[j+1] = item[j];
     j--;
   }
   j++;
// PUT THE ith ELEMENT IN THE AVAILABLE j POSITION
   item[j] = ith;

• Lecture 7 ...

  
 Lecture 7  Home
Wed Jun 17 15:07:39 EDT 1998