fortran指针与动态数据结构学习课程

1、1 1 . 1 1 1 . 1 概 述概 述/ /概 述概 述/ /动 态 数 据 结 构 示 例动 态 数 据 结 构 示 例l静态数据结构静态数据结构: :在编译时为其分配存储空间在编译时为其分配存储空间, ,大小不能改变。大小不能改变。l静态数据结构优点静态数据结构优点: :分配算法简单分配算法简单, ,易于实现易于实现, ,使用方便。使用方便。l静态数据结构缺点静态数据结构缺点: :易浪费存储空间易浪费存储空间, ,易产生下标越界错误。易产生下标越界错误。l动态数据结构动态数据结构: :在运行时为其分配存储空间在运行时为其分配存储空间, ,大小可改变。大小可改变。l动态数据结构优点动态

2、数据结构优点: :可节约存储空间，灵活，应用广。可节约存储空间，灵活，应用广。l动态数据结构缺点动态数据结构缺点: :分配算法复杂分配算法复杂, ,实现难度大。实现难度大。 象象链表、树结构、图结构链表、树结构、图结构等数据结构都适合用动态数据结构实现，等数据结构都适合用动态数据结构实现，指针是实现动态数据结构的有效手段。指针是实现动态数据结构的有效手段。 指针和动态数据结构广泛应用于软件设计，熟练掌握和灵活应用指针和动态数据结构广泛应用于软件设计，熟练掌握和灵活应用指针和动态数据结构求解问题，可使程序更加简洁、紧凑、高效。指针和动态数据结构求解问题，可使程序更加简洁、紧凑、高效。11.1 概

3、述a a1 1a a2 2a an n 链表链表树结构树结构图结构图结构概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态第十一讲第十一讲 指针与动态数据结构指针与动态数据结构第1页/共36页第一页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述/ / 存 储 结 构存 储 结 构l存储单元地址存储单元地址: :存储单元在内存中的排列序号（编号）。存储单元在内存中的排列序号（编号）。l存储分配存储分配: :系统为变量、数组、结构体、指针分配连续存储系统为变量、数组、结构体、指针分配连续存储单元，用于存储有关数据，其变量名、数组名、结构体名、单元

4、，用于存储有关数据，其变量名、数组名、结构体名、指针名代表连续存储单元指针名代表连续存储单元首地址首地址。l指针变量（指针）指针变量（指针）: :为其分配的存储单元用于保存其它变量、数组、为其分配的存储单元用于保存其它变量、数组、结构体的地址。通过改变其所存储的地址内容实现动态数据结构。结构体的地址。通过改变其所存储的地址内容实现动态数据结构。l示例：示例： INTEGER,TARGET : I=1255INTEGER,TARGET : I=1255 REAL : R=534.45 REAL : R=534.45 CHARACTER CHARACTER* *5 :S=CHINA5 :S=CHI

5、NA INTEGER : A(3)=(/35,45,55/) INTEGER : A(3)=(/35,45,55/) INTEGER,POINTER : P INTEGER,POINTER : P P=I P=I11.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态第2页/共36页第二页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述/ / 存 储 结 构存 储 结 构 / / 示 例示 例l存储单元地址存储单元地址: :存储单元在内存中的排列序号（编号）。存储单元在内存中的排列序

6、号（编号）。l存储分配存储分配: :系统为变量、数组、结构体、指针分配连续存储系统为变量、数组、结构体、指针分配连续存储单元，用于存储有关数据，其变量名、数组名、结构体名、单元，用于存储有关数据，其变量名、数组名、结构体名、指针名代表连续存储单元首地址。指针名代表连续存储单元首地址。l指针变量（指针）指针变量（指针）: :为其分配的存储单元用于保存其它变量、数为其分配的存储单元用于保存其它变量、数组、结构体的地址。通过改变其所存储的地址内容实现动态数据组、结构体的地址。通过改变其所存储的地址内容实现动态数据结构。结构。l示例：示例： INTEGER,TARGET : I=1255INTEGER

7、,TARGET : I=1255 REAL : R=534.45 REAL : R=534.45 CHARACTER CHARACTER* *5 :S=CHINA5 :S=CHINA INTEGER : A(3)=(/35,45,55/) INTEGER : A(3)=(/35,45,55/) INTEGER,POINTER : P INTEGER,POINTER : P P=I P=I11.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构 12551255534.45534.45CHINACHINA35354545555510001000整型变量整型变量I,I,地址地址1000

8、,41000,4字节字节, ,值值12551255实型变量实型变量R,R,地址地址1004,41004,4字节字节, ,值值534.45534.45字符型变量字符型变量S,S,地址地址1008,51008,5字节字节, ,值值CHINACHINA整型数组整型数组A,A,地址地址1013,121013,12字节字节, ,值值3535、4545、5555指针变量指针变量P,P,地址地址1025,41025,4字节字节, ,值为值为100010000 01 11000100010041004100810081013101310251025n n概述概述存储结构存储结构访问方式访问方式指针声明指针声明

