程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++封裝鏈式表

C++封裝鏈式表

編輯：關於C++

面向對象三大特性：封裝、繼承、多態。這也是面向對對象語言相對面向過程而言，最大的優勢和特點。面向對象使得程序更加利於維護，讓設計人員更加關注設計，要想真正的理解面向對象的特性，則必須要清楚和掌握這三大規律。

鏈式結構分析

對於鏈式結構而言，與線性結構有所差別的是，其邏輯結構不為連續的，而是采用一種前驅後繼的方式進行節點之間的關聯，使得上一個節點，可以訪問到下一個節點，從而形成一種鏈式的線性結構。鏈式結構的優點在於，其插入刪除的效率較高，因此叫常用於插入刪除較頻繁的情形。
對於鏈式結構，應該有的屬性為：

鏈表由節點構成，每一個節點包含一個數據鏈表為鏈式結構，在物理上不連續鏈式結構為隨機存儲結構，在堆區開辟空間，需要手動管理內存

開始鏈表的實現

鏈表節點的實現

/**
     * 鏈表節點類
     */
    template
    class ZLinkedListNode {
    public:
        /**
         * 默認構造函數，需要目的類型提供默認構造函數?
         */
        ZLinkedListNode(){_nextNode = nullptr;}
        /**
         * 構造函數，用於構造一個鏈表節點，並為其制定一個節點值
         * @param data 要賦予的節點的值
         */
        ZLinkedListNode(const T &data);
        /**
         * 構建指定前驅的鏈表節點
         * @param data 要指定節點的值
         * @param preNode 要指定的上一個節點
         */
        ZLinkedListNode(const T &data, ZLinkedListNode &preNode);
        /**
         * 獲取節點值
         * @return 返回該節點值的副本，為保證安全，應該相應的數據類型重載賦值和拷貝構造
         */
        const T data() const{return _data;}
        /**
         * 引用該節點的值
         * @return 返回節點值的引用
         */
        T &ref() {return _data;}

        /**
         * 獲取下一個節點
         * @return 返回下一個節點
         */
        ZLinkedListNode *nextNode(){return _nextNode;}

        /**
         * 下一個節點的引用
         * @return 返回下一個節點指針的引用
         */
        ZLinkedListNode *&nextNodeRef(){return _nextNode;}

        /**
         * 設置下一個節點
         * @param nextNode 要設置的下一個節點
         */
        void setNextNode(ZLinkedListNode *nextNode);
    protected:
        T _data;// 節點數據
        ZLinkedListNode *_nextNode; // 下一個節點
    };

    /*以下為Node的實現*/
    template
    ZLinkedListNode::ZLinkedListNode(const T &data) {
        _data = data;
        _nextNode = nullptr;
    }

    template
    ZLinkedListNode::ZLinkedListNode(const T &data, ZLinkedListNode &preNode) {
        _data = data;
        // 連接節點
        preNode._nextNode = this;
        _nextNode = nullptr;
    }

    template
    void ZLinkedListNode::setNextNode(ZLinkedListNode *nextNode) {
        _nextNode = nextNode;
    }

鏈表的實現

/**
     * 鏈表類
     */
    template
    class ZLinkedList : public Sequence {
    public:
        /**
         * 默認構造函數，為節省空間，不設置哨兵節點
         */
        ZLinkedList();

        /**
         * 根據指定值創建鏈表，該值為鏈表頭部
         * @param data 要指定的頭部值
         */
        ZLinkedList(const T& data);

        /**
         * 創建指定值的指定個數的鏈表
         * @param data 指定值
         * @param count 指定值的個數
         */
        ZLinkedList(const T& data, z_size count);

        /**
         * 插入到最後一個位置
         */
        virtual void push_back(const T& val);
        /**
         * 從指定位置中，移除元素，並返回該元素的副本，若為指針，請自行進行內存管理
         * @param pos 元素位置
         * @return 返回該元素值
         */
        virtual T pop(const rank pos);
        /**
         * 訪問指定位置的值
         * @param pos 元素所在的位置
         * @return 返回該位置的元素值
         */
        virtual const T &at(const rank pos) const;
        /**
         * 移除指定位置元素
         * @param pos 元素所在位置
         * @return 返回是否移除成功
         */
        virtual bool remove(const rank pos);

        /**
         * 獲取迭代器
         * @return 返回迭代器
         */
        virtual Iterator &iterator();
        /**
         * 重載訪問器
         * @param pos 元素位置
         * @return 返回元素引用
         */
        virtual T& operator[](const rank pos);

        /**
         * 判斷是否為空表
         */
        bool isEmpty() const;

        virtual ~ZLinkedList();

        z_size length() const{return _length;}

        //聲明友元關系
        friend class ZLinkedListIterator;

    protected:
        ZLinkedListNode *_list_head; // 鏈表頭結點
        ZLinkedListNode *_list_tail; // 鏈表尾節點，冗余數據，為了加快尾插法的效率
        z_size _length;                 // 長度
        Iterator *preIterator;       // 上一個迭代器，用於迭代器的釋放
    };
    /*
 鏈表的實現
 */
