50276 (588702), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

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.

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

ПРИМЕР 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 Данные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

Список файлов ВКР