# Lec.3 期中考後

[TOC]

<br>

## 物件導向 (OOP, Object-oriented programming) - Part.I

### 物件導向的四大特性

- **抽象 (Data Abstraction)**
- **封裝 (Encapsulation)**
- **繼承 (Inheritance)**
- **多型 (Polymorphism)**

<br>

### 抽象資料型別 (ADT, Abstract Data Type)

- **Data Abstraction & Encapsulation **


- **Data Type**


- ADT的優點

<br>

### 結構體 (Struct)

> Member Data (成員資料)

<br>

- **宣告**

struct Sales_data {
   string book_no;
   unsigned unit_sold = 0;
   double revenue = 0.0;
};

<br>

- **呼叫**

- 在Sales_data.h中撰寫struct Sales_data

    #ifndef SALES_DATA_H
    #define SALES_DATA_H
    #include <string>
    
    struct Sales_data {
        std::string bookNo;
        unsigned units_sold = 0;
        double revenue = 0.0;
    };
    #endif

- 在main.cpp中呼叫

    #include <iostream>
    #include "Sales_data.h"
    using namespace std;
    
    int main() {
        Sales_data data1;
        double price = 0;
        cout << "Please enter Book No., Unit of sold, and price> ";
        cin >> data1.bookNo >> data1.units_sold >> price;
        data1.revenue = data1.units_sold * price;
        cout << "Revenue: " <<data1.revenue <<endl;
    }

<br>

### 類別 (Class)

> Member Data (成員資料)
> Member Function (成員函數)
> Friend Function
> Friend Class

#ifndef RECTANGLE_H 
#define RECTANGLE_H 
class Rectangle { 
//private: // private members, encapsulation, implementation 
    // data members 
    int x1, y1, h, w; 
    // (x1, y1) -> bottom left corner 
    // w: width, h: height 
public: // public members, interface, specification 
    // member functions 
    Rectangle(); // constructor or ctor 
    ~Rectangle(); // destructor or dtor 
    int GetHeight() const; // return height 
    int GetWidth() const; // return width 
}; 
#endif

<br>

- **宣告**

class class_name {
        int x, y;        #預設為private
    public:
    nt member1;
    private:
    int member2;
    protected:
        int member2;
};

:::info
**成員的權限範圍，如果沒有宣告範圍則預設為private：**
－public: 任何一個class都可以使用
－private: 只有同一個class的其他成員或該class的friend class可以使用
－protected: 只有同一個class的其他成員、該class的friend class或derived class可以使用
:::

<br>

- **constructor初始化物件**

> 在class內部，只定義prototype，在class外才定義內容。
其中::是範圍運算子，賦予成員適當的範圍屬性，也就是所屬的class

#include <iostream>
using namespace std;

class CRectangle{
      int width, height;
  public:
      CRectangle (int,int);                    //constructor prototype
      int area (void){return (width*height);}
};

//constructor
CRectangle::CRectangle (int a, int b){         //constructor 內容
  width = a;
  height = b;
}


int main() {
  CRectangle rectA(3,4);
  cout << "area: " << rectA.area() << endl;
}

<br>

- **Overloading constructor 建構子重載**

#include <iostream>
using namespace std;

class CRectangle{
      int width, height;
  public:
      CRectangle ();
      CRectangle (int,int);
      int area (void){return (width*height);}
};

//overloading constructor
CRectangle::CRectangle (){
  width = 5;
  height = 5;
}

CRectangle::CRectangle (int a, int b){
  width = a;
  height = b;
}

int main() {
  CRectangle rectA(3,4);
  CRectangle rectB;
  cout << "area of rect A: " << rectA.area() << endl;
  cout << "area of rect B: " << rectB.area() << endl;
}

或是

#include <iostream>
using namespace std;

class CRectangle{
      int width, height;
  public:
      CRectangle (): width(5), height(5){};    //contructor without parameter
      CRectangle (int,int);                    //contructor with parameter
      int area (void){return (width*height);}
};

//constructor
CRectangle::CRectangle (int a, int b){         //constructor 內容
  width = a;
  height = b;
}


int main() {
  CRectangle rectA;
  CRectangle rectB(4,6);
  cout << "area: " << rectA.area() << endl;
  cout << "area: " << rectB.area() << endl;
}

<br>

- **類別中的指標 (Pointer to class)**

