Главная Промышленная автоматика.

в листинге 1.1 вы легко вьщелите средства нашего псевдоязыка. Мы применяем полркирное начертание для зарезервированных ключевых слов языка Pascal, которые имеют тот же смысл, что и в стандартном языке Pascal. Написание строчными буквами таких слов, как GRAPH (Граф) и SET (Множество), указывает на имена абстрактных типов данных. Их мокно определить с помощью объявления типов языка Pascal и операторов, соответствующих абстрактным типам данных, которые задаются посредством процедур языка Pascal (эти процедуры должны входить в окончательный вариант программы). Более детально абстрактные типы данных мы рассмотрим в следующих двух разделах этой главы.

Управляющие конструкции языка Pascal, такие как if, for и while, могут применяться в операторах псевдоязыка, но условные выражения в них (как в строке (3)) могут быть неформальными, в отличие от строгих логических выражений Pascal. Также и в строке (1) в правой части оператора присваивания применяется неформальный символ. Еще отметим, что оператор цикла for в строке (2) проводит повторные вычисления по элементам множества.

Чтобы стать исполняемой, программа на псевдоязыке должна быть преобразована в программу на языке Pascal. В данном случае мы не будем приводить все этапы такого преобразования, а покажем только пример преобразования оператора if (строка (3)) в более традиционный код.

Чтобы определить, имеет ли вершина v соединение с какой-либо вершиной из newclr, мы рассмотрим кавдый элемент w из newclr и по графу G проверим, существует ли ребро мевду вершинами v и w. Для этого используем новую булеву переменную found (поиск), которая будет принимать значение true (истина), если такое ребро существует. Листинг 1.2 показывает частично преобразованную программу листинга 1.1.

Листинг 1.2. Частично преобразованная программа greedy

procedure greedy ( var G: GRAPH; var newclr: SET ) ; begin

(1) newclr 0;

(2) for для каждой незакрашенной вершины v из G do begin

(3.1) found:= false;

(3.2) for для каждой вершины w из newclr do

(3.3) if суш:ествует ребро между v и w then

(3.4) found:= true;

(3.5) if found = false then begin

{ V не соединена ни с одной вершиной из newclr }

(4) пометить v цветом;

(5) добавить V в newclr end

end; { greedy }

Обратите внимание, что наш алгоритм работает с двумя множествами вершин. Внешний цикл (строки (2) - (5)) выполняется над множеством незакрашенных вершин графа G. Внутренний цикл (строки (3.2) - (3.4)) работает с текущим множеством вершин newclr. Оператор строки (5) добавляет новые вершины в это множество.

Существуют различные способы представления множеств в языках программирования. В главах 4 и 5 мы изучим несколько таких представлений. В этом примере мы можем представить кавдое множество вершин посредством абстрактного типа LIST (Список), который можно выполнить в виде обычного списка целых чисел, ограниченного специальным значением null (для обозначения которого мы будем использовать число 0). Эти целые числа могут храниться, например, в массиве, но есть и другие способы представления данных типа LIST, которые мы рассмотрим в главе 2.

Мы отличаем абстрактный тип данных SET от встроенного типа данных set языка Pascal. 1.1. ОТ ЗАДАЧИ К ПРОГРАММЕ 21



Теперь можно записать оператор for в строке (3.2) в виде стандартного цикла по условию, где переменная w инициализируется как первый элемент списка newclr и затем при каждом выполнении цикла принимает значение следующего элемента из newclr. Мы также преобразуем оператор for строки (2) листинга 1.1. Измененная процедура greedy представлена в листинге 1.3. В этом листинге есть еще операторы, которые необходимо преобразовать в стандартный код языка Pascal, но мы пока ограничимся сделанным. D

Листинг t .3. Измененная профамма greedy

procedure greedy ( var G: GRAPH; var newclr: LIST ) ;

{ greedy присваивает переменной newclr множество вершин графа G, которые можно окрасить в один цвет }

found: boolean; V, w: integer; begin

newclr := O;

v:- первая незакрашенная вершина из G; while V о null do begin found: = false;

w: = первая вершина из newclr while wo null do begin

if существует ребро между vh w then found:= true;

w: = следующая вершина из newclr;

end;

if found = false then begin пометить V цветом; добавить V в newclr

