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

admin2013-12-31  32

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

选项

答案算法如下: int LocateNode(DuLlnkList&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->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 1; } }

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

随机试题
最新回复(0)