欢迎来到天天文库
浏览记录
ID:21240122
大小:3.03 MB
页数:177页
时间:2018-10-20
《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;}qa0a1a2an-1…first∧p例如删除a2ObjectivesInthischapter,youwilllearnto:Implementadoubly-linkedlist(双向链表)Implementacircularlinkedlist(循环链表)Applylinkedliststosolveprogrammingprob9、lemsConsiderasortedlistof100000numbersstoredinalinkedlist.Ifyouwanttodisplaythesenumbersinascendingorder,whatwillyoudo?Traversetheliststartingfromthefirstnode.ImplementingaDoubly-LinkedListNowconsideracaseinwhichyouneedtodisplaythesenumbersinadescendingorder.Howwillyousolvethisprob10、lem?Eachnodeislinkedtothenextnodeinsequence.Thismeansthatyoucantraversethelistintheforwarddirectiononly.Todisplaythenumbersinthedescendingorder,youneedtoreversethelinkedlist.Algorithmtoreverseasingly-linkedlist.Declarethreevariables/pointersptr1,ptr2,andptr3.Ifthereisonlyonenodeint11、helist:Exit.Markthefirstnodeinthelistasptr1.Markthesuccessorofptr1asptr2Markthesuccessorofptr2asptr3.Makethenextfieldofptr1pointtoNULL.Makethenextfieldofptr2pointtoptr1.Repeatuntilptr3becomesNULLSetptr1=ptr2Setptr2=ptr3Makeptr3pointtothenextnodeinitssequence.Makethenextfieldofptr2p12、ointtoptr1.MakeSTARTpointt
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;}qa0a1a2an-1…first∧p例如删除a2ObjectivesInthischapter,youwilllearnto:Implementadoubly-linkedlist(双向链表)Implementacircularlinkedlist(循环链表)Applylinkedliststosolveprogrammingprob9、lemsConsiderasortedlistof100000numbersstoredinalinkedlist.Ifyouwanttodisplaythesenumbersinascendingorder,whatwillyoudo?Traversetheliststartingfromthefirstnode.ImplementingaDoubly-LinkedListNowconsideracaseinwhichyouneedtodisplaythesenumbersinadescendingorder.Howwillyousolvethisprob10、lem?Eachnodeislinkedtothenextnodeinsequence.Thismeansthatyoucantraversethelistintheforwarddirectiononly.Todisplaythenumbersinthedescendingorder,youneedtoreversethelinkedlist.Algorithmtoreverseasingly-linkedlist.Declarethreevariables/pointersptr1,ptr2,andptr3.Ifthereisonlyonenodeint11、helist:Exit.Markthefirstnodeinthelistasptr1.Markthesuccessorofptr1asptr2Markthesuccessorofptr2asptr3.Makethenextfieldofptr1pointtoNULL.Makethenextfieldofptr2pointtoptr1.Repeatuntilptr3becomesNULLSetptr1=ptr2Setptr2=ptr3Makeptr3pointtothenextnodeinitssequence.Makethenextfieldofptr2p12、ointtoptr1.MakeSTARTpointt
8、returnfalse;}Node*q=first,*p;for(intj=0;jlink;p=q->link;q->link=p->link;deletep;n--;returntrue;}qa0a1a2an-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
此文档下载收益归作者所有