《动态数据类型指针优秀PPT.ppt》由会员分享,可在线阅读,更多相关《动态数据类型指针优秀PPT.ppt(28页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态数据类型指针第1页,本讲稿共28页一、指针的定义及操作一、指针的定义及操作(一)指针类型和指针变量(一)指针类型和指针变量在pascal中,指针变量(也称动态变量)存放某个存储单元的地址;也就是说,指针变量指示某个存储单元。指针类型的格式为:基类型说明:一个指针只能指示某一种类型数据的存储单元,这种数据类型就是指针的基类型,基类型可以是除指针、文件外的所有类型。type pointer=Integer;var p1,p2:pointer;定义了两个指针变量p1和p2,这两个指针可以指示一个整型存储单元(即p1、p2 中存放的是某存储单元的地址,而该存储单元恰好能存放一个整型数据)。第2页,
2、本讲稿共28页和其它类型变量一样,也可以在var区直接定义指针型变量。例如:var a:real;b:boolean;又如:type person=recordname:string20;sex:(male,female);age:1.100end;var pts:person;第3页,本讲稿共28页pascal规定所有类型都必须先定义后使用,但只有在定义指针类型时可以例外,如下列定义是合法的:type pointer=rec;rec=recorda:integer;b:charend;第4页,本讲稿共28页(二)开辟和释放动态存储单元(二)开辟和释放动态存储单元1 1、开辟动态存储单元、开辟
3、动态存储单元在pascal中,指针变量的值一般是通过系统分配的,开辟一个动态存储单元必须调用标准过程new。new过程的调用的一般格式:New(指针变量)功能:开辟一个存储单元,此单元能存放的数据的类型正好是指针的基类型,并把此存储单元的地址赋给指针变量。第5页,本讲稿共28页几点说明几点说明:这实际上是给指针变量赋初值的基本方法。例如,设有说明:var p:Integer;这只定义了P是一个指示整型存储单元的指针变量,但这个单元尚未开辟,或者说P中尚未有值(某存储单元的首地址)。当程序中执行了语句new(p)才给赋值,即在内存中开辟(分配)一个整型变量存储单元,并把此单元的地址放在变量中。示
4、意如下图:(a)编译时给 (b)执行New(p)后 (c)(b)的简略表示 p分配空间 生成新单元?表示值不定 新单元的地址为XXXX内存单元示意图第6页,本讲稿共28页一个指针变量只能存放一个地址。如再一次执行New(p)语句,将在内存中开辟另外一个新的整型变量存储单元,并把此新单元的地址放在中,从而丢失了原存储单元的地址。当不再使用当前所指的存储单元时,可以通过标准过程Dispose释放该存储单元。如:New(p);New(p);Dispose(p);第7页,本讲稿共28页释放动态存储单元释放动态存储单元dispose语句的一般格式:dispose(指针变量);功能:释放指针所指向的存储单
5、元,使指针变量的值无定义。Dispose(p);如:New(p);第8页,本讲稿共28页(三)动态存储单元的引用(三)动态存储单元的引用在给一个指针变量赋以某存储单元的地址后,就可以使用这个存储单元.引用动态存储单元一般格式:指针变量说明:说明:在用New过程给指针变量开辟了一个它所指向的存储单元后,要使用此存储单元的唯一方法是利用该指针。对动态存储单元所能进行的操作是该类型(指针的基类型)所允许的全部操作。第9页,本讲稿共28页例例1 1 设有下列说明:var p:integer;i:integer;画出执行下列操作后的内存示意图:New(p);P:=4;i:=p;(a)编译时 (b)执行N
6、ew语句(c)执行P:=4(d)执行i:=P分配存储 单元 内存单元示意图第10页,本讲稿共28页(四)对指针变量的操作(四)对指针变量的操作 具有同一基类型的指针变量之间相互赋值具有同一基类型的指针变量之间相互赋值例例2 2 设有下列说明与程序段:var p1,p2,p3:integer;begin New(P1);New(P2);New(P3);P1:=P2;P2:=P3;end;2 2、可以给指针变量赋、可以给指针变量赋nilnil值值nil是PASCAL的关键字,它表示指针的值为空。例如,执行:p1:=ni1后,p1的值是有定义的,但p1不指向任何存储单元。第11页,本讲稿共28页3
7、3、可以对指针变量进行相等或不相等的比较运算、可以对指针变量进行相等或不相等的比较运算在实际应用中,通常可以在指针变量之间,或指针变量与nil之间进行相等()或不相等(的比较,比较的结果为布尔量。例例3 3 输入两个整数,按从小到大打印出来。分析:分析:不用指针类型可以很方便地编程,但为了示例指针的用法,我们利用指针类型。定义一个过程swap用以交换两个指针的值。Type pointer=integer;var p1,p2:pointer;procedure swap(var q1,q2:pointer);var q:pointer;beginq:=q1;q1:=q2;q2:=q;end;be
8、ginnew(p1);new(p2);write(Input 2 data:);readln(pq,p2);if p1p2 then swap(p1,p2);writeln(Output 2 data:,p1:4,p2:4);end.第12页,本讲稿共28页例1分别用简单变量和指针变量交换两个变量的值。解:设两个变量a,b的值分别为5,8(1)用简单变量交换:ProgramExam101;consta=5;b=8;常量varc:integer;beginc:=a;a:=b;b:=c;用简单变量交换Type指针类型名=基类型;writeln(a=:8,a,b=:8,b);readlnend.第1
9、3页,本讲稿共28页(2)用指针变量交换:ProgramExam102;typepon=integer;pon为指针类型vara,b,c:pon;a,b,c为指针变量beginNew(指针变量);new(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所指单元的值Dispose(指针变量);readlnEnd.第14页,本讲稿共28页第(2)种方法,对各存储单元所保存的值并不改变,只是交换了指向这些单元的存储地址(指针值),可以简略地用如下图示
10、说明:第(1)种方法,直接采用变量赋值进行交换,(实际上给各存储单元重新赋值)其过程如下图所示:第15页,本讲稿共28页(图中“-”表示指向存储单元)指针类型的指针变量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)。存储单元的值没有重新赋值,只是存放指针值的变量交换了指针值。第16页,本讲稿共28页例2 利用指针对数组元素值进行排序。分析:分析:定义一个各元
11、素为指针类型的数组a:定义一个交换指针值的过程(swap);定义一个打印过程(print);定义过程(int)将数组b的值赋给a数组各元素所指向的各存储单元。过程pixu用交换指针值的方式,按a数组所指向的存储单元内容值从小到大地调整各元素指针值,实现“指针”排序;按顺序打印a数组各元素指向单元的值(a i )。第17页,本讲稿共28页ProgramExam2;constn=8;b:array1.nofinteger=(44,46,98,86,36,48,79,71);typepon=integer;vara:array1.nofpon;Procedureswap(varp1,p2:pon);
12、交换指针varp:pon;beginp:=p1;p1:=p2;p2:=pend;Procedureprint;打印数组各元素指向单元(ai)的值vari:integer;beginfori:=1tondowrite(ai:6);writeln;writeln;end;第18页,本讲稿共28页 Procedure int;将数组b的值赋给a数组各元素所指向的存储单元 var i:integer;begin for i:=1 to n do begin new(a i);a i :=b i;end;print;end;Procedure pixu;排序 var i,j,k:integer;begi
13、n 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;第19页,本讲稿共28页Begin 主程序部分 int;pixu;print;readln End.第20页,本讲稿共28页例3 有m只猴子要选猴王,选举办法如下:所有猴子按1.m编号围坐成圆圈,从第一号开始按顺序1,2,.,.,n连续报数,凡报n号的退出到圈外。如此循环报数,直到圈上只剩下一只猴子即当选为王。普通方法经仔细分析,此题实质与筛选法求素数类似。1)开始时将m个下标变量的值均赋为1,表示大家都在圈上。2)
14、假设我们用变量K来计数,当报到n时(即K的值为n)退出,将相应的下标变量的值改赋为0,表示他已退出圈,其值不影响K的下一次计数。3)连圈问题:计数时下标值从1开始依次增加,超n时重新赋为1,这样做就连成圈了。第21页,本讲稿共28页Programmonkey;Vara:array1.100ofinteger;I,k,p,x:integer;Beginreadln(m,n);forI:=1tondoai:=1;k:=0;p:=0;whilepm-1do当P=m-1时结束任务,即只有一个人还在圈上beginx:=0;每次计数时清零whilexmthenk:=1;连成圈x:=x+ak;end;wri
15、te(k,);ak:=0;p:=p+1;end;End.程序说明:K:数组下标值,为了连成圈P:统计出圈个数X:报数值第22页,本讲稿共28页例3 有m只猴子要选猴王,选举办法如下:所有猴子按1.m编号围坐成圆圈,从第一号开始按顺序1,2,.,.,n连续报数,凡报n号的退出到圈外。如此循环报数,直到圈上只剩下一只猴子即当选为王。用指针(环形链表)编程。分析:分析:让指针pon指向的单元为记录类型,记录内容含有两个域:编号变量 链指针变量用过程crea建立环形链;用过程king进行报数处理:每报数一次t计数累加一次,当所报次数能被n整除,就删去该指针指向的记录,将前一个记录的链指针指向下一个记录
16、。删去的指向单元(记录)应释放。直到链指针所指向的单元是同一单元,就说明只剩下一个记录。打印指向单元记录中编号域(num)的值。第23页,本讲稿共28页programExam03;typepon=rec;指向rec类型rec=recordrec为记录类型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:
17、=send;p.nxt:=hd end;第24页,本讲稿共28页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:=p end;begin write(m,n=);readln(m,n);输入m只猴,报数到n号 crea;king;writeln(then king is:,hd .num);readln end
18、.第25页,本讲稿共28页1.请将下列八个国家的国名按英文字典顺序排列输出。China(中国)Japan(日本)Cancda(加拿大)Korea(朝鲜)England(英格兰)France(法兰西)American(美国)India(印度)2.某医院里一些刚生下来的婴儿,都还没有取名字,全都统一用婴儿服包装,很难区分是谁的小孩。所以必须建立卡片档案,包含内容有编号、性别、父母姓名、床号。实际婴儿数是变动的,有的到期了,家长要抱回家,要从卡片上注销;新的婴儿出生,要增加卡片,请编程用计算机处理动态管理婴儿的情况。习习 题题第26页,本讲稿共28页二、链表结构二、链表结构设有一批整数(12,56,
19、45,86,77,),如何存放呢?当然我们可以选择以前学过的数组类型。但是,在使用数组前必须确定数组元素的个数。如果把数组定义得大了,就会有大量空闲存储单元,定义得小了,又会在运行中发生下标越界的错误,这是静态存储分配的局限性。指针类型可以构造一个简单而实用的动态存储分配结构链表结构。第27页,本讲稿共28页下图是一个简单链表结构示意图:下图是一个简单链表结构示意图:说明:说明:每个框表示链表的一个元素,称为结点。框的顶部表示了该存储单元的地址(当然,这里的地址是假想的)。每个结点包含两个域:一个域存放整数,称为数据域,另一个域存放下一个结点(称为该结点的后继结点,相应地,该结点为后继结点的前趋结点)的地址。链表的第一个结点称为表头,最后一个结点表尾,称为指针域;指向表头的指针head称为头指针(当head为nil时,称为空链表),在这个指针变量中 存放了表头的地址。在表尾结点中,由指针域不指向任何结点,一般放入nil。第28页,本讲稿共28页