数据结构考研分类复习真题 第二章 答案[55]

．[题目分析]首先在双向链表中查找数据值为x的结点查到后将结点从链表上摘下然后再顺结点的前驱链查找该结点的位置

DLinkList locate(DLinkList LElemType x)∥L是带头结点的按访问频度递减的双向链表本算法先查找数据x查找成功时结点的访问频度域增最后将该结点按频度递减插入链表中适当位置

{ DLinkList p=L>nextq;∥p为L表的工作指针q为p的前驱用于查找插入位置

while (p && p>data !=x) p=p>next;∥查找值为x的结点

if (!p) {printf(不存在值为x的结点\n); exit();}

else { p>freq++;∥令元素值为x的结点的freq域加

p>next>pred=p>pred;∥将p结点从链表上摘下

p>pred>next=p>next;

q=p>pred;∥以下查找p结点的插入位置

while (q !=L && q>freq<p>freq) q=q>pred;

p>next=q>next; q>next>pred=p;∥将p结点插入

p>pred=q; q>next=p;

}

return(p);∥返回值为x的结点的指针

}∥算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []