用程序表达的有隔断的盒子——线性表（C++）

为什么把线性表比喻成一个有隔断的盒子？

因为它有一块连续的存储空间，不管从左边用还是从右边用都有唯一的“第一个格子”和“最后一个格子”，除了两头的格子，其他的都紧挨着两个格子。

注:图片来自于互联网
线性结构的基本特征：
1．集合中必存在唯一的一个"第一元素"；
2．集合中必存在唯一的一个"最后元素"；
3．除最后元素在外，均有唯一的后继；
4．除第一元素之外，均有唯一的前驱。
线性表类代码:
#ifndef seqlist_H<br />#define seqlist_H<br /><br />template<class ElemType><br />class seqlist<br />{<br />private:<br /> ElemType* sl_;<br /> int slsize_; //线性表大小<br /> int currsize_; //插入元素的个数 <br /><br />public:<br /> seqlist(int size); //构建函数<br /> ~seqlist(); //析构函数<br /> bool Insert(int pos,ElemType item); //插入(pos>=0)<br /> bool Delete(int pos); //删除(pos>=0)<br /> inline int Length(){return slsize_;}; //返回线性表大小<br /> inline int Size(){return currsize_;}; //返回已填入元素的大小<br /> ElemType* Get(int pos); //(pos>=0) <br /> ElemType* Prior(int pos); //取前驱元素<br /> ElemType* Next(int pos); //取后继元素 <br /> int Locate(ElemType elem); //定位元素的位置<br /> void SetNull(); //置空队列<br /> bool Empty(); //判断是否空队列<br />};<br /><br />template<class ElemType><br />seqlist<ElemType>::seqlist(int size) <br />{<br /> sl_ = new ElemType[size];<br /> slsize_ = size;<br /> currsize_ = 0;<br />}<br /><br />template<class ElemType><br />seqlist<ElemType>::~seqlist()<br />{<br /> delete [] sl_; <br />}<br /><br />template<class ElemType><br />bool seqlist<ElemType>::Insert(int pos,ElemType item)<br />{<br /> if(pos >= 0 && pos <= currsize_ && currsize_ < slsize_)<br /> {<br /> for(int i = currsize_; i >= pos; i--)<br /> {<br /> sl_[i+1] = sl_[i]; <br /> }<br /> sl_[pos] = item;<br /> currsize_ += 1;<br /> return true;<br /> }<br /> else<br /> return false;<br />}<br /><br />template<class ElemType><br />bool seqlist<ElemType>::Delete(int pos)<br />{<br /> if(pos >= 0 && pos < currsize_)<br /> {<br /> for(int i = pos; i < currsize_; i++)<br /> {<br /> sl_[i-1] = sl_[i];<br /> }<br /> currsize_ -= 1; <br /> return true;<br /> }<br /> else<br /> return false;<br />}<br /><br />template<class ElemType><br />ElemType* seqlist<ElemType>::Get(int pos)<br />{<br /> if(pos >= 0 && pos < currsize_)<br /> return &sl_[pos];<br /> else return NULL;<br />}<br /><br />template<class ElemType><br />ElemType* seqlist<ElemType>::Prior(int pos)<br />{<br /> return Get(pos-1);<br />}<br /><br />template<class ElemType><br />ElemType* seqlist<ElemType>::Next(int pos)<br />{<br /> return Get(pos+1);<br />}<br /><br />template<class ElemType><br />int seqlist<ElemType>::Locate(ElemType elem)<br />{<br /> for(int i = 0; i < currsize_; i++)<br /> {<br /> if(elem == sl_[i])<br /> return i+1;<br /> }<br /> return -1;<br />}<br /><br />template<class ElemType><br />void seqlist<ElemType>::SetNull()<br />{<br /> for(int i = 0; i < currsize_; i++)<br /> {<br /> this->Delete(i);<br /> }<br />}<br /><br />template<class ElemType><br />bool seqlist<ElemType>::Empty()<br />{<br /> return (currsize_ == 0)<br />}<br /><br />#endif
测试代码：
void listall(seqlist<int>* sl) //列出已填入元素<br />{<br /> cout << "cout:" << sl->Size() << endl;<br /> for(int i=0; i < sl->Size(); i++)<br /> {<br /> cout << "pos:" << i << ",item:" << *sl->Get(i) << endl;<br /> }<br />}<br />void seqlist_test()<br />{<br /> //创建对象<br /> seqlist<int>* sl = new seqlist<int>(10);<br /> //倒插入8个元素<br /> cout << "insert 8 items!" << endl;<br /> for(int i = 0; i < 8 ; i++)<br /> {<br /> sl->Insert(i,i);<br /> cout << "pos:" << i << ",Insert:" << i << endl;<br /> }<br /> //列出已填入元素<br /> cout << "result:" << endl;<br /> listall(sl);<br /> //删除位置3上的元素<br /> cout << "delete the 4th item!"<< endl;<br /> sl->Delete(3);<br /> cout << "result:" << endl;<br /> //列出已填入元素<br /> listall(sl);<br /> //销毁对象<br /> delete sl;<br />}