您现在的位置:小学生自学网>> 信息>> 学习电脑

4链表

作者: 来源: 发布时间:2009年01月14日 点击数:
 
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<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.

上一篇:3栈

下一篇:5队列