Методы сортировки и поиска




НазваниеМетоды сортировки и поиска
страница3/8
Дата04.03.2013
Размер1.02 Mb.
ТипДокументы
Смотрите также:
1   2   3   4   5   6   7   8


В языках линии Паскаль переменной указательного типа можно присваивать только значения, вырабатываемые встроенной процедурой динамического выделения памяти new, значения переменных того же самого указательного типа и специальное "пустое" ссылочное значение nil, которое входит в любой указательный тип. Не допускаются преобразования типов указателей и какие-либо арифметические действия над их значениями. С переменной-указателем var можно выполнять только операцию var, обеспечивающую доступ к значению переменной типа T0, на которую указывает значение переменной var.


Напротив, в языках Си и Си++ имеется полная свобода работы с указателями. С помощью операции "&" можно получить значение указателя для любой переменной, над указателями определены арифметические действия, возможно явное преобразование указательных типов и даже преобразование целых типов к указательным типам. В этих языках не фиксируется значение "пустых" (ни на что не ссылающихся) указательных переменных. Имеется лишь рекомендация использовать в качестве такого значения константу с символическим именем NULL, определяемую в библиотечном файле включения. По сути дела, понятие указателя в этих языках очень близко к понятию машинного адреса.


Отмеченные свойства механизма указателей существенно повлияли на особенности реализации в языках Си и Си++ работы с массивами. Имя массива в этих языках интерпретируется как имя константного указателя на первый элемент массива. Операция доступа к i-тому элементу массива arr хотя и обозначается как и в языках линии Паскаль arr[i], имеет низкоуровневую интерпретацию *(arr+i). Поэтому было логично допустить подобную запись для любой переменной var с указательным типом: var[i] интерпретируется как *(var+i). По этой причине понятие массива в Си/Си++ существенно отличается от соответствующего понятия в Паскале. Размер массива существенен только при его определении и используется для выделения соответствующего объема памяти. При работе программы используется только имя массива как константный указатель соответствующего типа. Нет операций над "массивными переменными" целиком; в частности, невозможно присваивание. Фактически отсутствует поддержка массивов как параметров вызова функций - передаются именно значения указателей (в связи с этим, при описании формального параметра-массива его размер не указывается). Функции не могут вырабатывать "массивные" значения.


Как отмечалось выше, особенности работы с указателями в некоторой степени повлияли и на организацию структур. Хотя в описаниях языков Си и Си++ и рекомендациях по программированию присутствует настоятельный совет обращаться к полям структурных переменныхтолько по их именам, известно, что каждое имя на самом деле интерпретируется как смещение от начала структуры. Поэтому, имея значение указателя на начало структурной переменной и манипулируя известными длинами полей структуры, технически можно добраться до любого поля, не используя его имя.


Подводя итоги этого краткого обсуждения механизма указателей в Си/Си++, заметим, что позволяя программировать с очень большой эффективностью, этот механизм делает языки очень опасными для использования и требует от программистов большой аккуратности и сдержанности. При разработке получающего все большее распространение языка Java (одним из основных предков которого был Си++) для повышения уровня безопасности были резко ограничены именно средства работы с указателями в языке Си++.

1.7. Динамическое распределение памяти и списки


При решении ряда задач становится неудобно, неэффективно, а иногда и просто невозможно обойтись использованием памяти, выделяемой компилятором и системой поддержки времени выполнения в соответствии с явными описаниями переменных в программе. Во всех языках, более или менее приспособленных к практическому применению, имеется возможность явно запрашивать и использовать области так называемой динамической памяти. Такие области принято называть "динамическими переменными". Возможности создания и использования динамических переменных тесно связаны с механизмами указателей, поскольку динамическая переменная не имеет статически заданного имени, и доступ к такой переменной возможен только через указатель.


Как и во многих обсуждавшихся ранее случаях, механизмы работы с динамической памятью в языках с сильной типизацией существенно отличаются от соответствующих механизмов языков со слабой типизацией. В языках линии Паскаль для запроса динамических переменных используется встроенная процедура new(var), где var - переменная некоторого ссылочного типа T. Если тип T определялся конструкцией type T = T0, то при выполнении этой процедуры подсистема поддержки времени выполнения выделяет динамическую область памяти с размером, достаточным для размещения переменных типа T0, и переменной var присваивается ссылочное значение, обеспечивающее доступ к выделенной динамической переменной.


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


