2022年指针类型与动态数据结构 .pdf

《2022年指针类型与动态数据结构 .pdf》由会员分享，可在线阅读，更多相关《2022年指针类型与动态数据结构 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五节指针类型与动态数据结构前面所学的变量都具有共同的特点：系统依据程序说明部分获得变量名和类型信息，即为变量分配对应大小的存储空间，在程序执行过程中，各变量对应的存储空间始终存在且保持不变，这些变量均称为静态变量。与静态变量对应的是动态变量，在程序执行过程中可以动态产生或撤消，所使用的存储空间也随之动态地分配或回收。为了使用动态变量。PASCAL系统提供了指针类型，用指针变量（静态变量）来指示动态变量（存储地址变量）。下面介绍如何利用指针建立动态数据结构。 例 5. 19 分别用简单变量和指针变量交换两个变量的值。解：设两个变量a,b 的值分别为5, 8(1) 用简单变量交换：Program

2、 Exam519; const a=5; b=8 ; 常量 var c: integer; begin c: =a; a: =b; b: =c; 用简单变量交换 writeln( a= : 8, a, b= : 8, b ) ; readln end .(2) 用指针变量交换：Program Exam519_1; type pon= integer; pon为指针类型 var a, b, c: pon; a, b, c 为指针变量 begin new(a ); new(b ) ; new(c ) ; 开辟动态存储单元 a : =5; b : =8; 给 a, b 指向的存储单元赋值 c: =a

3、; a: =b; b: =c; 交换存储单元的指针 writeln(a=: 8, a , b= : 8, b ); 输出 a, b 所指单元的值 readln End .第(2) 种方法，对各存储单元所保存的值并不改变，只是交换了指向这些单元的存储地址（指针值），可以简略地用如下图示说明：( 图中“”表示指向存储单元)指针类型的指针变量a, b 存有各指向单元的地址值，将指针交换赋值步骤为：将 c: =a ( 让 c 具有 a 的指针值 ) ;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

4、- 第 1 页，共 4 页 - - - - - - - - - 将 a: =b ( 让 a 具有 b 的指针值 ) ;将 b: =c ( 让 b 具有 c 的指针值 ) ;最后输出a, b 所指向存储单元(a 和 b )的值，此时的a 指向了存储整数8 的单元（即 a = 8）， b 指向了存储整数5 的单元（即b = 5）。存储单元的值没有重新赋值，只是存放指针值的变量交换了指针值。程序 Exam519_1 Type pon= integer; 是定义指针类型，一般格式为：基类型就是指针所指向的数据元素的数据类型。也可以将类型说明合并在变量说明中直接定义说明：例如 Exam519_1中类型说

5、明与变量可以合并说明为：Var a , b, c: integer; 与程序中分开说明的作用相同定义了指针变量的类型之后，必须调用New过程开辟存储单元，调用格式如下：如果不再需要指针变量当前所指向的存储单元，可调用Dispose 过程释放所占用的存储单元， Dispose 和 New的作用正好相反，其格式为：在程序中对所指存储单元（为a ）可以视作简单变量进行赋值计算和输出。如： a : = 5 例 5. 20 利用指针对数组元素值进行排序。解：定义一个各元素为指针类型的数组a :定义一个交换指针值的过程(swap) ；定义一个打印过程(print)；定义过程 (int)将数组 b 的值赋给

6、 a 数组各元素所指向的各存储单元。过程 pixu 用交换指针值的方式，按 a 数组所指向的存储单元内容值从小到大地调整各元素指针值，实现“指针”排序；按顺序打印a 数组各元素指向单元的值(a i )。Program Exam520; const n=8; b: array1 . n of integer =(44, 46, 98, 86, 36, 48, 79, 71) ; type pon= integer; var a: array1 . n of pon; Procedure swap(var p1, p2: pon); 交换指针 var p: pon; begin p: =p1; p

7、1: =p2; p2: =p end; Procedure print; 打印数组各元素指向单元(a i )的值 var i: integer; begin for i: =1 to n do write(a i : 6); writeln; writeln; end; Procedure int; 将数组 b 的值赋给a 数组各元素所指向的存储单元 var i: integer; begin for i: =1 to n do名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，

8、共 4 页 - - - - - - - - - begin new(a i ); a i : =b i ; end; print; end; Procedure pixu; 排序 var i, j, k: integer; begin for i: =1 to n-1 do begin k: =i ; for j: =i+1 to n do if aj ak then k: =j ; swap(ak, a i ) end end; Begin int; pixu; print; readln End . 例 5. 21 有 m只猴子要选猴王，选举办法如下：所有猴子按1 . . m编号围坐成圆圈

9、，从第一号开始按顺序1, 2, . . , n 连续报数，凡报 n 号的退出到圈外。如此循环报数， 直到圈上只剩下一只猴子即当选为王。用指针 （环形链表）编程。解：让指针pon 指向的单元为记录类型，记录内容含有两个域：编号变量链指针变量用过程 crea 建立环形链；用过程king 进行报数处理：每报数一次t 计数累加一次，当所报次数能被n整除， 就删去该指针指向的记录，将前一个记录的链指针指向下一个记录。删去的指向单元（记录）应释放。直到链指针所指向的单元是同一单元，就说明只剩下一个记录。打印指向单元记录中编号域（num)的值。program Exam521 ; type pon= rec;

10、 指向 rec 类型 rec=record rec 为记录类型 num: byte ; 域名 num为字节类型 nxt: pon 域名 nxt 为 pon 类型 end; var hd: pon; m, n: byte ; procedure crea; 建立环形链 var s, p: pon;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - i: byte ; begin new(s); hd: =s; s . num : =1

11、; p: =s; for i: =2 to n do begin new(s); s . num : =i ; p . nxt : =s; p: =s end; p . nxt : =hd end; procedure king; 报数处理 var p, q: pon; i, t: byte ; begin p: =hd; t : =0; q: =p; repeat p: =q . nxt ; inc(t); if t=n then begin q . nxt : =p . nxt ; dispose(p); t : =0 end else q: =p until p=p . nxt ; hd

12、: =p end; begin write(m, n=); readln(m, n); 输入 m只猴，报数到n 号 crea; king; writeln(then king is : , hd . num); readln end .习题 5. 51. 请将下列八个国家的国名按英文字典顺序排列输出。 China(中国 ) Japan(日本 ) Cancda(加拿大 ) Korea(朝鲜 ) England(英格兰 ) France(法兰西 ) American(美国 ) India(印度 )2. 某医院里一些刚生下来的婴儿，都还没有取名字，全都统一用婴儿服包装，很难区分是谁的小孩。所以必须建立卡片档案，包含内容有编号、性别、父母姓名、床号。实际婴儿数是变动的， 有的到期了， 家长要抱回家， 要从卡片上注销； 新的婴儿出生， 要增加卡片，请编程用计算机处理动态管理婴儿的情况。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -