3-3线性表-双向循环链表.ppt

《3-3线性表-双向循环链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式ai三、p95程序3-21双向链表a2a3a1LeftEndRightEnda2a3a1LLengthtemplateintDouble::Length()const{intlen=0;DoubleNode*current=RightEnd;while(current){current=current->left;len++;}returnlen;}LengthtemplateintDouble::Length()const{intlen=0;

2、DoubleNode*current=LeftEnd;while(current){current=current->right;len++;}returnlen;}Insertai-1aies->right=p->right;s->left=p;p->right=s;s->right->left=s;psai-1aiDeleteai-1aiai+1p->right=q->right;q->right->left=p;pai-1qq=p->right;双向循环链表LeftEndRightEnda2a3a1LeftEndRightEndfirst间接寻址链

3、表a1a2a3tablea1a2a3间接寻址链表templateclassIndirectList{public:IndirectList(intMaxListSize=10);virtual~IndirectList();boolIsEmpty()const{returnlength==0;}intLength()const{returnlength;}boolFind(intk,T&x);intSearch(T&x)const;IndirectList&Delete(intk,T&x);IndirectList&Insert(i

4、ntk,constT&x);voidOutput(std::ostream&out)const;private:T**table;intlength,MaxSize;};构造函数templateIndirectList::IndirectList(intMaxListSize){MaxSize=MaxListSize;length=0;table=newT*[MaxSize];}tablea1a2a3释构函数templateIndirectList::~IndirectList(){for(inti=0;i

5、th;i++)deletetable[i];delete[]table;}Insert函数templateIndirectList&IndirectList::Insert(intk,constT&x){if(k<0

6、

7、k>length)throwOutOfBounds();if(length==MaxSize)throwNomem();for(inti=length-1;i>=k;i--)table[i+1]=table[i];table[k]=newT;*table[k]=x;length++;return*this;}Dele

8、te函数templateIndirectList&IndirectList::Delete(intk,T&x){if(k<1

9、

10、length