pascal指针与链表.ppt

第八章　指针与链表 指针的定义及操作 链表结构 双向链表 循环链表 循环链表的应用举例 【上机练习】 请维护编者版权，请勿将课件在网络上传播。 福建省长乐一中 董永建 浙江省温州中学 舒春平 2009年9月 * * 前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中，这些类型的变量一经说明，就在内存中占有固定的存储单元，直到该程序结束。 程序设计中，使用静态数据结构可以解决不少实际问题，但也有不便之处。如建立一个大小未定的姓名表，随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型──指针类型。通过指针变量，可以在程序的执行过程中动态地建立变量，它的个数不再受限制，可方便高效地增加或删除若干数据，这比修改一个记录数组更加方便。 （1）指针类型和指针变量 　　在Pascal中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说， 指针变量指示某个存储单元。 　　指针类型的格式为： ＾基类型 说明： ① 一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类型。基类型可以是除指针、文件外的所有类型。例如，下列说明： type pointer=^integer; var p1,p2 : pointer; 定义了两个指针变量p1和p2，这两个指针可以指示一个整型存储单元( 即p1、p2 中存放的是某存储单元的地址，而该存储单元恰好能存放一个整型数据 )。 ② 和其它类型变量一样，也可以在var区直接定义指针型变量。 例如：var a : ^real; b : ^boolean; 又如：type person=record 　　　　　　　　　　　 name : string[20]; 　　　　　　　　　 　　sex : (maLe,femaLe); 　　　　　　　　　 　　age : 1..100 　　　　　　　　 　end; 　　　 var point : ^person; ③ Pascal规定所有类型都必须先定义后使用，但只有在定义指针类型时可以例外，如下列定义是合法的： 　type pointer=^rec; //允许rec类型后定义 　　　　　　rec=record 　　　　　　　　 a : integer; 　　　　　　　　 b : char 　　　　　　　 end; （2）开辟和释放动态存储单元 ① 开辟动态存储单元 在Pascal中，指针变量的值一般是通过系统分配的，开辟一个动态存储单元必须调用标准过程new。 new过程调用的一般格式： new(指针变量) 功能：开辟一个存储单元，此单元能存放的数据的类型正好是指针的基类型，并把此存储单元的地址赋给指针变量。 说明：1) 这实际上是给指针变量赋初值的基本方法。例如，设有说明：var p : ^integer; 这只定义了P是一个指示整型存储单元的指针变量，但这个单元尚未开辟，或者说P中尚未有值（某存储单元的首地址）。当程序中执行了语句new(p)才给ｐ赋值，即在内存中开辟（分配）一个整型变量存储单元，并把此单元的地址放在变量ｐ中。示意如下图： ? ? XXXX ? P P P (a)编译时给P分配空间，？表示值不定 (b)执行new(p)后生成新单元，新单元地址为XXXX (c)(b)的简略表示 2) 一个指针变量只能存放一个地址。如再一次执行New(p)语句，将在内存中开辟另外一个新的整型变量存储单元，并把此新单元的地址放在ｐ中，从而丢失了原存储单元的地址。 3) 当不再使用ｐ当前所指的存储单元时，可以通过标准过程Dispose释放该存储单元。 ② 释放动态存储单元 dispose语句的一般格式：dispose(指针变量) 功能：释放指针所指向的存储单元，使指针变量的值无定义。例如： new(p); dispose(p); （3）动态存储单元的引用 在给一个指针变量赋以某存储单元的地址后，就可以使用这个存储单元。 引用动态存储单元一般格式：＜指针变量＞＾ 说明： ①在用New过程给指针变量开辟了一个它所指向的存储单元后，要使用此存储单元的唯一方法是利用该指针。 ②对动态存储单元所能进行的操作是