программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 8. Записи и динамические структуры данных Внимательный читатель заметит, что мы допустили серьезную ошибку в опе- рациях (a), (b) и (c). Мы не учли, что список может быть пустым (Ptr=nil). Для этого необходимо ввести очевидные изменения. Циклические списки можно использовать не только для представления струк- тур, которым свойственна цикличность, но также для представления линейных структур; циклический список с одним указателем на последний узел, по суще- ству, эквивалентен простому линейному списку с двумя указателями на начало и конец. В связи с этим наблюдением возникает естественный вопрос: Как най- ти конец списка, имея в виду круговую симметрию? Пустой связи nil, которая отмечает конец, не существует. Проблема решается так: если мы выполняем неко- торые операции, двигаясь по списку от одного узла к следующему, то мы должны остановиться, когда мы вернулись к исходному месту (предполагая, конечно, что исходное место все еще присутствует в списке). Чтобы достичь еще большей гибкости в работе с линейными списками, мы можем включить в каждый узел две связи, указывающие на элементы, находящиеся по обе стороны от данного узла (рис. 8.6). Здесь Left и Right — переменные, указывающие на левый и правый концы списка. Рис. 8.6 – Список с двумя связями В каждом узле списка имеются две связи, назовем их, например, Llink и Rlink. Списки с двумя связями занимают обычно больше пространства памяти, чем односвязные. Дополнительные операции, которые можно теперь эффективно выполнять, дают часто более чем достаточную компенсацию за повышенные тре- бования к памяти. Помимо очевидного достоинства, состоящего в том, что при просмотре списков с двумя связями можно продвигаться как вперед, так и назад. Еще одним новым важным преимуществом является возможность исключения уз- ла, на который указывает ссылка X, из списка, в котором он находится, если задано только значение X: (X ∧ .Llink) ∧ .Rlink:=X ∧ .Rlink; (X ∧ .Rlink) ∧ .Llink:=X ∧ .Llink; dispose(X); Совершенно аналогично в список с двумя связями можно легко включить узел, соседний узлу X, как слева, так и справа. Операторы new(P); P ∧ .Rlink:=X ∧ .Rlink; P ∧ .Llink:=X; (X ∧ .Rlink) ∧ .Llink:=P; X ∧ .Rlink:=P; выполняют такое включение справа от узла X; меняя местами левые и правые связи, мы получаем соответствующий алгоритм для включения слева. 8.2 Динамические структуры данных 153 8.2.6 Стеки и очереди Очень часто встречаются линейные списки, в которых включение, исключение или доступ к значениям почти всегда производятся в первом или последнем узлах, и мы дадим им специальные названия: Стек — линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка (рис. 8.7). Рис. 8.7 – Стек Очередь — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце (рис. 8.8). Из стека мы всегда исключаем «младший» элемент из имеющихся в списке, т. е. тот, который был включен позже других («last-in-first-out» — «последний пришел — первый ушел»). Для очереди справедливо в точности противоположное правило: исключается всегда самый «старший» элемент; узлы покидают список в том по- рядке, в котором они в него вошли («first-in-first-out» — «первый пришел — первый ушел»). Рис. 8.8 – Очередь Стеки очень часто встречается на практике. При решении задач наш мозг ведет себя как «стек»: одна проблема приводит к другой, а та в свою очередь к сле- дующей; мы накапливаем в стеке эти задачи и подзадачи и удаляем их по мере того, как они решаются. Аналогично процесс входов в подпрограммы и выходов из них при выполнении машинной программы подобен процессу функционирова- ния стека. Стеки особенно полезны при обработке языков, имеющих архитектуру вложений. К ним относятся языки программирования, арифметические выражения. Вообще, стеки чаще всего возникают в связи с алгоритмами, имеющими явно или неявно рекурсивный характер. 154 Глава 8. Записи и динамические структуры данных Рассмотрим преобразование с помощью стека рекурсивной программы «Ха- нойские башни» к нерекурсивному виду. Напомним исходную программу: procedure Tower(i,m,n,p:integer); {перекладываем i верхних колец с иглы m на иглу n, используя иглу p как вспомогательную} begin if i=1 then writeln(‘сделать ход’, m’->‘,n) else begin Tower(i −1,m,p,n); writeln(‘сделать ход’, m’->‘,n); Tower(i −1,p,n,m) end end; Видно, что задача «переложить i верхних дисков с иглы m на иглу n» сводится к трем задачам того же типа: двум задачам с i − 1 дисками и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что еще осталось делать. Для этой цели заведем стек со следующим типом элементов type solve = record i,m,n,p:integer end; Каждая такая запись вершина стека. Стек можно реализовать с помощью линейного списка. Получаем такую программу: procedure Tower(i,m,n,p:integer); {перекладываем i верхних колец с иглы m на иглу n, используя иглу p как вспомогательную} begin {сделать стек заказов пустым} {положить в стек запись while {стек не пуст} do begin {удалить верхний элемент, переложив его в if j=1 then writeln(‘сделать ход’, x, ’->‘,y) else begin {положить в стек записи: <1,x,y,z> end end end; Заметим, что первой в стек кладется запись, которую надо выполнять последней. 8.2 Динамические структуры данных 155 8.2.7 Деревья Определим формально дерево как конечное множество T, состоя- щее из одного или более узлов, удовлетворяющих следующим свой- ствам. • Имеется один специальный узел, называемый корнем дан- ного дерева. • Остальные узлы (исключая корень) содержатся в m ⩾ 0 попарно не пересекающихся множествах T 1 ,. . ., T m , каж- дое из которых в свою очередь является деревом. Деревья T 1 ,. . ., T m называются поддеревьями данного дерева. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Из нашего определения следует, что каждый узел дерева является корнем неко- торого поддерева, которое содержится в этом дереве. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется кон- цевым узлом, или листом. Дерево называется бинарным, если каждый узел имеет степень не больше двух. Но обычно бинарное дерево определяется несколько иначе. Например, рас- смотрим бинарные деревья с базовым типом integer. Бинарное дерево либо пусто, либо состоит из узла, содержащего целое число, и левого и правого поддеревьев, являющихся бинарны- ми деревьями. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Соответствующее определение типа бинарное дерево, использующее ссылки, следующее: type tree = ∧ node; {ссылка на узел дерева} node = record {узел дерева} info:integer; left,right:tree end Пустое дерево обычно обозначается ссылкой nil. На рис. 8.9 изображено одно из бинарных деревьев. Узел с числом 7 является корнем дерева. Дерево обычно изображают корнем вверх. Узлы, имеющие только пустые поддеревья, называются листьями (в данном дереве это узлы: 15, 2, 100 и 10). Пустые поддеревья листьев не показаны. Каждый узел поддерева имеет свой уровень, который определяется рекурсивно: • уровень корня бинарного дерева равен 0; • если уровень узла равен n, то уровни корней левого и правого поддеревьев равны n+1. 156 Глава 8. Записи и динамические структуры данных Рис. 8.9 – Пример бинарного дерева Обход дерева До конца раздела будем рассматривать только бинарные деревья, поэтому при- лагательное бинарное будем опускать. Имеется много задач, которые можно выполнять на древовидной структуре: распространенная задача — выполнение заданной операции P с каждым элементом дерева. Здесь P рассматривается как параметр более общей задачи посещения всех узлов, или, как это обычно называют, обхода дерева. Если рассматривать эту задачу как единый последовательный процесс, то от- дельные узлы посещаются в некотором определенном порядке и могут считаться расположенными линейно. В самом деле, описание многих алгоритмов существен- но упрощается, если можно говорить о переходе к следующему элементу дерева, имея в виду некоторое упорядочение. Существуют три принципа упорядочения, которые естественно вытекают из структуры деревьев. Так же как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Пусть R обозначает корень, а A и B левое и правое поддеревья, тогда можно определить такие три упорядочения: • сверху вниз: R, A, B (посетить корень до поддеревьев); • слева направо: A, R, B; • снизу вверх: A, B, R (посетить корень после поддеревьев). Обходя дерево из рис. 8.9 и выписывая числа, находящиеся в узлах, в том порядке, в котором они встречаются, мы получаем следующие последовательности: • сверху вниз: 7, 9, 15, 27, 2, 13, 3, 100, 10; • слева направо: 15, 9, 2, 27, 7, 13, 100, 3, 10; • снизу вверх: 15, 2, 27, 9, 100, 10, 3, 13, 7. Теперь выразим эти три метода обхода как три конкретные программы с явным параметром t, означающим дерево, с которым они имеют дело, и неявным парамет- 8.2 Динамические структуры данных 157 ром P, означающим операцию, которую нужно выполнить с каждым узлом. Эти три метода легко сформулировать в виде рекурсивных процедур; они вновь служат примером того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. procedure preorder(t:tree); begin if t <> nil then begin P(t); preorder(t ∧ .left); preorder(t ∧ .right) end end; procedure postorder(t:tree); begin if t<>nil then begin postorder(t ∧ .left); postorder(t ∧ .right); P(t) end end; procedure inorder(t:tree); begin if t<>nil then begin inorder(t ∧ .left); P(t); inorder(t ∧ .right) end end; Поиск по дереву с включением Бинарные деревья часто используются для представления множества данных, элементы которых ищутся по уникальному, только им присущему ключу. Если дерево организовано таким образом, что для каждого узла t все ключи в левом поддереве меньше ключа t, а ключи в правом поддереве больше ключа t, то это дерево называется деревом поиска. В дереве поиска можно найти место каждо- го ключа, двигаясь, начиная с корня и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа. Возможности техники динамического размещения переменных с доступом к ним через ссылки демонстрируются в задачах, в которых сама структура дерева изменяется, т. е. дерево растет и/или уменьшается во время выполнения программы. Хорошим примером этого является задача построения частотного словаря. В этой задаче задана последовательность слов, и нужно установить число появ- лений каждого слова. Это означает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появлений, если нет — в дерево вставляется новое слово (с начальным значением счетчика, рав- ным 1). Для простоты будем использовать целые числа в качестве слов. Предлагаются следующие описания типов: type tree = ∧ word; word = record key:integer; count:integer; 158 Глава 8. Записи и динамические структуры данных left,right:tree end; Пусть у нас есть исходный файл ключей f, а переменная root указывает на корень дерева поиска, мы можем записать программу следующим образом: root:=nil; reset(f); while not eof(f) do begin read(f,x); search(x,root) end Процесс поиска с включением представлен в виде рекурсивной процедуры search : procedure search(x:integer;var p:tree); begin if p=nil then begin {слова нет в дереве;включить его} new(p); with p ∧ do begin key:=x;count:=1;left:=nil;right:=nil end end else if x ∧ .key then search(x,p ∧ .left) else if x>p ∧ .key then search(x,p ∧ .right) else p ∧ .count:=p ∧ .count+1 end Для входной последовательности 8, 9, 11, 15, 7, 3, 2, 1, 5, 6, 4, 10 программа строит бинарное дерево поиска (рис. 8.10). Рис. 8.10 – Упорядоченное бинарное дерево Контрольные вопросы по главе 8 159 Сортировка деревом Хотя задача предыдущего алгоритма — поиск, его можно применить и для сор- тировки. Действительно, после того как входной файл ключей запишется в дерево поиска, мы можем получить отсортированную последовательность, обходя дерево методом слева направо и печатая в данном порядке ключи: procedure print(t:tree); begin if t<>nil then begin print(t ∧ .left); write(t ∧ .key:5); print(t ∧ .right) end end Вызов этой процедуры с параметром, равным корню построенного дерева, выдаст отсортированную последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 15. Эта сортировка так же быстра, как быстрая сортировка Хоара. Кроме того, данную сортировку удобно применять для сортировки файлов: читаем последовательность элементов из файла и создаем упорядоченное бинарное дерево, потом обходим его и записываем элементы в новый файл. Контрольные вопросы по главе 8 1. Описать тип записи для представления следующего понятия: а) время в часах, минутах и секундах; б) данные из медицинской карты (фамилия, имя, отчество, пол, возраст); в) адрес (город, улица, дом, квартира); г) бланк требования на книгу в библиотеке (сведения о книге: шифр, автор, название; сведения о читателе: номер читательского билета, фамилия; дата заказа). 2. Ответьте на следующие вопросы: а) Верно ли, что все поля записи должны быть разных типов? б) Почему при описании записи её поля могут перечисляться в любом порядке? в) Верно ли, что названия полей записи могут совпадать с именами пе- ременных, констант и других объектов программы, но не могут сов- падать с названиями полей других записей? г) Почему в переменной-поле (т. е. конструкции r.f) имя поля (f ) долж- но указываться явно и не может быть задано в виде выражения? 3. type ref = ∧ integer; var p,q: ref; 160 Глава 8. Записи и динамические структуры данных Пусть переменные p и q получили значения после выполнения следующих операторов: new(p); new(q); p ∧ := 5; q ∧ := 3; Ответьте на следующие вопросы: а) Что является значением переменной p: ссылка на объект (переменную) целого типа или сам этот объект? Что обозначает переменная p ∧ : ссыл- ку на объект целого типа, сам этот объект или целое 5? Каковы типы переменных p и p ∧ ? б) Что будет выдано на печать в результате выполнения следующих опе- раторов? p ∧ := q ∧ ; if p = q the p = nil else if p ∧ = q ∧ then q := p; if p = q then q ∧ := 4; writeln(p ∧ ); 4. Почему объекты (переменные), создаваемые процедурой new и уничтожае- мые процедурой dispose, называют динамическими? Почему им не дают имена? 5. Имеется описание var x: ∧ boolean; y: booolean; Можно ли переменной x присвоить ссылку на переменную y? Можно ли с помощью процедуры dispose уничтожить переменные x и y? Рекомендуемая литература к главе 8 [1] Кнут Д. Искусство программирования / Д. Кнут. — 3-е изд. — М. : Вильямс, 2005. — Т. 1 : Основные алгоритмы. — 712 с. [2] Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с. [3] Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. : Мир, 1985. — 405 с. Глава 9 МОДУЛИ И ГРАФИКА 9.1 Модули 9.1.1 Модульное программирование Понятие модуля или, в общем случае, модульного программирования возникло на определенном этапе развития программирования и было обусловлено, в первую очередь, возрастающими объемами программ, их увеличивающейся внутренней сложностью и коллективным характером разработок. Модули — независимо храни- мые и разрабатываемые, независимо компилируемые и тестируемые программные единицы со строго определенными интерфейсами, которые могут объединяться с главной программой. Модуль — совокупность программных ресурсов (констант, типов, переменных, подпрограмм), предназначенных для использования другими модулями и программами. Сам модуль не выполняется, используются только его объекты. Ресурсы модуля делятся на две части: • Интерфейс — то, что используется в других модулях и программах. Сюда входит описание объектов, доступных (видимых) из других программ. • Реализация — то, что используется только в данном модуле. Эта часть со- держит описание объектов, недоступных (невидимых, скрытых) от других программ. Модуль в общем виде имеет следующее представление. unit Unitname; {имя модуля — произвольный идентификатор; этот модуль должен храниться в файле с тем же именем, в данном случае, в файле с именем unitname.pas} interface {описание видимых объектов} implementation {описание скрытых объектов} begin 162 Глава 9. Модули и графика {здесь могут присутствовать операторы, инициализирующие объекты модуля; установка значений переменных} end. Следующий пример модуля содержит только интерфейсную часть. unit Calendar; interface type Days = (Mon, Tue, Wed, Thu, Fri, Sat, Sun); WorkingDays = Mon..Fri; Months = (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec); Summer = jun..aug; Autumn = sep..nov; Spring = mar..may; DayNo = 1..31; YearNo = 1900..2000; Date = record Day: DayNo; Month : Months; Year : YearNo; end; implementation begin end. Если какая-то функция из модуля будет использоваться в других модулях или программах, то ее определение разбивается на две части. В интерфейс модуля помещается заголовок функции, а в реализацию — ее тело. Следующий пример модуля реализует действия над комплексными числами. unit Comp; interface type Complex = record Re, Im: real;end; procedure InitC (var C: Complex; R, I: real); {создание комплексного числа} procedure AddC (C1, C2: Complex; var C3: Complex); {сложение целых чисел} implementation procedure InitC (var C: Complex; R, I: real); begin with C do begin Re:=R; Im:=I end end; procedure AddC (C1, C2: Complex; var C3: Complex); begin with C3 do begin Re := C1.Re + C2.Re; Im := C1.Im + C2.Im end; end; 9.1 Модули 163 begin end. Модификация реализации при прежнем интерфейсе никак не отражается на программах, использующих модули. Прежде чем модуль можно использовать в программах, его необходимо отком- пилировать. Если модуль содержится в файле name.pas, то в результате компи- ляции образуется дисковый файл name.tpu. Если программа использует объекты из модулей u1, u2, u3, то первой строкой в программе (после возможного заголовка программы) должна быть директива для компилятора uses u1, u2,u3; Если модуль использует другие модули, то это задается с помощью такой же директивы. unit u; interface uses u1,u2,u3; Пример uses Comp; var C1,C2,C3: Complex; begin InitC(C1,1,2); InitC(C2,3, −5); AddC(C1,C2,C3); end. Наиболее часто используемые модули (так называемые стандартные модули) хранятся в библиотеке — файле turbo.tpl. С помощью служебной программы Tpumover пользователь может включить в библиотеку и какой-то собственный модуль. Приведем пример полезного модуля, реализующего операции со стеком. unit StackOps; {операции над стеком целых чисел} interface procedure Push (Elem: integer); {добавление элемента в стек} function Pop: integer; {извлечение элемента из стека} function Empty: boolean; {проверка стека на пустоту} function Full: boolean; {проверка стека на переполнение} implementation {Стек реализован в виде линейного массива целых элементов. Переменная Top отмечает позицию стека над вершиной.} |