線形テーブルのいくつかの簡単な操作(C++実装)
4091 ワード
#include
using namespace std;
template
class linearList{
public:
virtual ~linearList(){};
virtual bool empty() const = 0; //
virtual int size() const = 0; //
virtual T & get(int theindex) const = 0;// theindex
virtual int indexof(const T& theelement) const = 0;// theelement
virtual void erase(int theindex) = 0;// theindex
virtual void insert(int index, const T& theelement) = 0;// theelement index
virtual void output() const = 0;//
};
template
class arrayList : public linearList
{
public:
//
arrayList(int initial);
arrayList(const arrayList &);
~arrayList(){
delete [] element;
}
//ADT
bool empty() const {return listSize == 0;};
int size () const {return listSize;};//
T & get(int theindex) const;
int indexof(const T& theelement) const;
void erase(int theindex);
void insert(int theindex, const T& theelement);
void output() const;
int capacity()const{return arrayLength;}//
private:
void checkIndex(int theindex) const;///
T *element;//
int arrayLength; //
int listSize; //
};
/* */
template
arrayList :: arrayList(int initial)
{
if(initial < 1)
{
cout << "initial capacity = " << initial << "must be > 0" << endl;
}
arrayLength = initial;
element = new T[arrayLength];
listSize = 0;
}
/* */
template
arrayList :: arrayList(const arrayList& thlist)
{
arrayLength = thlist.arrayLength;
listSize = thlist.listSize;
element = new T[arrayLength];
copy(thlist.element, thlist.element+listSize, element);
}
/* */
template
void arrayList :: checkIndex(int theindex) const
{
if(theindex < 0 || theindex >=listSize)
{
cout << "index=" << theindex << "is not included
";
}
}
/* */
template
T& arrayList :: get(int theindex) const
{
//
checkIndex(theindex);
return element[theindex];
}
/* */
template
int arrayList :: indexof(const T& theelement) const
{
int theindex;
for(int i=0; i
void arrayList :: erase(int theindex)
{
checkIndex(theindex);
copy(element+theindex+1, element+listSize, element+theindex);//
element[--listSize].~T();
}
/* */
template
void arrayList :: output()const
{
for(int i=0; i
void changelength(T*& a, int oldlength, int newlength)
{
if(newlength<0)
{
cout << "the newlength can not < 0
";
}
T *temp = new T[newlength];
int number = min(oldlength, newlength);
copy(a, a+number, temp);
a = temp;
}
/* index */
template
void arrayList :: insert(int theindex, const T& theelement)
{
if(theindex < 0 || theindex > listSize )
{
cout << "teh theindex is not included
";
}
if(listSize == arrayLength)
{
changelength(element, arrayLength, 2*arrayLength);
arrayLength = arrayLength * 2;
}
copy_backward(element+theindex, element+listSize, element+listSize+1);
element[theindex] = theelement;
listSize++;
}
まとめ:
1.抽象データ型
抽象データ型
{
実例:(有限要素の集合)
操作:
リニアテーブルが空であるか否かを判断する(bool)
線形テーブルのサイズを返します
線形テーブルのインデックスがindexの数値を返します.
…………
};
2. テンプレートと派生関数の運用
抽象クラスの派生クラスは、ベースクラスを実現したすべての純粋な虚関数だけが具体的なクラスであり、そうでなければ抽象はインスタンス化されません.