数据结构-带头结点的循环链表.docx

File chainNode.h#ifndef chainNode_#define chainNode_template struct chainNode / data members T element; chainNode *next; / methods chainNode() next=NULL; chainNode(const T& element) this-element = element; this-next=NULL; chainNode(const T& element, chainNode* next) this-element = element; this-next = next;#endifFile linnerList.h/ abstract class linearList/ abstract data type specification for linear list data structure/ all methods are pure virtual functions#ifndef linearList_#define linearList_#include using namespace std;templateclass linearList public: virtual linearList() ; virtual bool empty() const = 0; / return true iff list is empty virtual int size() const = 0; / return number of elements in list virtual T& get(int theIndex) const = 0; / return element whose index is theIndex virtual int indexOf(const T& theElement) const = 0; / return index of first occurence of theElement virtual void erase(int theIndex) = 0; / remove the element whose index is theIndex virtual void insert(int theIndex, const T& theElement) = 0; / insert theElement so that its index is theIndex virtual void output(ostream& out) const = 0; / insert list into stream out;#endifFile circularListWithHeader.h/ circularList list with header node and iterator#ifndef circularListWithHeader_#define circularListWithHeader_#include#include#include#include chainNode.h#include myExceptions.h#include linearList.husing namespace std;templateclass circularListWithHeader public: / 构造函数 circularListWithHeader(); / some methods bool empty()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; void reverse(); / iterators to start and end of list class iterator; iterator begin() return iterator(headerNode-next); iterator end() return iterator(headerNode); / iterator for chain class iterator public: / typedefs required by C+ for a forward iterator typedef forward_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; / 构造函数 iterator(chainNode* theNode = NULL) node = theNode; / 解引用操作符 T& operator*() const return node-element; T* operator-() const return &node-element; / 迭代器加法操作 iterator& operator+() / preincrement node = node-next; return *this; iterator operator+(int) / postincrement 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* node; ; / end of iterator class protected: void checkIndex(int theIndex) const; / 如果索引无效，抛出异常 chainNode* headerNode; / 指向链表第一个元素的指针 int listSize; / 元素个数;templatecircularListWithHeader:circularListWithHeader()/ 构造函数 headerNode = new chainNode(); headerNode-next = headerNode; listSize = 0;templatevoid circularListWithHeader:checkIndex(int theIndex) const/ 确定 theIndex在 0和listSize - 1之间转换. if (theIndex = listSize) ostringstream s; s index = theIndex size = listSize; throw illegalIndex(s.str(); templateT& circularListWithHeader:get(int theIndex) constcheckIndex(theIndex);chainNode* currentNode = headerNode-next;for(int i = 0;inext;return currentNode-element;templateint circularListWithHeader:indexOf(const T& theElement) const/ Return元素theElement首次出现时的索引. / 如果不存在Return -1 . /将theElement放入headerNode headerNode-element = theElement; / 在链表中寻找 theElement chainNode* currentNode = headerNode-next;/指向链表的第一个 int index = 0; / 返回的索引，从0开始计数 while (currentNode-element != theElement) / 移动到下一节点 currentNode = currentNode-next; index+; / 确定是否找到element if (currentNode = headerNode) return -1; else return index;templatevoid circularListWithHeader:erase(int theIndex)/ Delete索引为theIndex的元素. / 如果不存在这样的元素就抛出异常.checkIndex(theIndex);/索引有效，需找要删除的元素节点chainNode* deleteNode;/ use p 指向要删除节点的前驱结点chainNode* p = headerNode-next;for(int i = 0;i next;deleteNode = p-next;p-next = p-next-next;/ 删除 deleteNode指向的节点listSize-;delete deleteNode;templatevoid circularListWithHeader:insert(int theIndex, const T& theElement)/ Insert theElement so that its index is theIndex. if (theIndex listSize) / 无效索引 ostringstream s; s index = theIndex size = listSize; throw illegalIndex(s.str(); / find 新元素前驱 chainNode* p = headerNode; for (int i = 0; i next; / insert after p p-next = new chainNode(theElement, p-next); listSize+;templatevoid circularListWithHeader:output(ostream& out) const/ 把链表放入输出流. for (chainNode* currentNode = headerNode-next; currentNode != headerNode; currentNode = currentNode-next) out element ;/ overload template ostream& operator(ostream& out, const circularListWithHeader& x) x.output(out); return out;templatevoid circularListWithHeader:reverse()if(listSize = 1) return;chainNode*currentNode = headerNode-next,*nextNode,*lastNode = headerNode;while(currentNode != headerNode)nextNode = currentNode-next;currentNode-next = lastNode;lastNode = currentNode;currentNode = nextNode;headerNode-next = lastNode;File circularListWithHeader.cpp/ test the class circularListWithHeader#include#include circularListWithHeader.h#includeusing namespace std;int main() / test constructor circularListWithHeader y; / test size cout Initial size of y = y.size() endl; / test insert 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 Inserted 6 integers, list y should be 1 2 3 4 5 6 endl; cout Size of y = y.size() endl; y.output(cout); cout endl Testing overloaded endl; cout y endl; / test iterator cout endl Ouput using forward iterators pre and post + endl; for (circularListWithHeader:iterator i = y.begin(); i != y.end(); i+) cout *i ; cout endl; for(circularListWithHeader:iterator i = y.begin(); i != y.end(); +i) cout *i ; *i += 1; cout endl; / test indexOf int index = y.indexOf(4); if (index 0) cout 4 not found endl; else cout The index of 4 is index endl; index = y.indexOf(7); if (index 0) cout 7 not found endl; else cout The index of 7 is index endl; int sum = accumulate(y.begin(), y.end(), 0);/初始值是0 cout The sum of the elements is sum endl; /test reverse y.reverse(); coutyendl; return 0;#endifFile myExceptions.h/ exception classes for various error types#ifndef myExceptions_#define myExceptions_#include using namespace std;/ illegal parameter valueclass illegalParameterValue public: illegalParameterValue(string theMessage = Illegal parameter value) message = theMessage; void outputMessage() cout message endl; private: string message;/ illegal input dataclass illegalInputData public: illegalInputData(string theMessage = Illegal data input) message = theMessage; void outputMessage() cout message endl; private: string message;/ illegal indexclass illegalIndex public: illegalIndex(string theMessage = Illegal index) message = theMessage; void outputMessage() cout message endl; private: string message;/ matrix index out of boundsclass matrixIndexOutOfBounds public: matrixIndexOutOfBounds (string theMessage = Matrix index out of bounds) message = theMessage; void outputMessage() cout message endl; private: string message;/ matrix size mismatchclass matrixSizeMismatch public: matrixSizeMismatch(string theMessage = The size of the two matrics doesnt match) message = theMessage; void outputMessage() cout message endl; private: string message;/ stack is emptyclass stackEmpty public: stackEmpty(string theMessage = Invalid operation on empty stack) message = theMessage; void outputMessage() cou