Первый - это явное использование встроенной процедуры dispose(var), где var - переменная ссылочного типа, значение которой указывает на ранее выделенную и еще не освобожденную динамическую переменную. Строго говоря, при выполнении процедуры dispose должно быть не только произведено действие по освобождению памяти, но также переменной var и всем переменным того же ссылочного типа с тем же значением должно быть присвоено значение nil. Это гарантировало бы, что после вызова dispose в программе были бы невозможны некорректные обращения к освобожденной области памяти. К сожалению, обычно из соображений эффективности такая глобальная очистка не производится, и программирование с использованием динамической памяти становится достаточно опасным.


Второй механизм, обеспечивающий более безопасное программирование, состоит в том, что подсистема поддержки времени выполнения хранит ссылки на все выделенные динамические переменные и время от времени (обычно, когда объем свободной динамической памяти достигает некоторого нижнего предела) автоматически запускает процедуру "сборки мусора". Процедура просматривает содержимое всех существующих к этому моменту ссылочных переменных, и если оказывается что некоторые ссылки не являются значением ни одной ссылочной переменной, освобождает соответствующие области динамической памяти. Заметим, что это является возможным в силу наличия строгой типизации ссылочных переменных и отсутствия явных или неявных преобразований их типов.


Работа с динамической памятью в языках Си/Си++ гораздо проще и опаснее. Правильнее сказать, что в самих языках средства динамического выделения и освобождения памяти вообще отсутствуют. При программировании на языке Си для этих целей используются несколько функций из стандартной библиотеки stdlib, специфицированной в стандарте ANSI C. При реализации языка Си в среде ОС UNIX используются соответствующие функции из системной библиотеки stdlib.


Базовой функцией для выделения памяти является malloc(), входным параметром которой является размер требуемой области динамической памяти в байтах, а выходным - значение типа *void, указывающее на первый байт выделенной области. Гарантируется, что размер выделенной области будет не меньше запрашиваемого и что область будет выравнена так, чтобы в ней можно было корректно разместить значение любого типа данных. Тем самым, чтобы использовать значение, возвращаемое функцией malloc(), необходимо явно преобразовать его тип к нужному указательному типу.


Для освобождения ранее выделенной области динамической памяти используется функция free(). Ее входным параметром является значение типа *void, которое должно указывать на начало ранее выделенной динамической области. Поведение программы непредсказуемо при использовании указателей на ранее освобожденную память и при задании в качестве параметра функции free() некорректного значения.


Заметим, что по причине наличия возможности получить значение указателя на любую статически объявленную переменную, работа с указателями на статические и динамические переменные производится полностью единообразно. Единообразная работа с массивами и указателями естественным образом позволяет создавать и использовать динамические массивы.


Как видно, с динамической памятью в языках Си/Си++ работать можно очень эффективно, но программирование является опасным.


Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти - списки, деревья, графы и т.д. (Особенности указателей в языках Си/Си++ позволяют, вообще говоря, строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных.) Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип T, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная var типа T (или переменная типа указателя на T в случае полностью динамического создания структуры). Имя этой переменной при выполнении программы используется как имя "корня" динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной var (или первой динамической переменной, указатель на которую содержится в переменной var). Понятно, что этот подход позволяет создать динамическую структуру с любой топологией.


Наиболее простой динамической структурой является однонаправленный список (рисунок 1.1). Для создания списка определяется структурный тип T, у которого имеется одно поле next, объявленное как указатель на T. Другие поля структуры содержат информацию, характеризующую элемент списка. При образовании первого элемента ("корня") списка в поле next заносится пустой указатель (nil или NULL). При дальнейшем построении списка это значение будет присутствовать в последнем элементе списка

Рис. 1.1.


Над списком, построенном в такой манере, можно выполнять операции поиска элемента, удаления элемента и занесение нового элемента в начало, конец или середину списка. Понятно, что все эти операции будут выполняться путем манипуляций над содержимым поля next существующих элементов списка. Для оптимизации операций над списком иногда создают вспомогательную переменную-структуру (заголовок списка), состоящую из двух полей - указателей на первый и последний элементы списка (рисунок 1.2). Для этих же целей создают двунаправленные списки, элементы которых, помимо поля next, включают поле previous, содержащее указатель на предыдущий элемент списка (рисунок 1.3) и, возможно, ссылки на заголовок списка (рисунок 1.4).

Рис. 1.2.

Рис. 1.3.

Рис. 1.4.

1.8. Абстрактные (определяемые пользователями) типы данных


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


