数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1.
PROC ins__linklist(la:linkisttp; i:integer; b:elemtp);
{la 为指向带头结点的单链表的头指针，本算法在表中第 i 个元素之前插入元素 b}
p:=(1) ; j:=(2) ;{指针初始化，j 为计数器}
WHILE (p<>NIL) AND ((3) ) DO [p:=(4) ; j:=j 1；]
{寻找第 i-1 个结点}
IF (p=NIL) OR ((5) )
THEN error (‘No this position’)
ELSE [new(s) ; s↑.data:=b; s↑.next:=p↑.next; p↑.next:=s;]
ENDP;{ins-linklist}
2.
已知双链表中结点的类型定义为：
TYPE dpointer=^list;
list=RECORD
data:integer; left,right:dpointer;
END;
如下过程将在双链表第 i 个结点（i>=0）之后插入一个元素为 x 的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。
PROCEDURE insert(VAR head:dpointer;i,x:integer);
VAR s,p:dpointer; j: integer;
BEGIN
new(s); s^.data:=x;
IF(i=0)THEN BEGIN s^.right:=head; (1)___ head:=s END{如果 i=0,则将 s 结点插入到表头后返回}
ELSE BEGIN p:=head; (2)_______；{在双链表中查找第 i 个结点,由 p 所指向}
WHILE ((p<>NIL) AND (j<i)) DO BEGIN j:=j 1; (3) _ END;
IF p<>NIL THEN
IF （p^.right=NIL）
THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END
ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END
ELSE writeln(‘can not find node!’)
END
END
正确答案
1．
(1)la
(2)0
(3)j<i-1
(4)p↑.next
(5)i<1
2.
(1)head^.left:=s ∥head的前驱指针指向插入结点
(2)j:=1;
(3)p:=p^.right ∥工作指针后移
(4)s^.left:=p
(5)p^.right^.left:=s; ∥p后继的前驱是s
(6)s^.left:=p;
如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！
-end-
你学习了么?
文 | 闫小林
