Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 8
Текст из файла (страница 8)
Операция принадлежности относится к классу операций отношений. Ниже приведены примеры выражений с множествами и полностью эквивалентные им выражения со скобками: г ь 8+ г = (г ьв) + Г г — з ч Г =- г — (в ь г') г — в+с=(г — в)+г х! п з + Г = х 1п (в + г) Наш первый пример использования множеств — программа простого сканера в трансляторе. Сканер — это процедура, задача которой — преобразовать последовательность символов в последовательность текстовых единиц транслируемого языка, так называемых лексем. При каждом вызове сканер считывает нужное число входных символов и выдает одну выходную лексему. Конкретные правила трансляции следующие: 1.
Имеются следующие выходные лексемы: идентификатор, число, меньше-равно, больше-равно, присвоить — и лексемы, соответствующие отдельным символам, таким, как +,—, ит.д. 2. Лексема идентификатор выдается по прочтении последовательности букв и цифр, начинающейся с буквы. 3. Лексема число выдается по прочтении последовательности цифр. 4. Лексемы меньше-равно, болыие-равно и присвоить выдаются по прочтении соответствующих пар символов (=, 5.
Пробелы и концы строк опускаются. В нашем распоряжении имеется простая процеду рз геаФ(х), которая читает очередной символ из входной после- д9. Множество довательности и присваивает его переменной х. Полученная выходная лексема присваивается глобальной переменной аут. Кроме того, имеются глобальные переменные Ы н нищ, назначение которых будет видно из программы !.2, а также сй, содержащая текущий символ входной последовательности.
Массив лексем 5 задает отображение символов в лексемы, его индексы ограничены лишь теми символами, которые не являются ни цифрами, ни буквами. Как мы видим, использование множеств символов позволяет программировать сканер независимо от их упорядоченности. Второй пример использования множеств в программа составления школьного расписания. Предположим, что каждый из М учеников выбирает для изучения какне-либо предметы из ях общего числа ДГ. Теперь нужно так построить расписание, чтобы можно было некоторые предметы читать одновременно и при этом не возникало бы конфликтов [1.1[. В принципе построение расписания — сложная комбина.
торная задача. При ее решении нужно учитывать много различных факторов. Но в этом примере мы значительно упростим задачу и отвлечемся от реальной ситуации, для которой составляется расписание. Прежде всего для того чтобы решить, какие предметы можно читать в одно н то же время, нужно проанализировать индивидуальные списки выбранных предметов, составленные учениками. Зтн списки представляют собой перечисления предметов, которые нельзя читать одновременно. Поэтому вначале мы программируем процесс сокращения данных.
Ученикам прнсванваются номера от 1 до М, а предметам— от! до л1. туре соигге =- 1 .. лГ; зги/еле =- 1 .. М; ее!ее!гол =- зе! оГ соигге; тат з: сонме; 1: епиуелг; геягэ1гаггоги вегас[хгЫелг! о1 ее1еег1ол; сол111ег: аггау[еоигге! о1 ее!есггон; [ Определение множества курсов, вступающих в конфликт, по спискам курсов, выбранных отдельными учащимися) Гоге:= 1 го Х оо еопЯ1ег[г[:=- [ 1; Хог 1:=- 1 Го М ао Гоге:= 1 то йГ йо !1е й! гедЫга6олД гйев еопЯ!с![е[:= еолфеЩ + герыгагголД (Заметны, что из этого алгоритма следует з !п сов[1!с1[з1.!' Основная теперь задача — составить расписание, т.
е, список читаемых предметов, так, чтобы они следовали в нужном порядке и не противоречили друг другу. Из множества всех курсов мы выбираем подмножества «неконфликтующих» предметов, Подмножества выбираются из переменной гетауп!пй, до тех пор пока множество оставшихся предметов не станет пустым. тат й: 1нгеиег; гетатте, веге!оп: ве!есбоп; с1те1аЫе: аггау[1 .. !г') оГ ее1еебоп; 1с:=- 0; гета!п1пе:= [1., У); »где гета1п!пя ~ [ ) Йо Ьея[а вею!ап: = — следующая выборки; гета!и!пе: = сета!пгпя — »ею!оп; и:= и+1; 11те1аЫе[!с):= еевг!оп еай [1.29) Как определяется «следующая выборка»? Вначале берется любой из множества оставшихся предметов.
Затем из этого множества выбираются все такие предметы, которые «не конфликтуют» с выбранными ранее. Назовем множество таких предметов 1г!а!ее!. Затем будем исследовать каждый элемент множества 1г1а1зе1, Включение такого элемента в зеве!оп зависит от того, пусто или нет пересечение множества предметов, уже включенных в зева!оп, с множеством предметов, конфликтующих с данным. Оператор «зезз!оп:= ;= следуюа)ая выборка» принимает вид тат е,г; еаигее; гг1а1ге1: ее!европ,' Ьеййг г:= 1„" »гЬПе — ~(г 1а гетауп1гП) йо е:= в+1; ееег!оп: = [е)1 1г1а!«е1: == гетатй д — еаЯсЯ1 гоге:= 1 $о лс йо К 1 1а Р1аЬе! «Ьеа Ьеа[а [Е со411сг[1)» гегг1ап =- [ ! СЬеа еехг1ап:= веге!оп + [г! епй еай Конечно, такой способ выбора параллельно читаемых предметов не позволяет строить расписание оптимальным образом.
В неудачных случаях множество выборок параллельных курсов может оказаться столь же велико, как н множество всех курсов, даже если существуют курсы, которые можно было бы читать параллельно. 1. Фундаментаевнвве структуры данных ЕЛО. ПРЕДСТАВЛЕНИЕ МАССИВОВ, ЗАПИСЕЙ И МНОЖЕСТВ Основная цель использования абстракций в программировании — обеспечить разработку, анализ и проверку про. граммы на основе законов, управляющих этими абстракциями, При этом иет необходимости знать, какими способами эти абстракции реализуются на конкретной вычислительной машине. Однако квалифицированному программисту полезно разбираться в наиболее часто применяемых приемах представления основных абстракций программирования — таких, как фундаментальные структуры данных.
Эти знания могут помочь программисту строить программу н описывать данные с учетом не только абстрактных свойств структур, но и их реализации на конкретной ЭВМ, принимая во внимание ее свойства н присущие ей ограничения. Проблема представления данных есть проблема отображения абстрактной структуры в память вычислительной машины.
В первом приближении эта память представляет собой массив отдельных ячеек памяти, называемых словами. Индексы этих слов называются адресами: чаг йоге: аггау1ас(е(гезу) о1 иост( (1.31) Кардинальные числа типов аЫтезз и вота' различны для разных вычислительных машин. Особенная сложность заключается в разнообразии кардинальных чисел для слова. Логарифм кардинального числа называется размером слова, по. скольку он равен количеству разрядов, из которых состоит ячейка памяти. Е.Ю.1. Прадставпенме массивов Представление массива — это отображение (абстрактного) массива компонент типа Т в память, которая представляет собой массив компонент типа ыогв(. Массив следует отображать таким способом, чтобы можно было максимально просто и потому эффективно вычислять адреса его компонент. Адрес, или индекс памяти,( 1сй компоненты массива вычисляется с помощью линейной функции отображения (1.
32) 1= (о+1в з где (а — адрес первой компоненты, а з — число слов„которые «занимает> компонента. Так как по определению слово есть минимальная доступная единица памяти, то, по-видимому, желательно, чтобы з было целым числом; в простейшем случае з = 1. Если з — не целое число слов памяти (а так бывает довольно часто), то з обычно округляется до о Ф Ф 1 о Ф о Ф Ф а М Ф о о Ф1 о Ф,Ф ао е ~ о РФОО Ю .
° 3 1 Ф $ о б о о с а М Р Ф Ш Ф Ф Ф и о ЬФ о Ф 1 $ а Ф О Ф Ф о о Ф 2 о й о в Ф о .й Ф Ф О, Ф 'з Ф 'о Ф 3 Ф Ф $ Ф о с Ф о Оо Ф Ф 3 Ф Ф й Ф Ф $ о ФФ о К Ф $ Ф л Ф з У о, Ф Ф Ыих ~ о о РФо о. о Ь ФФФ ООР Ф РФ Ф и ' к 'р и о \ 'Р Ф Ф Ь Ф о Ф М Р о о о. Ф И Ф о 6 Л Фнндалентольные структуры данньм ближайшего большего целого числа (4. В этом случае каждая компонента массива занимает (з] слов, причем часгь слова величиной [4 — з остается неиспользованной (см.
вмять абстраатимя массив Рис. 1.5. Отабраиссппе пассива в паиять. рпс. 1.5 и 1.6). Округление числа занимаемых слов до ближайшего целого называагся выравнивпниеик Отношение размера памяти, которая отводится для описания структуры 5 = 2.3 (а'; =3 иеиспопьзтемая память Рис, 1.6. Претставпеипе записи с выравниванием. данных, к размеру действительно занятой памяти называется коэффициентом использования памяти: е е и= —,=— а' (а) (!.ЗЗ) С одной стороны, разработчик стремится получить козффгщнент использования памяти, близкий к 1. Но поскольку, с другой стороны, доступ к частям слова — неясный и довольно неэффективный процесс, разработчику приходится идти на некоторый компромисс.
При этом он должен учитывать следующие обстоятельства: 1. Выравнивание понижает коэффициент использования памяти. 2. Отказ от выравнивания может привести к неэффективному обращению к частям слова. 1.10. Представление массивов, записей и множеств 47 3. Обращение к частям слова может удлинить программу (оттранслированную) и этим свести на нет выигрыш, достигнутый отказом от выравнивания. В действительности положения 2 и 3 обычно более важны, и трансляторы всегда автоматически применяют выравнивание. Заметим, что при з» 0.5 коэффициент использования памяти всегда будет и) 0.5.
Однако, если з (0.5, этот . выравнивание Рис. К7. упаковка шести компонент в одно слово коэф(тзициент можно значительно увеличить, помещая в каждое слово более одной компоненты массива. Этот прием называется упаковкой. Если в слово упаковано и компонент, го коэффициент использования памяти равен (см. рис. 1.7) и= (1.34) Доступ к ю'-й компоненте упакованного массива требует вычисления 1 — адреса слова, в котором расположена эта компонента, а также й — относительного адреса расположения компоненты внутри слова: 1 = 151р л и = 1 той и =1 — 1 е и (1.35) Большинство языков программирования не дает программисту возможности управлять реализацией абстрактных структур данных.
Однако полезно иметь возможность указывать желательность упаковки хотя бы в тех случаях, когда в одно слово можно поместить более одной компоненты, поскольку при этом достигается экономия памяти в 2 и более раз. Мы вводим соглашение, что желательность упаковки будет обозначаться словом раскеб перед словом аггау (или гесогб).
Примерк 1уре а11а = раскеб аггау[! .. и) о1 с)заг Эта особенность наиболее ценна для вычислительных машин с длинными словами и сравнительно удобным доступом к отдельным частям слов. Важное свойство этого префикса состоят в том, что он не изменяет значение и правильность программы. Это означает, что можно выбирать любое нз альтернативных представлений с уверенностью, что это ие повлияет на смысл программы. 48 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
