数据结构 | 每日一练（27）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

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-