这是指针中的链表
链表
1 建立链表
链表是动态数据结构的一种基本形式。如果我们把指针所指的一个存贮单元叫做结点，那么链表就是把若干个结点链成了一串。我们把链表叫做动态数据结构，是因为链表中的结点可增可减，可多可少，可在中间任意一个位置插入和删除。
下面就是一个链表：
（图T10．2）
每个链表有两个域，一个是数据域，一个是指向下一个结点的指针域。最后一个结点的指针域为NIL，NIL表示空指针。
要定义一个链表，每个结点要定义成记录型，而且其中有一个域为指针。
TYPE
POINT=↑PP；
PP=RECORD
DATA：STRING[5]；
LINK：POINT；
END；
VAR P1，P2：POINT；
在这个定义中，定义了两个指针变量P1，P2。每个结点有两个域，一个是数据域，一个是指针域，数据域是字符串型。这种定义中，指针中有记录，记录中有指针，形成一种递归调用。
下面我们来看一下如何定义上图的链表：
有：P1，P2，P3，P4属于POINT类型。
（1）建立第一个结点
NEW（P1）；
P1↑.DATA:=D1;
(2) 建立第二个结点,并把它接在P1的后面
NEW(P2);
P2↑.DATA:=D2;
P1↑.LINK:=P2;
(3) 建立第三个结点,并把它接在P2的后面.
NEW(P3);
P3↑.DATA:=D3;
P2↑.LINK:=P3;
(4) 建立最后一个结点,并把它接在P3的后面.
NEW（P4）；
P4↑．DATA：＝D4；
P4↑．LINK：＝NIL；
P3↑．LINK：＝P4；
例1 建立一个有10个结点的链表，最后输出该链表。
P2前一个结点，K一直指向第一个结点。
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
{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;
type //开始定义类型
Point = ^Node; //定义point 为 node类型 的专属指针
Node = record //定义node为一个 记录类型
i: Integer; //node内部的变量和元素
L, R: Point
end;
简单来说,指针是一个变量,其储存的值是一个地址,是一类数据的储存地址.
type //类型定义
Point = ^Node; //^ （指针类型的符号）
Node = record // 该指针为记录类型
i: Integer; // 这里与数组一样
L, R: Point // 该指针的前趋 和 后继
end;
for example （约瑟夫问题）
type
node=^point;
point=record
num:Longint;
next:node;
end;
var
n, i:Longint;
p, q, h:node;
begin
writeln('please input the number of students:');
readln(n);
new(q); h := q;
for i := 1 to n do begin
q^.num := i;
p := q; new(q);
p^.next := q;
end;
p^.next := h;
i := 1; q := p; p := h;
while n <> 1 do begin
write(p^.num,' ',i);
if i=3 then begin
write(' out'); i := 1; dec(n);
q^.next := p^.next;
p := p^.next;
end else begin
inc(i);
q := p; p := p^.next;
end;
writeln;
end;
writeln('answer: ',p^.num);
end.
不常用指针，不过看你的这个结构使我想到读大一的时，上机考试随机抽带了一道30分的题。
“30个小朋友围成1圈，每人有一个号码，从1开始数“123123123...”，凡是数到3的就要出局，求出最后一个能留下的小朋友是几号。”
i是小朋友的号码，L指向他的上一位小朋友，R指向他的下一位小朋友。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024