FORTRAN90第十章指针与递归.ppt

10指针与递归 10 1指针的概念 10 2指针的使用 10 3指针数组 10 4链表 10 5递归及其应用 10 1指针的概念 指针变量的定义格式 类型 Pointer 变量名列表或者分两步定义 类型 变量名列表Pointer变量名列表 指针变量的类型与它的目标变量的类型必须一致 指针变量所指向的变量称为目标变量 简称为目标 对目标变量的定义必须用target属性 类型 target 变量名列表 10 1指针的概念 指针赋值语句 指针变量 目标变量赋值号 读作 指向 注意它的写法 同类型的指针变量可相互赋值指针变量 指针变量 指针变量通过指针赋值语句指向目标变量之后 使用目标变量和使用它的指针是等同的 这两者之间的暂时等同关系直到用指针赋值语句使指针变量指向另外的目标变量为止 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 例 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 可以有多个指针同时指向同一个目标变量 如 P1 R P2 R 但不可能一个指针同时指向多个目标变量 4 指针赋值可以改变当前的别名 例如 p2 p1使p2指向p1所指向的目标 10 2指针的使用 指针处于三种状态之一 未定义 程序刚开始时所有指针都未定义空指针 已定义但没有指向任何目标关联 指针已定义并指向某一目标 NULLIFY语句的作用是使指针变量处于空状态 其格式为 NULLIFY p P是指针变量 10 2 1指针的状态 10 2 2NULLIFY语句 10 2指针的使用 例 Real Pointer p1 p2Real Target aP1 a p2 a p1 p2都指向aNULLIFY p1 p1为空 p2指向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 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 2 print 1x 8f8 1 p1Nullify p1 Deallocate p2 stat i If I 0 write 1x A P2释放成功 End 例 ImplicitnoneTypestudentinteger numreal scoretype student pointer nextEndTypestudentType student pointer p1 p1Allocate p1 Allocate p2 Read p1 num p1 scoreRead p2 num p2 scoreNullify p1 next Nullify p2 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是空指针 ElsePrint p不是空指针 10 2 4ASSOCIATED固有函数 Endifend 如果p1 p2指向同一数组的不同部分 它们被认为是未结合的 ImplicitnoneReal 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 2 5悬空指针与无法访问的内存 10 3指针数组 指针数组是由指针组成的数组 容易与之混淆的概念是数组指针 指向数组的一个指针 Real Dimension Pointer A A是数组指针DimensionB 10 C 8 5 A B A指向一维数组BA C 4 A指向二维数组C的第4列 数组指针也可以是动态变量Real Dimension Pointer A A是数组指针Allocate A 50 给指针A分配内存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个元素的指针数组 TYPEreal pointerreal pointer pENDtypereal pointerReal target a b c d e f g h x yTYPE real pointer R 5 Dataa 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 而不是指向实型目标的指针 指向实型目标的指针p是数组元素的一个成员 而不是数组元素本身 使用数组的最大好处是可以进行下标运算 上例中确实存在5个指向实型目标的指针 也确实可以象使用数组一样通过使用R数组的下标变量R I 的成员p来实现下标运算 因此上说它间接地实现了指针数组 在FORTRAN90中 严格地由指针组成的指针数组是不能实现的 IMPLICITNONEINTEGER ITYPEROWREAL DIMENSION POINTER RENDTYPEROWINTEGER PARAMETER N 6TYPE ROW DIMENSION N S TDOI 1 NALLOCATE T I R 1 I T I R 1 I IENDDOS T 相当于s I r t I rDoI 1 nPrint s I r 1 I Enddo DoI 1 ns I r 1 I 2 iEnddoDoI 1 nPrint t I r 1 I Enddoend 1 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 0 2 04 04 06 06 06 08 08 08 08 010 010 010 010 010 012 012 012 012 012 012 0 10 4链表 链表概念链表的创建链表的插入链表的删除链表的输出链表举例 10 4 1链表概念 链表是一个节点的序列 其中每个节点被连接到它前面的节点上 从上面链表可知 每个节点有二个域 第一个是数据域 第二个是指针域 链表的第一个节点称为表头 最后一个节点称为表尾 指向表头的指针称为头指针 最后一个节点的指针域为空指针 没有任何节点的链表称为空链表 空链表的头指针为空 为了表示链表 必须先定义一个派生类型来表表示节点的结构 例如整型数值链表中节点的类型定义为 Typenodeinteger valuetype node pointer nextEndTypenode 表头节点的指针可用下述方法建立 Typelisttype node pointer headEndTypelist Type list L则L head为链表表头节点的指针 10 4 2链表的创建 用一个函数子程序NEW 来创建一个空链表 空链表形式如图 FUNCTIONNEW RESULT NEW LIST TYPE LIST NEW LISTNULLIFY NEW LIST HEAD ENDFUNCTIONNEW使用这个函数 就可以通过下列语句创建一个空链表 TYPE LIST LL NEW 下面为L添加结点 建立一个如下图所示的链表 TYPE NODE POINTER CURRENTALLOCATE CURRENT CURRENT VALUE NUMCURRENT NEXT L HEADL HEAD CURRENT三个结点可用下列语句实现 L NEW DOI 1 3READ NUMALLOCATE CURRENT CURRENT VALUE NUMCURRENT NEXT L HEADL HEAD CURRENTENDDO 10 4 3链表的插入 在链表中插入结点 先要找出插入位置 然后完成插入 例如在下列链表中插入一个结点 结点数字部分的值为25 下列程序段用来找出插入位置 其中Q指向插入结点的后继结点 P指向插入结点的前一个结点 INTEGER NUMBERTYPE NODE POINTER P Q TEMPNULLIFY P Q L HEADDOWHILE ASSOCIATED Q AND NUMBER Q VALUE P QQ Q NEXTENDDO 建立结点并插入链表的程序段为 ALLOCATE TEMP TEMP VALUE NUMBERTEMP NEXT QIF ASSOCIATED P THENP NEXT TEMPELSEL HEAD TEMPENDIF 上述过程可编写成下列子程序 ALLOCATE TEMP TEMP VALUE NUMBERTEMP NEXT QIF ASSOCIATED P THENP NEXT TEMPELSEL HEAD TEMPENDIF TYPE NODE POINTER P Q TEMPNULLIFY P Q L HEADDOWHILE ASSOCIATED Q AND NUMBER Q VALUE P QQ Q NEXTENDDO SUBROUTINEINSERT L NUMBER TYPE LIST INTENT INOUT LINTEGER INTENT IN NUMBER ENDSUBROUTINEINSERT 10 4 4链表的删除 在链表中删除结点 先要找出删除位置 然后完成删除 下列程序段用来找出删除位置 其中Q指向删除结点 P指向删除结点的前一个结点 NULLIFY P Q L HEADDOWHILE ASSOCIATED Q AND NUMBER Q VALUE P QQ Q NEXTENDDOIF ASSOCIATED Q THENFOUND TRUE ELSE FOUND FALSE ENDIF 删除结点程序段 IF FOUND THENIF ASSOCIATED P THENP NEXT Q NEXTELSEL HEAD Q NEXTENDIFDEALLOCATE Q ENDIF 删除一个链表全部结点的子程序为 Subroutineempty L type list intent inout Ltype node pointer tempdowhile associated L HEAD temp L headL head temp nextdeallocate temp EnddoEndSubroutineempty 10 4 5链表的输出 SUBROUTINEPRINT LIST L TYPE LIST INTENT IN LTYPE NODE POINTER PP L HEADDOWHILE ASSOCIATED P PRINT P VALUEP P NEXTENDDOENDSUBROUTINEPRINT LIST 10 5递归及其应用 过程直接或间接地调用自身 就形成递归过程 有递归函数和递归子程序 10 5 1递归函数 定义方式 RECURSIVEFUNCTIONfunc 虚参表 RESULT result name 函数体 END Function fun 关键词RECURSIVE说明函数是递归的 recursiveFunctionFact n result f real fif n 1 thenf 1elsef fact n 1 nendifendfunctionfact 例 计算n 主程序 InterfacerecursiveFunctionFact n result f real fendfunctionfactEndInterfaceread ns fact n print n send 10 5递归及其应用 10 5 2递归子程序 定义方式 RecursiveSubroutinesubname 虚参表 过程体 END Subroutine subname 关键词RECURSIVE说明过程是递归的 典型的例子是汉诺 Hanoi 问题 递归过程把不断地简化 问题的最简形式必须是已知的 这就是所谓递归终止条件 例 计算n Recursivesubroutinesub f n Integer intent in nInteger fIf n 0 thenF n fCallsub f n 1 ElseF 1EndifEndsubroutinesub InterfaceRecursivesubroutinesub f n Integer intent in nInteger fendsubroutineEndInterfaceIntegerf nread nCallsub f n print n fend