Файл: А. Б. Шнейвайс основы программирования.pdf

В этой програме через оператор typedef struct candidat* link для типа указателя на struct candidat определён синоним link и описание поля next имеет вид: link next;. Причина в желании упростить и уни- фицировать описание типа рабочих переменных first, tek и nov (типа struct candidat*) и операцию приведения к типу struct candidat*
указателя типа void (получаемого функцией malloc). Использование псевдонима link (вместо struct candidat*), хоть и незначительно, но упростит исходный текст.
126

3.4
Понятие о указателях ФОРТРАНа
В простейшем случае указатель в ФОРТРАНе можно рассматривать как переменную, значением которой является ссылка на другой объект или указание об отсутствии такой ссылки.
1. Посредством указателей можно во время работы программы созда- вать в оперативной памяти динамические объекты, списки, де- ревья и т.д. Для объявления указателя в ФОРТРАНе используется атрибут pointer. Например,
integer, pointer :: p, q real, dimension (:), pointer :: inp pointer :: ptr(:,:)
2. Связь указателя с объектом можно установить:
1) либо посредством оператора allocate (при создании динамического объекта);
2) либо посредством оператора присваивания
3. Вид оператора присваивания для указателя отличается от обычного оператора присваивания и имеет вид указатель => адресат
Здесь адресат либо указатель; либо объект, на который можно ссылаться через указатель, либо ссылка на функцию, возвращаю- щую в вызывающую её единицу компиляции указатель.
4. Значением операнда-указателя служит значение объекта, связанно- го с ним в момент обращения.
5. Оператор nullify уничтожает связь указателя с объектом.
6. Оператор deallocate уничтожает и размещённые объекты, и связь с ними.
В качестве примеров использования указателей в ФОРТРАНе приведём две простые программы. Первая строит в оперативной памяти связный список и выводит его. Вторая решает задачу о считалке. Полезно сопо- ставить её ФОРТРАН-решение с СИ-решением.
127

3.4.1
Построение и вывод простого связного списка program testlist; use modlist; implicit none type (link), pointer :: top, cur integer i, k top=>NULL()
! инициализация указателя i=1; do; write(*,*) ’ введи ’,i,’-е число > 0’
read (*,*) k write(*,*) i,’-е число равно ’, k i=i+1; if (k/=0) then; allocate (cur)
cur%info= k
!/ или же так:
cur%next=>top
!\
cur=link(k,top)
top=>cur else; exit endif enddo call prtlist(top)
end module modlist; implicit none type link
! описание производного типа link (звено)
integer info
! имя информационного поля звена type (link), pointer :: next ! имя указательного поля звена end type link
! завершение описания типа link contains subroutine prtlist(top)
! описание подпрограммы вывода списка type(link), pointer :: top, cur ! top --- указатель на голову списка cur=>top
!
(формальный аргумент prtlist).
do while (associated(cur))
! cur --- локальная переменная для write(*,*) cur%info
!
хранения указателя на cur => cur%next
!
очередное звено списка.
enddo
! Пока cur"/="null() выводим cur%info end subroutine prtlist end module modlist
NULL([mold]) — функция связности указателя. Её вызов без ука- зания аргумента эквивалентен инициализации указателя, что означает установку статуса связности указателя на значение не связан. Функ- ция NULL() отсутствует в ФОРТРАНе-90 (в нём используется опера- тор nullify(pointer) — обнуление указателя pointer, точнее разрывает связь указателя с объектом).
При наличии аргумента функция NULL возвращает значение имею- щее тот же статус связности, что и аргумент (другими словами выраже- ние p=>NULL(q) преобразует статус связности указателя p на статус связности указателя q). Пока будем вызывать NULL() без аргумента.
128