#include <iostream>
using namespace std;

class CRectangle{
      int width, height;
  public:
      void set_values(int, int);
      int area (void){return (width*height);}
};

void CRectangle::set_values(int a, int b){
  width = a;
  height = b;
}

int main() {
  CRectangle a, *b, *c;
  CRectangle *d = new CRectangle[2];
  b = new CRectangle;
  
  a.set_values(1, 2);
  b->set_values(3, 4);
  c = &a;
  d->set_values(5, 6);
  d[1].set_values(7, 8);

  cout << "area of a: " << a.area() << endl;
  cout << "area of *b: " << b->area() << endl;
  cout << "area of *c: " << c->area() << endl;
  cout << "area of d[0]: " << d[0].area() << endl;
  cout << "area of d[1]: " << d[1].area() << endl;

  return 0;
}

:::info
**類別中指標的解讀方法：**
- *x: pointed by x
- &x: address of x
- x.y: member y of object x
- (*x).y: member y of object pointed by x
- x->y: 跟(*x).y一樣 member y of object pointed by x
- x[n]: (n+1)th object pointed by x
:::

<br>

- **關鍵字 this**
> 關鍵字this是一個指標，被用於一個class內部，指正在被執行的物件的記憶體位址。
主要用途有兩個：
> 1. 用來檢查傳入的物件程員函數的參數，是否是該物件本身
> 2. 用來return物件的指標

- 用來檢查傳入的物件程員函數的參數，是否是該物件本身

#include <iostream>
using namespace std;

class CDummy{
  public:
      int isitme(CDummy& param);
};

int CDummy::isitme(CDummy& param){
  if (&param == this)                 //this就是&param
    return 1;
  else
    return 0;
}

int main() {
  CDummy a;
  CDummy *b = &a;

  if(b->isitme(a))
    cout << "yes, &a is b"<<endl;

  return 0;
}

- 用來return物件的指標

CVector& Cvector::operator= (const CVector& param){
    x=param.x;
    y=param.y;
    return *this;
}

<br>

- **Static Members(靜態成員)**

> 靜態成員可以是資料變數，也可以是函式，對同一個class產生的所有物件，都可以共用這個成員，所以又稱class variable。
常見用法是計算一個class產生的物件個數，如下，這個n就是class內全部成員共用。

#include <iostream>
using namespace std;

class CDummy{
  public:
    static int n;         //用static方式宣告
    CDummy (){ n++;};
    ~CDummy (){ n--;};
};

int CDummy::n=0;

int main() {
    CDummy a;
    CDummy b[5];
    CDummy *c = new CDummy;
    cout << a.n << endl;
    delete c;
    cout << CDummy::n << endl;

  return 0;
}

<br>

- **運算子多載 (Overloading Operators)**

> 標準運算子，例如+ - * /可以用於基礎型別，但如果要讓類別/結構物件也可以運用這些運算子，可以使用運算子多載的語法

宣告方式：
type operator sign (parameters);

type是class名稱
operator是保留字
sign可以是 + - * / = < >

- 將+運算子進行多載

#include <iostream>
using namespace std;

class CVector{
  public:
    int x,y;
    CVector ();
    CVector (int, int);
    CVector operator +  (CVector);
};

CVector::CVector(){
  x = 0;
  y = 0;
}

CVector::CVector(int a, int b){
    x = a;
    y = b; 
}

CVector CVector::operator+ (CVector param){
    CVector temp;
    temp.x = x + param.x;
    temp.y = y + param.y;
  
    return (temp);
}


int main() {
    CVector a(3,1);
    CVector b(1,2);
    CVector c;
    c = a + b;
    cout << c.x << ", "<< c.y<<endl;

    return 0;
}

<br>

- **授權：Friend**
- Friend Function
> 為了實現允許外部函數可以訪問class的private和protected成員，我們必須在class內部宣告該外部函數的prototype。
>

#include <iostream>
using namespace std;

class CRectangle{
    int width, height;
  public:
    void set_values (int, int);
    int area (void) {return (width * height);}
    friend CRectangle duplicate (CRectangle); //宣告friend function
};

void CRectangle::set_values(int a, int b){
  width = a;
  height = b;
}

