Учебное пособие по курсу «Технология программирования»

Вид материала

Учебное пособие

Содержание Стек (stack) Очередь (queue) Дека, двусторонняя очередь (deque) Список (list)

Подобный материал:

• Курсовой проект по курсу «Технология программирования», 147.33kb.
• Учебное пособие для студентов специальности 260202 «Технология хлеба, кондитерских, 1941.61kb.
• О. М. Мышалова общая технология мясной отрасли учебное пособие, 1355.07kb.
• Учебное пособие Иркутск 2006 Рецензент, 2159.1kb.
• Учебное пособие Иркутск 2006 Рецензент, 2160.36kb.
• Учебное пособие Кемерово 2004 удк, 1366.77kb.
• Учебное пособие Тамбов 2009 удк 339. 138, 1882.57kb.
• А. Ю. Просеков С. Ю. Юрьева технология молочных продуктов детского питания учебное, 4980.6kb.
• А. Н. Петров А. Г. Галстян А. Ю. Просеков С. Ю. Юрьева технология продуктов детского, 2728.08kb.
• Учебное пособие Йошкар-Ола, 2008 ббк п6 удк 631. 145+636: 612. 014., 7797.37kb.

5. Данные.

Любую программу можно рассмотреть, как некий набор операций, который применяется к некоторым данным в некоторой последовательности.

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

Хотя программист и не определяет явно служебных данных, он обязан знать об их наличии и учитывать при программировании. Грамотный программист, нередко, может получать доступ к служебным данным и сам их менять или использовать. В своё время в DOS, большинство грамотных программистов при работе с графикой пользовались непосредственным доступом к видеопамяти, а не стандартными средствами графики, это было на порядок быстрее. В Pascale – возможны массивы с задаваемыми границами, а, следовательно, где-то хранится информация с описанием массива и его границами, чего нет в Cи, где нет многомерных массивов и нет операций с массивами и т.д.

Или: любой Cи – программист, только начав работать в Cи со строками, быстро разбирался, что в Cи нет операций с массивами, а следовательно и со строками, и вообще в Cи - строка это простая последовательность байт ограниченная байтом 0x00. Обратите внимание на то, что программиста вынуждают знать внутреннее представление строк! Спросите любого Basic – программиста: “Как представляется строка в Basice?» В девяти случаев из десяти вы не получите правильного ответа. Важно понимать, что язык может способствовать ознакомлению программиста с внутренним представлением (Cи++) и наоборот всячески скрывать наличие служебных данных, препятствуя проникновению программиста «во внутрь» - Basic.

При применении языков, обычно, у программиста две альтернативы: использовать язык с явным описанием данных или вовсе не описывать данные. Не следует думать, что отсутствие в языке средств описания данных – это плохо. Во многих очень серьёзных языках данные можно либо вовсе не описывать, либо не описывать частично, например, такой язык, как АПЛ не имеет средств явного описаний массивов, но великолепно динамически работает с массивами.

Явное описание данных или декларация служит трём главным целям.

1. Более эффективное хранение структур данных и доступ к ним. Наиболее очевидная цель декларации состоит в том, чтобы указать свойства структур и данных, остающиеся неизменными во время выполнения программы. Транслятор оптимальным образом размещает данные в памяти и генерирует соответствующие команды работы с данными.

2. Улучшение управления памятью. Именно декларация позволяет определить области видимости данных и время их существования. Декларация позволяет применять к управлению данными более простые алгоритмы. Если массив объявлен и имеет статическое распределение в памяти, то достаточно знать тип данных и границы массива. Если массив создаётся динамически и размеры его могут быть динамически изменены в ходе работы программы, то необходимо где-то хранить информацию о точках создания и уничтожения или перераспределения массива, кроме того, чаще всего добавляется информация от операционной среды о блоках памяти и т.п.

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

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

Реальные языки программирования имеют полный набор способов деклараций, от обязательного в языке Cи и Cи++ до их отсутствия в Basic. Многие языки позволяют выполнять неявные декларации: Fortran – все необъявленные переменные с первой буквой I … N – целые, остальные плавающие.


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

Таким образом, сначала даётся собственно описание данных, а затем операций, которые можно совершать с описываемыми данными. Схема общая. Если вы возьмётесь описывать любой объект, то всегда сначала описываете, что этот объект представляет, а затем - что можно с этим объектом делать: какие операции может выполнять сам объект и какие операции можно выполнять над объектом.

Аппаратное описание данных, теперь как правило, рассматривается в курсе архитектуры ЭВМ. Современные средства программирования достаточно далеко «отодвинули» среднего программиста от аппаратуры. Здесь мы не будем касаться аппаратных представлений, наша цель выполнить обзор существующих структур данных.

Итак, данные. Простые переменные. Идентификатор, который в течение всего времени выполнения программы связан с одним простым элементом данных, называется простой переменной. Одним из простых элементов данных являются числа. Как они представляются в памяти машины? Обычной практикой является прямое использование аппаратного представления.

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

