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

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

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

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

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

procedure VSTAVKA_V_DEK_PERED(X, Y: SS);

begin

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

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

end.

ЗАМЕЧАНИЕ 2. При вставке нового звена Y в дек относительно X следует учитывать, что на момент применения рассмотренных процедур звенья X и Y уже сформированы и значения этих ссылочных переменных определены. Так, например, звено Y можно сформировать следующим образом:

NEW(Y); Y^.NEXT:= NIL; Y^.PRED:= NIL; READ(Y^.ELEM).

Что касается звена X, то здесь возможны два случая:

1) известен адрес (ссылка) на элемент X; тогда при обращении к процедуре уже задано значение фактического параметра;

2) известен только сам элемент (информационное поле звена X);

для определения ссылки на звено X в указанном деке следует "прокрутить" дек до этого звена (подобно поиску N-го звена в стеке).

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

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

ЗАМЕЧАНИЕ. Данная процедура применима только для звена X, находящегося внутри дека. Для пограничных случаев, когда звено X является первым или единственным, необходимо использовать более сложную процедуру:

procedure UDAL_DEK_1(X: SS; VAR Y, Z: SS);

begin

¦ if Y^.next = nil then writeln('Дек пуст !') else

¦ if X = Y then Y:= Y^.next else

¦ begin x^.pred^.next:=x^.next;

¦ ¦ {Переброска ссылки next вверху}

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

¦ ¦ {Переброска ссылки pred внизу}

¦ end;

end.

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

Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.

14.4 Общие приемы работы с линейными списками

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

Процедура печати списка имеет вид:

procedure VIVOD_SPISOK(var Y: SS);

var X: SS;

begin X:= Y;

¦ while X^.next <> nil do

¦ begin

¦ ¦ write(X^.elem,' '); X:=X^.next;

¦ end;

end.

ПОЯСНЕНИЕ. Здесь Y - начало списка, а переменная X введена, чтобы после печати списка значение переменной Y не изменилось (не потерялось начало списка).

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

procedure POISK_V_SPISKE(var Y,Z: SS; ZNACH: integer;

var N: integer);

var X: SS;

begin

¦ N:= 1; X:= Y;

¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do

¦ begin

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

¦ ¦ N:= N+1

¦ end;

¦ if X^.next = nil then

¦ begin N:= 0; Z:= nil; end;

end.

ПОЯСНЕНИЕ. С помощью данной процедуры в списке Y ищется звено с элементом ZNACH. Значение переменной N дает номер искомого звена, а переменная Z - ссылку на это звено. Если такого звена нет, то N = 0 и Z = NIL.

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

procedure SORTSPISOK (var X: SS);

{ X - Ссылка на начало списка }

var X1, Y1:SS; P: integer;

begin

¦ X1:= X; { Выбор элемента для сравнения }

¦ while X1^.next <> nil do { Проход по списку до

¦ предпоследнего элемента}

¦ begin

¦ ¦ Y1:=X1^.next;

¦ ¦ while Y1^.next <> nil do { Проход до последнего

¦ ¦ элемента }

¦ ¦ begin

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

¦ ¦ ¦ if Y1^.elem < X1^.elem then

¦ ¦ ¦ begin

¦ ¦ ¦ ¦ P:= X1^.elem; X1^.elem:= Y1^.elem;

¦ ¦ ¦ ¦ y1^.elem:= P;

¦ ¦ ¦ end;

¦ ¦ ¦ Y1:= Y1^.next; { Сдвиг по списку }

¦ ¦ end;

¦ ¦ X1:= X1^.next; { Сдвиг по списку }

¦ end;

end.

ПОЯСНЕНИЕ. В данной процедуре для сортировки использован метод прямого выбора, т.е. способ поиска минимального элемента и установка его в начало списка.

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

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

SPISOK

NEXT

PRED

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

*

*

*

*

*

*

*

*

*

el

el

el

*

*

*

el

el

el

*

*

*

Spi-1

SPi

Spi+1

Для реализации этой структуры необходимо задать два типа данных: SS - для обычных списков, SS1 - для дека суперсписка:

type SS = ^ZVENO;

ZVENO = record

el: integer;

next: SS;

end;

SS1 = ^ZVENO1;

ZVENO1 = record

pred1, next1: SS1;

SP: SS;

end.

ЗАМЕЧАНИЕ. В описании 3-го поля второго списка имеется тип SS из первого списка, что позволяет рассматривать каждое звено второго списка как начальное (очередное) звено первого. Для содержания всей этой структуры в рабочем состоянии достаточно хранить в памяти ссылку на один из указателей дека (начало или конец).

Заметим также, что в случае очереди целесообразно построение звена дека из 4-х полей: PRED1, NEXT1, SPL (начало очереди), SPR (конец очереди).

15. ДЕРЕВЬЯ

15.1 Характеристика древовидной структуры данных

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

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

При ВЛОЖЕНИИ МНОЖЕСТВ используются хорошо известные в математике диаграммы Венна. Способ изображения дерева в виде ВЛОЖЕНИЯ СКОБОК менее нагляден, например, A(В(D,E)), C(F,G,H)).

Рассмотрим терминологию, присущую представлению дерева в виде графа:

1) элемент дерева - ВЕРШИНА, из которого связи только выходят, называют КОРНЕМ дерева (в нашем случае А);

2) связи между элементами дерева называются РЕБРАМИ;

3) если вершина В находится на графе ниже А, то В называется ПОТОМКОМ, а А - ПРЕДКОМ В;

4) каждая вершина находится на своем УРОВНЕ, причем корню соответствует 0-й уровень;

5) число уровней (или максимальный уровень) называют ВЫСОТОЙ или ГЛУБИНОЙ дерева;

6) если вершина не имеет потомков, то она называется ЛИСТОМ (в нашем примере F,G,H,D,E - листы);

7) вершины, лежащие между корнем и листьями, называют ВНУТРЕННИМИ.

Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо признаку. Для деревьев, элементами (вершинами) которых являются целые числа, упорядоченность устанавливается по возрастанию (убыванию) элементов.

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

НАПРИМЕР:

5

/ \

3 10

/ \ / \

2 4 9 12

2 < 3 < 5 < 10 < 12; 2 < 3 < 4;

3 < 10;

2 < 4 < 9 < 12; 9 < 10 < 12.

Особый интерес представляют деревья, у которых из каждой вершины может исходить не более 2-х (т.е. ни одного, одно или два) ребер. Такие деревья называют ДВОИЧНЫМИ или БИНАРНЫМИ, либо деревьями 2-й степени.

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

R

/ \

O W

/ | \ \

E Q X H

Бинарное дерево принято также называть ГЕНЕАЛОГИЧЕСКИМ:

