/*
* 测试例,主函数位于这个文件中
* extendedChain.cpp
*/
#include<iostream>
#include<numeric>
#include"extendedchain.h"
using namespace std;
int main(void)
{
extendedChain<int> y;
y.insert(0,2);
y.insert(1,6);
y.insert(0,1);
y.insert(2,4);
y.insert(3,5);
y.insert(2,3);
cout<<"after insert some elements:"<<endl;
cout<<"size of y = "<<y.size()<<endl;
y.erase(4);
y.erase(0);
y.push_back(6);
cout << "List y should be 1 2 3 6" << endl;
cout << "Size of y = " << y.size() << endl;
cout << y << endl;
y.insert(3,4);
y.insert(0,0);
cout << "List y should be 0 1 2 3 4" << endl;
cout << "Size of y = " << y.size() << endl;
cout << y << endl;
y.clear();
y.push_back(1);
y.push_back(2);
y.push_back(3);
cout << "Appended 3 integers, list y should be 1 2 3" << endl;
cout << "Size of y = " << y.size() << endl;
cout << y << endl;
//迭代器这部分的测试是有问题的,代码总是提示未定义的错误,还未找到问题点。以后再找。
/******************************************************************/
// 测试 iterator
/*
cout << "Ouput using forward iterators pre and post ++" << endl;
for (extendedChain<int>::iterator i = y.begin();
i != y.end(); i++)
cout << *i << " ";
cout << endl;
for (extendedChain<int>::iterator i = y.begin();
i != y.end(); ++i)
{
cout << *i << " ";
*i += 1;
}
cout << endl;
cout << "Incremented by 1 list is " << y << endl;
// try out an STL algorithm
int sum = accumulate(y.begin(), y.end(), 0);
cout << "The sum of the elements is " << sum << endl;
*/
/*******************************************************************************/
return 0;
}
/*
* 扩展的抽象线性表的类,其中只是在原有线性表抽象类的基础上,添加了几个抽象函数
* extendedLinearList.h
*/
#ifndef EXTENDEDLINEARLIST_H
#define EXTENDEDLINEARLIST_H
#include<iostream>
#include"linearlist.h"
using namespace std;
template<class T>
class extendedLinearList : linearList<T>
{
public:
virtual ~extendedLinearList(){}
virtual void clear() = 0;//删除链表
virtual void push_back(const T& theELement) = 0;//在链表尾部插入新元素
};
#endif // EXTENDEDLINEARLIST_H
扩展后的链表添加了lastNode指针,是一个指向链表的尾节点的指针。 利用lastNode指针,可以在时间复杂度为O(1)的情况下在链表尾部插入新元素。 数据成员lastNode有时需要更改,因为在删除和插入元素的时候会改变尾节点,这时就要更新指向尾节点的指针lastNode。 以下的extendedChain要完成的工作有:
/*
* 扩展后的链表的具体类实现
* extendedChain.h
*/
#ifndef EXTENDEDCHAIN_H
#define EXTENDEDCHAIN_H
#include<iostream>
#include<sstream>
#include<string>
#include"extendedlinearlist.h"
#include"chainwithiterator.h"
#include"myexceptions.h"
using namespace std;
template<class T>
class extendedChain : public extendedLinearList<T>,public chain<T>
{
public:
extendedChain(int initialCapacity = 10):
chain<T>(initialCapacity){}
extendedChain(const extendedChain<T>& c):
chain<T>(c){}
/*
* 各个函数的实现和声明
*/
bool empty()const{return listSize == 0;}
int size() const{return listSize;}
T& get(int theIndex) const
{
return chain<T>::get(theIndex);
}
int indexOf(const T &theELement) const
{
return chain<T>::indexOf(theELement);
}
void erase(int theIndex);
void insert(int theIndex,const T& theElement);
//子类中新添加的函数,功能是删除链表
void clear()
{
while(firstNode != NULL)
{
chainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
listSize = 0;
}
//子类中新添加的元素,功能为在链表尾部插入新元素
void push_back(const T& theElement);
void output(ostream& out) const
{
chain<T>::output(out);
}
//清空链表
void zero()
{
firstNode = NULL;
listSize = 0;
}
//迭代器类的定义
class iterator
{
public:
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//构造函数
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;
};
//迭代器
iterator bebin(){return iterator(firstNode);}
iterator end(){return iterator(NULL);}
protected:
chainNode<T>* lastNode = NULL;
chainNode<T>* firstNode = NULL;
void checkIndex(int theIndex) const;
int listSize = 0;
};
template<class T>
void extendedChain<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;
if(deleteNode == lastNode)
lastNode = p;
}
listSize--;
delete deleteNode;
}
template<class T>
void extendedChain<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);
if(listSize == 0)
lastNode = 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);
if(listSize == theIndex)
lastNode = p->next;
}
listSize++;
}
template<class T>
void extendedChain<T>::push_back(const T& theElement)
{
chainNode<T>* newNode = new chainNode<T>(theElement,NULL);
if(firstNode == NULL)
firstNode = lastNode = newNode;
else
{
lastNode->next = newNode;
lastNode = newNode;
}
listSize++;
}
template<class T>
void extendedChain<T>::checkIndex(int theIndex) const
{
if(theIndex < 0 || theIndex >= listSize)
{
ostringstream s;
s <<"index = "<<theIndex<<" size = "<<listSize;
throw illegalIndex(s.str());
}
}
#endif // EXTENDEDCHAIN_H
chainNode.h
/*
* 链表节点定义
* chainNode.h
*/
#ifndef CHAINNODE_H
#define CHAINNODE_H
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;
}
};
#endif // CHAINNODE_H
chainWithIterator.h
/*
* 加入了迭代器的链表
* chainWithIterator.h
*/
#ifndef CHAINWITHITERATOR_H
#define CHAINWITHITERATOR_H
#include<iostream>
#include<sstream>
#include<string>
#include"linearlist.h"
#include"chainnode.h"
#include"myexceptions.h"
using namespace std;
class linkedDigraph;
template <class T> class linkedWDigraph;
template<class T>
class chain : public linearList<T>
{
friend linkedDigraph;
friend linkedWDigraph<int>;
friend linkedWDigraph<float>;
friend linkedWDigraph<double>;
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(ostream &out) const;
//迭代器
class iterator;
iterator bebin(){return iterator(firstNode);}
iterator end(){return iterator(NULL);}
//迭代器类的定义
class iterator
{
public:
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//构造函数
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;
};
protected:
void checkIndex(int theIndex) const;//检查索引是否合法
chainNode<T>* firstNode;//指向链表第一个元素
int listSize;//链表元素个数
};
/*
* 类中某些函数的具体实现
*/
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;
}
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()
{
chainNode<T> *nextNode;
while(firstNode != NULL)
{
nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
template<class T>
void chain<T>::checkIndex(int theIndex) const
{
if(theIndex < 0 || theIndex >= listSize)
{
ostringstream s;
s <<"index = " <<theIndex <<" size = "<<listSize;
throw illegalIndex(s.str());
}
}
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;
}
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;
else
return index;
}
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;
}
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;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;
}
#endif // CHAINWITHITERATOR_H
linearList.h
/*
* 旧的线性表的抽象类
* linearList.h
*/
#ifndef LINEARLIST_H
#define LINEARLIST_H
#include<iostream>
using namespace std;
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 indexOf(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;
};
#endif // LINEARLIST_H
myExceptions.h
/*
* 异常类的定义和实现
* myException.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>
using namespace std;
//非法参数
class illegalParameterValue
{
public:
illegalParameterValue(string theMessage = "Illegal parameter value")
{
message = theMessage;
}
void outputMessage()
{
cout <<message <<endl;
}
private:
string message;
};
//非法输入的数据
class illegalInputData
{
public:
illegalInputData(string theMessage = "Illegal data input")
{
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;
};
#endif // MYEXCEPTIONS_H