Программирование на языке delphi

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

УПРАВЛЕНИЕ ОБРАЗОВАНИЯ ГОРОДА АЛМАТЫ

ЦЕНТРАЛЬНОАЗИАТСКИЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ

КОЛЛЕДЖ

ОТЧЕТ

по учебной практике №2

по программированию

Выполнил студент:

Белоусов Т.

специальность 1304000

квалификация 1304053

группа ТЗИ2Б

Проверил преподаватель:

Наумов В.В.

Алматы 2011

СОДЕРЖАНИЕ

Введение

1 Общая часть

1.1 Вложенные циклы

1.2 Одномерные массивы

1.3 Матица

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

1.3.2 Комбинированные типы данных

1.4 Иерархические записи

1.5 Оператор выбора

1.6 Циклы с параметрами

1.7 Циклы с предусловием

1.8 Циклы с постусловием

2 Специальная часть

2.1 Постановка задачи № 1

2.1.1 Таблица идентификаторов

2.1.2 Блок-схема алгоритма № 1

2.1.3 Контрольный пример № 1

2.1.4 Листинг программы № 1

2.2 Постановка задачи № 2

2.2.1 Таблица идентификаторов

2.2.2 Блок-схема алгоритма № 2

2.2.3 Контрольный пример № 2

2.2.4 Листинг программы № 2

2.3 Постановка задачи № 3

2.3.1 Таблица идентификаторов

2.3.2 Блок-схема алгоритма № 3

2.3.3 Контрольный пример № 3

2.3.4 Листинг программы № 3

2.4 Постановка задачи № 4

2.4.1 Таблица идентификаторов

2.4.2 Блок-схема алгоритма № 4

2.4.3 Контрольный пример № 4

2.4.4 Листинг программы № 4

2.5 Постановка задачи № 5

2.5.2 Блок-схема алгоритма № 5

2.5.3 Контрольный пример № 5

2.5.4 Листинг программы № 5

2.6 Постановка задачи № 6

2.6.1 Таблица идентификаторов

2.6.2 Блок-схема алгоритма № 6

2.6.3 Контрольный пример № 6

2.6.4 Листинг программы № 6

Заключение

Список литературы

1.Общая часть

1.1 Вложенные циклы

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

Полное число исполнений тела внутреннего цикла не превышает произведения числа итераций внутреннего и всех внешних циклов. Например взяв три вложенных друг в друга цикла, каждый по 10 итераций, получим 10 исполнений тела для внешнего цикла, 100 для цикла второго уровня и 1000 в самом внутреннем цикле.

Одна из проблем, связанных с вложенными циклами -- организация досрочного выхода из них. Во многих языках программирования есть оператор досрочного завершения цикла (break в Си, exit в Турбо Паскале, last в Perl и т. п.), но он, как правило, обеспечивает выход только из цикла того уровня, откуда вызван. Вызов его из вложенного цикла приведёт к завершению только этого внутреннего цикла, внешний же цикл продолжит выполняться. Проблема может показаться надуманной, но она действительно иногда возникает при программировании сложной обработки данных, когда алгоритм требует немедленного прерывания в определённых условиях, наличие которых можно проверить только в глубоко вложенном цикле.

Решений проблемы выхода из вложенных циклов несколько.

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

Альтернатива -- использовать штатные средства завершения циклов, в случае необходимости устанавливая специальные флаги, требующие немедленного завершения обработки. Недостаток -- усложнение кода, снижение производительности без каких-либо преимуществ, кроме теоретической «правильности» из-за отказа от goto.

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

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

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

1.2 Одномерные массивы

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

ТИП имя_переменной[] ;

Здесь ТИП задает базовый тип массива. Базовый тип определяет тип данных каждого из элементов, составляющих массив. Таким образом, базовый тип массива определяет тип данных, которые будет содержать массив. Например, следующий оператор объявляет массив month_days, имеющий тип "массив элементов типа int":

int roonth_days[];

Хотя это объявление утверждает, что month_days -- массив переменных, в действительности никакого массива еще не существует. Фактически значение массива month_ days установлено равным null, которое представляет массив без значений. Чтобы связать month_days с реальным физическим массивом целочисленных значений, необходимо с помощью операции new распределить память и присвоить ее массиву month_days.

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

переменная_массива = new тип [размер] ;

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

month_days = new int[12];

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

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

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

month_days[1] = 28;

