问答题
设有一头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针)域外,还有一个访问频度域freq。在链表被起用前,其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点的最后,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。【清华大学1997二(10分)】【苏州大学2004四(15分)】【江苏大学2006四、2(13分)】
【正确答案】正确答案:先查找x,若失败,则在链表尾插入;若查找成功,则域freq增1。将该结点暂从链表上摘下,按域freq值向前查找其插入位置。先前已有双向链表的插入、删除,这里不再赘述。
【答案解析】