Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 9

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

Текст из файла (страница 9)

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

Пусть имеются пере. менные и: аггау(а..с() о)Т р: раскес( аггау(Ь .. с) о(Т где и ( Ь =' с =' !т' — одного и того же скалярного типа. Тогда расИ (и, !', р) (а < ! ~ ~Ь вЂ” с + 11) (1.36) эквивалентно Р И:=и()'+ !' — Ь), 1= Ь..с а ипрасИ(р, и, !) (а~!'~~Ь вЂ” с+с() (13Т) эквивалентно и(1+1 — Ь):=рЦ, )=Ь..с 1.т0.2. Представление записей Заппси отображаются в память (размещаются) так, что пх компоненты располагаются последовательно. Адрес какойлпбо компоненты (поля) т, относительно начального адреса записи т называется сл!еи(еиием компоненты Иь Оио вычислгс!ся следующим образом: И! = з! + за+... + з! „ (1,33) где з; — размер в словах )чй компоненты.

Поскольку у мас- сива все компоненты одного типа, то а и, следовательно, И!=Б! +за+ . ° . +Б! ! =(1 — 1) э. Универсальность записи не позволяет вычислять относительные адреса ее компонент с помощью такой же простой линейной функции, поэтому очень полезно ограничить доступ к ее компонентам и пользоваться лишь фиксированными идентификаторами. Это ограничение позволяет узнать относительные адреса во время трансляции, что намного увеличивает эффективность доступа к полям записи. 1.1О. Представление массивов, заласес и ииоасеств 49 Если несколько компонент записи умещаются в одном слове памяти, то может идти речь об упаковке (см. рис.

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

1.10.3. Предстввненне мненееств Множество з наилучшим образом представляется в памяти машины с помощью характеристической функции С(з), Характеристическая функция — это массив логических значений, 1-я компонента которого означает наличие или отсутствие Рго значения базового типа в мнонсестве в. Размер этого массива равен кардинальному числу базового типа множества. С (зт) =— (! !и з) (1.39) Например, мнозкество небольших целых чисел з = (1, 4, 8, 9) представляется последовательностью логических значений Р(!а1зе) н Т(1гне) С (з) = (РТРРТРРРТТ) если базовый тип множества з — целыс числа, принадлежащие диапазону 0,.9, В памяти машины последовательность логических значений изображается так называемой строкой разрядов (см.

рнс. 1.9). Представление множеств нх характеристической функцией позволяет реализовать операции объединения, пересечения и разности двух множеств с помощью элементарных логических операций. Для любого элемента 1, принадлежащего 60 1. Фундаментальные струнтрраю данных к базовому типу множеств х и у, имеют место следующие эквивалентности мехсду операциями над множествами и логическими операциями: ю юп (х+у) ы (ю' зп х) Ч (ю зп у) ю' зп (хву) = — (ю' юп х) Л (ю зп у) (Е40) ю'ш(х — у) гв(ю'зпх) Л (юшу) Такие логические операции имеются на всех вычислительных машинах, более того, они выполияюотся одновременно иад всеми элементами (разрядами) слова.

Поэтому для более 012 Рис. !лв Представление множества в виде разрядкой строки. эффективной реализации основных операций иад множествами желательно, чтобы множеству соответствовало небольшое фиксированное число слов„над которыми кроме основных логических операций можно было бы выполнять также операции сдвига. В этом случае проверка принадлежности выполняется с помощью сдвига н последующей проверки знакового разряда. Следовательно, проверку хзп]с„с„..., сн] можно реализовать значительно эффективнее, чем при помощи эквивалентного булевского выражения (х= с ) з/ (х=сз) Ч...'т/ (х= с„) Поэтому следует использовать множества только с небольшими базовыми тинами. Наибольшее значение кардинального числа базового типа, при котором реализация достаточно эффективна, зависит от длины слова соответствующей вычислзпельной машины. Разумеется, в этом отношении предпочтительны машины с большой длиной слова. Если размер слова сравнительно невелик, можно использовать несколько слов.

1Л!. ПОСЛЕДОВАТЕЛЬНЫЙ ФАЙЛ Общее свойство структур данных, которые до сих пор обсуждались, а именно массива, записи и множества, заюсиочзется в том, что их кардинальное число конечно. Предполагается, что нардннальные числа типов их компонент конечны. Поэтому они не слишком трудны для реализации; со- 1.П. Пася дог«ге»в«ай файл ответствующее представление легко находится для любой вычислительной машины. Большинство так называемых усложненных структур: последовательности, деревья, ~рафы и т. д.— характеризуЮтся тем, что пх кардинальные числа бесконечны.

Это отличие от базовых структур с конечными кардинальными числами очень важно н имеет существенные практические следствия. Например, определим пюследооате»вну>о структуру следующим образом. Последовательность с базовым типом Тв — это либо пустая последовательность, либо конкатенация последовательности (с базовым типом Тв) и значения типа Т,. Тип Т, определенный таким образом, содержит бесконечное число значений. Каждое отдельное значение состоит из конечного числа компонент, но это число не ограничено, т. е. для каждой данной последовательности можно построить более длинную. Аналогичные рассуждения применимы ко всем другим усложненным структурам данных, Из этого прежде всего следует, что объем памяти, необходимый для размещения структуры усложненного типа, неизвестен во время трансляции и может изменяться во время выполнения программы.

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

Отсюда также следует, что программист должен избегать использования таких структур, если при решении задачи можно ограничиться фундаментальными структурами данных. В большинстве языков и трансляторов учитывается и используется тот факт, что все усложненные структуры состоят либо из неструктурированных элементов, либо из фундаментальных структур. Это позволяет использовать преимущества усложненных структур, не имея информации об их возмоисном применении. Если в языке имеются средства для дина.

мического размещения компонент, для динамической связи компонент и ссылки на них, то в нем могут создаваться произвольные структуры с помощью явных операций, определяемых программистом. Способы создания таких структур и работы с ними рассматриваются в гл. 4. 1. Фуядаменгальяие структуры давних Однако существует структура, которая является усложненной, поскольку ее кардинальное число не ограничено, но которая так широко и часта используется, что ее приходится включить в число фундаментальных структур. Это †последовательность. Для описания абстрактного понятия последовательности мы вводим следующую терминологию и нотацию: 1.

( ) обозначает пустую последовательность. 2. (хз) обозначает последовательность, состоящую из единственной компоненты хь, она называется единичной последовательностью. 3. Если х = (хь ..., х„) и у = (уь ., у,1 — последовательности, то хху=(хи „х„, у„..., у„) (1.41) есть конкатенация х и у. 4. Если х = (хь ..., х„) — непустая последовательность, го 11гз1 (х) = х, (1.42) обозначает первый элемент х. б.

Если х = (хь ..., х„) — непустая последовательность, то гев1(х)=(х„..., х„) (1.43) есть последовательность х без первой компоненты. Следовательно, мы получаем инвариантное отношение (11гс1 (х)) сг гезг (х) == х (1.44) Введение этих обозначен .й пе предполагает, что онп будут использоваться в конкретных программах и обрабатываться реальными вычислительными машинами. В действительности весьма существенно, что операция конкатенации не используется в общем виде и обработка последовательностей ограничивается применением тщательно отобранного множества операций, предполагающих определенный наряда,. использования.

Сами операторы определяются с помощью абстрактных понятий последовательности н конкатенации, Тщательный выбор множества операторов, работающих с последавателнюстями, позволяет при реализации находить удобное и эффективное представление последовательности на любом данном запоминающем устройстве. В результате соответствующий механизм динами:еского распределения памяти может быть достаточно простым, что позволяет программисту работать, не вникая в его тонности. Для того чтобы было ясно, что последовательность, вводимая в качестве базового типа, допускает применение только ограниченного множества операторов, основанных иа строго последовательном доступе к компонентам, эта струк- 1.1!.

Характеристики

Список файлов учебной работы