Следующая строка кода отображает значение, хранящееся в элементе с индексом, равным 3:

System.out.println(month_days[3]) ;

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

// Демонстрация использования одномерного массива.

class Array {

public static void main(String argsf]) {

int month_days[];

month_days = new int[12];

month_days[0] = 31;

month_days[1] = 28;

month_days[2] = 31;

month_days[3] = 30;

month_days[4] = 31;

month_days[5] = 30;

month_days[6] =31;

month_days[7] = 31;

month_days[8] = 30;

month_days[9] = 31;

month_days[10] = 30;

month_days[11] = 31;

System.out.println("В апреле " + month_days[3] + " дней.");

}

}

Если выполнить эту программу, она выведет количество дней в апреле. Как уже было сказано, в Java индексация элементов массивов начинается с нуля, поэтому количество дней в апреле -- month_days [ 3 ], или 30.

Объявление переменной массива можно объединять с распределением самого массива, как показано в следующем примере:

int month_days[] = new int[12];

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

// Усовершенствованная версия предыдущей программы.

class AutoArray {

public static void main(String args[]) {

int month_days [] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

System.out.println("В апреле " + month_days[3] + " дней.");

}

}

При выполнении этой программы она генерирует такой же вывод, как и предыдущая версия.

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

1.3 Матрицы

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

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

Рассмотрим двумерный массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:

Каждый элемент имеет свой номер, как у одномерных массивов, но сейчас номер уже состоит из двух чисел - номера строки, в которой находится элемент, и номера столбца. Таким образом, номер элемента определяется пересечением строки и столбца. Например, a 21 - это элемент, стоящий во второй строке и в первом столбце.

Описание двумерного массива Паскаля.

Существует несколько способов объявления двумерного массива Паскаля.

Мы уже умеем описывать одномерные массивы, элементы которых могут иметь любой тип, а, следовательно, и сами элементы могут быть массивами. Рассмотрим следующее описание типов и переменных:

Пример описания двумерного массива Паскаля

Type

Vector = array [1..5] of <тип_элементов>;

Matrix= array [1..10] of vector;

Var m: matrix;

Мы объявили двумерный массив Паскаля m, состоящий из 10 строк, в каждой из которых 5 столбцов. При этом к каждой i -й строке можно обращаться m [ i ], а каждому j -му элементу внутри i -й строки - m [ i , j ].

Определение типов для двумерных массивов Паскаля можно задавать и в одной строке:

Type

Matrix= array [1..5] of array [1..10] of < тип элементов >;

или еще проще:

type

matrix = array [1..5, 1..10] of <тип элементов>;

Обращение к элементам двумерного массива имеет вид: M [ i , j ]. Это означает, что мы хотим получить элемент, расположенный в i -й строке и j -м столбце. Тут главное не перепутать строки со столбцами, а то мы можем снова получить обращение к несуществующему элементу. Например, обращение к элементу M [10, 5] имеет правильную форму записи, но может вызвать ошибку в работе программы.

Основные действия с двумерными массивами Паскаля

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

type

matrix= array [1..5, 1..10] of integer;

var

a , b : matrix ;

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

Ввод двумерного массива Паскаля.

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

Рассмотрим пример ввода двумерного массива Паскаля с клавиатуры:

Пример программы ввода двумерного массива Паскаля с клавиатуры

type

matrix= array [1..5, 1..10] of integer;

var

a, : matrix;

i, j: integer; { индексы массива }

begin

for i :=1 to 5 do {цикл для перебора всех строк}

for j :=1 to 10 do {перебор всех элементов строки по столбцам}

readln ( a [ i , j ]); {ввод с клавиатуры элемента, стоящего в i -й строке и j -м столбце}

Комбинированный тип данных (записи)

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

Пример

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

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

Запись - это структурированный тип, содержащий набор объектов разных типов. Составляющие запись объекты называются ее полями. В записи каждое поле имеет свое собственное имя. Чтобы описать запись, необходимо указать ее имя, имена объектов, составляющих запись и их типы. Общий вид такой:

Type

"имя записи" = Record

"поле 1" : "тип 1";

"поле 2" : "тип 2";

...

"поле n" : "тип n"

End;

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

Type

pupil = Record

fam: String[15]; {поле фамилии ученика}

b1, b2, b3, b4, b5 : 2...5; {поля баллов по дисциплинам}

sb : Real {поле среднего балла}

End;;

Запись

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

Чтобы хранить в памяти ЭВМ информацию о всех 25 учениках класса, необходимо ввести массив klass, представляющий массив записей:

Var klass : Array[1.25] Of pupil;

Примечания

1. Имена полей, составляющих запись, не должны повторяться.

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

Доступ к полям записи

Его можно осуществить двумя способами.

1. Указанием имени переменной и имени поля. Например, klass[2].fam, klass[3].sb, klass[1].b4. Поэтому ввод фамилий и оценок учащихся, то есть элементов массива klass, можно задать так:

For i: = 1 To 25 Do

Begin

Readln(klass[i].fam);

Readln(klass[i].b1);

Readln(klass[i].b2);

Readln(klass[i].b3);

Readln(klass[i].b4);

Readln(klass[i].b5);

End;

2. Использованием оператора присоединения, который позволяет осуществлять доступ к полям записи, таким образом, как если бы они были простыми переменными. Его общий вид:

With <имя записи> Do <оператор>.

Внутри оператора к компонентам записи можно обращаться только с помощью имени соответствующего поля.

Пример

For i : = 1 To 25 Do

With klass [i] Do

Begin

Readln (fam);

ReadLn (b1,b2,b3,b4,b5);

End;

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

Program Example_54;

Type

pupil = Record

fam : String[15];

b1, b2, b3, b4, b5 :2..5;

sb : Real;

End;

Var klass : Array[1..25] Of pupil;

p : pupil;

i, m : Integer;

sbmax : Real;

Begin

{ввод исходных данных}

For i:=1 To 25 Do

With klass[i] Do

Begin

Writeln ('Введите фамилию и пять оценок');

Readln(fam);

ReadLn(b1,b2,b3,b4,b5);

End;

For i:=1 To m Do

With klass[i] Do sb:=(b1+b2+b3+b4+b5)/5; {поиск максимального среднего балла}

sbmax:=0;

For i:=1 To m Do

If klass[i].sb>=sbmax Then sbmax:=klass[i].sb; {печать результатов}

For i:=1 To m Do

If klass[i].sb=sbmax Then

With klass[i] Do Writeln(fam:20,'-',sb:6:3);

Readln;

End.

Пример

Определить дату завтрашнего дня.

Решение

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

Пусть дата вводится следующим образом:

1 2 1997

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

Type

year = 1500..2000;

month = 1..12;

day = 1..31;

data = Record

y : year;

m : month;

d : day;

End;

Заметим, что:

Если это не последний день месяца, то завтра будет этот же год, этот же месяц, а число увеличится на 1.

Если это последний день месяца, то:

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

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

Program Example_55;

Type year = 1500..2000;

month = 1..12;

day = 1..31;

data = Record

y : year;

m : month;

d : day;

End;

Var dat, next : data; {dat - переменная для сегодняшней даты, next - переменная для определения даты завтрашнего дня}

Function Leap(yy: year): Boolean; {функция, определяющая високосный год или нет}

Begin {год называется високосным, если его номер делится на 4, но если это год столетия, то номер столетия не делится на 4, то есть не делится на 400}

Leap: = (yy Mod 4 = 0) And ( yy Mod 400 <> 0);

End;

Function Dmonth (mm: month; yy: year): day; {функция определения количества дней данного месяца в данном году}

Begin

Case mm Of

1, 3, 5, 7, 10, 12 : Dmonth := 31;

4, 6, 9, 11 : Dmonth := 30;

If Leap (yy) Then Dmonth := 29

Else Dmonth := 28;

End;

End;

Procedure Tomorrow(td: data; Var nd: data); {процедура определения завтрашней даты}

Begin

If td.d<> Dmonth(td.m,td.y) {если это не последний день месяца}

Then With nd Do Begin

d := td.d + 1;

m := td.m;

y := td.y;

End {если это последний день месяца}

Else {если это декабрь}

If td.m = 12 Then

With nd Do Begin

d := 1;

m := 1;

y := td.y + 1;

End {если это не декабрь}

Else

With nd Do Begin

d := 1;

m := td.m + 1;

y := td.y;

End;

End;

Begin

Writeln('Введите сегодняшнее число,месяц и год');

Readln( dat.d,dat.m,dat.y);

Tomorrow(dat,next);

Writeln('Завтра будет ');

Writeln(next.d,'.',next.m,'.',next.y);

Readln;

End.

Решение задач

1. Написать программу, определяющую:

a. дату следующего (предыдущего) дня;

b. дату, которая наступит через mдней;

c. дату, которая была за m дней до сегодняшнего дня;

d. количество суток, прошедших от даты t1 до t2;

e. день недели, выпадающий на дату t1, если известно, что в первый день нашей эры был понедельник.

2. Дано время, описанное следующим образом:

Type time = Record

h : 0..23;

m, s : 0..59

End;

Описать:

a. логическую функцию для проверки, предшествует ли время t1 времени t2 (в рамках суток);

b. процедуру, присваивающую параметру t1 время, на 1 секунду большее времени t (учесть смену суток).

3. Const n = 300;

Type MyRecord = Record

Key : Integer;

Name : String;

End;

Var Table = Array[1..n] Of MyRecord;

Считая, что в таблице записи имеют различные ключи, описать:

a. процедуру, упорядочивающую записи таблицы по убыванию значений поля Key;

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

4. Дан массив, содержащий информацию об учениках некоторой школы.

a. Заполнить второй массив данными об учениках только девятых классов;

b. Выяснить, на сколько человек в восьмых классах больше, чем в девятых.

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

a. Найти багаж, средний вес одной вещи в котором отличается не более чем на 0,3 кг от общего среднего веса одной вещи;

b. Найти число пассажиров, имеющих более двух вещей и число пассажиров, количество вещей которых превосходит среднее число вещей;

c. Выяснить, имеется ли пассажир, багаж которого состоит из одной вещи весом менее 30 кг

1.4 Иерархические записи

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

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

Формально дерево ( tree ) определяется как конечное множество T одного или более узлов со следующими свойствами:

* Существует один выделенный узел, а именно - корень ( root ) данного дерева;

* Остальные узлы (за исключением корня) распределены среди m ?0 непересекающихся множеств T 1 , T 2 , …. T m , и каждое из этих множеств, в свою очередь, является деревом; деревья T 1 , T 2 , ... T m называются поддеревьями данного корня.

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

* Один узел является деревом. Этот же узел также является корнем этого дерева.

* Пусть n - это узел, а T 1 , T 2 , ... T m - деревья с корнями n 1 , n 2 , … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1 , n 2 , … n m . В этом дереве n будет корнем, а T 1 , T 2 , ... T m - поддеревьями этого корня. Узлы n 1 , n 2 , … n m называются сыновьями узла n .

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

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

Узел A является корнем, который имеет два поддерева { B } и { C , D , E , F , G }. Корнем дерева{ C , D , E , F , G } является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева { D }, { E }и { F , G }, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .

Путем из узла n 1 в узел n k называется последовательность узлов n 1 , n 2 , … n k , где для всех i , 1? i ? k , узел n i является родителем узла n i +1 . Длиной путиназывается число, на единицу меньшее числа узлов, составляющего этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. Например, на рисунке путем длины 2 будет путь от узла A к узлу F или от узла C к узлу G .

Если существует путь из узла a в узел b , то в этом случае узел a называется предком узла b , а узел b - потомком узла a . Отметим, что любой узел одновременно является предком и потомком самого себя. Например, на рисунке предками узла G будут сам узел G и узлы F , C и A . Потомками узла C будут являться сам узел C и узлы D , T , F , G . В дереве только корень не имеет предков, а листья не имеют потомков.

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

Высотой узла дерева называется длина самого длинного пути от этого узла до какого-либо листа. Глубина узла определяется как длина пути от корня до этого узла.

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

Порядок узлов

Если в определении дерева имеет значение порядок поддеревьев T 1 , T 2 , ... T m , то дерево является упорядоченным.

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

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

Обходы дерева

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

* Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;

* Если дерево T состоит из одного узла, то в список обхода записывается этот узел;

* Пусть дерево T имеет корень n и поддеревья T 1 , T 2 , ... T m , как показано на рисунке

Тогда для различных способов обхода имеем следующее:

* Прямой обход . Сначала посещается корень n , затем в прямом порядке узлы поддерева T 1 , далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m .

* Обратный обход . Сначала посещаются в обратном порядке все узлы поддерева T 1 , затем в обратном порядке узлы поддеревьев T 2 … T m , последним посещается корень n .

* Симметричный обход . Сначала в симметричном порядке посещаются все узлы поддерева T 1 , затем корень n , после чего в симметричном порядке все узлы поддеревьев T 2 … T m .

Рассмотрим пример всех способов обхода дерева, изображенного на рисунке:

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

1 2 3 5 8 9 6 10 4 7.

Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1.

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

2 1 8 5 9 3 10 6 7 4.

Помеченные деревья и деревья выражений

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

Рассмотрим пример дерева с метками, представляющее арифметическое выражение ( a + b )*( a + c ), где n 1 , n 2 , …, n 7 - имена узлов, а метки проставлены рядом с соответствующими узлами. Правила соответствия меток деревьев элементам выражений следующие:

* Метка каждого листа соответствует операнду и содержит его значение;

* Метка каждого внутреннего (родительского) узла соответствует оператору.

Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом обходе получим известную префиксную формузаписи выражения, где оператор предшествует обоим операндам. В нашем примере мы получим префиксное выражение вида: *+ ab + ac .

Обратный обход меток дерева дает постфиксное представление выражения (польскую запись). Обратный обход нашего дерева даст нам следующую запись выражения: ab + ac +*.

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

При симметричном обходе мы получим обычную инфиксную запись выражения: a + b * a + c . Правда для инфиксной записи выражений характерно заключение в скобки: ( a + b )*( a + c ).

Реализация деревьев

Пусть дерево T имеет узлы 1, 2, …., n . Возможно, самым простым представлением дерева T будет линейный массив A , где каждый элемент A [ i ] содержит номер родительского узла (является курсором на родителя). Поскольку корень дерева не имеет родителя, то его курсор будет равен 0.

Рассмотрим пример.

Для приведенного на рисунке дерева построим линейный массив по следующему правилу: A [ i ]= j , если узел j является родителем узла i , A [ i ]=0, если узел i является корнем. Тогда массив будет выглядеть следующим образом:

Другой важный и полезный способ представления деревьев состоит в формировании для каждого узла списка его сыновей. Рассмотрим этот способ для приведенного выше примера.

Двоичные деревья

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

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

Двоичные деревья нельзя непосредственно сопоставить с обычным деревом.

Обход двоичных деревьев в прямом и обратном порядке в точности соответствует таким же обходам обычных деревьев. При симметричном обходе двоичного дерева с корнем n левым поддеревом T 1 и правым поддеревом T 2 сначала проходится поддерево T 1 , затем корень n и далее поддерево T 2 .

Представление двоичных деревьев

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

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

Пример фрагмента программы дерева

Type

Tree=^s;

S=record

Inf: <тип хранимой информации>;

Left , right : tree ;

End ;

Изобразим схематично пример дерева, организованного в виде динамической структуры данных:

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

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

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

Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:

* Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:

- если ключи совпадают, поиск завершен;

- если ключ в корне больше искомого, выполнить поиск в левом поддереве;

- если ключ в корне меньше искомого, выполнить поиск в правом поддереве.

* Если дерево пусто, то искомый элемент не найден.

Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность: 1 6 8 10 20 21 25 30.

Можно организовать «зеркально симметричный» обход, начиная с правого поддерева, тогда получим упорядоченную по убыванию последовательность: 30 25 20 10 8 6 1.

Таким образом, деревья поиска можно применять для сортировки значений.

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

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

* Поиск по дереву;

* Обход дерева;

* Включение узла в дерево;

* Удаление узла из дерева.

1. Алгоритм поиска по дереву мы рассмотрели выше. Функция поиска :

Пример функции поиска

программирование алгоритм массив дерево

function find(root:tree; key:integer; var p, parent:tree):Boolean;

begin

p:=root;

while p<>nil do begin

if key=p^.inf then begin{ узел с таким ключом есть }

find:=true;

exit;

end;

parent:=p {запомнить указатель на предка}

if key<p^.inf then

p := p ^. left {спуститься влево}

else p := p ^. right ; {спуститься вправо}

end;

find:=false;

end;

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

Пример обхода дерева с помощью рекурсии

Procedure obhod(p:tree);

Begin

if p<>nil then

begin

obhod(p^.left);

writeln(p^.inf);

obhod(p^.right);

end;

end;

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

Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.

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

Сложнее всего случай, когда у удаляемого узла есть оба потомка.

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

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

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

Рассмотрим реализацию алгоритма удаления.

Пример программы удаления узла из дерева

procedure del ( var root : tree ; key : integer );

var

