C++クラステンプレート:ヘッダ付きチェーンテーブルの実装

チェーンテーブルの概念
チェーンテーブルは、線形テーブルに属する一般的な基本データ構造の1つです.同じ線形テーブルに属するものに順序テーブルがあり,我々がよく言う配列が順序テーブルである.
バンドヘッドチェーン
チェーンテーブルの実現には、テーブルヘッド付きとテーブルヘッドなしの2つの方法がある.最も原始的な方式、すなわちヘッダを持たない実現方式は、ヘッダノードを指すポインタ変数でチェーンテーブルの開始位置を記録し、ノードを挿入または削除する操作を行う場合、最初のノードと他のノードについて異なる判断を行い、その後、異なるコードでこの2つの状況をそれぞれ処理しなければならない.
ヘッダ付き実現方式とは、ヘッダノードとして空のノードを用い、そのdataドメインはデータを置かず、nextポインタは最初のデータが格納されたノードを指す.このような利点は、各データノードに同じタイプの前駆ノードがあり、どの位置で操作を実現しても、チェーンテーブルの開始位置、中間位置、または尾部位置を判断することなく、同じコードで実現できるという統一的な形式で記述できることである.
実現構想.
チェーンテーブルクラスのいくつかの基本的な方法を実装します.

ノード(チェーンテーブルの末尾まで)

を追加

挿入接点(任意の位置まで)

削除ノード

ノードの検索

チェーンテーブル長

を取得する.

ノードデータ

を取得する.

ソート

チェーンテーブルクラスLinklistの定義部分

template ElemType>
class Linklist {
    private:
        struct Node{
            ElemType data;
            Node* next;
            Node():next(nullptr){};
            Node(ElemType data, Node* next = nullptr):
                data(data), next(next){};
        };
        Node Head;

    public:
        Linklist() {};
        ~Linklist();

        void append(ElemType data);
        void insert(ElemType data, int pos = 0);
        bool del(int pos);
        int  search(ElemType data);
        int  getLength();
        ElemType getData(int pos);
        void sort(int(*compare)(ElemType& a, ElemType& b));
};

Linklistの実装部分

template 
Linklist::~Linklist() {
    Node *ptr = &Head;
    Node *t = nullptr;

    while(ptr->next != nullptr) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
    }
}

template 
void Linklist::append(ElemType data) {
    Node *ptr = &Head;

    while(ptr->next != nullptr) {
        ptr = ptr->next;
    }
    ptr->next = new Node(data);
}

/*             ，          */
template 
void Linklist::insert(ElemType data, int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr)
    {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }
    ptr->next = new Node(data, ptr->next);
}

template 
bool Linklist::del(int pos) {
    Node *ptr = &Head;
    Node *t = nullptr;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    if(p == pos) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
        return true;
    } else {
        return false;
    }

}

/*            ，    -1 */
template 
int Linklist::search(ElemType data) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(ptr->next->data == data) {
            return p;
        }
        p++;
        ptr = ptr->next;
    }
    return -1;
}

template 
int Linklist::getLength() {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        p++;
        ptr = ptr->next;
    }

    return p;
}

template 
ElemType Linklist::getData(int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    return ptr->next->data;
}

/*             int          
*      ： a>b ， compare(a, b)      0
*      ： a0
*    ： a=b ，compare(a, b)           0。
*/
template 
void Linklist::sort(int(*compare)(ElemType& a, ElemType& b)) {
    Node *ptr;
    Node *t;
    int tmp;
    bool sorted = false;

    while(!sorted) {
        sorted = true;
        ptr = &Head;
        t = ptr->next;
        while(ptr->next != nullptr && t->next != nullptr) {
            tmp = compare(t->data, t->next->data);
            if(tmp > 0) {
                ptr->next = t->next;
                t->next = ptr->next->next;
                ptr->next->next = t;
                sorted = false;
            }
            ptr = t;
            t = t->next;
        }
    }
}

作者:Wray Zhengリンク:http://www.codebelief.com/article/2016/11/linklist-implementation/