在链式描述中，线性表的元素在内存中的存储位置是随机的，每个元素都有一个明确的指针或链指向下一个元素的位置
chain类
在此使用单向链表实现了线性表，其中最后一个节点的指针域为NULL，即它用单向链接的一组节点实现线性表
template<class T>
class chain : public linearList<T>{
public:
chain(int initialCapacity = 10);
chain(const chain<T> &);
~chain();
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(std::ostream &out) const;
private:
void checkIndex(int theIndex) const;
chainNode<T> *firstNode;
int listSize;
};
构造函数
在构造函数中创建一个空链表，即令第一个节点指针firstNode的值为NULL
template<class T>
chain<T>::chain(int initialCapacity) {
if (initialCapacity < 1) {
ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}
firstNode = NULL;
listSize = 0;
}
复制构造函数要复制链表theList的每一个节点:
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);
sourceNode = sourceNode->next;
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>
chain<T>::~chain() {
while (firstNode != NULL) {
chainNode<T> *nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
基本方法
get方法在链表中，寻找索引为theIndex的元素，必须从第一个节点开始，跟踪链域next直至找到所需的元素节点指针
template<class T>
T& chain<T>::get(int theIndex) const {
checkIndex(theIndex);
chainNode<T> *currentNode = firstNode;
for (int i = 0; i<theIndex; i++)
currentNode = currentNode->next;
return currentNode->element;
}
indexOf方法搜索链表，寻找元素
template<class T>
int chain<T>::indexOf(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;
}
return index;
}
erase方法删除索引为theIndex的元素，要考虑三种情况:
- listSize < 0 && listSize >= listSize，即listSize在无效范围
删除非空表的第0个元素节点
删除其他元素节点
template<class T>
void chain<T>::erase(int theIndex) {
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;
}
insert方法插入和删除的过程相似，在链表中索引为theIndex的位置上插入一个新元素，要首先找到索引为theIndex-1的元素节点，然后在该节点之后插入新元素节点
template<class T>
void chain<T>::insert(int theIndex, const T &theElement) {
if (theIndex < 0 || theIndex > listSize) {
ostringstream s;
s << "index = " << theIndex << " size = " << listSize;
throw illegalIndex(s.str());
}
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++;
}
output方法用于输出链表
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;
}
迭代器类
对于单链表，定义了一个向前迭代器
template<class T>
class iterator {
public:
iterator(chainNode<T>* theNode = NULL) { node = theNode; }
T& operator*() const { return node->element; }
T* operator->() const { return &node->element; }
iterator& operator++() { node = node->next; return *this; }
iterator& operator++(int) { iterator old = *this; node = node->next; return old; }
bool operator!=(const iterator right) const { return node != right.node; }
bool operator==(const iterator right) const { return node == right.node; }
protected:
chainNode<T> *node;
};