X -внук

/ \

сын - Y Z -дочь

/ \ / \

A B C D

мать отец мать отец

ОПРЕДЕЛЕНИЕ: дерево называется ПРЕДЕЛЬНО (ИДЕАЛЬНО) СБАЛАНСИРОВАННЫМ, если разница между числом вершин в его левых и правых поддеревьях (на всех уровнях) не более 1.

15.2 Построение идеально сбалансированного дерева

Для построения такого дерева используется рекурсивное правило:

Пусть требуется построить дерево из N элементов (вершин).

Выберем один из них в качестве корня.

2. Строим левое поддерево с количеством вершин NL = N div 2.

3. Так же строим правое поддерево с числом вершин NR = N-NL-1.

Например, при построении дерева из 5 элементов:

1) один элемент идет на корень;

2) оставшиеся 4 элемента разбиваются на два поддерева:

NL = 2 и NR = 2;

3) в каждом из поддеревьев один элемент идет на корень, а другой - на лист: NL1= 1, NR1= 0.

Очевидно, что для отображения структуры дерева в память ЭВМ требуется построение динамических объектов.

Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.

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

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

function FORMIRTREE (N: integer): SS;

var Z: SS; NL, NR: integer;

begin

¦ if N = 0 then Z:= nil {Пустое дерево}

¦ else

¦ begin

¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);

¦ ¦ write('Ввести вершину'); readln(Z^.k);

¦ ¦ Z^.right:= FORMIRTREE (NR);

¦ end;

¦ FORMIRTREE:= Z; {Запоминание ссылки на корень дерева}

end.

ПОЯСНЕНИЕ. Сначала все N-1 элементов разбиваем на две части - левую и правую. Затем каждую часть соответственно делим на две. Рекурсия прекращается, когда N становится равным нулю - деление закончено, последняя образованная ссылка указывает на корневой элемент:

1

left

right

2

4

left

left

3

right

5

right

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

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

procedure PRINTTREE (Z: ss; X: integer; var Y: integer);

var I: integer;

begin

¦ Y:= (X-5)/5 - 1;{ Подсчет числа уровней }

¦ if Z <> nil then

¦ begin

¦ ¦ PRINTTREE(Z^.right, X+5, Y);

¦ ¦ for I:=1 to X do write(' ');

¦ ¦ writeln(Z^.k);

¦ writeln;

¦ ¦ PRINTTREE(Z^.left, X+5, Y);

¦ end;

end.

ЗАМЕЧАНИЕ. Эта рекурсивная процедура выводит на экран элементы слева направо, причем крайним левым элементом оказывается корень дерева. Между соседними уровнями процедура печатает 5 пробелов, а между элементами одного уровня - одну строчку. В процедуре параметр Y, как выходной, служит для указания числа уровней построенного дерева. Формула (X-5)/5-1 дает число уровней, т.к. по построению между элементами соседних уровней находится 5 пробелов, а в завершение работы этой процедуры последним печатается самый левый (самый нижний и, значит, самый удаленный от левого края экрана) лист дерева:

Теперь, имея рекурсивную функцию FORMIRTREE формирования дерева и рекурсивную процедуру PRINTTREE печати его элементов, можно записать основную программу построения и печати дерева с указанным числом вершин.

program TREE;

type SS = ^ZVENO;

ZVENO = record

K: integer;

left, right: SS;

end;

var KOL: integer; Y: REAL; DER: SS;

{KOL - число элементов дерева; DER - ссылка на корень дерева}

< рекурсивная функция FORMIRTREE формирования дерева>;

< рекурсивная процедура PRINTTREE печати дерева>;

begin

¦ write('Введите число элементов дерева');

¦ y:= 0; {Число уровней дерева}

¦ readln (KOL); DER:= FORMIRTREE (KOL);

¦ writeln; writeln(' Д Е Р Е В О:');

¦ PRINTTREE (DER, 5, y); writeln;

¦ writeln(' Всего', y:3:0,' уровня(ей) дерева.');

end.

ПОЯСНЕНИЕ. Дерево, состоящее из пяти элементов (1,2,3,4,5), будет выведено на экран в виде следующего графа:

ДЕРЕВО

4 \

правое поддерево

/

5

1 \

2 \

3

левое поддерево

15.3 Основные операции над деревьями

Над деревьями, как и над другими связными списками, выполняются те же операции: поиск элемента, вставка элемента в дерево и удаление из него.

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

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

1) входные параметры (параметры-значения) - ссылка на дерево (т.е. на корень дерева, где ищется элемент) и значение элемента поиска;

2) выходной параметр (параметр-переменная) - ссылка на найденный элемент.

Таким образом, имеем следующую процедуру:

procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if S <> nil then

if S^.k = ZNACH then ELEM:= S

¦ else

begin

¦ ¦ POISK(S^.left, ZNACH, ELEM);

¦ ¦ POISK(S^.right, ZNACH, ELEM);

¦ end;

end.

ЗАМЕЧАНИЕ. Из самой процедуры видно, что рекурсия заканчивается по достижению последнего элемента дерева, поэтому переменная ELEM получит значение ссылки на последний элемент, равный ZNACH. Если такого элемента в дереве нет, то переменная ELEM не будет определена, т.к. на оператор ELEM:= S программа выходит только при условии S^.K = ZNACH. В этом случае значение переменной ELEM^.K - "мусор".

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

procedure POISK1(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if (S^.k >= N1) and (S^.k <= N2) then

¦ begin write(S^.k:3); i:= i+1; end;

¦ if S^.k = ZNACH then begin j:=1;ELEM:= S end

¦ else if S <> nil then

¦ begin

¦ ¦ POISK1(S^.left, ZNACH, ELEM);

¦ ¦ if j = 0 then

¦ ¦ POISK1(S^.right, ZNACH, ELEM);

¦ end;

end.

ПОЯСНЕНИЕ. Данная процедура заканчивает работу либо при нахождении искомого элемента, либо при достижении конца дерева. В ней имеются две глобальные переменные I и J, которые должны быть обнулены в основной программе. Переменная I служит для подсчета просмотренных во время поиска элементов, которые попутно выводятся на печать. При нахождении элемента ZNACH в левом поддереве вырабатывается признак J = 1, препятствующий вхождению поиска в правое поддерево.

Условие (S^.k >= N1) and (S^.k <= N2) необходимо для того, чтобы не выводились на печать K - элементы "сухих" ветвей (выходящих из терминальных вершин) при обходе дерева. Здесь N1 - наименьший и N2 - наибольший из введенных в дерево элементов. Обе эти переменные должны быть определены в основной программе.

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

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

предыдущее звено;

новое звено;

фиксированное звено;

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

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

1) вставлять новый элемент S2 между S и S1;

2) если S ссылается на S1 левым полем, то вставляемый элемент S2 будет также ссылаться на S1 левым полем;

3) если S ссылается на S1 правым полем, то и вставляемый элемент должен ссылаться на S1 правым полем.

а). Левое

б). Правое

S

S

S2

S2

nil

nil

S1

S1

Отсюда следует процедура вставки (нерекурсивная):

procedure VSTAVKA (S, S1, S2: SS);

begin

¦ if S^.left = S1 then

¦ begin

¦ ¦ S^.left:= S2;

¦ ¦ S2^.left:= S1;

¦ ¦ S2^.right:= nil;

¦ end

¦ else

¦ begin

¦ ¦ S^.right:= S2;

¦ ¦ S2^.right:= S1;

¦ ¦ S2^.left:= nil;

¦ end;

end.

ЗАМЕЧАНИЕ. В отличие от процедуры POISK здесь нет на входе явного указания на корень дерева. Однако при указании двух соседних вершин в ссылках на них фигурирует ссылка на корень дерева. Например, для вставки в дерево DER некоего элемента EL между вторым и третьим элементами левого поддерева необходимо выполнить следующие операторы:

new(Z); write ('Введите вставляемый элемент: ');

readln(EL); Z^.k:= EL: Z^.left:= nil; Z^.right:= nil;

VSTAVKA (DER^.left, DER^.left^.left, Z).

На практике ссылка S чаще всего есть результат работы процедуры поиска, т.е. получена путем применения POISK(DER,ZNACH,S). Тогда для вставки элемента Z в левое поддерево вершины S в качестве S1 надо взять S^.left, в противном случае - положить S1=S^.right.

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

Если вершина Si является терминальной (листом) или из нее выходит только одна ветвь, то удаление реализуется довольно просто - для этого надо скорректировать соответствующую ссылку у вершины предшественника:

а).

б).

Si-1

Si-1

Si

Si

Si-1

NIL

Si-1

Si+1

Si-1

NIL

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

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

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

Для второго - надо перейти в следующее звено по правой ветви, а потом идти все время по левой до NIL.

ПРИМЕР. Пусть требуется удалить в дереве вершину 50.

Для решения этой задачи переходим в правое поддерево на вершину 55 и затем идем все время по левым ветвям к вершине 33, которую ставим на место 50.

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

100 | 100

/ \ | / \

20 120 | 20 120

/ \ \ | / \ \

15 50 130 | 15 33 130

/ \ | / \

30 55 | 30 55

/ / \ | / / \

28 35 60 | 28 35 60

/ \ |

33 50 |

Вид дерева |

ДО удаления | Вид дерева ПОСЛЕ удаления 50

15.4 Дерево поиска

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

a) A б) A

/ \ / \

B C C B

/ / \

D D E

Сбалансированное Несбалансированное

Организация ИДЕАЛЬНО СБАЛАНСИРОВАННЫХ деревьев не всегда оправдана, т.к. деревья часто строят для поиска того или иного элемента в структуре данных. В дереве общего вида для поиска одного элемента иногда приходится перебрать и все другие, если этот элемент является листом. Такой путь нерационален, т.к. теряется сама идея построения дерева. Лучше создать линейный список в виде стека, дека или очереди. Вот почему для упрощения поиска при организации дерева его строят в виде ДЕРЕВА ПОИСКА, т.к. число переборов для нахождения нужного элемента здесь значительно меньше.

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

Например, пусть заданы элементы: 10,5,7,12,15,3,7,9. Расположить их в виде дерева поиска с корнем 10.

10

/ \

5 12

/ \ \

3 7 15

\

9

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

Рассмотрим теперь процедуру формирования дерева поиска с учетом принципа его построения:

procedure TREEPOISK(var S: SS; ZNACH: integer);

begin

¦ if S = nil then begin

¦ ¦ new(S); S^.k:= ZNACH;

¦ ¦ S^.left:= nil;

¦ ¦ S^.right:= nil; S^.n:= 1;

¦ end

¦ else

¦ if ZNACH < S^.k then TREEPOISK(S^.left,ZNACH)

¦ else

¦ if ZNACH > S^.k then TREEPOISK(S^.right,ZNACH)

¦ else S^.n:= S^.n + 1;

end.

ЗАМЕЧАНИЕ. Из этой процедуры видно, что звено дерева поиска уже состоит из четырех полей: К, LEFT, RIGHT и N. Целочисленное поле N добавлено для того, чтобы увеличивать его значение при появлении в дереве нескольких одинаковых элементов. Поле S^.n позволяет узнать для каждой вершины число породивших ее элементов (кратность вершины). Дело в том, что в отличие от сбалансированного дерева, в дерево поиска элемент входит только один раз. Например, если подавать на вход процедуры TREEPOISK элементы 7,5,3,2,8,4,3,1,7,9, то сформируется дерево из вершин 7,5,3,2,8,4,1,9, а в 4-м поле звена 7 (в нашем случае корень дерева) будет находиться 2.

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

var DER: SS; EL: integer;

begin write('Введите элемент: '); readln(EL);

¦ DER:=nil;

¦ while EL <> 0 do begin TREEPOISK(DER, EL);

¦ readln(EL); end;

end.

15.5 Операции над деревом поиска

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

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

Например, пусть в дерево надо вставить элемент 4:

10

/ \

5 12

/ \ / \

3 7 11 15

1) т.к. 4 < 10, то нужно идти в левое поддерево(т.е. на 5);

2) т.к. 4 < 5, следует спуститься ниже 5;

3) т.к. 4 > 3, необходимо вставить этот элемент в правое поддерево.

СХЕМА ВСТАВКИ

10

/ \

5 12

/ \ / \

3 7 11 15

\

4

Итак, для вставки в дерево DER элемента 4 надо записать оператор TREEPOISK(DER,4).

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

Например, для поиска некоторого элемента EL в дереве DER необходимо выполнить TREEPOISK(DER, EL), добавив в процедуре TREEPOISK оператор WRITELN(DER^.N), который следует поставить в начало ее тела (после слова BEGIN). Наличие в этом списке числа 2 говорит о вхождении элемента EL в дерево, причем можно даже узнать его порядковый номер.

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

1) поместить данный элемент (не принадлежащий дереву) после указанного элемента дерева;

2) вставить определенный элемент дерева после некоторого элемента того же дерева (переместить элемент).

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

Решение второй задачи может быть реализовано с помощью следующей программы:

program POISK_I_VSTAVKA;

label 1,2,3;

type SS = ^ZVENO;

ZVENO = record

k,n: integer;

left, right: SS;

end;

var DER1,Z,X,T:ss; I,J:integer;

