Заметим также в заключение, что ссылки, которые указывают на идентичные типы, можно сравнивать друг с другом с помощью знаков "=" и "< >", при этом P = Q, если:

а) P = NIL, Q = NIL;

b) P и Q указывают на один и тот же динамический объект.

11.5 Действия над динамическими переменными

Мы рассмотрели вопрос, когда речь шла о действиях над ссылочными переменными (указателями). Теперь обратимся к действиям над динамическими переменными.

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

Итак, DISPOSE освобождает память для нового использования. Динамические переменные, не стертые с помощью DISPOSE, продолжают занимать место в "куче" после окончания работы фрагмента программы (становятся "мусором"), их надо убирать.

ПРИМЕР 3. Порождение и последующее стирание двух динамических объектов

program UKAZATEL;

var A,B: ^integer;

K: integer;

begin

new(A); new(B); A^:= 1; B^:= 2;

K:= A^ + B^; write(K);

dispose(B); dispose(A);

end.

ПРИМЕР 4. Нахождение в вещественном массиве RA элемента с индексом, равным значению наименьшего элемента массива IA

program MINPOISK;

type RA = array[1..10] of real;

IA = array[1..10] of integer;

PR = ^RA; PI = ^IA;

var k,i: integer;

F: PR;

G: PI;

begin

{порождение динамического массива IA, поиск в нем наименьшего элемента с последующим уничтожением}

new(G); randomize;

G^[1]:= random(12) + 6; k:= G^[1];

for i:= 2 to 10 do begin G^[i]:= random(12) + 6;

rite(G^[i],' '); if G^[i] < k then k:= G^[i] end; writeln;

writeln('Вот значение искомого индекса = ', k); dispose(G);

{порождение динамического массива RA, поиск в нем k-го элемента}

new(f); for i:= 1 to 10 do

begin F^[i]:= random(12);

write(F^[i]:5:1) end; writeln;

writeln('Искомый элемент равен ',F^[k]:5:1);

end.

ПРИМЕР 5. Нахождение наибольшего из чисел, на которые ссылаются элементы массива указателей

program MZB;

const n = 10;

type S = ^real;

W = array[1..n] of S;

var X: W; i: integer; k: real;

begin

¦ {Порождение динамического массива }

¦ new(X[1]); X[1]^:= random(10) + 4;

¦ write (x[1]^:4:1,' '); k:= X[1]^;

¦ { Поиск наибольшего элемента }

¦ for i:= 2 to n do

¦ begin

¦ ¦ new (X[i]); X[i]^:= random(10) + 4;

¦ ¦ write (X[i]^:4:1,' ');

¦ ¦ if X[i]^ > k then k:= X[i]^;

¦ end;

¦ writeln; writeln ('Наибольший элемент: ', k:4:1);

¦ { Уничтожение сформированного массива }

¦ for i:= n downto 1 do dispose (X[i]);

end

ЗАМЕЧАНИЕ. В отличие от примера 4, где были образованы массивы, на которые указывали соответствующие ссылки (одна ссылка на весь массив), здесь весь массив состоит из ссылок, каждой из которых соответствует свой элемент порождаемого с помощью RANDOM массива. Поэтому для уничтожения массива примера 4 понадобился всего один оператор DISPOSE, а в примере 5 уже требуется уничтожать каждый элемент массива в отдельности.

11.6 Динамические структуры данных. Обработка цепочек

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

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

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

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

Есть три классические задачи работы со строками:

1) поиск вхождения заданной литеры в строку;

2) вставка заданной литеры в указанное место строки;

3) исключение литеры из указанного места строки.

Решение этих задач зависит от способа представления строки:

1) векторное представление;

2) представление строки в виде цепочки с использованием ссылочного и комбинированного типов.

Сюда относятся типы STRING и символьный массив. Например, слово PASCAL можно представить двумя способами:

VAR S1: STRING[6]; S2: ARRAY[1..6] OF CHAR.

В этом случае S1[1]='P', S2[4]='C'.

Итак, мы имеем непосредственный доступ к литере, и это удобно для решения первой задачи. Сложнее обстоит вопрос с решением задачи вставки элемента в строку (или удаления из строки).

Например, в слово PASAL нужно вставить пропущенную букву C PASCAL. Здесь элементы, идущие за вставкой, увеличивают свои индексы, т.е. после вставки надо проводить переиндексацию программным путем. Такая же ситуация и при удалении элемента.

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

ПРИМЕР 6. Удаление в литерном векторе элемента, следующего за указанным индексом

program UDAL;

const N =...

var ST: array[1..N] of char;

K, IND: integer;

begin {ввод строки, последний элемент = '#'}

¦...................

¦ writeln('индекс?'); read(IND); K:=IND+1;

¦ while ST[K]<>'#' do