Дробные числа, обычно, представляются плавающими. Обычно аппаратура позволяла работать с простым плавающим числом или с двойным. Не следует забывать, что ещё 286 ПЭВМ не имели встроенных средств для работы с плавающими числами.

Мы достаточно обсуждали особенности работы с плавающими и целыми. Важно, что вышеуказанное представление, позволяет сразу обратиться к числу как к единому целому. Одна операция доступа и мы получаем целиком число. Дескрипторы, обычно, отсутствуют.

Комплексные числа, чаще всего не имеют аппаратного представления. Их очень удобно представлять программно в виде пар плавающих чисел, например в виде структуры. Код достаточно простой, чтобы его здесь приводить. Сейчас, делается немного по-другому, а именно, строится класс «комплексные числа», но это обсудим позже.

Несколько сложнее обстоит дело с рациональными числами, если мы хотим представить их непосредственно в виде простых дробей. В процессе вычислений знаменатели имеют тенденцию неограниченно возрастать, что приводит к тому, что представлению рациональных чисел в виде пары целых не хватает длины аппаратного представления. Таким образом, для простого (с точки зрения математики) представления рациональных чисел требуется значительный объём программного моделирования. Отметим, что программное моделирование требует, прежде всего, моделирования всех операций.

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

Как представляется не числовая информация? Поскольку минимально адресуемой частью памяти является байт, то каждому состоянию байта соответствует один символ. То есть мы имеем таблицу из 256 значений, где на соответствующих местах находятся определённые алфавитные символы. На самом деле, этого числа значений достаточно только для алфавитного письма. Уже слоговые азбуки не все можно реализовать в этом количестве значений, идеографические системы совершенно не помещаются в эти границы. Поскольку таблицу соответствия составляет человек, то ясно, что конкретных кодировок составлено множество. В совремённом мире используется около 25 систем письма, а различных кодировок этих письменностей известно более 170.

В младшей части кодовой таблицы (коды от 0x00 до 0x79) расположена таблица ASCII – American Standart Code for Information Exchange. В этой таблице находятся латинские буквы, цифры, знаки препинания и общепринятые управляющие символы. Все национальные кодировки расположены во второй половине таблицы, от кода 0x80 до кода 0xFF. Нас, прежде всего, интересуют таблицы кодировки кириллицы.

В 74 году вышел ГОСТ-19768-74, который определил первую восьмибитную кодировку кириллицы. Код, задаваемый этим гостом известен как таблица КОИ-8. Эта таблица, относительно кириллицы, имеет массу недостатков: нарушен алфавитный порядок кириллических символов, что создаёт трудности при сортировке строк и их сравнении. Несмотря на это именно КОИ-8 стала стандартной кодировкой русифицированных версий системы Unix. Она же была предложена в качестве основы для кодировки ISO-IR-111, предложенной в качестве общеевропейского стандарта. Кроме того, в 1993г. в таблицу добавили букву ё и символы псевдографики и стали использовать сначала в сети РЕЛКОМ, а затем в Internete. То есть КОИ-8 стала стандартом для русскоязычной электронной почты.

Параллельно, с приходом в Россию компьютеров клона IBM и операционной системы MS-DOS появилась таблица кодировки, которая называется альтернативной. Она используется всеми программами, работающими под управлением DOS. Ясно, что приход системы Windows принёс с собой новую таблицу кодировки: Windows-1251.

В результате всего сложилась следующая ситуация: Большинство Web-серверов и почтовых серверов работают под управлением Unix-систем, поэтому для них стандартной кодировкой является код КОИ-8Р. Большинство клиентских машин работает под управлением Windows и для них стандарт – Windows-1251. Альтернативная кодировка используется при эмуляции DOS системой Windows. Кроме того, есть ещё и Macintosh, где, конечно же, другая таблица перекодировки.

Ситуация сложилась совсем ненормальная. Поэтому лет десять назад пришла идея создать единую таблицу для всех национальных алфавитов. Такой подход был предложен стандартом Unicode, или ISO/IEC 10646. Кажется, что это нереально. Однако из примерно 6700 живых языков официальными являются только около 50, которые пользуются примерно 25 системами письменности. Эти цифры вполне приемлемы. Для кодировки Unicode необходимы уже двухбайтовые коды символов. Unicode обладает целым рядом положительных качеств. Прежде всего, это не просто большая таблица кодировки, а база данных. Здесь каждому коду сопоставлен определённый символ, имеющий набор свойств и изображающую его графему. Такая база позволяет преобразовывать строчные буквы в прописные и обратно, сортировать строки и многое другое. При этом блок кириллицы в Unicode включает все живые кириллические алфавиты: русский, украинский, белорусский, болгарский и т.п., а также все буквы церковно-славянской письменности.

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

1. Операционные системы должны поддерживать Unicode на уровне ввода, хранения и отображения текстовых строк.

