p->freq++; p->pre->next=p->next;p->next->pre=p->pre; /*将 x 结点
从链表上摘下*/
q=p->pre;
while(q->freq<=p->freq&&p!= (*L)) q=q->pre; /*查找插入
位置*/
if(q!=p->pre) /*将 x 结点
插入*/
{ q->next->pre=p;
p->next=q->next;
q->next=p;p->preq; /*调
整位置*/
}
return p;
}/*Locate_DuList */
13、【算法分析】留下三个链表中公共数据,首先查找两表 A 和 B 中公共数据,
再去 C 中找有无该数据。要消除重复元素,应记住前驱,要求时间复杂度 O
(m+n+p),在查找每个链表时,指针不能回溯。
【算法源代码】
LinkList Common(LinkList A, LinkList B, LinkList C)
{ pa=A->next;pb=B->next; pc=C->next; /*pa,pb 和 pc 是工作指针*/
pre=A;
while(pa && pb && pc) /*当三表均不空时,查找共同元素*/
{ while(pa && pb)
if(pa->data<pb->data) /*处理 pa 结点,后移指针*/
{u=pa;pa=pa->next;free(u);}
else if(pa->data> pb->data)pb=pb->next;
else if (pa && pb) /*处理 A 和 B 表元素值相等的结点*/
{ while(pc && pc->data<pa->data) pc=pc->next;
if(pc)
{if(pc->data>pa->data) /*处理 pa 结点,后移指针*/
{u=pa;pa=pa->next;free(u);}
else
{if(pre==A) /*结果表中第一个结点*/
{ pre->next=pa;pre=pa;pa=pa->next}
else if(pre->data==pa->data) /*重复结点不链入 A 表*/
{u=pa;pa=pa->next;free(u);}
else
{pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入 A 表 */
pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/
}
}
else
if(pa==NULL)pre->next=NULL; /*若 A 表已结束,置 A 表表尾*/
else /*处理原 A 表未到尾而 B 或 C 到尾的情况*/