p : tree ; {удаляемый узел}

parent : tree ; {предок удаляемого узла}

y : tree ; {узел, заменяющий удаляемый}

function spusk(p:tree):tree;

var

y : tree ; {узел, заменяющий удаляемый}

pred:tree; { предок узла “y”}

begin

y:=p^.right;

if y^.left=nil then y^.left:=p^.left {1}

else {2}

begin

repeat

pred:=y; y:=y^.left;

until y^.left=nil;

y^.left:=p^.left; {3}

pred^.left:=y^.right; {4}

y^.right:=p^.right; {5}

end;

spusk:=y;

end;

begin

if not find(root, key, p, parent) then {6}

begin writeln(` такого элемента нет '); exit; end;

if p^.left=nil then y:=p^.right {7}

else

if p^.right=nil then y:=p^.left {8}

else y:=spusk(p); {9}

if p=root then root:=y {10}

else {11}

if key<parent^.inf then

parent^.left:=y

else parent^.right:=y;

dispose(p); {12}

end.

В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элементp и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .

В операторах {7}-{9} определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева ({7}).

Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева ({8}).

В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву ({9}).

В этой функции первым делом проверяется особый случай, описанный выше ({1}). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл ({2}), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).

В операторе {3} к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла ({5}), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый ({4}), поскольку этот узел перейдет на новое место.

Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень ({10}), иначе - присоединить этот указатель к соответствующему поддереву предка удаляемого узла ({11}).

После того как узел удален из дерева, освобождается занимаемая им память ({12}).

2. Специальная часть

2.1 Постановка задачи №1

Дан массив размера N. Найти количество его локальных минимумов 1 и максимумов 2.

2.1.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
Mas1	integer	array	-32768..+32767
n	integer	Размер массива	-32768..+32767
min	integer	Минимальное число	-32768..+32767
max	integer	Максимальное число	-32768..+32767
i	integer	Переменная для цикла	-32768..+32767



2.1.3 Листинг программы

program zadacha_144;

uses crt;

var mas1:array[1..99] of integer;

razm,i,max,min:integer;

begin

clrscr;

writeln(`введите размер массива');

readln(razm);

max:=0;

min:=100;

for i:=1 to razm do

begin

readln(mas1[i]);

if mas1[i]>max then max:=mas1[i];

if mas1[i]<min then min:=mas1[i];

end;

writeln('максимальное=',max);

writeln('минимальное=',min);

readkey;

end.

2.1.4 Контрольный пример

2.2 Постановка задачи №2

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

2.2.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
a	integer	array	-32768..+32767
f	boolian	Правда лож	1

2.2.2 Блок-схема



2.2.3 Листинг программы

program zadacha_147;

uses crt;

var count,i,n:integer;

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

f:boolean;

begin

count:=0;

writeln('vvedite razmer massuva');

readln(n);

for i:=1 to n do

readln(a[i]);

f:=false;

for i:=1 to n do begin

if a[i]<a[i+1] then f:=true;

if (a[i]>a[i+1]) and f then

begin

inc(count);

f:=false;

end;

end;

if a[n]>a[n-1] then inc(count);

writeln('kol vo uchastkov =',count);

readln;

end.

2.2.4 Контрольный пример

2.3 Постановка задачи № 3

Дана целочисленная матрица размера M x N. Вывести номер ее первой1|последней2 строки3|столбца4, содержащего максимальное количество одинаковых элементов.

2.3.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
Mas2	integer	array	-32768..+32767
N		Размер массива
Min		Минимальное число
Max		Максимальное число
i		Переменная для цикла
j		Переменная для цикла
str		Номер строки
stolb		Номер столбца
x		координата
y		координата
m		Размер массива



2.3.3 Листинг программы

program zadacha_183;

uses crt;

var mas2:array[1..99,1..99] of integer;

n,m,i,j,min,max,str,stolb,x,y:integer;

begin

clrscr;

writeln(`введите кол во строк массива');

readln(n);

writeln(`введите кол во столбцов массива');

readln(m);

x:=1;

y:=6;

for i:=1 to n do

begin

for j:=1 to m do

begin

gotoxy(x,y);

readln(mas2[i,j]);

x:=x+3;

end;

x:=1;

y:=y+2;

end;

for i:=1 to n do

begin

for j:=1 to m do

begin

if mas2[i,j]>max then begin

str:=i;

stolb:=j;

max:=mas2[i,j];

end;

end;

end;

writeln('максимальный элемент = ',max,'находится в ',str,' строке и в ',stolb,' столбце');

end.

2.3.4 Контрольный пример

2.4 Постановка задачи №4

Дано число k и матрица размера 4 x 10. Удалить строку1|столбец2 матрицы с номером k. Matrix26. Дана матрица размера 5 x 10. Удалить строку1|столбец2, содержащий минимальный3|максимальный4 элемент матрицы

2.4.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
A	integer	array	-32768..+32767
M	byte	Размер массива	0..255
N
J		Переменная для цикла
i		Переменная для цикла
k		Переменная для цикла while
w		Переменная для case

2.4.2 Блок схема

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

2.4.3 Листинг программы

program zadacha_195;

uses crt;

var a:array[1..4,1..10] of integer;

m,n,i,j,k,w:byte;

begin

clrscr;

randomize;

m:=4;

n:=10;

writeln('Исходная матрица:');

for i:=1 to m do

begin

for j:=1 to n do

begin

a[i,j]:=random(20);

write(a[i,j]:4);

end;

writeln;

end;

writeln;

repeat

writeln('Выберите действие 1-удалить строку 2-удалить столбец');

readln(w);

until w in [1,2];

case w of

1:begin

repeat

write('Введите номер строки для удаления от 1 до ',m,' k=');

readln(k);

until k in [1..m];

if k< >m then

begin

for i:=k to m-1 do

for j:=1 to n do

a[i,j]:=a[i+1,j];

m:=m-1;

writeln('Строка номер ',k,' удалена');

end;

else m:=m-1;

end;

2:begin

repeat

write('Введите номер столбца для удаления от 1 до ',n,' k=');

readln(k);

until k in [1..n];

if k< >n then begin

for j:=k to n-1 do

for i:=1 to m do

a[i,j]:=a[i,j+1];

n:=n-1;

writeln('Столбец номер ',k,' удален');

end;

else n:=n-1;

end;

end;

for i:=1 to m do

begin

for j:=1 to n do

write(a[i,j]:4);

writeln

end;

readln

end.

2.4.4 Контрольный пример

2.5 Постановка задачи №5

Дана строка S и число N. Преобразовать строку S в строку длины N следующим образом: если длина строки S больше N, то отбросить первые символы, если длина строки S меньше N, то в ее начало добавить символы "." (точка).

2.5.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
s	String	Переменная для строки	-32768..+32767
n	Integer	Номер буквы	-32768..+32767
i	integer	Переменная для цикла	-32768..+32767

2.5.2 Блок схема

2.5.3 Листинг программы

program zadacha_214;

uses crt;

var s: string;

n, i: integer;

begin

write ('s=');

readln (s);

write ('n=');

readln (n);

if length(s)>n then delete (s,1,(length(s)-n)) else

for i:=length(s) to n-1 do

s:=s+'.';

writeln (s);

end.

2.5.4 Контрольный пример

2.6 Постановка задачи №5

Дана строка, состоящая из русских слов, разделенных пробелами (одним или несколькими). Определить длину самого короткого1|длинного2 слова.

2.6.1 Таблица идентификаторов

Идентификатор	Тип	Назначение	Размер
s	string	строка
sd	integer	Для вывода на экран	-32768..+32767
sk	integer	Для вывода на экран	-32768..+32767
S1	string	строка
i	integer	Переменная для цикла	-32768..+32767
d	integer	Переменная для if	-32768..+32767

2.6.2 Блок-схема



2.6.3 Листинг программы

program zadacha_226;

uses crt;

var sd,sk,d,i:integer;

s,s1:string;

BEGIN

clrscr;

writeln('Vvedite striky!');

readln(s);

sd:=0;

sk:=length(s);

s1:='';

for i:=1 to Length(s) do

if (s[i]=' ')or(i=length(s))then

begin

if s1<>''then

begin

d:=length(s1);

if d>sd then sd:=d;

if d<sk then sk:=d;

s1:='';

end;

end else s1:=s1+s[i];

writeln('Dlina samogo bolshogo slova: ',sd);

writeln('Dlina samogo malenkogo slova: ',sk);

readln;

END.

2.6.4 Контрольный пример

Заключение

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

Список литературы

1.Turbo Pascal 7.0(Фаронов.В.В)

Размещено на Allbest.ru