2. Необходимы «умные» драйвера клавиатуры, позволяющие нам вводить символы любого блока Unicode и передающие их коды операционной системе.

3. Прикладные программы должны поддерживать отображение всех символов Unicode и выполнять над ними общепринятый набор символьных операций.

4. Должна быть поддержка всех устаревших кодировок, так как они будут ещё некоторое время существовать параллельно с Unicode.

Последовательного решения всех этих задач нет пока ни в одной операционной среде. -

Тем не менее, следует знать, что в Cи++ предусмотрен тип wchar_t – для представления строк Unicode. Опять-таки официально заявлено, что этот тип сохраняет все свойства short int. Скорее всего, он представлен последовательностью целых полуслов.

Рассмотрим попутно и такую простую задачу, как перекодировка. Принципиально её должен понимать каждый грамотный программист. Задача ставится так: в последовательности символов заменить одни символы на заданные другие. Ясно, что у нас должна быть таблица соответствия одних символов другим. Тогда просмотрев первую таблицу и найдя там перекодируемый символ, мы по тому же индексу выбираем символ из другой таблицы и подставляем вместо исходного.

Реально используется несколько другой алгоритм. Входной символ рассматривается как индекс, по которому из таблицы выбирается замещающий его символ. Во-первых, такой алгоритм требует всего одну таблицу вместо двух. Во-вторых, скорость его работы не зависит от перекодируемого текста, так как нет последовательного просмотра таблицы. Тогда программа перекодировки может выглядеть следующим образом.


Пусть void Transl (char * A, int La, char * Tbl, char * B); обращение к программе перекодировки, где: A – входная строка; B – выходная строка; La – длина входной строки; Tbl – таблица кодировки. Согласно стандарту языка Cи программа будет такая:


for (int i = 0; i < La; i++)

*(B + i) = * (Tbl + (*(A + i))); // здесь используется, что char в “Cи”

// рассматривается как int !


Реально такой код поддерживается не всеми трансляторами. Watcom Cи, например, справился с таким кодом и реально сгенерировал правильную программу, но Borland Cи не стал этого делать. Под Borland и, конечно Cи++Builder программу надо немного подкорректировать, оставив идею прежней:


union IntChar {

int j;

char C[4];

} Indx;

int i;

Indx.j = 0;

for (i = 0; i < La; i++) {

Indx.C[0] = *(A+i);

*(B+i) = *(Tbl + Indx.j);

}


Перекодировки используются не только при «оформлении» документа, но и в системах секретности.


Представление строк уже требует определённой структуризации элементов данных. Обычно применяют, по крайней мере, три схемы:

1. Цепочки фиксированной длины, задаваемой в декларации. Допускаются операции, не изменяющие длины цепочки. Элементы цепочки, символы/литеры можно сравнивать, заменять. Изменение длины цепочки сопровождается либо усечением цепочки при увеличении её длины, либо добавлением пробелов справа. Такой способ используется, например в Cobole.

2. Цепочки переменной длины, предел которой задаётся в декларации. В декларации указывается максимальная длина цепочки. Цепочка обрезается по длине, если её длина превышает заданный предел. Этот метод используется в PL/1.

3. Цепочки неограниченной длины. Длина цепочки может быть произвольной. Декларации о предельной длине не требуется. Память для хранения цепочки выделяется по мере необходимости. (Снобол 4).

С представлением строк в Cи++ мы уже знакомы. Фактически в Cи нет типа данных string, как например, в Pascale. Здесь в Cи мы имеем дело с обычным массивом знаков.

В Pascale мы имеем более широкий выбор:

String – как строка длиной не более 255 символов, первый байт которой содержит описатель длины.

AnsiString – строка неограниченной длины. Этот тип сохранён и в Cи++Builder и его можно использовать при программировании на Cи++. Важно отметить, что для этого типа определены все обычные операции для строк, чего, фактически, нет в Cи для обычных строк. Реально AnsiString представляет собой довольно не простую структуру, где и хранятся все сведения о цепочке. При работе с AnsiString вы получаете доступ как ко всей строке целиком, так и к каждому элементу строки в отдельности. Поскольку вся работа с AnsiStirng реализована на Pascale, то начальный индекс элементов строки, как массива будет не 0, а 1. Работа с AnsiString сильно упрощает жизнь, так как для этого класса реализованы все необходимые операции и функции, но следует помнить, что этот тип есть только в Cи++Builder (Delphi – тоже).
В Cи++ AnsiString определён, как class в заголовке dstring.h.

AnsiString преобразуется в обыкновенную строку функцией c_str():


AnsiString St; char Bu[128]; Bu = St.c_str();


Функцией WideChar AnsiString преобразуется в тип wchar_t:


AnsiString St; wchar_t Wbu[128];

wchar_t * U; U = St.WideChar(Wbu, 128);

Не ясно, почему, но возвращаемый указатель должен отличаться от указателя аргумента. Возможно и обычное применение: St.WideChar(Wbu, 128);