Y:real; O:char;

begin

1:clrscr; gotoxy(20,2);write(' ПОИСК И ВСТАВКА');

writeln; writeln(' ОБЩЕЕ ДЕРЕВО ');writeln;

PRINTTREE(DER1,3,Y); writeln;

writeln('ВСТАВКА HОВОГО ЭЛЕМЕHТА ПОСЛЕ HАЙДЕHHОГО ВЛЕВО');

2:writeln;write('Укажите элемент для вставки: '); readln(I);

POISK(DER1,I,X);

if X^.k <> I then begin

write('Такого элемента нет в деpеве!'); goto 2 end;

3:write('Укажите элемент, за которым идет вставка:');read(j);

POISK(DER1,J,Z); if Z^.k <> J then begin

write('Такого элемента нет в деpеве ! ');

readln;goto 3 end; clrscr;

gotoxy(41,3); write(' ДЕРЕВО до вставки ');

PRINTTREE(DER1,3,Y);

new(T); T^.left:= nil; T^.right:= nil; T^.k:= X^.k;

VSTAVKA(Z,Z^.LEFT,T);

gotoxy(3,3);write(' ДЕРЕВО после вставки ');

PRINTTREE(DER1,3,Y); writeln;

writeln('Вставлен элемент',I:3,'влево после элемента',J:3);

write('Еще ?(y/n): '); readln(O); if O='y' then goto 1

end.

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

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

procedure UDALEN(var Z, X:ss);

{ X - удаляемый элемент, Z - предшествующий}

var P, M: SS; { Вспомогательные вершины }

begin

¦if X^.left = nil then { Удаление левых листов }

¦ if Z^.left^.k = X^.k

¦ then Z^.left:= X^.right

¦ else Z^.right:= X^.right

¦ else { Удаление правых листьев }

¦ if X^.left^.right = nil then

¦ if Z^.left^.k = X^.k then

¦ begin

¦ ¦ Z^.left:= X^.left;

¦ ¦ X^.left^.right:= X^.right;

¦ end

¦ else begin

¦ ¦ Z^.right:=X^.left;

¦ ¦ X^.left^.right:= X^.right;

¦ ¦ Z^.right:=X^.right

¦ end

¦ else begin {Удал-е внутр. вершин}

¦ ¦ P:=X^.left^.right; M:=X^.left;

¦ ¦ while P^.right <> nil do

¦ ¦ begin M:=P; P:=P^.right; end;

¦ ¦ X^.k:=P^.k;

¦ ¦ M^.right:=nil; {Отрезание листа}

¦ end;

end.

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

Все это показано в следующей программе:

program POISK_I_UDALENIE;

label 1,2,3;

type SS = ^ZVENO;

ZVENO = record

k,n: integer;

left, right: SS; end;

var DER,Z,X,T:ss; I,J:integer;

Y:real; O:char;

begin

1:clrscr; gotoxy(20,2); write('ПОИСК И УДАЛЕНИЕ');

writeln(' ДЕРЕВО ПОИСКА '); PRINTTREE(DER,3,Y);

writeln(' УДАЛЕНИЕ УКАЗАННОГО ЭЛЕМЕНТА ');

2:writeln;write('Укажите элемент для удаления: '); readln(I);

POISK(DER,I,X); if X^.k <> I then begin

{ X - ссылка на вершину I }

write('Такого элемента нет в деpеве ! '); readln;goto 2 end;

if X^.k = DER^.k then begin

writeln('ВHИМАHИЕ ! Это - коpень деpева !'); goto 2 end;

3:write('Укажите элемент, перед которым идет удаление:');

readln(J); POISK(DER,J,Z);

{ Z - ссылка на вершину J}

if Z^.k <> J then begin

write('Такого элемента нет в деpеве ! '); goto 3 end;

if (Z^.left^.k <> I) and (Z^.right^.k <> I) then

begin write('Такой паpы элементов нет в деpеве ! ');

goto 3 end; clrscr;

gotoxy(41,3); write(' ДЕРЕВО до удаления '); writeln;

PRINTTREE(der,43,y); UDALEN(Z,X);

gotoxy(3,3);write(' ДЕРЕВО после удаления ');writeln;

PRINTTREE(der,3,y); writeln;

writeln('Удален элемент',i:3,' после элемента ',j:3);writeln;

write('Еще ?(y/n): '); readln(o); if O='y' then goto 1;

end.

15.6 Некоторые дополнительные возможности работы с динамическими структурами

Как мы уже отмечали выше, все динамические структуры, образующиеся в памяти ЭВМ, могут рассматриваться в ОЗУ, отведенной для программы пользователя, как "КУЧА". Пользователь может работать с этой "кучей" с помощью специальных процедур. Среди них самыми важными являются запоминание состояния "кучи" и последующее воспроизведение ее. Это делается с помощью процедур MARK и RELASE.

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

Для решения этой задачи необходимо представлять себе, что все динамические объекты (списки, стеки, деки, очереди, деревья), как и другие простые данные, лежат в некоторой, строго отведенной области ЭВМ. При этом начальный объект в структуре находится в ячейке памяти с номером N, образованным в результате работы процедуры NEW, а последний - в ячейке памяти с номером N+б (дельта), где б, в каком-то смысле, есть длина динамического объекта. Если знать эти числа, т.е. номера первой и последней ячеек, то можно, не обходя все дерево, переписать содержимое группы ячеек между адресами N и N+б на диск в виде файла. Затем при необходимости есть возможность списать с диска данные не куда-нибудь в память, а именно в ячейки с указанными адресами.

Для решения этой задачи используется функция HEAPPTR, которая возвращает так называемый текущий указатель "кучи", т.е. адрес ее конца. В этом случае достаточно запомнить адрес конца "кучи" в самом начале и по окончании работы с динамическими объектами.

Все эти операции реализованы в следующей программе:

procedure ZAPIS(F: file of integer);

var N,K,I,ZN: integer;

begin

N:= HEAPPTR; { Начало "кучи" }

................

{ Создание динамической структуры }

.................

K:= HEAPPTR; {Конец "кучи"}

rewrite(F); write(F, N);

for i:=1 to k do begin ZN:=MEM[i];

write(F, ZN); end;

close(F);

end.

ПОЯСНЕНИЕ. Первым в файл идет начальный адрес "кучи". Это необходимо для того, чтобы узнать потом, с какого адреса можно воспроизвести "кучу". Далее в процедуре идет имя MEM - стандартное имя массива-памяти. То есть вся память понимается как массив, а ее индексы есть адреса ее точек. Это делается в рамках Паскаля. Вся запись и чтение в памяти идет через одномерный массив.

