Структуры данных и алгоритмы (1021739), страница 5
Текст из файла (страница 5)
В главах 4 и 5 мы изучим несколько таких представлений. В этом примере мыможем представить каждое множество вершин посредством абстрактного типа LIST(Список), который можно выполнить в виде обычного списка целых чисел, ограниченного специальным значением null (для обозначения которого мы будем использоватьчисло 0). Эти целые числа могут храниться, например, в массиве, но есть и другие способы представления данных типа LIST, которые мы рассмотрим в главе 2.1Мы отличаем абстрактный тип данных SET от встроенного типа данных set языка Pascal.1.1.
ОТ ЗАДАЧИ К ПРОГРАММЕ21Теперь можно записать оператор for в строке (3.2) в виде стандартного цикла лоусловию, где переменная w инициализируется как первый элемент списка newclr изатем при каждом выполнении цикла принимает значение следующего элемента изnewclr. Мы также преобразуем оператор for строки (2) листинга 1.1. Измененнаяпроцедура greedy представлена в листинге 1.3. В этом листинге есть еще операторы,которые необходимо преобразовать в стандартный код языка Pascal, но мы пока ограничимся сделанным.
DЛистинг 1.3. Измененная программа greedyprocedure greedy ( var G: GRAPH; var newclr: LIST ) ;{ greedy присваивает переменной newclr множество вершинграфа G, которые можно окрасить в один цвет }varfound: boolean;v, w: integer;beginnewclr:= 0;v.= первая незакрашенная вершина из G;. while v <> null do beginfound:= false;w: = первая вершина из newclrwhile w <> null do beginif существует ребро между v и.
w thenfound:= true;w:= следующая вершина из newclr;end;if found = false then beginпометить v цветом;добавить v в newclrendv:= следующая незакрашенная вершина из G;end;end; { greedy }Резюме-''•'.•,•'.',На рис. 1.4 схематически представлен процесс программирования так, как онтрактуется в этой книге. На первом этапе создается модель исходной задачи, для чего привлекаются соответствующие подходящие математические модели (такие кактеория графов в предыдущем примере). На этом этапе для нахождения решениятакже строится неформальный алгоритм.На следующем этапе алгоритм записывается на псевдоязыке — композиции(смеси) конструкций языка Pascal и менее формальных и обобщенных операторов напростом "человеческом" языке. Продолжением этого этапа является замена неформальных операторов последовательностью более детальных и формальных операторов.
С этой точки зрения программа на псевдоязыке должна быть достаточно подробной, так как в ней фиксируются (определяются) различные типы данных, над которыми выполняются операторы. Затем создаются абстрактные типы данных длякаждого зафиксированного типа данных (за исключением элементарных типов данных, таких как целые и действительные числа или символьные строки) путем задания имен процедурам для каждого оператора, выполняемого над данными абстрактного типа, и замены их (операторов) вызовом соответствующих процедур.Третий этап процесса программирования обеспечивает реализацию каждого абстрактного типа данных и создание процедур для выполнения различных операторов надданными этих типов. На этом этапе также заменяются все неформальные операторы22ГЛАВА 1.
ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВпсевдоязыка на код языка Pascal. Результатом этого этапа должна быть выполняемаяпрограмма. После ее отладки вы получите работающую программу, и мы надеемся,что, используя пошаговый подход при разработке программ, схема которого показанана рис. 1.4, процесс отладки конечной программы будет небольшим и безболезненным.МатематическаямодельНеформальныйалгоритмРис. 1.4.
Схема процесса создания программ для решенияприкладных задач1.2. Абстрактные типы данныхБольшинство понятий, введенных в предыдущем разделе, обычно излагаются вначальном курсе программирования и должны быть знакомы читателю. Новыми могут быть только абстрактные типы данных, поэтому сначала обсудим их роль в процессе разработки программ.
Прежде всего сравним абстрактный тип данных с такимзнакомым понятием, как процедура.Процедуру, неотъемлемый инструмент программирования, можно рассматриватькак обобщенное понятие оператора. В отличие от ограниченных по своим возможностям встроенных операторов языка программирования (сложения, умножения и т.п.), спомощью процедур программист может создавать собственные операторы и применятьих к операндам различных типов, не только базовым. Примером такой процедурыоператора может служить стандартная подпрограмма перемножения матриц.Другим преимуществом процедур (кроме способности создавать новые операторы)является возможность использования их для инкапсулирования частей алгоритмапутем помещения в отдельный раздел программы всех операторов, отвечающих заопределенный аспект функционирования программы. Пример инкапсуляции: использование одной процедуры для чтения входных данных любого типа и проверкиих корректности.
Преимущество инкапсуляции заключается в том, что мы знаем,какие инкапсулированные операторы необходимо изменить в случае возникновенияпроблем в функционировании программы. Например, если необходимо организоватьпроверку входных данных на положительность значений, следует изменить тольконесколько строк кода, и мы точно знаем, где эти строки находятся.Определение абстрактного типа данныхМы определяем абстрактный тип данных (АТД) как математическую модель ссовокупностью операторов, определенных в рамках этой модели. Простым примеромАТД могут служить множества целых чисел с операторами объединения, пересечения и разности множеств. В модели АТД операторы могут иметь операндами нетолько данные, определенные АТД, но и данные других типов: стандартных типовязыка программирования или определенных в других АТД.
Результат действия оператора также может иметь тип, отличный от определенных в данной модели АТД.Но мы предполагаем, что по крайней мене один операнд или результат любого оператора имеет тип данных, определенный в рассматриваемой модели АТД.Две характерные особенности процедур — обобщение и инкапсуляция, — о которых говорилось выше, отлично характеризуют абстрактные типы данных. АТД можно рассматривать как обобщение простых типов данных (целых и действительныхчисел и т.д.), точно так же, как процедура является обобщением простых операторов(+, - и т.д.).
АТД инкапсулирует типы данных в том смысле, что определение типа и1.2. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ23все операторы, выполняемые над данными этого типа, помещаются в один разделпрограммы. Если необходимо изменить реализацию АТД, мы знаем, где найти и чтоизменить в одном небольшом разделе программы, и можем быть уверенными, что этоне приведет к ошибкам где-либо в программе при работе с этим типом данных. Болеетого, вне раздела с определением операторов АТД мы можем рассматривать типыАТД как первичные типы, так как объявление типов формально не связано с их реализацией.
Но в этом случае могут возникнуть сложности, так как некоторые операторы могут инициироваться для более одного АТД и ссылки на эти операторы должны быть в разделах нескольких АТД.Для иллюстрации основных идей, приводящих к созданию АТД, рассмотрим процедуру greedy из предыдущего раздела (листинг 1.3), которая использует простыеоператоры над данными абстрактного типа LIST (список целых чисел). Эти операторы должны выполнить над переменной newclr типа LIST следующие действия.1.2.3.Сделать список пустым.Выбрать первый элемент списка и, если список пустой, возвратить значение nu.ll.Выбрать следующий элемент списка и возвратить значение null, если следующего элемента нет.4. Вставить целое число в список.Возможно применение различных структур данных, с помощью которых можноэффективно выполнить описанные действия.
(Подробно структуры данных будут рассмотрены в главе 2.) Если в листинге 1.3 заменить соответствующие операторы выражениямиMAKENULL(neu>cfr);w := FlRST(newclr);w := NEXT(newclr);INSERT(u, newclr);то будет понятен один из основных аспектов (и преимуществ) абстрактных типовданных. Можно реализовать тип данных любым способом, а программы, использующие объекты этого типа, не зависят от способа реализации типа — за это отвечаютпроцедуры, реализующие операторы для этого типа данных.Вернемся к абстрактному типу данных GRAPH (Граф).
Для объектов этого типанеобходимы операторы, которые выполняют следующие действия.1.2.3.4.Выбирают первую незакрашенную вершину.Проверяют, существует ли ребро между двумя вершинами.Помечают вершину цветом.Выбирают следующую незакрашенную вершину.Очевидно, что вне поля зрения процедуры greedy остаются и другие операторы,такие как вставка вершин и ребер в граф или помечающие все вершины графа какнезакрашенные. Различные структуры данных, поддерживающие этот тип данных,будут рассмотрены в главах 6 и 7.Необходимо особо подчеркнуть, что количество операторов, применяемых к объектам данной математической модели, не ограничено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
