Перечислимый и ограниченный типы данных

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

Var month: (january, february, marth, april, may, june, jule, august, september, october, november, december);

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

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

Например,Var a: 1..25; ch: 'a'..'z';

Здесь переменные а и ch могут принимать значения только из указанного интервала; базовым типом для переменой а является целый тип, а для переменной ch – символьный.Переменная ограниченного типа сохраняет все свойства переменных базового типа.Для чего вводится ограниченный тип данных? Использование ограниченного типа делает программу наиболее понятной и наглядной. Например, если в программе переменная b может принимать только значения 3, 4, 5, 6, 7, 8, то лучше описать её следующим образом: Var b: 3..8;, чем Var b: Integer; так как в случае выхода значения b за диапазон 3..8 в первом случае будет выдано диагностическое сообщение, которое поможет найти ошибку. Во втором случае будет получен неправильный результат, что затруднит поиск ошибки. Таким образом, второй вариант описания переменной следует использовать в тех случаях, когда диапазон значений заранее неизвестен либо занимает весь допустимый интервал значений для рассматриваемого типа.

Основные (стандартные) типы данных часто называют арифметическими, поскольку их можно использовать в арифметических операциях. Для описания основных типов определены следующие ключевые слова:
int (целый);
char (символьный);
wchar_t (расширенный символьный);
bool (логический);
float (вещественный);
double (вещественный с двойной точностью).
Первые четыре типа называют целочисленными (целыми), последние два – типами с плавающей точкой. Код, который формирует компилятор для обработки целых величин, отличается от кода для величин с плавающей точкой.
Существует четыре спецификатора типа, уточняющих внутреннее представление и диапазон значений стандартных типов:
short (короткий);
long (длинный);
signed (знаковый);
unsigned (беззнаковый).