template
ZTemplate::ZLinkedList::ZLinkedList():Sequence() {
    _list_head = nullptr;
    _length = 0;
    _list_tail = nullptr;
    preIterator = nullptr;
}

template
ZTemplate::ZLinkedList::ZLinkedList(const T &data):Sequence() {
    _list_head = new ZTemplate::ZLinkedListNode(data);
    _length = 1;
    preIterator = nullptr;
    _list_tail = _list_head;
}

template
ZTemplate::ZLinkedList::ZLinkedList(const T &data, ZTemplate::z_size count):Sequence() {
    _list_head = new ZTemplate::ZLinkedListNode(data);
    _length = count;
    preIterator = nullptr;
    ZTemplate::ZLinkedListNode *curNode = _list_head; // 用於拼接節點
    for (int i = 0; i < count - 1; i++) {
        ZTemplate::ZLinkedListNode *newNode = new ZTemplate::ZLinkedListNode(data, *curNode); // 在構建時，直接追加至末尾
        curNode = newNode;
    }
    _list_tail = curNode;
}
template
void ZTemplate::ZLinkedList::push_back(const T &val) {
    // 創建節點，直接插入尾部
    ++_length;
    if (_list_head == nullptr) { // 頭為空
        _list_head = _list_tail = new ZLinkedListNode(val);
    }else {
        _list_tail = new ZTemplate::ZLinkedListNode(val, *_list_tail);
    }
}

template
T ZTemplate::ZLinkedList::pop(const rank pos) {
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->data();
}

template
const T& ZTemplate::ZLinkedList::at(const rank pos) const{
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->ref();
}

template
bool ZTemplate::ZLinkedList::remove(const rank pos) {
    if (pos >= _length) {
        return false;
    }
    --_length;
    // 頭結點刪除
    if (0 == pos) {
        ZTemplate::ZLinkedListNode *delNode = _list_head;
        _list_head = _list_head->nextNode();
        delete delNode;
        return true;
    }
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos - 1; i++) { // 遍歷至pos之前的一個節點
        nodePointer = nodePointer->nextNode();
    }
    ZTemplate::ZLinkedListNode *delNode = nodePointer->nextNode();// 待刪除的節點
    nodePointer->setNextNode(nodePointer->nextNode()->nextNode());
    delete delNode;
    return true;
}

template
ZTemplate::Iterator &ZTemplate::ZLinkedList::iterator() {
    if (nullptr != preIterator) {
        delete preIterator;
    }
    Iterator *_iterator = new ZTemplate::ZLinkedListIterator(*this);
    preIterator = _iterator;
    return *_iterator;
}

template
T & ZTemplate::ZLinkedList::operator[](const rank pos) {
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->ref();
}

template
bool ZTemplate::ZLinkedList::isEmpty() const {
    return _length <= 0;
}

template
ZTemplate::ZLinkedList::~ZLinkedList() {
    while (!isEmpty()) {
        remove(0);
    }
}

鏈表迭代器的實現

