鏈結串列(Linked List)

鏈結串列是由許多相同資料型態的項目,所組成的有限序列,這邊使用單向鏈結串列,串列每個節點除了要儲存原本的資料,還必須要儲存下一筆資料的位址,大概為以下的流程:
1.建立新節點,並另一流動指標指向頭節點(ptr=head)。
2.建立另一個新節點,並把兩個節點串起來(ptr->next=newnode)。
3.將流動指標指向剛剛建立的節點(ptr=ptr->next)。
4.重複上面2和3的步驟。

#include <iostream> 
using namespace std;

struct List{
    char *name;
    int age;
    List *next;
};

List *createList(char*name, int age);
void addANode(List *&ptr, char*name, int age); //要用參考才能改變ptr引數的指向位址
void deleteList(List *head);
void printfList(List *head);

int main(){
    List *head = createList("Mike", 18);
    List *ptr = head;
    addANode(ptr, "Bill", 20);
    addANode(ptr, "Lisa", 15);

    ptr = head;
    printfList(ptr);

    deleteList(head);
    return 0;
}

List *createList(char*name, int age){
    List *head = new List;
    if (!head){
        cout << "配置記憶體失敗" << endl;
        exit(1);
    }
    head->name = name;
    head->age = age;
    head->next = NULL;
    return head;
}
void addANode(List *&ptr, char*name, int age){
    List *newnode = new List;
    if (!newnode){
        cout << "配置記憶體失敗" << endl;
        exit(1);
    }
    newnode->name = name;
    newnode->age = age;
    newnode->next = NULL;
    ptr->next = newnode;
    ptr = ptr->next;
}

void printfList(List *ptr){
    while (ptr != NULL){
        cout << "姓名:" << ptr->name << '\t' << "年齡:" << ptr->age << endl;
        ptr = ptr->next;
    }
}

void deleteList(List *head){
    while (head != NULL){
        List *delptr = head;
        head = head->next;
        delete delptr;
    }
}

陣列結構(Array)

陣列是一排緊密相鄰的記憶體,我們這邊用陣列來儲存矩陣,以及進行矩陣的相加、轉置、相乘等操作。
稀疏矩陣是一種很多內部元素為0的矩陣,我們可以用傳統的方式儲存,但是比較浪費記憶體,這邊示範改良的三項式儲存方式,共有n列3行,第一列分別表示陣列的列數、行數、非零的元素個數,隨後每列分別表示某個非零元素的列數、行數、實際值,以下為實際的程式碼。

#include <iostream> 
using namespace std; 

void createMatrix(int *a, int dimX, int dimY);
void printfMatrix(int *a, int dimX, int dimY);
void addMatrix(int *a, int *b, int *c, int dimX, int dimY);
void transMatrix(int *a, int *b, int dimX, int dimY);
void multiplyMatrix(int *a, int *b, int *c, int m, int n, int p);
void compressMatrix(int *a, int *b, int m, int n, int p);

int main(){
    int a[12], b[12], add[12], trans[12], multiply[16];
    createMatrix(a, 4, 3);
    createMatrix(b, 4, 3);
    addMatrix(a, b, add, 4, 3);
    transMatrix(a, trans, 4, 3);
    multiplyMatrix(a, trans, multiply, 4, 3, 4);

    printfMatrix(a, 4, 3);
    printfMatrix(b, 4, 3);
    printfMatrix(add, 4, 3);
    printfMatrix(trans, 3, 4);
    printfMatrix(multiply, 4, 4);

    int sparse[36], compress[9];
    int size=6;
    for(int i=0; i < size; i++){
        for(int j=0; j < size; j++){
            sparse[i*size+j] = 0;
        }
    }
    sparse[14] = 9;
    sparse[25] = 3;
    compressMatrix(sparse, compress, size, size, 2);
    printfMatrix(sparse, 6, 6);
    printfMatrix(compress, 3, 3);

    system("PAUSE");
    return 0;
}

void createMatrix(int *a, int dimX, int dimY){
    //每個矩陣值範圍都從0~9
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            a[row*dimY+col] = rand()%10;
        }
    }
}

void printfMatrix(int *a, int dimX, int dimY){
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            cout << a[row*dimY+col] << '\t';
        }
        cout << '\n';
    }
    cout << '\n';
}

void addMatrix(int *a, int *b, int *c, int dimX, int dimY){
    if(dimX<=0 || dimY<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            c[row*dimY+col] = a[row*dimY+col] + b[row*dimY+col];
        }
    }
}

