数据结构-C++实现(一):数组链表

数据结构-C++实现(一):数组链表

数据结构C++实现第一发,主要有几部分构成,分别是一个抽象类LinearList.h、数组链表的头文件ArrayList.h以及main.cpp源文件。
LinearList.h文件具体信息如下:

#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;
};

ArrayList.h文件如下:

#ifndef INC_01_ARRAYLIST_ARRAYLIST_H
#define INC_01_ARRAYLIST_ARRAYLIST_H

#include "LinearList.h"
#include
#include
using namespace std;

template  void resizeCapacity(T*& a,int oldCapacity, int newCapacity);

template
class ArrayList :public LinearList {
public:
    //iterator
    class iterator{
    public:
        //
        typedef bidirectional_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
        typedef T* pointer;
        typedef T& reference;
        //construct
        iterator(T* thepos=0) { pos = thepos;}
        //operator
        T& operator*() const { return *pos;}
        T* operator->() const { return &*pos;}
        iterator& operator++()
            { ++pos; return *this;}
        iterator& operator++(int)
            { iterator old = *this; ++pos; return old;}
        iterator& operator--()
            { --pos; return *this;}
        iterator& operator--(int)
            { iterator old = *this; --pos; return old;}
        bool operator!=(const iterator rhl) const
            { return pos != rhl.pos;}
        bool operator==(const iterator rhl) const
            { return pos == rhl.pos;}
    protected:
        T* pos;
    };
    iterator begin(){ return iterator(element);}
    iterator end(){ return iterator(element+listsize);}
public:
    //construct copy destroy
    //ArrayList(int initCapacity = 10);
    ArrayList(int initCapacity = 10, int size = 0);
    ArrayList(const ArrayList&);
    ~ArrayList() { delete [] element;};
    //ADT methods
    bool empty() const override { return listsize==0;}
    int size() const override { return listsize;}
    T& get(int index) const override;
    int indexof(const T& theElement) const override ;
    void erase(int index) override ;
    void insert(int index, const T& theElement) override ;
    void output(ostream& out) const override ;
    //other
    int capacity() const { return arrayCapacity;}
    void set(int index, T var);
    void trimToSize();
    void setSize(int setSize);
    T& operator[](int);
    bool const operator==(const ArrayList &);
    bool const operator!=(const ArrayList &);
    bool const operator<(const ArrayList &);

protected:
    void checkIndex(int index) const;
    T* element;
    int arrayCapacity;
    int listsize;
    int addsize;
};
template
ostream& operator<<(ostream& out,ArrayList& al);


template
ArrayList::ArrayList(int initCapacity,int size)
{
    if (initCapacity < 0 || size<0)
    {
        std::cerr << "----!Initdata error!----" << std::endl;
    }
    arrayCapacity = initCapacity;
    listsize = 1;
    element = new T[arrayCapacity];
    addsize = size;
}

template
ArrayList::ArrayList(const ArrayList &rhl)
{
    arrayCapacity = rhl.arrayCapacity;
    listsize = rhl.listsize;
    delete [] element;
    element = new T[arrayCapacity];
    copy(rhl.element,rhl.element+listsize,element);
}

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

template
T &ArrayList::get(int index) const
{
    checkIndex(index);
    return element[index];
}

template
int ArrayList::indexof(const T &theElement) const
{
    int pos = find(element,element+listsize,theElement)-element;
    if (pos==listsize)
        return -1;
    return pos;
}

