для телефона

t:Boolean;

Begin

Write( 'Введите первую дату (день, месяц)'); Readln(d1, m1);

Write( 'Введите вторую дату (день, месяц)'); Readln(d2, m2);

t:=(m1<m2) Or ((m1=m2) And(d1<d2)); Writeln(t);

End.

Перечисляемый тип данных. Этот тип данных получил название перечисляемого, потому что он задаётся в виде перечисления некоторых значений. Эти значения образуют упорядоченное множество и являются константами этого типа. Для объявления переменной список возможных значений, разделённых запятой, указывается в круглых скобках. Например,Var month: (january, february, marth, april, may, june, jule, august, september, october, november, december); Упорядоченность элементов перечисляемого типа определяется порядком их следования. Самый левый имеет минимальное значение (значение функции ord для него равно 0), а наиболее правый - максимальное.

Типы данных, вводимые пользователем Тип данных определяет:

-внутреннее представление данных в памяти компьютера;

-множество значений, которые могут принимать величины этого типа;

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

Основные типы данных

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

int (целый);

char (символьный);

wchar_t (расширенный символьный); bool (логический);

float (вещественный);

double (вещественный с двойной точностью).

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

short (короткий); long (длинный); signed (знаковый);unsigned (беззнаковый).

Символьный тип (char).

Под величину символьного типа отводится количество байт, достаточное для размещения десятичного кода любого символа из набора символов для данного компьютера, что и обусловило название типа. Как правило, это 1 байт. Тип char, как и другие целые типы, может быть со знаком или без знака. В величинах со знаком можно хранить значения в диапазоне от -128 до 127. При использовании спецификатора unsigned значения могут находиться в пределах от 0 до 255. Этого достаточно для хранения любого символа из 256-символьного набора ASCII. Величины типа char применяются также для хранения целых чисел, не превышающих границы указанных диапазонов.

Логический тип (bool).

Величины логического типа могут принимать только значения true и false, являющиеся зарезервированными словами. Внутренняя форма представления значения false – 0 (нуль). Любое другое значение интерпретируется как true. При преобразовании к целому типу true имеет значение 1.

Вещественный тип (float, double и long double).

Стандарт C++ определяет три типа данных для хранения вещественных значений: float, double и long double.

Вещественные типы данных хранятся в памяти компьютера иначе, чем целочисленные. Внутреннее представление вещественного числа состоит из двух частей – мантиссы и порядка. В IBM PC-совместимых компьютерах величины типа float занимают 4 байта, из которых один двоичный разряд отводится под знак мантиссы, 8 разрядов под порядок и 23 под мантиссу.

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

Спецификатор long перед именем типа doublе указывает, что под величину отводится 10 байт.

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

FLT_MIN…FLT_MAX – диапазон типа float,

DBL_MIN…DBL_MAX – диапазон типа double,

LDBL_MIN…LDBL_MAX – диапазон типа long double.

Эти константы находятся в библиотеке <float.h> и следует убедиться, что она подключена.

Константы с плавающей точкой имеют по умолчанию тип double. Можно явно указать тип константы с помощью суффиксов F, f (float) и L, 1 (long). Например, константа 2E+6L будет иметь тип long doublе, а константа 1.82f – тип float.

В стандарте ANSI диапазоны значений для основных типов не задаются, определяются только соотношения между их размерами, например:

sizeof(float) < sizeof(double) < sizeof(long double) sizeof(char) < sizeof(short) < sizeof(int) <, sizeof(long)

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

17 Структурированные ТД

Чаще всего, из структурированных типов данных встречается массив.

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

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

Определяя массив в языке BASIC, пишем служебное слово dim, после которого указываем имя массива. Тип элементов указывается значком %, !, #, $. Размерность определяет количество чисел в скобках. Сами числа – это наибольшее значение индекса. Начальное значение индекса – 0. Наибольшая размерность массивов – 2. По умолчанию, элементы массива – действительные числа.Следует отметить, что если массив одномерный и в нем не больше 10 элементов, то его объявление не обязательно. То есть использование команды DIM не требуется.

BASIC

dim <имя><тип элементов>(<дополнительная информация>)

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

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

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

PASCAL

<имя>:array[<дополнительная информация>] of <тип элементов> Ввод и вывод массивов обычно происходит поэлементно.

Основные операции – это обращение по индексам для запоминания или считывания значений элементов.

Вязыке Pascal можно выполнять оператор присваивания с массивами и задать константу-массив.

Обобщения массива.

Существует возможность хранить и обрабатывать упорядоченные данные разного типа.

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

Взаписях требует уточнений: количество и тип полей.

Как это оформляется в языке pascal показано ниже. Структурированные типы данных - запись

PASCAL <имя записи>:record

<имя поля>:<тип поля>; <имя поля>:<тип поля>;

...

end;

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

Основной операцией при работе с записями является обращение по именам к значениям полей для запоминания или считывания.При оформлении, после имени самой записи ставится точка, затем имя поля.PASCAL <имя записи>.<имя поля>Элементы записи могут быть любого типа (кроме файлового), в том числе и массивы, и другие записи.Оформление в языке программирования PASCAL: Пусть имеем перечислимый тип t1.

Тогда <имя типа> = set of t1; определяет множество.

* Способ образования.Элементы нового типа - группы выбранных элементов (в том числе и пустое множество) типа t1..Операции над множествами в языке