Рассмотрим теперь процедуру воспроизведения, где данные считываются из файла и записываются в нужные адреса памяти:

procedure VOSPROIZV(F: file of integer; var NACH: SS;)

var ZN, N:integer;

begin reset (F); read(F, ZN);

NACH:= ptr(ZN); n:= zn;

{Начальный адрес заполнения памяти}

while not eof(F) do begin read(F, ZN);

mem[N]:= ZN;

N:= N+1; end;

close(F);

end.

ПРИМЕЧАНИЕ. Здесь PTR - функция, восстанавливающая ссылку на адрес ZN - первый адрес динамической структуры. Эта ссылка запоминается в переменной NACH, после чего процедура может обращаться к динамическому объекту по данной ссылке.

ЛИТЕРАТУРА

Йенсен К.В. Паскаль: руководство для пользователя и описание языка. - М.: Финансы и статистика, 1982.

Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль.- М.: Наука, 1989.

Эрбс Х.Э., Штольц О. Введение в программирование на языке Паскаль.- М.: Наука, 1989.

Корноухов М.А., Пантелеев И.В. Справочное руководство по языку программирования TURBO-PASCAL.- М.: Изд-во МГУ им.Ломоносова, 1985.

Хершель Р. Турбо Паскаль.- Вологда: МП "МИК", 1991.

ПРИЛОЖЕНИЕ

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

program RABMAS; uses crt;

const M=10; N=10;

type LINE = array[1..n ] of integer;

TAB = array[1..m] of LINE;

var S,I,J,X,Y:integer; MAS:TAB;

{ ВХОЖДЕНИЕ БКУВ В ТЕКСТ }

procedure COUNTER;

var COUNT: array['a'..'z'] of integer;

CH: char; N: integer;

begin

¦ for CH:= 'a' to 'z' do

¦ COUNT [CH]:= 0; N:= 0;

¦ repeat

¦ ¦ read(CH); N:= N+1;

¦ ¦ if (CH >= 'a') and (CH <= 'z') then

¦ ¦ COUNT [CH]:= COUNT [CH]+1;

¦ until CH = '.'; readln; writeln;

¦ writeln('Частота вхождения букв: '); writeln;

¦ for CH:= 'a' to 'z' do

begin

¦ ¦write(CH,COUNT[CH]:10,COUNT[CH]*100/N:10:2,' ':15);

¦ ¦CH:=succ(CH);

¦ ¦writeln(ch,count[ch]:10,count[CH]*100/N:10:2);

¦ end;

end;

{ ЧИСЛО ДНЕЙ В МЕСЯЦЕ }

procedure NUMBRDAY;

type MONAT = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,

SEP, OKT, NOV, DEC);

var DAY: array [MONAT] of 28..31;

T: MONAT; k:integer;

begin

¦ for T:= JAN to DEC do

¦ case T of

¦ JAN, MAR, MAY, JUL, AUG, OKT, DEC: DAY[T]:= 31;

¦ APR, JUN, SEP, NOV: DAY[T]:= 30;

¦ FEB: DAY[T]:= 28;

¦ end;

¦ writeln(' Число дней в месяцах: '); K:=1;

¦ for T:= JAN to DEC do begin

¦ writeln(' ',K:2,'-й',' месяц ',day[t],' дней ');

¦ K:=K+1;

¦ end;

end;

{ ВВОД, ПЕЧАТЬ И ОБРАБОТКА МАССИВА }

procedure VVODMASSIV(M,N:integer;var MAS:TAB);

begin

¦ for I:=1 to M do

¦ for J:=1 to N do

¦ read(MAS[I][J]); readln;

end;

procedure VIVODMASSIV(M,N:integer;var MAS:TAB);

begin

¦ for I:=1 to M do

¦ begin

¦ ¦ for J:=1 to N do

¦ ¦ write(MAS[I][J]:5,' ');

¦ ¦ writeln;

¦ end;

end;

procedure OBRABOTKA(M,N:integer; MAS:TAB; var SUM:integer);

begin

¦ SUM:= 0;

¦ for I:=1 to M do

¦ for J:=1 to n do

¦ if J > I then SUM:= SUM+MAS[I][J];

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin

clrscr; writeln(' ПОДСЧЕТ ЧИСЛА ВХОЖДЕНИЙ БУКВ В ТЕКСТ');

writeln; write('Введите текст с точкой на конце: ');COUNTER;

readln;clrscr;

writeln(' ЧИСЛО ДHЕЙ В МЕСЯЦАХ ГОДА !');

writeln; NUMBRDAY; READLN;

CLRSCR;writeln('СУММА ЭЛ-ОВ МАССИВА HАД ГЛАВHОЙ ДИАГHАЛЬЮ ');

writeln; write(' Введите число стpок матpицы: '); readln(X);

write(' Введите число столбцов матpицы: ');readln(Y);

write(' Введите чеpез пpобел ',X*Y,' чисел(ла): ');

VVODMASSIV(X,Y,MAS); writeln; writeln;

writeln(' ИСХОДНЫЙ МАССИВ');

VIVODMASSIV(X,Y,MAS); OBRABOTKA(X,Y,MAS,S);writeln;

writeln(' Сумма элементов = ',s);

writeln; write (' К О H Е Ц Р А Б О Т Ы ! ');readln;

end.

program LITERI; uses crt;

procedure SKOBKI;

var c: char; i: integer;

begin

¦ i:=0; read(c); writeln;

¦ write('Строка без скобок: ');

¦ while c <> '.' do

¦ begin

¦ ¦ if c='(' then i:=1

¦ ¦ else if c = ')' then i:=0

¦ ¦ else if i=0 then write(c);

¦ ¦ read(c);

¦ end;

end;

procedure SUITE;

var c,d: char;

b¦gin

¦for c:='a' to 't' do

¦ begin

¦ ¦for d:='a' to c do write(d);

¦ ¦writeln(' ');

¦ end;

end;

procedure SOWPADENIE;

label 1;

type t = array[1..5] of char;

var s:t; y:char; i:integer;

begin

¦ write('Введите пеpвые 5 символов: ');

¦ for i:=1 to 5 do read(s[i]); readln;

¦ write('Введите последние 5 символов:');

¦ for i:=1 to 5 do

¦ begin

¦ ¦ read(y);

¦ ¦ if s[i] <> y then

¦ ¦ begin writeln;

¦ ¦ ¦ write('ОТВЕТ: не совпадает');

¦ ¦ ¦ goto 1;

¦ ¦ end;

¦ end;

¦ writeln;write('ОТВЕТ: совпадает'); 1:;

end;

procedure REVERSE;

var OLD_LINE, NEW_LINE: string[50];

PROBEL: integer; WORD: string[50];

begin

