Алгоритмический язык Паскаль

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 26.01.2011
Размер файла 276,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

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

*

*

*

*

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

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

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

*

*

*

*

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

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

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

STR

*

P

*

A

*

S

*

C

*

A

*

L

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.

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

SP

*

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],..., А[N], причем длина N этого массива выбирается с таким запасом, чтобы длина очереди не превышала N.

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

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

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

X:=А[I]; I:=I+1.

После этого индекс I указывает на следующий элемент очереди, т.е. "головой" ее становится следующий по порядку элемент. Запись нового элемента Y в очередь сводится к выполнению операций:

А[J]:=Y; J:=J+1.

Теперь индекс J снова указывает на первый свободный элемент массива.

Элементы очереди могут поступать и обрабатываться неравномерно, поэтому длина ее будет изменяться. В частности, возможен случай, когда очередь окажется пустой. Признаком этого может служить равенство I = J после чтения головного элемента очереди.

В процессе обработки очереди ее элементы будут смещаться к концу массива, т.к. J увеличивается после каждой записи в очередь. Поэтому возможен случай J > N после записи в очередь очередного элемента. При этом надо сместить очередь в начало массива, т.е. положить I = 1 и последовательно переписать все элементы очереди в элементы массива, начиная с А[1].

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

I голова

.

.

.

хвост

J

.

.

.

A[1]

A[2]

A[3]

A[N-2]

A[N-1]

A[N]

При такой закольцовке просто определить переполнение очереди. Признаком этого факта является условие J = I, т.е. признак того, что "хвост" совпал с "головою" очереди.

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

Очередь

Указатель начала

Указатель конца

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

Для стеков используют два представления - ПОСЛЕДОВАТЕЛЬНОЕ и СВЯЗАННОЕ.

ПОСЛЕДОВАТЕЛЬНОЕ представление требует резервирования блока памяти - одномерного массива А[1], А[2],..., А[N] - по тому же принципу, что и очередь. Величина N должна быть такой, чтобы стек мог расти до своего максимального размера без переполнения блока. Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение I = 0 перед чтением из стека служит признаком его пустоты, а значение I = N перед записью в стек - признаком переполненности стека.

Представление стека в памяти:

I - вершина

.

.

.

D[K]

D[K-1]

D[3]

D[2]

D[1]

указатель

вершины стека

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

СТЕК

D0

СТЕК

D1

D0

новый элемент

D2

D1

D2

СТЕК

СТЕК

Свободное

пространство

D1

D1

D2

D2

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

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

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

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

Список

С1

С2

Сn

Nil

0-звено

1-звено

2-звено

n-звено

(голова)

2. Представление с двумя связями: каждый элемент списка соединен с последующим и предыдущим; в голове списка имеются указатели и на первый, и на последний элементы. Такие двусвязные списки принято называть деками.

СХЕМА ПРЕДСТАВЛЕНИЯ ДВУХСВЯЗНОГО СПИСКА

Список

С1

Ук. 1-го эл-та

Ук. 2-го эл-та

С2

Сn-1

Cn

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

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

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

Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.

13. СТРУКТУРЫ ПРЯМОГО ДОСТУПА. СПОСОБЫ СОРТИРОВКИ МАССИВА

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

При решении ее возможны два подхода: использование промежуточного (вспомогательного) массива и сортировка внутри самого массива.

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

Выделяют 3 основных способа сортировки:

1. Прямое включение.

2. Прямой выбор.

3. Прямой обмен.

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

13.1 Прямое включение

Суть этого способа такова: в массиве берется i-й элемент и включается (вставляется) на свое место между 1-м и i-м элементами. Эта идея может быть выражена в виде следующего цикла:

FOR I:=2 TO N DO

BEGIN X:=A[I];

<включить X на свое место между A[1] и A[I]> END.

Из указанного видно, что на каждом шаге i все элементы с 1-го до (I-1)-го уже упорядочены, следовательно, при I = N произойдет последняя сортировка и N-й элемент встанет на свое место. Алгоритм должен быть таким, что если I-й элемент стоит в ряду, т.е. не нарушает порядка, то никаких действий совершать не надо, а следует перейти к I+1-му элементу.