9、指针状态指针状态第3页/共36页第三页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述/ / 访 问 方 式访 问 方 式11.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构l直接访问直接访问: :直接访问存储单元中的内容。如对普通变量、数直接访问存储单元中的内容。如对普通变量、数组元素、结构体成员的访问，采用直接访问方式。如图组元素、结构体成员的访问，采用直接访问方式。如图12-12-2 2所示。所示。l间接访问间接访问: :先从存储单元中得到被访问存储单元地址，然后先从存储单元中得到被访问存储单元地址，然后通过该地址访问被访问存储单元中的内容。如

10、对指针变量通过该地址访问被访问存储单元中的内容。如对指针变量的访问，采用间接访问方式。如图的访问，采用间接访问方式。如图12-312-3所示。所示。l指针变量存储单元中保存目标变量地址，通常用箭头表示。指针变量存储单元中保存目标变量地址，通常用箭头表示。F90F90指针保存目标变量名称，将指针看成目标变量的别名。指针保存目标变量名称，将指针看成目标变量的别名。l指针变量声明后指针变量声明后, ,未分配存储空间未分配存储空间, ,访问前需分配存储空间。访问前需分配存储空间。 ( (示例示例) )I I125125125125J J3753753 3* *125125I=125I=125J=3J=

11、3* *I IP PI I125125125125J J3753753 3* *1251253 3* *P PI I地址地址I=125I=125P=IP=IJ=3J=3* *I I概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态第4页/共36页第四页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述 / /访 问 方 式访 问 方 式/ /示 例示 例11.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构l直接访问直接访问: :直接访问存储单元中的内容。如对普通变量、数直接访问存储单元中的内容。如对普通变量、数组元素、结构体成员的

12、访问，采用直接访问方式。如图组元素、结构体成员的访问，采用直接访问方式。如图12-12-2 2所示。所示。l间接访问间接访问: :先从存储单元中得到被访问存储单元地址，然后先从存储单元中得到被访问存储单元地址，然后通过该地址访问被访问存储单元中的内容。如对指针变量通过该地址访问被访问存储单元中的内容。如对指针变量的访问，采用间接访问方式。如图的访问，采用间接访问方式。如图12-312-3所示。所示。l指针变量存储单元中保存目标变量地址，通常用箭头表示。指针变量存储单元中保存目标变量地址，通常用箭头表示。F90F90指针保存目标变量名称，将指针看成目标变量的别名。指针保存目标变量名称，将指针看成

13、目标变量的别名。l指针变量声明后指针变量声明后, ,未分配存储空间未分配存储空间, ,访问前需分配存储空间。访问前需分配存储空间。 ( (示例示例) )I I125125125125J J3753753 3* *125125I=125I=125J=3J=3* *I IP PI I125125125125J J3753753 3* *1251253 3* *P PI I地址地址I=125I=125P=IP=IJ=3J=3* *I I概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态!例11.1 使用指针实现两个整数交换INTEGER,TARGET : I,J !声明两个目标

14、变量I和JINTEGER,POINTER : P1,P2,P3 !声明三个指针变量P1、P2和P3I=25;J=35 !给目标变量I和J直接赋值P1=I;P2=J !给指针分配指向I和J的存储空间 WRITE(*,*) 未交换数据：,P1,P2 !通过指针变量间接输出I和J的值P3=P1;P1=P2;P2=P3 !交换指针P1和P2指向的目标变量PRINT*,已交换数据： ,P1,P2 !通过指针变量间接输出J和I的值ENDI I2525P1P1图图12-4 12-4 指针交换指针交换J J3535P2P2J J3535P2P2P1P1P3P3交换前交换前交换后交换后I I2525第5页/共3

15、6页第五页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述/ /指 针 声 明指 针 声 明11.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构lPOINTERPOINTER属性属性: :通过通过POINTERPOINTER属性声明指针变量。属性声明指针变量。lTARGETTARGET属性属性: :通过通过TARGETTARGET属性声明指针可指的目标变量。属性声明指针可指的目标变量。l一般格式：一般格式： ,POINTER:,POINTER:, 或或 POINTER POINTER , 例：例： REAL Q1,Q2REAL Q1,Q2 INTEG

16、ER,POINTER:P1,P2 INTEGER,POINTER:P1,P2! !声明指向整型变量的指针声明指向整型变量的指针P1P1和和P2P2 POINTER Q1POINTER Q1 ! !声明指向实型变量的指针声明指向实型变量的指针Q1Q1 POINTER IQ1,IQ2POINTER IQ1,IQ2! !声明指向整型变量的指针声明指向整型变量的指针IQ1IQ1和和IQ2IQ2 概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态第6页/共36页第六页，编辑于星期五：十九点 五十分。1 1 . 1 1 1 . 1 概 述概 述 / / 指 针 状 态指 针 状 态1

