指针与动态变量课件

引言n以前所讲的简单类型的数据或构造类型的数据都是静态数据，这些类型的变量一经定义，就在内存中占有固定的存储单元，直至程序结束。n指针类型的变量属于动态数据。是在程序执行时，根据程序的数据存储需要而扩充或缩减。n在PASCAL中，指针变量存放某个存储单元的地址，即指针变量指向某个存储单元。引言以前所讲的简单类型的数据或构造类型的数据都是静态数据，这1指针类型说明的一般形式nType 指针类型标识符=类型标识符；n说明1：指针类型标识符由用户定义，必须符合标识符命名规则；n说明2：类型标识符：是除文件以外的任何数据类型。n例1：type point1=integer;point2=real;n解释：上例定义了两个指针类型，point1是整型指针类型，point2是实型指针类型。指针类型说明的一般形式Type 指针类型标识符=类型标识符2指针类型变量的定义n说明了指针类型，就可以定义该类型的指针变量。n例var p1:point1;p2:point2;n类型说明可以与变量定义合并在一起。n例：var p1:integer;p2:real;n注意点：指针类型说明时，可以不遵循注意点：指针类型说明时，可以不遵循“先说明先说明”后后“使使用用”的原则。的原则。n例：point=node;node=record num:integer;name:string;end;var stu:point;指针类型变量的定义说明了指针类型，就可以定义该类型的指针变量3动态变量n静态变量中存放的是相应类型的数据，而指针变量中存放的是相应类型数据所在的存储单元的地址。要访问指针变量所指向的数据，必须使用动态变量。n动态变量不在变量说明中定义，在程序执行过程中建立。它没有标识符，而是用指针变量后跟符号表示。如p:=245;n指针变量本身是简单类型（静态数据），它所指向的数据可以构成动态数据整型变量P某个数据指针变量P动态变量p某个存储单元的地址某个数据动态变量静态变量中存放的是相应类型的数据，而指针变量中存放的4动态变量的建立n指针变量的值一般是通过系统分配的，建立一个动态变量（动态存储单元）必须调用标准过程NEW。nNew过程调用的格式：new(指针变量);nNew过程的作用:建立动态变量；为动态变量分配一定的存储空间，用以存放动态变量；并将动态变量的存储空间的首地址存入指针变量中。n例：var p:integer;此时P的值为nil执行语句：new(p);此时P的值为一存储单元地址p:=245;一个指针变量只一个指针变量只能存放一个地址能存放一个地址动态变量的建立指针变量的值一般是通过系统分配的，建立一个动态5动态变量的撤消n释放动态变量使用标准过程dispose。nDispose过程调用的格式：dispose(指针变量)nDispose过程的作用：释放指针所指向的存储单元，使指针变量的值为nil，不指向任何存储单元。n例：dispose(p);动态变量的撤消释放动态变量使用标准过程dispose。6动态变量的操作n动态变量的引用：指针变量n例：p:=4;i:=p;n对动态变量所能进行的操作是该类型(指针的基类型)所允许的全部操作。n例：var p:integer;i:integer;New(p);i:=4:p:=4;动态变量的操作动态变量的引用：指针变量7指针变量的操作n可调用new、dispose过程。如new(p);dispose(p);n具有同一基类型的指针变量之间相互赋值。n例：var p1,p2,p3:integer;New(p1);new(p2);new(p3);P1:=5;p2:=P1;p3:=p1+P2;n可以给指针变量赋nil值。Nil是pascal的关键字，它表示指针的值为“空”。n例：P1:=nil;n可以对指针变量进行比较运算。n例1：new(P1);write(p1=nil);结果将输出FALSEn例2：new(p1);new(p2);write(p1=p2);false指针变量的操作可调用new、dispose过程。如new(p8指针的应用一指针的应用一 链链 表表 结结 构构指针的应用一 9简单链表结构示意图n每个框表示链表的一个元素，称为结点n框的顶部表示了该存储单元的地址(当然，这里的地址是假想的)n每个结点包含两个域：一个域存放整数，称为数据域，另一个域存放下一个结点(称为该结点的后继结点，相应地，该结点为后继结点的前趋结点)的地址，称为指针域n链表的第一个结点称为表头，最后一个结点称为表尾n指向表头的指针head称为头指针(当head为nil时，称为空链表)，在这个指针变量中存放了表头的地址n在表尾结点中，指针域不指向任何结点，一般放入nil。简单链表结构示意图每个框表示链表的一个元素，称为结点10链表的基本结构n链表中的每个结点至少应该包含两个域：一是数据域，一是指针域，因此，每个结点都是一个记录类型。指针的基类型也正是这个记录类型。因此，head可以这样定义：type pointer=rec；rec=record data：integer;next:pointer;end;var head:pointer;n相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的，一旦失去了一个指针值，后面的元素将全部丢失n与数组结构相比，使用链表结构时可根据需要采用适当的操作步骤使链表加长或缩短，而使存储分配具有一定的灵活性，这是链表结构的优点n与数组结构相比，数组元素的引用比较简单，直接用“数组名下标”即可，因为数组元素占用连续的存储单元，而引用链表元素的操作却比较复杂。链表的基本结构链表中的每个结点至少应该包含两个域：一是数据域11线性链表n链表中的每个结点只包含一个指针域，故称为线性链表或单链表。n线性链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（表头）的存储位置。同时，由于最后一个结点（表尾）没有后继，故线性链表中最后一个结点的指针域的值为空，即为nil。线性链表链表中的每个结点只包含一个指针域，故称为线性链表或单12线性链表的主要操作线性链表的主要操作1、线性链表的建立、线性链表的建立n例：编写一个程序，将读入的一串正整数存入链表，遇负数结束并统计链表的长度。n分析：每读入一个数，必须开辟一个存储单元，并将该数存入存储单元中，并链入链表中。n步骤：步骤：（1）申请新结点、调用new过程开辟一个存储单元（2）在结点的数据域填读入的数据（3）将结点链入表中某个位置（头指针指向第一个结点.）链表尾结点的后继结点为空线性链表的主要操作1、线性链表的建立例：编写一个程序，将13program create_link;type pointer=rec;rec=record data:integer;next:pointer;end;var head,p,q:pointer;num,j,outnum:integer;begin num:=0;read(j);while j=0 do begin num:=num+1;new(p);p.data:=j;if num=1 then head:=p else q.next:=p;q:=p;read(j);end;if headnil then q.next:=nil;/dispose(p);writeln(num:,num);End.program create_link;142、链表的遍历与输出链表的遍历与输出n从表头开始依次访问至表尾,方法如下：n（1)设临时工作变量P指针链表的头结点（头结点的地址不能丢失或改变，否则会丢失整个链表）n（2）while pnil do begin 输出p所指结点（当前结点）的数据值；p移向后一个结点；end;练习：请将前面的链表输出2、链表的遍历与输出从表头开始依次访问至表尾,方法如下：153、线性链表的查找、线性链表的查找n在链表中查找符合条件的结点（一般是指定数据值）（1）设临时变量p指向链表头结点（2）while(未到表尾)and(未找到)do if(找到)then 退出循环 else p移向下一个结点（3）if 到了表尾 then 输出“未找到”else（找到）对p所指结点进行相应处理。nWhile(pnil)and not(found)do begin if x=p.data then found:=true else p:=p.next end;nIf found thenelse writeln(no found);3、线性链表的查找在链表中查找符合条件的结点（一般是指定数据164、结点的插入n在P结点和Q结点之间插入一个结点m，其操作如下图所示，用下列语句即可完成。P.next:=m;M.next:=q;这两步的顺序可以颠倒吗？这两步的顺序可以颠倒吗？4、结点的插入在P结点和Q结点之间插入一个结点m，其操作如下175、结点的删除n要删除单向链表中结点P，则只要将其前趋结点的指针域指向P的后继结点即可，如上图所示。q.next:=p.next;dispose(p);5、结点的删除要删除单向链表中结点P，则只要将其前趋结点的指18循环链表n对于单向链表（线性链表），让尾部结点的指针指向链表的头部，这样就形成了一个链环，从任何一个结点开始都可以访问完全部的结点。这就是循环链表，也成为环形链表。n对于单向链表（线性链表），每个结点都只有一个指向其后继结点的指针域，如果链表的每个结点再加上一个指向其前趋结点的指针域，则称这种链表为双向链表。n对双向链表的插入、删除特别方便。同样我们也可以定义双向循环链表。循环链表对于单向链表（线性链表），让尾部结点的指针指向链表的19小结：n掌握线性链表的访问的基本方法是：从头结点开始沿线性链表反向进行探求，一般用到两个指针变量：一个用于指向刚查过的结点地址，另一个用于指向下一个待查的结点地址。结束访问的条件有两个：一个是结点地址为nil，另一个是找到了相应的结点。小结：掌握线性链表的访问的基本方法是：从头结点开始沿线性链表20指针的应用二指针的应用二 二二 叉叉 树树指针的应用二 21n二叉树是计算机中常用的另外一种动态数据结构，每个结点最多有两个后继结点，一左一右，分别称为左子女和右子女。因此对二叉树的结点类型应该是包括三个域的记录类型：一个数据域，两个指针域，分别是左指针和右指针，指向左右子女。n二叉树事实上就是由多个线性链表合成的，本质上仍是结点的插入和删除，只是相对复杂一点。二叉树是计算机中常用的另外一种动态数据结构，每个结点最多有两22应用练习：n输入一个正整数序列，遇负数停止，并按照输出顺序反向输出正整数序列。问题分析：由于线性链表在数据访问时只能从表头结点开始，所以在建立链表时应采用插入到表首的方法进行建立。请参考教师上传的代码。应用练习：输入一个正整数序列，遇负数停止，并按照输出顺序反向23