问答题
设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针)域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Loga,te(L，x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学1997年】
【正确答案】正确答案：算法的基本设计思想：首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。算法的代码： DLinkList 10cate(DLinkLiSt L，ElemType x){ ／IL是带头结点的按访问频度递减的双向链表，本算法先查找数据X，查找成功 ／／时结点的访问频度域增l，最后将该结点按频度递减插入链表中适当的位置 DLinkLiSt p=L一>next，q； ／／P为L表的工作指针，q为P的前驱，用于查找插入位置 while(p＆＆p一>data!=x) ／／查找值为x的结点 P=P一>next； if(!P) { printf(“不存在值为x的结点＼n”)j return NULL； } else { p一>freq++； ／／令元素值为x的结点的freq域加1 p->next一>pred=p一>pred； ／／将P结点从链表上摘下 P一>pred一>next=P一>next ； q=p->pred； ／／以下查找P结点的插入位置 while(q!=L=&&q一>freq
freq) q=q一>pred； P一>next=q一>next： q一>next一>pred=p； ／／将P结点插入 P一>pred=q； q一>next=P ; } return P; ／／返回值为x的结点的指针 }／／locate
【答案解析】