17、1.1 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构l指针有三种状态指针有三种状态: :未定义、空指针、被关联。未定义、空指针、被关联。u未定义：程序在初始状态中未定义所有指针。未定义：程序在初始状态中未定义所有指针。u空指针：指针已定义，但未成为目标变量别名。空指针：指针已定义，但未成为目标变量别名。u被关联：指针已定义，已成为目标变量别名。被关联：指针已定义，已成为目标变量别名。概述概述存储结构存储结构访问方式访问方式指针声明指针声明指针状态指针状态第7页/共36页第七页，编辑于星期五：十九点 五十分。1 1 . 2 1 1 . 2 指 针 引 用 和 赋 值指 针 引 用

18、和 赋 值/ / 指 针 引 用指 针 引 用l指针引用：指针引用：引用指针所指目标变量。引用指针所指目标变量。11.2 指针引用和赋值第十一讲第十一讲 指针与动态数据结构指针与动态数据结构指针引用指针引用指针赋值指针赋值结构体指针结构体指针!例11.2INTEGER,TARGET : R=25INTEGER,POINTER : PP=RM=3*P-4WRITE(*,*) P,MEND!结果：25，71!例11.3INTEGER,POINTER：P1,PINTEGER,TARGET：R=12P=RR=2*PWRITE(*,*) P,REND!结果：24，24!例11.4INTEGER,TARG

19、ET：R=13INTEGER,POINTER：P1,P2P1=RP2=P1WRITE(*,*) P1,P2,R END !结果：13，13，13第8页/共36页第八页，编辑于星期五：十九点 五十分。1 1 . 2 1 1 . 2 指 针 引 用 和 赋 值指 针 引 用 和 赋 值 / /指 针 赋 值指 针 赋 值l别名赋值：别名赋值：将目标变量名作为别名赋值给指针。将目标变量名作为别名赋值给指针。l数据赋值：数据赋值：将数据表达式值赋值给指针所指目标变量。将数据表达式值赋值给指针所指目标变量。l一般格式：一般格式： = = = = 11.2 指针引用和赋值第十一讲第十一讲 指针与动态数据结

20、构指针与动态数据结构!例11.5INTEGER,TARGET：R1=25INTEGER,TARGET：R2=35INTEGER,POINTER：P1,P2P1=R1P2=R2P1=P2WRITE(*,*) P1,P2END!结果：35，35P1P1R125R2P235R135R2P235指针引用指针引用指针赋值指针赋值结构体指针结构体指针第9页/共36页第九页，编辑于星期五：十九点 五十分。1 1 . 2 1 1 . 2 指 针 引 用 和 赋 值指 针 引 用 和 赋 值 / /结 构 体 指 针结 构 体 指 针11.2 指针引用和赋值第十一讲第十一讲 指针与动态数据结构指针与动态数据结构

21、l结构体指针：结构体指针：指向结构体的指针。指针可为结构体别指向结构体的指针。指针可为结构体别名。名。 例：例： TYPE date_recordTYPE date_record INTEGER(2) year INTEGER(2) year INTEGER(1) month,day INTEGER(1) month,day END TYPE date_record END TYPE date_record TYPE(date_record),TARGET : date TYPE(date_record),TARGET : date TYPE(date_record),POINTER : P

22、TYPE(date_record),POINTER : P P=dateP=date P.year=1995 P.year=1995；P.month=12P.month=12；P.day=25P.day=25 y=3+P.year y=3+P.year； m=P.month-2m=P.month-2；d=5+P.dayd=5+P.day WRITE(WRITE(* *, ,* *) ) datedate WRITE(WRITE(* *, ,* *) ) P P WRITE(WRITE(* *, ,* *) ) y,m,dy,m,d END END ! !输出结果：输出结果： !1995 12

23、25!1995 12 25 !1995 12 25 !1995 12 25 !1998 10 30 !1998 10 30YearYearMonthMonthdaydayP Pdatedate1995199512122525P Pdatedate指针引用指针引用指针赋值指针赋值结构体指针结构体指针第10页/共36页第十页，编辑于星期五：十九点 五十分。1 1 . 3 1 1 . 3 整 型 指 针整 型 指 针 / /概 述概 述l整型指针整型指针: :地址按地址按4 4字节整数对待的指针。整型指针可参与整字节整数对待的指针。整型指针可参与整数运算。数运算。l整型指针组成整型指针组成: :指针