¦ NEW_LINE:= ''; readln(OLD_LINE);

¦ OLD_LINE:= concat(OLD_LINE,' ');

¦ while OLD_LINE <> '' do

¦ begin

¦ ¦ PROBEL:= pos(' ', OLD_LINE);

¦ ¦ WORD:= copy(OLD_LINE, 1, PROBEL);

¦ ¦ NEW_LINE:= concat(WORD, NEW_LINE);

¦ ¦ delete(OLD_LINE, 1, PROBEL);

¦ end;

¦ writeln; write('СЛОВА В ОБРАТHОМ ПОРЯДКЕ: ');

¦ writeln(NEW_LINE)

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin clrscr;writeln('ПЕЧАТЬ ЭЛЕМЕНТОВ СТРОКИ ');writeln;

write('Введите строку, включая скобки (точка в конце):');

SKOBKI; readln;readln;clrscr;

writeln(' ПЕЧАТЬ ПОСЛЕДОВАТЕЛЬНОСТИ БУКВ ');writeln;

SUITE; readln;clrscr;

writeln('СОВПАДЕНИЕ НАЧАЛА ПОСЛЕДОВАТЕЛЬHОСТИ С КОНЦОМ ');

writeln; write('Введите 10 символов !'); writeln;

SOWPADENIE; readln;readln;clrscr;

writeln('ПЕЧАТЬ СЛОВ В ОБРАТНОМ ПОРЯДКЕ ');writeln;

write('Введите пpедложение, отделяя слова пpобелами: ');

REVERSE; writeln;write(' К О H Е Ц Р А Б О Т Ы !');

readln; end.

program MNOJESTVA; uses crt;

type KOST = 1..6; BROSOK = set of KOST;

var A,B,C: BROSOK; M:integer;

procedure ERATOS(N:integer);

const MAXPRIM = 100;

var PRIMES: set of 2..MAXPRIM;

COUNT, MULTIPLE: integer;

begin

¦ write('Простые числа, меньше ', N, ': ');

¦ PRIMES:= [2..MAXPRIM];

¦ for COUNT:= 2 to N do

¦ if COUNT in PRIMES then

¦ begin

¦ ¦ write(COUNT:3);

¦ ¦ for MULTIPLE:=1 to (N div COUNT) do

¦ ¦ PRIMES:= PRIMES-[COUNT*MULTIPLE]

¦ end;

end;

procedure SRAWNENIE (D: BROSOK);

var K: KOST;

begin

¦ write('[ ');

¦ for K:= 1 to 6 do

¦ if K in D then write(K:2,',');

¦ write(' ]');writeln

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin

clrscr; writeln(' ПЕЧАТЬ ПРОСТЫХ ЧИСЕЛ ПО ЭРАТОСФЕНУ ');

writeln; write('Введите веpхнюю гpаницу пpостых чисел: ');

readln(M); ERATOS(M); writeln; readln; clrscr;

writeln(' ДЕЙСТВИЯ HАД МНОЖЕСТВАМИ И ИХ ВЫВОД ');

writeln;

A:= [1,3,4]; B:= [2,4,6];

C:= A + B; writeln(' С У М М А ');

write('[ 1, 3, 4 ] + [2, 4, 6 ] = ');

SRAWNENIE (C); writeln;

C:= A - B; writeln(' Р А З H О С Т Ь ');

write('[ 1, 3, 4 ] - [ 2, 4,6 ] = ');

SRAWNENIE (C);writeln;

C:= A * B; writeln(' П Е Р Е С Е Ч Е H И Е ');

write('[ 1, 3, 4 ] * [ 2, 4, 6 ] = ');

SRAWNENIE (C); writeln;

writeln(' К О H Е Ц Р А Б О Т Ы !');readln;

end.

program zapisi; uses crt;

type PATIENT = record

NAME: string [10];

MALADI: string [30];

AGE: integer;

DATE: record

DEN: integer;

MESJATS: string [10];

GOD: integer;

end;

MARIE: boolean;

end;

var NEKTO: PATIENT;

procedure INST;

const N_STUD = 5;

N_SOTR = 3;

N = 10;

type SEX = CHAR;

STUD = RECORD

FAM,IM,OTH: array [1..N_STUD] of string[n];

POL: SEX;

GR: 111..154;

STIP: boolean;

end;

SOTR = record

AM,IM,OTH: array [1..N_SOTR] of string[n];

POL: SEX;

DOLGN: (LAB, ASS, STPR, DOZ, PROF);

ZARPL: integer;

end;

var X: STUD; Y: SOTR;

STIP: integer;

begin

¦ with X, Y do

¦ begin

¦ ¦ IM[3]:= 'ALEXANDR ';

¦ ¦ POL:= 'M';

¦ ¦ STIP:= true;

¦ ¦ GR:= 122;

¦ ¦ write(IM[3],' ', POL,' ',STIP,' ',GR);

¦ end;

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin

clrscr; write('ДАHHЫЕ О БОЛЬHОМ ПАЦИЕHТЕ: ');

with NEKTO, DATE do

begin

¦ NAME:= 'MANUELA'; AGE:= 20;

¦ MALADI:= 'GRIP';

¦ DEN:= 18;

¦ MESJATS:= 'MART';

¦ GOD:= 1944;

¦ MARIE:= TRUE;

¦ write('ПАЦИЕНТ: ',NAME,' ',AGE,' ', DEN,' ');