Например, рассмотрим сортировку следующего массива:

-3

2

4

1

6

3

1

2

3

4

5

6

Здесь все элементы до четвертого уже упорядочены и сортировка должна произойти при I = 4. Суть метода состоит в том, что среди элементов с 1-го по 4-й ищется такой, который меньше четвертого, равного 1. В нашем случае этим элементом является первый, равный -3. В ходе поиска четвертый элемент 1 запоминается в специальной переменной X, а все элементы циклически сдвигаются на одну позицию вправо:

1-й шаг: 1<4? - да => сдвиг

-3

2

4

4

6

3

2-й шаг: 1<2? - да => сдвиг

-3

2

2

4

6

3

3-й шаг: 1<-3? - нет

-3

1

2

4

6

3

На третьем шаге сдвига не происходит и после него запомненный элемент ставится на свое место, т.е. на место второго элемента ставится четвертый из исходного массива. Поиск и сдвиг идут по циклу WHILE, в котором в качестве условия берется сравнение X < А[I-1].

Продолжая наш пример, заметим, что на пятом шаге никаких действий происходить не будет, а на шестом элемент А[6]=3 должен пойти на четвертое место, сдвигая пятый элемент на шестое место, а четвертый элемент - на пятое место:

3<6? - да => сдвиг

-3

1

2

4

6

6

3<4? - да => сдвиг

-3

1

2

4

4

6

3<2? - нет=>

-3

1

2

3

4

6

Прежде чем переходить к самой программе, заметим, что если I-й элемент должен передвинуться на 1-е место, то в нашем алгоритме для окончания процесса сдвига нужно иметь элемент слева от А[1] для сравнения (барьер). Таким элементом является А[0]. Отсюда заключаем, что в цикле FOR от 2 до N нужно для каждого шага I предусмотреть засылку в А[0] сортируемого элемента.

procedure PRVKLUCH (var MM:MAS);

var I,J,X: integer;

begin

¦ for I:= 2 to N do

¦ begin

¦ ¦ X:=MM[I]; MM[0]:=X; J:=I;

¦ ¦ while X < MM[J-1] do

¦ ¦ begin

¦ ¦ ¦ MM[J]:=MM[J-1]; J:=J-1;

¦ ¦ end;

¦ ¦ MM[J]:=X;

¦ end;

end.

Из этой процедуры видно, что выход из нее происходит тогда, когда (J-1)-й элемент становится меньше I-го элемента. Слева от I-го уже не может быть меньшего элемента, т.к. на каждом шаге все элементы до него уже отсортированы ранее в цикле FOR.

13.2 Прямой выбор

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

Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.

ОБЩАЯ СХЕМА ПРОГРАММЫ:

for I:=1 to N-1 do

begin

¦ {Запоминание индекса и самого I-го элемента}

¦ for J:=I+1 to N do

¦ begin

¦ {Поиск минимального элемента от I+1 до N}

¦ end;

¦ {Перестановка I-го и минимального элементов}

end.

ОБЩИЙ ВИД ПРОГРАММЫ:

procedure SELECTION (var MM:MAS);

var I,J,K,X: integer;

begin

¦ for I:= 1 to N-1 do

¦ begin

¦ ¦ { Это тело внешнего цикла }

¦ ¦ K:= I; X:= MM[I];

¦ ¦ { Внутренний цикл - поиск MIN элемента }

¦ ¦ for J:= I+1 to N do

¦ ¦ if X > MM[J] then

¦ ¦ begin

¦ ¦ ¦ { Запоминание номера и значения

¦ ¦ ¦ минимального элемента }

¦ ¦ ¦ X:= MM[J];

¦ ¦ ¦ K:= J;

¦ ¦ end;

¦ ¦ { Минимальный и I-й элементы меняются местами}

¦ ¦ MM[K]:= MM[I]; MM[I]:= X;

¦ end;

end.

Проследим работу этой программы на следующем примере:

I=0

-3

2

4

1

6

3

исходный массив

I=1

-3

2

4

1

6

3

1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте

I=2

-3

1

4

2

6

3

2-й шаг: 2-й и 4-й поменялись местами

I=3

-3

1

2

4

6

3

3-й шаг: 3-й и 4-й поменялись местами

I=4

-3

1

2

3

6

4

4-й шаг: 4-й и 6-й поменялись местами

I=5

-3

1

2

3

4

6

5-й шаг: 5-й и 6-й поменялись местами

Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.

13.3 Прямой обмен (метод пузырька, всплытие)

Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.

В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:

for I:= 2 to N do

for J:= N downto I do

{ Обмен местами (всплытие) более легкого элемента }

end;

end.

ОБЩИЙ ВИД ПРОГРАММЫ:

procedure BUBLESORT (var MM: MAS);

var I,J,X: integer;

begin

¦ for I:=2 to N do

¦ for J:= N downto I do

¦ if MM[J-1] > MM[J] then

¦ begin

¦ ¦ X:= MM[J-1];

¦ ¦ MM[J-1]:= MM[J];

¦ ¦ MM[J]:= X

end;

end.

Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:

I=2

I=3

J=6

-3

2

4

1

3

6

J=6

-3

1

2

4

3

6

J=5

-3

2

4

1

3

6

J=5

-3

1

2

3

4

6

J=4

-3

2

1

4

3

6

J=4

-3

1

2

3

4

6

J=3

-3

1

2

4

3

6

J=3

-3

1

2

3

4

6

J=2

-3

1

2

4

3

6

Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.

13.4 Сравнительная характеристика методов

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

1. Массив уже отсортирован (но мы не знаем об этом).

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

2. Исходный массив упорядочен по убыванию.

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

ПРИМЕР:

1 шаг:

8

6

4

2

0

2 шаг:

0

6

4

2

8

Результат:

0

2

4

6

8

3. Массив дан случайным образом.

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

13.5 Улучшенный метод сортировки. QUICK - сортировка

Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.

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

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

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

¦ {Установка границ, от которых идет движение к середине}

¦ I:= L; J:= R;

¦ {Выбор граничного элемента}

X:= M[(L+R) div 2];

¦ repeat

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

¦ ¦ while X > M[I] do I:= I+1;

¦ ¦ { Поиск справа элемента, меньшего X }

¦ ¦ while X < M[J] do J:= J-1;

¦ ¦ if I <= J then

¦ ¦ begin

¦ ¦ ¦ W:= M[I]; {Обмен местами

¦ ¦ ¦ M[I]:= M[J]; I-го и J-го

¦ ¦ ¦ M[J]:= W; элементов,

¦ ¦ ¦ I:=I+1; дальнейшее продвижение

¦ ¦ ¦ J:=J-1; вперед (назад)}

¦ ¦ end;

¦ ¦ {Выход из цикла, если левый край перевалил за правый}

¦ until I > J;

¦ { Повтор обмена для левой части }

¦ if L < J then QUICKSORT (L,J,M);

¦ { Повтор обмена для правой части }

¦ if R > i then QUICKSORT (I,R,M);

¦

end;

ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:

6

4

3

2

7

1

5

1

2

3

4

5

6

7

Здесь имеем значения L=1; I=1; J=7; R=7. Цикл WHILE X > M[I] при Х = 2 дает сразу же отказ и значение I остается старым, т.е. I = 1. Цикл WHILE X < M[J] при Х = 2 дает J = 6. Сравнение IF I <= J дает 1 <= 6, т.е. истина, отсюда идет обмен между I-м и J-м элементами - первый элемент 6 меняется местом с шестым элементом 1:

1

2

3

4

7

6

5

1

2

3

4

5

6

7

и индекс I (J) увеличивается (уменьшается):

I:=I+1, т.е. I = 2;

J:=J-1, т.е. J = 5.

Сравнение I > J, т.е. 2 > 5, является ложным, поэтому идет возврат наверх. Циклы WHILE доводят значения переменной I до 2, а значение J становится равным 4. Так как I=2 <= J=4, то идет обмен между 2-м и 4-м элементами:

1

2

3

4

5

6

7

1

2

3

4

5

6

7

и индексы получают значения: I = 3, J = 3.

При таких значениях индексов имеем M[I]=M[J]=3, что в результате работы циклов WHILE дает I=3 и J=2. Сравнение I<=J будет ложным, поэтому обмена элементов нет, кроме того, становится истинным условие проверки окончания работы цикла REPEATE (I>J) и происходит переход на рекурсивное обращение к самой процедуре.

Из двух условий истинным является первое (сравнение L < J дает 1< 2), поэтому идет обращение к процедуре при параметрах L=1 и R=2. Однако для этих праметров упорядочивание уже произошло. Затем формируется отрезок [3,7], где происходит обмен между 5-м и 7-м элементами:

1

2

3

4

5

6

7

1

2

3

4

5

6

7

В результате этой работы массив уже упорядочен, однако затем формируются отрезки [3,6] и [5,6], при которых никаких обменов не происходит, но параметры I, J получают значения: I=6, J=4. Ни одно из сравнений L<J (5<4) и R>I (6>6) не является истинным, поэтому рекурсия завершается и процедура заканчивает свою работу.

ЗАМЕЧАНИЕ. Данная процедура очень медленно обрабатывает уже упорядоченный массив.

14. СТРУКТУРЫ ПОСЛЕДОВАТЕЛЬНОГО ДОСТУПА. ЛИНЕЙНЫЕ СПИСКИ

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

Итак, рассмотрим теперь более подробно эти виды динамических структур.

14.1 Очередь

Очередь - это линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) - на другом. Очередь иногда называют циклической памятью или списком типа FIFO (от первых букв английской фразы "First Input First Output"): первым включается - первым исключается.

При работе с очередью мы говорим о ее начале и конце - объекты вставляются в конце очереди и удаляются в начале:

ИСКЛЮЧИТЬ

ВКЛЮЧИТЬ

*

*

*

*

НАЧАЛО

ВТОРОЙ

ТРЕТИЙ

КОНЕЦ

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

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

type SS = ^ZVENO;

ZVENO = record

elem: integer;

next: SS;

end.

Рассмотрим сначала алгоритм формирования очереди. Для этого введем три указателя - на начало очереди, на ее конец и текущий указатель:

VAR L: SS; {начало очереди}

R: SS; {конец очереди}

K: SS; {рабочий указатель}

el1,el2: integer;{рабочие элементы}

Алгоритм формирования очереди представлен на следующей схеме:

ОПЕРАТОРЫ

ПОЯСНЕНИЕ

new(K);

el:=random(10);

K

*

el

nil

K^.next:=nil;

K^.elem:=el;

L:=K;

L

*

K

*

el

nil

R:=K;

R

*

el:=random(10);

while el<>0

do begin

K

*

el

nil

new(K);

K^.elem:=el;

K^.next:=nil;

L

*

el

*

R^.next:=K;

R

*

K

el

nil

R:=K;

L

*

el

*

R

*

el

nil

el:=random(10); end;

K

Запишем теперь полностью процедуру формирования очереди:

procedure FORMIR_OTCHERED_1 (var L, R: SS);

var K: SS; EL: integer;

begin

¦ { Формирование первого звена очереди }

¦ randomize; EL:= random(10);

¦ new(K); L:= K; R:= K;

¦ K^.elem:= EL; K^.next:= nil;

¦ EL:= random(10);

¦ { Помещение очередного элемента в очередь }

¦ while EL <> 0 do

¦ begin

¦ ¦ new(K);

¦ ¦ K^.elem:= EL; K^.next:= nil;

¦ ¦ R^.next:= K; R:= K;

¦ ¦ EL:= random(10);

¦ end;

end.

ЗАМЕЧАНИЕ. Из программы видно, что L всегда хранит начало очереди, а R - ее конец. Процедура имеет два возвращаемых параметра, которые идентифицируют получаемую с ее помощью очередь. Первый параметр L позволяет начать просмотр очереди или удалить из нее элемент, а второй R - добавить новый элемент (согласно правилу работы с очередями).

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

L,R

*

0

nil

Если пустой очередью считать очередь без единого звена, то процедура принимает вид:

procedure FORMIR_OTCHERED_2 (var L, R: SS);

var K: SS;

EL1, EL2: integer;