24、、基变量、目标对象。指针、基变量、目标对象。l创建指针步骤创建指针步骤: :u第一步：将一个指针基变量链接在一个整型指针上。第一步：将一个指针基变量链接在一个整型指针上。 POINTER(POINTER( ， )u第二步：将目标对象地址赋值给整型指针。第二步：将目标对象地址赋值给整型指针。 =LOC(=LOC() =MALLOC(=MALLOC()l标准函数标准函数LOCLOC功能功能: :获得目标对象起始内存地址。获得目标对象起始内存地址。l标准函数标准函数MALLOCMALLOC功能功能: :计算表达式值计算表达式值n n，分配，分配n n个字节存储单元，个字节存储单元，获得存储单元起始地

25、址。获得存储单元起始地址。 （示例示例）11.3 整型指针第十一讲第十一讲 指针与动态数据结构指针与动态数据结构概述概述例例11.611.6例例11.711.7第11页/共36页第十一页，编辑于星期五：十九点 五十分。1 1 . 3 1 1 . 3 整 型 指 针整 型 指 针/ / 概 述概 述/ /示 例示 例l整型指针整型指针: :地址按地址按4 4字节整数对待的指针。整型指针可参与整数运算。字节整数对待的指针。整型指针可参与整数运算。l整型指针组成整型指针组成: :指针、基变量、目标对象。指针、基变量、目标对象。l创建指针步骤创建指针步骤: :u第一步：将一个指针基变量链接在一个整型指

26、针上。第一步：将一个指针基变量链接在一个整型指针上。 POINTER(POINTER( ， )u第二步：将目标对象地址赋值给整型指针。第二步：将目标对象地址赋值给整型指针。 =LOC(=LOC() =MALLOC(=MALLOC()l标准函数标准函数LOCLOC功能功能: :获得目标对象起始内存地址。获得目标对象起始内存地址。l标准函数标准函数MALLOCMALLOC功能功能: :计算表达式值计算表达式值n n，分配，分配n n个字节存储单元，个字节存储单元，获得存储单元起始地址。获得存储单元起始地址。 （示例示例）11.3 概述第十一讲第十一讲 指针与动态数据结构指针与动态数据结构概述概述例

27、例11.611.6例例11.711.7INTEGER ：I,J=20POINTER（P,I）!建立指针基变量I和目标对象J的等价关系P=LOC(J) !将目标对象J的地址赋予整型指针变量PWRITE(*,*) P,I,J !输出结果为：4442932 20 20I=30WRITE(*,*) P,I,J !输出结果为：4442932 30 30J=40WRITE(*,*) P,I,J !输出结果为：4442932 40 40END第12页/共36页第十二页，编辑于星期五：十九点 五十分。1 1 . 3 1 1 . 3 整 型 指 针整 型 指 针/ /例例 1 1 . 61 1 . 6分析下面程

28、序分析下面程序 REAL A(10),B(5) REAL A(10),B(5) POINTER POINTER（P,BP,B） P=LOC(A)P=LOC(A) A(2)=125.0 A(2)=125.0 ! !等价于设置等价于设置B(2)B(2)为为125.0125.0 WRITE(WRITE(* *, ,* *) ) B(2) B(2) END END通过通过POINTERPOINTER语句语句, ,将指针基数组将指针基数组B B与目标对象数组与目标对象数组A A建立联系建立联系, ,即指即指针针P P中存放的数组中存放的数组A A的起始地址就是数组的起始地址就是数组B B的起始地址的起始

29、地址, ,所以运行程所以运行程序后序后, ,输出输出B(2)B(2)的值为的值为125.0125.0。 11.3 整型指针第十一讲第十一讲 指针与动态数据结构指针与动态数据结构概述概述例例11.611.6例例11.711.7第13页/共36页第十三页，编辑于星期五：十九点 五十分。1 1 . 3 1 1 . 3 整 型 指 针整 型 指 针 / /例例 1 1 . 71 1 . 7分析下面程序分析下面程序 INTEGER : A(5),BINTEGER : A(5),B POINTER POINTER（P,BP,B） P=LOC(A)P=LOC(A) DO I=1,5 DO I=1,5 B=I

30、 B=I* *1010 P=P+4 P=P+4 ENDDO ENDDO WRITE(WRITE(* *, ,* *) ) A A END END ! !输出结果为：输出结果为： 10 20 30 40 5010 20 30 40 50 通过指针运算和指针基变量通过指针运算和指针基变量B B的赋值操作的赋值操作, ,生成数组生成数组A A的的5 5个元素值。个元素值。通过指针运算和指针基变量通过指针运算和指针基变量B B的赋值操作的赋值操作, ,生成数组生成数组A A的的5 5个元素值。整个元素值。整型指针型指针P P增加增加4,4,相当于把数组的下标加相当于把数组的下标加1 1。11.3 整型

31、指针第十一讲第十一讲 指针与动态数据结构指针与动态数据结构A AB B1 2 3 4 51 2 3 4 5P PP PP PP PP P概述概述例例11.611.6例例11.711.7第14页/共36页第十四页，编辑于星期五：十九点 五十分。1 1 . 41 1 . 4与指针相关与指针相关的函数和语句的函数和语句/ N U L L I F Y/ N U L L I F YlNULLIFY:NULLIFY:将指针设置为空状态。空状态可用标准函数将指针设置为空状态。空状态可用标准函数ASSOCIATEDASSOCIATED进行检测。进行检测。 指针声明后，一般应将其设置为空状态。指针声明后，一般应

32、将其设置为空状态。 如：如：INTEGERINTEGER，POINTER : PPOINTER : P NULLIFY NULLIFY（P P）11.4 与指针相关的函数和语句第十一讲第十一讲 指针与动态数据结构指针与动态数据结构NULLIFYNULLIFYASSOCIATEDASSOCIATEDALLOCATEALLOCATEDEALLOCATEDEALLOCATE第15页/共36页第十五页，编辑于星期五：十九点 五十分。1 1 . 41 1 . 4与指针相关与指针相关的函数和语句的函数和语句/ A S S O C I A T E D/ A S S O C I A T E DlASSOCIA

33、TED:ASSOCIATED:判定是否有目标对象与指针链接。判定是否有目标对象与指针链接。 如：如： REAL A1(:),A2(:),A3(5)REAL A1(:),A2(:),A3(5) POINTER A1,A2 POINTER A1,A2 TARGET A3 TARGET A3 LOGICAL S1,S2,S3 LOGICAL S1,S2,S3 A1=A3 A1=A3 ！指针赋值！指针赋值 A2=A3 A2=A3 ！指针赋值！指针赋值 S1=ASSOCIATED(A1)S1=ASSOCIATED(A1)！结果！结果TRUE;TRUE;指针指针A1A1已指向目标变量已指向目标变量 S2=

34、ASSOCIATED(A1,A3) S2=ASSOCIATED(A1,A3) ！结果！结果TRUE;A1TRUE;A1已指向已指向A3A3 S3=ASSOCIATED(A1,A2) S3=ASSOCIATED(A1,A2) ！结果！结果TRUE;A1TRUE;A1和和A2A2都指向都指向A3A311.4 与指针相关的函数和语句第十一讲第十一讲 指针与动态数据结构指针与动态数据结构NULLIFYNULLIFYASSOCIATEDASSOCIATEDALLOCATEALLOCATEDEALLOCATEDEALLOCATE第16页/共36页第十六页，编辑于星期五：十九点 五十分。1 1 . 41 1

35、 . 4与指针相关与指针相关的函数和语句的函数和语句/ A L L O C A T E/ A L L O C A T ElALLOCATE:ALLOCATE:为指针分配所指向的存储空间。为指针分配所指向的存储空间。 如：如： REALREAL，POINTER : P1POINTER : P1 ALLOCATE(P1) ALLOCATE(P1) P1=911.911 P1=911.91111.4 与指针相关的函数和语句第十一讲第十一讲 指针与动态数据结构指针与动态数据结构NULLIFYNULLIFYASSOCIATEDASSOCIATEDALLOCATEALLOCATEDEALLOCATEDEA

36、LLOCATEP1P1911.911911.911第17页/共36页第十七页，编辑于星期五：十九点 五十分。1 1 . 41 1 . 4与指针相关与指针相关的函数和语句的函数和语句/ D E A L L O C A T E/ D E A L L O C A T ElDEALLOCATE:DEALLOCATE:释放指针所指存储空间。释放指针所指存储空间。 如：如： REALREAL，POINTER : P1POINTER : P1 ALLOCATE(P1) ALLOCATE(P1) P1=911.911 P1=911.911 DEALLOCATE DEALLOCATE（P1P1）11.4 与指针

37、相关的函数和语句第十一讲第十一讲 指针与动态数据结构指针与动态数据结构P1P1911.911911.911NULLIFYNULLIFYASSOCIATEDASSOCIATEDALLOCATEALLOCATEDEALLOCATEDEALLOCATE第18页/共36页第十八页，编辑于星期五：十九点 五十分。1 1 . 5 1 1 . 5 指 针 数 组指 针 数 组 / /指 针 数 组指 针 数 组11.5 指针数组第十一讲第十一讲 指针与动态数据结构指针与动态数据结构指针数组指针数组函数返回函数返回l指针数组指针数组: :具有具有POINTERPOINTER属性的数组。指针数组类似动态数属性的

38、数组。指针数组类似动态数组，声明时，指针数组不指定数组维的上下界。如：组，声明时，指针数组不指定数组维的上下界。如： REAL,DIMENSION(:),POINTER : AREAL,DIMENSION(:),POINTER : A l存储分配存储分配: :指针数组需通过指针数组需通过ALLOCATEALLOCATE语句分配存储空间。如：语句分配存储空间。如： ALLOCATEALLOCATE（A A（5050） 例：使用指针数组存储下三角矩阵。例：使用指针数组存储下三角矩阵。 （程序程序）1 0 0 01 1 0 01 1 1 01 1 1 1R R RRR11111111111 12 2

39、3 34 4T第19页/共36页第十九页，编辑于星期五：十九点 五十分。1 1 . 5 1 1 . 5 指 针 数 组指 针 数 组/ /概 述概 述/ /程 序程 序11.5 指针数组第十一讲第十一讲 指针与动态数据结构指针与动态数据结构指针数组指针数组函数返回函数返回l指针数组指针数组: :具有具有POINTERPOINTER属性的数组。指针数组类似动态数属性的数组。指针数组类似动态数组，声明时，指针数组不指定数组维的上下界。如：组，声明时，指针数组不指定数组维的上下界。如： REAL,DIMENSION(:),POINTER : AREAL,DIMENSION(:),POINTER :

40、A l存储分配存储分配: :指针数组需通过指针数组需通过ALLOCATEALLOCATE语句分配存储空间。如：语句分配存储空间。如： ALLOCATEALLOCATE（A A（5050） 例：使用指针数组存储下三角矩阵。例：使用指针数组存储下三角矩阵。 （程序程序）1 0 0 01 1 0 01 1 1 01 1 1 1R R RRR11111111111 12 23 34 4TPROGRAM exam129 TYPE row INTEGER,DIMENSION(:),POINTER : R END TYPE INTEGER,PARAMETER : N=4 TYPE(row),DIMENSIO

41、N(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 ENDDOEND第20页/共36页第二十页，编辑于星期五：十九点 五十分。1 1 . 5 1 1 . 5 指 针 数 组指 针 数 组/ /函 数 返 回函 数 返 回11.5 指针数组第十一讲第十一讲 指针与动态数据结构指针与动态数据结构lFORTRAN90FORTRAN90允许指针数组作为函数值返

42、回。允许指针数组作为函数值返回。PROGRAM exam1210PROGRAM exam1210 IMPLICIT NONE IMPLICIT NONE INTEGER,DIMENSION(10): X=(/11,8,15,4,20,3,5,18,21,17/) INTEGER,DIMENSION(10): X=(/11,8,15,4,20,3,5,18,21,17/) WRITE( WRITE(* *,(20I3) array(X),(20I3) array(X)CONTAINS CONTAINS FUNCTION array(A) FUNCTION array(A) INTEGER,DIM

43、ENSION( INTEGER,DIMENSION(:):), POINTER : array, POINTER : array INTEGER,DIMENSION( INTEGER,DIMENSION(:) : :) : A A INTEGER I,J,T INTEGER I,J,T ALLOCATE(array(SIZE(A) ALLOCATE(array(SIZE(A) ! !为为arrayarray数组分配存储单元数组分配存储单元 array=Aarray=A DO I=1,SIZE(A)-1 DO I=1,SIZE(A)-1 DO J=I+1,SIZE(A) DO J=I+1,SIZ

44、E(A) IF (array(I)array(J) THEN IF (array(I)array(J) THEN T=array(J) T=array(J) array(J)=array(I) array(J)=array(I) array(I)=T array(I)=T ENDIF ENDIF ENDDO ENDDO ENDDO ENDDO END FUNCTION array END FUNCTION arrayENDEND指针数组指针数组函数返回函数返回第21页/共36页第二十一页，编辑于星期五：十九点 五十分。1 1 . 6 1 1 . 6 动 态 链 表动 态 链 表/ /概 述概

45、述11.6 动态链表第十一讲第十一讲 指针与动态数据结构指针与动态数据结构概述概述创建搜索创建搜索u 插入节点插入节点u 删除节点删除节点 链表是通过结点中的指针成员将若干个具有相同派生类型的结链表是通过结点中的指针成员将若干个具有相同派生类型的结点拉成链，从而对一些在内存中不连续的数据进行动态处理的点拉成链，从而对一些在内存中不连续的数据进行动态处理的一种方式。链表中的第一个结点称为头结点，指向头结点的指一种方式。链表中的第一个结点称为头结点，指向头结点的指针称为头指针。针称为头指针。该派生类型的成员中至少有一个指向本派生类该派生类型的成员中至少有一个指向本派生类型的指针，链表中最后一个表目

46、的成员的指针值为空，其余表型的指针，链表中最后一个表目的成员的指针值为空，其余表目的成员的指针均指向下一个表目。为了便于对链表的操作，目的成员的指针均指向下一个表目。为了便于对链表的操作，需要引入另一个派生类型，它用于存放链表的头指针。链表的需要引入另一个派生类型，它用于存放链表的头指针。链表的头指针表示链表的存在与否头指针表示链表的存在与否( (头指针为空表示空链表，否则表示链头指针为空表示空链表，否则表示链表中至少有一个以上的表目表中至少有一个以上的表目) )。如果链表尾结点的指针成员指向。如果链表尾结点的指针成员指向了头结点，这样的链表称为了头结点，这样的链表称为“循环链表循环链表”。在

47、本节主要讨论单。在本节主要讨论单向链表向链表( (简称链表简称链表) )。TYPE nodeTYPE node INTEGER data INTEGER data TYPE(node),POINTER : next TYPE(node),POINTER : nextEND TYPE nodeEND TYPE node TYPE(node),POINTER : head,P,Q,LTYPE(node),POINTER : head,P,Q,L 第22页/共36页第二十二页，编辑于星期五：十九点 五十分。1 1 . 6 1 1 . 6 动 态 链 表动 态 链 表 / /创 建 和 搜 索创 建

48、和 搜 索11.6 动态链表第十一讲第十一讲 指针与动态数据结构指针与动态数据结构 创建链表的过程就是把一个个结点插入链表的过程。因而创建链创建链表的过程就是把一个个结点插入链表的过程。因而创建链表的操作实际上就是不断地插入的过程。表的操作实际上就是不断地插入的过程。 ALLOCATE(Q) !ALLOCATE(Q) !创建一个新结点创建一个新结点 Q.data=95 !Q.data=95 !或或Q%data=95Q%data=95 NULLIFY(Q%next) ! NULLIFY(Q%next) !将结点中将结点中nextnext置为空指针置为空指针 head=Q !head=Q !将指针

49、将指针Q Q赋予表头指针赋予表头指针headhead上述四条语句执行后上述四条语句执行后, ,建立了有一个结点的链表建立了有一个结点的链表, ,如图如图11-111-1所示。所示。 ALLOCATE(P) !ALLOCATE(P) !创建一个新结点创建一个新结点 P.data=85 !P.data=85 !或或 P%data=85P%data=85 P%next=head ! P%next=head !将原表头结点指针将原表头结点指针headhead赋予指针赋予指针P P的的nextnext指针域指针域 head=P !head=P !将指针将指针P P赋予表头指针赋予表头指针headhead

50、上述四条语句执行后上述四条语句执行后, ,建立了有二个结点的链表建立了有二个结点的链表, ,如图如图11-211-2所示。所示。 图图11-1 11-1 一个结点的链表一个结点的链表 图图11-2 11-2 二个结点的链表二个结点的链表概述概述创建搜索创建搜索u 插入节点插入节点u 删除节点删除节点head95 Q85 Q95 headhead链表创建后,需要从表头结点开始搜索链表,完成修改、输出、统计等有关处理操作。若head为表头结点指针,则一般通过下面语句完成搜索操作。 Q=head DO WHILE (ASSOCIATED(Q) !有关处理操作语句 Q=Q.next !搜索下一结点 E

51、NDDO ASSOCIATED(Q)函数用于判定指针Q是否为空指针。 第23页/共36页第二十三页，编辑于星期五：十九点 五十分。1 1 . 6 1 1 . 6 动 态 链 表动 态 链 表/ /插 入 节 点插 入 节 点11.6 动态链表第十一讲第十一讲 指针与动态数据结构指针与动态数据结构执行下面语句创建新结点执行下面语句创建新结点Q,Q,结点结点Q Q插入链表有三种情况插入链表有三种情况: : ALLOCATE(Q) ALLOCATE(Q) Q.data=num Q.data=num NULLIFY(Q%next) NULLIFY(Q%next)1 1、假设链表为空表假设链表为空表,

52、,即表头指针即表头指针headhead为空指针为空指针, ,执行赋值语句执行赋值语句head=Qhead=Q实现插入实现插入 2 2、假设链表为非空表假设链表为非空表, ,在表头在表头headhead前插入前插入, ,执行下面赋值语句实执行下面赋值语句实现插入现插入 Q.next=headQ.next=headhead=Qhead=Q 3 3、假设已创建部分链表假设已创建部分链表, ,表头指针为表头指针为head,head,指针指针P P指向链表中某结指向链表中某结点点, ,将新结点将新结点Q Q插入到插入到P P结点之后结点之后, ,执行下面赋值语句实现插入执行下面赋值语句实现插入 Q.ne

53、xt=P.nextQ.next=P.next P.next=QP.next=Q 概述概述创建搜索创建搜索u 插入节点插入节点u 删除节点删除节点第24页/共36页第二十四页，编辑于星期五：十九点 五十分。1 1 . 6 1 1 . 6 动 态 链 表动 态 链 表/ /删 除 节 点删 除 节 点11.6 动态链表第十一讲第十一讲 指针与动态数据结构指针与动态数据结构从链表中删除结点从链表中删除结点Q Q有两种情况有两种情况, ,结点删除后结点删除后, ,要用要用DEALLOCATE(Q)DEALLOCATE(Q)语句将结点释放语句将结点释放 1.1. 待删除结点待删除结点Q Q为表头结点为表

54、头结点假 设 链 表 为 非 空 表假 设 链 表 为 非 空 表, , 表 头 指 针 为表 头 指 针 为h e a d ,h e a d ,执 行 赋 值 语 句执 行 赋 值 语 句head=Q.nexthead=Q.next实现删除实现删除 2.2. 待删除结点待删除结点Q Q为非表头结点为非表头结点假设链表为非空表假设链表为非空表, ,表头指针为表头指针为head,head,待删除结点待删除结点Q Q的前趋结点指针的前趋结点指针为为P,P,执行赋值语句执行赋值语句P.next=Q.nextP.next=Q.next或或P.next=P.next.nextP.next=P.next.

55、next实现删实现删除除 概述概述创建搜索创建搜索u 插入节点插入节点u 删除节点删除节点第25页/共36页第二十五页，编辑于星期五：十九点 五十分。1 2 . 1 1 2 . 1 接 口接 口/ /概 述概 述l接口界面功能类似接口界面功能类似EXTERNALEXTERNAL语句，为主调程序提供外部子程序语句，为主调程序提供外部子程序有关接口信息，接口界面可看作是有关接口信息，接口界面可看作是EXTERNALEXTERNAL语句的扩充，提供的语句的扩充，提供的信息比信息比EXTERNALEXTERNAL丰富。丰富。l使用接口界面块可提高程序可读性。使用接口界面块可提高程序可读性。l接口界面块

56、可用在主程序单元、模块单元、外部子程序单元中接口界面块可用在主程序单元、模块单元、外部子程序单元中, ,以指明以指明主调程序与被调用外部子程序之间的接口信息主调程序与被调用外部子程序之间的接口信息, ,以便保证外部子程以便保证外部子程序的正确使用。序的正确使用。12.1 接口概述概述格式格式示例示例第26页/共36页第二十六页，编辑于星期五：十九点 五十分。1 2 . 1 1 2 . 1 接 口接 口/ /格 式格 式12.1 接口 INTERFACEINTERFACE END INTERFACE END INTERFACE FUNCTION FUNCTION () END FUNCTION

57、END FUNCTION SUBROUTINE SUBROUTINE () END SUBROUTINE END SUBROUTINE概述概述格式格式示例示例第27页/共36页第二十七页，编辑于星期五：十九点 五十分。1 2 . 1 1 2 . 1 接 口接 口/ / 说 明说 明12.1 接口 对于一些常规函数和子例行程序对于一些常规函数和子例行程序, ,使用时不需要用使用时不需要用INTERFACEINTERFACE接口声接口声明它们的接口信息明它们的接口信息, ,但遇到以下情况必须在主调程序中使用接口界但遇到以下情况必须在主调程序中使用接口界面块面块: :l外部函数返回结果是一个数组外部

58、函数返回结果是一个数组, ,即外部函数名类型为数组。即外部函数名类型为数组。l外部函数返回结果是一个字符串外部函数返回结果是一个字符串, ,且长度不是常数且长度不是常数, ,也不是假定长度也不是假定长度( (* *) )。l外部函数返回结果是一个指针。外部函数返回结果是一个指针。l外部子程序形式参数外部子程序形式参数( (哑元哑元) )是一个数组片段。是一个数组片段。l外部子程序实在参数是关键字变元或是缺省的可选变元。外部子程序实在参数是关键字变元或是缺省的可选变元。l外部子程序扩展了赋值号的使用范围。外部子程序扩展了赋值号的使用范围。l外部子程序参数个数不确定。外部子程序参数个数不确定。l外

59、部子程序改变参数传递位置。外部子程序改变参数传递位置。 概述概述格式格式示例示例第28页/共36页第二十八页，编辑于星期五：十九点 五十分。1 2 . 1 1 2 . 1 接 口接 口 / / 示 例示 例12.1 接口PROGRAM main !PROGRAM main !主程序单元，求三个数最大值主程序单元，求三个数最大值 IMPLICIT NONEIMPLICIT NONE INTERFACE INTERFACE FUNCTION max3(a,b,c) FUNCTION max3(a,b,c) IMPLICIT NONE IMPLICIT NONE INTEGER max3,a,b,c

60、 INTEGER max3,a,b,c END FUNCTION END FUNCTION END INTERFACE END INTERFACE INTEGER x,y,z INTEGER x,y,z READ( READ(* *, ,* *) x,y,z) x,y,z WRITE( WRITE(* *, ,(1X,(1X,三个数的最大值为三个数的最大值为: :,I4),I4) max3(x,y,z) max3(x,y,z)ENDENDFUNCTION max3(a,b,c) !FUNCTION max3(a,b,c) !求三个数最大值外部函数子程序求三个数最大值外部函数子程序 INTEGE