WideString – также строка неограниченной длины, но символы двухбайтовые, позволяющие представлять строки Unicode. Этот тип также сохранён в Cи++Builder и с ним также можно работать, как с AnsiStirng. Определён тип WideString как class в заголовке wstring.h. Принципиально вы можете выполнить присвоение AnsiString ->
WideString. Всё отработает правильно. Однако обратное присвоение в общем случае может привести к неясным ошибкам. Обычно это бывает, тогда когда WideString содержит знаки wchar_t. Поэтому пользоваться WideString следует осторожно, только тогда, когда это действительно необходимо.

Попутно обратим внимание на присвоение данных строкам типа wchar_t. Нельзя написать обычное присвоение, как это делалось со строками char – теперь типы данных разные. Такое присвоение выполняется, если перед строкой поставить букву L – что означает длинные знаки. Однако типу WideString можно присваивать данные достаточно свободно.


Наконец, у нас есть Basic. В нём тоже есть строки и их представление совершенно отлично как от Pascal, так и от Cи. При межъязыковом программировании вопрос представления строк становится очень важным. Фактически, сегодня идёт революция в программировании, а именно стремительное нашествие Active X. Поскольку основные концепции в Active X, были предложены фирмой MicroSoft, то следует ожидать широкого использования Basic, что и имеет место. Таким образом, появляется ещё один тип представления строк – BSTR. Первоначально этот тип был сконструирован специально для совместимости со строками Basic, но впоследствии он стал широко использоваться в COM – технологиях и теперь о Basic напоминает только первая буква в имени типа. BSTR легко перевести в WideString и обратно, но при этом часто возникают определённые проблемы, которые легче обсудить в рамках темы COM – технологии.


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

Уже в языке PL\1 появились указатели: переменные этого типа могли получать значение адреса любой другой переменной, с ними можно было выполнять простые арифметические операции. То есть, через указатели в языке PL\1 реализовывалась обыкновенная адресная арифметика, а тип указатель в PL\1 был синонимом типа адрес. Указатель мог быть настроен на адрес переменной любого типа, то есть, сам указатель не имел типа. Автор до сих пор гадает, почему разработчики PL\1 спрятали тип «адрес» за псевдонимом «указатель» и почему тип «адрес» так и не был реализован ни в одном алгоритмическом языке. Отметим также, что в любом руководстве по PL\1 указывалось, что указатели это средство, как сейчас бы заявили, для продвинутого программиста и что использовать указатели надо весьма осторожно, так как они могут быть источником плохо диагностируемых ошибок.

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

К тому же структура и синтаксис языка Си таковы, что принуждают программиста к использованию указателей с самого начала (более подробно см. ниже). Но начинающий программист весьма смутно представляет, что такое адрес, а уж что такое указатель понять ещё тяжелее. Учтите при этом, что “*” используется в Си при указателях в двух смыслах: объявление указателя и операция разыменования. Таким образом, указатели в Си стали источником бесконечного числа ошибок. Дошло до жаркой дискуссии о необходимости указателей в языке.

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

Требование обязательного описания данных достаточно жёстко и нередко препятствует выполнению некоторых «программистских трюков». Впрочем, это теперь так называют некоторые приёмы, ранее широко используемые грамотными программистами. Это в некотором смысле «противозаконные» способы обработки информации. С точки зрения программиста на Assemblere – это обычная практика. Другой разговор, что это противоречит, некоторым парадигмам, декларируемым авторами алгоритмических языков, правда, сами они, не задумываясь, используют эти «незаконные» приёмы.

Одним из способов законного обхода парадигмы обязательного описания данных будет возможность рассмотрения одной области памяти как области одновременного нахождения нескольких переменных разных типов. Приём очень старый, используемый уже в языке FORTRAN: COMMON области. В Си это называется объединение – union. Объявление объединения начинается ключевым словом union, за которым может следовать необязательное описание типа, затем открывающая фигурная скобка, перечисление переменных, закрывающая фигурная скобка и необязательные имена переменных:

union < имя типа > {

int A;

float B;

char c[4];

} Un;

Хитрость в том, что адрес начала всех трёх переменных (A, B, c) один и тот же, то есть все три переменных занимают одну область памяти. Тогда для переменной Un.A генерируются транслятором команды работы с int, а для переменной Un.B транслятор генерирует команды работы с float. Рассматривая Un.c[i], мы работаем с i-ым байтом целого или плавающего, но рассматриваем его как символ. Таким образом, мы с одной стороны указали транслятору, когда какие команды генерировать, с другой стороны мы, фактически имеем тип данного, отсутствующий в языке.

