《FORTRAN90第十章指针与递归.ppt》由会员分享，可在线阅读，更多相关《FORTRAN90第十章指针与递归.ppt（38页珍藏版）》请在三一办公上搜索。
1、10 指针与递归,10.1 指针的概念10.2 指针的使用10.3 指针数组10.4 链表10.5 递归及其应用,10.1 指针的概念,指针变量的定义格式:类型,Pointer:变量名列表或者分两步定义:类型:变量名列表Pointer 变量名列表,指针变量的类型与它的目标变量的类型必须一致。,指针变量所指向的变量称为目标变量,简称为目标。对目标变量的定义必须用target属性:类型,target:变量名列表,10.1 指针的概念,指针赋值语句:指针变量=目标变量赋值号=读作“指向”,注意它的写法。同类型的指针变量可相互赋值指针变量=指针变量,指针变量通过指针赋值语句指向目标变量之后,使用目标变
2、量和使用它的指针是等同的。这两者之间的暂时等同关系直到用指针赋值语句使指针变量指向另外的目标变量为止。,10.1 指针的概念,例:Real,pointer:p1,p2!p1,p2可指向实型目标变量。Real,target:x,y!实型目标变量P1=x;p2=y!指针赋值语句X=-0.618!P1=-0.618P2=1.414!Y=1.414,例:Real,Dimension(:),pointer:p!p可指向有target属性的一维实型数组(包括二维数组的一行或一列)。Real,target:a(5,6)!实型目标数组P=A(2,:)!指针赋值语句p=1!赋值语句,使A数组第2行元素全为1,例
3、:Real,pointer:p1,p2Real,target:r=13P1=rP2=p1Prinr*,p1,p2,rend,Real,pointer:p1,p2Real,target:r1=13Real,target:r2=15Print*,r1,r2P1=r1;p2=r2Print*,p1,p2P1=p2Print*,p1,p2,r1,r2r2=2*r2P2=p1Print*,p1,p2,r1,r2end,说明：（1）指针变量通过指针赋值语句指向目标变量之后，便成为所指向目标的别名。（2）对于一个指针变量的访问，实际上就是对其目标变量的访问。（3）可以有多个指针同时指向同一个目标变量，如：P
4、1=R，P2=R。但不可能一个指针同时指向多个目标变量。（4）指针赋值可以改变当前的别名。例如：p2=p1使p2指向p1所指向的目标。,10.2 指针的使用,指针处于三种状态之一:未定义:程序刚开始时所有指针都未定义空指针:已定义但没有指向任何目标关联:指针已定义并指向某一目标,NULLIFY语句的作用是使指针变量处于空状态。其格式为:NULLIFY(p)P是指针变量,10.2.1 指针的状态,10.2.2 NULLIFY语句,10.2 指针的使用,例:Real,Pointer:p1,p2Real,Target:aP1=a;p2=a!p1,p2都指向aNULLIFY(p1)!p1为空,p2指向
5、aP2=p1!p1与p2都为空指针,用Allocate分配一块内存,并使指针变量指向它,指针变量就成了这块内存的别名。这就是动态变量。Allocate语句的格式:Allocate(p,Stat=整型变量名)P必须已定义,整型变量表明分配是否成功，分配成功，整型变量被赋值0，否则赋非0值。,10.2.3 动态变量,10.2 指针的使用,例:Real,Pointer:pAllocate(p)!给指针p分配内存,用DeAllocate语句可以释放已分配给某指针变量的内存,并使该指针变量置空。其格式为:DeAllocate(p,Stat=整型变量名),例:Real,Pointer:pAllocate(
6、p)!给指针p分配内存P=13;print*,pDeAllocate(p)!释放指针p的内存End,10.2 指针的使用,例:Real,Pointer:p1(:)Real,Allocatable,Target:p2(:,:)Allocate(p1(1:8),stat=I)!给指针p1分配内存If(I=0)print*,P1分配成功P1=2.5;print(1x,8f8.1),p1Allocate(p2(1:8,1:3),stat=I)!给数组p2分配内存If(I=0)print*,P2分配成功P2=1.5;p2(1:8:2,2)=6.8;write(*,(1x,8f8.1)p2P1=p2(2:
7、7,2);print(/1x,8f8.1),p1Nullify(p1)Deallocate(p2,stat=i)If(I=0)write(*,(/1x,A)P2释放成功End,例：Implicit noneType student integer:num real:score type(student),pointer:nextEnd Type studentType(student),pointer:p1,p1Allocate(p1)Allocate(p2)Read*,p1%num,p1%scoreRead*,p2%num,p2%scoreNullify(p1%next);Nullify(p
8、2%next),Print*,p1%num,p1%scorePrint*,p2%num,p2%scoreDeallocate(p1)Deallocate(p2)end,10.2 指针的使用,逻辑型固有函数ASSOCIATED检查一指针是否指向一个目标或是否为另一个对象的别名。其格式为:ASSOCIATED(p1,p2)待检查的指针p1必须已定义;可选参数p2如果是目标变量,则检查p1是否指向它,p2若是指针,则检查p1与p2是否指向同一目标或同时为空指针。,例:Real,Pointer:p,q;NULLify(q);!Q是空指针If(ASSOCIATED(p,q)thenPrint*,”p是空
9、指针”ElsePrint*,”p不是空指针”,10.2.4 ASSOCIATED固有函数,End ifend,如果p1,p2指向同一数组的不同部分，它们被认为是未结合的。Implicit noneReal,target,dimension(4):a=(/1,2,3,4/)Real,pointer,dimension(:):p,qP=a(1:3)Q=a(2:4)Print*,associated(p,q)end,10.2 指针的使用,没有指向任何对象的指针就是悬空指针。刚刚定义的指针就是悬空的。用DeAllocate语句间接释放的指针很可能是悬空的。悬空指针有不定值,引用悬空指针的结果是随机的,
10、表现为程序运行不稳定或死机。,不经过内存释放的步骤而将动态变量的指针直接置空或指向其它目标,就会使该变量所占的内存不可访问。这会造成内存浪费。,10.2.5 悬空指针与无法访问的内存,10.3 指针数组,指针数组是由指针组成的数组。容易与之混淆的概念是数组指针:指向数组的一个指针。Real,Dimension(:),Pointer:A!A是数组指针Dimension B(10),C(8,5)A=B!A指向一维数组BA=C(:,4)!A指向二维数组C的第4列,数组指针也可以是动态变量Real,Dimension(:),Pointer:A!A是数组指针Allocate(A(50)!给指针A分配内存
11、A=10;print*,ADeAllocate(A)!释放指针A的内存End,10.3 指针数组,当数组指针是动态变量时,它所分配到的内存区被当作一个数组使用,但是,该数组是没有名字的,数组指针的名字就作为它的别名。下面的例子说明A不是一个指针数组：Dimension(:),Pointer:A!A是数组指针Real,target:b=2Allocate(A(50)!给指针A分配内存A(1)=B!错误,A(1)不是指针A(2)=64;print*,A(2)DeAllocate(A)!释放指针A的内存End,10.3 指针数组,指针数组只能用间接方法实现。,例:定义一个具有5个元素的指针数组。TY
12、PE real_pointer real,pointer:pEND type real_pointerReal,target:a,b,c,d,e,f,g,h,x,yTYPE(real_pointer)R(5)Data a,b,c,d,e,f,g,h,x,y/1,2,3,4,5,6,7,8,9,10/R(1)%p=b;r(2)%p=d;r(3)%p=fr(4)%p=h;r(5)%p=yPrint*,(R(I)%p,I=1,5),a,c,e,g,xEND,10.3 指针数组,事实上,上例中并没有一个指针数组,因为数组的类型是派生类型real_pointer,而不是指向实型目标的指针。指向实型目标的
13、指针p是数组元素的一个成员,而不是数组元素本身。,使用数组的最大好处是可以进行下标运算,上例中确实存在5个指向实型目标的指针,也确实可以象使用数组一样通过使用R数组的下标变量R(I)的成员p来实现下标运算。因此上说它间接地实现了指针数组。,在FORTRAN 90中,严格地由指针组成的指针数组是不能实现的。,IMPLICIT NONEINTEGER:ITYPE ROW REAL,DIMENSION(:),POINTER:REND TYPE ROWINTEGER,PARAMETER:N=6TYPE(ROW),DIMENSION(N):S,TDO I=1,N ALLOCATE(T(I)%R(1:I)
14、T(I)%R(1:I)=IEND DOS=T!相当于 s(I)%r=t(I)%rDo I=1,nPrint*,s(I)%r(1:I)End do,Do I=1,ns(I)%r(1:I)=2*iEnd doDo I=1,nPrint*,t(I)%r(1:I)End doend,1.02.0 2.03.0 3.0 3.04.0 4.0 4.0 4.05.0 5.0 5.0 5.0 5.06.0 6.0 6.0 6.0 6.0 6.0,2.04.0 4.06.0 6.0 6.08.0 8.0 8.0 8.010.0 10.0 10.0 10.0 10.012.0 12.0 12.0 12.0 12.
15、0 12.0,10.4 链表,链表概念链表的创建链表的插入链表的删除链表的输出链表举例,10.4.1 链表概念,链表是一个节点的序列，其中每个节点被连接到它前面的节点上。,从上面链表可知，每个节点有二个域，第一个是数据域，第二个是指针域。链表的第一个节点称为表头，最后一个节点称为表尾。指向表头的指针称为头指针，最后一个节点的指针域为空指针。没有任何节点的链表称为空链表。空链表的头指针为空。,为了表示链表，必须先定义一个派生类型来表表示节点的结构。例如整型数值链表中节点的类型定义为：Type nodeinteger:valuetype(node),pointer:nextEnd Type nod
16、e,表头节点的指针可用下述方法建立：Type listtype(node),pointer:headEnd Type list,Type(list):L则L%head为链表表头节点的指针。,10.4.2 链表的创建,用一个函数子程序NEW（）来创建一个空链表。空链表形式如图：,FUNCTION NEW（）RESULT（NEW_LIST)TYPE(LIST):NEW_LISTNULLIFY(NEW_LIST%HEAD)END FUNCTION NEW使用这个函数,就可以通过下列语句创建一个空链表:,TYPE(LIST):LL=NEW()下面为L添加结点,建立一个如下图所示的链表:,TYPE(NO
17、DE),POINTER:CURRENTALLOCATE(CURRENT)CURRENT%VALUE=NUMCURRENT%NEXT=L%HEADL%HEAD=CURRENT三个结点可用下列语句实现:,L=NEW()DO I=1,3READ*,NUMALLOCATE(CURRENT)CURRENT%VALUE=NUMCURRENT%NEXT=L%HEADL%HEAD=CURRENTENDDO,链表的插入,在链表中插入结点,先要找出插入位置,然后完成插入,例如在下列链表中插入一个结点,结点数字部分的值为25.,下列程序段用来找出插入位置,其中Q指向插入结点的后继结点,P指向插入结点的前一个结点.,
18、INTEGER:NUMBERTYPE(NODE),POINTER:P,Q,TEMPNULLIFY(P)Q=L%HEADDO WHILE(ASSOCIATED(Q).AND.NUMBERQ%VALUE),P=QQ=Q%NEXTEND DO,建立结点并插入链表的程序段为:ALLOCATE(TEMP)TEMP%VALUE=NUMBERTEMP%NEXT=QIF(ASSOCIATED(P)THENP%NEXT=TEMPELSEL%HEAD=TEMPEND IF,上述过程可编写成下列子程序:,ALLOCATE(TEMP)TEMP%VALUE=NUMBERTEMP%NEXT=QIF(ASSOCIATED(
19、P)THENP%NEXT=TEMPELSEL%HEAD=TEMPEND IF,TYPE(NODE),POINTER:P,Q,TEMPNULLIFY(P)Q=L%HEADDO WHILE(ASSOCIATED(Q).AND.NUMBERQ%VALUE),P=QQ=Q%NEXTEND DO,SUBROUTINE INSERT(L,NUMBER)TYPE(LIST),INTENT(INOUT):L INTEGER,INTENT(IN):NUMBER,END SUBROUTINE INSERT,链表的删除,在链表中删除结点,先要找出删除位置,然后完成删除。,下列程序段用来找出删除位置,其中Q指向删除结
20、点,P指向删除结点的前一个结点.NULLIFY（P）Q=L%HEADDO WHILE(ASSOCIATED(Q).AND.NUMBER/=Q%VALUE)P=Q Q=Q%NEXTENDDOIF(ASSOCIATED(Q)THEN FOUND=.TRUE.ELSE,FOUND=.FALSE.END IF,删除结点程序段:IF(FOUND)THEN IF(ASSOCIATED(P)THEN P%NEXT=Q%NEXT ELSE L%HEAD=Q%NEXT END IF DEALLOCATE(Q)END IF,删除一个链表全部结点的子程序为：Subroutine empty(L)type(list)
21、,intent(inout):L type(node),pointer:temp do while(associated(L%HEAD)temp=L%head L%head=temp%next deallocate(temp)End doEnd Subroutine empty,链表的输出,SUBROUTINE PRINT_LIST(L)TYPE(LIST),INTENT(IN):L TYPE(NODE),POINTER:P P=L%HEAD DO WHILE(ASSOCIATED(P)PRINT*,P%VALUEP=P%NEXT END DOEND SUBROUTINE PRINT_LIST
22、,10.5 递归及其应用,过程直接或间接地调用自身,就形成递归过程。有递归函数和递归子程序。,10.5.1 递归函数,定义方式:RECURSIVE FUNCTION func(虚参表)RESULT(result-name)函数体END Function fun关键词RECURSIVE说明函数是递归的,recursive Function Fact(n)result(f)real:fif(n=1)then f=1else f=fact(n-1)*nendifend function fact,例:计算n!,!主程序:Interfacerecursive Function Fact(n)resul
23、t(f)real:fend function factEnd Interfaceread*,ns=fact(n)print*,n,send,10.5 递归及其应用,10.5.2 递归子程序,定义方式:Recursive Subroutine subname(虚参表)过程体END Subroutine subname关键词RECURSIVE说明过程是递归的,典型的例子是汉诺(Hanoi)问题。,递归过程把不断地简化,问题的最简形式必须是已知的,这就是所谓递归终止条件。,例:计算n!,Recursive subroutine sub(f,n)Integer,intent(in):nInteger:fIf(n0)thenF=n*fCall sub(f,n-1)ElseF=1End ifEnd subroutine sub,InterfaceRecursive subroutine sub(f,n)Integer,intent(in):nInteger:fend subroutineEnd InterfaceInteger f,nread*,nCall sub(f,n)print*,n,fend,
