# 程式設計Ⅱ【筆記ⅡⅠ】
* [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函數來處理通用類型，並為鏈表操作提供函數式風格的接口，呈現了函數式編程的概念。
Sign in with Wallet
Connect another wallet