/**鏈表迭代器類*/
    template
    class ZLinkedListIterator : public Iterator{
    public:
        /**
         * 構造函數
         */
        ZLinkedListIterator(ZLinkedList &list);
        /**
         * 下一個元素
         * @return 返回下一個迭代器
         */
        virtual Iterator &next();

        /**
         * 獲取迭代器值
         * @return 返回值
         */
        virtual const T data() const;

        /**
         * 是否含有下一個元素
         * @return 返回是否有後續元素
         */
        virtual bool hasNext() const;

        /**
         * 重載++
         */
        virtual Iterator& operator++();
        virtual Iterator& operator++(int);
        virtual ~ZLinkedListIterator(){_list = nullptr;pointTo = nullptr;}
    protected:
        ZLinkedList *_list;      // 迭代器綁定的表
        ZLinkedListNode *pointTo;               // 當前游標
    };

    /* 迭代器的實現部分
     */
    template
    ZLinkedListIterator::ZLinkedListIterator(ZLinkedList &list) {
        _list = &list;
        pointTo = list._list_head;
    }

    template
    Iterator& ZLinkedListIterator::next() {
        pointTo = pointTo->nextNode();
        return *this;
    }

    template
    const T ZLinkedListIterator::data() const{
        return pointTo->data();
    }

    template
    bool ZLinkedListIterator::hasNext() const{
        return nullptr != pointTo;
    }

    template
    Iterator & ZLinkedListIterator::operator++() {
        next();
        return *this;
    }

    template
    Iterator & ZLinkedListIterator::operator++(int i) {
        Iterator & tempIt = *(new ZLinkedListIterator(*this));
        next();
        return tempIt;
    }

以上所涉及的類在前一篇文章中進行查看：C++封裝向量-線性表

完整代碼為：

//
//  ZLinkedList.hpp
//  Array
//
//  Created by 鄒智鵬 on 16/7/3.
//  Copyright ? 2016年 Frank. All rights reserved.
//

#ifndef ZLinkedList_hpp
#define ZLinkedList_hpp

#include 
#include 
#include "Sequence.hpp"
#include "Iterator.hpp"

namespace ZTemplate {
    /**
     * 鏈表節點類
     */
    template
    class ZLinkedListNode {
    public:
        /**
         * 默認構造函數，需要目的類型提供默認構造函數?
         */
        ZLinkedListNode(){_nextNode = nullptr;}
        /**
         * 構造函數，用於構造一個鏈表節點，並為其制定一個節點值
         * @param data 要賦予的節點的值
         */
        ZLinkedListNode(const T &data);
        /**
         * 構建指定前驅的鏈表節點
         * @param data 要指定節點的值
         * @param preNode 要指定的上一個節點
         */
        ZLinkedListNode(const T &data, ZLinkedListNode &preNode);
        /**
         * 獲取節點值
         * @return 返回該節點值的副本，為保證安全，應該相應的數據類型重載賦值和拷貝構造
         */
        const T data() const{return _data;}
        /**
         * 引用該節點的值
         * @return 返回節點值的引用
         */
        T &ref() {return _data;}

        /**
         * 獲取下一個節點
         * @return 返回下一個節點
         */
        ZLinkedListNode *nextNode(){return _nextNode;}

        /**
         * 下一個節點的引用
         * @return 返回下一個節點指針的引用
         */
        ZLinkedListNode *&nextNodeRef(){return _nextNode;}

        /**
         * 設置下一個節點
         * @param nextNode 要設置的下一個節點
         */
        void setNextNode(ZLinkedListNode *nextNode);
    protected:
        T _data;// 節點數據
        ZLinkedListNode *_nextNode; // 下一個節點
    };

    /*以下為Node的實現*/
    template
    ZLinkedListNode::ZLinkedListNode(const T &data) {
        _data = data;
        _nextNode = nullptr;
    }

    template
    ZLinkedListNode::ZLinkedListNode(const T &data, ZLinkedListNode &preNode) {
        _data = data;
        // 連接節點
        preNode._nextNode = this;
        _nextNode = nullptr;
    }

    template
    void ZLinkedListNode::setNextNode(ZLinkedListNode *nextNode) {
        _nextNode = nextNode;
    }

    template
    class ZLinkedListIterator;

    /**
     * 鏈表類
     */
    template
    class ZLinkedList : public Sequence {
    public:
        /**
         * 默認構造函數，為節省空間，不設置哨兵節點
         */
        ZLinkedList();

        /**
         * 根據指定值創建鏈表，該值為鏈表頭部
         * @param data 要指定的頭部值
         */
        ZLinkedList(const T& data);

        /**
         * 創建指定值的指定個數的鏈表
         * @param data 指定值
         * @param count 指定值的個數
         */
        ZLinkedList(const T& data, z_size count);