8)«Основные (базовые) типы данных» Понятие типа данных Напомним о понятии «переменная».В алгоритмических языках под переменной понимают область памяти, где хранятся обрабатываемые данные. (Исходные, промежуточные и итоговые.). Название происходит от того, что при работе ЭВМ данные могут менять свои значения.Область памяти характеризуется размером и адресом начала. Чтобы разные переменные человеку легче было отличать друг от друга, им даются имена (идентификаторы). (Компьютер отличает переменные друг от друга по их началу в памяти.) Информацию, хранящуюся в переменной в момент обращения к этой переменной называют ЗНАЧЕНИЕМ переменной. адрес начала и размер в памяти | | | +--+- память -+----------+ | | | | ПЕРЕМЕННАЯ | | / \ | +- имя значение – тип (возможный диапазон значений) В переменных хранятся разные данные, разные по размеру и назначению. Компьютер работает и с числами, и с буквами, и с картинками. Выполняемые над разными объектами действия должны быть различны. Для обеспечения принципа детерминированности (компьютер должен знать, что можно делать с разными данными), все данные разбиты на группы, с данными одной группы можно выполнять определенный набор действий. Заодно, договорились, что и размер места в памяти данных одного типа одинаков. Описанные группы данных называют данными одного типа. Типы данных так же имеют имена. Будем изучать все типы данных по одной схеме: 1) имя типа 2) размер в памяти (кодирование) 3) набор операций 4) связь с данными других типов К простейшим (базовым) типам данных относят такие, для которых достаточно только имени, чтобы компьютер понял, сколько места выделить в памяти для их хранения и какие операции с ними можно выполнять. *** Классификация типов данных * Сложные (структурные) типы данных. Данные этих типов, как и данные базовых типов, занимают в памяти фиксированную область. Фактически, являются совокупностью данных базового или самого структурного (кроме файлов) типа. Идентификатор заложен в транслятор (массив, запись, множество, файл). Кодирование требует уточнений. Набор внутритиповых операций связан с обращением к данным. Набор операций связи с данными других типов связан с кодированием. * Динамические типы данных. Область памяти, где хранятся данные этих типов, может изменять со временем свои размеры. В современных языках программирования специальных средств не имеют. Идентификатор определяется программистом. Кодирование определяется программистом. Набор внутритиповых операций определяется программистом. Набор операций связи с данными других типов определяется программистом. ***** БАЗОВЫЕ ТИПЫ ДАННЫХ 1 Базовые (простые) типы данных (базовые способы хранения информации). Для работы с данными этих типов не требуется никаких уточнений, достаточно только указать тип. Идентификатор, кодирование и набор операций заложены в транслятор. Есть возможность увеличения набора операций (функции пользователя). 3 Получение информации базовых типов происходит специальным оператором присваивания, из константы или чтением с клавиатуры (или из файла). Вывод данных базовых типов организуется единой стандартной командой.   10)Базовый тип данных - целое число. (Имена типов приводятся согласно ЯП Паскаль) Компьютер предназначен прежде всего, для работы с числами. Выделяют несколько типов целых чисел. Целые натуральные (без знака) и целые со знаком. Кроме того, целые числа занимают разное количество байт. Для числа без знака используется двоичная запись в выделенное место памяти. Поскольку счет идет с 0, то: для одного байта диапазон [0..255] (byte) {=2^8-1}; для двух байт - [0..65535] (unsign) {=2^16-1}; для четырех байт - [0..4294967295] {=2^32-1} Для числа со знаком самый старший бит выделен для знака 0 - число положительное, 1 - отрицательное. В целом, отрицательное число образуется из положительного за два шага: 1) в двоичной записи числа обратим цифры "1" в цифры "0" и наоборот, 2) к полученному числу добавим 1 (действие выполняем в двоичной системе счисления).Очевидно появление цифры "1" на первом месте, если там был "0". Такое кодирование решает три задачи: 1) образование положительного числа из отрицательного выполняется теми же двумя операциями (убедитесь сами!) 2) числа "+0" и "-0" представляются одинаково. 3) кодирование самообратимо { k(k(x))=x } 00000101 - число 5 в 1 байте 00000101 - исходное 11111010 - после инверсии 11111011 - после добавления 1 11111011 - число -5 в 1 байте 11111011 - исходное 00000100 - после инверсии 00000101 - после добавления 1 Описанный способ представления отрицательных чисел называется «дополнительное кодирование». Дополнение до 1, которая при сложении числа А с числом –А уйдет за пределы выделенной области, останется 0. Прежде встречались:- прямое кодирование – просто у отрицательных чисел вписывалась 1 в старший бит. Тое есть число 0 можно было писать 00000000 и 10000000 (+0 и -0!!!) - обратное кодирование – у числа 0 менялись на 1, а 1 на 0. Тоже в наличии значения +0 и -0 соответственно 00000000 и 11111111 В зависимости от выделяемой памяти имеются: для одного байта диапазон [-128..+127] (shortint) для двух байт - [-32768..+32767] (integer) для четырех байт - [-2147483648..+2147483647] (longint) В языке PASCAL имя типа диапазон значений byte 1 байт, без знака, 0..255 word 1 байт, без знака, 0..65535 shortint 1 байт, со знаком, -128..+127 integer 2 байт, со знаком, -32768..+32767 longint 4 байт, со знаком, -2147483648..+2147483647 Способ кодирования – двоичное представление и дополнительный код для отрицательных чисел. Основные операции. BASIC PASCAL сложение a и b a+b a+b вычитание a и b a-b a-b умножение a на b a*b a*b Делить целые числа нельзя! – Результат – не целое число. деление нацело a на b a\b a div b остаток от деления a на b a mod b a mod b взятие модуля a abs(a) abs(a) логические И от a и b a and b a and b ИЛИ от a и b a or b a or b отрицание a not a not a Связь с данными других типов. В языке pascal различают 5 типов целочисленных данных, связь между ними автоматическая, то есть аргументы операций приводятся к одному типу, выполняется операция. Попытка сохранения результата в другом типе, например word как integer, может привести к ошибкам. Числа, большие чем 32767, будут показаны как отрицательные.Пока другие типы не изучались, связь целочисленных типов с ними рассматривать не будем. В языке basic программу можно написать не обращая внимания на типы. Имеющийся целочисленный тип соответствует паскалевскому типу integer, обозначается наличием знака % в конце имени переменной. 3) Способы записи алгоритмов Алгоритм – точная конечная последовательность команд, приводящая от исходных данных к искомому результату за конечное число шагов Способы (формы) записи алгоритмов Словесно-пошаговый, алгоритмический язык, блок-схема, структурограмма. Словесно-пошаговый способ записи алгоритмовОписывает алгоритм на естественном языке, задавая шаги в виде последовательных пунктов. Не смотря на простоту этого способа, он имеет множество недостатков: отсутствие строгой формализации, толкование шагов не всегда однозначно, описание чрезмерно многословно. Классическим примером словесно-пошагового алгоритма являются рецепты приготовления блюд. Графический способ описания алгоритмов:Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Достоинство блок схем – наглядность и простота записи алгоритма. Каждому действию алгоритма соответствует геометрическая фигура В линейном алгоритме команды выполняются последовательно,блок-схема будет иметь вид: Т.к. в разветвляющемся алгоритме порядок следования команд может быть разный,блок-схема примет вид: В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид: Структурограммы: дают полное визуальное представление деталей логических операций над группами операторов программы. Структурограмма (схема Насси–Шнейдермана) – это схема, иллюстрирующая структуру передачи управления внутри модуля с помощью вложенных друг в друга блоков. Каждый блок имеет форму прямоугольника и может быть вписан в любой внутренний прямоугольник любого другого блока. Запись внутри блока производится на естественном языке или с помощью математических обозначений. Символ «Обработка» содержит описание действий, выполняемых оператором или группой операторов. В подобном символе можно помещать операторы присваивания, ввода/вывода и т. д. Управление передается в прямоугольник сверху, а выходит из него снизу. Символ «Cледование» объединяет ряд следующих друг за другом процессов обработки. В отдельные прямоугольники записываются логически завершенные шаги программы. Управление начинает свой путь на внешней стороне верхнего прямоугольника, проходит через каждый прямоугольник и завершает путь на внешней стороне нижнего прямоугольника. Символ «Решение» применяется для обозначения конструкций IF-THEN-ELSE. Условие (вопрос) располагается в верхнем треугольнике, варианты ответов – по его сторонам, а процессы обработки обозначаются прямоугольниками. В результате принятия решения управление передается в один из нижних прямоугольников: Для усеченной конструкции разветвления IF-THEN прямоугольник, соответствующий ветви невыполнения условия – НЕТ, следует оставить пустым. Символ CASE представляет расширение блока решение. Условие, называемое селектором выбора, записывается в верхнем треугольнике. Варианты выхода из треугольника, соответствующие точно определенным значениям селектора, размещаются в маленьких треугольниках по его левой стороне. Каждому варианту соответствует свой символ обработки. По правой стороне треугольника размещается выход по несовпадению условий и соответствующий ему альтернативный символ обработки. Символ «Цикл» служит для обозначения конструкций WHILE-DO и REPEAT-UNTIL. Изображенный внутренним прямоугольником процесс повторяется некоторое число раз либо пока выполняется некоторое условие (WHILE), либо до тex пор пока не выполнится некоторое условие (UNTIL). Затем управление выходит из нижней стороны внешнего прямоугольника. Условие окончания цикла размещается в верхней полосе внешнего прямоугольника для цикла WHILE-DO и в нижней полосе – для цикла REPEAT-UNTIL. Горизонтальная линия внутри символа показывает место проверки условия завершения цикла – в его начале для цикла WHILE-DO и в его конце для цикла REPEAT-UNTIL.ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКАДостаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Под исполнителем в алгоритмическом языке может подразумеваться не только компьютер, но и устройство для работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно предназначена компьютеру. Как и каждый язык, алгоритмический язык имеет свой словарь. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной.При построении новых алгоритмов могут использоваться алгоритмы, составленные ранее. Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными алгоритмами. Вспомогательным может оказаться любой алгоритм из числа ранее составленных. Не исключается также, что вспомогательным в определенной ситуации может оказаться алгоритм, сам содержащий ссылку на вспомогательные алгоритмы.Очень часто при составлении алгоритмов возникает необходимость использования в качестве вспомогательного одного и того же алгоритма, который к тому же может быть весьма сложным и громоздким. Было бы нерационально, начиная работу, каждый раз заново составлять и запоминать такой алгоритм для его последующего использования. Поэтому в практике широко используют, так называемые, встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обращение к таким алгоритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. У исполнителя-робота встроенным вспомогательным алгоритмом может быть перемещение в склад из любой точки рабочего поля; у исполнителя-язык программирования Бейсик это, например, встроенный алгоритм «SIN».Алгоритм может содержать обращение к самому себе как вспомогательному и в этом случае его называют рекурсивным. Если команда обращения алгоритма к самому себе находится в самом алгоритме, то такую рекурсию называют прямой. Возможны случаи, когда рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение. Такая рекурсия называется косвеннойАлгоритмы, при исполнении которых порядок следования команд определяется в зависимости от результатов проверки некоторых условий, называют разветвляющимися. Для их описания в алгоритмическом языке используют специальную составную команду - команда ветвления. Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную формуАлгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла. 14. *** Работа с файлами. 1 Определение. Файл - информация, подготовленная для хранения во внешней памяти или к использованию на внешних устройствах (ВУ). Частным случаем файла является ТЕКСТ (TEXT) Текст - файлы последовательного доступа (чтение и запись данных начинаются всегда от начала файла) В файлах могут храниться как данные, так и команды (программы) Различают файлы программы: - хранящие текст программы на языке высокого уровня - хранящие исполняемый код для прцессора файлы данных: - последовательного доступа (чтение и запись данных начинаются всегда от начала файла) - прямого доступа (чтение и запись данных возможны для любого места) 2 Способы представления (хранения). Для различия между собой, файлы имеют имена. Имена имеют и ВУ: CON, KBD, CRT, PRN, LPT1,...LPT3, COM1, COM2 (ДОС); GRP (MSX-basic); SCRN, KYBD (GWbasic) Стандартными внешними устройствами являются клавиатура и дисплей. Используя при передаче файловой информации вместо имен файлов имена устройств, получают ввод информации с указаных устройств или вывод информации на нестандартные устройства. Поэтому имена устройств нельзя давать файлам. Полное имя файла состоит из трех частей: адресная - <имя устройства памяти>:[/<имена подкаталогов через />] именная - <имя файла до 8 знаков> расширение имени файла - <три знака> При написании, между именем файла и расширением ставится точка. При работе с текущим устройством адресная часть полного имени файла может быть пропущена (берется "по умолчанию"), важными являются только имя и расширение, которые обычно называют именем файла. ТЕКСТ - набор данных, имеющий вид упакованных строк, закачивается специальным знаком "конец файла" <26>. Файлы - программы, доступные процессору, т.е. могут сразу исполнены, имеют расширения.COM или.EXE. Имена таких файлов служат командами исполнения содержимого для операционной системы. Операционная система (ОС) - специальная программа, автоматически запускаемая при включении компьютера, основным назначением которой является поиск и исполнение файлов-программ. Файлы - программы на языке "Pascal" - содержат текст программы, являются строками. Могут быть созданы с помощью любого текстового редактора. С помощью программы-транслятора могут быть преобразованы в файлы, исполняемые процессором. Обычно специальный редактор объединяют с транслятором, куда добавляются средства контроля программ и систему подсказок (Help) - получается система программирования. Результат работы такой системы, записанный в виде.COM или.EXE - файла, в дальнейшем, присутствия системы программирования не требует. По стандарту языка "BASIC", для выполнения программ обязательно требуется присутствие BASIC-системы. При работе которой оператор находится в среде специального редактора. Набираемые команды могут быть выполнены немедленно, или, если имеют метку - номер, запомнены в оперативной памяти. Команды оперативной памяти могут быть просмотрены командой "LIST" или исполнены командой "RUN" Из оперативной памяти программа может быть перенесена во внешнюю командой SAVE"<ИМЯ ФАЙЛА>"[,A] Запись присходит в более коротком кодированном варианте или (при наличии флажка - буквы "A" в команде) в полном варианте, пригодном для просмотра и печати средствами ДОС. Командой восстановления программы в оперативную память из файла является LOAD"<ИМЯ ФАЙЛА>"[,R] Флаг 'R' служит для немедленного запуска программы после "загрузки". Загрузить в оперативную память и сразу исполнить программу можно командой RUN"<ИМЯ ФАЙЛА>" Обычно, файл - программа на языке "BASIC" имеет расширение.BAS. Запись/загрузка подпрограмм в кодах проводится командами BSAVE"<имя>" BLOAD"<имя>" При работе с кассетным магнитофоном в качестве ВУ, используют команды CSAVE"<имя>" CLOAD"<имя>" Есть возможность объединения двух текстов - программ в один. Для этого один текст должен быть в оперативной памяти, а другой, заранее подготовленный, должен быть записан в файл в полном варианте. Команда MERGE"<имя подготовленного файла>" создаст в оперативной памяти совместный текст обеих программ. Если в склеиваемых текстах были строки с одинаковами номерами, то останется только строка подготовленного файла. Итак, на примере работы с файлами-программами на языке "BASIC", имеем три вида работы с файлами - создание (SAVE), чтение (LOAD) и добавление (MERGE). Для работы с файлами данных в языке BASIC, в начале программы должно быть указано число одновременно открытых файлов MAXFILES=<N>, по умолчанию, это число =1. Каналы связи программы с файлом нумеруются, номера используются в командах. В файлах могут быть только данные базовых типов. В языке PASCAL вместо номеров каналов связи вводятся переменные файлового типа, которые описываются как :file of <тип элементов>; или:text; Элементы файлов могут быть любых типов, кроме файлового. Слово "text" указывает на файл строк произвольной длины. * Способ образования (хранения). <цифры приведены для ЭВМ "Yamaha"> В памяти компьютера, для каждого файла, выделяется буфер <256 байт> При создании файла последовательного доступа, заполняется не файл, а буфер. По заполнении буфера, все его содержимое копируется во внешне устройство (файл), буфер очищается и готов заполняться снова. При чтении, часть содержимого файла, копируется в буфер, откуда читается программой. По мере необходимости, в буфер считываются очередные порции информации. При работе файлов прямого доступа, команды смены содержимого буфера приходится программировать. Для работы буфера используются служебная информация - блок управления файлом (File Control Blok - FCB) <9 байт> * Для работы с текстами обычно используют специальный редактор. Для работы с файлами данных в языке BASIC, в начале программы должно быть указано число одновременно открытых файлов MAXFILES=<N>, по умолчанию, это число =1. Каналы связи программы с файлом нумеруются, номера используются в командах. В языке PASCAL вместо номеров каналов связи вводятся переменные файлового типа, которые описываются как:text; 3 Основные операции. С файлами проделывают две операции: открывают с какой-то целью и закрывают. (file - папка (англ)). Существуют три цели открытия файла - для занасения в него данных (заново) - для добавления в него данных (в конец) - для извлечения из него информации. BASIC PASCAL открыть open "<имя>" for output as#1 rewrite(f) для записи open "<имя>" for input as#1 reset(f) для чтения open "<имя>" for append as#1 append(f) для добавления close(#1) close(f) закрыть После открытия файла стандартные команды получения и вывода информации,при наличии указания на номер или имя канала связи, работают с файлом: PRINT #1, A;B WRITE(f,A,B); WRITELN(f,A,B); INPUT #1, X,Y READ(f,X,Y); READLN(f,X,Y); В языке PASCAL файловая переменная перед использованием связывается с именим файла - строкой знаков специальной командой ASSIGN(f,<имя>); 4 Связь с данными других типов. Элементом текста является строка. Возможны файлы данных любого вообразимого типа. В файле могут быть несколько данных одного типа.Файлы программ считаются двоичными. В них хранятся байты кодов команд процессора (в двоичной форме). 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^.NextEnd; dx^.Next:=x^.Next; Dispose(x); Удаление элемента из конца списка Оно производится, когда указатель ах показывает на предпоследний элемент списка, а х — на последний. {найдем предпоследний элемент} х:=и; ах:=и; While x^.Next<>NIL DoBegin 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(¹'Введите элементы стека. Окончание ввода — О'); Read(Digit); While Digit<>O Do BeginWriteStack(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=RecordData: 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 BeginWriteO(xl,x2,Digit); Read(Digit); End End. Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка. Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди. Procedure Reado(Var xl,x2:EXO; Var c:Integer); Var u:ЕХО; Function Nul (xl: ЕХО): Boolean; BeginNul:=(xl=Nil); End; Begin If Nul(xl) Then Writeln(‘0чepeдь пуста') Else Beginc:=xl^.Data; u:=xl; xl:=xl^.Next; Dispose(u); End; End; Деревья Введение основных понятий Граф — это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек. Если на каждом ребре задать направление, то граф будет ориентированный. Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем. Замкнутый путь, состоящий из различных ребер, называется циклом.Граф называется связным, если любые две его вершины соединены путём. Связный граф без циклов называется деревом. На рис. 54 изображено дерево, в узлах которого располагаются символы. Примечание. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями. Для дальнейшей работы с деревьями необходимо определить ряд понятий. • Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у. • Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной. • Количество непосредственных потомков внутренней вершины называется ее степенью. • Степенью дерева называется максимальная степень всех вершин. Например: • вершины F, D, Е являются непосредственными потомками вершины В; • вершины F, D, Е являются листьями; • вершиныС, G, Н — внутренние; • степень вершины В — 3, а вершины Н — 1; • степень дерева равна 3. Двоичное дерево — это дерево, в котором из каждой вершины исходит не более двух ребер. 6.2. Представление деревьев Дерево — это сложная динамическая структура данных, применяющаяся для эффективного хранения информации. Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой — сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два - левое и правое. Type TreeLink =^Tree; Tree=Record Data: <mun данных>; Left, Right: TreeLink; End; Корень дерева опишем в разделе описания переменных: Var kd: TreeLink; 6.3. Основные операции над деревом К основным операциям над деревьями относятся: • занесение элемента в дерево; • обход дерева; • удаление элемента из дерева. Рассмотрим вставку и обход дерева на примере следующей задачи. 6.5. Удаление из дерева Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной (рис. 55) или из нее выходит только одно ребро (рис. 56). Для этого нужно изменить соответствующую ссылку у предшествующей вершины. Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины (рис. 57).Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая: • удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка); • удаляемая вершина имеет не более одного поддерева (0 или 1); • удаляемой вершины в дереве нет. Ниже приведена рекурсивная процедура deltree, решающая поставленную задачу. Она отыскивает элемент с заданным ключом и удаляет его. В процедуре deltree описана вспомогательная процедура dl, которая работает только в первом из трех перечисленных случаев.Вспомогательная процедура dl "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.   1. Базис, алфавит, основание. Система счисления - способ записи (изображения) чисел. Символы, при помощи которых записывается число, называются цифрами. Системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в коде(записи) числа, называются позиционными. Основаниемпозиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления. Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или "вес" каждого разряда.   Например: Базисы некоторых позиционных систем счисления. Десятичная система: 10⁰, 10¹, 10², 10³, 10⁴,..., 10ⁿ,... Двоичная система: 2⁰, 2¹, 2², 2³, 2⁴,..., 2ⁿ,... Восьмеричная система: 8⁰, 8¹, 8², 8³, 8⁴,..., 8ⁿ,... Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Количество цифр в алфавите равно основанию системы счисления. Уравновешенные системы счисления   ---===---   Двоичная СС с большим успехом используется в компьютерной технике до сих пор. Однако выявились и существенные недостатки использования двоичной СС, влияющие на скорость работы процессора и надежность передачи информации.   Одним из этих недостатков является так называемая проблема представления отрицательных чисел. Попытка преодолеть этот и другие недостатки двоичной системы счисления стимулировала использование в компьютерах других систем счисления и развитие собственно теории систем счисления.     Выбирая систему кодирования информации в компьютере, разработчики в первую очередь думают о быстродействии процессора, т.е. о скорости обработки закодированной информации. /// Что привычно и хорошо для человека, выполняющего вычисления на бумаге, не всегда хорошо для компьютера. Для того чтобы сложить два целых числа с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить следующие действия: 1) взять модули слагаемых; 2) сравнить эти модули; 3) запомнить знак большего по модулю слагаемого; 4) получившийся результат з 5) из большего модуля вычесть меньший модуль; 6) записать со знаком из п. 3. Многовато будет для простой и часто используемой операции! \\\   В десятичной системе счисления для представления отрицательных чисел человек использует знак числа. То, есть для записи отрицательных чисел имеющихся 10 знаков недостаточно. Используется еще один знак - '-'. То есть для записи отрицательных десятичных чисел потребоваломь 11 знаков! Аналогично, для записи отрицательных двоичных чисел требуется 3 знака, но в нашем распоряжении их два - 0 и 1. Для решения проблемы вначале века использовалось прямое кодирование: в старший бит регистра числа явно вписывался знак '0' для положительных и знак '1' для отрицательных чисел. При определении значения числа этот бит игнорировался. Вроде бы все нормально, но процессор не может работать с отдельными битами регистра. Для определения знака числа, число загружалось в процессор, применение маски (числа 10 или 1000) оставляло в регистре только бит знака, весь регистр проверялся (ноль или нет). Для выделения значения числа снова использовалась маска (7F или 7FFF), после чего определялось число - не слишком ли много действий процессора для выполнения простых операций? /// для 1 байта 5 = 00000101 -5 = 10000101 \\\ Чтобы сократить число действий процессора, придумали обратный код: для чисел договорились старший бит не использовать, а для получения отрицательного числа выполнять команду инвертирования - менять в записи 0 на 1, а 1 на 0. Это одна команда для процессора. Но проверка бита знака все равно остется. /// для 1 байта 5 = 00000101 -5 = 11111010 \\\   Кроме всего прочего применение прямого или обратного кодирования добавляет новую проблему: число 0 оказываеися можно хранить двумя разными способами (как?). Появились значения +0 и -0. Представьте, решаем квадратное уравнение, и начинаем проверять, равен ли он 0. Поребуется сравнивать как с число 0, так и с числом -0, - двойная работа! Использующийся в настоящее время во всех компьютерах способ хранения отрицательных чисел называется "дополнительный код". Для получения из положительного числа отрицательного, как и при дополнительном коде, выполняют инвертирование, после чего к результату добавляется 1. Неболбьшое усложнение кодирования снимает проблему двойного представления нуля: 00000000 - исходное   11111111 - после инвертирования     ---------- 100000000 - после добавления 1 Так как самый старший бит является девятым и в однобайтный регистр не помещается, он будет отброшен. То есть 0 представляется только как 00000000.   Кодирование называется дополнительным, потому что положительное и отрицательное числа "дополняют" друг друга до той самой единицы, бит для хранения которой выходит за пределы регистра. Поэтому и преобразование отрицательного числа в положительное происходит по тому же правилу: инверсия и увеличение на 1.   Еще одно преимущество такого представления чисел: появилась возможность отказаться от операции вычитания. Вместо нее применяется сложение с отрицательным числом. Попробуйте выполнить сложение над двоичными числами, записанными в дополнительном коде. /// !!! подобрать примеры сложения положительных, отрицательных, смешанных чисел!!! \\\   Все вроде хорошо, но попробуйте в переменную X, объявленную как var x:integer; записать положительное число 37000, хранимое без знака (как word), получим, неожидано, отрицательный результат -28536! Подобные фокусы могут привести к ошибочной интерпретации результатов работы программы. /// var x:integer; y:word; begin y:=37000; x:=y; writeln(x); readln; end. \\\ Ошибка произошла потому, что типы integer и word по разному понимают содержимое старшего бита регистра.   ---===---   Троичная система   Можно ли записывать целые отрицательные числа без знака, но и без дополнительного кодирования? Можно! Например, в любой P-ичной уравновешенной системе счисления.   Уравновешенная система с наименишим основанием - это троичная. В 60-х годах XX столетия в МГУ им. М.В. Ломоносова была создана троичная ЭВМ "Сетунь", запущенная потом в серию. Для кодирования информации в этой машине использовалась троичная уравновешенная система счисления, вместо бита использовался трит, вместо привычной двоичной логики - троичная. Разработчик этой ЭВМ Николай Петрович Брусенцов.  

