admin 管理员组文章数量: 1086864
最基本的顺序表（经典顺序表）
// 顺序表.cpp -- 最基本的顺序表（经典顺序表）
// 完整的class.// List abstract class -- 线性表的C++抽象类声明
template<class Elem> class List()
{public:// Reinitialize the list. the client is responsible for// reclaiming the storange used by the list elements.virtual void clear() = 0;// Insert an element at the front of the right partition.// Return true if successful, false if the list is full.virtual bool insert(const Elem&) = 0;// Append an element at the end of the right partition.// Return true if successful, false if the list is full.virtual bool append(const Elem&) = 0;// Remove the first element of right partition. Return// true if successful, false if the list is empty.// The element removed is returned in the parameter.virtual bool remove(Elem&) = 0;// Place fence at list start, making left partition empty.virtual void setStart() = 0;// Place fence at list end, making right partition empty.virtual void setEnd() = 0;// Move fence one step left; no change if already at start.virtual void prev() = 0;// Move fence one step right; no change if already at endvirtual void next() = 0;// Return length of left partitionvirtual int leftLength() const = 0;// Return length of right partitionvirtual int rightLength() const = 0;// If pos or more elements are in the list, set the size// of left partition to pos and return true. Otherwise,// do nothing and return false.virtual bool setPos(int pos) = 0;// Return in first parameter the first element of the// right partition. Return true if successful, false // if the right partition is empty.virtual bool getValue(Elem&) const = 0;// print the contents of the listvirtual void print() const = 0;
};// Array-based list implementation -- 线性表的实现
template <class Elem>
class Alist: public List<Elem> //继承
{private:int maxSize; // Maximum size of listint listSize; // Actual number of elements in listint fence; // Position of fenceElem* listArray; // Array holding list elementsspublic:AList(int size = DefaultListSize) // constructor{maxSize = size;lastSize = fence = 0;listArray = new Elem[maxSize];}~AList() { delete [] listArray;} // Destructorvoid clear(){delete [] listArray;listSize = fence = 0;listArray = new Elem[maxSize];}bool insert(const Elem&);bool append(const Elem&);bool remove(Elem&);void setStart() { fence = 0;}void setEnd() { fence = listSize;}void prev() { if (fence != 0) fence--;}void next() { if (fence <= listSize) fence++;}int leftLength()const {return fence;}int rightLength()const {return lastsize - fence;}bool setPos(int pos){if ((pos >= 0) && (pos <= listSize)) fence = pos;return (pos >= 0) && (pos <= listSize);}bool getValue(Elem& it)const(){if (rightLength() == 0) return flase;else { it = listArray[fence]; reutrn true;}}void print()const {int temp = 0;cout << " < ";while (temp < fence) cout << listArray[temp++] << " ";cout << " | ";while (temp < ListSize) cout << listarray[temp++] << " ";cout << " >\n";}
};template <class Elem> // Insert at front of right partition
bool Alist <Elem>::insert(const Elem& item)
{if (listsize == maxSize) return flase; // List is fullfor (int i = listsize; i > fence; i--) // Shift Elem uplistArray[i] = listArray[i-1]; // to make roomlistArray[fence] = item;listSize++; // Increment list sizereturn true;
}// Remove and return first Elem in right partition
template <class Elem> bool AList <Elem>::remove(Elem& it)
{if (rightLength() == 0) return false; // nothing in rightit = listArray[fence]; // copy removed elemfor (int i = fence; i < listSize -1; i++) // Shift them downlistArray[i] = listArray[i + 1];listSize--; // Decrement Sizereturn true;
}// 看完以后就觉得，原来掌握顺序表是很简单的事，只需要掌握几个点；
// 其中最重要的思想是确定位置。
// 知道现在的位置，开始的位置，结束的位置，数组的大小，该位置左右的大小。
本文标签： 最基本的顺序表（经典顺序表）
版权声明：本文标题：最基本的顺序表（经典顺序表） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686714476a28398.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论