template
void ArrayList::erase(int index)
{
    checkIndex(index);
    copy(element+index+1,element+listsize,element+index);
    element[--listsize].~T();
    if(arrayCapacity>4*listsize)
    {
        for(int i = 4*listsize;i
void ArrayList::insert(int index, const T &theElement)
{
    ++listsize;
    checkIndex(index);
    if(listsize>=arrayCapacity)
    {
        if(addsize==0)
        {
            resizeCapacity(element, arrayCapacity, arrayCapacity * 2);
            arrayCapacity *= 2;
        }
        else
        {
            resizeCapacity(element, arrayCapacity, arrayCapacity + addsize);
            arrayCapacity += addsize;
        }
    }
    copy(element+index,element+listsize-1,element+index+1);
    element[index] = theElement;
}

template
void ArrayList::output(ostream &out) const
{
    copy(element,element+listsize,ostream_iterator(out," "));
}

template
void ArrayList::set(int index, T var)
{
    checkIndex(index);
    element[index] = var;
}

template
void ArrayList::trimToSize()
{
    int edge = max(1,listsize);
    for(int i = edge+1;i
void ArrayList::setSize(int setSize)
{
    if(setSize= listsize !----";
    if(setSize<=arrayCapacity)
    {
       for(int i = setSize+1;i
T &ArrayList::operator[](int index)
{
    checkIndex(index);
    return element[index];
}
template
bool const ArrayList::operator==(const ArrayList &rhl)
{
    if(listsize!=rhl.listsize)
        return 0;
    else
    {
        for(int i = 0;i
bool const ArrayList::operator!=(const ArrayList &rhl)
{
    return !(*this==rhl);
}
template
bool const ArrayList::operator<(const ArrayList &rhl)
{
    int index = min(listsize,rhl.listsize);
    for(int i = 0;i=rhl.element[i])
            return 0;
    }
    if(listsize
ostream &operator<<(ostream &out, ArrayList &al)
{
    al.output(out);
    return out;
}
template
void resizeCapacity(T*& a,int oldCapacity, int newCapacity)
{
    if(newCapacity<0)
    {
        cerr << "----!newCapacity must be>=0!----";
    }
    T* tmp = new T[newCapacity];
    int num = min(oldCapacity,newCapacity);
    copy(a,a+num,tmp);
    delete [] a;
    a = tmp;
}
#endif //INC_01_ARRAYLIST_ARRAYLIST_H

简单的测试如下:

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

template <typename T>
void resizeLength2D(T**& a,int oldRow,int oldCol,int newRow,int newCol)
{
    T** tmp = new T*[newRow];
    int r = min(oldRow,newRow);
    int c = min(oldCol,newCol);
    for(int i = 0;i<newRow;i++)
        tmp[i] = new T[newCol];
    for(int i = 0;i<r;i++)
    {
        copy(a[i],a[i]+c,tmp[i]);
    }
    for(int i = 0;i<oldRow;i++)
        delete [] a[i];
    delete [] a;
    a = tmp;
}

int main()
{
    ArrayList<int> ia(5);
    ia.insert(0,1);ia.insert(0,2);ia.insert(0,3);ia.set(3,0);
    std::cout << ia << std::endl;
    for(auto i = ia.begin();i!=ia.end();++i)
        std::cout << *i << " ";
    ArrayList<int> ib(ia);
    cout << (ia!=ib) << endl;
    return 0;
}

这里我对ArrayList类里的函数做一些说明;
- element代表存储元素,arrayCapacity表示容量大小,listsize表示数组实际大小,capacity是要比listsize大的,相当于留有一些裕量,这一点和stl的vector类似。addsize表示listsize达到一定大小后,单次对capacity扩容的大小。checkIndex()函数后续用于检测索引值是否有效。
- 然后是public部分,内嵌类iterator为数组链表定义了迭代器,begin()以及end()的设置与stl的容器相同。
- 构造函数ArrayList()中有两个参数,一个代表预先给capacity的大小,另一个设置的是单次扩容值,如果缺省,则默认每次扩容时将capacity翻倍。析构函数,清空element元素。
- 接下来时覆写抽象类成员函数的部分,empty()函数返回当前数组是否为空,为空返回true;size()函数返回当前的数组大小,这里的大小时listsize,不是容量。get()函数返回指定索引处的值;indexof()返回目标值的第一个索引,若目标不在数组中,返回-1;erase()擦除指定index的数据,相应更改数组大小与容量;insert()在指定索引处插入值;output()函数将数组元素依次输出;
- 接下来是非构造拷贝析构函数、同时也不是覆写的成员函数。capacity()函数返回容量值,set()设定指定索引处的值;trimToSize()函数将容量设置为与listsize大小一i样;setSize()函数使得数组大小等于指定大小。
- 最后是几个运算符的重载,应该能看懂。另外,还有一个输出流的运算符的重载,定义在类外。

Comments are closed.