¦ begin ST[K]:=ST[K+1]; K:=K+1; end;

end.

Эта задача решается гораздо проще, если представить литерный вектор с помощью типа STRING и применить процедуру DELETE, однако и здесь надо заранее заказывать длину вектора.

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

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

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

Геометрически это можно представить так:

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

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

Схематически это выглядит так:

Новый элемент при этом может быть размещен в любом свободном месте памяти.

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

Пусть в памяти ЭВМ находится цепочка (строка) 'PASCAL', которая инициализируется (связывается) с переменной-ссылкой STR. Это можно представить в виде схемы:

STR

Nil

1) CHAR - для обозначения самого элемента цепочки;

2) RECORD - для образования звеньев цепочки из двух полей;

3) ссылку (^) - для установления связи между звеньями.

Обозначим тип ссылочной переменной через SVYAZ, а тип динамической переменной через ZVSTR (звено строки). Этот факт описывается следующим образом: type SVYAZ = ^ZVSTR. Говорят, что тип SVYAZ указывает (ссылается) на компоненты типа ZVSTR, или тип SVYAZ связан с типом ZVSTR.

Чтобы объединить динамические переменные в цепочку, надо в каждой компоненте иметь ссылку на следующую. Исходя из этого, заключаем, что тип данных ZVSTR есть запись с двумя полями - полем символьного значения ELEM и полем ссылки SLED:

type ZVSTR = record

elem: char;

sled: SVYAZ;

end.

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

type SVYAZ = ^ZVSTR;

ZVSTR = record

elem: char;

sled: SVYAZ;

end.

Теперь остается с помощью VAR ввести ссылочную переменную (в нашем примере STR), в которую нужно записать ссылку на первое звено цепочки. Следовательно, эта переменная также должна иметь тип SVYAZ.

Итак, VAR STR: SVYAZ.

С точки зрения техники программирования выход на цепочку осуществляется через его заглавное (нулевое) звено. Отсюда имеем:

STR - ссылочная переменная, указывающая на первое звено;

STR^- сама динамическая переменная;

STR^.elem - поле символьного значения (информационное поле);

STR^.sled - поле ссылки.

ПРИМЕР 7. Схема образования цепочки динамических данных

1. Зарезервировать место в памяти для указателей

2. Зарезервировать место в памяти для значений динамических переменных и поместить их адреса в указатели UKZV и UKSTR:

NEW(UKZV); NEW(UKSTR);


UKSTR	*	UKZV	*

3. Заполнить поля ELEM значениями UKSTR^.ELEM:='P';

UKZV^.ELEM:='A':


UKSTR	*	P	UKZV	*	A

4. Заполнить поля SLED значениями UKSTR^.SLED:=UKZV;

UKZV^.SLED:=NIL:


UKSTR	*	P	*	A	Nil

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

Несколько предварительных соображений по данному примеру:

1) для ссылки на цепочку как единое целое введен указатель UKSTR;

2) для ссылки на очередное звено в цепочке введен указатель UKZV;

3) для продвижения по цепочке от одного звена к другому нужно текущему указателю UKZV присваивать в качестве значения ссылку на это следующее звено: UKZV:= UKZV^.SLED;

4) т.к. поле SLED имеет тип SVYAZ, т.е. ссылку на запись, то можно записать UKZV^.SLED^.SLED, что означает переход на звено, находящееся через звено от исходного;

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

ПРИМЕР 8. Формирование и распечатка цепочки символов

program SOZDANIE_ZEPOCHKI;

type SVYAZ = ^ZVSTR;

ZVSTR = record

elem: char; sled: SVYAZ;

end;

var UKSTR, UKZV: SVYAZ; SYM: char;

begin { Создание головного (нулевого) звена }

¦ new(UKSTR); UKZV:= UKSTR; UKZV^.sled:= nil;

¦ read(SYM);

¦ { Создание всей цепочки}

¦ while SYM <> '.' do

¦ begin

¦ ¦ new(UKZV^.sled); UKZV:= UKZV^.sled;

¦ ¦ UKZV^.elem:= SYM; UKZV^.sled:= nil;

¦ ¦ read(SYM);

¦ end;

¦ UKZV:= UKSTR^.sled; writeln; {Печать цепочки}

¦ while UKZV <> nil do

¦ begin

¦ ¦ write(UKZV^.elem,' ');

¦ ¦ UKZV:= UKZV^.sled;

¦ end;

end.

ПРИМЕР 9. Процедура удаления из списка SP элемента, содержащего в качестве данных некоторую букву

procedure UDALENIE_VNUTRI(var SP: SVYAZ; BUKVA: char);

var ZV: SVYAZ;

begin

¦ if SP = nil then writeln('Нет такого элемента!') else

