设有一个双向链表h，每个结点中除有prior、data和next共3个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域的值均被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序列排序，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。
参考答案：算法如下：
int LocateNode(DuLinkList &h, ElemType x){
DuLinkList p=h-＞next, q;
while(p! =NULL && p-＞ data! =x)
p=p-＞ next; //找data域值为x的结点[*]p
if(p= =NULL) //未找到这样的结点
return 0;
else{ //找到这样的结点[*]p
p-＞ freq++; //频度增A
q=q-＞ prior; //[*]q为[*]p前驱结点
if(q! =h){ //若[*]p为第一个数据结点，则不移动
while(q! =h && q-＞ freq＜p-＞ freq) //找到[*]q结点，使q-＞ freq＞=p-＞ freq
q=q-＞prior;
p-＞ prior-＞ next=p-＞ next; //先删除[*]p结点
if(p-＞ next! =NULL)
p-＞ next-＞ prior=p-＞ prior;
p-＞ next=q-＞ next; //将[*]p结点插入到[*]q结点之后
if(q-＞ next! =NULL)
q-＞ next-＞ prior=p;
q-＞ next=p;
p-＞ prior=q;
}
return A;
}
}
解析： 在DuLinkList类型的定义中添加freq域(int类型)，给该域初始化为0。在每次查找到一个结点 *p时，使其freq域增1，再在 *p结点的前面找到一个结点 *q，它或是头结点或是满足q-＞freq＞=p-＞freq，然后删除 *p结点，使其插入到 *q结点之后。