void transMatrix(int *a, int *b, int dimX, int dimY){
    if(dimX<=0 || dimY<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < dimX; row++){
        for(int col=0; col < dimY; col++){
            b[col*dimX+row] = a[row*dimY+col];
        }
    }
}

void multiplyMatrix(int *a, int *b, int *c, int m, int n, int p){
    //matrix(m*n) * matrix(n*p) =  matrix(m*p)
    if(m<=0 || n<=0 || p<=0){
        cout << "維度必須大於0" << endl;
        return;
    }
    for(int row=0; row < m; row++){
        for(int col=0; col < p; col++){
            int temp = 0;
            for(int k=0; k < n; k++){
                temp = temp + a[row*n+k] * b[k*p+col];
            }
            c[row*p+col] = temp;
        }
    }
}

void compressMatrix(int *a, int *b, int m, int n, int p){
    //m*n的矩陣共有p個元素不為0
    if(m<=0 || n<=0){
        cout << "維度必須大於0" << endl;
        return;
    }

    b[0] = m;
    b[1] = n;
    b[2] = p;
    int temp = 3;
    for(int row=0; row < m; row++){
        for(int col=0; col < n; col++){
            if(a[row*n+col]!=0){
                b[temp] = row;
                b[temp+1] = col;
                b[temp+2] = a[row*n+col];
                temp += 3;
            }
        }
    }
}

狀態模式(State Pattern)

狀態模式:允許物件隨著內部狀態改變而改變行為,就好像物件的類別改變一樣。

有時候成員函式內部,有許多if else的判斷式,後續更新可能持續增加判斷式,以至於最後變得冗長不好維護,這時可以用狀態模式將每個狀態視為一個獨立物件,讓後續需求更動能更好維護,不過也會造成類別變多的情況。

我們用門票販賣機來解釋狀態模式,販賣機有四種狀態,分別是有錢、沒錢、售出門票、門票售完,使用者有投錢和按下買票鍵兩個選擇,販賣機根據目前狀態,會對使用者行為產生對應的結果,我們用TicketMachine類別表示我們的販賣機,建構式參數代表門票數,預設狀態為沒錢,以下為程式碼。

#include <iostream>
using namespace std;

class TicketMachine{
private:
    const static int SOLD_OUT = 0;
    const static int NO_MONEY = 1;
    const static int HAS_MONEY = 2;
    const static int SOLD = 3;
    int m_count;
    int m_state;
public:
    TicketMachine(int count){
        m_count = count;
        m_state = NO_MONEY;
    }
    void insertMoney();
    void buyTicket();
    void dispense();
};
void TicketMachine::insertMoney(){
    if (m_state == HAS_MONEY){ 
        cout << "禁止投錢,已有鈔票" << endl; 
    }
    else if (m_state == NO_MONEY){ 
        m_state = HAS_MONEY; 
        cout << "投入鈔票" << endl; 
    }
    else if (m_state == SOLD_OUT){ 
        cout << "禁止投錢,票已售完" << endl; 
    }
    else if (m_state == SOLD){
        cout << "稍待片刻" << endl;
    }
}
void TicketMachine::buyTicket(){
    if (m_state == HAS_MONEY){
        cout << "買票成功" << endl;
        m_state = SOLD;
        dispense();
    }
    else if (m_state == NO_MONEY){
        cout << "買票失敗,您沒投錢" << endl;
    }
    else if (m_state == SOLD_OUT){
        cout << "買票失敗,票已售完" << endl;
    }
    else if (m_state == SOLD){
        cout << "買票失敗" << endl;
    }
}
void TicketMachine::dispense(){
    cout << "正在售票" << endl;
    m_count--;
    if (m_count == 0){
        m_state = SOLD_OUT;
        cout << "票已售完" << endl;
    }
    else{
        m_state = NO_MONEY;
    }
}
int main(){
    TicketMachine myTicketMachine(2); //預設有2張票
    myTicketMachine.buyTicket();
    myTicketMachine.insertMoney();
    myTicketMachine.buyTicket();
    myTicketMachine.insertMoney();
    myTicketMachine.buyTicket();
    
    return 0;
}

假使我們之後要增加功能,上面的設計除了增加一個狀態,buyTicket()和insertMoney()函式都必須加上更多的判斷式和處理,這邊使用狀態模式,讓每一個狀態實踐各自的動作,以下為程式碼。

#include <iostream>
using namespace std;

class State{
public:
    virtual void insertMoney() = 0;
    virtual void buyTicket() = 0;
};
class Machine{
public:
    State *m_soldOutState;
    State *m_noMoneyState;
    State *m_hasMoneyState;
    State *m_soldState;
    virtual void insertMoney() = 0;
    virtual void buyTicket() = 0;
    virtual void dispense() = 0;
    virtual void setState(State *state) = 0;
};