        /**
         * 插入到最後一個位置
         */
        virtual void push_back(const T& val);
        /**
         * 從指定位置中，移除元素，並返回該元素的副本，若為指針，請自行進行內存管理
         * @param pos 元素位置
         * @return 返回該元素值
         */
        virtual T pop(const rank pos);
        /**
         * 訪問指定位置的值
         * @param pos 元素所在的位置
         * @return 返回該位置的元素值
         */
        virtual const T &at(const rank pos) const;
        /**
         * 移除指定位置元素
         * @param pos 元素所在位置
         * @return 返回是否移除成功
         */
        virtual bool remove(const rank pos);

        /**
         * 獲取迭代器
         * @return 返回迭代器
         */
        virtual Iterator &iterator();
        /**
         * 重載訪問器
         * @param pos 元素位置
         * @return 返回元素引用
         */
        virtual T& operator[](const rank pos);

        /**
         * 判斷是否為空表
         */
        bool isEmpty() const;

        virtual ~ZLinkedList();

        z_size length() const{return _length;}

        //聲明友元關系
        friend class ZLinkedListIterator;

    protected:
        ZLinkedListNode *_list_head; // 鏈表頭結點
        ZLinkedListNode *_list_tail; // 鏈表尾節點，冗余數據，為了加快尾插法的效率
        z_size _length;                 // 長度
        Iterator *preIterator;       // 上一個迭代器，用於迭代器的釋放
    };

    /**鏈表迭代器類*/
    template
    class ZLinkedListIterator : public Iterator{
    public:
        /**
         * 構造函數
         */
        ZLinkedListIterator(ZLinkedList &list);
        /**
         * 下一個元素
         * @return 返回下一個迭代器
         */
        virtual Iterator &next();

        /**
         * 獲取迭代器值
         * @return 返回值
         */
        virtual const T data() const;

        /**
         * 是否含有下一個元素
         * @return 返回是否有後續元素
         */
        virtual bool hasNext() const;

        /**
         * 重載++
         */
        virtual Iterator& operator++();
        virtual Iterator& operator++(int);
        virtual ~ZLinkedListIterator(){_list = nullptr;pointTo = nullptr;}
    protected:
        ZLinkedList *_list;      // 迭代器綁定的表
        ZLinkedListNode *pointTo;               // 當前游標
    };

    /* 迭代器的實現部分
     */
    template
    ZLinkedListIterator::ZLinkedListIterator(ZLinkedList &list) {
        _list = &list;
        pointTo = list._list_head;
    }

    template
    Iterator& ZLinkedListIterator::next() {
        pointTo = pointTo->nextNode();
        return *this;
    }

    template
    const T ZLinkedListIterator::data() const{
        return pointTo->data();
    }

    template
    bool ZLinkedListIterator::hasNext() const{
        return nullptr != pointTo;
    }

    template
    Iterator & ZLinkedListIterator::operator++() {
        next();
        return *this;
    }

    template
    Iterator & ZLinkedListIterator::operator++(int i) {
        Iterator & tempIt = *(new ZLinkedListIterator(*this));
        next();
        return tempIt;
    }
}

/*
 鏈表的實現
 */
template
ZTemplate::ZLinkedList::ZLinkedList():Sequence() {
    _list_head = nullptr;
    _length = 0;
    _list_tail = nullptr;
    preIterator = nullptr;
}

template
ZTemplate::ZLinkedList::ZLinkedList(const T &data):Sequence() {
    _list_head = new ZTemplate::ZLinkedListNode(data);
    _length = 1;
    preIterator = nullptr;
    _list_tail = _list_head;
}

template
ZTemplate::ZLinkedList::ZLinkedList(const T &data, ZTemplate::z_size count):Sequence() {
    _list_head = new ZTemplate::ZLinkedListNode(data);
    _length = count;
    preIterator = nullptr;
    ZTemplate::ZLinkedListNode *curNode = _list_head; // 用於拼接節點
    for (int i = 0; i < count - 1; i++) {
        ZTemplate::ZLinkedListNode *newNode = new ZTemplate::ZLinkedListNode(data, *curNode); // 在構建時，直接追加至末尾
        curNode = newNode;
    }
    _list_tail = curNode;
}
template
void ZTemplate::ZLinkedList::push_back(const T &val) {
    // 創建節點，直接插入尾部
    ++_length;
    if (_list_head == nullptr) { // 頭為空
        _list_head = _list_tail = new ZLinkedListNode(val);
    }else {
        _list_tail = new ZTemplate::ZLinkedListNode(val, *_list_tail);
    }
}