begin

¦ {Формирование первого звена очереди }

¦ randomize; EL1:= random(10);

¦ if EL1= 0 then begin L:= nil; R:= L end

¦ else begin new(K);

¦ L:= K; R:= K; K^.next:= nil;

¦ K^.elem:= EL1;

¦ { Помещение очередного элемента в очередь }

¦ EL2:=random(10);

¦ while EL2<>0 do

¦ begin

¦ new(K);

¦ K^.elem:= EL2; K^.next:= nil;

¦ R^.next:= K; R:= K; EL2:= random(10);

¦ end; end;

end.

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

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

procedure VIVOD_OTCHERED (var L, R: SS);

var K: SS;

begin

¦ if (L^.elem= 0) or (L= nil) then

¦ writeln('Очеpедь пуста ! ')

¦ else begin

¦ ¦ K:= L;

¦ ¦ write('Элементы очереди: ');

¦ ¦ while K <> R^.next do

¦ ¦ begin

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

¦ ¦ ¦ K:= K^.next;

¦ ¦ end;

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре знание ссылки R на конец очереди совсем не обязательно. Здесь можно обойтись только ссылкой на начало, а в цикле WHILE в качестве условия взять сравнение значения переменной K с NIL: WHILE K <> NIL.

Добавление нового звена EL к очереди происходит справа (используется указатель R). Рассмотрим сначала алгоритм:

ОПЕРАТОРЫ

ПОЯСНЕНИЕ

read(el); new(K);

K^.next:=nil;

K

*

el

nil

K^.elem:=el;

L

*

el1

*

R^.next:=K;

R

*

elN

*

el

nil

K

L

X

el1

*

R:=K;

elN

*

R

X

el

nil

K

Запишем теперь процедуру добавления звена к очереди:

procedure DOBAV_OTCHERED (EL:integer; var L, R: SS);

var K: SS;

begin

¦ if L^.elem = 0 then R^.elem:= EL

¦ else if L = nil then

¦ begin

¦ ¦ new(K);L:= K;

¦ ¦ R:= K;

¦ ¦ K^.next:= nil;

¦ ¦ K^.elem:= EL

¦ end

¦ else begin

¦ ¦ new(K);

¦ ¦ K^.elem:=el;

¦ ¦ K^.next:=nil;

¦ ¦ R^.next:=K;

¦ ¦ R:=K

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре сначала проверяется, является ли очередь пустой. Если пустая очередь имеет нулевое звено,то оно заполняется элементом EL. Если же она не содержит звеньев, то создается одно звено по тем же правилам, как при формировании очереди. В общем случае к последнему звену очереди добавляется новое звено.

Исключение звена из очереди происходит слева - используется указатель L - и осуществляется одним оператором: L:=L^.next. При такой операции, однако, память не освобождается. Для ее освобождения необходимо дополнительно использовать процедуру DISPOSE.

L

*

el1

*

el2

*

R

*

elN

nil

procedure UDALENIE_OTCHERED (var l, r:ss);

begin

¦ if l=nil then writeln('Очеpедь пуста !')

¦ else l:=l^.next

end.

ОБЩЕЕ ЗАМЕЧАНИЕ. В рассмотренных процедурах признаком конца очереди являлось число 0. Если очередь заполняется символами, то для этого нужно выбрать свой признак конца, например, ".". Для ввода символов, как и для ввода чисел, также можно использовать датчик случайных чисел. Но в этом случае он должен генерировать коды ASCII, которые затем с помощью функции преобразования типов CHR трансформировать в сами символы.

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

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

14.2 Стек

Стек - это структура данных, которая обеспечивает доступ к списку по принципу LIFO (от первых букв английской фразы "Last Input First Output"): последним вошел, первым вышел. Компонента извлекается из стека таким образом, что первой выбирается та, которая была помещена последней.

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

Значением указателя, представляющего стек как единый объект, является ссылка на ВЕРШИНУ стека. Последнее звено цепочки - стека содержит в поле ссылок значение NIL.

STACK

*

elN

*

el2

*

el2

nil

Если стек пуст, то значением указателя является ссылка NIL.