3.4.2
Cхема функционирования программы testlist testlist строит односвязный список вида LIFO (Last In First Out, т.е. последним вошёл — первым вышел). Модуль modlist содержит описание производного типа link и подпрограммы prtlist вывода списка. testlist в цикле вводит положитель- ные значения целочисленной переменной k (нуль — признак завершения ввода). Для каждого введённого положительного программа выделяет область памяти под соот- ветствующее звено списка, помещая адрес звена в указатель cur. Далее info-полю звена присваивается значение k, а next-полю — значение указателя на предыдущее звено. Результат работы testlist при вводе чисел 4, 3, 2, 1, 0:
введи
1 -е число > 0 1 -е число равно
4
введи
2 -е число > 0 2 -е число равно
3
введи
3 -е число > 0 3 -е число равно
2
введи
4 -е число > 0 4 -е число равно
1
введи
5 -е число > 0 5 -е число равно
0 1
2 3
4
Как видно, содержимое информационных полей выводится prtlist в порядке обрат- ном порядку ввода чисел (последним вошёл — первым вышел). Аргументом проце- дуры служит указатель на головное звено списка (т.е. последнее заполненное).
1. F: type(link), pointer :: top, cur
|
С: link top, cur;
top cur
Отведены переменные top и cur для размещения указателей на данные типа link. Значения top и cur пока не заданы.
2. F: top=>NULL()
|
С: top=NULL;
top cur null
Теперь top смотрит на null — код завершения лю- бого списка. Значение указателя cur по-прежнему не задано.
129

3. F: i=1; read(*,*) k
С: scanf(”%d”,&k); Первое введённое значение переменной k, равно 4.
Далее предстоит занести его в info-поле данного типа link, под которое память пока не выделена.
4. allocate(cur)
top null cur inf o next top по-прежнему смотрит на null. Но cur те- перь смотрит на область памяти, предназна- ченную для размещения нового данного типа link (первого звена списка), т.е. структуры из двух полей inf o и next. Правда, пока в эти поля ничего не занесено (но место под них выделено и адресовано оператором allocate).
5. cur=link(k,top) или, что то же, cur%info=k; cur%next=>top top null cur
4
inf o next
Теперь звено, адресуемое cur, заполнено: в inf o-поле — значение переменной k, а в next- поле — значение указателя top (т.е. next-поле первого звена смотрит туда же, куда и top —
в null, который фиксирует окончание строяще- гося списка). Поэтому в top теперь можно по- местить адрес первого звена списка, который пока хранится в cur.
6. top=>cur.
top null cur
4
inf o next
После top=>cur указатель top уже адресует голову списка. Её же пока адресует и cur. Од- нако, теперь cur может быть использовать для фрахтовки места под новое звено, если таковое потребуется.
7. i=2; read(*,*) k. Второе введённое значение переменной k равно 3.
8. allocate(cur)
top null cur
4
inf o next inf o next top по-прежнему хранит адрес первого звена,
т.е головы предшествующего списка. Однако cur уже адресует новое звено и теперь его нуж- но заполнять.
130

9. cur=link(k,top) или, что то же, cur%info=k; cur%next=>top top null
4
inf o next
3
cur top пока хранит адрес головы старого списка.
Но поля нового (второго) звена уже заполнены.
Так что, если поместить в top адрес начала вто- рого звена, то top (как и cur) станет адресовать список из уже двух звеньев.
10. top=>cur)
top null
4
inf o next
3
cur
Теперь top уже адресует голову двузвенного списка, и, значит, можно (если нужно) исполь- зовать cur для адресации нового звена типа link.
11. i=3; read(*,*) k; allocate(cur).
top null
4
inf o next
3
cur
Третье введённое значение переменной k рав- но 2. allocate(cur) находит место для нового
(третьего) звена типа link.
131

12. cur=link(k,top) или, что то же, cur%info=k; cur%next=>top top null
4
inf o next
3 2
cur
Трёхзвенный список, по существу дела, уже имеется. Правда, он адресуется указателем cur,
который используется в качестве рабочего. Для адресации нового головного звена через указа- тель top необходимо присвоить top значение указателя cur.
13. top=>cur top null
4
inf o next
3 2
cur
Добавим ещё одно звено в голову списка, при- ведя окончательную схему к виду, соответству- ющему данным 4, 3, 2, 1, указанным в нвчале этого параграфа.
14. i=4; read(*,*) k; allocate(cur); cur=link(k,top); top=>cur.
top null
4
inf o next
3 2
1
cur
Теперь top адресует голову списка, состоящего из четырёх звеньев.
132

