программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 7. Рекурсия Анализ алгоритма показывает, что общее число сравнений и обменов пропор- ционально n log n. Витькины дубли на столе продолжали работать. Самый маленький был уже ростом с муравья». А. и Б. Стругацкие «Понедельник начинается в субботу» Контрольные вопросы по главе 7 1. Когда рекурсивные алгоритмы наиболее пригодны? 2. Когда следует избегать использовать рекурсию? 3. Почему нежелательно использовать присваивания значений глобальной пе- ременной в теле рекурсивной подпрограммы? 4. В чем заключается метод накапливающего параметра? 5. Пусть S n = 1 + 2 + 3 + . . . + n, n ⩾ 0. Напишите три варианта рекурсивной подпрограммы, вычисляющей S n А. Используйте рекурсивную функцию f(n) = S n Б. Используйте рекурсивную процедуру p(n:ineger; var y:integer), где y = S n В. Используйте рекурсивную функцию g(m, k) с накапливающим па- раметром k, где S n = g(n, 0). Рекомендуемая литература к главе 7 [1] Бауэр Ф. Л. Информатика. Вводный курс : в 2 ч. / Ф. Л. Бауэр, Г. Гооз. — М. : Мир, 1990. — Ч. 1. — 336 с. [2] Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. : Мир, 1985. — 405 с. Глава 8 ЗАПИСИ И ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 8.1 Записи 8.1.1 Определение комбинированных типов Запись (комбинированный тип) есть абстракция конечной по- следовательности элементов, но в отличие от массивов объеди- няет значения различных типов. Также в отличие от массивов компоненты записи обозначаются идентификаторами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Пример Для адекватного представления информации о некотором студенте необходима структура данных, состоящая из следующих элементов: • фамилия, имя, отчество — строки; • пол — перечислимый тип (два значения); • индекс специальности — целое число. type person = record name,secondName,surName:string; sex :(male,female); speciality:integer end; 140 Глава 8. Записи и динамические структуры данных Элементы записи называются полями. Каждое описание поля выглядит как описание простой переменной. Структура записи: • фиксированное число полей; • каждое поле имеет имя (уникальное в пределах записи, но может совпадать с любым идентификатором вне этой записи); • каждое поле имеет произвольный тип. Описание переменных комбинированного типа: var Sasha,Masha:person; Доступ к полям записи осуществляется с помощью селектора записи — кон- струкции вида <переменная типа записи>.<идентификатор поля> Использование: Sasha.name:= 'Александр'; Masha.name:= 'Мария'; Sasha.sex:=male; Masha.sex:=female; Masha.Speciality:=Sasha.Speciality; Можно создавать сложные структуры данных: массив записей или запись, в со- став которых входят записи. Пример var group:array[1..20] of person; Доступ к полям записей составляющий этот массив: group[i].sex:=female; if group[j].name= 'Борис' then writeln(group[j].surName); Пример Или, например, пусть о персоне требуется хранить информацию о дате рождения. type date=record month:(jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov, dec); day:1..31; year:1900..2005 end; person=record name,secondName,surName:string; 8.1 Записи 141 sex:(male,female); speciality:integer; birthDay:date end; Доступ к полям из элемента birthDay осуществляется с помощью повторного селектора записи: Sasha.birthDay.year:=1970; Masha.birthDay.month:=feb; Пример Определение комплексных чисел с помощью записи. type complex = record re,im:real end; procedure addc(c1,c2:complex;var c3:complex); {сложение комплексных чисел} begin c3.re:=c1.re+c2.re; c3.im:=c1.im+c2.im; end; 8.1.2 Оператор над записями with (оператор присоединения) В некоторых случаях использование селектора записи приводит к громоздким выражениям: var myDate:date; {переход к следующему месяцу} if myDate.month = dec then begin myDate.month := jam; myDate.year := myDate.year+1 end else myDate.month := succ(myDate.month); Для более краткой записи действий над полями записи используется опера- тор with. Оператор присоединения (with) — «выносит» общий для всех составных имен идентификатор записи в отдельный заголовок, после которого поля записи указываются только их идентификаторами. 142 Глава 8. Записи и динамические структуры данных Пример with myDate do if month=dec then begin month:=jan; year:=year+1 end else month:=succ(month); В общем виде: with <переменная записи> do begin ... end; Пример Комбинированный тип для представления экзаменационной ведомости (пред- мет, номер группы, дата экзамена, 25 строчек с полями: фамилия студента, номер его зачетной книжки, оценка за экзамен). type ведомость=record предмет:string; номергруппы:integer; дата: record число:1..31; месяц:1..12; год:integer end; студенты: array[1..25] of record фамилия:string; номерзачкнижки:integer; оценка:2..5 end end; Использование русского языка в идентификаторах в этом примере связано толь- ко с повышением ясности определения. Пример Комбинированный тип для представления игральной карты. type масть = (пики, трефы, бубны, червы); достоинство = (шесть, семь, восемь, девять, десять, валет, дама, король, туз); карта = record m:масть; d:достоинство end; 8.2 Динамические структуры данных 143 Логическая функция kill(k1, k2, km) проверяет, «бьет» ли карта k1 карту k2 с учетом того, что масть km является козырной. function kill(k1,k2:карта;km:масть):boolean; begin if k1.m = k2.m then kill:= k1.d > k2.d else kill:= k1.m = km end; 8.2 Динамические структуры данных 8.2.1 Ссылочный тип Характерная особенность рекурсивных структур данных, которая отличает их от основных структур (массивов, записей, множеств), — их способность изменять размер. Поэтому для рекурсивно определенных структур невозможно установить фиксированный размер памяти, и поэтому транслятор не может приписать ком- понентам такой переменной определенные адреса. Для решения этой проблемы чаще всего применяется метод динамического распределения памяти, т. е. выде- ление памяти для отдельных компонент в тот момент, когда они появляются во время выполнения программы, а не во время трансляции. В этом случае транс- лятор выделяет фиксированный объем памяти для хранения адреса динамически размещаемой компоненты, а не самой компоненты. К сожалению, при программировании на языке Паскаль программист вынуж- ден сам решать вопросы динамического распределения памяти, используя ссылоч- ный тип данных. Ссылочный тип определяется в виде type <имя ссылочного типа>= ∧ <имя базового типа>; Пример type mas=array[1..10] of integer; Ptr = ∧ integer; link = ∧ mas; linkchar = ∧ char; tie = ∧ real; 144 Глава 8. Записи и динамические структуры данных Пример Описание переменных ссылочного типа: var p:ptr; v:link; a: ∧ real; Значение ссылочного типа (неформально) — адрес в памяти, где располагается конкретное значение базового типа. Есть специальный указатель, который «нику- да не указывает». В адресном пространстве оперативной памяти выделяется один адрес, в котором заведомо не может быть размещена никакая переменная. На это место в памяти и ссылается такой пустой или «нулевой» указатель, который обо- значается служебным словом nil. Указатель nil считается константой, принадлежащей любому ссылочному ти- пу. Иными словами, это значение можно присваивать любому указательному типу. Рассмотрим операции над значениями ссылочного типа. • Сравнение на равенство (=), сравнение на неравенство (<>), — ссылаются ли два указателя на одно и то же место в памяти? Пример var p1,p2:ptr; sign:=p1=p2; if p1<>nil then ... • Разыменование — доступ к переменной по указателю. Для того, чтобы по указателю на переменную получить доступ к самой этой переменной, необходимо после переменной-указателя поставить знак ' ∧ '; p1 ∧ есть «переменная», на которую ссылается p1. Такая конструкция может находиться в любом контексте, в котором допустимо нахождение самой указываемой перемен- ной. Если p1 имеет тип ∧ integer , то p1 ∧ имеет тип integer. Разыменование некорректно, если ссылочная переменная имеет значение nil. Поэтому p1:=nil; p1 ∧ :=2; некорректно и приводит к трудно распознаваемым ошибкам. 8.2 Динамические структуры данных 145 Пример var p1,p2: ∧ integer; Пусть переменные p1 ∧ и p2 ∧ уже имеют значения 1 и 2 соответственно. Ре- зультаты присваиваний p1:=p2 и p1 ∧ :=p2 ∧ различны (рис. 8.1). Рис. 8.1 – Результаты присваиваний 8.2.2 Статические и динамические переменные Память для локальных переменных отводится при вызове подпрограммы, при выходе память освобождается. Память для глобальных переменных отводится в на- чале выполнения подпрограммы. Таким образом, память отводится под перемен- ные с учетом статической структуры программы, поэтому такие переменные назы- ваются статическими. Динамические переменные — это те, которые образуются и уничтожаются в про- извольный момент выполнения программы. Средство доступа к статическим переменным есть идентификатор. Динамиче- ские переменные, количество которых и место расположения в памяти неизвестно, невозможно обозначить идентификаторами. Средство доступа к динамическим пе- ременным — указатель на место их текущего расположения в памяти. Как создаются и уничтожаются динамических переменные? Процедура new(<переменная ссылочного типа>) предназначена для создания динамической переменной: • в динамической области памяти отводится место для хранения переменной, тип которой совпадает с базовым типом указателя-переменной; • переменной, переданной в параметре, присваивается указатель на отведен- ную область памяти. 146 Глава 8. Записи и динамические структуры данных Пример type mas=array[1..10] of integer; link= ∧ mas; var t:link; new(t); Отводится память, достаточная для хранения массива типа mas. Переменной t присваивается адрес этой памяти. Теперь возможен доступ к элементам массива, например: t ∧ [i]:=0; t ∧ [i]:=t ∧ [j]; Переменная t является статической, место в памяти для ее значения выде- лено при трансляции. Переменная t ∧ — динамическая, она появляется только при выполнении процедуры new(t). Процедура dispose(<переменная ссылочного типа>) служит для освобожде- ния памяти, отведенной с помощью процедуры new с той же переменной. Мы иллюстрируем применение процедур new и dispose (переменные p1 и p2 имеют тип ∧ integer ) при последовательном выполнении операторов на рис. 8.2. Рис. 8.2 – Создание и уничтожение динамических переменных 8.2.3 Линейные списки Рассмотрим создание и обработку структур данных, компоненты которых свя- заны явными ссылками. Особое значение придается структурам простой формы; приемы работы с более сложными структурами можно получить из способов ра- боты с основными видами структур: линейными списками и деревьями. 8.2 Динамические структуры данных 147 Самый простой способ соединить, или связать, множество элементов — это рас- положить их линейно в списке. В этом случае каждый элемент содержит только одну ссылку, связывающую его со следующим элементом списка. Пример Пусть тип link описан следующим образом: type link = ∧ node; node = record info:string; next:link end; var s,p:link; Мы можем создать с помощью этого типа список элементов типа link (рис. 8.3). Рис. 8.3 – Список из двух элементов Переменная — ссылка s указывает на первую компоненту списка. По-видимому, самое простое действие, которое можно выполнить со списком, это вставить в его начало некоторый элемент (рис. 8.4). new(p); p ∧ .info:= 'Петров'; p ∧ .next:=s; s:=p; Рис. 8.4 – Добавление элемента в начало списка Мы можем включать элементы в начало списка, в конец списка и в произволь- ное место списка. Рассмотрим эти операции по порядку. Операция включения элемента в начало списка определяет, как можно постро- ить список: начиная с пустого списка, последовательно добавляя элементы в его начало. Пример Пусть число связываемых элементов равно n. Тогда формировать список можно следующим образом: s:=nil; {начали с пустого списка} while n>0 do begin 148 Глава 8. Записи и динамические структуры данных new(p); p ∧ .next:=s; read(p ∧ .info); s:=p;n:=n −1 end; Это самый простой способ построения списка. Но при этом полученный по- рядок элементов обратен порядку их «поступления». В некоторых случаях это нежелательно; следовательно, новые элементы должны добавляться в конец списка. Мы можем добавлять элементы в конец линейного списка с помощью цикла и с помощью рекурсии. Нерекурсивная процедура немного сложнее. procedure add (var s:link; m:string); {s указывает на голову списка} var t,p:link; begin if s=nil then begin new(s); s ∧ .info:=m; s ∧ .next:=nil end else begin t:=s; while t ∧ .next <> nil do t:=t ∧ .next; new(p); t ∧ .next:=p; p ∧ .info:=m; p ∧ .next:=nil; end; end; var s:link; m:string; i:integer; begin s:=nil; for i:=1 to 10 do begin read(m); add(s,m) end; end. Хотя конец списка легко найти проходом по списку, такой непосредственный подход требует затрат, которые просто избежать, используя вторую ссылку q, кото- рая всегда указывает на последний элемент. Рекурсия для операций со списками естественней (потому, что списки — это рекурсивные структуры) и компактнее. Рекурсивное добавление элемента в конец списка задается процедурой addrec. procedure addrec(var s:link;m:string); begin if s=nil then begin new(s);s ∧ .info:=m;s ∧ .next:=nil end else addrec(s ∧ .next,m) end; Рассмотрим теперь ситуацию, когда элемент, на который указывает ссылка q, нужно включить в список после элемента, на который указывает ссылка p. Необ- ходимые присваивания значений ссылкам: q ∧ .next:=p ∧ .next; p ∧ .next:=q; Если требуется включение перед элементом, указанным p ∧ , а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку 8.2 Динамические структуры данных 149 нет «прохода» к элементам, предшествующим данному. Однако простой «трюк» позволяет решить эту проблему: k:=q ∧ .info; q ∧ :=p ∧ ; p ∧ .info:=k; p ∧ .next:=q; «Трюк» состоит в том, что новая компонента в действительности вставляется после p ∧ , но затем происходит обмен значениями между новым элементом и p ∧ Рассмотрим теперь задачу удаления элемента из списка. Мы удаляем элемент из списка, для которого поле info содержит указанную строку; если таких элементов несколько, то удаляется только первое вхождение. Здесь также возможны два подхода: нерекурсивный и рекурсивный. Сначала процедура с циклом. procedure del(var t:link;m:string); {из списка t убирается элемент m} var p1,p:link; begin if t ∧ .info=m then begin p:=t ∧ .next; dispose(t); t:=p end else begin p:=t; while (p ∧ .info<>m) and (p ∧ .next<>nil) do begin p1:=p; p:=p ∧ .next end; if p ∧ .info=m then begin p1 ∧ .next=p ∧ .next; dispose(p) end end end; Рекурсивная процедура удаления элемента из списка короче. procedure delrec(var s:link;m:string); var t:link; begin if s<>nil then begin if s ∧ .info=m then begin t:=s ∧ .next; dispose(s); s:=t end else delrec(s ∧ .next,m) end end; Перейдем к основной операции прохода по списку. Предположим, что опера- ция F должна выполняться с каждым элементом списка, первый элемент которого есть p ∧ . Эту задачу можно выразить следующим образом: while список, на который указывает p, не пуст do begin выполнить операцию F; перейти к следующему элементу end 150 Глава 8. Записи и динамические структуры данных Подробнее это действие описывается оператором while p<>nil do begin F(p ∧ ); p:=p ∧ .next end Из определения оператора цикла с предусловием и списковой структуры сле- дует, что F будет выполнено для всех элементов списка и ни для каких других. Очень частая операция — поиск в списке элемента с заданным ключом x. По- иск ведется строго последовательно. Он заканчивается, либо когда элемент найден, либо когда достигнут конец списка. Снова предположим, что начало списка обо- значено ссылкой p. Соответствующий цикл следующий while (p<>nil) and (p ∧ .info<>x) do p:=p ∧ .next; 8.2.4 Проблема потерянных ссылок Работа с динамическими переменными через указатели требует большей тща- тельности и аккуратности при проектировании программ. В частности, следует стремиться освобождать выделенные области сразу же после того, как необхо- димость в них отпадает, иначе «засорение» памяти ненужными динамическими переменными может привести к быстрому ее исчерпанию. Кроме того, необходимо учитывать еще одну проблему, связанную с противо- речием между стековым принципом размещения статических переменных и про- извольным характером создания и уничтожения динамических переменных. Рассмотрим следующий схематический пример программы: type PPerson= ∧ Person; Person= record end; procedure GetPerson; var P:PPerson; begin new(P) end; begin Writeln(MemAvail); GetPerson; Writeln(MemAvail) end. Вызов New в процедуре GetPerson приводит к отведению памяти для дина- мической переменной типа Person. Указатель на эту переменную присваивается переменной P. Рассмотрим ситуацию, возникающую после выхода из процедуры GetPerson . По правилам блочности все локальные переменные подпрограммы перестают существовать после ее завершения. В нашем случае исчезает локальная переменная P. Но, с другой стороны, область памяти, отведенная в процессе работы GetPerson , продолжает существовать, так как освободить ее можно только явно, посредством процедуры Dispose. Таким образом, после выхода из GetPerson отсутствует какой бы то ни было доступ к динамической переменной, так как единственная «ниточка», связывающая ее с программой, указатель P, оказался по- терянным при завершении GetPerson. Вывод на печать общего объема свободной памяти до и после работы GetPerson подтверждает потерю определенной области. Турбо-паскаль, как и многие другие языки программирования, не имеет встро- енных средств борьбы с засорением памяти неиспользуемыми динамическими пе- ременными. 8.2 Динамические структуры данных 151 Во всяком случае, нужно придерживаться правила, согласно ко- торому при выходе из блока необходимо или освободить все со- зданные в нем динамические переменные, или сохранить каким-то образом ссылки на них (например, присвоив эти ссылки глобаль- ным переменным). К описанной проблеме примыкает коллизия другого рода, заключа- ющаяся в ситуации, когда некоторая область памяти освобождена, а в программе остался указатель на эту область. Например, пусть ссылка p указывает на элемент списка и был выполнен оператор p:=nil или dispose(p). Несмотря на это, можно (неправиль- но) использовать далее в программе выражение p ∧ .next , но его значение непредсказуемо. 8.2.5 Списки специального вида Рассмотрим некоторые специальные списки: циклические, с двумя связями, стеки и очереди. Циклически связанный список обладает той особенностью, что связь его по- следнего узла не равна nil, а идет назад к первому узлу списка (рис. 8.5). В этом случае можно получить доступ к любому элементу, находящемуся в списке, от- правляясь от любой заданной точки; одновременно мы достигаем также полной симметрии, и теперь нам уже не приходится различать в списке «последний» или «первый» узел. Рис. 8.5 – Пример циклического списка Предположим, в узлах имеется два поля — info и next. Переменная связи Ptr указывает на самый правый узел списка, а Ptr ∧ .next является адресом самого левого узла. Следующие операции относятся к числу наиболее важных: a) Включить Y слева: new(p);p ∧ .info:=Y; p ∧ .next:=Ptr ∧ .next;Ptr ∧ .next:=p; b) Включить Y справа: Включить Y слева, а затем Ptr:=p; c) Присвоить Y значение из левого узла и исключить узел: p:=Ptr ∧ .next;Y:=p ∧ .info; Ptr ∧ .next:=p ∧ .next;dispose(p); |