📄 xtjd2.htm
字号:
else<br>
{<br>
pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表<br>
}<br>
pre=pc;<br>
}<br>
while(pa)<br>
{<br>
q=pa->next;pa->next=pc;pc=pa;pa=q; //插入A中余下的元素<br>
}<br>
while(pb)<br>
{<br>
q=pb->next;pb->next=pc;pc=pb;pb=q; //插入B中余下的元素<br>
}<br>
C=A;A->next=pc; //构造新表头<br>
}//reverse_merge<br>
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
<p>2.25
<p>void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中<br>
{<br>
i=1;j=1;k=0;<br>
while(A.elem[i]&&B.elem[j])<br>
{<br>
if(A.elem[i]<B.elem[j]) i++;<br>
if(A.elem[i]>B.elem[j]) j++;<br>
if(A.elem[i]==B.elem[j])<br>
{<br>
C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素,<br>
i++;j++; //就添加到C中<br>
}<br>
}//while<br>
}//SqList_Intersect
<p>2.26
<p>void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题<br>
{<br>
p=A->next;q=B->next;<br>
pc=(LNode*)malloc(sizeof(LNode));<br>
while(p&&q)<br>
{<br>
if(p->data<q->data) p=p->next;<br>
else if(p->data>q->data) q=q->next;<br>
else<br>
{<br>
s=(LNode*)malloc(sizeof(LNode));<br>
s->data=p->data;<br>
pc->next=s;pc=s;<br>
p=p->next;q=q->next;<br>
}<br>
}//while<br>
C=pc;<br>
}//LinkList_Intersect
<p>2.27
<p>void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中<br>
{<br>
i=1;j=1;k=0;<br>
while(A.elem[i]&&B.elem[j])<br>
{<br>
if(A.elem[i]<B.elem[j]) i++;<br>
else if(A.elem[i]>B.elem[j]) j++;<br>
else if(A.elem[i]!=A.elem[k])<br>
{<br>
A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素<br>
i++;j++; //且C中没有,就添加到C中<br>
}<br>
}//while<br>
while(A.elem[k]) A.elem[k++]=0;<br>
}//SqList_Intersect_True
<p>2.28
<p>void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题<br>
{<br>
p=A->next;q=B->next;pc=A;<br>
while(p&&q)<br>
{<br>
if(p->data<q->data) p=p->next;<br>
else if(p->data>q->data) q=q->next;<br>
else if(p->data!=pc->data)<br>
{<br>
pc=pc->next;<br>
pc->data=p->data;<br>
p=p->next;q=q->next;<br>
}<br>
}//while<br>
}//LinkList_Intersect_True
<p>2.29
<p>void SqList_Intersect_delete(SqList &A,SqList B,SqList C)//从有序顺序表A中删除那些在B和C中都出现的元素<br>
{<br>
i=1;j=1;k=1;<br>
while(B.elem[i]&&C.elem[j])<br>
{<br>
if(B.elem[i]<C.elem[j]) i++;<br>
else if(B.elem[i]>C.elem[j]) j++;<br>
else //找到了需要从A中删除的元素<br>
{<br>
u=B.elem[i];<br>
while(A.elem[k]<u) k++;<br>
for(;A.elem[k]==u;k++)<br>
A.elem[k]=INFINITY; //把A中待删除元素置换为特殊记号<br>
while(B.elem[i]==u) i++;<br>
while(C.elem[j]==u) j++;<br>
}//else<br>
}//while<br>
for(i=1,j=1;j<=A.length;i++) //第二遍扫描A,删除特殊记号<br>
{<br>
while(A.elem[j]==INFINITY)<br>
{<br>
j++;A.length--;<br>
}<br>
if(i<j) A.elem[i]=A.elem[j];//执行"紧缩"操作<br>
j++;<br>
}//for<br>
}//SqList_Intersect_delete<br>
分析:本算法的时间复杂度为O(m),m为表长.思考:你自己的算法时间复杂度是多少?实际上也可以只用一遍扫描就完成整个操作,且时间复杂度也为O(m),但非常复杂,你能写出来吗?
<p>2.30
<p>void LinkList_Intersect_delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题<br>
{<br>
p=B->next;q=C->next;r=A-next;<br>
while(p&&q&&r)<br>
{<br>
if(p->data<q->data) p=p->next;<br>
else if(p->data>q->data) q=q->next;<br>
else<br>
{<br>
u=p->data; //确定待删除元素u<br>
while(r->next->data<u)
r=r->next; //确定最后一个小于u的元素指针r<br>
if(r->next->data==u)<br>
{<br>
s=r->next;<br>
while(s->data==u)<br>
{<br>
t=s;s=s->next;free(t);
//确定第一个大于u的元素指针s<br>
}//while<br>
r->next=s; //删除r和s之间的元素<br>
}//if<br>
while(p->data=u) p=p->next;<br>
while(q->data=u) q=q->next;<br>
}//else<br>
}//while<br>
}//LinkList_Intersect_delete
<p>2.31
<p>Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱<br>
{<br>
p=s;<br>
while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p<br>
p->next=s;<br>
return OK;<br>
}//Delete_pre
<p>2.32
<p>Status DuLNode_pre(DuLinkList &L)//完成双向循环链表结点的pre域<br>
{<br>
for(p=L;!p->next->pre;p=p->next) p->next->pre=p;<br>
return OK;<br>
}//DuLNode_pre
<p>2.33
<p>Status LinkList_divide(LinkList &L,CiList &A,CiList &B,CiList
&C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.<br>
{<br>
s=L->next;<br>
A=(CiList*)malloc(sizeof(CiLNode));p=A;<br>
B=(CiList*)malloc(sizeof(CiLNode));q=B;<br>
C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点<br>
while(s)<br>
{<br>
if(isalphabet(s->data))<br>
{<br>
p->next=s;p=s;<br>
}<br>
else if(isdigit(s->data))<br>
{<br>
q->next=s;q=s;<br>
}<br>
else<br>
{<br>
r->next=s;r=s;<br>
}<br>
}//while<br>
p->next=A;q->next=B;r->next=C; //完成循环链表<br>
}//LinkList_divide
<p>2.34
<p>void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值<br>
{<br>
p=L.left;pre=NULL;<br>
while(p)<br>
{<br>
printf("%d",p->data);<br>
q=XorP(p->LRPtr,pre);<br>
pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针<br>
}<br>
}//Print_XorLinkedList
<p>2.35
<p>Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x<br>
{<br>
p=L.left;pre=NULL;<br>
r=(XorNode*)malloc(sizeof(XorNode));<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -