青少年信息学竞赛Pascal语言：指针（十）(3)
单链表
单链表的数据类型可定义如下：
type dlb=^node;
node=record
data:datatype;
next:dlb;
end;
例1 连续输入一序列整数,组成链表（并以动态的形式把它们记录下来）,当输入的数为-1时,停止输入,然后把输入的整数按相反的顺序输出.
program lianbiao;
type link=^data;
data=record
num:integer;
next:link;
end;
var p,q:link;
i:integer;
begin
q:=nil;
readln(i);
while i<>-1 do
begin
new(p);
with p^ do
begin
num:=i;
next:=q;
end;
q:=p;
readln(i);
end;
while p<>nil do
begin
write(p^.num:6);
p:=p^.next;
end;
readln;
end.
练习:将例1中如果数据不按现反的顺序(按输入时的顺序)输出时,怎样建表.
程序：
建链表与顺序遍历:
program lianbiao;
type link=^data;
data=record
num:integer;
next:link;
end;
var head,p,tail:link;
i:integer;
begin
head:=nil;
readln(i);
while i<>-1 do
begin
new(p);
p^.num:=i;
p^.next:=nil;
if head=nil then begin head:=p; tail:=p end
else begin tail^.next:=p; tail:=p end;
readln(i);
end;
p:=head;
while p<>nil do
begin
write(p^.num:6);
p:=p^.next;
end;
readln;
end.
上述建表方式其实就是分别从表头和表尾插入元素,下面是从表中插入元素;
例2:输入若干整数（输入32767停止输入）排序（小到大）输出之。
program lianbiao;
type link=^data;
data=record
num:integer;
next:link;
end;
var head,p,q,r:link;
i:integer;
begin
head:=nil;
readln(i);
while i<>32767 do
begin
new(p);
p^.num:=i;
p^.next:=nil;
if head=nil then begin head:=p;end
else
begin
q:=head;
if p^.num<q^.num then begin head:=p;p^.next:=q end else
begin
while (p^.num >=q^.num) and (q<>nil) do begin r:=q ;q:=q^.next;end;
if q=nil then r^.next:=p else begin r^.next:=p;p^.next:=q end
end;
end;
readln(i);
end;
p:=head;
while p<>nil do
begin
write(p^.num:6);
p:=p^.next;
end;
readln;
end.
练习:建立一个若干整数的链表后(-1结束）再从链表中删除从键盘上输入一个整数的所有结点.
程序：
链表的删除程序如下:
program lianbiao;
type link=^data;
data=record
num:integer;
next:link;
end;
var head,p,tail,r:link;
i,x:integer;
begin
writeln('input lbdata:');
head:=nil;
readln(i);
while i<>-1 do
begin
new(p);
p^.num:=i;
p^.next:=nil;
if head=nil then begin head:=p; tail:=p end
else begin tail^.next:=p; tail:=p end;
readln(i);
end;
write('input delete integer:');
readln(x);
p:=head;
while p<>nil do
begin
if p^.num=x then
if p=head then begin head:=p^.next;p:=head end
else if p^.next<>nil then
begin r^.next:=p^.next ;p:=p^.next end
else
begin r^.next:=nil;p:=nil end
else begin r:=p;p:=p^.next end;
end;
p:=head;
while p<>nil do
begin
write(p^.num:6);
p:=p^.next;
end;
readln;
end.
往期最新阅读：信息学竞赛Pascal语言：集合类型（八）
更多内容，请参加合肥奥数网“杯赛竞赛”频道。
