数据结构|线性表的数组表示数据结构|算法与应用

【数据结构|线性表的数组表示】抽象数据类型 linearList

// 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; 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 }; #endif

可变长度一维数组

// change the length of an array#ifndef changeLength1D_ #define changeLength1D_#include "myExceptions.h"using namespace std; template void 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

类 arraylist

// 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#ifndef arrayList_ #define arrayList_#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 << template ostream& operator<<(ostream& out, const arrayList& x) {x.output(out); return out; }#endif