¦ write('MESJATS,' ', GOD,' ', MARIE,' ', MALADI);

end;

writeln; writeln;write('ДАHHЫЕ О СОТРУДHИКЕ: ');

INST; readln; writeln;

write('КОНЕЦ РАБОТЫ!'); readln;

end.

program FILES(FIL);uses crt;

type KOD = 65..90; SHIFR = file of kod;

var SH: SHIFR; F: text; N: integer;

procedure KODIROVKA;

type KOD = 65..90;

SHIFR = file of KOD;

var X: KOD;

SH: SHIFR;

begin

¦ assign(SH,'SHFRTXT');

¦ rewrite (SH);

¦ read(X);

¦ while X<> 00 do

¦ begin

¦ ¦ write (SH,X);

¦ ¦ read(x);

¦ end;

¦close(SH); readln;

end;

procedure RASSHIFROVKA;

type KOD = 65..90;

LITERA = 'a'..'z';

SHIFR = file of KOD;

var X: KOD; Y: LITERA;SH: SHIFR;

begin

¦ assign(SH,'SHFRTXT');

¦ reset(SH);

¦ while not eof(SH) do

¦ begin

¦ ¦ read(SH,X);

¦ ¦ Y:=chr(X);

¦ ¦ write(Y:2,' ');

¦ end; close(sh);

end;

procedure MAXELEM;

type FT = file of integer;

var F,G,H: FT;

i,j: integer;

procedure VIVODFILE(var A: FT);

begin

¦ reset(a);

¦ while not eof(A) do

¦ begin

¦ read(A,I); write(I:4);

¦ end; writeln;

¦

end;

begin { формирование исходных файлов }

¦ assign(f,'f'); assign(g,'g'); assign(h,'h');

¦ randomize; rewrite(f);

¦ for i:=1 to 10 do

¦ begin

¦ j:= random(10)-5; write(f,j);

¦ end;

¦ writeln(' Пеpвый исходный файл: ');

¦ VIVODFILE(f); close(f); writeln;

¦ rewrite(g);

¦ for i:= 1 to 10 do

¦ begin

¦ j:= random(10)-5; write(g,j);

¦ end;

¦ writeln(' Втоpой исходный файл: ');

¦ VIVODFILE(g); close(g); writeln;

¦ { Формирование файла результата }

¦ reset(f); reset(g); rewrite(h);

¦ while not eof(f) do

¦ begin

¦ ¦ read(f,i); read(g,j);

¦ ¦ if i > j then write(h,i) else write(h,j);

¦ end;

¦ writeln(' Файл - pезультат: '); VIVODFILE(h);

¦ writeln; close(h); close(g); close(f);

¦

end;

procedure NOMBRELINE;

var K: integer; BOOK: text; S: char;

begin { формирование файла BOOK }

¦ assign(BOOK,'f1'); rewrite(BOOK);

¦ read(S);

¦ while S<> '.' do begin

¦ while S <> '$' do begin

¦ write(BOOK,S); read(S); end;

¦ writeln(BOOK); read s);end;

¦ close(BOOK);

¦ { подсчет числа строк в тексте BOOK }

¦ K:= 0; reset(BOOK); writeln;writeln('С Т Р О К И:');

¦ writeln;

¦ while not eof(BOOK) do

¦ begin

¦ ¦ if eoln(BOOK) then K:=K+1;

¦ ¦ read(BOOK,S); write(S);

¦ end;writeln;

¦ writeln('В текстовом файле BOOK ', K,' - строк(и)');

¦ close(BOOK);

end;

procedure NOMBRELINE1;

var K: integer; BOOK: text; S: char;

begin

¦{ Формирование файла BOOK }

¦ assign(BOOK,'f1'); rewrite(BOOK);

¦ read(S);

¦ while s<> '.' do begin

¦ write(BOOK,s); read(s);

¦ end; close(BOOK);

¦ { подсчет числа строк в тексте BOOK }

¦ K:= 0; reset(BOOK); writeln;writeln('С Т Р О К И:');

¦ while not eof(BOOK) do

¦ begin

if eoln(BOOK) then K:=K+1; read(BOOK,S); write(S);

¦ end;writeln;

¦ writeln('В текстовом файле BOOK ', K,' - строк(и)');

¦ close(BOOK);

end;

procedure FORMFIL;

var F: text; s: char;

begin

¦ assign(F,'ACROSTIH');

¦ rewrite(F); read(s);

¦ while s<> '#' do begin

¦ while s <> '$' do begin

¦ write(F,s); read(s); end;

¦ writeln(F);read(s);end;

¦ close(F);

end;

procedure FORMFIL1;

var F: text; s: char;

begin

¦ assign(F,'FIL');

¦ rewrite(F); read(s);

¦ while s<> '#' do begin

¦ write(F,s); read(s); end;

¦ close(F);

end;

procedure SLOVO;

var l:char; T: text;

begin

¦ assign(T,'ACROSTIH');

¦ reset(T);

¦ while not eof(T) do

¦ begin

¦ ¦ read(T,l); write(l);

¦ ¦ readln(T);

¦ end;

end;

function PUNCTUATION(var CHARFILE: text): integer;

var SYMBOLNOMB: integer;

SYMBOL: char;

begin

¦ SYMBOLNOMB:=0; reset(CHARFILE);

¦ write('Знаки пунктуации: ');

¦ while not eof(CHARFILE) do

¦ begin

¦ ¦ read(CHARFILE, SYMBOL);

¦ ¦ if SYMBOL in ['.',',',' ',':',';','-','!','?']then

¦ ¦ begin

¦ ¦ ¦ write(symbol,' ');

¦ ¦ ¦ symbolnomb:= symbolnomb+1;

¦ ¦ end;

end; writeln;

¦ PUNCTUATION:= SYMBOLNOMB;

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin

clrscr; writeln(' РАСШИФРОВКА '); writeln;

writeln('Введите чеpез пpобел одоы от 65 до 90 !');

writeln('00 - признак конца !'); writeln;

write(' Коды: '); KODIROVKA;

writeln; write('Расшифровка: ');

assign(sh,'shfrtxt');reset(sh);RASSHIFROVKA; readln;

clrscr;writeln(' ФАЙЛ МАКСИМАЛЬНЫХ ЭЛЕМЕНТОВ ');

writeln; MAXELEM; readln; clrscr;

writeln(' ЧИСЛО СТРОК В ТЕКСТЕ '); writeln;

writeln('Введите текст, отделяя стpоки знаком $ !');

writeln('Пpизнаком конца текста служит точка !');writeln;

write('Текст:'); NOMBRELINE; readln; readln;clrscr;

writeln(' ЧИСЛО СТРОК В ТЕКСТЕ '); writeln;

writeln('Введите текст, отделяя стpоки нажатием клавиши ENTER !');

writeln('Пpизнаком конца текста служит точка !');writeln;

write('Текст:'); NOMBRELINE1; readln; readln;clrscr;

writeln(' А К Р О С Т И Х '); writeln;

writeln('Введите текст, отделяя стpоки знаком $ !');

writeln('Пpизнаком конца текста служит # !');writeln;

write('Текст:'); FORMFIL; writeln;

write('Зашифрованное слово: '); SLOVO; readln; readln;clrscr;

writeln(' ЧИСЛО ЗНАКОВ ПРЕПИНАНИЯ В ТЕКСТЕ '); writeln;

writeln('Введите текст, пpизнаком конца текста служит # !');

write('Текст: ');FORMFIL1;

assign (F,'FIL'); reset(F); N:=PUNCTUATION(F); close(F);

writeln('Число знаков препинания в тексте FIL =', n);

write(' КОHЕЦ РАБОТЫ !'); readln;readln;

end.

program OBRABOTKA_ZEPOCHKI; uses crt;

type SVYAZ = ^ZVSTR;

ZVSTR = record

elem: char;

sled: SVYAZ;

end;

var UKSTR, UKZV: SVYAZ;

SYM,CH: char;

procedure VIVOD(var UKSTR: SVYAZ);

