结构推理
已知L是一个数据类型linkedlist的单循环链表,pa和pb是指向L中结点的指针。简述下列程序段的功能。
TYPE linkedlist=↑node;
node=RECORD
data:datatype; next:linkedlist
END;
PROC Mp(pa,pb:linkedlist);
PROC subp(s,q: linkedlist);
p:=s;
WHILE p↑.next<>q DO p:=p↑.next;
p↑.next:=s
ENDP;
subp(pa,pb);
subp(pb,pa);
ENDP;
【正确答案】mp是一个过程,其内嵌套有过程subp。
subp(s,q)的作用是构造从s到q的循环链表。
subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。
subp(pb,pa)调用结果是将pb到pa的前驱(指在L链表中,并非刚构造的pa循环链表中)构造为循环链表。
总之,两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。
【答案解析】