第五章第五节指针类型与动态数据结构

第五节指针类型与动态数据结构前面所学的变量都具有共同的特点：系统依据程序说明部分获得变量名和类型信息，即为变量分配对应大小的存储空间，在程序执行过程中，各变量对应的存储空间始终存在且保持不变，这些变量均称为静态变量。与静态变量对应的是动态变量，在程序执行过程中可以动态产生或撤消，所使用的存储空间也随之动态地分配或回收。为了使用动态变量。PASCAL系统提供了指针类型，用指针变量（静态变量）来指示动态变量（存储地址变量）。下面介绍如何利用指针建立动态数据结构。[例5.19]分别用简单变量和指针变量交换两个变量的值。解：设两个变量a,b的值分别为5,8(1)用简单变量交换：ProgramExam519;consta=5;b=8;{常量}varc:integer;beginc:=a;a:=b;b:=c;{用简单变量交换}writeln(’a=’:8,a,’b=’:8,b);readlnend.(2)用指针变量交换：ProgramExam519_1;typepon=^integer;{pon为指针类型}vara,b,c:pon;{a,b,c为指针变量}beginnew(a);new(b);new(c);{开辟动态存储单元}a^:=5;b^:=8;{给a,b指向的存储单元赋值}c:=a;a:=b;b:=c;{交换存储单元的指针}writeln('a=':8,a^,‘b=':8,b^);{输出a,b所指单元的值}readlnEnd.第(1)种方法，直接采用变量赋值进行交换，（实际上给各存储单元重新赋值）其过程如下图所示：555558888aaabbbccc①②③①将ac②将ba③将cb(图中表示赋值）第(2)种方法，对各存储单元所保存的值并不改变，只是交换了指向这些单元的存储地址（指针值），可以简略地用如下图示说明：Type指针类型名=^基类型；Var指针变量名:^基类型；New（指针变量）;Dispose（指针变量）；指针变量名^555888aaabbbccc①②③(图中“—→”表示指向存储单元)指针类型的指针变量a,b存有各指向单元的地址值，将指针交换赋值步骤为：①将c:=a(让c具有a的指针值);②将a:=b(让a具有b的指针值);③将b:=c(让b具有c的指针值);最后输出a,b所指向存储单元(a^和b^)的值，此时的a指向了存储整数8的单元（即a^=8），b指向了存储整数5的单元（即b^=5）。存储单元的值没有重新赋值，只是存放指针值的变量交换了指针值。程序Exam519_1Typepon=^integer;是定义指针类型，一般格式为：基类型就是指针所指向的数据元素的数据类型。也可以将类型说明合并在变量说明中直接定义说明：例如Exam519_1中类型说明与变量可以合并说明为：Vara,b,c:^integer;{与程序中分开说明的作用相同}定义了指针变量的类型之后，必须调用New过程开辟存储单元，调用格式如下：如果不再需要指针变量当前所指向的存储单元，可调用Dispose过程释放所占用的存储单元，Dispose和New的作用正好相反，其格式为：指针所指向的存储单元用如下形式表示：程序中的a^表示指针变量a所指向的存储单元，与指针变量的关系如下图所示：在程序中对所指存储单元（为a^）可以视作简单变量进行赋值计算和输出。如：a^:=5[例5.20]利用指针对数组元素值进行排序。解：①定义一个各元素为指针类型的数组a:②定义一个交换指针值的过程(swap)；③定义一个打印过程(print)；④定义过程(int)将数组b的值赋给a数组各元素所指向的各存储单元。⑤过程pixu用交换指针值的方式，按a数组所指向的存储单元内容值从小到大地调整各元素指针值，实现“指针”排序；⑥按顺序打印a数组各元素指向单元的值(a[i]^)。ProgramExam520;constn=8;b:array[1..n]ofinteger=(44,46,98,86,36,48,79,71);typepon=^integer;vara:array[1..n]ofpon;Procedureswap(varp1,p2:pon);{交换指针}varp:pon;beginp:=p1;p1:=p2;p2:=paa^指针单元end;Procedureprint;{打印数组各元素指向单元(a[i]^)的值}vari:integer;beginfori:=1tondowrite(a[i]^:6);writeln;writeln;end;Procedureint;{将数组b的值赋给a数组各元素所指向的存储单元}vari:integer;beginfori:=1tondobeginnew(a[i]);a[i]^:=b[i];end;print;end;Procedurepixu;{排序}vari,j,k:integer;beginfori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]^a[k]^thenk:=j;swap(a[k],a[i])endend;Beginint;pixu;print;readlnEnd.[例5.21]有m只猴子要选猴王，选举办法如下：所有猴子按1..m编号围坐成圆圈，从第一号开始按顺序1,2,..,n连续报数，凡报n号的退出到圈外。如此循环报数，直到圈上只剩下一只猴子即当选为王。用指针（环形链表）编程。解：①让指针pon指向的单元为记录类型，记录内容含有两个域：编号变量链指针变量②用过程crea建立环形链；③用过程king进行报数处理：每报数一次t计数累加一次，当所报次数能被n整除，就删去该指针指向的记录，将前一个记录的链指针指向下一个记录。删去的指向单元（记录）应释放。直到链指针所指向的单元是同一单元，就说明只剩下一个记录。④打印指向单元记录中编号域（num)的值。编号链123m...programExam521;typepon=^rec;｛指向rec类型｝rec=record｛rec为记录类型｝num:byte;｛域名num为字节类型｝nxt:pon｛域名nxt为pon类型｝end;varhd:pon;m,n:byte;procedurecrea;{建立环形链}vars,p:pon;i:byte;beginnew(s);hd:=s;s^.num:=1;p:=s;fori:=2tondobeginnew(s);s^.num:=i;p^.nxt:=s;p:=send;p^.nxt:=hdend;procedureking;{报数处理}varp,q:pon;i,t:byte;beginp:=hd;t:=0;q:=p;repeatp:=q^.nxt;inc(t);ift=nthenbeginq^.nxt:=p^.nxt;dispose(p);t:=0endelseq:=puntilp=p^.nxt;hd:=pend;beginwrite('m,n=');readln(m,n);｛输入m只猴，报数到n号｝crea;king;writeln('thenkingis:',hd^.num);readlnend.习题5.51.请将下列八个国家的国名按英文字典顺序排列输出。China(中国)Japan(日本)Cancda(加拿大)Korea(朝鲜)England(英格兰)France(法兰西)American(美国)India(印度)2.某医院里一些刚生下来的婴儿，都还没有取名字，全都统一用婴儿服包装，很难区分是谁的小孩。所以必须建立卡片档案，包含内容有编号、性别、父母姓名、床号。实际婴儿数是变动的，有的到期了，家长要抱回家，要从卡片上注销；新的婴儿出生，要增加卡片，请编程用计算机处理动态管理婴儿的情况。