指针与动态变量课件

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