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

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

admin2014-12-08  34
问题 设有一个双向链表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＋＋； ／／频度增1 q＝q－>prior； ／／*q为*p前驱结点 if(q!＝h){ ／／若*p为第一个数据结点，则不移动 while(q!＝h&&q－>freqfreq) ／／找到*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 1； } }
解析 在DuLinkList类型的定义中添加freq域(int类型)，给该域初始化为0。在每次查找到一个结点*p时，使其freq域增1，再在*p结点的前面找到一个结点*q，它或是头结点或是满足q－>freq>＝p－>freq，然后删除*p结点，使其插入到*q结点之后。
转载请注明原文地址:https://kaotiyun.com/show/wpxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)