class NoMoneyState : public State{
private:
    Machine *m_ticketMachine;
public:
    NoMoneyState(Machine *machine){ m_ticketMachine = machine; }
    void insertMoney(){
        m_ticketMachine->setState(m_ticketMachine->m_hasMoneyState);
        cout << "投入鈔票" << endl;
    }
    void buyTicket(){ cout << "買票失敗,您沒投錢" << endl; }
};
class HasMoneyState : public State{
private:
    Machine *m_ticketMachine;
public:
    HasMoneyState(Machine *machine){ m_ticketMachine = machine; }
    void insertMoney(){ cout << "禁止投錢,已有鈔票" << endl; }
    void buyTicket(){
        cout << "買票成功" << endl;
        m_ticketMachine->setState(m_ticketMachine->m_soldState);
        m_ticketMachine->dispense();
    }
};
class SoldState : public State{
private:
    Machine *m_ticketMachine;
public:
    SoldState(Machine *machine){ m_ticketMachine = machine; }
    void insertMoney(){cout << "稍待片刻" << endl;}
    void buyTicket(){cout << "買票失敗" << endl;}
};
class SoldOutState : public State{
private:
    Machine *m_ticketMachine;
public:
    SoldOutState(Machine *machine){ m_ticketMachine = machine; }
    void insertMoney(){ cout << "禁止投錢,票已售完" << endl; }
    void buyTicket(){ cout << "買票失敗,票已售完" << endl; }
};

class TicketMachine : public Machine{
private:
    State * m_state;
    int m_count;
public:
    TicketMachine(int count){
        m_count = count;
        m_soldOutState = new SoldOutState(this);
        m_noMoneyState = new NoMoneyState(this);
        m_hasMoneyState = new HasMoneyState(this);
        m_soldState = new SoldState(this);
        m_state = m_noMoneyState;
    }
    ~TicketMachine(){
        delete m_soldOutState;
        delete m_noMoneyState;
        delete m_hasMoneyState;
        delete m_soldState;
    }
    void insertMoney(){ m_state->insertMoney(); }
    void buyTicket(){ m_state->buyTicket(); }
    void dispense();
    void setState(State *state){ m_state = state; }
};
void TicketMachine::dispense(){
    cout << "正在售票" << endl;
    m_count--;
    if (m_count == 0){
        m_state = m_soldOutState;
        cout << "票已售完" << endl;
    }
    else{
        m_state = m_noMoneyState;
    }
}

int main(){
    TicketMachine myTicketMachine(2); //預設有2張票
    myTicketMachine.buyTicket();
    myTicketMachine.insertMoney();
    myTicketMachine.buyTicket();
    myTicketMachine.insertMoney();
    myTicketMachine.buyTicket();
    
    return 0;
}

樣板方法模式(Template Method Pattern)

樣板方法模式:將一個演算法的骨架定義在一個方法中,而其中的某些方法定義在次類別中,樣板方法讓次類別可以在不改變演算法架構的情況下,重新定義演算法中的某些步驟。

我們用泡茶和咖啡來解釋樣板方法模式,假設我們有以下兩個類別Coffee和Tea,我們可以看出兩個類別提供的方法,有很多類似的地方。

class Coffee{
public:
    void prepareRecipe(){
        boilWater();
        brewCoffeeGrinds();
        pourInCup();
    }
    void boilWater(){ cout << "煮開水" << endl; }
    void brewCoffeeGrinds(){ cout << "煮咖啡" << endl; }
    void pourInCup(){ cout << "倒入杯中" << endl; }
};

class Tea{
public:
    void prepareRecipe(){
        boilWater();
        steepTeaBag();
        pourInCup();
    }
    void boilWater(){ cout << "煮開水" << endl; }
    void steepTeaBag(){ cout << "泡茶" << endl; }
    void pourInCup(){ cout << "倒入杯中" << endl; }
};

這時我們可以用樣板方法模式,創造一個Beverage類別,將Coffee和Tea類別相同的地方,抽取到Beverage類別內。

#include <iostream>
using namespace std;

class Beverage{
public:
    void prepareRecipe(){
        boilWater();
        brew();
        pourInCup();
    }
    void boilWater(){ cout << "煮開水" << endl; }
    virtual void brew() = 0;
    void pourInCup(){ cout << "倒入杯中" << endl; }
};
class Coffee : public Beverage{
public:
    void brew(){ cout << "煮咖啡" << endl; }
};

class Tea : public Beverage{
public:
    void brew(){ cout << "泡茶" << endl; }
};