var UKZV: SVYAZ;

begin

¦ { распечатка строки }

¦ UKZV:= UKSTR^.sled;

¦ while UKZV <> nil do

¦ begin

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

¦ ¦ ukzv:=UKZV^.sled;

¦ end;

end;

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

var ZV: SVYAZ;

begin

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

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

¦ else begin ZV:=SP;

¦ ¦ SP:=SP^.sled;

¦ ¦ dispose(ZV);

¦ end;

end;

procedure UDALENIE1(var SP: SVYAZ);

var Q: SVYAZ;

begin

¦ if SP^.sled <> nil then

¦ begin

¦ ¦ Q:= SP;

¦ ¦ SP:= SP^.sled;

¦ ¦ dispose(Q);

¦ end

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

end;

procedure VSTAVKA(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;

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

var Q: SVYAZ;

begin

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

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

¦ SP^.sled:= Q

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin clrscr;

gotoxy(15,3);write('ДИHАМИЧЕСКАЯ ЦЕПОЧКА');

writeln;writeln;

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

write(' Введите последовательность символов с точкой:');

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;

readln; writeln;

write(' Исходная цепочка: ');

VIVOD(UKSTR); writeln; writeln;

write(' Введите удаляемую букву: '); readln(SYM);

UDALENIE(UKSTR,SYM); writeln;

write(' Полученная цепочка: ');

VIVOD(UKSTR); writeln; writeln;

UDALENIE1(UKSTR);

write('Цепочка с удаленным первым элементом:');

VIVOD(UKSTR); writeln;writeln;

write(' Введите новую букву: '); readln(SYM);

write(' Введите букву, за которой идет вставка: ');

readln(CH); VSTAVKA(UKSTR,CH,SYM);

write(' Полученная цепочка с вставленным элементом: ');

VIVOD(UKSTR); writeln; writeln;

write(' Введите новую букву: '); readln(SYM);

VSTAVKA1(UKSTR,SYM);writeln;

write(' Цепочка со вставленным головным элементом: ');

VIVOD(UKSTR); writeln; writeln;

writeln('К О Н Е Ц Р А Б О Т Ы !');readln;

end.

program otch; uses crt;

type SS = ^ZVENO;

ZVENO = record

elem: char;

next: SS;

end;

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

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

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

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

procedure VIVOD_OTCHERED (var L, R: SS);

var K: SS;

begin

¦ if (L^.elem= '.') 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;

procedure FORMIR_OTCHERED (var L, R: SS);

var K: SS;

EL1, EL2: char;

begin

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

¦read(el1);

¦if el1='.' then begin l:=nil; r:=l end

¦ else begin new(K);

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

¦ ¦ K^.elem:= EL1;

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

¦ ¦read(EL2);

¦ ¦while (EL1<>'.') and (EL2<>'.') do

¦ ¦ begin

¦ ¦ ¦ new(K);

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

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

¦ ¦ end; readln;

¦ end;

end;

procedure FORMIR_OTCHERED1(var L, R: SS);

var K: SS;

EL1, EL2: char;

begin

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

¦ read(EL1); new(K);

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

¦ K^.elem:= EL1;

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

¦ read(EL2);

¦ while (EL1<>'.') and (EL2<>'.') do

¦ begin

¦ ¦ new(K);

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

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

¦ end; readln;

end;

procedure DOBAV_OTCHERED (el:char; var l, r: ss);

var k: ss;

begin

¦ writeln(' Добавляемый элемент: ',el);

¦ if (l^.elem = '.') 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;

procedure UDALENIE_OTCHERED (var l, r:ss);

begin

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

¦ else l:=l^.next

end;

{ ОСНОВНАЯ ПРОГРАММА }

begin

clrscr; gotoxy(25,3); writeln(' ОЧЕРЕДЬ '); writeln;

write(' Введите элементы очереди с точкой:');

FORMIR_OTCHERED (L, R);

VIVOD_OTCHERED(L, R); writeln; writeln;

write(' Введите новый элемент: '); readln(EL1);

DOBAV_OTCHERED(EL1,L,R);

VIVOD_OTCHERED(L, R);writeln; writeln;

UDALENIE_OTCHERED (L,R);

writeln(' Удаление элемента из очереди !');

VIVOD_OTCHERED(L, R); writeln;writeln;

UDALENIE_OTCHERED(L,R);

writeln(' Удаление элемента из очереди !');

VIVOD_OTCHERED(L,R); writeln;

write(' Введите элементы очереди с точкой:');

FORMIR_OTCHERED1 (L, R);

VIVOD_OTCHERED(L, R); writeln;writeln;

write(' Введите новый элемент: '); readln(EL1);

DOBAV_OTCHERED(EL1,L,R);

VIVOD_OTCHERED(L, R);writeln; writeln;

UDALENIE_OTCHERED (L,R);

writeln(' Удаление элемента из очереди !');

VIVOD_OTCHERED(L, R); writeln;writeln;

writeln(' К О Н Е Ц Р А Б О Т Ы !');readln;

end.

program STACK; uses crt;

type SS = ^ZVENO;

ZVENO = record

elem: integer; next: SS;

end;

var ST: SS; {начало очереди}

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

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

el,sklad,kol: integer; {рабочий элемент}

procedure VIVOD(var ukstr: SS);

var ukzv: SS;

begin

¦ kol:=0; { распечатка строки }

¦ ukzv:=ukstr;

¦ while ukzv<>nil do

¦ begin

¦ ¦ write(ukzv^.elem,' '); kol:=kol+1;

¦ ¦ ukzv:=ukzv^.next;

¦ end; writeln;

¦ writeln(' Стек содеpжит ',kol,' элемента(ов) !');

end;

procedure SOZDAN_STACK (var ST: SS;var kol:integer);

var K: SS;

EL: integer;

begin

¦ randomize; write(' Подаваемые в стек элементы: ');

¦ new(ST); ST:= nil; kol:=0;

¦ EL:= random(5); write(el,' ');

¦ while EL <> 0 do

¦ begin

¦ ¦ new(K); K^.elem:= EL;

¦ k^.next:= ST; ST:= K;

¦ ¦ EL:= random(5); write(el,' '); kol:=kol+1;

¦ end;

end;

procedure VSTAVKA_V_STACK(var ST:SS; EL:integer);

var K: SS;

begin

¦ new(K); K^.elem:= EL;

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

end;

procedure UDALENIE_IZ_STACK(var ST: SS;var SKLAD: integer);

begin

¦ SKLAD:= ST^.elem;

¦ ST:= ST^.next

end;

procedure UDALENIE_1(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;

procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;


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

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

    лекция [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-файлы представлены только в архивах.
Рекомендуем скачать работу.