fortran指针与动态数据结构.ppt

1. 概述 2. 指针引用与赋值 3. 整型指针 4. 与指针相关的函数和语句 5. 指针数组 6. 动态链表,第十一讲 指针与动态数据结构,第十一讲 指针与动态数据结构,11.1 概述/概述,静态数据结构:在编译时为其分配存储空间,大小不能改变。 静态数据结构优点:分配算法简单,易于实现,使用方便。 静态数据结构缺点:易浪费存储空间,易产生下标越界错误。 动态数据结构:在运行时为其分配存储空间,大小可改变。 动态数据结构优点:可节约存储空间，灵活，应用广。 动态数据结构缺点:分配算法复杂,实现难度大。 象链表、树结构、图结构等数据结构都适合用动态数据结构实现，指针是实现动态数据结构的有效手段。 指针和动态数据结构广泛应用于软件设计，熟练掌握和灵活应用指针和动态数据结构求解问题，可使程序更加简洁、紧凑、高效。,11.1 概述,第十一讲 指针与动态数据结构,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/概述/动态数据结构示例,静态数据结构:在编译时为其分配存储空间,大小不能改变。 静态数据结构优点:分配算法简单,易于实现,使用方便。 静态数据结构缺点:易浪费存储空间,易产生下标越界错误。 动态数据结构:在运行时为其分配存储空间,大小可改变。 动态数据结构优点:可节约存储空间，灵活，应用广。 动态数据结构缺点:分配算法复杂,实现难度大。 象链表、树结构、图结构等数据结构都适合用动态数据结构实现，指针是实现动态数据结构的有效手段。 指针和动态数据结构广泛应用于软件设计，熟练掌握和灵活应用指针和动态数据结构求解问题，可使程序更加简洁、紧凑、高效。,11.1 概述,概述 存储结构 访问方式 指针声明 指针状态,第十一讲 指针与动态数据结构,11.1 概述/存储结构,存储单元地址:存储单元在内存中的排列序号（编号）。 存储分配:系统为变量、数组、结构体、指针分配连续存储单元，用于存储有关数据，其变量名、数组名、结构体名、指针名代表连续存储单元首地址。 指针变量（指针）:为其分配的存储单元用于保存其它变量、数组、结构体的地址。通过改变其所存储的地址内容实现动态数据结构。 示例： INTEGER,TARGET : I=1255 REAL : R=534.45 CHARACTER*5 :S=CHINA INTEGER : A(3)=(/35,45,55/) INTEGER,POINTER : P P=I,11.1 概述,第十一讲 指针与动态数据结构,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/存储结构/示例,存储单元地址:存储单元在内存中的排列序号（编号）。 存储分配:系统为变量、数组、结构体、指针分配连续存储单元，用于存储有关数据，其变量名、数组名、结构体名、指针名代表连续存储单元首地址。 指针变量（指针）:为其分配的存储单元用于保存其它变量、数组、结构体的地址。通过改变其所存储的地址内容实现动态数据结构。 示例： INTEGER,TARGET : I=1255 REAL : R=534.45 CHARACTER*5 :S=CHINA INTEGER : A(3)=(/35,45,55/) INTEGER,POINTER : P P=I,11.1 概述,第十一讲 指针与动态数据结构,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/访问方式,11.1 概述,第十一讲 指针与动态数据结构,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/访问方式/示例,11.1 概述,第十一讲 指针与动态数据结构,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/指针声明,11.1 概述,第十一讲 指针与动态数据结构,POINTER属性:通过POINTER属性声明指针变量。 TARGET属性:通过TARGET属性声明指针可指的目标变量。 一般格式： ,POINTER:, 或 POINTER , 例： REAL Q1,Q2 INTEGER,POINTER:P1,P2!声明指向整型变量的指针P1和P2 POINTER Q1 !声明指向实型变量的指针Q1 POINTER IQ1,IQ2 !声明指向整型变量的指针IQ1和IQ2,概述 存储结构 访问方式 指针声明 指针状态,11.1 概述/指针状态,11.1 概述,第十一讲 指针与动态数据结构,指针有三种状态:未定义、空指针、被关联。 未定义：程序在初始状态中未定义所有指针。 空指针：指针已定义，但未成为目标变量别名。 被关联：指针已定义，已成为目标变量别名。,概述 存储结构 访问方式 指针声明 指针状态,11.2 指针引用和赋值/指针引用,指针引用：引用指针所指目标变量。,11.2 指针引用和赋值,第十一讲 指针与动态数据结构,指针引用 指针赋值 结构体指针,!例11.2 INTEGER,TARGET : R=25 INTEGER,POINTER : P P=R M=3*P-4 WRITE(*,*) P,M END !结果：25，71,!例11.3 INTEGER,POINTER：P1,P INTEGER,TARGET：R=12 P=R R=2*P WRITE(*,*) P,R END !结果：24，24,!例11.4 INTEGER,TARGET：R=13 INTEGER,POINTER：P1,P2 P1=R P2=P1 WRITE(*,*) P1,P2,R END !结果：13，13，13,11.2 指针引用和赋值/指针赋值,别名赋值：将目标变量名作为别名赋值给指针。 数据赋值：将数据表达式值赋值给指针所指目标变量。 一般格式： = = ,11.2 指针引用和赋值,第十一讲 指针与动态数据结构,!例11.5 INTEGER,TARGET：R1=25 INTEGER,TARGET：R2=35 INTEGER,POINTER：P1,P2 P1=R1 P2=R2 P1=P2 WRITE(*,*) P1,P2 END !结果：35，35,指针引用 指针赋值 结构体指针,11.2 指针引用和赋值/结构体指针,11.2 指针引用和赋值,第十一讲 指针与动态数据结构,指针引用 指针赋值 结构体指针,11.3 整型指针/概述,整型指针:地址按4字节整数对待的指针。整型指针可参与整数运算。 整型指针组成:指针、基变量、目标对象。 创建指针步骤: 第一步：将一个指针基变量链接在一个整型指针上。 POINTER(，) 第二步：将目标对象地址赋值给整型指针。 =LOC() =MALLOC() 标准函数LOC功能:获得目标对象起始内存地址。 标准函数MALLOC功能:计算表达式值n，分配n个字节存储单元，获得存储单元起始地址。 （示例）,11.3 整型指针,第十一讲 指针与动态数据结构,概述 例11.6 例11.7,11.3 整型指针/概述/示例,整型指针:地址按4字节整数对待的指针。整型指针可参与整数运算。 整型指针组成:指针、基变量、目标对象。 创建指针步骤: 第一步：将一个指针基变量链接在一个整型指针上。 POINTER(，) 第二步：将目标对象地址赋值给整型指针。 =LOC() =MALLOC() 标准函数LOC功能:获得目标对象起始内存地址。 标准函数MALLOC功能:计算表达式值n，分配n个字节存储单元，获得存储单元起始地址。 （示例）,11.3 概述,第十一讲 指针与动态数据结构,概述 例11.6 例11.7,INTEGER ：I,J=20 POINTER（P,I） !建立指针基变量I和目标对象J的等价关系 P=LOC(J) !将目标对象J的地址赋予整型指针变量P WRITE(*,*) P,I,J !输出结果为：4442932 20 20 I=30 WRITE(*,*) P,I,J !输出结果为：4442932 30 30 J=40 WRITE(*,*) P,I,J !输出结果为：4442932 40 40 END,11.3 整型指针/例11.6,分析下面程序 REAL A(10),B(5) POINTER（P,B） P=LOC(A) A(2)=125.0 !等价于设置B(2)为125.0 WRITE(*,*) B(2) END 通过POINTER语句,将指针基数组B与目标对象数组A建立联系,即指针P中存放的数组A的起始地址就是数组B的起始地址,所以运行程序后,输出B(2)的值为125.0。,11.3 整型指针,第十一讲 指针与动态数据结构,概述 例11.6 例11.7,11.3 整型指针/例11.7,分析下面程序 INTEGER : A(5),B POINTER（P,B） P=LOC(A) DO I=1,5 B=I*10 P=P+4 ENDDO WRITE(*,*) A END !输出结果为： 10 20 30 40 50 通过指针运算和指针基变量B的赋值操作,生成数组A的5个元素值。通过指针运算和指针基变量B的赋值操作,生成数组A的5个元素值。整型指针P增加4,相当于把数组的下标加1。,11.3 整型指针,第十一讲 指针与动态数据结构,概述 例11.6 例11.7,11.4与指针相关的函数和语句/NULLIFY,NULLIFY:将指针设置为空状态。空状态可用标准函数ASSOCIATED进行检测。 指针声明后，一般应将其设置为空状态。 如：INTEGER，POINTER : P NULLIFY（P）,11.4 与指针相关的函数和语句,第十一讲 指针与动态数据结构,NULLIFY ASSOCIATED ALLOCATE DEALLOCATE,11.4与指针相关的函数和语句/ASSOCIATED,ASSOCIATED:判定是否有目标对象与指针链接。 如： REAL A1(:),A2(:),A3(5) POINTER A1,A2 TARGET A3 LOGICAL S1,S2,S3 A1=A3 ！指针赋值 A2=A3 ！指针赋值 S1=ASSOCIATED(A1)！结果TRUE;指针A1已指向目标变量 S2=ASSOCIATED(A1,A3) ！结果TRUE;A1已指向A3 S3=ASSOCIATED(A1,A2) ！结果TRUE;A1和A2都指向A3,11.4 与指针相关的函数和语句,第十一讲 指针与动态数据结构,NULLIFY ASSOCIATED ALLOCATE DEALLOCATE,11.4与指针相关的函数和语句/ALLOCATE,ALLOCATE:为指针分配所指向的存储空间。 如： REAL，POINTER : P1 ALLOCATE(P1) P1=911.911,11.4 与指针相关的函数和语句,第十一讲 指针与动态数据结构,NULLIFY ASSOCIATED ALLOCATE DEALLOCATE,11.4与指针相关的函数和语句/DEALLOCATE,DEALLOCATE:释放指针所指存储空间。 如： REAL，POINTER : P1 ALLOCATE(P1) P1=911.911 DEALLOCATE（P1）,11.4 与指针相关的函数和语句,第十一讲 指针与动态数据结构,NULLIFY ASSOCIATED ALLOCATE DEALLOCATE,11.5 指针数组/指针数组,11.5 指针数组,第十一讲 指针与动态数据结构,指针数组 函数返回,11.5 指针数组/概述/程序,11.5 指针数组,第十一讲 指针与动态数据结构,指针数组 函数返回,PROGRAM exam129 TYPE row INTEGER,DIMENSION(:),POINTER : R END TYPE INTEGER,PARAMETER : N=4 TYPE(row),DIMENSION(N) : T !声明类型为row的数组T DO I=1,N ALLOCATE(T(I)%R(1:I) !为数组元素分配空间 ENDDO DO I=1,N T(I)%R(1:I)=1 !为下三角矩阵T赋值 ENDDO DO I=1,N WRITE(*,*) T(I)%R(1:I) !打印矩阵T ENDDO END,11.5 指针数组/函数返回,11.5 指针数组,第十一讲 指针与动态数据结构,FORTRAN90允许指针数组作为函数值返回。,PROGRAM exam1210 IMPLICIT NONE INTEGER,DIMENSION(10): X=(/11,8,15,4,20,3,5,18,21,17/) WRITE(*,(20I3) array(X) CONTAINS FUNCTION array(A) INTEGER,DIMENSION(:), POINTER : array INTEGER,DIMENSION(:) : A INTEGER I,J,T ALLOCATE(array(SIZE(A) !为array数组分配存储单元 array=A DO I=1,SIZE(A)-1 DO J=I+1,SIZE(A) IF (array(I)array(J) THEN T=array(J) array(J)=array(I) array(I)=T ENDIF ENDDO ENDDO END FUNCTION array END,指针数组 函数返回,11.6 动态链表/概述,11.6 动态链表,第十一讲 指针与动态数据结构,概述 创建搜索 插入节点 删除节点,链表是通过结点中的指针成员将若干个具有相同派生类型的结点拉成链，从而对一些在内存中不连续的数据进行动态处理的一种方式。链表中的第一个结点称为头结点，指向头结点的指针称为头指针。该派生类型的成员中至少有一个指向本派生类型的指针，链表中最后一个表目的成员的指针值为空，其余表目的成员的指针均指向下一个表目。为了便于对链表的操作，需要引入另一个派生类型，它用于存放链表的头指针。链表的头指针表示链表的存在与否(头指针为空表示空链表，否则表示链表中至少有一个以上的表目)。如果链表尾结点的指针成员指向了头结点，这样的链表称为“循环链表”。在本节主要讨论单向链表(简称链表)。 TYPE node INTEGER data TYPE(node),POINTER : next END TYPE node TYPE(node),POINTER : head,P,Q,L,11.6 动态链表/创建和搜索,11.6 动态链表,第十一讲 指针与动态数据结构,创建链表的过程就是把一个个结点插入链表的过程。因而创建链表的操作实际上就是不断地插入的过程。 ALLOCATE(Q) !创建一个新结点 Q.data=95 !或Q%data=95 NULLIFY(Q%next) !将结点中next置为空指针 head=Q !将指针Q赋予表头指针head 上述四条语句执行后,建立了有一个结点的链表,如图11-1所示。 ALLOCATE(P) !创建一个新结点 P.data=85 !或 P%data=85 P%next=head !将原表头结点指针head赋予指针P的next指针域 head=P !将指针P赋予表头指针head 上述四条语句执行后,建立了有二个结点的链表,如图11-2所示。 图11-1 一个结点的链表 图11-2 二个结点的链表,概述 创建搜索 插入节点 删除节点,链表创建后,需要从表头结点开始搜索链表,完成修改、输出、统计等有关处理操作。若head为表头结点指针,则一般通过下面语句完成搜索操作。 Q=head DO WHILE (ASSOCIATED(Q) !有关处理操作语句 Q=Q.next !搜索下一结点 ENDDO ASSOCIATED(Q)函数用于判定指针Q是否为空指针。,11.6 动态链表/插入节点,11.6 动态链表,第十一讲 指针与动态数据结构,执行下面语句创建新结点Q,结点Q插入链表有三种情况: ALLOCATE(Q) Q.data=num NULLIFY(Q%next) 1、假设链表为空表,即表头指针head为空指针,执行赋值语句head=Q实现插入 2、假设链表为非空表,在表头head前插入,执行下面赋值语句实现插入 Q.next=head head=Q 3、假设已创建部分链表,表头指针为head,指针P指向链表中某结点,将新结点Q插入到P结点之后,执行下面赋值语句实现插入 Q.next=P.next P.next=Q,概述 创建搜索 插入节点 删除节点,11.6 动态链表/删除节点,11.6 动态链表,第十一讲 指针与动态数据结构,从链表中删除结点Q有两种情况,结点删除后,要用DEALLOCATE(Q)语句将结点释放 1. 待删除结点Q为表头结点 假设链表为非空表,表头指针为head,执行赋值语句head=Q.next实现删除 2. 待删除结点Q为非表头结点 假设链表为非空表,表头指针为head,待删除结点Q的前趋结点指针为P,执行赋值语句P.next=Q.next或P.next=P.next.next实现删除,概述 创建搜索 插入节点 删除节点,12.1 接口/概述,接口界面功能类似EXTERNAL语句，为主调程序提供外部子程序有关接口信息，接口界面可看作是EXTERNAL语句的扩充，提供的信息比EXTERNAL丰富。 使用接口界面块可提高程序可读性。 接口界面块可用在主程序单元、模块单元、外部子程序单元中,以指明主调程序与被调用外部子程序之间的接口信息,以便保证外部子程序的正确使用。,12.1 接口,概述 格式 说明 示例,12.1 接口/格式,12.1 接口,INTERFACE END INTERFACE FUNCTION () END FUNCTION SUBROUTINE () END SUBROUTINE,概述 格式 说明 示例,12.1 接口/说明,12.1 接口,对于一些常规函数和子例行程序,使用时不需要用INTERFACE接口声明它们的接口信息,但遇到以下情况必须在主调程序中使用接口界面块: 外部函数返回结果是一个数组,即外部函数名类型为数组。 外部函数返回结果是一个字符串,且长度不是常数,也不是假定长度(*)。 外部函数返回结果是一个指针。 外部子程序形式参数(哑元)是一个数组片段。 外部子程序实在参数是关键字变元或是缺省的可选变元。 外部子程序扩展了赋值号的使用范围。 外部子程序参数个数不确定。 外部子程序改变参数传递位置。,概述 格式 说明 示例,12.1 接口/示例,12.1 接口,PROGRAM main !主程序单元，求三个数最大值 IMPLICIT NONE INTERFACE FUNCTION max3(a,b,c) IMPLICIT NONE INTEGER max3,a,b,c END FUNCTION END INTERFACE INTEGER x,y,z READ(*,*) x,y,z WRITE(*,“(1X,三个数的最大值为:,I4)“) max3(x,y,z) END FUNCTION max3(a,b,c) !求三个数最大值外部函数子程序 INTEGER max3,a,b,c,max max=a IF (Bmax) max=B IF (Cmax) max=C max3=max END FUNCTION,概述 格式 说明 示例,12.2 模块/概述,模块是FORTRAN 90新增功能,用以实现数据封装、特性继承、操作重载、公私分隔等面向对象特性,使程序安全、可靠、高效。 模块中可声明常量、变量、数组、数据块、派生类型、接口界面块、模块函数、模块子例行程序,可看成是外部子程序功能的扩充。,12.2 模块,概述 格式 说明 示例 使用,12.2 模块/格式,模块单元的一般形式是： MODULE 模块名 类型说明部分 CONTAINS 内部过程 内部过程 END MODULE 模块名 MODULE语句下面写各