---
# System prepended metadata

title: 程式設計Ⅱ【筆記ⅡⅠ】
tags: [Programming]

---

# 程式設計Ⅱ【筆記ⅡⅠ】

* [name=Ivy Lin]
* [筆記Ⅰ](https://hackmd.io/lvLLSXxoTo6hLxpEyBIJbQ)
* [筆記ⅠⅠ](https://hackmd.io/ukBiB1VJTB-T5T4c_uAA3g)
* [//筆記Ⅳ](https://hackmd.io/Ts0lnTMpQgGPGw7cvc3X-A)


## 第八週 < *2023.10.31* >

* ***standard library namespace***
    * *#include <iostream>*
        * *using namespace std;*
        * *setprecision();* //設定精準度(double小數點後幾位)
    * *#include<algorithm>* //for_each 的標頭檔
    * *#include<iomanip>* //設定cout格式的標頭檔
    * *#include<functional>* //可以使用function這個container來宣告函數的變數
        * 宣告例子 => *void print(function<int(double,double)> f);* //function 的回傳值是int, 傳入值是兩個double
    * *#include<math.h>* //數學運算值 Ex.fabs(); ->取絕對值
    
    


* ***string*** 資料型態
    * 可以使用'+'來連接字串
    * *string* 相關函數 
        => *s.length()* 計算字串長度
        => *s.clear()* 清空字串
        => *s.empty()* 查看字串是否為空
    
* ***auto 好用的 type inference***
* ***complex 資料型別*** //實數、虛數
* ***允許定義兩個名字相同但長相不同的function***
    
* ***Range-based for loop***
    * *vector < type > v_name*
        * *standard library 裡面定的 container*
        * *vector.push_back(value);* //將value丟到vector中
        * *vector.begin()* //vector開頭
        * *vector.end()* //vector結尾
    
    * *for(const auto& i:v)* //特殊寫法
        * *setw(num)* //一個輸出設成幾個字元寬度
    
    
* ***Reference &***
    * 幫變數取別名(效能等同C語言的指標)
    * 型別宣告方式 => *type&*
    
    
* ***Lambda functions***
    * 僅需寫"[]"作為函數名稱
    * "[]"內要填寫function多用的值(或變數)
```clike=
//Example
for each(v.begin(), v.end(),
    [](auto& n){
        n+=7;
    }
);
```
    
* ***Class 物件導向設計***
    * 成員預設是*private* //不可被外部使用
    * *public*區塊 //可以開放給外部使用
```clike=
//Example
class complex{
private:
    double re;
    double im;
  
public:
    // constructor 寫法
    //class 名字(傳入參數): 初值設定 {函式內部程式碼}
    //class 名字(傳入參數) {函式內部程式碼}
    complex(double r,double i): re{r},im{i} {} 
    complex(double r): re{r}, im{0} {}
    complex(): re{0},im{0} {}
    
    double real() const
    //加上 const ->不讓外部函示改動(cpp會辨識有const的函示，使重新定義的宣告失效)
    {
        return re;
    }
    double real(double d)
    {
        re=d;
    }
    
    complex& operator+=(complex z) 
    //定義 complex 間的 "+=" 
    //compiler會把operator拔掉剩下+=
    {
        re+=z.re,im+=z.im;
        return *this;  //特殊指標=>指向當前處理的物件
    }
    
    //宣告class的朋友
    friend std::ostream & operator<<(std::ostream& os, const complex& a);
};
    
//朋友的宣告
ostream& operator<<(ostream& os, const complex& a)
{
    if (a.im>0)
        os << a.re << "+" << a.im <<  "i";
    else if (a.im<0)
        os << a.re <<  a.im << "i";
    else
        os << a.re;
    return os;
}
    
complex v{2.0}; //宣告一個complex v初值為 2.0+0i
```
                  
                  
## 第九週 < *2023.11.7* >
    
### 實作一個 Rational class

```clike=
#include <iostream>
#include <iomanip>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;

// define
class Rational
{
private:
    int number;
    int denom;

public:
    // 備註:分號要拿掉
    Rational() : number{0}, denom{1} { cout << "call default constructor\n"; }
    Rational(int n) : number{n}, denom{1} { cout << "call Rational(n)\n"; }
    Rational(int n, int d);
    // Rational(int n, int d) : number{n}, denom{d} {cout << "call Rational(n,d)\n"};
};

// global
Rational::Rational(int n, int d) : number{n}, denom{d} { cout << "call Rational(n,d)\n"; }

// function

// main
int main()
{
    Rational a;
    Rational b(3);
    Rational c(4, 5);

    return 0;
}
```
    

* 結構體 class 的一些簡介和實作
```clike=
#include <iostream>
using namespace std;
class Cwin
{
public:
    int weight;
    int length;

    // 建構函數(名字與結構體名稱相同，無返回型別->通常用來初始化)
    Cwin() : weight(0), length(0) {}
    Cwin(int x, int y) : weight(x), length(y) {}

    // 成員函數
    space()
    {
        return weight * length;
    }
    // 自定義操作符
    // this是當前對象的指標(一個代號)，因此使用指標取值方式
    // const可以保護被引用的對象不在函數內被更改值
    //"&"在這邊是類似指標的用法(引用原本的函數而不是另外複製一份)
    Cwin operator+(const Cwin &other) const
    {
        Cwin result;
        result.x = this->x + other.x;
        result.y = this->y + other.y;
        return result;
    }
};

int main()
{
    Cwin x1; //
    Cwin x2(10, 20);
    x1.weight = 5;
    x1.length = 10;
    cout << "x1 space =" << x1.space() << endl;
    cout << "x2 space =" << x2.space() << endl;

    // 使用自定義的加法
    Cwin sum = x1 + x2;
    cout << "sum x1,x2=" << sum << endl;

    return 0;
}
```
    
//分辨使用const和'&'的時機
    * const : 不想改動原始值，避免作出規範外舉動設的安全值
    * & : 當函數會需要取用傳入變數的值，或是需要回傳/更動傳入變數值的時候會使用
    
### 前情提要

####  *access control*
* 一個 class 的 member 可以分成 
    * private ->只有同一個 class 的其他 member functions，或是該 class 的 friends 才能使用。
    * protected ->只有同一個 class 的其他 member functions，或是該 class 的 friends，或是 derived classes 的 member functions 才能使用。
    * public ->大家都可以用。


繼承的時候，在 class 名稱後面可以用 : 
* *public base_class_name*
* *: protected base_class_name*
* *: private base_class_name* 
的形式，來指定繼承而來的 public 和 protected functions，要放在自己的哪個區域。
    
#### *virtual function*

* 用來達到 *run-time polymorphic type* 的效果 (要搭配 pointers 或 references)
* Compiler 通常是利用所謂的 virtual function table (vtbl) 來記錄指標，透過指標指向對應的 virtual functions。
* 一個 class 只要包含了任何 *pure virtual function*，就是一個 *abstract class*。Abstract class 不能產生物件，只能當作其他 classes 的 interface。
    
    
```clike=
#include <iostream>
#include <vector>

namespace shapes {
using namespace std;
struct Point
{
	int x;
	int y;
	Point(int a, int b) : x{a}, y{b} { }
};

class Shape
{
public:
	virtual Point center() const =0; // pure virtual function
	virtual void shift(Point dxy) =0;
	virtual void rotate(int angle) =0;
	virtual void draw() =0;
	virtual ~Shape() {}
};


class Rectangle;
class Circle : public Shape
{
public:
	Circle(Point p, int rr) : c{p}, r{rr} { }
	Point center() const override
	{
		return c;
	}
	void shift(Point dxy) override
	{
		c.x += dxy.x;
		c.y += dxy.y;
	}
	void rotate(int ) override { }
	void draw() override
	{
		cout << c.x << " " << c.y << " " << r << "\n";
	}
	friend bool bounding(Rectangle &rec, Circle &cir);
private:
	Point c;
	int r;
};

class Rectangle : public Shape
{
public:
	Rectangle(Point p1, int wid, int hei) : ul{p1}, w{wid}, h{hei} { }
	Point center() const override
	{
		return
			Point(ul.x+w/2, ul.y+h/2);
	}
	void shift(Point dxy) override
	{
		ul.x += dxy.x;
		ul.y += dxy.y;
	}
	void rotate(int ) override { }
	void draw() override
	{
		cout << ul.x << " " << ul.y << " : ";
		cout << w << " " << h << "\n";
	}
	friend bool bounding(Rectangle &rec, Circle &cir);
private:
	Point ul;
	int w, h;
};

void move_all(vector<Shape*>& v, Point to)
{
	for (auto p : v)
		p->shift(to);
}
void rotate_all(vector<Shape*>& v, int angle)
{
	for (auto p : v)
		p->rotate(angle);
}

void draw_all(vector<Shape*>& v)
{
	for (auto p : v)
		p->draw();
}

bool bounding(Rectangle &rec, Circle &cir)
{
	return  (cir.c.x - cir.r)>=(rec.ul.x) && (cir.c.x+cir.r)<=(rec.ul.x+rec.w)
			&& (cir.c.y - cir.r)>=(rec.ul.y) && (cir.c.y+cir.r)<=(rec.ul.y+rec.h);
}
} // namespace shapes

int main()
{
	using namespace shapes;
	//Shape s; // no objects of an abstract class can be created.
	Circle c1 {Point{3,2},3};
	Circle c2 {Point{2,5},4};
	Circle c3 {Point{-2,-3},5};
	Rectangle r1 {Point{-3,-1},10,10};
	vector<Shape*> cp {&c1, &c2, &c3, &r1};

	cout << "Three circles:\n";
	draw_all(cp);
	cout << "Shifted by (5, 10)\n";
	move_all(cp, Point(5,10));
	draw_all(cp);

	cout.setf(ios::boolalpha);        // set format for bool
	cout << bounding(r1, c1) << endl; // print true or false instead of 1 or 0
	cout << bounding(r1, c2) << endl;
	cout << bounding(r1, c3) << endl;
}

```
    
## 第十週 < *2023.11.14* >
> *MINI PROJECT DEMO*
    

## 第十一週 < *2023.11.21* >
    
   
```clike=
#include <iostream>
#include <memory>
#include <cstdlib>


using namespace std;
template<typename T>
class List {
private:
    struct Node
    {
        T val;
        shared_ptr<const Node> next;
        Node(T v, const shared_ptr<const Node>& n): val{v}, next{n}  { }
    };

    shared_ptr<const Node> head;

    explicit List (const shared_ptr<const Node> & nodes) : head{nodes} { }

public:

    List(): { } //head{nullptr} done by shared_ptr

    List(T val, const List & tail): head{make_shared<Node>(val, tail.head)} { }

    bool isEmpty() const { return (head == nullptr); }

    T car() const {
        if (isEmpty()) exit(EXIT_FAILURE);
        return head->val;
    }
    List cdr() const {
        if (isEmpty()) exit(EXIT_FAILURE);
        return List(head->next);
    }

    void show() const {
        if (isEmpty()) std::cout << ".\n";
        else {
            std::cout << car() << "->";
            cdr().show();
        }
    }
};


template <typename T>
List<T> cons(T val, List<T> tail)
{
    return List<T>{val, tail};
}

template<typename S, typename T, typename F>
List<S> mapl(F f, List<T> lst)
{
    if (lst.isEmpty())
        return List<S>();
    else
        return List<S>(f(lst.car()), mapl<S>(f, lst.cdr()));
}

template<typename T, typename P>
List<T> filter(P p, List<T> lst)
{
    if (lst.isEmpty())
        return List<T>();
    else {
      if (p(lst.car())) {
        return List<T>(lst.car(), filter(p, lst.cdr()));
      } else {
        return filter(p, lst.cdr());
      }
    }
}

template<typename S, typename T, typename F>
S foldr(F f, S accumul, List<T> lst)
{
    if (lst.isEmpty())
        return accumul;
    else
        return f(lst.car(), foldr(f, accumul, lst.cdr()));
}
template<typename S, typename T, typename F>
S foldl(F f, S accumul, List<T> lst)
{
    if (lst.isEmpty())
        return accumul;
    else
        return foldl(f, f(accumul, lst.car()), lst.cdr());
}
template<typename T, typename F>
void foreach(F f, List<T> lst)
{
    if (!lst.isEmpty()) {
        f(lst.car());
        foreach(f, lst.cdr());
    }
}
template<class T>
void print(List<T> lst)
{
    foreach([](T v)
    {
        cout << v << "->";
    }, lst);
    cout << ".";
}

template<typename T>
List<T> concat(const List<T> a, const List<T> b)
{
    if (a.isEmpty())
        return b;
    return List<T>(a.car(), concat(a.cdr(), b));
}
template<typename T>
T findmax(const List<T>  a)
{
    return foldl([](T acc, T x){return (acc>x) ? acc : x;}, a.car(), a);
}


List<int> qqsort(const List<int> a)
{

    if (a.isEmpty()) return a;

    int piv = a.car();

    List<int> le = qqsort(filter<int>([=](int x){return piv>x;}, a.cdr()));
    List<int> ri = qqsort(filter<int>([=](int x){return piv<=x;}, a.cdr()));
    return concat<int>(le, cons(piv, ri));
}


int main()
{
    List<int> l;
    List<int> n = cons(4, cons(5, cons(6, cons(7, cons<int>(8, l)))));
    l.show();
    n.show();

    auto m0 = mapl<double>([](int i){return i*0.5;} , n); // List<double>
    m0.show();
    n.show();
    auto m = mapl<int>([](int i){return i+1;} , n); // List<int>
    m.show();

    List<string> s = cons("abc"s, cons("defg"s, cons("hijkl"s, List<string>())));
    s.show();

    auto s_len = mapl<size_t>([](string r){return r.size();}, s);
    s_len.show();


    m = filter<int>([](int i){ return i%2==0;}, n);
    m.show();

    s = filter<string>([](string r){ return r.size()>4;}, s);
    s.show();


    cout << foldl([](int acc, int i){return acc+i;}, 0, m) << endl;
    print(m); // or print<int>(m);
    cout << endl;
    List<List<int>> ll;
    auto mm = cons(m, cons(n, ll)); // List<List<int>>
    foreach([](List<int> l) { cout << "["; print(l); cout << "]" << "->";}, mm);
    cout << endl;

    auto g = concat(n, m); //List<int>
    g.show();
    cout << findmax(g) << endl;

    List<int> ns = cons(9, cons(10, cons(6, cons(5, cons(4, cons(8, cons(7, l)))))));
    cout << "Before: ";
    ns.show();
    ns = qqsort(ns);
    cout << "After: ";
    ns.show();

}
```

   
* 這個C++程式定義了一個基本的函數式風格鏈表實現，展示了各種列表操作，包括映射、過濾、折疊、串聯和快速排序。



* List 類別:

> List 類別是一個泛型的鏈表實現。
> 鏈表中的每個節點由 Node 結構表示，包含一個值 (val) 和指向下一個節點的共享指針 (next)。
> 列表本身由指向頭節點的共享指針 (head) 表示。
    
* 建構子:

> 有兩個建構子：一個默認建構子，初始化一個空列表，以及一個建構子，接受一個值和另一個列表，以在前端創建具有給定值的新列表。
* 基本列表操作:

> isEmpty(): 檢查列表是否為空。
> car(): 返回列表的第一個元素。
> cdr(): 返回一個新列表，不包含第一個元素。
> show(): 印出列表的元素。

* 列表操作 (map、filter、fold、foreach、print、concat、findmax):

> mapl: 對列表的每個元素應用一個函數，生成一個新列表。
> filter: 根據一個預測函數過濾列表的元素。
> foldr 和 foldl: 使用二元函數在列表上執行右折疊和左折疊（累加）。
> foreach: 對列表的每個元素應用一個函數。
> print: 印出列表的元素。
> concat: 串聯兩個列表。
> findmax: 找到列表中的最大元素。
* qqsort (鏈表的快速排序):

> qqsort: 實現了鏈表的快速排序算法。
* 主函數:

> 創建並操作整數和字符串列表，使用定義的操作。
> 演示了映射、過濾、折疊、打印、串聯和快速排序的使用。

* 這個程序展示了在C++中使用模板和Lambda函數來處理通用類型，並為鏈表操作提供函數式風格的接口，呈現了函數式編程的概念。 