Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 7
Текст из файла (страница 7)
1.3); х:= Сотр!ех (1.О, — 1.0) 11:=Оп!е(1, 4, 1973) р:= — Регзоп ('%1ЙТН','СНЙ18', Оа!е(18, 1, 1966), та!е, и!пй!е) Идентификаторы зь ..., з„, которые вводятся при определении комбинированного типа, являются именами отдельных пате д Сотр1ек т Репоп Р— ио Рис, !.3. Записи твпов Со»»»р1ел, Ваге, Регзон. компонент переменных этого типа, они употребляются в селекторах записи, где нх добавляют к переменной, обозначающей всю запись. Если имеется переменная х: Т, то ее ") В языке Паскаль такие ковструкторы также отсутствуют.— Прил. 1тед. П7. Заииеи зз (!.21) Если такой сслектор стоит в левой части оператора присваи- вания, то происходит выборочное изменение х: Х.е~ .— — Х7 где х; — значение выражения типа Ти Если даны переменные: г: Сотр1ех д: Ва1е р: Регзоп то нк можно использовать, например, со следующими селек- торами: На примере типа Регеоп мы видим, что компоненты записи могут в свою очередь быть составными.
Таким образом, селекторы могут добавляться одни к другому. Кроме того, разные составные типы могут комбинироваться различными способами. Например, 1-я компонента массива а, который является компонентой записи г, обозначается как г.а (1) а компонента с селектором г, входящая в 1-ю компопенту- запись массива записей а, обозначается как а !1),з Декартово произведение в принципе содержит есе комбинации значений типов компонент. Однако следует заметить, что на практике не все такие комбинации могут быть «законными», т. е.
иметь смысл. Например, тип Ваге, определенный выше, включает значения (31, 4, 1973) и (29, 2, !815) котя дней с такимн датами ие существует. Таким образом, определение зтого типа не отражает реального положения 1-я компонента обозначается как а.(т д.топй р.пагпе р.йг1ййа1е р.(пг1йг(а(ел)ау (типа геа1) (типа 1..12) (типа а1)а) (типа Ва1е) (типа 1..31) и Фундаментальные структуры данных 34 вещей.
Все же оно достаточно близко к практическим целям, и ответственность за то, чтобы при выполнении программы не возникалн подобные бессмысленные значения, возлагается на программиста. В следующем небольшом фрагменте программы показано использование записей. Его задача — сосчитать число «людей» в массиве а, которые одновременно прннадлежат жен. скому полу и одиноки: тат а: аггау(1 .. М) оЧРегзоп1 соиле: 1пгелег; соипг: = 0; Гог);= 14о)удо Ы(а(1).тех = Хета1е) 1~ (аи.пгагегагие = е1пя1е) 4аеи соипг:= соипг+1 (1.22] Инвариант цикла здесь соилг = С (1) где С(1) — число одиноких женщин в подмножестве аь ..., ар В другом варианте записи этого оператора используется конструкция, которая называется оператором присоединения: йн 1: = 1 то йг йо нв1й аи йо Г(еех = Хета1е) Л (тагегагие = егпя1е) 1йен соиле:= соип1+1 Выражение в11Ьгбоз означает, что внутри оператора з селекторы переменной г можно использовать без префикса: считается, что все они ссылаются на переменную г.
Таким образом, оператор присоединения позволяет сократить текст программы, а также предотвращает повторное вычисление адреса индексированной компоненты а (1). В следующем примере мы предполагаем, что некоторые группы людей в массиве а чем-то объединены (возможно, чтобы их можно было быстрее находить). Связующая информация выражается дополнительной компонентой записи Регзоп, называемой 1(пп (связь). Эти компоненты соединяют записи в линейный список, так что для каждого человека легко можно найти предшествующую и последующую записи. Интересно, что прн таком методе связывания можно легко просматривать список в обоих направлениях, используя только одно число, хранящееся в каждой записи.
Это делается следующим образом. 1.8. Записи с еариангаии Предположим, что индексы трех последовательных элементов списка есть 1а г, га, га+~ Значение 1гви для Й-го элемента берется равнылг гл г — ге ь При проходе по списку вперед 1а+г определяется двумя текущими индексными переменными х = гл г и ц = г» по формуле га, = х+ а 1р11ти а прн проходе по списку в обратном направлении га ~ опре- деляется с помошью х = 1атг и р = 1а по формуле га, = х — и 1р1.11пй Пример объединения при помощи 11пя всех лиц одного пола показан в табл. П2, Ф таблица 1Дч Массив ааемеитов типа Реглан Гйлг Наале хех 1Ыс Запись и массив имеют обшее свойство: оба являются структурами со «случайным доступомв.
Запись — более универсальная структура, поскольку не требуется, чтобы типы всех ее компонент были одинаковы. С другой стороны, массив предоставляет большие возможности, так как селекторы его компонент могут вычисляться (если они представлены выражениями), тогда как селекторы компонент записи — зто фиксированные идентификаторы, задаваемые в описании типа. ка. зАписи с ВАРиАнтАми ла практической работе часто кажется удобным и естественным рассматривать два типа как варианты одного и того же типа, Например, тип СоогЖпа1е, введенный в предыдущем разделе, можно рассматривать как объединение двух 1 2 5 5 б 7 9 10 Саго!уп СЬПа Тгаа коьеге 1опагнап Хепппег Каупкеоп Магу Лапе Манйаа 2 2 5 3 3 5 5 .3 1 3 !. Фундаментальные структуры данных вариантов: декартовых и полярных координат, компонентами которых являются соответственно (а) две длины и (Ь) длина и угол. Для того чтобы определить, какой вариант принят в данный момент, вводится третья компонента. Она называется дискриминантом типа или полем признака.
суре Соогй!пасе = гесогй саве к!гта': (Сагсевсап, росаг) оГ Сагселап: (х, у: геа1); ро!агс (г: геа1; р: геа1) Здесь имя поля признака — Ыпй, а имена координат — либо х и у в случае значения СагСевсап (декартовы), либо г и ср в случае значения ро!аг (полярные). Множество значений типа Соотг!спасе есть объединение двух типов; Т, =(х, йч геа1) Тв = (г: геа1; ср; геа1) а его кардинальное число равно сумме кардинальных чисел Тс и Тт. Однако чаще всего приходится объединять не два полностью различных типа, а два типа с частично совпадающвмн компонентами. Для такой ситуации применяется термин «запись с вариантами», Примером может служить тип Регвоп определенный в предыдущем разделе, если существенные характеристики должны записываться в файл в зависимости от пола.
Например, для мужчины могут считаться в какой-то определенной ситуации существенными такие признаки, как вес и наличие бороды, а для женщины можно считать важными три ее основных размера (тогда как вес она может хранить в тайне). Исходя из зтих допущений, получим следующее описание типа: Суре Регютс = гесогй пате, Ягясате. 'асса; ЬСгс!тс!осе с Васе; гтсгсгвсассссп (тстту1е, пгастЫ, и !с(ни еьст а1гогееа) ," сазе,тех: (пса!о, .сесна!е) ог та1е: (несу!тс: геа1; Ьеагйей: Воо1еаст); уесста(ес (в!ге: аггау(! ..
3) о1 сттсеуег) евй 37 ПЗ. Записи с аариантаии Общий вид описания составного типа с вариантами: (1.24) Эдесь з; и зп — селекторы компонент, принадлежащих к типам компонент Т; и Т;„а з.— имя различающего поля признака типа Т„. Переменная х типа Т состоит из компонент х.зо х.з„, х.з„, х,зм о ..., х.зм „ в том и только том случае, когда текущее значение хл„= с„. Компоненты жзь ... „х.з, составляют оби1ую часть т вариантов. Таким обРазом, использование селектоРа х,за ь (1~ л ~ е- и,) при хл, Ф сн следует рассматривать как серьезную ошибку программирования. Это может, например, означать (для типа Регзоп, определенного выше,) проверку, является лп некая леди бородатой, или (в случае выборочного присваивания) приписывание ей этого свойства! Поэтому при использовании записей с вариантами требуется особое внимание. Лучше всего действия, связанные с каждым из вариантов, группировать в выбирающем селекторе, так называемом операторе варианта; его с~руктура отражает структуру описания типа записи с вариантами: сазе х.з„и( с,: Я,, с,: Я„.
(1.25) с„: Я евй Оператор Ян выполняется в случае, когда для х выбирается й-й вариант, т. е. поле признака х,з„принимает значение с,. Следовательно, для того чтобы предотвратить неправильное использование селекторов, нужно следить, чтобы каждый бн содержал только селекторы х.з„, х.за л и х зь о ° ° ° х зь „ Л Фундаментальные структуры донных за В следующем небольшом фрагменте программы вычисляется расстояние между двумя точками А и В, заданными переменными а и Ь типа Соогс!!па!а (запись с вариантами).
Способ вычисленяя выбирается в зависимости от четырех воз- Рис Ь4. Декартовы и полярные коораинаты. можных комбинаций декартовых и полярных координат (см. рпс. ?.4). саяе а.!с!пИ оГ Саггея1ап: саяе Ь.Ипс! о$ Саггея!ап: е1: =- лдгг(яс1г(а.х — Ьл)+яаг(а.у — Б.у)); Ро!аг: д:= яаг!(яаг(а.х — Ь.гьсоя(Ьлр) + тт!г(а. у — Ьг е я!а(Ь р)) ева; сане Б,к!па( от Саггел!ап; а(: = луг!(ят!г(а.г еооя(а~р) — Ьст? +наг(а.ге я!п(а.гр) — Ь.у)); Ро1аг: Ы: = а!г!(яг!г(а.г)+яг!г(Ь.г) — 2" а.гей.гесоя(ар — Ь.гр)) Ро!аг: евй евй 1.9. МНОЖЕСТВО Кроме массива н записи имеется третья фундаментальная структура данных — множество. Соответствующий тип описывается следующим образом: Туре Т= яе! о!Т, 1 (!.26? Значениями переменной х типа Т являются множества элементов типа То.
Множество всех подмножеств множества Та называется мпожестволт-степенью Та. Таким образом, тип Т вЂ” это множество-степень своего базового типа Тм 1.9, Мяоасестао Пригнеры: (уре 1пувег = зеФ о$ О .. 30 туре сйагзег =- вес оу сваг туре сарехсасие =- вег оГ ехсер11оп Во втором примере базовым типом является стандартное подмножество символов — тип сйаг, в третьем примере — тип исключительных состояний магнитных лент, описанный как скалярный тип: $уре ексер11ол = (ип)оайесу, пгапиа1, раг11у, гкелн) значения которого соответствуют различным состояниям устройства лентопротяжек. Если даны переменные; 1е .' 1псгес св: сугагсес ; аггау[1 .. 6) о! 1арез(а1иг то формировать и присваивать значения переменных-множеств можно, скажем, так: лч 1г: = [1, 4, 9, 16, 25) 1[3): = [псапиа1) 1[5):=. [) 1[б): =- [ип!оас(есу .. гкенг) Здесь значение, присваиваемое 1]3],— это множество, состоящее из одного элемента тапиа1, 1[5] присваивается пустое множество, что соответствует рабочему состоянию 5 лснтопротяжки (какие-либо исключительныс состояния отсутствуют), а 1[б] присваивается значение множества, включающего все четыре исключительных состояния.
Кардинальное число множества типа Т равно саус(1па11(у(Т) =2'"а""н" ~~'. (1.27) Это следует из того, что каждый из элементов сагб1па]йу (Те) представляется в Множестве одним из двух значений: «присутствует» или «отсутствует», и эти элементы входят в множество независимо друг от друга, Очевидно, что для эффективной и экономной реализации не только базовый тнп ') В отличие от принятой ногацин лгы используем для множества не фигурные, а квадратные скобки. В фигурные скобки закл~очаготся комментарии в программах. 40 д Фундаментальные структуры данник множества должен быть конечным, но н его кардинальное число †достаточ небольшим. На всех множествах определены следующие элементарные операции: ь пересечение множеств + объединение множеств — разность множеств 1п принадлежность множеству Пересечение и объединение двух множеств часто называют соответственно умножением и сложением множеств; соответствующим образом определены приоритеты операций: операция пересечения имеет приоритет перед операциямн объединения и разности, а они в свою очередь имеют приоритет перед операцией принадлежности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