Перед началом заполнения стека его необходимо сделать пустым, т.е. выполнить "обнуление" указателя стека: STACK:= NIL.

Над стеком, как и над очередью, допустимы следующие операции:

1) формирование;

2) занесение нового элемента;

3) удаление элемента;

4) доступ (только для просмотра) к N-му звену стека.

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

ОПЕРАТОРЫ

ПОЯСНЕНИЕ

Var ST:SS;

EL:integer;

K:SS;

ST

*

nil

Begin

New(ST);

ST:=nil;

New(K);

K

*

Randomize;

EL:=random(10);

K^.elem:=el;

K

*

el1

nil

K^.next:=ST;

K

*

el1

nil

ST:=K;

ST

*

New(K);

K

*

EL:=random(10);

K

*

el2

*

K^.elem:=EL;

ST

*

el1

nil

K^.next:=ST;

ST:=K;

K

*

el2

*

ST

*

el1

nil

Запишем теперь саму процедуру формирования стека:
procedure SOZDAN_STACK (var ST: SS);
var K: SS;
EL: integer;
begin
randomize;
EL:= random(10);
new(ST); ST:= nil;
while EL <> 0 do
begin
¦ new(K); K^.elem:= EL;
¦ k^.next:= ST; ST:= K;
¦ EL:= random(10);
end;
end.
ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.
Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:

ST

*

Eln

*

EL1

nil

Eln+1

*

Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:
PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);
var K: SS;
begin
new(K); K^.elem:= EL;
K^.next:= ST; ST:= K
end.
Схематически процесс удаления можно изобразить так:

ST

*

Eln

*

Eln-1

*

EL1

nil

По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:
procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);
begin
¦ SKLAD:= ST^.elem;
¦ ST:= ST^.next
end.
Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.
Данная процедура имеет недостатки:
1) предполагается, что стек заведомо не пуст, иначе программа зависнет;
2) исключаемое звено не уничтожается, т.к. меняется только ссылка в переменной ST. Если таких удалений несколько, то память будет забита "мусором". Поэтому следует исключить элементы не только из списка, но и из памяти. Для этого можно использовать процедуру DISPOSE.
Указанные недостатки учтены в следующей процедуре:
procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);
var K: SS;
begin
¦ if ST = nil then writeln('стек пустой')
¦ else begin
¦ ¦ SKLAD:= ST^.elem; K:=ST;
¦ ¦ ST:= ST^.next; dispose(K);
end;
end.
Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.
Для извлечения из стека N-го элемента необходимо поступить так же, как при выборке элемента из файла, - "прокрутить" стек на N-1 позиций и затем извлечь N-й элемент. Для "прокрутки" стека можно воспользоваться процедурой UDALENIE, т.к. удаление в динамических структурах означает не уничтожение звеньев списка, а только передвижение указателя на следующий элемент.
Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:
procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;
N: integer);
var K: SS; i: integer;
begin
¦ K:= ST;
¦ for i:= 1 to N-1 do
¦ UDALENIE_IZ_STACK(K, SKLAD);
¦ SKLAD:= K^.elem;
end.
Для вывода на печать элементов стека можно воспользоваться процедурой печати для цепочки, т.к. в этом смысле цепочка ничем не отличается от стека. Отметим только, что элементы стека будут выведены в порядке, обратном его заполнению.

14.3 Дек

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

левый

второй

второй

правый

конец

слева

справа

конец

EL1

EL2

..

..

Eln-1

Eln

включить

включить

или

или

исключить

исключить

Более точно следует представить так:

EL1

EL2

EL3

Eln

*

*

*

*

nil

nil

*

*

*

*

Формирование дека

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

type SS = ^ZVENO;

ZVENO = record

ELEM: integer;

next: SS;

pred: SS;

end.

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

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

procedure FORMIR_DEK_1(var L, R: SS);

var Z: SS; EL: integer;

begin

¦ new(L); read(L^.elem);

¦ L^.pred:= nil; R:= L; Z:= L;

¦ WHILE R^.elem <> 0 do

¦ begin

¦ ¦ new(R^.next); R:=R^.next;

¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;

¦ end;

¦ R^.next:= nil; readln;

