DS and Algorithm_session_03_doubly lingked list

《DS and Algorithm_session_03_doubly lingked list》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、delete前驱待删除后继前驱后继insert待插入1122.3.2带表头结点的单链表单链表在做插入和删除运算时，要考虑一般情况和特殊情况，用带表头结点的单链表可以简化上述两种算法。带表头结点的单链表在单链表前增加一个结点，称为表头结点。表头结点的数据域Entry不存放单链表的元素，它或者为空，或者用于存放实现算法所需的辅助数据。注意：区分“表头结点”和“头结点”，表头结点是添加的额外结点，头结点是单链表的起始结点1.带表头结点的单链表(a0,a1,...,ai...,an-1)在原单链表中增加一个结点，但它的element域中不存放线性表中的任何元素，称该

2、结点为表头结点。firsta0a1a2an-1…∧非空表first∧空表2.带表头结点单链表的构造、插入和删除（1）构造函数SingleList::SingleList(){first=NULL;n=0;}HeaderList::HeaderList(){Node*first=newNode;first->link=NULL;n=0;}first∧空表（2）插入操作templateboolHeaderList::Insert(inti,Tx){if(i<-1

3、

4、i>n-1){cout<<"OutOfBounds“

5、<*p=first;for(intj=0;j<=i;j++)p=p->link;Node*q=newNode;q->element=x;q->link=p->link;p->link=q;n++;returntrue;}（3）删除操作templateboolHeaderList::Delete(inti){if(!n){cout<<"UnderFlow"<

6、

7、i>n-1){cout<<"OutOfBounds"<

8、returnfalse;}Node*q=first,*p;for(intj=0;jlink;p=q->link;q->link=p->link;deletep;n--;returntrue;}qa0a1a2an-1…first∧p例如删除a2ObjectivesInthischapter,youwilllearnto:Implementadoubly-linkedlist（双向链表）Implementacircularlinkedlist（循环链表）Applylinkedliststosolveprogrammingprob

9、lemsConsiderasortedlistof100000numbersstoredinalinkedlist.Ifyouwanttodisplaythesenumbersinascendingorder,whatwillyoudo?Traversetheliststartingfromthefirstnode.ImplementingaDoubly-LinkedListNowconsideracaseinwhichyouneedtodisplaythesenumbersinadescendingorder.Howwillyousolvethisprob

10、lem?Eachnodeislinkedtothenextnodeinsequence.Thismeansthatyoucantraversethelistintheforwarddirectiononly.Todisplaythenumbersinthedescendingorder,youneedtoreversethelinkedlist.Algorithmtoreverseasingly-linkedlist.Declarethreevariables/pointersptr1,ptr2,andptr3.Ifthereisonlyonenodeint

11、helist:Exit.Markthefirstnodeinthelistasptr1.Markthesuccessorofptr1asptr2Markthesuccessorofptr2asptr3.Makethenextfieldofptr1pointtoNULL.Makethenextfieldofptr2pointtoptr1.Repeatuntilptr3becomesNULLSetptr1=ptr2Setptr2=ptr3Makeptr3pointtothenextnodeinitssequence.Makethenextfieldofptr2p

12、ointtoptr1.MakeSTARTpointt