PROGRAM E1(INPUT,OUTPUT);
TYPE point=^pp;
pp=record
data:string[5];
link:point;
end;
VAR
p1,p2,k:point;
i:integer;
BEGIN
{产生新结点P1,作为链表的头}
new(p1);
writeln('input data');
readln(p1^.data);
{指针K指向链表头}
k:=p1;
{用循环产生9个新结点,每个结点都接在上一个结点之后}
for i:=1 to 9 do
begin
new(p2);
writeln('input data');
readln(p2^.data);
p1^.link:=p2;
p1:=p2;
end;
{给最后一个结点的LINK域赋空值NIL}
p2^.link:=nil;
{从链表头开始依次输出链表中的DATA域}
while k^.link<>nil do
begin
write(k^.data,'->');
k:=k^.link;
end;
END.
在本程序里,输出链表的过程就是一个链表的遍历。给出一个链表的头结点,依次输出后面每一个结点的内容,指针依次向后走的语句用K:=K↑.LINK 来实现。
例2 读入一批数据,遇负数时停止,将读入的正数组成先进先出的链表并输出。
分析:首先应定义指针类型,结点类型和指针变量,读入第一个值,建立首结点,读入第二个值,判断它是否大于零,若是,建立新结点。
PROGRAM fifo(input,output);
{建立先进先出链表}
TYPE
Point=^node;
Node=RECORD
Data:real;
Link:point
END;
VAR
head,last,next:point;
x:real;
BEGIN
{读入第一个值,建立首结点}
read(x);
write(x:6:1);
new(head);
head^.data:=x;
last:=head;
{读入第二个值}
read(x);
write(x:6:1);
WHILE x>=0 DO
BEGIN
{建立新结点}
new(next);
next^.data:=x; {链接到表尾}
last^.link:=next; {指针下移}
last:=next; {读入下一个值}
read(x);
write(x:6:1)
END;
Writeln; {表尾指针域置NIL}
Last^.link:=NIL; {输出链表}
Next:=head;
WHILE next<>NIL DO
BEGIN
Write(next^.data:6:1);
Next:=next^.link
END;
Writeln
END.
例3 读入一批数据,遇负数时停止,将读入的正数组成先进后出的链表并输出。
PROGRAM fifo(input,output);
{建立先进后出链表}
TYPE
point=^node;
node=RECORD
data:real;
link:point
END;
VAR
head,last,next:point;
x:real;
BEGIN
{初始准备}
next:=NIL;
read(x); {读入第一个数}
write(x:6:1);
WHILE x>=0 DO
BEGIN {建立一个新结点}
new(head);
head^.data:=x; {链接到表首}
head^.link:=next;{指针前移}
next:=head; {读入下一个数}
read(x);
write(x:6:1)
END;
writeln; {输出链表}
WHILE next<>NIL DO
BEGIN
write(next^.data:6:1);
next:=next^.link
END;
writeln
END.
2 在链表中插入结点
在一个已建好的链表中插入一个结点,这是一种常见算法。当我们找到插入点后,就断开原先的链接,将新结点插入进来。
(图T10.3)
如图所求示:要把P3的结点插入到P2之前,应该这样操作:
(1) P1,P2之间的链断开,改为P1指向P3。
P1↑.LINK:=P3;
(2) 将P2,P3连接起来:
P3↑.LINK:=P2;
于是,P3所指向的结点便插入进来了。
例4 插入一结点的过程
PROCEDURE insert(x:real;VAR head:point);
{插入一结点的过程}
VAR
q,last,next:point;
BEGIN
{建立新结点}
new(q);
q^.data:=x;
IF X<=head^.ata
THEN {插入前表}
BEGIN
q^.link:=head;
head:=q;
EDN
ELSE BEGIN {找出表中合适的位置}
Next:=head;
WHILE (x>next^.data) AND (next^.link<>NIL) DO
BEGIN
Last:=next;
Next:=next^.link
END;
IF x<=next^.data
THEN {插入中间表}
BEGIN
last^.link:=q;
q^.link:=next
END
ELSE {插入表尾}
BEGIN
next^.link:=q;
q^.link:=NIL
END
END
END;
例5 建立一个有序的整数链表,再将一任意整数插入进链表,使链表仍然有序。
PROGRAM e1(input,output);
TYPE point=^pp;
pp=record
data:integer;
link:point;
end;
VAR
p1,p2,p3,k:point;
BEGIN
{建立一个整数的链表,要求输入的整数依次是有序的,以数9999结束}
new(p1);
writeln('input data');
readln(p1^.data);
k:=p1;
repeat
new(p2);
writeln('input data');
readln(p2^.data);
p1^.link:=p2;
p1:=p2;
until p2^.data=9999;
p2^.link:=nil;{有序链表建立完毕}
writeln('input p3');
readln(p3^.data);
p1:=k;p2:=k;{P1,P2都指向表头}
{P2找到插入点后一个结点}
while p2^.data<p3^.data do
p2:=p2^.link;
{P1找到插入点以前的结点}
while p1^.link<>p2 do
p1:=p1^.link;
{将P3接入P1,P2之间}
p1^.link:=p3;
p3^.link:=p2;
{将整个插入后的链表依次打印出来}
repeat
write(k^.data,'->');
k:=k^.link;
until k^.data=9999;
write(k^.data);
END.
3 删除一个结点
要在一个链表中删去一个结点,首先在链表中找到该结点,将其前面的指针与该点断开,直接接到后面的结点,再用DISPOSE 命令将P3结点空间释放。如图,删除P3结点:
(图T10.4)
删除语句如下:
P1↑.LINK:=P3↑.LINK
DISPOSE(P3);
例6 删除结点的过程
PROCEDURE delete(x:real;VAR head;point;VAR deleted:Boolean);
{删除结点的过程}
VAR
Last,next:point;
BEGIN
{遍历表直到找到目标或到达表末}
next:=head;
WHILE(next^.data<>x)AND(next^.link<>DIL) DO
BEGIN
Last:=next;
Next:next^.link
END;
{如果目标文件找到,删除包含它的结点,设置deleted}
IF next^.data=x
THEN BEGIN
Deleted:=true;
IF next=head
THEN head:=head^.link
ELSE last^.link:=next^.link
END
ELSE deleted:=false
END;
例7 在一个有序链表中装有1到100共100个整数。要求任意输入100以内的一个整数,把它从链表中删除。
PROGRAM e1(input,output);
TYPE point=^pp;
pp=record
data:integer;
link:point;
end;
VAR
p1,p2,p3,k:point;
i:integer;
BEGIN
{建立一个1――100的整数的有序链表}
new(p1);
k:=p1;
p1^.data:=1;
for i:=2 to 100 do
begin
new(p2);
p2^.data:=i;
p1^.link:=p2;
p1:=p2;
end;
p2^.link:=nil;
{输入要删除的结点的DATA值}
new(p3);
writeln('input p3');
readln(p3^.data);
P1:=k;p2:=k;
{P2指针查找P3结点}
while p2^.data<p3^.data do
p2:=p2^.link;
{P1指针定位于P3之前}
while p1^.link<>p2 do
p1:=p1^.link;
p1^.link:=p2^.link;
dispose(p3);{将P3结点的空间释放}
{输出修改后的链表}
repeat
write(k^.data,'->');
k:=k^.link;
until k^.data=100;
write(k^.data);
END.
五年级上册解方程练… | 255433 |
九连环图解解法 | 226841 |
wifi万能钥匙破解的… | 177845 |
纸飞机Skyking(空… | 170787 |
小学语文知识大全(… | 152068 |
各种鱼钩鱼线绑法与… | 116926 |
课题研究的方法有哪些 | 113467 |
人教版pep小学英语… | 104518 |
小学语文知识大全(… | 96797 |
人教版pep小学英语… | 96109 |
小学数学五年级上册… | 93391 |
人教版pep小学英语… | 82565 |
小学语文知识大全(… | 80375 |
笔记本电脑如何关闭… | 79814 |
小学生六一搞笑小品… | 78875 |
不打结的红领巾系法… | 78044 |