专升本数据结构试题解析(8)
时间:2025-07-10
时间:2025-07-10
数据结构上机实验与习题解析 亱店↘打烊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);}