设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中

admin2013-09-16  32

问题 设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中结点的次序,使其按访问频度的递减序列排序,以便使被频繁访问的结点总靠近表头,试写一符合上述要求的LocateNode运算的算法。

选项

答案在DLinkList类型的定义中添加freq域(int类型),给该域初始化为0。在每次查找到一个结点*P时,使其freq域增1,再在*P结点的前面找到一个结点*q,它或是头结点或是满足q->freq>=p->freq,然后删除*P结点,使其插入到*q结点之后。算法描述如下: int LocateNode(DLinkList*h,ElemType x) { DLinkList *p=h一b->next,*q; while(p!=NULL&&p->data!=x) p=p一>

解析
转载请注明原文地址:https://kaotiyun.com/show/rgxi777K
0

最新回复(0)