第十三章动态数据类型

第十三章动态数据类型前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中，这些类型的变量一经说明，就在内存中占有固定的存储单元，直到该程序结束。程序设计中，使用静态数据结构可以解决不少实际问题，但也有不便之处。如建立一个大小未定的姓名表，随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型──指针类型。通过指针变量，可以在程序的执行过程中动态地建立变量，它的个数不再受限制，可方便地高效地增加或删除若干数据。一、指针的定义及操作（一）指针类型和指针变量在pascal中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说，指针变量指示某个存储单元。指针类型的格式为:＾基类型说明:①一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类型。基类型可以是除指针、文件外的所有类型。例如，下列说明：typepointer=^Integer;varp1,p2:pointer;定义了两个指针变量p1和p2，这两个指针可以指示一个整型存储单元(即p1、p2中存放的是某存储单元的地址，而该存储单元恰好能存放一个整型数据)。②和其它类型变量一样，也可以在var区直接定义指针型变量。例如：vara:^real;b:^boolean;又如：typeperson=recordname:string[20];sex:(male,female);age:1..100end;varpts:^person;③pascal规定所有类型都必须先定义后使用，但只有在定义指针类型时可以例外，如下列定义是合法的：typepointer=^rec;rec=recorda:integer;b:charend;（二）开辟和释放动态存储单元1、开辟动态存储单元在pascal中，指针变量的值一般是通过系统分配的，开辟一个动态存储单元必须调用标准过程new。new过程的调用的一般格式:New(指针变量)功能：开辟一个存储单元，此单元能存放的数据的类型正好是指针的基类型，并把此存储单元的地址赋给指针变量。说明：①这实际上是给指针变量赋初值的基本方法。例如，设有说明：varp:^Integer;这只定义了P是一个指示整型存储单元的指针变量，但这个单元尚未开辟，或者说P中尚未有值（某存储单元的首地址）。当程序中执行了语句new(p)才给ｐ赋值，即在内存中开辟（分配）一个整型变量存储单元，并把此单元的地址放在变量ｐ中。示意如下图：(a)编译时给(b)执行New(p)后(c)(b)的简略表示p分配空间生成新单元?表示值不定新单元的地址为XXXX内存单元示意图②一个指针变量只能存放一个地址。如再一次执行New(p)语句，将在内存中开辟另外一个新的整型变量存储单元，并把此新单元的地址放在ｐ中，从而丢失了原存储单元的地址。③当不再使用ｐ当前所指的存储单元时，可以通过标准过程Dispose释放该存储单元。⒉释放动态存储单元dispose语句的一般格式:dispose(指针变量)功能：释放指针所指向的存储单元，使指针变量的值无定义。（三）动态存储单元的引用在给一个指针变量赋以某存储单元的地址后，就可以使用这个存储单元。引用动态存储单元一般格式：＜指针变量＞＾说明：①在用New过程给指针变量开辟了一个它所指向的存储单元后，要使用此存储单元的唯一方法是利用该指针。②对动态存储单元所能进行的操作是该类型（指针的基类型）所允许的全部操作。例1设有下列说明:varp:^integer;i:integer;画出执行下列操作后的内存示意图：New(p);P^:=4;i:=p^;解:如下图所示。(a)编译时(b)执行New语句(c)执行P^:=4(d)执行i:=P^分配存储单元内存单元示意图（四）对指针变量的操作前已述及，对指针所指向的变量（如Ｐ＾）可以进行指针的基类型所允许的全部操作。对指针变量本身，除可用New、Dispose过程外，尚允许下列操作：⒈具有同一基类型的指针变量之间相互赋值例2设有下列说明与程序段:varp1,p2,p3:^integer;beginNew(P1);New(P2);New(P3);P1:=P2;P2:=P3;end;2、可以给指针变量赋nil值nil是PASCAL的关键字，它表示指针的值为空。例如，执行：p1:=ni1后，p1的值是有定义的，但p1不指向任何存储单元。3、可以对指针变量进行相等或不相等的比较运算在实际应用中，通常可以在指针变量之间，或指针变量与nil之间进行相等(＝)或不相等(＜＞＝的比较，比较的结果为布尔量。例3输入两个整数，按从小到大打印出来。分析：不用指针类型可以很方便地编程，但为了示例指针的用法，我们利用指针类型。定义一个过程swap用以交换两个指针的值。源程序如下：Typepointer=^integer;varp1,p2:pointer;procedureswap(varq1,q2:pointer);varq:pointer;beginq:=q1;q1:=q2;q2:=q;end;beginnew(p1);new(p2);write('Input2data:');readln(pq^,p2^);ifp1^p2^thenswap(p1,p2);writeln('Output2data:',p1^:4,p2^:4);end.二、链表结构设有一批整数(12，56，45，86，77，……，)，如何存放呢?当然我们可以选择以前学过的数组类型。但是，在使用数组前必须确定数组元素的个数。如果把数组定义得大了，就会有大量空闲存储单元，定义得小了，又会在运行中发生下标越界的错误，这是静态存储分配的局限性。利用本章介绍的指针类型可以构造一个简单而实用的动态存储分配结构――链表结构。下图是一个简单链表结构示意图：其中：①每个框表示链表的一个元素，称为结点。②框的顶部表示了该存储单元的地址(当然，这里的地址是假想的)。③每个结点包含两个域：一个域存放整数，称为数据域，另一个域存放下一个结点(称为该结点的后继结点，相应地，该结点为后继结点的前趋结点)的地址。④链表的第一个结点称为表头，最后一个结点表尾，称为指针域；⑤指向表头的指针head称为头指针(当head为nil时，称为空链表)，在这个指针变量中存放了表头的地址。⑥在表尾结点中，由指针域不指向任何结点，一般放入nil。（一）链表的基本结构由上图可以看出：①链表中的每个结点至少应该包含两个域；一是数据域，一是指针域。因此，每个结点都是一个记录类型，指针的基类型也正是这个记录类型。因此，head可以这样定义：typepointer=^rec；rec=recorddata：integer;next:pointer;end;varhead:pointer;②相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的，一旦失去了一个指针值，后面的元素将全部丢失。③与数组结构相比，使用链表结构时；可根据需要采用适当的操作步骤使链表加长或缩短，而使存储分配具有一定的灵活性。这是链表结构的优点。④与数组结构相比，数组元素的引用比较简单，直接用数组名[下标]即可，因为数组元素占用连续的存储单元，而引用链表元素的操作却比较复杂。（二）单向链表的基本操作上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表的基本操作，并假设类型说明如前所述。例6编写一个过程，将读入的一串整数存入链表，并统计整数的个数。分析：过程的输入为一串整数，这在执行部分用读语句完成。过程的输出有两个：一是链表的头指针，一是整数的个数，这两个输出可以用变量形参来实现。由于不知道整数的个数，我们用一个特殊的9999作为结束标记。过程如下：procedurecreat(varh:pointer;varn:integer);varp,q:pointer;x:integer;beginn:=0;h:=nil;read(x);whilex9999dobeginNew(p);n:=n+1;p^.data:=x;ifn=1thenh:=pelseq^.next:=p;q:=p;read(x)end;ifhnilthenq^.next:=nil;Dispose(p);end;例7编一过程打印链表head中的所有整数,5个一行。分析：设置一个工作指针P,从头结点顺次移到尾结点，每移一次打印一个数据。过程如下：procedureprint(head:pointer);varp:pointer;n:integer;beginn:=0;p:=head;whilepnildobeginwrite(p^.data:8);n:=n+1;ifnmod5=0thenwriteln;p:=p^.next;end;writeln;end;（三）链表结点的插入与删除链表由于使用指针来连接，因而提供了更多了灵活性，可以插入删除任何一个成分。设有如下定义：typepointer=^rec;rec=recorddata:integer;next:pointerend;varhead:pointer;⒈结点的插入如下图所示,要在P结点和Q结点之间插入一个结点m,其操作如下:只要作如下操作即可:New(m);read(m^.data);m^.next:=q;p^.next:=m;例8设链表head中的数据是按从小到大顺序存放的，在链表中插入一个数，使链表仍有序。分析：显然，应分两步：查找、插入。设ｐo指向要插入的结点，若仅知道ｐo应插在ｐ之前（作为ｐ的前趋结点）是无法插入的，应同时知道ｐ的前趋结点地址ｑ。当然，如果插在链表原头结点这前或原链表为空表或插在原尾结点之后，则插入时又必须作特殊处理。过程如下：procedureinserting(varhead:pointer;x:integer);varpo,p,q:pointer;beginnew(po);po^.data:=x;p:=head;ifhead=nil{原表为空表}thenbeginhead:=po;po^.next:=nil;endelsebeginwhile(p^.datax)and(p^.nextnil)dobeginq:=p;p:=p^.nextend;ifp^.data=x{不是插在原尾结点之后}thenbeginifhead=pthenhead:=poelseq^.next:=po;po^.next:=pendelsebeginpo^.next:=po;po^.next:=nilend;end;end;⒉结点的删除如下图所示，要在删除结点P的操作如下:要删除结点P,则只要将其前趋结点的指针域指向P的后继结点即可。q^.next:=p^.next;dispose(p);例9将链表head中值为X的第一个结点删除分析:有三种情况存在:头结点的值为X;除头结点外的某个结点值为X;无值为X的结点。为将前两种情况统一起来，我们在头结点之前添加一个值不为Ｘ的哨兵结点。算法分两步：查找、删除。过程如下：proceduredeleteing(varhead:pointer;x:integer);varp,q:pointer;beginNew(p);p^.data:=x-1;p^.next:=head;head:=p;{以上为添加哨兵结点}while(xp^.data)and(p^.nextnil)dobeginq:=p;p:=p^.nextend;ifx=p^.data{存在值为X的结点}thenq^.next:=p^.nextelsewriteln('NOtfound!');head:=head^.next{删除哨兵}end;（四）环形链表结构在单向链表中，表尾结点的指针为空。如果让表尾结点的指针域指向表头结点，则称为单向环形链表，简称单链环。如图所示。单链环示意图（五）双向链表结构单链表中，每个结点只有一个指向其后继结点的指针域。如果每个结点不仅有一个指向其后继结点的指针域，还有一个指向其前趋的指针域，则这种链表称为双向链表。如图所示。双向链表示意图可用如下定义一个数据