Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 4
Текст из файла (страница 4)
Поэтому вряд ли следует требовать, чтобы программист сам определял способы представления чисел или даже характеристики запоминающего устройства. Эти «решения низшего уровня» можно предоставить разработчикам ЭВМ, так как они располагают наибольшей информацией о ее технологии, что позволяет им выбрать способ представления чисел, пригодный для всех (или почти всех) случаев. Д Фрндаментал»ныл структуры данных С этой точки зрения очевидно значение языков прогромлтирования.
Язык программирования описывает некоторую абстрактную вычислительную машину, понимающую термииы этого языка, что соответствует какому-то уровню абстракция от обьектов, используемых реальной ЭВМ. Слсдовательио, работая с таким «языком высокого уровня», программист освобождается (и отстраняется) от вопросов представления чисел, если число — элементарный объект этого языка. Примеиеиие языка, который предоставляет подходящее множество осиовиых абстракций, общих для оольшииства задач обработки данных, увеличивает надежность программ.
Легче иаиисать программу, осиоваииу1о иа знакомых нотациях для чисел, множеств, последовательностей и циклов, чем иа разрядах, есловах» и переходах, разумеется, в самой ЭВМ все даипые; и числа, и множества, и последовательности — будут представлены в виде большой совокупности разрядов. Но для программиста это несущественно, если ои ие заботится о подробностях представлсиия выбраииык им абстракций и если ои уверен, что представлеипе, которое выберет машииа (или транслятор), подходит для его целей.
ь)ем ближе абстракции к конкретной ЭВМ, тем легче разработчику языка выбрать представление данных и тем больше вероятность, что оио будет пригодно для всех (или по пи всех) возможных задач. Это накладывает определениые ограничения из уровень абстракции от реальной вычислительиой машины, Например, ие имеет смысла включа~ь в язык общего иазиачеиия в качестве основных элементов данных геометрические объекты, так как из-за сложиости их представления оио будет сильио зависеть от выполияемых с ипми действий.
Но природа этих действий и их частота будут иеизвестиы разраоотчику универсального языка и его транслятора, поэтому любое его решеиие в некоторых случаях будет непригодным. В настоящей книге эти соображения определяют выбор нотаций для описания алгоритмов и представления данных. Понятно, что мы хотим использовать привычиую математическую нотацию, т. е.
числа, множества, последовательиосги и т. д., а ие такие машинно-зависимые понятия, как последопательиости разрядов. Но ясно также, что желатсльио использовать язык, для которого существует эффективный транслятор. В равной мере неразумно как использовать машпиио-ориеитироваииый или машииио-зависимый язык, так и составлять программу для вычислительной машины с помощью абстрактных нотаций, ие затрагивая проблему представления. В качестве компромисса между этими крайностями был разработан язык программироваиия Паскаль, который и ис. П2. Концепция типа для данны» !7 пользуется в данной книге (1.3, 1.5). Этот язык был успешно реализован на нескольких ЭВМ, и было показано, что он достаточно близок к реальным машинам, а его свойства п их реализация довольно понятны.
Кроме того, этот язык близок к другим языкам, особенно к Алголу-бб, поэтому наши выводы можно использовать также применительно и к этим языкам. 1.2. КОНЦЕПЦИЯ ТИПА ДПЯ ДАННЫХ В математике принято классифицировать переменные в соответствии с некоторыми важными характеристиками. Проводится строгое разграничение, во-первых, между вегцественными, комплексными и логическими переменными, во-вторых, между переменпымп, представляющими отдельные значения, множества значений или множества множеств, в-третьих, между функциями, функционалами, множествами функций и т. д.
При обработке данных такая классификация не менее (если не более) важна. Мы будем придерживаться того принципа, что каждая константа, переменная, выражение ияи функция бывают определенного типа. Этот тип существенным образом характеризует множество значений, к которому принадлежит константа, которые может принимать переменная или выражение или которые может вырабатывать функция. В математических текстах тип переменной обычно определяется по ее виду без обращения к контексту, но в программах для вычислительных машин это неприменимо, поскольку в них обычно используются буквы только одного вида, который допускает оборудование ЭВМ (латинскне буквы).
Поэтому широко используется правило, что тип явно задается в описании константы, переменной или функции, которое предшествует в тексте их использованию. Это правило особенно важно потому, что транслятор должен выбрать представление объекта в памяти ЭВМ, Очевидно, что объем памяти, выделяемой для переменной, должен устанавливаться в зависимости от того, какие значения она может принимать. Если эта информация известна транслятору, то можно избежать так называемого динамического распределения памяти, Это часто позволяет реализовать алгоритм более эффективно. Таким образом, рассматриваемая здесь концепция типа, которая включена в язык программирования Паскаль, имеет следуюгцне основные свойства 11.2): 1. Любой тип данных определяет множество значений, к которому принадлежит константа, которые может принимать переменная (или выражение), или вырабатывать операция (или функция).
Д Фундаменталснсге струнтуры данных 2. Тип значения, задаваемого константой, переменной илн выражением, можно определить по их виду или описанию без необходимости выполнять какие-либо вычисления. 3. Каждая операция и,тн функция требует аргументов фиксированного типа н выдает результат фиксированного типа. Если операция допускает аргументы нескольких типов (например, «+» используется для сложения как целых, так и вещественных чисел), то тип результата можно определить по специальным правилам языка. Следовательно, транслятор может использовать информацию о типах для проверки вычислимости и правильности различных конструкций. Например, присванвание арифметической (вещественной) переменной булевского (логического) значения можно выявить без выполнения программы.
Такая избыточность в тексте программы является важным вспомогательным средством разработки программ и рассматривается как существенное преимущество хороших языков высокого уровня перед машинным кодом или символическим языком ассемблера. Конечно, в конце концов данные будут представлены в виде большого количества двоичных цифр независимо от того, была ли программа написана на языке высокого уровня с использованием концепции типа или иа языке ассемблера, где типы отсутствуют.
Для вычислительной машины память — это однородная совокупность разрядов без какой-либо структуры. Но именно абстрактная структура позволяет программисту определять типы данных на фоне однообразных записей в памяти ЭВМ. Теория, которая используется в этой книге, и язык программирования Паскаль предполагают некоторые методы определения типов данных. В большинстве случаев новые типы данных определяются с помощью ранее определенных типов данных, Значения, принадлежащие к такому типу, обычно представляют собой совокупности значений компонент, принадлежащих к определенным ранее типам комггонент, такие составные значения называются сгрунтггрированными, Если имеется только один тип компонент, т, е, все компоненты принадлежат одному типу, то он называется базовым. Число различных значений, принадлежащих типу Т, называется кардинальным числом Т.
Кардинальное число определяет размер памяти, нужной для размещения переменной х типа Т. Этот факт обозначается так — х: Т. Поскольку типы компонент могут также быть составными, можно построить целую иерархию структур, но конечные компоненты структуры, разумеется, должны быть атомарными. Следовательно, система нотаций должна допускать описание дд Коняепяил типа длл данных и простых, неструктурированных типов.
Самый простой метод описании простого типа — это перечисление значений этого типа. Например, в программе, связанной с плоскими геометрическими фигурами, может описываться простой тип, называемый фигурой, значения которого задаются идентификаторами прямоугольник, квадрат, эллипс, круг. Но кроме типов, задаваемых программистом, нужно иметь некоторые стандаргньсг типы, которые называются предопределенными.
Они обычно включают числа и логические переменные. Если значения некоторого типа упорядочены, то такой тип называется упорядоченным или скалярньсм. В Паскале предполагается, что все неструктурированные типы упорядочены, и случае когда значения явно перечисляются, считается, что они упорядочены в порядке перечисления.
Применяя эти правила, можно описывать простые типы и строить из них структурированные типы любой степени сложности. Однако на практике недостаточно иметь только один общий метод объединения типов компонент в структуру. С учетом практических задач представления и использования данных универсальный язык должен располагать несколькими методами структурирования. Они могут быть эквивалентны в математическом смысле н различаться только операциями построения их значений и выбора компонент этих значений. Основные рассматриваемые здесь методы позволяют строить следующие структуры: массив, запись, лсножгсгво и последовательность (файл).
Более сложные структуры обычно не описываются как «статические» типы, а «динамически» создаются во время выполнения программы, причем их размер и вид могут изменяться. Такие структуры рассматриваются в гл, 4 — это списки, кольца, деревья и общие конечные графы, Переменные и типы данных вводят в программу для того, чтобы пх использовать в каких-либо вычислениях. Следовательно, нужно еще иметь и некоторое множество операций. Вместе с типами данных язык программирования задает некоторые простые, стандартньсе (атомарные) операции и методы структурирования, которые позволяют описывать сложные действия в терминах простых операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
