- •1. Двоичная система счисления.
- •2. Восьмеричная система счисления.
- •3. Шестнадцатеричная система счисления.
- •4. Сложение и вычитание в 2, 8 и 16 c/c.
- •2. Вещественные числа (числа с плавающей запятой).
- •3. Логические данные.
- •2. Зарезервированные слова.
- •X a8 alpha Massiv z52d9 eps Res_52_a ___75
- •6. Метка.
- •2. Целые типы данных.
- •4. Вещественные типы.
- •1. Раздел описания меток.
- •2. Раздел описания констант.
- •3. Раздел описания типов.
- •4. Раздел описания переменных.
- •6. Раздел операторов.
- •7. Последовательность разделов.
- •1. Формульно-словесный способ.
- •2. Блок-схемный способ.
- •Ввод - вывод одномерного массива
- •2. Ввод массива из текстового файла.
- •3. Вывод одномерного массива на экран.
- •Примеры обработки одномерных массивов
- •1. Параметр цикла должен быть ординального типа.
- •2. Параметр должен быть описан в том же блоке, где находится сам оператор цикла.
- •5. В теле цикла параметр не должен изменяться.
- •6. Начальное и конечное значения параметра цикла вычисляются только один раз, до начала цикла.
- •7. При нормальном завершении цикла значение его параметра считается неопределенным.
- •Контроль ординальных переменных
- •Вставка элемента в упорядоченный массив
- •Удаление элементов из массива
- •«Школьный» алгоритм сортировки
- •Группировка массива методом прямой выборки
- •Группировка массива методом прямого обмена
- •Var c : array[1..10,1..15,1..8] of real.
- •1. Ввод элементов матрицы с клавиатуры.
- •2. Ввод матрицы из текстового файла.
- •3. Вывод матрицы на экран.
- •Тождественные и совместимые типы
- •Обработка в процедуре одномерных массивов с различными именами типов
- •Обработка в процедуре матриц с различными именами типов
- •Var s : string[V],
- •Процедуры и функции для обработки строк
- •Определение битовой структуры поля памяти
- •Процедуры и функции для файлов любого типа
- •Var p : pointer;
- •1. Формирование стека из текстового файла.
- •7. Определение значения и местоположения максимального элемента в стеке.
- •8. Удаление из стека максимального элемента.
- •9. Добавление элемента в упорядоченный стек.
- •2. Добавление нового элемента в очередь.
- •3. Удаление элемента из очереди.
- •6. Удаление произвольного элемента из очереди.
- •7. Добавление нового элемента в произвольное место очереди.
- •1. Формирование дека.
- •Var sin : integer;
- •Процедура заполнения FillChar
- •Процедура перемещения данных move
- •Управление экраном в текстовом режиме
- •Сохранение и восстановление экрана
- •Interface
- •Implementation
- •Процедуры управления текстовым режимом экрана
- •Intr(n:byte; Var Reg:Registers),
- •If KeyPressed then
- •Автоматическая оптимизация программ
- •1. Свертывание констант.
- •2. Слияние констант.
- •3. Вычисление по короткой схеме.
- •4. Удаление неиспользуемого кода.
- •If false then
- •5. Эффективная компоновка.
- •Оверлейная структура программы
- •Interface
- •Implementation
- •Interface
- •Implementation
- •Использование сопроцессора
9. Добавление элемента в упорядоченный стек.
Будем считать, что элементы стека расположены по возрастанию их численных значений.
Возможны два варианта включения нового элемента:
a) включение в начало стека (рис.16);
б) включение в произвольное место стека (рис.17).
Во втором случае, как и в программе добавления нового элемента в упорядоченный массив, производим последовательный просмотр элементов стека до обнаружения элемента, большего по значению, чем добавляемый элемент.
Как следует из анализа рис.17, для изменения связей в стеке при добавлении элемента требуется знать адрес предыдущего элемента.
Program InsElem1;
Label 10;
Type PoinType = ^DynType;
DynType = record
Inf : integer;
Next : PoinType;
end;
Var Beg,Run,
Pred, { указатель эл-та, предшествующего }
{ включаемому новому элементу }
NewEl : PoinType; { указатель нового элемента }
k : integer;
Begin
Формирование стека
Read(k); New(NewEl); NewEl^.Inf:=k;
If (Beg=nil) or (k<=Beg^.Inf) then
Begin
NewEl^.Next:=Beg; { включение нового эл-та }
Beg:=NewEl; { в начало стека }
End
Else
Begin
Pred:=Beg; Run:=Beg^.Next;
While Run<>nil do
If Run^.Inf > k then
Begin
NewEl^.Next:=Run; { включение нового эл-та }
Pred^.Next:=NewEl; { в середину стека }
Goto 10
End
Else
Begin
Pred:=Run; { перебор элементов }
Run:=Run^.Next { стека }
End;
Pred^.Next:=NewEl; { включение нового эл-та }
NewEl^.Next:=nil; { в конец стека }
End;
10:
Печать стека
End.
Если при просмотре стека не обнаружен элемент, превышающий значение k, то это означает, что значение k должно быть записано после последнего элемента стека.
Как и в предыдущем примере, программу InsElem1 можно реализовать без указателя Pred, возложив его функции на указатель Run.
Program InsElem2;
Type PoinType = ^DynType;
DynType = record
Inf : integer;
Next : PoinType;
end;
Var Beg,Run,
NewEl : PoinType; { указатель нового элемента }
k : integer;
Cond : boolean;
Begin
Формирование стека
Read(k);
New(NewEl); NewEl^.Inf:=k;
If (Beg=nil) or (k<=Beg^.Inf) then
Begin
NewEl^.Next:=Beg; { включение нового эл-та }
Beg:=NewEl; { в начало стека }
End
Else
Begin
Run:=Beg; Cond:=true;
While (Run^.Next<>nil) and Cond do
If Run^.Next^.Inf > k then
Begin
NewEl^.Next:=Run^.Next; { включение нового эл-та }
Run^.Next:=NewEl; { в середину стека }
Cond:=false
End
Else
Run:=Run^.Next;
If Cond then
Begin
Run^.Next:=NewEl; { включение нового эл-та }
NewEl^.Next:=nil; { в конец стека }
End;
End;
Печать стека
End.
Здесь следует обратить также внимание, что за счет небольшой модификации программы в InsElem2 исключен оператор Goto.
О Б Р А Б О Т К А О Ч Е Р Е Д И
Очередь - это линейный список, в котором все включения производятся на одном конце списка, а исключения делаются на другом конце. Принцип организации очереди: "Первый пришел - первый вышел", что сокращенно обозначают также FIFO (‘First in – first out’).
Указатели R и L (рис.18) определяют правый (Right) и левый (Left) концы очереди. Указатели Next, входящие в состав каждого элемента, определяют адрес следующего справа элемента в очереди. Следовательно, с левого конца можно и добавить, и удалить элемент (как в стеке). Указатель Next крайнего правого элемента пустой. Этому элементу неизвестно, где находится предыдущий элемент. Поэтому справа можно только добавлять новые элементы. Следовательно, в очереди добавление элемента должно производиться справа, а удаление - слева.
В дальнейшем будем считать, что в каждом фрагменте программы, иллюстрирующей методы формирования и обработки очереди, действует следующее описание:
Type PoinType = ^DynType;
DynType = record
Inf : integer;
Next : PoinType;
end;
Var L, { указатели левого и правого }
R, { концов очереди }
Run : PoinType; { текущий указатель }
k : integer;
F : text;
Формирование очереди из текстового файла.
В программе формирования очереди учтены два частных случая:
а) исходный файл пустой; тогда и очередь должна быть пустой, о чем свидетельствует значение L = nil;
б) в файле содержится лишь одно число; тогда адрес единственного элемента очереди определяют оба указателя L и R.
Будем считать, что адрес очередного элемента очереди определяет текущий указатель Run, и рассмотрим два этапа формирования очереди:
из файла прочитан первый элемент, включаемый в очередь (возможно, этот элемент останется единственным в очереди);
из файла прочитан второй элемент.
Признаком первого этапа является равенство L = nil. На этом этапе должны быть выполнены следующие действия:
Run^.Next:=nil; L:=Run; R:=Run
Значение L<>nil является признаком чтения из файла следующего элемента очереди. В этом случае должно быть выполнено:
Run^.Next:=nil; R^.Next:=Run; R:=Run
Тогда программа формирования очереди будет иметь следующий вид:
L:=nil; R:=nil;
While not SeekEof(F) do
Begin
Read(F,k);
New(Run);
Run^.Inf:=k;
If L=nil then
Begin
Run^.Next:=nil;
L:=Run; R:=Run
End
Else
Begin
Run^.Next:=nil;
R^.Next:=Run;
R:=Run;
End;
End;
В альтернативах условного оператора имеются одинаковые операторы. Это позволяет записать программу формирования очереди в более компактном виде:
L:=nil; R:=nil;
While not SeekEof(F) do
Begin
Read(F,k);
New(Run); Run^.Inf:=k;
Run^.Next:=nil;
If L=nil then
L:=Run
Else
R^.Next:=Run;
R:=Run;
End;
Примечание. Элементы очереди, в отличие от стека, располагаются в том же порядке, что и в файле. Если же почему-либо требуется, чтобы относительный порядок элементов в очереди был обратным, то добавление новых элементов нужно производить слева, а не справа (как в стеке).