如何在C++中建立一个顺序表

如何在C++中建立一个顺序表

#include <iostream>
using namespace std;
//ADT抽象数据类型
template <class T>
class linearList
{
public:
virtual ~linearList(){};
virtual bool empty()const = 0;
virtual int size()const = 0;
virtual T& get(int theIndex)const = 0;
virtual int indeOf(const T& theElement)const = 0;  
virtual void erase(int theIndex) = 0;
virtual void insert(int theIndex, const T& theElement) = 0;
virtual void output(ostream& out)const = 0;
};

template <class T>
struct chainNode
{
//数据成员
T element;
chainNode<T> *next;

//方法
chainNode(){}
chainNode(const T& element)
{
this->element = element;
}
chainNode(const T& element, chainNode<T>* next)
{
this->element = element;
this->next = next;
}
};

template <class T>
class chain :public linearList<T>
{
public:
//构造函数
chain(int initialCapacity = 10);
chain(const chain<T>&);
~chain();

//抽象数据类型ADT的方法
bool empty()const{ return listSize == 0; }
int size()const{ return listSize; }
T& get(int theIndex)const;
int indeOf(const T& theElement)const;
void erase(int theIndex);
void insert(int theIndex, const T& theElement);
void output(ostream& out)const;




protected:
//检查索引，无效抛出异常
void checkIndex(int theIndex)const;
chainNode<T>* firstNode;
int listSize;
};
template <class T>
chain<T>::chain(int initialCapacity = 10)
{
//if (initialCapacity < 1)
//{
// throw 1;
//}
firstNode = NULL;
listSize = 0;
}
template <class T >
chain<T>::chain(const chain<T>& theList)
{
listSize = theList.listSize;
if (listSize == 0)
{
firstNode = NULL;
return;
}
chainNode <T> sourceNode = theList.firstNode;
firstNode = new chainNode<T>(sourceNode->element);
chainNode<T>* targetNode = firstNode;
while (sourceNode != NULL)
{
targetNode->next = new chainNode<T>(sourceNode->element);
targetNode = targetNode->next;
sourceNode = sourceNode->next;
}
targetNode->next = NULL;
}
template <class T>
void chain<T>::checkIndex(int theIndex)const
{
if (theIndex < 0 || theIndex >= listSize)
{
throw 1;
}
}


template<class T>
chain<T>::~chain()
{
while (firstNode != NULL)
{
chainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
template <class T>
T& chain<T>::get(int theIndex)const
{
try
{
checkIndex(theIndex);
}
catch (int)
{
cout << "索引无效！！" << endl;
}
chainNode<T>* currentNode = firstNode;
for (int i = 0; i < theIndex; i++)
currentNode = currentNode->next;
return currentNode->element;
}
template <class T>
int chain<T>::indeOf(const T& theElement)const
{
chainNode<T>* currentNode = firstNode;
int index = 0;
while (currentNode != NULL&&currentNode->element != theElement)
{
currentNode = currentNode->next;
index++;
}
if (currentNode == NULL)
return -1;
else
return index;
}


template <class T>
void chain<T>::erase(int theIndex)
{
try
{
checkIndex(theIndex);
chainNode<T>*deleteNode;
if (theIndex == 0)
{
deleteNode = firstNode;
firstNode = firstNode->next;
}
else
{
chainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1; i++)
p = p->next;
deleteNode = p->next;
p->next=p->next->next;
}
listSize--;
delete deleteNode;
}
catch (int)
{
cout << "索引无效" << endl;
}

}


template <class T>
void chain<T>::insert(int theIndex, const T& theElement)
{
if (theIndex < 0 || theIndex>listSize)
cout << "索引不正确";
if (theIndex == 0)
firstNode = new chainNode<T>(theElement, firstNode);
else
{
chainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1; i++)
p = p->next;
p->next = new chainNode<T>(theElement, p->next);
}
listSize++;
}
template <class T>
void chain<T>::output(ostream& out)const
{
for (chainNode<T>* currentNode = firstNode; currentNode != NULL; currentNode = currentNode->next)
{
out << currentNode->element << " ";
}
}
template <class T>
ostream& operator<<(ostream& out, const chain<T>& x)
{
x.output(out);
return out;
}
//点击我头像有惊喜
int main()
{
chain<int> a(3);
a.insert(0, 1);
a.insert(1, 2);
a.insert(2, 3);
a.insert(3, 4);
a.insert(0, 5);
chain<char> b;
b.insert(0, 'A');
b.insert(1, 'B');
b.insert(2, 'C');
//专业解答.
cout << a<<endl;
cout << b << endl;
cout << a.get(0);
cout << a.get(1);
return 0;
}嗯大致就是这些内容,使用了很多C++的知识