用 户:

密 码:

       科组介绍 在线课堂 竞赛专栏 图文资讯 教学资源 教学设计 学生作品 外部链接

        您现在正在浏览: 首页 » 信息技术科 » 在线课堂 » 正文
第十三章 动态数据类型
发布时间: 2012-10-02 21:20:41   作者:本站编辑   来源: 本站原创   浏览次数:   我要评论()

前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中,这些类型

的变量一经说明,就在内存中占有固定的存储单元,直到该程序结束。

  程序设计中,使用静态数据结构可以解决不少实际问题,但也有不便之处。如建立一个

大小未定的姓名表,随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型──

指针类型。通过指针变量,可以在程序的执行过程中动态地建立变量,它的个数不再受限制,

可方便地高效地增加或删除若干数据。 

一、指针的定义及操作

  (一)指针类型和指针变量

  在pascal,指针变量(也称动态变量)存放某个存储单元的地址;也就是说, 指针变量

指示某个存储单元。

  指针类型的格式为:^基类型

  说明①一个指针只能指示某一种类型数据的存储单元,这种数据类型就是指针的基类

型。基类型可以是除指针、文件外的所有类型。例如,下列说明:

  type pointer=^Integer;

        var p1,p2:pointer;

  定义了两个指针变量p1p2,这两个指针可以指示一个整型存储单元(p1p2 中存放的是某存储单元的地址,而该存储单元恰好能存放一个整型数据)

  ②和其它类型变量一样,也可以在var区直接定义指针型变量。

  例如:var a:^real; b:^boolean;

  又如:type person=record

           name:string[20];

           sex:(male,female);

           age:1..100

          end;

     var pts:^person;

  ③pascal规定所有类型都必须先定义后使用,但只有在定义指针类型时可以例外,如下

列定义是合法的:

  type pointer=^rec;

      rec=record

        a:integer;

        b:char

       end;

  (二)开辟和释放动态存储单元

  1、开辟动态存储单元

  在pascal中,指针变量的值一般是通过系统分配的,开辟一个动态存储单元必须调用标 

准过程new

  new过程的调用的一般格式:

  New(指针变量)

  功能:开辟一个存储单元,此单元能存放的数据的类型正好是指针的基类型,并把此存

储单元的地址赋给指针变量。

  说明:①这实际上是给指针变量赋初值的基本方法。例如,设有说明:var p:^Integer;

这只定义了P是一个指示整型存储单元的指针变量,但这个单元尚未开辟,或者说P中尚未有值(某存储单元的首地址)。当程序中执行了语句new(p)才给p赋值,即在内存中开辟(分配)一个整型变量存储单元,并把此单元的地址放在变量p中。示意如下图:

           

    (a)编译时给  (b)执行New(p)后  (c)(b)的简略表示

   p分配空间    生成新单元

  ?表示值不定  新单元的地址为XXXX

          内存单元示意图

  ②一个指针变量只能存放一个地址。如再一次执行New(p)语句,将在内存中开辟另外一个新的整型变量存储单元,并把此新单元的地址放在p中,从而丢失了原存储单元的地址。

  ③当不再使用p当前所指的存储单元时,可以通过标准过程Dispose释放该存储单元。

  ⒉释放动态存储单元

  dispose语句的一般格式:dispose(指针变量)

  功能:释放指针所指向的存储单元,使指针变量的值无定义。

  (三)动态存储单元的引用

  在给一个指针变量赋以某存储单元的地址后,就可以使用这个存储单元。

  引用动态存储单元一般格式:<指针变量>^

  说明:①在用New过程给指针变量开辟了一个它所指向的存储单元后,要使用此存储单元的唯一方法是利用该指针。

  ②对动态存储单元所能进行的操作是该类型(指针的基类型)所允许的全部操作。

  例设有下列说明:

  var p:^integer; i:integer;

  画出执行下列操作后的内存示意图:

    New(p); P^:=4;i:=p^;

  解如下图所示。

   

   (a)编译时 (b)执行New语句   (c)执行P^:=4   (d)执行i:=P^

    分配存储 

     单元

                 内存单元示意图

  (四)对指针变量的操作

  前已述及,对指针所指向的变量(如P^)可以进行指针的基类型所允许的 全部操作。

