Linked List

這個禮拜最令我傷神的，不過幸好很久以前有想過一次，所以要回復記憶比較沒有那麼困難。首先我先把C++版本的linked list刻出來，當然骨幹是參考別人的，然後自己有改了些東西，沒花多久時間很快就用出來了。

以下是標頭檔：

class CKLinkList{
    private:
        struct node {
            int x;
            int y;
            int z;
            node *link;
        } *p;

        int count_i;

    public:
        CKLinkList();
        void append(int);
        void insert_after(int,int);
        void insert_first(int);

        void display(void);
        void display_line(void);
        int length(void);
        void del(int);
        ~CKLinkList();
};

接下來是實作

#include <iostream>
#include "linklist.h"

using namespace std;

CKLinkList::CKLinkList(){
    p = NULL;
    count_i = 0;
};

int CKLinkList::length(){
    return count_i;
};

void CKLinkList::del(int num){
    node *q, *r;
    q = p;

    // No node
    if (p == NULL) return;

    // Delete the first node
    if (q->x == num){
        p = q->link;
        delete q;
        count_i--;
        return;
    }

    // Delete the remainder
    r = q;
    while( q != NULL){
        if (q->x == num){
            r->link = q->link;
            delete q;
            count_i--;
            return;
        }

        r = q;
        q = q->link;
    }
};

void CKLinkList::insert_first(int num){

    node *q, *t;
    q = p;

    t = new node;
    t->x = num;
    t->y = num*2;
    t->z = num*3;

    t->link = q;
    p = t;
    count_i++;
};

void CKLinkList::insert_after(int start_val,int num){
    node *q, *t;

    if (start_val != 0){
        q = p;
        while(q->link != NULL){
            if (q->x == start_val){

                t = new node;
                t->x = num;
                t->y = num*2;
                t->z = num*3;
                t->link = q->link;
                q->link = t;

                count_i++;
                return;
            }

            q = q->link;
        }
    }
};

void CKLinkList::append(int num){
    node *q, *t;

    if (p == NULL){
        p = new node;
        p->x = num;
        p->y = num*2;
        p->z = num*3;
        p->link = NULL;
    } else {
        q = p;
        while(q->link != NULL){
            q = q->link;
        }

        t = new node;
        t->x = num;
        t->y = num*2;
        t->z = num*3;
        t->link = NULL;
        q->link = t;
    }

    count_i++;
};

void CKLinkList::display_line(void){
    node *q;

    for(q = p; q != NULL; q = q->link){
        cout << " <- " << q->x;
    }

    cout << endl;
};

void CKLinkList::display(void){
    node *q;

    for(q = p; q != NULL; q = q->link){
        cout << "This is : " << q->x << ", " << q->y << ", " << q->z << endl;
    }
};

CKLinkList::~CKLinkList(){
    node *q;
    if (p == NULL) return;

    while (p != NULL){
        q = p->link;
        delete p;
        p = q;
    }
};

接下來我看到了一個使用C++ template去實作的版本，應該說是某個老師的教學課程(參考第10,11,12章)，我就順便把她的課程講義看過一遍，然後把他的版本做出來。第一次使用C++的template，雖然滿麻煩的，但是真的是很強大，看來以後搞不好我的每個程式都要用template去做出來。以下是template的版本：

#include <iostream>
using namespace std;

template <class T>
class ChainNode {
    private:

    public:
        T data;
        ChainNode<T> *link;

        ChainNode(void){};
        ChainNode(const T& data){ this->data = data; };
        ChainNode(const T& data, ChainNode<T> *link){
            this->data = data;
            this->link = link;
        };
};

template <class T>
class Chain {
    private:
        ChainNode<T> *first;
        int count;

    public:
        Chain(void){ first = NULL; count = 0; };
        bool isEmpty() const {return first == NULL;}
        int IndexOf(const T&) const;
        int size(void){return count;}
        void Delete(int);
        void Insert(int,const T&);
        void Display(void);
        ~Chain();
};

// Destruction
template <class T>
Chain<T>::~Chain() {

    while (first != NULL){
        ChainNode<T> *next = first->link;
        delete first;
        first = next;
    }
};

template <class T>
int Chain<T>::IndexOf(const T& theElement) const{

    ChainNode<T> *currentNode = first;
    int index = 0;
    while(currentNode != NULL && currentNode->data != theElement){
        currentNode = currentNode->link;
        index++;
    }

    if (currentNode == NULL)
        return -1;
    else
        return index;
};

template <class T>
void Chain<T>::Delete(int theIndex){
    if (first == NULL) throw "Can not delete empty chain";

    ChainNode<T> *deleteNode;
    if (theIndex == 0){
        deleteNode = first;
        first = first->link;
        delete deleteNode;
        count--;

    } else {
        ChainNode<T> *p = first;
        for(int i =0; i< theIndex-1; i++){
            if (p == NULL) throw "Element not exist";
            p = p->link;
        }

        deleteNode = p->link;
        p->link = p->link->link;
        delete deleteNode;
        count--;
    }
}

template <class T>
void Chain<T>::Insert(int theIndex, const T& theElement){
    if (theIndex < 0) throw "Bad";

    if (theIndex == 0){
        first = new ChainNode<T>(theElement,first);
        count++;
    } else {
        ChainNode<T> *p = first;
        for(int i = 0; i < theIndex-1; i++){
            if (p == NULL) throw "Not Exist";
            p = p->link;
        }
        
        p->link = new ChainNode<T>(theElement, p->link);
        count++;
    }
};

template <class T>
void Chain<T>::Display(void){

    ChainNode<T> *p = first;

    while(p != NULL){
        cout << " <- " << p->data;
        p = p->link;
    }
    cout << endl;
};

int main() {
    cout << "This is LinkList .." << endl;

    Chain<int> *list = new Chain<int>;
    cout << "Size: " << list->size() << endl;

    list->Insert(0,1);
    list->Display();
    list->Insert(0,2);
    list->Display();
    list->Insert(1,3);
    list->Display();
    list->Insert(1,4);
    list->Display();
    list->Insert(0,5);
    list->Display();
    list->Delete(2);
    list->Display();

    cout << "Size: " << list->size() << endl;
}

繼續努力加油吧，這星期把linked list搞完之後還有很多要充實的，以上的source code都公布在github上看(其實blog根本不適合看這麼多程式碼是吧XD)。