Дело, конечно, не в том, чтобы иметь некий странный тип данных, а в том, что существует множество задач, где жёсткое предварительное задание типа данных существенно ограничивают возможности программиста. Например: вам необходимо просто скопировать одну область памяти в другую. Из условия задачи ясно, что тип данных находящихся в памяти совершенно безразличен как программисту, так и для алгоритма реализации. Однако в Си вы будете вынуждены задать тип данных на обе области памяти, более того это должен быть один тип (чаще всего для описания областей памяти используется тип char). В большинстве подобных случаев требование обязательного описания данных приводит к неоправданному увеличение трудоёмкости реализуемой задачи: вам требуется простенькая функция получения абсолютного значения числа – в Си их аж две: abs для целого и fabs для плавающих, это ещё хорошо, что fabs работает как с float, так и с double.

В Cи++ есть немало способов обхода «парадигмы обязательного описания данных», мы обязательно обсудим часть из них ниже, но дело в том, что нередко требуется средство работы с данными, тип которых определяется динамически. Частично эту проблему в Cи++ снимает тип Variant. Реализован этот тип через обычный union (существует и class Variant – не путать!). В объявлении union Variant просто перечислены наиболее часто встречающиеся типы данных и некоторые, более экзотические типы. Для Variant определены все основные операции. Есть возможность объявить массив типа Variant, но в целом работа с этим типом чрезвычайно неудобна, к тому же требуется знание некоторых макроопределений, которые почти не документированы. Однако, уже попадая в такую область, как работа с базами данных, вы сталкиваетесь данными, тип которых определяется динамически, а, следовательно, и с типом Variant.


Обратим внимание, что уже простое обсуждение представления строк привело нас к незаметной работе с агрегатами данных. Простая строка в Cи – уже массив знаков.

Массивом называется набор элементов одинакового типа. Для работы с любым массивом нам нужно знать его начальный адрес, длину элемента и количество элементов. Tогда адрес i – го элемента получается просто: A + i * l: где l – длина элемента в байтах; i – индекс элемента (при условии, что начальный индекс 0), А – адрес первого элемента. Это самая простая схема. Именно она положена в основу работы с массивами в Cи. Отметим, что при таком представлении, массив занимает непрерывную область памяти машины! Тогда способ адресации памяти в машине накладывает ограничения на максимальную величину массива. Вспомним ограничение в 64K на первых персоналках или в DOSe. Основная проблема при работе с таким агрегатом: не уйти за границы массива. Транслятор не может проверить корректность вашего обращения, поскольку конкретный индекс вычисляется только при работе программы. Следующий момент – инициализация массива. Программист не всегда знает максимальное число элементов в массиве. Тогда он размер массива определяет так, чтобы с гарантией иметь массив, вмещающий все предполагаемые элементы. Значит, чаще всего, часть массива остаётся пустой и, следовательно, программист обязан сам контролировать обращения к массиву, чтобы не обратиться к несуществующему элементу, точнее к непроинициализированному.

В большинстве языков нет операций с массивами. То есть, вы не можете выполнить присвоение A = B, если A и B массивы. Точно также, обычно, вы не можете присвоить массиву скаляр. Здесь язык Cи не исключение. Своеобразие языка Cи в том, что имя массива может использоваться в качестве указателя, что приводит к двусмысленному синтаксису. Если вы имеете следующее описание функции:

void Transp (double * A);  то по нему невозможно сказать, что реально должно быть передано в функцию: скаляр или массив! Внутри же функции вы можете обращаться к параметру и как элементу массива и как к простой переменной. Почему это появилось? Да очень просто, как не хотелось создателям языка Си сохранить парадигму передачи параметров в подпрограммы по значению, но они прекрасно понимали, что массив передать по значению весьма накладно. Для передачи массива по значению (так как это организовано на ПЭВМ) необходимо было иметь запас памяти по объёму не менее двойного объёма исходного массива: надо было скопировать массив в стек, а затем из стека скопировать значения в массив в подпрограмме. Вот и получается, что скалярные переменные передаются по значению, а массивы – по ссылке. Впрочем, это не единственная нелогичность языка Си.

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

Запросить память можно оператором new, а освободить оператором delete,

new тип <[ количество ]>; Оператор возвращает указатель на выделенную память. Тип указателя обязан совпадать с типом выделяемой памяти. Если по каким – либо причинам память выделена не была, оператор new вернёт NULL. Последнее поддерживается не всеми трансляторами. Новейшие трансляторы формируют исключение bad_alloc и предлагают программисту проверить это исключение в блоке catch, что достаточно неудобно. Кроме того, существуют старые программы, которые «не знают», что такое блок catch. Поэтому, если программисту не хочется возиться с исключениями, что чаще всего и бывает, то он поступает следующим образом:

например: int * A; A = NULL;

A = new int;

if (A == NULL) действия по ошибке выделения памяти.

Пример запроса памяти под массив:

double * B;

int M = 10;

B = new int [M] ;

ещё раз подчёркиваем, к переменной B можно обращаться как к элементу массива - B[i].


Если вы получили память по оператору new, то при завершении работы полученную память необходимо освободить оператором delete. Ни система, ни транслятор не могут проконтролировать- следует ли освобождать память при завершении программы – это целиком возложено на программиста.


delete < [ ] > имя;


например: delete A; или освобождение памяти, выделенной под массив:

delete [] B;


Вообще говоря, в Cи имеются только одномерные массивы. Но правилами языка не оговаривается, что может быть элементом массива. Единственное требование, чтобы это были одинаковые элементы. Тогда возможны массивы массивов или двумерные массивы. Однако, если синтаксис объявления двумерного массива прост, то динамический запрос памяти под двумерный массив и передача его в функцию вызывает затруднения. Приведём программу, динамически запрашивающую память под двумерный массив:


double * * matr;

int i;

int k;

………………………………………………………………………………….


matr = new double * [k];

for (i = 0; i < k; i++) matr[i] = new double [k];


…………………………………………………………….


for (i = 0; i < k; i++) delete [] matr[i];

delete [] matr;

Обратим внимание на то, как объявлен массив matr: указатель на указатель типа double. Первым шагом мы распределяем массив указателей (строку), а затем только получаем память под собственно переменные типа double. Таким образом, памяти нам понадобилось на k элементов больше, поскольку k элементов заняты указателями.

Кроме того, память запрашивалась строками и значит никто не гарантирует непрерывного блока памяти под весь массив! Строка от строки может находиться далече, хотя чаще всего, память выделяется одним блоком. Наконец, обращение к
i – тому элементу теперь идёт за два обращение к памяти, а следовательно дольше.
Надо отметить, что имеются и небольшие плюсы. Немного изменим выделение памяти в вышеприведённой программе:


matr = new double * [k];

for (i = 0; i < k; i++) matr[i] = new double [m[i]];

где int m[k];


из приведённого текста видно, что можно распределять строки разной длины,
сохраняя длину каждой строки в массиве m. Если вопрос экономии памяти стоит очень остро, то хоть здесь мы имеем небольшое преимущество.

Аналогичным образом можно иметь трёхмерный массив и т.д. Ясно, что накладные расходы растут. Для двумерной матрицы 10x10 у нас 10 лишних элементов, что составляет 10%, хотя для такой же матрицы 1000x1000 это всего лишь 0,1%. Для аналогичных трёхмерных матриц эти цифры в процентах останутся примерно такими же. Расходы падают с увеличением размера массива, но вся проблема в том, что у нас, как правило, нет очень больших массивов. Однако основной рост не в размере памяти, а увеличении времени обращения к элементу массива.

Конечно, следует помнить, как распределяется массив: в Cи самый правый индекс растёт быстрее всего – то есть массив распределён по строкам.


В Pascale при объявлении задаются границы изменения индекса массива:

например:

Var

MyAr : array [24..40] of Integer;

или двумерный массив:

MyArr : array [-1..23, 100..200] of Integer;

Существуют две функции: Low (array) и High(array), которые позволяют получать соответственно нижнюю и верхнюю границы массива. Массивы также можно распределить динамически (Delfi), для чего при объявлении массива ни задаются границы измерения.

DinAr : array of Integer; или DinArr : array of array of Integer;
Задание конкретных размеров массива выполняется специальной функцией SetLength.
Можно перераспределить массив функцией Copy. Обратим ваше внимание на то, что нет даже речи об удалении массива.

Таким образом, где-то хранятся как границы измерения, так и адрес самого массива. Освобождение памяти от распределяемых массивов по- видимому выполняется перед завершением работы всей программы.


Следующий часто применяемый агрегат данных – структура.

Структура – объединение данных разных типов. В Си структура начинается ключевым словом struct, затем идёт необязательное имя типа, фигурная скобка, собственно начинающая структуру, закрывается структура также фигурной скобкой, за которой может следовать необязательное имя переменной. Внутри скобок перечисляются члены структуры: данные простых типов, либо массивы, либо также структуры. Структура в Си используется в двух смыслах: если задано «имя типа», то везде далее вы можете ссылаться на это имя как на некий абстрактный тип данных, создавая объекты этого типа. Если «имя типа» не задано, но сразу заданы имена переменных (за закрывающей скобкой структуры), то распределяются объекты типа заданной структуры, но нет возможности ссылаться на структуру, как на абстрактный тип, так как нет имени типа. Задавая сразу «имя типа» и имена переменных, мы совмещаем эти два случая. Обычно программисты используют структуры именно для описания абстрактных типов данных. Данные, перечисляемые в структуре располагаются в памяти в том порядке, как они объявлены в структуре. К любому элементу структуры можно обратиться, указав сначала имя переменной типа структуры, а затем через точку имя элемента. Структура передаётся в подпрограммы по значению (ещё одна нелогичность языка Си, структура всё-таки агрегат и может быть произвольно большим!). Если вы объявляете структуру как тип, то не можете инициализировать внутренние элементы структуры, так как в этом случае, структура используется только как описание типа для транслятора. Если два объекта имеют тип одной структуры, то для них в Си определена операция присвоения (=).

В Pascale структуры называются запись – record. использование записей в Pascale примерно такое же, как и в Си, с поправкой на синтаксис.