v:= следующая незакрашенная вершина из G;

end;

end; { greedy )

Резюме

На рис. 1.4 схематически представлен процесс программирования так, как он трактуется в этой книге. На первом этапе создается модель исходной задачи, для чего привлекаются соответствующие подходящие математические модели (такие как теория графов в предыдущем примере). На этом этапе для нахождения решения также строится неформальный алгоритм.

На следующем этапе алгоритм записывается на псевдоязыке - композиции (смеси) конструкций языка Pascal и менее формальных и обобщенных операторов на простом "человеческом" языке. Продолжением этого этапа является замена неформальных операторов последовательностью более детальных и формальных операторов. С этой точки зрения программа на псевдоязыке должна быть достаточно подробной, так как в ней фиксируются (определяются) различные типы данных, над которыми выполняются операторы. Затем создаются абстрактные типы данных для каждого зафиксированного типа данных (за исключением элементарных типов данных, таких как целые и действительные числа или символьные строки) путем задания имен процедурам для каждого оператора, выполняемого над данными абстрактного типа, и замены их (операторов) вызовом соответствующих процедур.

Третий этап процесса программирования обеспечивает реализацию каждого абстрактного типа данных и создание процедур для выполнения различных операторов над данными этих типов. На этом этапе также заменяются все неформальные операторы



псевдоязыка на код языка Pascal. Результатом этого этапа должна быть выполняемая программа. После ее отладки вы получите работающую программу, и мы надеемся, что, используя пощаговый подход при разработке программ, схема которого показана на рис. 1.4, процесс отладки конечной программы будет небольшим и безболезненным.

Математическая модель

Неформалшый алгоритм

Абстрактные типы данных

Программа на псеадоязыке

Структуры данных

Программа на языке Pascal

Рис. 1.4. Схема процесса создания программ для решения прикладных задач

1.2. Абстрактные типы данных

Большинство понятий, введенных в предыдущем разделе, обычно излагаются в начальном курсе программирования и должны быть знакомы читателю. Новыми могут быть только абстрактные типы данных, поэтому сначала обсудим их роль в процессе разработки программ. Прежде всего сравним абстрактный тип данных с таким знакомым понятием, как процедура.

Процедуру, неотъемлемый инструмент программирования, можно рассматривать как обобщенное понятие оператора. В отличие от ограниченных по своим возможностям встроенных операторов языка программирования (сложения, умножения и т.п.), с помощью процедур программист может создавать собственные операторы и применять их к операндам различных типов, не только базовым. Примером такой процедуры-оператора может служить стандартная подпрограмма перемножения матриц.

Другим преимуществом процедур (кроме способности создавать новые операторы) является возможность использования их для инкапсулирования частей алгоритма путем помещения в отдельный раздел программы всех операторов, отвечающих за определенный аспект функционирования программы. Пример инкапсуляции: использование одной процедуры для чтения входных данных любого типа и проверки их корректности. Преимущество инкапсуляции заключается в том, что мы знаем, какие инкапсулированные операторы необходимо изменить в случае возникновения проблем в функционировании программы. Например, если необходимо организовать проверку входных данных на положительность значений, следует изменить только несколько строк кода, и мы точно знаем, где эти строки находятся.

Определение абстрактного типа данных

Мы определяем абстрактный тип данных (АТД) как математическую модель с совокупностью операторов, определенных в рамках этой модели. Простым примером АТД могут служить множества целых чисел с операторами объединения, пересечения и разности множеств. В модели АТД операторы могут иметь операндами не только данные, определенные АТД, но и данные других типов: стандартных типов языка программирования или определенных в других АТД. Результат действия оператора также может иметь тип, отличный от определенных в данной модели АТД. Но мы предполагаем, что по крайней мене один операнд или результат любого оператора имеет тип данных, определенный в рассматриваемой модели АТД.

Две характерные особенности процедур - обобщение и инкапсуляция, - о которых говорилось выше, отлично характеризуют абстрактные типы данных. АТД можно рассматривать как обобщение простых типов данных (целых и действительных чисел и т.д.), точно так же, как процедура является обобщением простых операторов (+, - и т.д.). АТД инкапсулирует типы данных в том смысле, что определение типа и





0 1 2 [3] 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002