PASCAL
пересечение множеств a и b	a*b
объединение множеств a и b	a+b

разность множеств a и b a-b

Для множеств возможны:

Проверка на равенство множеств a и b a=b Проверка на неравенство множеств a и b a<>b

Проверка, является ли a подмножеством от b a<=b , b>=a Проверка на принадлежность элемента e множеству a e in a Все проверки дают результат логического типа.

18) Динамические ТД

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

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (NIL).Чтобы список существовал, надо определить указатель на его начало. Опишем переменные:

Var и, х: EXS;

Создадим первый элемент:

New(u); {выделим место в памяти для переменной типа S}

u^.next:=nil;	{указатель пуст} и^.data:=3; {информационное поле
первого элемента}

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

х:=и; {Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом.}

New(x^.Next)•,{выделим область памяти для следующего элемента списка} x:=x^.Next; {переменная х принимает значение адреса выделенной области памяти}

x^.Data:=5; {определим значение этого элемента списка} x^.Next.=Nil:

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

Procedure Init(Var u: Exs); {создание списка}

Var х, у: Exs; Digit: Integer; {значение информационной части элемента списка} Begin

Writeln('Введите список '); u:=Nil; {список пуст} WriteLn('Bводите элементы списка. Конец ввода 0);

Read(Digit); While Digit<>0 Do Begin

New(y); {формирование элемента списка} y^.Nexf:=Nil; y^.Data:=Digit; If u=nil Then u:=y {вставляем первый элемент списка}

Else x^.Next:=y; {вставляем элемент в конец списка}

х:=у; {переносим значение указателя на последний элемент списка} Read(Digit);

End;

Writein;

End;

Итак, мы построили список добавлением элементов в конец списка. Вставим элемент со значением 7 в начало списка.

Удаление элемента из начала списка

Напишем фрагмент программы:

х:=и; {запомним адрес первого элемента списка} u:=u^.next; {теперь и указывает на второй элемент списка} Dispose(x); {освободим память, занятую переменной х^} Удаление элемента из середины списка

Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним. х:=и; {переменная х для хранения адреса удаляемого элемента} {найдем адреса нужных элементов списка }

While (x<>Nil) And (x^.Data<>Digit) Do Begin dx:=x; x:=x^.Next End; dx^.Next:=x^.Next; Dispose(x);

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

{найдем предпоследний элемент} х:=и; ах:=и; While x^.Next<>NIL Do Begin dx:=x; x:=x^.Next; End;

{удаляем элемент х^ из списка и освобождаем занимаемую им память} dx^.Next:= Nil; Dispose(x);

Стек

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

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

Основные операции со стеками Как было сказано выше, стек является динамической структурой, размеры

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

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

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

Таким образом, описать стек можно следующим образом:

Type EXST=^ST;

ST=Record Data: Integer; Next: EXST; End; Var Stack: EXST; {текущая переменная}

Тогда, если стек пуст, то значением указателя равно NIL. Занесение в стек

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

Занесение в стек производится аналогично вставке нового элемента в начало списка:

Procedure WriteStack (Var ir.EXST; digit: Integer); {запись в стек} Var x:.EXST;

Begin

New(x); {создание нового элемента стека} x^.Data:=diglt; х^.Nехt:=u

{созданный элемент определить как вершину стека} u:=х;

End;

Основная программа формирования стека будет иметь вид:

Var Stack: EXST; {текущая переменная} digit: Integer;

Begin

Stack:=Nil;

WriteLn(1'Введите элементы стека. Окончание ввода — О'); Read(Digit); While Digit<>O Do Begin WriteStack(Stack, digit); Read(digit); End

End.

Извлечение элемента из стека.

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

Procedure ReadStack(Var u-.EXST; Var i-.Integer); Var x: EXST;

Begin

i:u^.Data; x:=u; u:=u^.Next; Dlspose(x);

End;

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека. function Free(u:EXST):Boolean;

Очереди

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

Очередь является динамической структурой — с течением времени изменяется и ее длина, и набор составляющих ее элементов. Поэтому удобно представить ее в виде списка.

Описание очереди на языке программирования:

Type ЕХО=^О; O=Record Data: Integer; Next: EXO; End;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

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

Var xl, х2: EXO;

где xl — соответствует началу очереди и будет использоваться для вывода элемента из очереди, х2 — соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.

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

Procedure WriteO (Var xl,x2: EXO; с: Integer); Varи: EXO;

Begin

New(u); u^.data:=c; u^.nexf:=^NIL;

If xl=NIL Then xl:=u {если очередь пуста}

Else x2^.next:=u; {заносим элемент в конец списка} х2:=u;

End;

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

Begin

xl:=NIL; x2:=NIL;

Write Ln('Введите элементы очереди. Конец ввода — О'); Read(Digit); While Digit<>O Do Begin WriteO(xl,x2,Digit); Read(Digit); End

End.

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

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

Procedure Reado(Var xl,x2:EXO; Var c:Integer); Var u:ЕХО; Function Nul (xl: ЕХО): Boolean; Begin Nul:=(xl=Nil); End;

Begin

If Nul(xl) Then Writeln(‘0чepeдь пуста') Else

Begin c:=xl^.Data; u:=xl; xl:=xl^.Next; Dispose(u); End;

End;

Деревья

Введение основных понятий Граф — это непустое множество точек (вершин) и множество отрезков (ребер),

концы которых принадлежат заданному множеству точек.

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