Структуры появились, когда потребовалось автоматизировать работу с файлами заданной структуры. Запись такого файла очень удобно представлять в виде структуры. Однако, правилами языка Си не запрещено в структуру помещать любой тип переменных. Тогда помещая в структуре объявление функции, вы получаете весьма своеобразный объект. Вы получаете набор некоторых данных, объединённых с набором некоторых операций (если рассматривать функцию как операцию). Более того, функции получаются «приписанными» к конкретным объектам: вы не можете обратиться к функции объекта, не указав перед обращением его имя через точку. Таким образом, мы получили набор разных объектов одного типа, которые ещё и ведут себя вполне индивидуально (!), так каждый из этих объектов может ссылаться на свою «личную» функцию, определяющую то или другое поведение объекта. Другими словами – с помощью структур можно моделировать объекты. Это в своё время и заметил Бьёрн Страуструп. Почему он в Cи++ ввёл новый термин class, предоставив, тем не менее, структурам почти те же возможности, лучше выяснить из его же книги [8]. Само понятие класса и объекта мы обсудим несколько ниже в главе посвящённой ООП – объектно-ориентированному программированию.


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

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

^ Стек (stack): структура данных с одним входом в который можно последовательно помещать произвольные объекты. Объекты можно извлекать через вход в порядке обратным поступлению. Из определения видно, что стек осуществляет стратегию: первым пришёл – последним ушёл. Примером стека может быть обыкновенный железнодорожный тупик, в который можно последовательно загонять вагоны. Понятно, что вагоны можно выгнать из тупика только через вход в порядке обратном поступлению.

В случае программной реализации стека он представляет собой некоторую область памяти. В самом простом случае для работы со стеком необходимы только две операции: поместить в стек – push (объект) и получить из стека – pop(). Но так просто стек моделируется только тогда, когда работает с ограниченным кругом объектов, например, вы помещаете в стек только натуральные числа. Тогда возврат операцией pop() нуля может рассматриваться, как признак пустоты стека. То есть, в более сложных случаях необходима возможность получать два свойства стека: «стек пуст» (empty) и «стек заполнен» (обычно, пишут «переполнен»). Нередко, можно получить размер стека (size).

Если помещаемые в стек объекты одного типа, то при моделировании достаточно массива одного с помещаемыми объектами типа. Если же в стек помещаются объекты разных типов, то где-то необходимо вести таблицы что, в каком порядке и какого размера находится в стеке.

^ Очередь (queue): структура данных с одним входом и одним выходом. Объекты могут последовательно помещаться в очередь через вход и извлекаться из очереди в том же порядке через выход. Очередь осуществляет стратегию: первым пришёл – первым ушёл. В обыденной жизни мы постоянно сталкиваемся с очередями, очередь на получение услуги, например. Максимально приближаясь к жизни, можно определить очередь с приоритетами: объект помещается в очередь согласно определённым условиям и извлекается из очереди в том же порядке.

Таким образом, у очереди также две операции: push (объект) - поместить объект в очередь и pop() – извлечь объект из очереди. Но с очередями чаще всего эти операции имеют другие имена: push_back(объект) – подчёркивается, что объект помещается в конец очереди; pop_front () – объект извлекается из начала очереди.

Очевидно, что очереди также имеют свойства «очередь пуста», «очередь заполнена», «размер очереди». Кроме того, весьма важно знать число объектов находящихся в данный момент в очереди.

^ Дека, двусторонняя очередь (deque): структура данных с двумя входами, в любой из которых можно последовательно помещать объекты. Извлекать объекты можно через эти же входы. Дека, фактически, совмещает свойства стека и очереди.
Операции: push_front(объект), push_back(объект), pop_front(), pop_back(). Те же свойства: «дека пуста», «дека заполнена», «размер деки», «число реальных объектов в деке».

^ Список (list): структура данных имеющая начало, каждый элемент которой имеет ссылку на следующий. Помещение объектов возможно как в конец, так и в середину. Такой список называется прямым. Если список имеет прямой доступ к концу, вместо начала, а хранимые при объектах ссылки указывают на предыдущие члены списка, то список называется обратным. Наконец, возможна модификация списка с доступом, как к концу, так и к началу и двусторонними ссылками. Операции: push_front(объект), push_back(объект), pop_front(), pop_back(), insert(объект) – вставить объект в середину; erase (объект) – удалить объект из любого места. Свойства: «число объектов в списке».

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

Обратите внимание, что при определении структур данных мы нигде не требовали однотипности объектов, помещаемых в описываемую структуру. Все структуры рассматривались как некие хранилища данных, в которые может быть помещён объект любого типа. При реализации, однако, мы сталкиваемся с ограничениями языка. Язык Си, как язык с обязательным описанием данных, более всего препятствует приближению к определению. Вы не можете в Си создать стек, сам по себе – объекты, помещаемые в стек должны иметь заранее продекларированный тип (!), более того все объекты должны быть однотипными. Таким образом, вы можете создать стек целых, плавающих, стек, содержащий любые заранее объявленные структуры, стек стеков, стек очередей и т.п., только не стек, хранящий объекты любых типов.

