數(shù)據(jù)結(jié)構(gòu)-帶頭結(jié)點的循環(huán)鏈表

1、File chainNode.h#ifndef chainNode_#define chainNode_template <class T>struct chainNode / data members T element; chainNode<T> *next; / methods chainNode() next=NULL; chainNode(const T& element) this->element = element; this->next=NULL; chainNode(const T& element, chainNode&

2、lt;T>* 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 <iostream>using namespace s

3、td;template<class T>class 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

4、 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 vo

5、id 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<iostream>#include<sstream>#include<string>#include "c

6、hainNode.h"#include "myExceptions.h"#include "linearList.h"using namespace std;template<class T>class circularListWithHeader public: / 構(gòu)造函數(shù) circularListWithHeader(); / some methods bool empty()return listSize = 0; int size() const return listSize; T& get(int theInd

7、ex) 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); iterat

8、or 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; / 構(gòu)造函數(shù) iterator(ch

9、ainNode<T>* 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

10、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; ; / end of iterator class protected: void checkIndex(int theIndex) co

11、nst; / 如果索引無效，拋出異常 chainNode<T>* headerNode; / 指向鏈表第一個元素的指針 int listSize; / 元素個數(shù);template<class T>circularListWithHeader<T>:circularListWithHeader()/ 構(gòu)造函數(shù) headerNode = new chainNode<T>(); headerNode->next = headerNode; listSize = 0;template<class T>void circularListW

12、ithHeader<T>:checkIndex(int theIndex) const/ 確定 theIndex在 0和listSize - 1之間轉(zhuǎn)換. if (theIndex < 0 | theIndex >= listSize) ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str(); template<class T>T&

13、amp; circularListWithHeader<T>:get(int theIndex) constcheckIndex(theIndex);chainNode<T>* currentNode = headerNode->next;for(int i = 0;i<theIndex;i+)currentNode = currentNode->next;return currentNode->element;template<class T>int circularListWithHeader<T>:indexOf(c

14、onst T& theElement) const/ Return元素theElement首次出現(xiàn)時的索引. / 如果不存在Return -1 . /將theElement放入headerNode headerNode->element = theElement; / 在鏈表中尋找 theElement chainNode<T>* currentNode = headerNode->next;/指向鏈表的第一個 int index = 0; / 返回的索引，從0開始計數(shù) while (currentNode->element != theElement)

15、/ 移動到下一節(jié)點 currentNode = currentNode->next; index+; / 確定是否找到element if (currentNode = headerNode) return -1; else return index;template<class T>void circularListWithHeader<T>:erase(int theIndex)/ Delete索引為theIndex的元素. / 如果不存在這樣的元素就拋出異常.checkIndex(theIndex);/索引有效，需找要刪除的元素節(jié)點chainNode<

16、T>* deleteNode;/ use p 指向要刪除節(jié)點的前驅(qū)結(jié)點chainNode<T>* p = headerNode->next;for(int i = 0;i < theIndex - 1;i+)p = p->next;deleteNode = p->next;p->next = p->next->next;/ 刪除 deleteNode指向的節(jié)點listSize-;delete deleteNode;template<class T>void circularListWithHeader<T>:i

17、nsert(int theIndex, const T& theElement)/ Insert theElement so that its index is theIndex. if (theIndex < 0 | theIndex > listSize) / 無效索引 ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str(); / find 新

18、元素前驅(qū) chainNode<T>* p = headerNode; for (int i = 0; i < theIndex; i+) p = p->next; / insert after p p->next = new chainNode<T>(theElement, p->next); listSize+;template<class T>void circularListWithHeader<T>:output(ostream& out) const/ 把鏈表放入輸出流. for (chainNode&l

19、t;T>* currentNode = headerNode->next; currentNode != headerNode; currentNode = currentNode->next) out << currentNode->element << " "/ overload <<template <class T>ostream& operator<<(ostream& out, const circularListWithHeader<T>&

20、x) x.output(out); return out;template<class T>void circularListWithHeader<T>:reverse()if(listSize <= 1) return;chainNode<T>*currentNode = headerNode->next,*nextNode,*lastNode = headerNode;while(currentNode != headerNode)nextNode = currentNode->next;currentNode->next = l

21、astNode;lastNode = currentNode;currentNode = nextNode;headerNode->next = lastNode;File circularListWithHeader.cpp/ test the class circularListWithHeader#include<iostream>#include "circularListWithHeader.h"#include<numeric>using namespace std;int main() / test constructor cir

22、cularListWithHeader<int> 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

23、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 iter

24、ators pre and post +" << endl; for (circularListWithHeader<int>:iterator i = y.begin(); i != y.end(); i+) cout << *i << " " cout << endl; for(circularListWithHeader<int>:iterator i = y.begin(); i != y.end(); +i) cout << *i << " &quo

25、t; *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"

26、; << 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(); cout<<y<<endl; return 0;#endifF

27、ile myExceptions.h/ exception classes for various error types#ifndef myExceptions_#define myExceptions_#include <string>using namespace std;/ illegal parameter valueclass illegalParameterValue public: illegalParameterValue(string theMessage = "Illegal parameter value") message = theM

28、essage; 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: s

29、tring 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: matrixIndexOutO

30、fBounds (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 doesn't match") message = theMessage; void outputMessage() cout << message << endl; private: string message;/ stack is emptyclass stackEmpty public: stackEmpty(string theMessage = "Invalid operation on empty stack