数据结构-C++实现(二):单向链表

数据结构-C++实现(二):单向链表

和数组不同,链表的数据结构内部多了一个指针指针下一个位置,使得在链表中插入删除特定位置的元素效率很高,代码实现依旧分为三个部分,抽象类LinearList.h,模板类chain.h以及main函数源文件。

废话不多说,我们看代码,这次LinearList.h抽象类里面多了两个成员函数一个是push_back(),一个是clear():

//
// Created by djf on 2016/12/18 0018.
//

#ifndef INC_01_ARRAYLIST_LINEARLIST_H
#define INC_01_ARRAYLIST_LINEARLIST_H

#include 
template 
class LinearList {
public:
    virtual ~LinearList() {};
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual T& get(int index) const = 0;
    virtual int indexof(const T& theElement) const = 0;//first pos
    virtual void erase(int index) = 0;
    virtual void insert(int index, const T& theElement) = 0;
    virtual void output(std::ostream& out) const = 0;
    //extend
    virtual void clear() = 0;
    virtual void push_back(const T& theElement)  = 0;
};


#endif //INC_01_ARRAYLIST_LINEARLIST_H

``
然后是chain.h,单向链表的模板类:
```cpp
//
// Created by djf on 2016/12/20 0020.
//

#ifndef INC_02_CHAIN_CHAIN_H
#define INC_02_CHAIN_CHAIN_H

#include "LinearList.h"
using namespace std;
template 
struct chainNode{
    //data
    T element;
    chainNode *next;
    //method
    chainNode() {}
    chainNode(const T& e) { this->element=e;}
    chainNode(const T& e, chainNode* n) { this->element=e;this->next=n;}
};

template 
class chain: public LinearList {
public:
    //one direction iterator
    class iterator{
    public:
        // typedefs required by C++ for a forward iterator
        typedef forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
        typedef T* pointer;
        typedef T& reference;
        //construct
        iterator(chainNode* theNode = nullptr) { node = theNode;}
        //operator
        T& operator*() const { return node->element;}
        T* operator&() const { return &node->element;}
        iterator& operator++() { node = node->next;return *this;}
        iterator operator++(int) { iterator old = *this; node = node->next; return old;}
        bool operator==(const iterator rhl) const { return node == rhl.node;}
        bool operator!=(const iterator rhl) const { return node != rhl.node;}
        //other

    protected:
        chainNode* node;
    };
public:
    //consturct copy destory
    chain(int initCapacity=10);
    chain(const chain&);
    ~chain();
    //ADT method from LinearList.h
    bool empty() const override { return listSize==0;};
    int size() const override { return listSize;}
    T& get(int index) const override;
    int indexof(const T&) const override;
    void erase(int index) override;
    void insert(int index,const T& theElement) override;
    void output(ostream& out) const override;
    void push_back(const T& theElement) override ;
    void clear() override ;
    //other
    void removeRange(int fromIndex,int toIndex);
    int lastIndexOf(const T& theElement);
    T& operator[](int index) const;
    void reverse();
protected:
    void checkIndex(int index) const;
    chainNode* headNode;
    int listSize;

};

template 
void chain::removeRange(int fromIndex, int toIndex)
{
    checkIndex(fromIndex);checkIndex(toIndex);
    if(toIndex* p = headNode;
    if(fromIndex!=0)
    {
        chainNode* q;
        for(int i = 0;inext;
            else
            {
                q = p->next;
                p->next = q->next;
                delete q;
            }
        }
    } else
    {
        for(int i = 0;i<=toIndex;++i)
        {
            headNode = headNode->next;
            delete p;
            p = headNode;
        }
    }
}

template 
chain::chain(int initCapacity)
{
    //chain中无capacity,这么写为了和LinearList兼容
    if(initCapacity<1)
        cerr << "----!initSize must be >=1 !----";
    listSize = 0;
    headNode = nullptr;
}

template 
chain::chain(const chain & theList)
{
    listSize = theList.listSize;
    if(listSize==0)
    {
        headNode = nullptr;
        return;
    }
    chainNode* sourceNode = theList.headNode;
    headNode = new chainNode(sourceNode->element);
    sourceNode = sourceNode->next;
    chainNode* targetNode = headNode;
    while(sourceNode!= nullptr)
    {
        targetNode->next = new chainNode(sourceNode->element);
        sourceNode = sourceNode->next;
        targetNode = targetNode->next;
    }
    targetNode->next = nullptr;
}

template 
chain::~chain()
{
    wsnippet_file_0hile(headNode!= nullptr)
    {
        chainNode* nextNode = headNode->next;
        delete headNode;
        headNode = nextNode;
    }
}

template 
T &chain::get(int index) const
{
    checkIndex(index);
    chainNode* currNode = headNode;
    for(int i=0;inext;
    return currNode->element;
}

template 
void chain::checkIndex(int index) const
{
    if(index<0 || index>=listSize)
    {
        cerr << "----! index outrange !----" << endl;
        return;
    }
}

template 
int chain::indexof(const T & theElement) const
{
    chainNode* currNode = headNode;
    for(int i = 0;ielement==theElement)
            return i;
        currNode = currNode->next;
    }
    return -1;
}

template 
void chain::erase(int index)
{
    checkIndex(index);
    chainNode* deleteNode;
    if(index==0)
    {
        deleteNode = headNode;
        headNode = headNode->next;
    } else
    {
        chainNode *p = headNode;
        for(int i=0;inext;
        deleteNode = p->next;
        p->next = p->next->next;
    }
    --listSize;
    delete deleteNode;
}

template 
void chain::insert(int index, const T &theElement)
{
    if(index<0 || index>listSize)
    {
        cerr << "---! insert index error !----" << endl;
        return;
    }
    if(index ==0)
    {
        headNode = new chainNode(theElement,headNode);
    } else
    {
        chainNode *p = headNode;
        for (int i = 0; i < index - 1; ++i)
            p = p->next;
        p->next = new chainNode(theElement, p->next);
    }
    listSize++;
}

template 
void chain::output(ostream &out) const
{
    for(chainNode* p = headNode;p != nullptr;p=p->next)
        out << p->element << " ";

}

template 
void chain::push_back(const T &theElement)
{
    chainNode* currNode = headNode;
    for(int i=0;inext;
    currNode->next = new chainNode(theElement, nullptr);
    ++listSize;
}

template 
void chain::clear()
{
    chainNode* p;
    while(headNode!= nullptr)
    {
        p = headNode->next;
        delete headNode;
        headNode = p;
    }
    listSize = 0;
}

template 
int chain::lastIndexOf(const T& theElement)
{
    int pos = -1;int i = 0;
    chainNode* p = headNode;
    while (p != nullptr)
    {
        if (p->element == theElement)
            pos = i;
        else
        {
            ++i;
            p = p->next;
        }
    }
}

template 
T& chain::operator[](int index) const
{
    checkIndex(index);
    chainNode* currNode = headNode;
    for(int i = 0;inext;
    return currNode->element;
}

template 
void chain::reverse()
{
    if(listSize==0 || listSize==1)
        return;
    else if(listSize == 2)
    {
        chainNode* p = headNode;
        headNode = headNode->next;
        headNode->next = p;
        p->next = nullptr;
    }
    else
    {
        chainNode* p = headNode;
        chainNode* q = headNode->next;
        chainNode* r = headNode->next->next;
        headNode->next = nullptr;
        while(r->next != nullptr)
        {
            q->next = p;
            p = q;
            q = r;
            r = r->next;
        }
        q->next = p;
        r->next = q;
        headNode = r;
    }

}

template 
ostream& operator<<(ostream& out, const chain &a)
{
    a.output(out);
    return out;
}


#endif //INC_02_CHAIN_CHAIN_H

随便写的测试:

#include <iostream>
#include "chain.h"
int main()
{
    chain<int> ic;
    ic.insert(0,1);ic.insert(0,2);ic.push_back(3);ic.push_back(4);
    chain<int> ic1(ic);ic1.reverse();
    cout << ic1 << endl;
    return 0;
}

我发现写这个还是很锻炼人的,一个完善的数据结构轻轻松松几百行代码,每天一发,感觉很酸爽,C++简直写上瘾。
不废话了,我们回归头来看看链表的头文件里都定义了啥:
- chainNode类定义了节点类,包含数据成员以及指向下一个节点的指针。包含构造、拷贝以及析构函数。
- chan类继承自LinearList抽象类,包含节点类的成员变量,以及一个嵌套类iterator。
成员函数分为几个部分,首先是构造、拷贝以及析构函数,值得注意的是在构造函数中有一个参数
initCapacity,实际是无作用的,仅仅为了和之前的ArrayList一致。
- 然后是继承自抽象类的方法,和ArrayList中的区别不大。
- 最后是我做的几个习题,void removeRange(int fromIndex,int toIndex)的作用是将参数限定范围内的节点删除的操作。int lastIndexOf(const T& theElement)是返回与函数参数相等的最后一个位置的索引。T& operator[](int index) const 是对[]运算符进行重载,返回指定索引的节点的数据的引用。void reverse()是将整个链表进行反转的操作,要求不开辟多余的空间。

Comments are closed.