int main(){
    Coffee myCoffee;
    Tea myTea;
    myCoffee.prepareRecipe();
    myTea.prepareRecipe();

    return 0;
}

表象模式(Facade Pattern)

表象模式:提供了一個統一的介面,用來存取次系統的一群介面,讓次系統共容易使用。

我們以泡咖啡來形容表象模式,假設泡咖啡有以下幾種流程:
1.煮開水
2.準備咖啡粉
3.倒入熱水
4.攪拌

我們可以使用表象模式,實踐一個表象類別,提供一個易操作的介面來簡化原先的複雜介面,如果我們需要次系統的複雜操作,可以使用原來的介面,如果需要一個方便使用的介面,就使用這個新的表象類別,以下為程式碼。

#include <iostream>
using namespace std;

class Boil{
public:
    void boilWater(){ cout << "煮開水" << endl; }
};
class Coffee{
public:
    void blueMountain(){ cout << "準備藍山咖啡" << endl; }
    void mandheling(){ cout << "準備曼特寧咖啡" << endl; }
};
class Pour{
public:
    void pourHotWater(){ cout << "倒熱水" << endl; }
    void pourColdWater(){ cout << "倒冷水" << endl; }
};
class Stir{
public:
    void fastStir(){ cout << "快速攪拌" << endl; }
    void slowStir(){ cout << "慢慢攪拌" << endl; }
};

class MakeCoffee{
private:
    Boil m_boil;
    Coffee m_coffee;
    Pour m_pour;
    Stir m_stir;
public:
    MakeCoffee(Boil, Coffee, Pour, Stir);
    void process();
};
MakeCoffee::MakeCoffee(Boil boil, Coffee coffee, Pour pour, Stir stir){
    m_boil = boil;
    m_coffee = coffee;
    m_pour = pour;
    m_stir = stir;
}
void MakeCoffee::process(){
    m_boil.boilWater();
    m_coffee.blueMountain();
    m_pour.pourHotWater();
    m_stir.slowStir();
}

int main(){
    Boil boil; 
    Coffee coffee; 
    Pour pour; 
    Stir stir;
    MakeCoffee myCoffee(boil, coffee, pour, stir);
    myCoffee.process();
    
    return 0;
}

轉接器模式(Adapter Pattern)

轉接器模式:將一個類別的介面,轉換成另一個介面以供客戶使用,轉接器讓原本不相容的類別可以互相合作。

假使有一個既有的軟體系統,想要和新的廠商類別庫搭配使用,我們不能改變廠商提供的程式碼,如果也不想改變原本的系統,這時可以寫一個類別,將廠商的介面轉成和舊系統相容的介面。

下面例子有類別狼和狗,這兩個類別彼此不相容,我們建了一個轉接器,將狗類別的成員函式,讓狼類別去實作,而testDog()函式,可以接受轉接器和狗類別當參數,所以我們不需要改變類別,以及testDog()函式的程式碼,就能達到目的。

#include <iostream>
using namespace std;

class Dog{
public:
    virtual void bark(){ cout << "旺旺" << endl; }
    virtual void run(){ cout << "跑一段距離" << endl; }
};
class Wolf{
public:
    virtual void howl(){ cout << "嚎~~" << endl; }
    virtual void run(){ cout << "跑一大段距離" << endl; }
};
class WolfAdapter : public Dog{
private:
    Wolf *m_wolf;
public:
    WolfAdapter(Wolf *wolf){ m_wolf = wolf; }
    void bark(){ m_wolf->howl(); }
    void run(){ m_wolf->run(); }
};

void testDog(Dog *dog);

int main(){
    Dog myDog;
    Wolf myWolf;
    WolfAdapter myWolfAdapter(&myWolf);

    testDog(&myDog);
    testDog(&myWolfAdapter);

    return 0;
}

void testDog(Dog *dog){
    dog->bark();
    dog->run();
}

我們也可以設計一個雙向轉接器,讓他同時可當作兩個類別的介面,以下是簡單的示範。

#include <iostream>
using namespace std;

class Dog{
public:
    virtual void bark(){ cout << "旺旺" << endl; }
};
class Wolf{
public:
    virtual void howl(){ cout << "嚎~~" << endl; }
};
class Adapter : public Dog, public Wolf{
private:
    Wolf *m_wolf;
    Dog *m_dog;
public:
    Adapter(Wolf *wolf){ m_wolf = wolf; }
    Adapter(Dog *dog){ m_dog = dog; }
    void bark(){ m_wolf->howl(); }
    void howl(){ m_dog->bark(); }
};

