题目
试设计一个实现下述要求的locate运算的函数。设有一个带头结点的双向链表L,每个结点有4个数据成员:指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data 和访问频度freq。 所有结点的freq初始时都为0。每当在链表上进行一次locate(x)操作时,令元素值为x的结点的访问频度freq加1,并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表中所有结点保持按访问频度递减的顺序排列,以使频繁访问的结点总是靠近表头。
分析
算法用到了四个双向循环链表的主要操作:
(1)正向搜索寻找满足要求的结点;
(2)把该结点从链表中摘下;
(3)反向分解访问计数寻找插入位置;
(4)把该结点重新插入到链中。
代码
核心代码:
DLNode * locate(DLNode *&DL,int x) {
DLNode *p=DL->next;
DLNode *q;
while(p!=NULL&&p->data!=x) {
p=p->next;
}
if(p!=NULL) {
++(p->freq);
q=p;// 该结点的访问频度加1
q->prior->next=q->next;// 从链表中摘下这个结点
q->next->prior=q->prior;
p=q->prior;// 寻找重新插入的位置
while(p!=DL&&q->freq>p->freq) p=p->prior;
q->next=p->next;
q->prior=p;// 插入在p之后
p->next->prior=q;
p->next=q;
return q;// 返回找到的结点地址
} else {
return NULL;// 没找到
}
}