链表

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一直指向第一个结点。