//friend function可以存取private member: width, height
CRectangle duplicate(CRectangle rectparam){
  CRectangle rectres;
  rectres.width = rectparam.width*2;
  rectres.height = rectparam.height*2;
  return (rectres);
}

int main() {
    CRectangle rect_a, rect_b;
    rect_a.set_values(2,3);
    rect_b = duplicate(rect_a);
    cout << rect_b.area()<<endl;
    return 0;

- Friend class
>我們也可以定義一個class是另一個class的friend，如此一來，friend class可以訪問第一個class protected和private成員。
>

 #include <iostream>
using namespace std;

class CSquare;      //必須加入，因為class CRectangle宣告有包括CSquare
class CRectangle{
    int width, height;
  public:
    int area (void) {return (width * height);}
    void convert (CSquare a);
};

class CSquare {
  private:
    int side;
  public:
    void set_side (int a){side=a;}
    friend class CRectangle;
};

void CRectangle::convert (CSquare a){
  width = a.side;
  height = a.side;
}

int main() {
    CSquare sqr;
    CRectangle rect;

    sqr.set_side(4);
    rect.convert(sqr);
    cout << rect.area();

    return 0;
}

<br>

- **Inheritance (繼承)**
- class之間的繼承
> 基於某個class生成新的class，新的class可以擁有前者的成員，又可以加上自己的成員。
被繼承的class，稱為base class，新生成的class，稱為derived class。
宣告語法如下：
class derived_class_name: 權限 base_class_name
其中權限可以為public, private, protected，定義存取base class的權限
也就是說，從base class繼承過來的成員，會以指定權限存在著。

#include <iostream>
using namespace std;

//base class
class CPolygon{
  protected:
    int width, height;
  public:
    void set_values(int a, int b) { width = a; height = b;}
};

//derived class
class CRectangle:public CPolygon{
  public:
    int area(void);
};

int CRectangle::area(){
  return (width*height);
}

//derived class
class CTriangle:public CPolygon{
  public:
    int area(void);
};

int CTriangle::area(){
  return (width*height/2);
}

int main() {
  CRectangle rect;
  CTriangle tri;

  rect.set_values(3, 4);
  tri.set_values(3, 4);

  cout << "Area of rect: " << rect.area()<<endl;
  cout << "Area of tri: " << tri.area()<<endl;

  return 0;
}

<br>

- **Polymorphism(多形)**

> Virtual Members: 先定義函數成員的prototype

#include <iostream>
using namespace std;

//base class
class CPolygon{
  protected:
    int width, height;
  public:
    void set_values(int a, int b) { width = a; height = b;}
    virtual int area(void) {return 0;}      //先定義prototype
};

//derived class
class CRectangle:public CPolygon{
  public:
    int area(void) {return (width*height);}
};

//derived class
class CTriangle:public CPolygon{
  public:
    int area(void) {return (width*height/2);}
};

int main() {
  CRectangle rect;
  CTriangle tri;
  CPolygon poly;

  CPolygon *ppoly1 = &rect;
  CPolygon *ppoly2 = &tri;
  CPolygon *ppoly3 = &poly;

  ppoly1->set_values(3, 4);
  ppoly2->set_values(3, 4);
  ppoly3->set_values(3, 4);

  cout << ppoly1->area() << endl;
  cout << ppoly2->area() << endl;
  cout << ppoly3->area() << endl;

  return 0;
}

> Abstract base class

#include <iostream>
using namespace std;

//base class
class CPolygon{
  protected:
    int width, height;
  public:
    void set_values(int a, int b) { width = a; height = b;}
    virtual int area(void) = 0;     //先定義prototype
    void printarea (void){
      cout << this->area() << endl;
    }
};

//derived class
class CRectangle:public CPolygon{
  public:
    int area(void) {return (width*height);} //derived class的實作
};

//derived class
class CTriangle:public CPolygon{
  public:
    int area(void) {return (width*height/2);} //derived class的實作
};

int main() {
  CRectangle rect;
  CTriangle tri;


  CPolygon *ppoly1 = &rect;
  CPolygon *ppoly2 = &tri;

  ppoly1->set_values(3, 4);
  ppoly2->set_values(3, 4);

  // 不用考慮具體是哪一個derived class的area()實作，會自動對應
  ppoly1->printarea();       //print 12
  ppoly2->printarea();       //print 6
  
  return 0;
}

<br>

- **Review 1: 總結成員權限**

| 權限 | public | protected | private |
| -------- | -------- | -------- | -------- |
| class本身 | yes | yes | yes |
| derived class | yes | yes | no |
| class以外 | yes | no | no |

<br>

- **Review 2: derived class會從base class繼承的東西**
> 預設來說
> 1. 會從base class繼承public、protected成員
> 2. 不會從base class繼承以下成員
> - 有參數的constructor/deconstructor
> - overloading operator
> - friends

<br>

- **Review 3: 當derived class生成物件時，base class也會同時調用建構子**

#include <iostream>
using namespace std;

//base class
class mother{
  public:
    mother () { cout << "mother: no parameters\n";}
    mother (int a) { cout << "mother: int parameters\n";}
};

//derived class
class daughter:public mother{
  public:
    daughter (int a){ cout<<"daughter: int parameter\n";} //預設mother無參數的建構子
};

//derived class
class son:public mother{
  public:
    son (int a):mother(a) { cout<<"son: int parameter\n";}  //指定mother帶有參數的建構子
};

int main() {
  daughter mary (1);
  son tom(1);

return 0;
}

<br>

- **Review 4: C++ class支援多重繼承**

> 多重繼承就是一個class，可以同時從多個class中繼承成員
>
> 範例如下：
> - class CRectangle同時繼承了CPolygon, COutput
> - class CTriangle同時繼承了CPolygon, COutput

#include <iostream>
using namespace std;

//base class 1
class CPolygon{
  protected:
    int width, height;
  public:
    void set_values(int a, int b) { width = a; height = b;}
};

//base class 2
class COutput{
  public:
    void output(int i) { cout << i << endl;}
};
//derived class
class CRectangle:public CPolygon, public COutput{
  public:
    int area(void) {return (width*height);}
};

//derived class
class CTriangle:public CPolygon, public COutput{
  public:
    int area(void) {return (width*height/2);}
};



int main() {
  CRectangle rect;
  CTriangle tri;

  rect.set_values(3, 4);
  tri.set_values(3, 4);

  rect.output (rect.area());
  tri.output (tri.area());

  return 0;
}

<br>

### Struct vs. Class


| struct| class |
| -------- | -------- |
|預設 public 屬性 | 預設 private 屬性 |
|預設 public 繼承 | 預設 private 繼承|
|不能用在 template | 可以用在 template |

<br>

## 資料結構 (Data Structure)

### Containers

<br>

### Stack

> LIFO


- Stack example

<br>

### Queue

> FIFO

<br>

- Queue example

<br>

### Circular Queue

> **Why use it?**
> 重新看一次Queue:
> 
> 

- Circular Queue

### Link List

### Tree

### 二元樹 (Binary Tree) (chap.5)

### Prefix, Infix, Postfix (chap.5)

- **Algorithm: from infix to postfix**


<br>

## 演算法 (Algorithm)


### 複雜度 (Complexity)

- **空間複雜度 (Space Complexity)**

- **時間複雜度 (Time Complexity)**

- **Big Oh function**

### 遞迴 (Recursive)


- 終止條件 (Termination Condition)


- Recursion vs. Iteration

### Divide and Conquer

<br>

## 演算法 - 動態規劃 (DP, Dynamic Programming)
https://web.ntnu.edu.tw/~algo/DynamicProgramming.html

https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://m.youtube.com/watch%3Fv%3D2DvjUleLCx8&ved=2ahUKEwih4K38g6aDAxVvslYBHUtqDmkQwqsBegQIEBAF&usg=AOvVaw3Ea7zKYSKduzaZ609NNwS7

### 概念

### 經典題型

### 範例

<br>

## 演算法 - 排序 (Sorting)

### Bubble Sort

### Selection Sort

### Insertion Sort

### Merge Sort

### Heap Sort

### Quick Sort

### Binary Search

- Recursive way

### 樹的遍歷 (Tree Traversal)

### 其他 - Counting Sort, Radix Sort, Bucket Sort

### 排序演算法的特性討論 - Stable/Time Complexity/Space Complexity

<br>

## 物件導向 (OOP, Object-oriented programming) - Part.II

### typedef

### 函數名稱重載 (Function name Overloading)

### 樣板函數 (Template function) & 樣板類別 (Template class)

### 運算子重載 (Operator Overloading)

### Virtual function