专升本数据结构试题解析(8)

数据结构上机实验与习题解析 亱店↘打烊oO

p->next=q->next;/*将p结点链入链表*/

q->next=p;

p=r;

}

12．设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。

【算法分析】

1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步；

2）修改x结点的访问频度freq，并将结点从链表上摘下；

3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。

【算法源代码】

DuLNode * Locate_DuList(DuLinkList *L,int x)

{ p=(*L)->next;

while(p.data!=x&&p!= (*L)) p=p->next;

if(p==(*L)) return NULL; /*没找到x结点*/

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->pre=q; /*调整位置*/

}

return p;

}/*Locate_DuList */

13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。

【算法分析】留下三个链表中公共数据，首先查找两表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);}