template
T ZTemplate::ZLinkedList::pop(const rank pos) {
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->data();
}

template
const T& ZTemplate::ZLinkedList::at(const rank pos) const{
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->ref();
}

template
bool ZTemplate::ZLinkedList::remove(const rank pos) {
    if (pos >= _length) {
        return false;
    }
    --_length;
    // 頭結點刪除
    if (0 == pos) {
        ZTemplate::ZLinkedListNode *delNode = _list_head;
        _list_head = _list_head->nextNode();
        delete delNode;
        return true;
    }
    // 節點游標
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos - 1; i++) { // 遍歷至pos之前的一個節點
        nodePointer = nodePointer->nextNode();
    }
    ZTemplate::ZLinkedListNode *delNode = nodePointer->nextNode();// 待刪除的節點
    nodePointer->setNextNode(nodePointer->nextNode()->nextNode());
    delete delNode;
    return true;
}

template
ZTemplate::Iterator &ZTemplate::ZLinkedList::iterator() {
    if (nullptr != preIterator) {
        delete preIterator;
    }
    Iterator *_iterator = new ZTemplate::ZLinkedListIterator(*this);
    preIterator = _iterator;
    return *_iterator;
}

template
T & ZTemplate::ZLinkedList::operator[](const rank pos) {
    ZTemplate::ZLinkedListNode *nodePointer = _list_head;
    for (int i = 0; i < pos; i++) {
        nodePointer = nodePointer->nextNode();
    }
    return nodePointer->ref();
}

template
bool ZTemplate::ZLinkedList::isEmpty() const {
    return _length <= 0;
}

template
ZTemplate::ZLinkedList::~ZLinkedList() {
    while (!isEmpty()) {
        remove(0);
    }
}

#endif /* ZLinkedList_hpp */

對封裝結果進行測試

簡單類型測試

//
//  main.cpp
//  Array
//
//  Created by 鄒智鵬 on 16/7/3.
//  Copyright ? 2016年 Frank. All rights reserved.
//

#include 
#include "Array.hpp"
#include "Iterator.hpp"
#include "ZLinkedList.hpp"
using namespace ZTemplate;


int main(int argc, const char * argv[]) {

    ZLinkedList list;
    std::cout << "start: " << list.length();

    list.push_back(2);
    list.push_back(3);
    list.push_back(5);

    Iterator *iterator = &list.iterator();
    std::cout << "--------------------" << std::endl;
    while (iterator->hasNext()) {
        std::cout << iterator->data() << std::endl;
        (*iterator)++;
    }

    list.remove(0);
    // 注意對於迭代器而言，只要remove後，迭代器失效，需要重置

    std::cout << "--------------------" << std::endl;
    iterator = &list.iterator();
    while (iterator->hasNext()) {
        std::cout << iterator->data() << std::endl;
        (*iterator)++;
    }
    std::cout << "--------------------" << std::endl;
    return 0;
}

結果：
這裡寫圖片描述

復雜類型測試

//
//  main.cpp
//  Array
//
//  Created by 鄒智鵬 on 16/7/3.
//  Copyright ? 2016年 Frank. All rights reserved.
//

#include 
#include "Array.hpp"
#include "Iterator.hpp"
#include "ZLinkedList.hpp"
using namespace ZTemplate;

class Student {
public:
    Student(){name = "", age = 0;}
    Student(std::string n, int a){name = n, age = a;}
    Student(const Student &stu){name = stu.name, age = stu.age;}
    void display() const{std::cout << "name:" << name << ",age:" << age << std::endl;}
private:
    std::string name;
    int age;
};

int main(int argc, const char * argv[]) {

    ZLinkedList list;
    std::cout << "start: " << list.length() << std::endl;

    list.push_back(Student("zz", 19));
    list.push_back(Student("ee", 20));
    list.push_back(Student("ff", 21));

    Iterator *iterator = &list.iterator();
    std::cout << "--------------------" << std::endl;
    while (iterator->hasNext()) {
        iterator->data().display();
        (*iterator)++;
    }

    list.remove(0);
    // 注意對於迭代器而言，只要remove後，迭代器失效，需要重置

    std::cout << "--------------------" << std::endl;
    iterator = &list.iterator();
    while (iterator->hasNext()) {
        iterator->data().display();
        (*iterator)++;
    }
    std::cout << "--------------------" << std::endl;
    return 0;
}

測試結果：
這裡寫圖片描述