数据结构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()函数使得数组大小等于指定大小。
– 最后是几个运算符的重载，应该能看懂。另外，还有一个输出流的运算符的重载，定义在类外。