Алгоритмы и структуры данных

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

1.1.2. Данные символьного типа

Значением символьного типа char являются символы из некоторого предопределенного множества. В качестве примеров этих множеств можно назвать ASCII (American Standard C0de f0r Inf0rmati0n Interchange). Это множество состоит из 256 разных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы.

Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы.

ASCII включает в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают «свободные места» в таблице кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен во множестве UNICODE. В этом множестве каждый символ кодируется двумя байтами, что обеспечивает более 2¹⁶ возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты. UNICODE, безусловно, является перспективным, однако, повсеместный переход к двухбайтным кодам символов может вызвать необходимость переделки значительной части существующего программного обеспечения.

Специфические операции над символьными типами - только операции сравнения. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами.

1.1.3. Данные логического типа

Значениями логического типа может быть одна из предварительно объявленных констант false (ложь) или true (истина).

Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true -любое ненулевое значение байта.

Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), ИСКЛЮЧАЮЩЕЕ ИЛИ (xor). Последняя операция реализована для логического типа не во всех языках.

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

Интересно, что в языке Си данные логического типа отсутствуют, их функции выполняют данные числовых типов, чаще всего типа int. В логических выражениях операнд любого числового типа, имеющий нулевое значение, рассматривается как «ложь», а ненулевое - как «истина». Результатами выражений логического типа являются целые числа 0 (ложь) или 1 (истина).

1.1.4. Данные типа указатель

Тип указателя представляет собой адрес ячейки памяти. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы.

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

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

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

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

var

ipt:  ^Ainteger; cpt:  Achar;

Здесь переменная ipt содержит адрес области памяти, в которой хранится целое число, а cpt - адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, считается, что указатели ipt и cpt имеют разный тип.

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

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

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

Операция получения адреса - одноместная, ее операнд может иметь любой тип. Результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес операнда.

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

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

 

1.2. Линейные структуры данных

Рассмотрим статические структуры данных: массивы, записи, множества. Цель описания типа данных и определения некоторых переменных, относящихся к статическим типам, состоит в том, чтобы зафиксировать диапазон значений, присваиваемых этим переменным, и соответственно размер выделяемой для них памяти. Поэтому такие переменные и называются статическими.

1.2.1. Массив

Массив - это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющих положение элемента в массиве.

Следующее объявление задает имя для массива, тип для индекса и тип элементов массива:

имя:  аггау[ТипИндекса]  of ТипЭлемента;

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

Количество используемых индексов определяет размерность массива. Массив может быть одномерным (вектор), двумерным (матрица), трехмерным (куб) и т. д.: var

Vector: array  [1..100]  of integer;

Matrix: array [1..100,  1..100]  of integer;

Cube:      array [1..100,  1..100,  1..100]  of integer;

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

Можно также выполнять операции над отдельными элементами массива. Перечень таких операций определяется типом элементов. Доступ к отдельным элементам массива осуществляется через имя массива и индекс (индексы) элемента:

Cube[0,0,10]   := 25;

Matrix[10,30]   := Cube[0,0,10]  + 1;

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

1.2.2. Строка

Строка - это последовательность символов (элементов символьного типа).

В Паскале количество символов в строке (длина строки) может динамически меняться от 0 до 255.

Рассмотрим пример описания строк:

var

TTxt: string; TWrd:  string[10];

Здесь описаны строка TTxt, максимальная длина которой 255 символов (по умолчанию) и строка TWrd, максимальная длина которой ограничена 10 символами. Каждый символ строки имеет свой индекс, принимающий значение от 1 до заданной длины строки. Следует обратить внимание, что существует элемент строки с индексом 0, который не доступен с использованием индекса, и содержит текущее количество символов в строке. Доступ к этому специфическому элементу можно получить только с помощью специальных функций языка.

Благодаря индексам, строки очень похожи на одномерные массивы символов, и доступ к отдельным элементам строки можно получать с использованием этих индексов, выполняя операции, определенные для символьного типа данных. Так же как и для массивов, определена операция присвоения строк в целом.

Однако есть ряд отличий. Операций сравнения строк больше, чем аналогичных операций для массивов: <, >, >, <, =, <>. Существует операция сцепления (конкатенации) строк «+».

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

1.2.3. Запись

Запись - это агрегат, составляющие которого (поля) имеют имя и могут быть различного типа.

Рассмотрим пример простейшей записи:

type

TPerson = record

Name:        string;

Address: string;

Index:      longint; end; var

Person1: TPerson;

Запись описанного типа объединяет три поля. Первые два из них символьного типа, а третье - целочисленного.

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

Можно также выполнять операции над отдельным полем записи. Перечень таких операций определяется типом поля.

Доступ к полям отдельной записи осуществляется через имя записи и имя поля:

Person1.Index := 190000; Person1.Name    := ^,Иванов';

Person1.Adress  := ^лСанкт-Петербург, ул. Б.Морская, д.67';

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

1.2.4. Множество

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

Множество - совокупность каких-либо однородных элементов, объединенных общим признаком и представляемых как единое целое.

Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются над структурами такого типа. Множество допускает операции объединения множеств «+», пересечения множеств «*», разности множеств «-» и проверки элемента на принадлежность к множеству «in». Множества, так же как и массивы, объединяют однотипные элементы. Поэтому в описании множества обязательно должен быть указан тип его элементов:

var

RGB, YIQ,  CMY:  set of char;

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

CMY := HM', 'C', 'Y']; RGB := HR', 'G', 'B']; YIQ :=  HY',   'Q',   'I'];

WritelnHnepece4eHMe цветовых систем RGB и CMY ', RGB*CMY); WritelnHnepece4eHMe цветовых систем YIQ и CMY ',  YIQ*CMY);

 

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

1.2.5. Таблица

Таблица представляет собой одномерный массив (вектор), элементами которого являются записи.

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

type

TPerson = record

Name:        string;

Address:  string;

Index:      longint; end;

TTable = array[1..1000]  of TPerson; var

PersonList: TTable;

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

Ключ таблицы (основной, первичный) - поле, значение которого может быть использовано для однозначной идентификации каждой записи таблицы. Ключ таблицы может быть составным - образовываться не одним, а несколькими полями данной таблицы.

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

Если последовательность записей упорядочена относительно какого-либо столбца (поля), то такая таблица называется упорядоченной, иначе - таблица неупорядоченная.