2.8 一直A,B和C为三个有序链表,编写算法从A表中删除B表和C表中共有的数据元素。
分析:被删除的元素特点为: = bj =
其他元素则为:
ai < bj 或 bj < ck 或 ck < ai
设三个指针的pa,pb和pc分别指向这三个链表中的相应结点,则算法中的主要操作为:
if(pa->data <pb->data) {pre = pa ; pa = pa->next}
else if(pb->data < pc->data) { pb = pb->next }
else if(pc->data < pa->data) { pc = pc ->next }
else{//删除
pre->next = pa->next; free(pa);
pa =pre->next;
}
2.9 双向循环链表的结点中,增加一个访问频度的数据域 freq,编写算法实现 LOCATE(L,x)。
分析:
1,算法的基本的操作应该是在链表中进行搜索,直至p->data = x为止。
2,在访问的品读freq增1之后,需将该结点调整到合适的位置,向前搜索直至找到一个访问频度大于它的结点为止。
p=L->next; //L 为双向链表的头指针。
while(p!L && p->data!=x) p=p->next; //如果p等于头结点了,那么证明已经循环一圈了。
if(p==L) return NULL;
q=p->priou;
while(q!=L && q->freq<p->freq) q=q->priou;//搜索访问频度不小于它的结点、
删除结点 *p;
将结点*p 插入在结点 *q之后。
此问题的搜索结果有两种,一个是找到之后,一个是没有找到之后所做出的操作;