C++配列構造を実現するリニアテーブル
8157 ワード
#include
#include//copy，copy_backward
#include //ostringstream
#include //
#include//
#include //ostream_iterator
using namespace::std;
// ,
/*template
void changeLength2D(T ** &a, unsigned oldRow,unsigned oldCol,unsigned newRow, unsigned newCol)
{
T **b = new T*[newRow];
for (unsigned i = 0; i != newRow; ++i)
b[i] = new T[newCol];
unsigned row, col;
row = min(oldRow, newRow);
col = min(oldCol, newCol);
for (unsigned i = 0; i != row; ++i)
{
copy(a[i], a[i]+col,b[i]);
}
for (unsigned i = 0; i != oldRow; ++i)
{
delete[] a[i];
}
delete[] a;
a = b;
}*/
//
/*class illegalParameterValue
{
public:
illegalParameterValue():
message("Illegal parameter value") { }
illegalParameterValue(char* theMessage)
{
message = theMessage;
}
void outputMessage() { cout << message << endl; }
private:
string message;
};*/// s.str() ， （ ）
class illegalParameterValue
{
public:
illegalParameterValue(string theMessage = "Illegal parameter value")
{
message = theMessage;
}
void outputMessage() { cout << message << endl; }
private:
string message;
};
class illegalIndex
{
public:
illegalIndex(string theMessage = "Illegal index") //
{
message = theMessage;
}
void outputMessage() { cout << message << endl; }
private:
string message;
};
// arayList ， ，
template
class arrayList//:public linearList
{
public:
// ， ，
arrayList(int initialCapacity = 10);
arrayList(unsigned theLengthChange = 0, int initialCapacity = 10);
~arrayList() { delete[] element; }
//ADT
void insert(int theIndex, const T& theElement);
void changeLength1D(T* &a, int oldLength, int newLength);
void output(ostream& out) const;
void trimToSize();
T operator[](const int i);
void push_back(const T& thelement);
void pop_back();
void clear();
int lastIndexof(const T& theElement);
void reverse();
void circularShift(int i);
private:
T* element;
int arrayLength;
int listsize;
unsigned LengthChange;
};
//
template
arrayList::arrayList(int initialCapacity)
{
if (initialCapacity < 1)
{
ostringstream s;
s << "Initial capacity=" << initialCapacity << "Must be >0";
throw illegalParameterValue(s.str());//s.str(() s string
}
arrayLength = initialCapacity;
element = new T[arrayLength];
listsize = 0;
LengthChange = 0; // private ， 0
}
//
template
arrayList::arrayList(unsigned theLengthChange,int initialCapacity)
{
if (initialCapacity < 1)
{
ostringstream s;
s << "Initial capacity=" << initialCapacity << "Must be >0";
throw illegalParameterValue(s.str());//s.str(() s string
}
arrayLength = initialCapacity;
element = new T[arrayLength];
listsize = 0;
LengthChange = theLengthChange;
}
//
template
void arrayList::insert(int theIndex, const T& theElement)
{
if (theIndex<0 || theIndex>listsize)
{
ostringstream s;
s <
void arrayList::changeLength1D(T* &a, int oldLength, int newLength)
{
if (newLength < 0)
throw illegalParameterValue("new lenght must be>=0");
T*temp = new T[newLength];
int number = min(oldLength, newLength);
copy(a, a + number, temp);
delete[] a;
a = temp;
}
//
template
void arrayList::output(ostream& cout) const
{
copy(element, element + listsize, ostream_iterator(cout, " "));
}
// max(size,1)
template
void arrayList::trimToSize()
{
int size = max(listsize, 1);
T *b = new T[size];
copy(element, element + size, b); // O(listSize);
delete[] element;
element = b;
}
// []
template
T arrayList::operator[](const int i)
{
if (i<0 || i>listsize)
{
ostringstream s;
s << "i=" << i;
throw illegalIndex(s.str());
}
return element[i];
}
// push_back,
template
void arrayList::push_back(const T& thelement)
{
element[listsize]= thelement; // O(1)
listsize++;
}
// pop_back,
template
void arrayList::pop_back()
{
element[--listsize].~T();// O(1)
}
// ，
template
void arrayList::clear()
{
for(int i=listsize-1;i>=0;i--) // O(listsize)
element[--listsize].~T();
}
// ， find( )，
template
int arrayList::lastIndexof(const T& theElement)
{
int i = listsize,j=0,theIndex=listsize; // （ 0）
do // ， while ，i=0 ， ，
{
i = theIndex;
theIndex = (int)(find(element + j, element + listsize, theElement) - element);// O(n)( )
j=theIndex+1;
} while (theIndex < listsize);
if (i==listsize)
return -1;
else return i;
}
// ， STL reverse
template
void arrayList::reverse()
{
T a;
for (int i = 0; i < listsize/2; i++) // listsize/2, O(listsize/2)
{
a = element[i];
element[i] = element[listsize - i - 1];
element[listsize-i-1] = a;
}
}
// （ ）
template
void arrayList::circularShift(int i)
{
T* b = new T[listsize];
while(i)
{
copy(element, element + listsize, b);
for (int j = 0; j < listsize-1; j++)
{
element[j] = b[j+1];
}
element[listsize - 1] = b[0];
i--;
}
delete[] b;
}
int main()
{
/*//
int row = 2, col = 3;
int temp[2][3]= { 1, 2, 3, 4, 5, 6 };
// a
int **a = new int*[row];
for (size_t i = 0; i != row; ++i)
{
a[i] = new int[col];
}
// temp
for (size_t i = 0; i != row; ++i)
for (size_t j = 0; j != col; ++j)
a[i][j] = temp[i][j];
changeLength2D(a, 2, 3, 3, 4);
// ，
for (size_t i = 0; i != 3; ++i)
for (size_t j = 3; j != 4; ++j)
a[i][j] = 0;
for (size_t i = 2; i != 3; ++i)
for (size_t j = 0; j != 4; ++j)
a[i][j] = 0;
//
for (size_t i = 0; i != 3; ++i)
{
for (size_t j = 0; j != 4; ++j)
{
cout << a[i][j] << ' ';
}
cout << '
';
}*/
//
//arrayListy(3);
/*arrayListy(6,3); // ，
y.insert(0, 2);
y.insert(1, 6);
y.insert(0, 1);
y.insert(2, 4);
y.insert(3, 5);
y.insert(2, 3);
y.output(cout);*/
//
/*arrayListy(10);
y.insert(0, 2);
y.insert(1, 6);
y.trimToSize();
//
try { y.insert(3, 0); }
catch (illegalIndex e)
{
cout << "Illegal index exception" << endl;
cout << "Insert index must be between 0 and list size" << endl;
e.outputMessage();
}*/
// []
/*arrayListy(3);
y.insert(0, 2);
y.insert(1, 6);
int s=y[1];
//
try { y[6]; }
catch (illegalIndex e)
{
cout << "Illegal index exception" << endl;
e.outputMessage();
}
cout <y(3);
y.push_back(2);
y.push_back(3);
// pop_back
y.pop_back();
//
y.clear();
y.output(cout);*/
// lastIndexOf 5
arrayListy(10);
y.push_back(0);
y.push_back(1);
y.push_back(2);
y.push_back(3);
y.push_back(4);
/*int i = y.lastIndexof(4);
cout << i << endl;*/
//
//y.reverse();
//
y.circularShift(2);
y.output(cout);
return 0;
}