主函数:
// test the class arrayList that uses STL algorithms#include#include "linearList.h"#include "arrayList.h"using namespace std;int main(){ // test constructor linearList *x = new arrayList (20); arrayList y(2), z; // test capacity cout << "Capacity of x, y and z = " << ((arrayList *) x)->capacity() << ", " << y.capacity() << ", " << z.capacity() << endl; // test size cout << "Initial size of x, y, and z = " << x->size() << ", " << y.size() << ", " << z.size() << endl; // test empty if (x->empty()) cout << "x is empty" << endl; else cout << "x is not empty" << endl; if (y.empty()) cout << "y is empty" << endl; else cout << "y is not empty" << 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; cout << "Capacity of y = " << y.capacity() << endl; if (y.empty()) cout << "y is empty" << endl; else cout << "y is not empty" << endl; y.output(cout); cout << endl << "Testing overloaded <<" << endl; cout << y << 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; // test get cout << "Element with index 0 is " << y.get(0) << endl; cout << "Element with index 3 is " << y.get(3) << endl; // test erase y.erase(1); cout << "Element 1 erased" << endl; cout << "The list is " << y << endl; y.erase(2); cout << "Element 2 erased" << endl; cout << "The list is " << y << endl; cout << "Size of y = " << y.size() << endl; cout << "Capacity of y = " << y.capacity() << endl; if (y.empty()) cout << "y is empty" << endl; else cout << "y is not empty" << endl; try {y.insert(-3, 0);} catch (illegalIndex e) { cout << "Illegal index exception" << endl; cout << "Insert index must be between 0 and list size" << endl; e.outputMessage(); } // test copy constructor arrayList w(y); y.erase(0); y.erase(0); cout << "w should be old y, new y has first 2 elements removed" << endl; cout << "w is " << w << endl; cout << "y is " << y << endl; // a few more inserts, just for fun y.insert(0,4); y.insert(0,5); y.insert(0,6); y.insert(0,7); cout << "y is " << y << endl; return 0;}
数据结构中使用的类的定义，包括类中各种函数的具体实现，都保存在头文件中，具体代码如下：
arrayList.h#ifndef ARRAYLIST_H#define ARRAYLIST_H// array implementation of a linear list// derives from abstract class linearList just to make sure// all methods of the ADT are implemented// USES STL ALGORITHMS TO SIMPLIFY CODE#include#include #include #include #include #include "linearList.h"#include "myExceptions.h"#include "changeLength1D.h"using namespace std;template class arrayList : public linearList { public: // constructor, copy constructor and destructor arrayList(int initialCapacity = 10); arrayList(const arrayList &); ~arrayList() {delete [] element;} // ADT methods 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; // additional method int capacity() const {return arrayLength;} protected: void checkIndex(int theIndex) const; // throw illegalIndex if theIndex invalid T* element; // 1D array to hold list elements int arrayLength; // capacity of the 1D array int listSize; // number of elements in list};template arrayList ::arrayList(int initialCapacity){// Constructor. if (initialCapacity < 1) {ostringstream s; s << "Initial capacity = " << initialCapacity << " Must be > 0"; throw illegalParameterValue(s.str()); } arrayLength = initialCapacity; element = new T[arrayLength]; listSize = 0;}template arrayList ::arrayList(const arrayList & theList){// Copy constructor. arrayLength = theList.arrayLength; listSize = theList.listSize; element = new T[arrayLength]; copy(theList.element, theList.element + listSize, element);}template void arrayList ::checkIndex(int theIndex) const{// Verify that theIndex is between 0 and listSize - 1. if (theIndex < 0 || theIndex >= listSize) {ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str()); }}template T& arrayList ::get(int theIndex) const{// Return element whose index is theIndex. // Throw illegalIndex exception if no such element. checkIndex(theIndex); return element[theIndex];}template int arrayList ::indexOf(const T& theElement) const{// Return index of first occurrence of theElement. // Return -1 if theElement not in list. // search for theElement int theIndex = (int) (find(element, element + listSize, theElement) - element); // check if theElement was found if (theIndex == listSize) // not found return -1; else return theIndex; }template void arrayList ::erase(int theIndex){// Delete the element whose index is theIndex. // Throw illegalIndex exception if no such element. checkIndex(theIndex); // valid index, shift elements with higher index copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T(); // invoke destructor}template void arrayList ::insert(int theIndex, const T& theElement){// Insert theElement so that its index is theIndex. if (theIndex < 0 || theIndex > listSize) {// invalid index ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str()); } // valid index, make sure we have space if (listSize == arrayLength) {// no space, double capacity changeLength1D(element, arrayLength, 2 * arrayLength); arrayLength *= 2; } // shift elements right one position copy_backward(element + theIndex, element + listSize, element + listSize + 1); element[theIndex] = theElement; listSize++;}template void arrayList ::output(ostream& out) const{// Put the list into the stream out. copy(element, element + listSize, ostream_iterator (cout, " "));}// overload < ostream& operator<<(ostream& out, const arrayList & x) {x.output(out); return out;}#endif
changeLength1d.h
#ifndef CHANGELENGTH1D_H#define CHANGELENGTH1D_H#include "myExceptions.h"using namespace std;templatevoid changeLength1D(T*& a, int oldLength, int newLength){ if (newLength < 0) throw illegalParameterValue("new length must be >= 0"); T* temp = new T[newLength]; // new array int number = min(oldLength, newLength); // number to copy copy(a, a + number, temp); delete [] a; // deallocate old memory a = temp;}#endif // CHANGELENGTH1D_H
linearList.h
#ifndef LINEARLIST_H#define LINEARLIST_H// LINEARLIST_H// abstract class linearList// abstract data type specification for linear list data structure// all methods are pure virtual functions#includeusing namespace std;template 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 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};#endi
myexceptions.h
#ifndef MYEXCEPTIONS_H#define MYEXCEPTIONS_H#includeusing 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 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") {message = theMessage;} void outputMessage() {cout << message << endl;} private: string message;};// queue is emptyclass queueEmpty{ public: queueEmpty(string theMessage = "Invalid operation on empty queue") {message = theMessage;} void outputMessage() {cout << message << endl;} private: string message;};// hash table is fullclass hashTableFull{ public: hashTableFull(string theMessage = "The hash table is full") {message = theMessage;} void outputMessage() {cout << message << endl;} private: string message;};// edge weight undefinedclass undefinedEdgeWeight{ public: undefinedEdgeWeight(string theMessage = "No edge weights defined") {message = theMessage;} void outputMessage() {cout << message << endl;} private: string message;};// method undefinedclass undefinedMethod{ public: undefinedMethod(string theMessage = "This method is undefined") {message = theMessage;} void outputMessage() {cout << message << endl;} private: string message;};#endif // MYEXCEPTIONS_H