15. i=5; read(*,*) k. Пятое введённое значение переменной k равно
0, который инициирует выход из цикла.
3.4.3
Cхема функционирования подпрограммы prtlist
1. cur=>top; do while (associated(cur)
null
4 3
2 1
cur top
В качестве аргумента prtlist использует top
— указатель на голову списка. Не будем ис- пользовать непосредственно top для адреса- ции очередного звена списка — ведь факти- чекие аргументы ФОРТРАН-процедур пере- даются по ссылке (а не по значению, как в
СИ). Поэтому внутри prtlist описан вспомо- гательный локальный указатель cur, который и используется для адресации. Далее работа- ет заголовок оператора цикла с предусловием,
вызывающим встроенную булеву ФОРТРАН- функцию associated, которая проверяет ста- тус связности указателя cur с каким-либо ад- ресатом. Если cur связан с полноправным оче- редным звеном списка, то возвращается .true.;
если же cur указывает на null — .false.. При
.true. оператор write(*,*) cur%info выведет
1
, после чего оператор cur=>cur%next пе- реключит cur на обзор предыдущего звена.
2. cur=>cur%next null
4 3
2 1
cur top
После того как выведено содержимое информа- ционного поля текущего звена списка, cur пере- настраивается на адресацию следующего звена.
Поскольку и для него associated(cur) ≡ .true.,
то после write(*,*) cur%info выведет
2 133

3. cur=>cur%next null
4 3
2 1
cur top
Теперь будет выведено
3 4. После очредного cur=>cur%next оператор write(*,*) cur%next выведет
4 5. cur=>cur%next null
4 3
2 1
cur top
Наконец, когда associated(cur) = .false. цикл прекратится и подпрограмма prtlist завершит свою работу.
134

3.4.4
Задача о считалке program testring; implicit none type candidat integer number type (candidat), pointer :: next end type candidat integer j, k, m, n, nfirst;
type (candidat), pointer :: first, tek, nov n=5
! число кандидатов m=3
! число слов в считалке allocate(first)
! Адресуем память под первое звено типа candidat.
first%number=1
! В поле number запомнен номер звена.
first%next=>first ! в поле next запомнен указатель на первое звено,
! т.е. кольцевой список из одного звена построен.
tek=>first
! Указатель на текущее звено (вначале первое).
do k=2,n allocate(nov)
! Адресуем память под новое (k-ое) звено.
nov%number=k
! В number-поле k-ого звена --- его номер.
tek%next=>nov
! В next-поле (k-1)-ого --- указатель на k-ое.
tek=>nov
! Теперь текущим становится k-ое звено.
enddo
! Сейчас в tek указатель на последнее (n-ое) звено.
tek%next=>first
! В next-поле n-го звена --- указатель на первое.
nullify(nov,first)! Разрыв связи указателей nov и first c адресатами
! c целью показать, что это не помешает дальнейшему
! поиску.
do k=n,2,-1
! Пока не останется один человек (водящий)
! повторяем:
do j=1,m-1
! проговор m-1 слова считалки, получая в tek tek=>tek%next ! указатель на игрока, который должен выбыть.
enddo
! Выбытие достигается присваиванием tek%next=>tek%next%next ! next-полю предшествующего звена
! значения указателя из next-поля
! удаляемого. При этом звено, удаляемое из
! списка становится недоступным и данной enddo
! программе, и операционной системе (ведь
! указатель на него, ранее хранящийся
! в next-поле предыдущего звена, уже
! затёрт).
write(*,*) ’ Водит игрок под номером ’,&
! Вывод номера tek%number
! водящего игрока end
135

3.4.5
Cхема построения кольцевого списка
1. type (candidat), pointer :: first, tek, nov first tek nov
Описаны переменные first, tek и nov для раз- мещения указателей на звенья cтруктуры типа type(candidat). Значения first, tek и nov пока не заданы.
2. n=5; m=3
n=5 — число кандидатов. m=3 — число слов.
3. allocate(first)
first tek nov first адресует место для пер- вого звена, которое в дальней- шем должно будет хранить ин- формацию о первом кандида- те, точнее, о том кандидате, с которого начнём проговаривать считалку (информация в поля звена пока не занесена)
4. first%number=1
first
1
tek nov
В number-поле занесён номер первого кандидата (можно бы- ло бы построить кольцевой спи- сок из одного звена посредством first%next=>first).
136

5. tek=>first first
1
tek nov
Для построения кольцевого списка используем указатели tek и nov. first потребует- ся лишь для ссылки послед- него звена кольцевого списка на первое. Теперь tek обозре- вает то же звено, что и first.
6. k=2; allocate(nov)
first
1
tek nov
Место для ново- го звена (второго игрока) адресует nov, но содержи- мое полей этого звена пока не за- дано.
7. nov%number=k; tek%next=>nov first
1
tek nov
2
Теперь номер вто- рого игрока запи- сан в number-поле второго звена и в next-поле первого звена записан ука- затель на второе.
137

8. tek=>nov first
1
tek nov
2
tek адресует уже второе звено, так что nov готово к поиску места для третьего.
9. k=3; allocate(nov)
first
1
tek nov
2
nov адресует тре- тье звено (пока не заполненное).
10. nov%number=k; tek%next=>nov first
1
tek nov
2 3
В number-поле звена, адресуемо- го nov, записан номер игрока, а в next-поле второ- го звена помещён указатель на тре- тье звено.
138

11. tek=>nov first
1
tek nov
2 3
tek переключён на обзор третьего звена, чтобы nov можно было пере- ключить на поиск четвёртого.
12. k=4; allocate(nov)
first
1
tek nov
2 3
nov хранит ука- затель на четвёр- тое звено (пока пустое).
13. nov%number=k; tek%next=>nov first
1
tek nov
2 3
4
Теперь заполнены number-поле чет- вёртого звена и next-поле третье- го.
139

14. tek=nov first
1
tek nov
2 3
4
Теперь nov мож- но будет исполь- зовать для ад- ресации нового
(пятого) звена,
поскольку после tek%next=>nov указатель tek хранит ссылку на четвёртое звено.
15. k=5; allocate(nov)
first
1
tek nov
2 3
4
nov хранит указа- тель на пятое зве- но (пока пустое).
140

16. nov%number=k; tek%next=>nov first
1
tek nov
2 3
4 5
Занесён номер пятого игрока в number-поле пя- того звена и ука- затель на пятое звено в next-поле четвёртого звена.
17. tek%next=>first first
1
tek nov
2 3
4 5
next-поле пято- го звена хранит указатель на пер- вое — кольцевой список из пяти звеньев завершён.
18. nullify(nov). Для поиска номера водящего, вообще говоря, указатель nov не нужен. Посредством оператора nullify разорвём его связь с пятым звеном (что- бы не загромождать в дальнейшем схему ссылок поиска водящего). Значение указателя tek, указывающее на последнее звено кольца, предполагает, что про- говор читалки начнётся с первого звена. Другими словами, поиск водящего может обойтись и без указателя first — ведь звено, указываемое через посред- ство first, указывается ещё и через посредство tek%next последнего звена.
Поэтому, чтобы не загромождать схему ссылок, разорвём связь first с первым звеном nullify(first). Проверить разрыв связи указателя с объектом можно по- средством логической функции associated(имя_указателя). В ФОРТРАНе-
95 наряду с оператором nullify имеется ещё и функция null, действие которой при отсутствии аргумента эквивалентно действию nullify.
141

3.4.6
Cхема функционирования поиска водящего
1. k=5; do j=1,m-1; tek=>tek%next; enddo.
1 5
2
tek
4 3
На предыдущем рисунке ука- затель tek адресовал послед- нее пятое звено. После отработ- ки цикла do j=1,2 содержи- мым tek будет указатель храня- щийся в next-поле первого зве- на, т.е. tek станет адресовать второе звено (см. рисунок сле- ва). Третье слово считалки —
последнее. Поэтому третье зве- но нужно будет исключить из кольцевого списка, поместив в next-поле второго звена указа- тель из next-поля третьего.
2. tek%next=>teh%next%next
1 5
2
tek
4 3
Третье звено исключено из кольцевого списка, но место в оперативной памяти оно про- должает занимать, причём указатель его расположения,
ранее хранившийся в next-поле второго звена уже затёрт ука- зателем на четвёртое звено.
Поэтому наша программа и са- ма потеряла доступ к третьему звену, и не отдала его место операционной системе (коро- че, повела себя как собака на сене: и сама не ест, и другим не даёт). Тем не менее поиск водящего программа может продолжать.
142