Data structures

Object-Oriented Programming
Outline

n Primitive data types

n String
n Math class
n Array
n Container classes

n Readings:
q HFJ: Ch. 13, 6.

q GT: Ch. 13, 6.

Đại học Công nghệ - ĐHQG HN Data structures 2

Basic classes

Object

Boolean Character Void Number Math String StringBuffer ...

Byte Short Integer Long Float Double

Đại học Công nghệ - ĐHQG HN Data structures 3

The Object class

n Class getClass() returns class name of the current objects.

Cat a = new Cat(”Tom”);

Class c = [Link]();
[Link](c);

n boolean equals(Object) compares objects, is usually

redefined.
n String toString() returns text representation of the object,
is usually redefined.

Đại học Công nghệ - ĐHQG HN Data structures 4

Primitive data types

n Utility methods:
q valueOf(String s) returns an object of the corresponding type
holding the value of String s.
Integer k = [Link]( "12"); // k = 12
q typeValue() returns primitive value of the object
int i = [Link](); // i = 12
q static parseType(String s) converts a string into a value of
the corresponding primitive type
int i = [Link]("12"); // i = 12
n constants
q Type.MAX_VALUE, Type.MIN_VALUE

Đại học Công nghệ - ĐHQG HN Data structures 5

The Character class

n Methods
q static boolean isUppercase(char ch)
q static boolean isLowercase(char ch)
q static boolean isDigit(char ch)
q static boolean isLetter(char ch)
q static boolean isLetterOrDigit(char ch)
q static char toUpperCase(char ch)
q static char toLowerCase(char ch)

Đại học Công nghệ - ĐHQG HN Data structures 6

The String class

n String: unmodifiable sequence of characters.

n Initialise:
q String(String)

q String(StringBuffer)

q String(byte[])

q String(char[])

n Methods
q int length the length of the string

q char charAt(int index) returns the character at position

index

Đại học Công nghệ - ĐHQG HN Data structures 7

The String class

n Comparison
q boolean equals(String)

q boolean equalsIgnoreCase(String)

q boolean startWith(String)

q boolean endWith(String)

q int compareTo(String)

n Conversion
q String toUpperCase()

q String toLowerCase()

n Concatenation
q String concat(String)

q operator “+”

Đại học Công nghệ - ĐHQG HN Data structures 8

The String class

n Search forwards
q int indexOf(int ch)

q int indexOf(int ch, int from)

q int indexOf(String)

q int indexOf(String s, int from)

n Search backwards
q int lastIndexOf(int ch)

q int lastIndexOf(int ch, int from)

q int lastIndexOf(String)

q int lastIndexOf(String, int)

Đại học Công nghệ - ĐHQG HN Data structures 9

The String class

n Replace
q String replace(char oldChar, char newChar)
returns a new string resulting from replacing all
occurrences of oldChar with newChar
n Substring
q String trim() returns a copy of the string, with leading

and trailing white space omitted.

q String substring(int startIndex)

q String substring(int start, int end)

Đại học Công nghệ - ĐHQG HN Data structures 10

StringBuffer

StringBuffer: modifiable sequence of characters

n Initialize

q StringBuffer(String)

q StringBuffer(int length)

q StringBuffer(): default size is 16

n Utilities

q int length()

q void setLength()

q char charAt(int index)

q void setCharAt(int index, char ch)

q String toString()

Đại học Công nghệ - ĐHQG HN Data structures 11

StringBuffer

n Edit
q append(String)

q append(type t) appends t's string representation

q insert(int offset, String s)

q insert(int offset, char[] chs)

q insert(int offset, type t)

q delete(int start, int end) deletes a substring

q delete(int index) deletes 01 character

q reverse()

Đại học Công nghệ - ĐHQG HN Data structures 12

The Math class

n Constants
q Math.E

q [Link]

n Static methods
q type abs(type): absolute value of int/double/long

q double ceil(double)

q double floor(double)

q int round(float)

q long round(double)

q type max(type, type), type min(type, type)

Đại học Công nghệ - ĐHQG HN Data structures 13