Quot;бит" - место для хранения двоичной цифры - 0 или 1, "трит" - место для хранения цифры троичной системы счисления.   Троичную систему счисления можно построить, как и другие, взяв за основание число 3. Базой при этом будут числа 1, 3, 9, 27, 81,..., а цифрами (алфавитом) 0, 1 и 2. Но кто нам мешает в качестве цифр взять символы { a, 0, 1}, где a равно -1. Глядя на набор цифр, понятно, почему эту систему назвали уравновешенной, или симметричной. Количество цифр до цифры 0 такое же ("уравновешено с"), что количество цифр после цифры 0. "Уравновесить" можно любые системы счисления с нечетным основанием.   Десятичное число Число в троичной уравновешенной системе положительное отрицательное положительное отрицательное 1 -1 1 a 2 -2 1a a1 3 -3 10 a0 4 -4 11 aa 5 -5 1aa a11 6 -6 1a0 a10 7 -7 1a1 a1a   Очевидно, знак для представления отрицательных чисел в урвновешенных системах счисления не нужен! Если у нас есть хотя бы трицифры, обязательно 0, обязательно 1, для третьей цифры можем ставить в соответствие отрицательное значение (-1). Можно ввести отрицательные значения для некотрых цифр СС с четным основанием, но это приводит к тому, что некоторые числа можно будет записать разными способами. /// Для "четверичной" системы счисления можно выбрать и {-1, 0, 1, 2}, и {-2, -1, 0, 1}. \\\   ---===---   Рассмотрим операции сложения и вычитания в троичных системах:   в троичной системе Сложение   + 0 1 2 0 0 1 2 1 1 2 10 2 2 10 11   Умножение   * 0 1 2 0 0 0 0 1 0 1 2 2 0 2 11     в троичной уравновешенной системе сложение + 1 0 1 1 11 1 0 0 1 0 1 1 0 1 11   умножение * 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1     /// сформировать правила построения таблиц сложения и умножения и правила арифметических операций для целых чисел. \\\ ЧислаФибона́ччи — элементы числовой последовательности, где каждое следующее число образуется суммой двух перед ним стоящих чисел (кроме первых двух). Фибоначчиева система счисления (фсс) Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания. Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101fib = 3810. Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел. Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение: F0 =1, F1 =1, Fn =Fn2 +Fn1. Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250). ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …. Обратите внимание, что F0 = 1 в базис не включается. В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления. Десятичное двоичное ФСС 100 или 11 1000 или 110 10010 или 1110 10100100 или 10011100 или 10100011 или 10011011 Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей. Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа. 4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно Как известно, все позиционные системы устроены одинаково и, следовательно, перевод из любой позиционной системы счисления в десятичную осуществляется по одному и тому же алгоритму. В P-ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k-м месте слева, равен a-Pk, где P — основание системы счисления. Часто говорят, что “вес” k-го разряда равен Pk. В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k-го разряда используется k-е число Фибоначчи. 10-й разряд 9-й разряд 8-й разряд 7-й разряд 6-й разряд 5-й разряд 4-й разряд 3-й разряд 2-й разряд 1-й разряд