对指针变量本身,除可用NewDispose过程外,尚允许下列操作:

  ⒈具有同一基类型的指针变量之间相互赋值

  例设有下列说明与程序段:

  var p1,p2,p3:^integer;

  begin

   New(P1) ; New(P2); New(P3);

   P1:=P2; P2:=P3;

  end;

  2、可以给指针变量赋nil

  nilPASCAL的关键字,它表示指针的值为""。例如,执行:

  p1:=ni1后,p1的值是有定义的,但p1不指向任何存储单元。

  3、可以对指针变量进行相等或不相等的比较运算

  在实际应用中,通常可以在指针变量之间,或指针变量与nil之间进行相等()或不相等(<>=的比较,比较的结果为布尔量。

  例输入两个整数,按从小到大打印出来。

  分析:不用指针类型可以很方便地编程,但为了示例指针的用法,我们利用指针类型。定义一个过程swap用以交换两个指针的值。

  源程序如下: 

  Type pointer=^integer;

  var p1,p2:pointer;

  procedure swap(var q1,q2:pointer);

   var q:pointer;

   begin

    q:=q1;

    q1:=q2;

    q2:=q;

   end;

  begin

   new(p1);new(p2);

   write('Input 2 data:');readln(pq^,p2^);

   if p1^>p2^ then swap(p1,p2);

   writeln('Output 2 data:',p1^:4,p2^:4);

  end. 

  二、链表结构

  设有一批整数(1256458677,……,),如何存放呢当然我们可以选择以前学过的数组类型。但是,在使用数组前必须确定数组元素的个数。如果把数组定义得大了,就会有大量空闲存储单元,定义得小了,又会在运行中发生下标越界的错误,这是静态存储分配的局限性。

  利用本章介绍的指针类型可以构造一个简单而实用的动态存储分配结构――链表结构。

  下图是一个简单链表结构示意图:

  

  其中:①每个框表示链表的一个元素,称为结点。

  ②框的顶部表示了该存储单元的地址(当然,这里的地址是假想的)

  ③每个结点包含两个域:一个域存放整数,称为数据域,另一个域存放下一个结点(称为该结点的后继结点,相应地,该结点为后继结点的前趋结点)的地址。

  ④链表的第一个结点称为表头,最后一个结点表尾,称为指针域;

  ⑤指向表头的指针head称为头指针(headnil时,称为空链表),在这个指针变量中 存放了表头的地址。

  ⑥在表尾结点中,由指针域不指向任何结点,一般放入nil

  (一)链表的基本结构

  由上图可以看出:

  ①链表中的每个结点至少应该包含两个域;一是数据域,一是指针域。因此,每个结点都是一个记录类型,指针的基类型也正是这个记录类型。因此,head可以这样定义:

  type pointer=^ rec

   rec=record

      datainteger;

      next:pointer;

     end;

   var head:pointer;

  ②相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的,一旦失去了一个指针值,后面的元素将全部丢失。 

  ③与数组结构相比,使用链表结构时;可根据需要采用适当的操作步骤使链表加长或缩 短,而使存储分配具有一定的灵活性。这是链表结构的优点。

  ④与数组结构相比,数组元素的引用比较简单,直接用"数组名[下标]"即可,因为数组元素占用连续的存储单元,而引用链表元素的操作却比较复杂。

  (二)单向链表的基本操作

  上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表的基本操作,并假设类型说明如前所述。

  例编写一个过程,将读入的一串整数存入链表, 并统计整数的个数。

  分析:过程的输入为一串整数,这在执行部分用读语句完成。过程的输出有两个:一是链表的头指针,一是整数的个数,这两个输出可以用变量形参来实现。 

  由于不知道整数的个数,我们用一个特殊的9999作为结束标记。

  过程如下:

  procedure creat(var h:pointer;var n:integer);

  var p,q:pointer;x:integer;

  begin

    n:=0;h:=nil; read(x);

    while x<>9999 do

    begin

     New(p);

     n:=n+1;p^.data:=x;

     if n=1 then h:=p

     else q^.next:=p;

     q:=p;read(x)

    end;

    if h<>nil then q^.next:=nil;

    Dispose(p);

  end;

  例编一过程打印链表head中的所有整数,5个一行。

  分析:设置一个工作指针P,从头结点顺次移到尾结点,每移一次打印一个数据。 

  过程如下:

  procedure print(head:pointer);

  var p:pointer; n:integer;

  begin

   n:=0;p:=head;

   while p<>nil do

    begin

     write(p^.data:8);n:=n+1;

     if n mod 5=0 then writeln;

     p:=p^.next;

    end;

   writeln;

  end;

  (三)链表结点的插入与删除

  链表由于使用指针来连接,因而提供了更多了灵活性,可以插入删除任何一个成分。

  设有如下定义:

  type pointer=^rec;

  rec=record

    data:integer;

    next:pointer

   end;

  var head:pointer;

  ⒈结点的插入

  如下图所示,要在P结点和Q结点之间插入一个结点m,其操作如下:

   

  只要作如下操作即可:

   New(m);

   read(m^.data);

   m^.next:=q;

   p^.next:=m; 

  例设链表head中的数据是按从小到大顺序存放的,在链表中插入一个数,使链表仍有序。

  分析:显然,应分两步:查找、插入。设po指向要插入的结点,若仅知道po应插在p之前(作为p的前趋结点)是无法插入的,应同时知道p的前趋结点地址q。

  当然,如果插在链表原头结点这前或原链表为空表或插在原尾结点之后,则插入时又必须作特殊处理。

  过程如下:

  procedure inserting(var head:pointer;x:integer);

  var po,p,q:pointer;

  begin

   new(po);po^.data:=x;

   p:=head;

   if head=nil{原表为空表}

    then begin

     head:=po;po^.next:=nil;

    end

   else begin

    while (p^.data<x)and(p^.next<>nil)do

    begin

     q:=p;p:=p^.next

    end;

    if p^.data>=x{不是插在原尾结点之后}

    then begin

      if head=p then head:=po

      else q^.next:=po;

      po^.next:=p

     end

   else begin

      po^.next:=po;

      po^.next:=nil

    end;

   end;

  end;

  ⒉结点的删除

  如下图所示,要在删除结点P的操作如下:

  

  要删除结点P,则只要将其前趋结点的指针域指向的后继结点即可。

  q^.next:=p^.next;

  dispose(p);

  例将链表head中值为X的第一个结点删除

  分析有三种情况存在:头结点的值为X; 除头结点外的某个结点值为X;无值为X的结点。为将前两种情况统一起来, 我们在头结点之前添加一个值不为X的哨兵结点。

  算法分两步:查找、删除。

  过程如下:

  procedure deleteing(var head:pointer;x:integer);

  var p,q:pointer;

  begin

   New(p);p^.data:=x-1;p^.next:=head;

   head:=p;{以上为添加哨兵结点}

   while(x<>p^.data)and(p^.next<>nil)do

   begin

    q:=p;

    p:=p^.next

   end;

   if x=p^.data{存在值为X的结点}

   then q^.next:=p^.next

   else writeln('NOt found!');

   head:=head^.next{删除哨兵}

  end;

  (四)环形链表结构

  在单向链表中,表尾结点的指针为空。如果让表尾结点的指针域指向表头结点,则称为单向环形链表,简称单链环。如图所示。

    

                单链环示意图

  (五)双向链表结构

  单链表中,每个结点只有一个指向其后继结点的指针域。如果每个结点不仅有一个指向其后继结点的指针域,还有一个指向其前趋的指针域,则这种链表称为双向链表。如图所示。

     

           双向链表示意图

  可用如下定义一个数据域为整型的双向链表:

    type pointer=^node;

      node=record

         prev:pointer;

         data:integer;

         next:pointer;

        end;

  对双向链表的插入、删除特别方便。与单向链环相似,我们还可定义双向链环。

  三、综合例析

  例10 读入一串以""为结束标志的字符,统计每个字符出现的次数。

  分析:设置一个链表存放,每读入一个字符,就从链表的头结点向后扫描链表,如果在链表中此字符已存在,则其频率加1, 否则将该字符的结点作为链表的新头结点,相应频率为1

  源程序如下:

  program ex11_10;

  type ref=^letters;

     letters=record

         key:char;

         count:integer;

         next:ref;

        end;

   var k:char;

    sentinel,head:ref;

   procedure search(x:char);

   var w:ref;

   begin

    w:=head;

    sentinel^.key:=x;

    while w^.key<>x do w:=w^.next;

    if w<>sentinel

    then w^.count:=w^.count+1

    else begin

        w:=head;new(head);

        with head^ do

         begin

           key:=x;count:=1;next:=w;

       end

  end;

  end;{of search}

  procedure printlist(w:ref);

   begin

    while w<>sentinel do

     begin

      writeln(w^.key:2,w^.count:10);

      w:=w^.next;

     end;

   end;{of printlist}

  begin{main program}

   new(sentine);

   with sentinel^ do

    begin

     key:='#';count:=0;next:=nil;

    end;

   head:=sentinel;

   read(k);

   while k<>'#' do

    begin

     search(k);read(k);

    end;

   printlist(head);

  end.

  例11 用链表重写筛法求2100之间所有素数程序。 

  源程序如下:

  program ex11_12;

   uses crt;

   type link=^code;

      code=record

         key:integer;

         next:link;

        end;

   var head:link;

   procedure printlist(h:link);{打印链表h}

    var p:link;

    begin

     p:=h;

     while p<>nil do

      begin

       write(p^.key,'-->');

       p:=p^.next;

      end;

    end;

   procedure buildlink;{建立链表}

    var p,q:link;

    i:integer;

    begin

     new(head);

     head^.key:=2;

     p:=head;

     for i:=3 to 100 do

      begin

       new(q);

       q^.key:=i;

       q^.next:=nil;

       p^.next:=q;

       p:=q;

      end;

    end;

   procedure prime;{筛法将找到的素数的倍数从链表中删除}

    var h,p,q:link;

    begin

     h:=head;

     while h<>nil do

      begin

       p:=h;q:=p^.next;

       while q<>nil do

        if (q^.key mod h^.key=0) then

         begin

          p^.next:=q^.next;

          dispose(q);

          q:=p^.next;

         end

        else begin

            p:=q;

            q:=q^.next;

           end;

       h:=h^.next;

      end;

    end;

   begin{main program}

     clrscr;

     buildlink;

     printlist(head);

     writeln;

     prime;

     printlist(head);

    end.

                    练习

  1、围绕着山顶有10个洞,一只兔子和一只狐狸各住一个洞,狐狸总想吃掉兔子。一天兔子对狐狸说,你想吃我有一个条件,你先把洞编号1到10。你从第10号洞出发,先到第1号洞找我,第二次隔一个洞找我,第三次隔两个洞找我,以后依次类推,次数不限。若能找到我,你就可以饱餐一顿,在没找到我之前不能停止。狐狸一想只有10个洞,寻找的次数又不限,哪有找不到的道理,就答应了条件。结果就是没找着。

  利用单链环编程,假定狐狸找了1000次,兔子躲在哪个洞里才安全。

  2、某医院病房的订位管理中, 将病人的记录按姓名的字母顺序排成一个链表。试编写程序,从键盘上输入下列字母,就可对病员记录进行管理:

  (1)i───新病人入院(插入一个病员记录)。

  (2)d───病人出院(删除一个病员记录,并显示该记录)。

  (3)s───查询某病员记录(显示该记录或"未找到")。

  (4)q───在屏幕上列出所有的病员记录并结束程序。

  3、编写一个简单的大学生新生入校登记表处理程序。



 
 

中学教学资源网 吉林教育信息网 教育资源网 E度网-中考,高考信息 人教网 中国园丁网 中国教育信息网 动感教育网

设为首页 - 加入收藏 - 管理登录
广东实验中学 版权所有 技术支持:协跃科技 粤ICP备05008850号
Copyright (©) 2012 www.gdsyzx.edu.cn All Rights Reserved