Конечно, в Си имеется «костыль» шаблонов, но это слабое утешение: вы не можете обойти требование однотипности объектов. Возможно использование типа Variant. Но, во-первых, этот достаточно неудобный в использовании класс, поддерживается не всеми трансляторами, а во-вторых, в общем, вы опять работаете с одним типом данных – Variant.

Фактически, мы опять подошли к обсуждению вопроса хорошо это или плохо требование обязательной декларации данных. Всю историю языка Си (Си++) можно рассмотреть с точки зрения: как уйти от парадигмы «обязательного описания данных», оставшись внутри этой парадигмы. С одной стороны имеется очень жёсткая парадигма «обязательного описания данных», с другой стороны на сегодняшний день имеются сложные аппараты обхода этой парадигмы. С третьей стороны существует Basic, где такого вопроса нет по определению. Возникает вопрос (стоит ли овчинка выделки?) окупаются ли усилия по разработке достаточно сложных аппаратов ухода от этого кошмара? Не дешевле ли просто на определённом этапе отказаться от самого принципа, вставив в язык возможность объявлять переменные тип которых определяется динамически, при выполнении программы обрабатываемыми данными: тип определяемый самими данными. Интересно, понадобятся ли программисту шаблоны, если он будет иметь такой тип переменных?


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

Контейнер – некоторая структура данных, в которой можно хранить объекты. Для любого контейнера должен быть определён порядок помещения объекта в контейнер, порядок извлечения объекта из контейнера и, возможно, порядок доступа к объекту в контейнере.

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

Таким образом, единственное, что требуется от контейнера это способность быть хранилищем чего-либо. Опять-таки заметим, что однотипности помещаемых в контейнер объектов, по определению, не требуется. Если на Assemblere реализация контейнера не вызывает проблем, то в Си++ мы сразу же обнаруживаем, что реализация контейнера согласно определению невозможна, так как в контейнер могут помещаться только однотипные элементы, однако «типизированные» контейнеры возможны.

Сама идея контейнера, как ни привлекательна она для теории, для практического использования всё-таки малопригодна. Мало что-то хранить в кладовке, надо знать, что там хранится и как быстро извлечь это оттуда.

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

Далее, обычно, определяют несколько базовых контейнеров, пользуясь которыми, строят все остальные структуры данных. Для примера, в STL [1] (Standart Template Library), базовыми последовательными контейнерами являются vector, deque и list. Такие структуры, как stack, queue, моделируются так называемыми адаптерами. Принципиально все структуры можно определить, имея только лишь один базовый контейнер, однако, скорость доступа к объектам и скорость выполнения операций (помещение в контейнер, удаление и т.д.) у специализированных контейнеров будет ниже, чем у обобщённого контейнера. Это понятно: за общность приходится платить скоростью операций.

С контейнерами связано ещё одно понятие. Если мы в контейнер можем поместить любой объект, в том числе и другой контейнер, то использование простого индекса при доступе к объектам контейнера становится затруднительно, а часто и невозможно. Всё дело в том, что теоретически контейнер не зависит от размера памяти и её строения. То есть, предполагается, что программист может помещать в контейнер объекты столько раз, сколько ему понадобится при выполнении задачи. Однако, в реальности приходится как-то учитывать ограничения по памяти. Это приводит к тому, что выполняется первичное распределение памяти под контейнер вполне определённого объёма. (В STL [1], например, первично выделяется 1К памяти, если размеры объектов, помещаемых в контейнер, не превышают 1К, или же запрашивается память только под один объект). Когда размера контейнера не хватает под следующий помещаемый элемент, выполняется перераспределение контейнера с удвоением его размера. Это приводит к тому, что адрес запрашиваемого объекта, должен определяться снова при каждом обращении к контейнеру. Это привело к понятию итератора: итератор – некий обобщённый указатель на объект, находящийся в контейнере. Работа с итераторами напоминает работу с указателями, но это не указатель.

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


Вопросы к главе 5.


1. На какие две группы можно разбить данные, существующие во время работы программы.

2. Для чего существует декларация данных?

3. Какие проверки типа данных существуют?

4. Встроенные типы данных.

5. Представление в машине символьной информации.

6. Что такое Unicode?

7. Программа перекодировки.

8. Схемы представления строк.

9. Что такое массив. Схемы представления массива в памяти.

10. Предложить программу распределения памяти под двумерный массив в Си++.

11. Что такое структура?

12. Специфические и универсальные операции.

13. Операторы new и delete в языке Cи++.

14. Агрегаты данных: перечислить известные, подробно рассказать о любом.

15. Объединение в Cи.

16. Стек и очередь.

17. Список и дека.

18. Контейнер?

19. Итератор?

20. Последовательные и ассоциативные контейнеры?

21. Тип Variant – что такое? реализация?