Data_Structures_in_Java 1-2

Posted on | Edited on

1 Java Primer

1.1 Base types

1
2
3
4
5
6
7
8
boolean   
char     16-bit
byte     8-bit
short    16-bit
int      32-bit
long     64-bit
float    32-bit
double   64-bit

1.2 Classes and Objects

Critical members of a class:
Instance variables: must have a type: either a base type or any class type(reference type)
Methods: accept parameters as arguments

1
2
3
4
5
6
7
8
public class Counter {
  private int count;  // a simple integer instance variable
  public Counter() { }  // default constructor (count is 0)
  public Counter(int initial) { count = initial; }  // an alternate constructor
  public int getCount() { return count; }  // an accessor method
  public void increment() { count++; }  // an update method
  public void increment(int delta) { count += delta; }   // an update method
  public void reset() { count = 0; }   // an update method

1.2.1 Dot Operator

1.2.2 Defining a class

1 Modifiers
Access control modifiers: public, protected, private

The static modifier: for any variable or method of a class.
The value of a static variable is associated with the class as a whole. It is used to store “global” information in a class.
When a method of a class is declared as static, it too is associated with the class as a whole, rather than with each individual instance of that class.

The abstract modifier: an advanced feature of OOP to be combined with inheritance.

The final modifier:
a variable that is declared with the final modifier can be initialized as part of that declaration, but can never again be assigned a new value.
a final method cannot be overridden by a subclass, and cannot even be subclassed.

2 Declaring Instance Variables

3 Declaring Methods

4 Declaring Constructors
Constructors cannot be static, abstract, or final.
The name of the constructor must be identical to the name of the class it constructs.
We don’t specify a return type of a constructor.

5 Keyword This

6 main Method

Unit Testing: use framework such as JUnit

1.3 Strings, Wrappers, Arrays, Enum types

1.3.1 String class

Instances are immutable

1
2
3
String title = "Data Structures in Java"; // declared a string
char c = title.charAt(0) // c = 'D';
String term = "over" + "load";  // Concatenation : term = "overload"

1.3.2 StringBuilder Class

Instances are mutable.

setCharAt(k, c): Change the character at index k to character c.
insert(k, s): Insert a copy of string _s_ starting at index _k_ of the sequence, shifting existing characters further back to make room.
append(s): Append string _s_ to the end of the sequence.
reverse(): Reverse the current sequence.
toString(): Return a traditional String instance based on the current character sequence.

1.3.3 Wrapper Types

1.3.4 Arrays

1.3.5 Enum Types

1.4 Expressions

1.4.1 Literals

1
2
3
4
5
6
null;
Boolean: true / false;
Integer: int-32bit, 176L/52l-64bit
Floating Point: default is double.
Character:
  '\n':newline  '\t': tab  '\b': backspace  '\r': return  '\f': form feed  '\\':backslash  '\'': single quote  '\"': double quote

1.4.2 Operators

Arithmetic:

- * / %```
1
String Concatenation:```+

Increment and Decrement Operators:

--```
1
2
Logical Operators:
  for numbers:```< <= == != >= >

for boolean:

&& ||```
1
Bitwise Operators:```~ & | ^异或 << >> >>>

Assignment Operator:

1
2
3
4
![Imgur](https://i.imgur.com/Q10pCkD.png)

### 1.4.3 Type Conversions
**Mutual conversion between int and double**

double d1 = 3.2;
double d2 = 3.9999;
int i1 = (int) d1; // i1 = 3
int i2 = (int) d2; // i2 = 3
double d3 = (double) i2; // d3 =3.0

1
**Mutual conversion between int to String**

String s1 = “2014”;
int i1 = Integer.parseInt(s1); // i1 gets value 2014
int i2 = −35;
String s2 = Integer.toString(i2); // s2 gets value “-35”

1
2
3
4
5
6
7
## 1.5 Control Flow
### if / switch
if...else if... else
switch... case...case...case...default...
### while / for

### control-flow statements

return
break
continue

1
2
3
4

## 1.6 Simple Input and Output
### Simple Output Method
print: String, Object, baseType

import java.io.PrintStream;

System.out.print();
System.out.println();

1
2
3

### Simple Input Method
Create a Scanner object:

new Scanner(System.in);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
```
import java.util.Scanner;   // loads Scanner definition for our use

public class InputExample {
  public static void main(String[ ] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Enter your age in years: ");
    double age = input.nextDouble();
    System.out.print("Enter your maximum heart rate: ");
    double rate = input.nextDouble();
    double fb = (rate − age) ∗ 0.65;
    System.out.println("Your ideal fat-burning heart rate is " + fb);
  }
}

java.util.Scanner Methods
Dealing with tokens:

1
2
3
4
hasNext(): return true/false
next(): return next token string; raise en error if there are no more tokens left
hasNextType():  
nextType():

Processing line by line:

1
2
3
hasNextLine(): return true/false
nextLine(): return next line
findInLine(String s): attempts to find a string matching the pattern s in the current line.

1
2
3
4
5
6
7
Scanner input = new Scanner(System.in);
System.out.print("Please enter an integer: ");
while (!input.hasNextInt()) {
  input.nextLine( );
  System.out.print("Invalid integer; please enter an integer: ");
}
int i = input.nextInt();

1.7 An Example Program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class creditCards {
    public static class CreditCard{

        private String customer;
        private String bank;
        private String account;
        private int limit;
        private double balance;

        private CreditCard(String cust, String bk, String acnt, int lim, double initialBal){
            customer = cust;
            bank = bk;
            account = acnt;
            limit = lim;
            balance = initialBal;
        }

        private CreditCard(String cust, String bk, String acnt, int lim){
            this(cust, bk, acnt, lim, 0.0);
        }

        public String getCustomer(){return customer;}
        public String getBank(){return bank;}
        public String getAccount(){return account;}
        public int getLimit(){return limit;}
        private double getBalance(){return balance;}

        private boolean charge(double price){
            if(price + balance > limit) return false;
            balance += price;
            return true;
        }

        private void makePayment(double amount){
            balance -= amount;
        }

        private static void printSummary(CreditCard card){
            System.out.println("Customer = " + card.customer);
            System.out.println("Bank = " + card.bank);
            System.out.println("Account = " + card.account);
            System.out.println("Balance = " + card.balance);
            System.out.println("Limit = " + card.limit);
        }
    }

    public static void main(String[] args){
        CreditCard[] wallet = new CreditCard[3];
        wallet[0] = new CreditCard("John Bowman", "California Savings","5391 0375 9387 5309", 5000);
        wallet[1] = new CreditCard("John Bowman", "California Federal", "3485 0399 3395 1954", 3500);
        wallet[2] = new CreditCard("John Bowman", "California Finance", "5391 0375 9387 5309", 2500, 300);

        for(int val = 1; val <= 16; val++){
            wallet[0].charge(3*val);
            wallet[1].charge(2*val);
            wallet[2].charge(val);
        }
        for(CreditCard card : wallet){
            CreditCard.printSummary(card);  // calling static method
            while (card.getBalance() > 200.0){
                card.makePayment(200);
                System.out.println("New balance = " + card.getBalance());
            }
        }
    }
}

1.8 Packages and Imports

1
2
3
package packageName;
import packageName.className;
import packageName.*;

1.9 Software Development

Three phases: Design, Coding, Testing and Debugging.

1.9.1 Design

For OOP, it is in the design step that we decide how to divide the workings of our program into classes, when we decide how these classes will interact, what data each will store, and what actions each will perform.

Determining how to define classes: Responsibilities; Independence; Behaviors.

UML diagrams to express the organization of a program.
“+”:public visibility
“#”:protected visibility
“-“:private visibility
Imgur

1.9.2 Pseudocode

1.9.3 Coding

To accelerate the development of this skill, we need to know various design patterns for designing OOP. These patterns provide templates for defining classes and the interactions between these classes.

1.9.4 Documentation and Style

Javadoc

1.9.5 Testing and Debugging

2 Object-Oriented Design

2.1 Goals, Principles, and Patterns

Achieving Robustness, Adaptability, and Reusability.

2.1.2 Object-Oriented Design Principles

Principles of OO approach:
Abstraction: An abstract data type specifies what each operation does, but not how it does.
Encapsulation: hide details of different components.
Modularity:

2.1.3 Design Patterns

Design Patterns fall into two groups:
Patterns for solving algorithm design problems;
Patterns for solving software engineering problems

Algorithms design patterns
Recursion;
Amortization;
Divide-and-Conquer;
Prune-and-Search, also known as Decrease-and-Conquer;
Brute Force;
The greedy method;
Dynamic Programming;

Software design patterns
Template method;
Composition;
Adapter;
Position;
Iterator;
Factory Method;
Comparator;
Locator

2.2 Inheritance

The correspondence between levels is often referred to as an “is a“ relationship, as a house is a building ,and a ranch is a house.
Imgur
This allows a new class to be defined based upon an existing class as the starting point.

The existing class is described as base class, parent class, or superclass;
Newly defined class is called as subclass, or child class.

2.2.1 Extending the CreditCard Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import creditCards.CreditCard;

public class PredatoryCreditCard extends CreditCard {
    // Additional instance variable
    private double apr; // annual percentage rate

    // Constructor for this class
    public PredatoryCreditCard(String cust, String bk, String acnt, int lim,
                               double initialBal, double rate) {
        super(cust, bk, acnt, lim, initialBal);  // initialize superclass attributes
        apr = rate;
    }

    // A new method for assessing monthly interest charges
    public void processMonth() {
        if (balance > 0) { // only charge interest on a positive balance
            double monthlyFactor = Math.pow(1 + apr, 1.0 / 12); // compute monthly rate
            balance *= monthlyFactor;  // assess interest
        }
    }

    // Overriding the charge method defined in the superclass
    public boolean charge(double price) {
        boolean isSuccess = super.charge(price);
        if (!isSuccess)
            balance += 5;
        return isSuccess;
    }
}

2.2.2 Polymorphism and Dynamic Dispatch

2.2.3 Inheritance Hierarchies

2.3 Interfaces and Abstract Classes

2.3.1 Interfaces in Java

2.3.2 Multiple Inheritance for Interfaces

2.3.3 Abstract Classes

2.4 Exceptions

2.4.1 Catching Exceptions

statements: try...catch...

2.4.2 Throwing Exceptions

2.5 Casting and Generics

2.5.1 Casting

2.5.2 Generics

2.6 Nested Classes