数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1.下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为 x 的结点，对该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。
TYPE
link=^node
node=RECORD
key:char; freq:integer; pre,next:link;
END;
VAR l:link;
FUNCTION loc(l:link;x:char):link;
VAR p,q:link;
BEGIN
p:=l^.next; （1）_；
WHILE p^.key<>x DO p:=p^.next;
IF p=l THEN [ new(q); q^.key:=x; q^.freq:=0 ]
ELSE {找到}
[ p^.freq:=p^.freq+1; q:=p; （2）______；
WHILE q^.freq>p^.pre^.freq DO p:=p^.pre;
IF p<>q THEN [ （3）______ ]
；
IF （4）_ THEN [q^.next:=p, q^.pre;=p^.pre; p^.pre^.next:=q; p^.pre:=q]
return(q);
END;
正确答案
1.
(1) l^.key:=x;∥头结点l这时起监视哨作用
(2) l^.freq:=p^.freq ∥头结点起监视哨作用
(3) q->pre->next=q->next; q->next->pre=q->pre; ∥先将q结点从链表上摘下
q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥结点q插入结点p前
(4) q^.freq=0 ∥链表中无值为x的结点，将新建结点插入到链表最后（头结点前）。
如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！
-end-