赞
踩
从循环链表中的任何一个结点的位置都可以找到其他所有结点,而单链表做不到
循环条件:p!=L;p->next!=L
对循环链表,有时不给出头指针,而给出尾指针可以更方便的找到第一个和最后一个结点
终端结点:rear
开始结点:rear->next->next
LInkList Connect(LinkList Ta,LinkList Tb)
{//假设Ta、Tb都是非空的单循环链表
p=Ta->next; //p存表头结点
Ta->next=Tb->next->next; //Tb表头连接Ta表尾
delete Tb->next; //释放Tb表头结点
Tb->next=p; //修改指针
return Tb;
}
typedef struct DuNode{
ElemType data; //结点数据
struct DuLNode*prior; //指向前一个结点
struct DuLNode*next; //指向后一个结点
}DuLNode,*DuLinkList
Status Listlnsert_DuL(DuLinkList&L,int i,ElemType e){
if(!(p=GetElemP_DuL(L,i)))return ERROR;
s=new DuLNode;
s->data=e;
s->prior=p->prior;
s-next=p;
s->prior=s;
p->prior=s;
return ok;
Status Listlnsert_DuL(DuLinkList&L,int i,ElemType &e){
if(!(p=GetElemP_DuL(L,i)))return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
delete p;
return ok;
}
1.创建一个空表Lc
2.依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后,直至其中一个表变空为止
3.继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
void MergeList_Sq(SqList LA,SqList LB,SqList&LC){ pa=LA.elem;pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素 LC.length=LA.length+LB.length; //由表新长度为待合并两表的长度之和 LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间 pc=LC.elem; //指针pc指向新表的第一个元素 pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素 pb_last=LB.elem+LB.length-1; //指针pb_last指向LB表的最后一个元素 while(pa<=pa->last&&pb<=pb_last){ //两个表都非空 if(*pa<=*pb) *pc++=*pa++ //依次摘取两表中值较小的结点 else *pc++=*pb++;} while(pa<=pa_last) *pc++=*pa++; //LB表已达到表尾 while(pb<=pb_last) *pc++=*pb++; //LA表已达到表尾 }//MergeList_Sq
1.Lc指向La
2.依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后,直至其中一个表变空为止
3.继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
4.释放Lb表的表头结点
void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){ pa=La->next;pb=Lb->next; pc=Lc=la; //用La的头结点作为Lc的头结点 while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next;} else{ pc->next=pb; pc=pb; pb=pb->next;} } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点 }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。