void testDog(Dog *dog);
void testWolf(Wolf *wolf);

int main(){
    Dog myDog;
    Wolf myWolf;
    Adapter dogAdapter(&myWolf);
    Adapter wolfAdapter(&myDog);

    testDog(&dogAdapter);
    testWolf(&wolfAdapter);

    return 0;
}

void testDog(Dog *dog){
    dog->bark();
}
void testWolf(Wolf *wolf){
    wolf->howl();
}

命令模式(Command Pattern)

命令模式:將請求封裝成物件,可以讓我們使用不同的請求、佇列、或者日誌來參數化其他物件。

我們用遙控器來解釋命令模式,假使要設計操作家電的遙控器,按鍵代表操作某個家電,我們不將操作細節寫在搖控器物件上,而是將命令和按鍵綁定,當我們按下按鍵時,透過之前綁定的命令,遙控器知道要將訊息通知哪個物件,由此物件進行實際的操作。

實作上我們定義Command命令類別,命令實例皆繼承於此類別,命令實例透過傳入參數得到接收者,execute()方法定義實際的操作,用RemoteControl類別的setCommand()方法,將某個命令和遙控器相關,Light和Door是接收命令的接收者,並進行實際的操作,以下為程式碼。

#include <iostream>
using namespace std;

class Light{
public:
    void on(){cout<<"開燈"<on();}
};
class DoorOpenCommand : public Command{
private:
    Door *m_door;
public:
    DoorOpenCommand(Door *door){m_door=door;}
    void execute(){m_door->open();}
};

class RemoteControl{
private:
    Command *slot;
public:
    void setCommand(Command *command){slot=command;}
    void pressButton(){slot->execute();}
};

int main(){
    RemoteControl myControl;
    Light myLight;
    Door myDoor;
    Light OnCommandcommand1(&myLight);
    Door OpenCommandcommand2(&myDoor);

    myControl.setCommand(&command1);
    myControl.pressButton();
    myControl.setCommand(&command2);
    myControl.pressButton();
    return 0;
}

下面實作有多個按鍵的遙控器,可以存放3個開與關的命令,我們使用陣列記錄這些命令,以下為程式碼。

#include <iostream>
using namespace std;

class Light{
public:
    void on(){ cout << "開燈" << endl; }
    void off(){ cout << "關燈" << endl; }
};
class Door{
public:
    void open(){ cout << "開門" << endl; }
    void close(){ cout << "關門" << endl; }
};

class Command{
public:
    virtual void execute() = 0;
};
class NoCommand: public Command{
public:
    void execute(){ cout << "尚未綁定命令" << endl; }
};
class LightOnCommand: public Command{
private:
    Light *m_light;
public:
    LightOnCommand(Light *light){ m_light = light; }
    void execute(){ m_light->on(); }
};
class LightOffCommand: public Command{
private:
    Light *m_light;
public:
    LightOffCommand(Light *light){ m_light = light; }
    void execute(){ m_light->off(); }
};
class DoorOpenCommand: public Command{
private:
    Door *m_door;
public:
    DoorOpenCommand(Door *door){ m_door = door; }
    void execute(){ m_door->open(); }
};
class DoorCloseCommand: public Command{
private:
    Door *m_door;
public:
    DoorCloseCommand(Door *door){ m_door = door; }
    void execute(){ m_door->close(); }
};

class RemoteControl{
private:
    Command *m_onCommands[3];
    Command *m_offCommands[3];
public:
    RemoteControl(Command *);
    void setCommand(int slot, Command *on, Command *off);
    void pressOnButton(int slot){ m_onCommands[slot]->execute(); }
    void pressOffButton(int slot){ m_offCommands[slot]->execute(); }
};
RemoteControl::RemoteControl(Command *command){
    for (int i = 0; i < 3; i++){
        m_onCommands[i] = command;
        m_offCommands[i] = command;
    }
}
void RemoteControl::setCommand(int slot, Command *on, Command *off){
    m_onCommands[slot] = on;
    m_offCommands[slot] = off;
}

int main(){
    Light myLight;
    Door myDoor;
    LightOnCommand command1(&myLight);
    LightOffCommand command2(&myLight);
    DoorOpenCommand command3(&myDoor);
    DoorCloseCommand command4(&myDoor);

    NoCommand nocommand;
    RemoteControl myControl(&nocommand);
    myControl.setCommand(0, &command1, &command2);
    myControl.setCommand(1, &command3, &command4);
    for (int i = 0; i < 3; i++){
        myControl.pressOnButton(i);
        myControl.pressOffButton(i);
    }
    system("PAUSE");
    return 0;
}