数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred（前驱指针），data（数据）和 next（后继指针）域外，还有一个访问频度域 freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
正确答案
PS：||代表注释
1．[题目分析]首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。
DLinkList locate(DLinkList L，ElemType x)∥ L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。
{ DLinkList p=L->next,q; ∥p为L表的工作指针，q为p的前驱，用于查找插入位置。
while (p && p->data !=x) p=p->next; ∥ 查找值为x的结点。
if (!p) {printf(“不存在值为x的结点\n”); exit(0);}
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<p->freq) q=q->pred;
p->next=q->next; q->next->pred=p;∥ 将p结点插入
p->pred=q; q->next=p；
}
return(p); ∥返回值为x的结点的指针
} ∥ 算法结束