end.

ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R - конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.

Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:

Звено 1

Звено 2

X

*

next

next

pred

pred

ELi

ELi+1

При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:

procedure FORMIR_DEK_2(var L, R: SS);

begin

¦ randomize; new(L);

¦ L^.elem:= random (10);

¦ L^.pred:= nil; R:= L;

¦ while R^.elem <> 0 do

¦ begin new(R^.next);

¦ ¦ R^.next^.elem:= random(10);

¦ ¦ R^.next^.pred:= R; R:=R^.next

¦ end;

R^.next:= nil

end.

Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.

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

ELi

Z

*

ELi+1

X

*

*

*

*

Y

*

*

EL

*

*

Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:

ОПЕРАТОРЫ

ПОЯСНЕНИЕ

Z

X

Elx

Elz

*

*

Y^.next:=X^.next;

*

Y

Ely

*

*

*

Z

X

Elx

Elz

*

*

Y^.pred:=X;

*

Y

Ely

*

*

*

Z

X

Elx

Elz

X^.next:=Y;

*

*

*

Y

Ely

*

*

*

Z

X

Elx

Elz

*

*

*

Y

Ely

*

Y^.next^.pred:=Y;

*

*

Процедура вставки нового звена Y в дек после звена X принимает вид:

procedure VSTAVKA_V_DEK_POSLE(X, Y: SS);

begin

¦ Y^.next:= X^.next;

¦ Y^.pred:= X;

¦ X^.next:= Y;

¦ Y^.next^.pred:= Y;

end.

ЗАМЕЧАНИЕ 1. Мы рассмотрели теперь процедуры вставки нового звена во все виды линейных списков с односторонней связью (цепочки, очереди, стеки) и в дек. Однако во всех этих процедурах новое звено вставлялось ПОСЛЕ указанного звена (в стеке - в вершину, в очереди - в хвост). Конечно, можно в односвязном линейном списке поставить новый элемент и ПЕРЕД указанным, но это требует некоторых дополнительных операций. Например, можно новый элемент поместить в следующее звено, а затем произвести обмен информационными полями. В деке же возможна прямая вставка звена ПЕРЕД указанным с использованием ссылки PRED. В результате получаем:


Подобные документы

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

    лекция [55,7 K], добавлен 21.05.2009

  • Логические конструкции в системе программирования Паскаль. Команды языка программирования, использование функций, процедур. Постановка и решение задач механики в среде системы Паскаль. Задачи статики, кинематики, динамики решаемые с помощью языка Паскаль.

    курсовая работа [290,9 K], добавлен 05.12.2008

  • Алгоритмы и алфавит языка Турбо Паскаль. Основные типы данных. Операторы присваивания, перехода и выбора. Понятие массива в Паскале. Особенности работы со строками в программе. Использование линейного поиска и поиска с барьером. Основные виды сортировок.

    учебное пособие [53,2 K], добавлен 09.11.2009

  • Общая характеристика языка программирования Турбо Паскаль: операторы, циклы, файлы. Процедуры и функции модуля Crt. Структурная и функциональная схема программы учета учащихся, таблица идентификаторов. Список и описание использованных подпрограмм.

    курсовая работа [702,9 K], добавлен 29.01.2011

  • История и основы структурного программирования в среде Turbo Pascal. Работа с различными типами данных. Операторы языка. Работа с символьными и строковыми переменами, одномерным, двумерным массивами. Классификация компьютерных игр. Игры на языке Паскаль.

    курсовая работа [28,8 K], добавлен 06.05.2014

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

    курсовая работа [78,9 K], добавлен 28.12.2012

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

    лабораторная работа [189,8 K], добавлен 17.04.2012

  • Разработка консольного приложения, которое обрабатывает входной файл с расширением .pas и транслирует в выходной файл с расширением .cpp или .txt (по выбору пользователя). Синонимичные операторы языков Паскаль и С. Разработка алгоритма решения задачи.

    курсовая работа [329,6 K], добавлен 04.06.2013

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

    курсовая работа [305,9 K], добавлен 03.07.2011

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

    лабораторная работа [15,7 K], добавлен 12.06.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.