¦ if SP^.elem <> BUKVA then UDALENIE(SP^.sled, BUKVA)

¦ else begin ZV:=SP; SP:=SP^.sled;

¦ dispose(ZV); end;

end.

ПОЯСНЕНИЕ. Данная процедура является рекурсивной. Выход из рекурсии осуществляется либо по нахождению и удалению соответствующей буквы, либо по достижению конца цепочки (обнаружение ссылки NIL). При удалении звена освобождается место в памяти с помощью DISPOSE.

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

SP:= SP^.SLED.

И это действительно так, ибо устранение звена не есть его "физическое" уничтожение, а переброска ссылки на следующее звено, как это показано на схеме

elem1

elem2

…

elemN

Nil

ПРИМЕР 10. Процедура удаления первого элемента цепочки

procedure UDALENIE_NACHALO(var SP: SVYAZ);

var Q: SVYAZ;

begin

¦ if SP^.sled <> nil then

¦ begin

¦ ¦ Q:= SP;

¦ ¦ SP:= SP^.sled;

¦ ¦ dispose(Q);

¦ end

¦ else writeln('Список пуст!');

end.

ПОЯСНЕНИЕ. Здесь введена вспомогательная переменная Q для временного хранения ссылки на удаляемое звено, прежде чем уничтожить его с помощью DISPOSE.

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

ПРИМЕР 11. Процедура вставки в список элемента, содержащего в качестве данных D, после элемента, содержащего X

procedure VSTAVKA_VNUTRI(var SP: SVYAZ; X, D: char);

var Q: SVYAZ;

begin

¦ if SP = nil then writeln('Нет такого элемента!')

¦ else if SP^.elem <> X then VSTAVKA(SP^.sled,X,D)

¦ else begin

¦ ¦ new(Q); Q^.elem:= D;

¦ ¦ Q^.sled:= SP^.sled; SP^.sled:= Q

end. end;

ПОЯСНЕНИЕ. Как и в примере 9, данная процедура является рекурсивной и по ней производится сначала поиск по цепочке звена, содержащего элемент Х, а затем сама вставка (если такое звено найдено).

ПРИМЕР 12. Процедура вставки звена в начало цепочки

procedure VSTAVKA_NACHALO(var SP: SVYAZ; D: char);

var Q: SVYAZ;

begin

new(Q); Q^.elem:= D;

Q^.sled:= SP^.sled;

SP^.sled:= Q

12. ПОНЯТИЕ ОБ ИНФОРМАЦИИ. ДАННЫЕ. СТРУКТУРЫ ДАННЫХ

12.1 Информация

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

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

В 40-х гг. XX в. ученый К.Шеннон попытался количественно описать информацию. Он ввел определение количества информации как меры определенности и упорядоченности. Шеннон считал, что с каждой порцией информации, полученной тем или иным объектом (системой), у объекта уменьшается неопределенность по какому-либо вопросу.

12.2 Данные

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

Данные программиста - он их определяет и ими манипулирует - простые данные, массивы, файлы и пр.

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

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

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

Структуры	Языки программирования
данных	РАЯ	BASIC	PASCAL
массивы	+	+	+
литеры	+	+	+
множества	-	-	+
файлы	-	+	+
списки	-	-	+

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

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

Различие между простыми и структурированными элементами данных зависит от языка и типа разрешенных операций доступа. Например, цепочка литер в некоторых языках является простым элементом данных и доступна только целиком в операциях ввода - вывода и при передаче в подпрограммы (данные типа STRING в Паскале). В других же языках индивидуально доступна каждая подцепочка внутри цепочки литер, причем последняя является структурированным элементом данных (литерный массив).

По способу доступа принято выделять структурированные элементы данных трех типов:

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

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

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

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

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

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

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

К простым типам данных относятся: числа (INTEGER, REAL), логические величины (BOOLEAN), символы (CHAR), цепочки литер (STRING), цепочки битов (BIT), указатели (POINTER). Последние два типа относятся к типам данных, образуемых самой системой, а не программистом.

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

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

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

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

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

Память	101	102	103	104	105	106	107
(ячейки)

Вектор Х	X[1]	X[2]	X[3]	X[4]	X[5]	X[6]	X[7]

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

[1,1]

[1,2]

[1,3]

[1,4]

Двумерный массив

[2,1]

[2,2]

[2,3]

[2,4]

(матрица)

[3,1]

[3,2]

[3,3]

[3,4]

[4,1]

[4,2]

[4,3]

[4,4]

Память

[1,1]

[1,2]

[1,3]

[1,4]

[2,1]

[2,2]

[2,3]

[2,4]

[3,1]

[3,2]

…

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

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

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

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

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

Элементы, находящиеся в середине очереди, недоступны для обработки. Следовательно, доступными являются только два элемента:

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11