《动态数据类型》由会员分享，可在线阅读，更多相关《动态数据类型（11页珍藏版）》请在金锄头文库上搜索。
1、第十三章 动态数据类型前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中，这些类型 的变量一经说明，就在内存中占有固定的存储单元，直到该程序结束。程序设计中，使用静态数据结构可以解决不少实际问题，但也有不便之处。如建立一个 大小未定的姓名表，随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型 指针类型。通过指针变量，可以在程序的执行过程中动态地建立变量，它的个数不再受限制， 可方便地高效地增加或删除若干数据。一、指针的定义及操作（一）指针类型和指针变量在 pascal 中,指针变量（也称动态变量）存放某个存储单元的地址；也就是说， 指针变量 指示某个存储单元。指针类型的
2、格式为：基类型说明：一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类 型。基类型可以是除指针、文件外的所有类型。例如，下列说明：type pointer二 Integer;var p1,p2：pointer;定义了两个指针变量P1和P2,这两个指针可以指示一个整型存储单元（即pl、p2中存放的是某存储 单元的地址，而该存储单元恰好能存放一个整型数据）。 和其它类型变量一样，也可以在var区直接定义指针型变量。例如：var a: real; b: boolean;又如： type person=recordname:string20; sex:（male,female）; a
3、ge:l.l00end;var pts: person; pascal规定所有类型都必须先定义后使用，但只有在定义指针类型时可以例外，如下 列定义是合法的：type pointer二 rec;rec=record a:integer; b:char end;（二）开辟和释放动态存储单元1、开辟动态存储单元在 pascal 中，指针变量的值一般是通过系统分配的，开辟一个动态存储单元必须调用标 准过程 new。new 过程的调用的一般格式:New（指针变量）功能：开辟一个存储单元，此单元能存放的数据的类型正好是指针的基类型，并把此存 储单元的地址赋给指针变量。说明：这实际上是给指针变量赋初值的基本
4、方法。例如，设有说明：var p:lnteger;这只定义了P是一个指示整型存储单元的指针变量，但这个单元尚未开辟，或者说P中尚未有值（某存储 单元的首地址）。当程序中执行了语句new（p）才给p赋值，即在内存中开辟（分配）一个整型变量存储单 元，并把此单元的地址放在变量P中。示意如下图：（a）编译时给（b）执行New（p）后 （c）（b）的简略表示p 分配空间生成新单元?表示值不定 新单元的地址为 XXXX 内存单元示意图 一个指针变量只能存放一个地址。如再一次执行New（p）语句，将在内存中开辟另外一个新的整型变 量存储单元，并把此新单元的地址放在P中，从而丢失了原存储单元的地址。 当不再
5、使用P当前所指的存储单元时，可以通过标准过程Dispose释放该存储单元。2. 释放动态存储单元dispose语句的一般格式：dispose（指针变量） 功能：释放指针所指向的存储单元，使指针变量的值无定义。（三）动态存储单元的引用在给一个指针变量赋以某存储单元的地址后，就可以使用这个存储单元。引用动态存储单元一般格式：指针变量说明：在用New过程给指针变量开辟了一个它所指向的存储单元后，要使用此存储单元的唯一方法 是利用该指针。对动态存储单元所能进行的操作是该类型（指针的基类型）所允许的全部操作。例 1 设有下列说明:var p: integer; i:integer;画出执行下列操作后的内
6、存示意图：New（p）; P:=4;i:=p;解: 如下图所示。(c)执行 P:=4(d) 执行 i:=P(a)编译时(b)执行New语句分配存储内存单元示意图单元四)对指针变量的操作前已述及，对指针所指向的变量(如P)可以进行指针的基类型所允许的全部操作。对指针变量本身，除可用 New、Dispose 过程外，尚允许下列操作：1. 具有同一基类型的指针变量之间相互赋值例 2 设有下列说明与程序段:var p1,p2,p3: integer;beginNew(P1) ; New(P2); New(P3);P1:=P2; P2:=P3;end;2、可以给指针变量赋 nil 值nil 是 PASC
7、AL 的关键字，它表示指针的值为空。例如，执行：p1：=ni1后，pl的值是有定义的，但pl不指向任何存储单元。3、可以对指针变量进行相等或不相等的比较运算在实际应用中，通常可以在指针变量之间，或指针变量与nil之间进行相等(=)或不相等( =的比 较，比较的结果为布尔量。例 3 输入两个整数，按从小到大打印出来。分析：不用指针类型可以很方便地编程，但为了示例指针的用法，我们利用指针类型。定义一个过程 swap 用以交换两个指针的值。源程序如下：Type pointer二 integer;var pl,p2:pointer;procedure swap(var ql,q2:pointer);v
8、ar q:pointer;beginq:=ql;ql:=q2;q2:=q;end;beginnew(p1);new(p2);write(Input 2 data:);readln(pq,p2);if pp2 then swap(pl,p2);writeln(Output 2 data:,p：4,p2:4);end.二、链表结构设有一批整数(12, 56, 45, 86, 77,),如何存放呢？当然我们可以选择以前学过的数组类型。 但是，在使用数组前必须确定数组元素的个数。如果把数组定义得大了，就会有大量空闲存储单元，定义 得小了,又会在运行中发生下标越界的错误,这是静态存储分配的局限性。利用本
9、章介绍的指针类型可以构造一个简单而实用的动态存储分配结构链表结构。其中：每个框表示链表的一个兀素，称为结点。 框的顶部表示了该存储单元的地址(当然，这里的地址是假想的)。 每个结点包含两个域：一个域存放整数，称为数据域，另一个域存放下一个结点(称为该结点的后继 结点,相应地,该结点为后继结点的前趋结点)的地址。 链表的第一个结点称为表头，最后一个结点表尾，称为指针域； 指向表头的指针head称为头指针(当head为nil时，称为空链表)，在这个指针变量中存放了表头 的地址。 在表尾结点中，由指针域不指向任何结点，一般放入nil。(一) 链表的基本结构由上图可以看出： 链表中的每个结点至少应该包
10、含两个域；一是数据域，一是指针域。因此，每个结点都是一个记录 类型，指针的基类型也正是这个记录类型。因此，head可以这样定义：type pointer= rec；rec=recorddata： integer; next:pointer;end;var head:pointer; 相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的，一旦失去了一个指针值，后 面的元素将全部丢失。 与数组结构相比，使用链表结构时；可根据需要采用适当的操作步骤使链表加长或缩短，而使存储 分配具有一定的灵活性。这是链表结构的优点。 与数组结构相比，数组元素的引用比较简单，直接用数组名下标即可，因为数组元素
11、占用连续 的存储单元，而引用链表元素的操作却比较复杂。(二) 单向链表的基本操作上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表的基本操作，并假设类型说 明如前所述。例 6 编写一个过程，将读入的一串整数存入链表， 并统计整数的个数。分析：过程的输入为一串整数，这在执行部分用读语句完成。过程的输出有两个：一是链表的头指针 一是整数的个数，这两个输出可以用变量形参来实现。由于不知道整数的个数，我们用一个特殊的 9999 作为结束标记。过程如下：procedure creat(var h:pointer;var n:integer);var p,q:pointer;x:intege
12、r;beginn:=0;h:=nil; read(x);while x9999 dobeginNew(p);n:=n+1;p .data:二x; if n=1 then h:=p else q .next:=p;q:=p;read(x)end;if hnil then q.next:二nil;Dispose(p);end;例7编一过程打印链表head中的所有整数,5个一行。分析：设置一个工作指针P,从头结点顺次移到尾结点，每移一次打印一个数据。过程如下：procedure print(head:pointer);var p:pointer; n:integer;begin n:=0;p:=he
13、ad; while pnil dobeginwrite(pdata:8);n:=n+l;if n mod 5=0 then writeln;p:=p .next;end;writeln;end;(三) 链表结点的插入与删除链表由于使用指针来连接，因而提供了更多了灵活性，可以插入删除任何一个成分 设有如下定义：type pointer二 rec;rec=recorddata:integer;next:pointerend;var head:pointer;1 结点的插入只要作如下操作即可:New(m);read(m data);m next:=q;p next:=m;例 8 设链表 head 中
14、的数据是按从小到大顺序存放的，在链表中插入一个数，使链表仍有序。分析：显然，应分两步：查找、插入。设po指向要插入的结点，若仅知道po应插在P之前(作为P 的前趋结点)是无法插入的，应同时知道P的前趋结点地址q。当然，如果插在链表原头结点这前或原链表为空表或插在原尾结点之后，则插入时又必须作特殊处理过程如下：procedure inserting(var head:pointer;x:integer);var po,p,q:pointer;beginnew(po);po data:二x;p:=head;if head=nil原表为空表then beginhead:二po;po next:二ni
15、l;endelse begin while (p datax)and(p .nextnil)do beginq:=p;p:=p.nextend;if p.data=x不是插在原尾结点之后 then beginif head=p then head:=poelse q next:=po;po next:二pendelse beginpo next:二po;ponext:二nilend;end;end;2.结点的删除如下图所示，要在删除结点 P 的操作如下:要删除结点P,则只要将其前趋结点的指针域指向P的后继结点即可。q next:=p next;dispose(p);例9将链表head中值为X的第一个结点删除分析：有三种情况存在:头结点的