Не обращая больше внимания на ущербность терминологии, займемся содержанием понятия АТД. Как мы видели, наличие перечисляемых, уточняемых и конструируемых типов данных в сочетании со средствами выделения динамической памяти позволяет конструировать и использовать структуры данных, достаточные для создания произвольно сложных программ. Ограниченность этих средств состоит в том, что при определении типов и создании структур невозможно зафиксировать правила их использования. Например, если определен структурный тип с полями salary, commissions и total в предположении, что для любой переменной этого типа поле total всегда будет содержать общую сумму выплат, то ничто не мешает по ошибке нарушить это условие (с точки зрения компилятора никакой ошибки нет) и получить неверные результаты работы программы.


Основной идеей АТД является то, что при его определении специфицируется не только структура значений типа, но и набор допустимых операций над переменными и значениями этого типа. В наиболее сильном случае доступ к внутренней структуре типа доступен только через его операции. В число операций обязаны входить один или несколько конструкторов значений типа.


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

1.8.1. Представление типа


При программировании с использованием АТД возможны три подхода (они могут быть смешаны): (1) перед началом написания основной программы полностью определить все требуемые типы данных; (2) определить только те характеристики АТД, которые требуются для написания программы и проверки ее синтаксической корректности; (3) воспользоваться готовыми библиотечными определениями. В каждом из этих подходов имеются свои достоинства и недостатки, но их объединяет то, что при написании программы известны по меньшей мере внешние характеристики всех типов данных. В некотором смысле это означает, что расширен язык программирования.


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


Переменные, используемые для внутреннего представления значений типа называются переменными состояния, а их совокупность состоянием значений.


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

1.8.2. Реализация типа


Реализация типа представляет собой многовходовой программный модуль, точки входа которого соответствуют набору операций реализуемого типа. Естественно, должно иметься полное соответствие реализации типа его спецификации. Набор статических переменных (в смысле языков Си/Си++) этого модуля образует структуру данных, используемую для представления значений типа. Такой же структурой обладает любая переменная данного абстрактного типа.


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

1.8.3. Инкапсуляция


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


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

1.8.4. Наследование типов


Под наследованием типов понимается возможность дисциплинированного создания новых типов на основе уже определенных. Мы подчеркиваем слово "дисциплинированного", потому что, конечно, можно определять новые типы и произвольным образом, используя в качестве заготовок куски существующих программных текстов.


В отличие от этого, при использовании механизма наследования типов требуется, чтобы спецификация нового типа (подтипа) полностью включала спецификацию наследуемого типа (супертипа). Но эта спецификация может быть расширена сигнатурами дополнительных операций, вводимых для подтипа. Соответственно в реализации подтипа должны присутствовать коды функций и/или процедур дополнительных операций, а структуры данных, функции и процедуры супертипа могут быть переопределены.


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


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


На рисунке 1.5 показана простая схема образования типов на основе одиночного наследования. Естественно, что в подтипах типа "Человек" появляются дополнительные операции, например, "размер пособия" для безработных и "должностной оклад" для служащих. Можно предположить, что операция "знание языков", вводимая для типа "Служащий", по-разному переопределяется для его подтипов "Программист" и "Преподаватель".

Рис. 1.5.


С другой стороны, очевидно, что из соображений здравого смысла и безработные, и служащие обладают общими свойствами, характерными для типа "Человек", а программисты и преподаватели относятся к категории "Служащие". Эти соображения приводят нас к рисунку 1.6, на котором показана иерархия включения значений этих типов данных. Это означает, что, в частности, должна иметься возможность единообразной работы со значениями типа "Человек" независимо от того, сформировано ли соответствующее значение конструктором этого типа или же конструктором любого из его подтипов. Конечно, при этом можно использовать только те операции, которые специфицированы во внешнем представлении типа "Человек".

Рис. 1.6.


Поскольку в подтипе может быть переопределена реализация операций, специфицированных в супертипе, то во время компиляции программы иногда невозможно установить, какую функцию или процедуру требуется вызывать при выполнении операции над значением типа. По этой причине в системах программирования, поддерживающих развитый механизм наследования, для обеспечения корректного вызова функций и/или процедур, которые реализуют операции типа, приходится применять так называемый метод позднего связывания (late binding).


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

1.8.5. Разновидности полиморфизма
1   2   3   4   5   6   7   8

Скачать 1.02 Mb.
Поиск по сайту:
Разместите кнопку на своём сайте:
Публикация документов


База данных защищена авторским правом ©dogend.ru 2000-2014
При копировании материала укажите ссылку
обратиться к администрации
Уроки, справочники, рефераты
Учебный материал

Рейтинг@Mail.ru