The Math class

n Static methods (cont.)

q double random() generates random value in the range [0.0,1.0]
q double pow(double, double)
q double exp(double) e raised to the power of a value.
q double log(double) natural logarithm (base e)
q double sqrt(double)
n trigonometric
q double sin(double) returns sine of an angle
q double cos(double) returns cosine of an angle
q double tan(double) returns tangent of an angle

Đại học Công nghệ - ĐHQG HN Data structures 14

Array

n An array is an object that

q contains a set of objects

q must be created (new) before use

int a[];
a = new int[10];
for (int i = 0; i < [Link]; i++) a[i] = i * i;
for (int w: a)
[Link](w + " ");

int b[] = {2, 3, 5, 7};

a = b;
int m, n[];
double[] arr1, arr2;

Đại học Công nghệ - ĐHQG HN Data structures 15

Array as argument and return value

int[] myCopy(int[] a)
{
int b[] = new int[[Link]];
for (i=0; i<[Link]; i++)
b[i] = a[i];
return b;
}
...
int a[] = {0, 1, 1, 2, 3, 5, 8};
int b[] = myCopy(a);

Đại học Công nghệ - ĐHQG HN Data structures 16

Multi-dimensional arrays

int a[][];
a = new int[10][20];
a[2][3] = 10;
for (int i=0; i<a[0].length; i++)
a[0][i] = i;
for (int w: a[0])
[Link](w + " ");

int b[][] = { {1 , 2}, {3, 4} };

int c[][] = new int[2][];
c[0] = new int[5];
c[1] = new int[10];

Đại học Công nghệ - ĐHQG HN Data structures 17

Array copy

n [Link](src, s_off, des, d_off, len)

q src: source array, s_off: source array's offset

q des: destination array, d_off: destination array's offset

q len: number of entries to be copied

n Entries's content is copied

q Primitive value

q Object reference.

Đại học Công nghệ - ĐHQG HN Data structures 18

The Array class

n In the package [Link]

n Four static methods
q fill() initialises array entries with one same value

q sort() sorts array

n works with arrays of primitive values

n works with classes that implement Comparable
q equals() compares two arrays
q binarySearch() performs binary search in sorted arrays,
creates logic error if used for unsorted arrays.

Đại học Công nghệ - ĐHQG HN Data structures 19

Container classes
<< interface>>
Map
<< interface>>
Collection HashMap

HashTable << interface>>

Sorted Map

<< interface>> << interface>>

Set List
Tree Map

HashSet << interface>> Array List Vector LinkedList

Sorted Set

TreeSet

Đại học Công nghệ - ĐHQG HN Data structures 20

Iterator

n An iterator allows a program to walk through a

collection and remove elements from the collection
during the iteration.
n Java Iterator interface
q hasNext()

q next()

q remove()

n Collection classes implement Iterator

Đại học Công nghệ - ĐHQG HN Data structures 21

import [Link].*;

public class TestList {

static public void main(String args[])
{
Collection list = new LinkedList();

[Link](3); 3
[Link](2); 2
[Link](1); 1
[Link](0); 0
[Link]("go!"); go!

Iterator i = [Link]();
while ([Link]()) {
[Link]([Link]());
}
}
}

Đại học Công nghệ - ĐHQG HN Data structures 22

import [Link].*;

public class TestList {

static public void main(String args[])
{
List list = new LinkedList();

[Link](3); 3
[Link](2); 2
[Link](1); 1
[Link](0); 0
[Link]("go!"); go!

for (int i=0; i<[Link](); i++) {

[Link]([Link](i));
}

}
}

Đại học Công nghệ - ĐHQG HN Data structures 23

import [Link].*;

public class TestList {

static public void main(String args[])
{
List<Integer> list = new LinkedList<Integer>();

[Link](3); 3
[Link](2); 2
[Link](1); 1
[Link](0); 0
//[Link]("go!");

for (int i=0; i<[Link](); i++) {

[Link]([Link](i));
}
}
}

Đại học Công nghệ - ĐHQG HN Data structures 24