- •Ю.П. Чернов, о.П. Шафеева программирование для начинающих
- •1. Среда программирования turbo pascal 7.0
- •1.1. Структура меню среды
- •1.2. Правила оформления программ
- •1.3. Команды редактора тп
- •Команды удаления и вставки
- •1.4. Компиляция и исправление синтаксических ошибок
- •2. Элементы языка pascal
- •2.1. Алфавит языка
- •2.2. Константы. Идентификаторы
- •2.3. Операторы
- •2.3.1. Оператор присваивания
- •2.3.2. Оператор безусловного перехода
- •Стандартные функции
- •2.3.3. Условный оператор if
- •2.3.4. Опеpатоp варианта case
- •2.3.5. Составной и пустой операторы
- •2.3.6. Операторы цикла
- •2.4. Процедуры прерываний
- •2.5. Типизированные константы
- •2.6. Структура программы
- •2.7. Подпрограммы
- •2.7.1. Определение процедур и функций
- •2.7.2. Вложенные подпрограммы
- •2.7.3. Вызов подпрограмм
- •2.7.4. Процедуры
- •2.7.5. Функции
- •2.7.6. Передача в подпрограмму параметров-массивов и параметров-строк
- •2.7.7. Рекурсия
- •2.8. Типы в Турбо Паскале
- •2.8.1. Целые типы
- •2.8.2. Логический тип
- •2.8.3. Символьный тип
- •2.8.4. Строковый тип
- •Встроенные функции и процедуры для обработки строк
- •Процедуры преобразования
- •2.8.5. Перечислимый тип
- •2.8.6. Ограниченный тип (диапазон)
- •2.8.7. Вещественные типы
- •2.8.8. Структурированные типы данных. Массивы
- •2.8.9. Множества
- •2.8.10. Записи
- •2.9. Изменение типа выражения
- •2.10. Процедурные типы
- •2.11. Файлы
- •2.11.1. Текстовые файлы
- •2.11.2. Типизированные файлы
- •2.11.3. Нетипизированные файлы
- •2.12. Указатели и динамическая память
- •2.13. Модули
- •2.14. Библиотека Турбо Паскаля
- •2.14.1. Модуль crt
- •2.14.2. Модуль graph
- •Var driver, Mode: integer переменные драйвера и режима.
- •Управление графическим режимом
- •Управление экраном, окном, страницей
- •Управление цветом и палитрой
- •Работа с точками
- •Работа с линиями
- •Построение фигур из линий
- •Построение криволинейных фигур
- •Работа с текстом
- •Обмен с памятью
- •2.15. Динамические структуры данных
- •2.15.1. Связанные динамические данные. Списки
- •Чтобы сослаться на двунаправленный кольцевой список как на единый программный объект, используется указатель, значением которого является ссылка на заглавное звено списка.
- •2.15.2 Очередь
- •2.15.3. Стек
- •3. Практическое программирование Этапы подготовки и решения задач на компьютере
- •Порядок выполнения лабораторных работ
- •Лабораторная работа 1 Основы программирования в среде Турбо Паскаля.
- •Приоритет операций в выражении
- •Задание 1 (программа 1_1)
- •Лабораторная работа 2 Программирование разветвленных алгоритмов. Операторы передачи управления
- •Лабораторная работа 3 Программирование циклических алгоритмов с заданным числом повторений
- •Лабораторная работа 4 Программирование циклических алгоритмов с предусловием
- •Лабораторная работа 5 Программирование циклических алгоритмов с постусловием
- •Модифицировать программу 3_2 для вычисления функций f1(X) и f2 (X) с применением оператора цикла с постусловием. Выполнить ее и сравнить результаты с полученными ранее.
- •Лабораторная работа 6 Программирование алгоритмов обработки одномерных массивов
- •Задание 1
- •Лабораторная работа 7
- •Лабораторная работа 8 Программирование с использованием функций
- •Лабораторная работа 9 Программирование с использованием процедур
- •Лабораторная работа 10 Обработка символьных и строковых данных
- •Лабораторная работа 11 Файлы
- •Лабораторная работа 12 Записи
- •Лабораторная работа 13 Решение нелинейных уравнений
- •Задание (программа_13)
- •Лабораторная работа 14 Вычисление приближенного значения определенного интеграла
- •Лабораторная работа 15 Модульное программирование
- •Лабораторная работа 16 Графика
- •Библиографический список
- •Обозначения графические в схемах алгоритмов (гост 19.701-90)
- •Зарезервированные слова Turbo Pascal 7.0
- •Приложение в
- •Кодировка символов в соответствии с кодами ascii
- •Приложение г
- •Альтернативная кодировка госТа для кодов 128...255
- •Клавиши с кодами из двух частей
Обмен с памятью
GetImage(х1, y1, x2, y2: Integer; var BitMap); сохраняет образ заданной области экрана в буфере. (x1,y1) и (х2,y2) координаты левого верхнего и правого нижнего углов прямоугольной области, BitMap указатель на область памяти, в которой сохраняется информация.
ImageSize(x1, y1, x2, y2: Integer): Word; возвращает размер памяти в байтах, необходимый для сохранения заданного прямоугольного фрагмента с координатами (x1,y1) и (x2,y2) для углов фрагмента.
PutImage(X, Y: Integer; var BitMap; BitBlt: Word); выводит в заданное место экрана копию фрагмента изображения, ранее помещенную в буфер процедурой GetImage. X, Y левый верхний угол области экрана, куда будет скопировано изображение из буфера BitMap, BitBlt – способ объединения выводимой на экран информации с уже имеющейся.
Пример программы, рисующей вращающийся треугольник:
PROGRAM I_13;
Uses Graph, crt;
Var I, a, b, x: integer;
begin
detectgraph(a,b);
initgraph(a, b, 'e:\bp\bgi');
setgraphmode(2);
setcolor(4);
setBKcolor(0);
moveTO(320,20);
repeat
for i=0 to 100 do
if keypressed then break
else
for x:=0 to 240 do
begin
setcolor(15);
line(320,20,140,280);
line(140,280,500,280);
line(500,280,320,20);
setcolor(5);
{бегающая линия}
line(320,60,200+x,240);
line(200+x,240,440-x,240);
line(440-x,240,320,60);
putPixel(110+(2*x),356,15);
putPixel(535-(2*x),356,15);
setcolor(9);
line(320,100,400-trunc(2*x/3),220);
line(400-trunc(2*x/3),220,240+trunc(2*x/3),220);
line(320,120,260+trunc(x/2),200);
line(260+trunc(x/2),200,380-trunc(x/2),200);
line(320,140,350-trunc(x/4),180);
line(350-trunc(x/4),180,290+trunc(x/4),180);
delay(10);
setcolor(0);
line(320,20,140,280);
line(140,280,500,280);
line(500,280,320,20);
line(320,60,200+x,240);
line(200+x,240,440-x,240);
line(440-x,240,320,60);
line(320,100,400-trunc(2*x/3),220);
line(400-trunc(2*x/3),220,240+trunc(2*x/3),220);
line(320,120,260+trunc(x/2),200);
line(260+trunc(x/2),200,380-trunc(x/2),200);
line(320,140,350-trunc(x/4),180);
line(350-trunc(x/4),180,290+trunc(x/4),180);
end;
UNTIL Keypressed;
closegraph;
end.
2.15. Динамические структуры данных
2.15.1. Связанные динамические данные. Списки
Одновременно с необходимостью в динамическом распределении памяти возникла необходимость в разработке способов управления этой памятью. Динамические переменные чаще всего реализуются как связные структуры.
Обращение к динамической переменной происходит посредством ссылочной переменной, которая содержит адрес соответствующей динамической переменной. Под ссылочную переменную компилятор отводит место в памяти; эта переменная имеет имя и явно упоминается в программе. Ссылочные переменные образуют тип данных ссылки или указатели.
Для организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал кроме информационного значения как минимум один указатель. Следовательно, в качестве элементов таких структур необходимо использовать записи, которые могут объединять в единое целое разнородные элементы.
Динамические переменные, как правило, имеют тип «ЗАПИСЬ», так как должны содержать, помимо значения (целого, вещественного), ссылку на другую динамическую переменную связанной структуры.
В простейшем случае элемент динамической структуры данных должен состоять из двух полей: информационного и указательного.
С хематично такую структуру данных можно показать следующим образом:
Соответствующие ей объявления записываются как
Type
Tptr=^Telem; {ссылка на динамическую переменную}
Telem = Record
info: integer;
next: Tptr; {указатель}
end;
Правило последовательности описаний в ТП требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Однако, в приведенном примере, как бы ни располагались описания типов указателя Tptr и элемента TElem, это правило выполнено не будет. Поэтому для описания типов элементов динамических структур данных сделано исключение. Тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента.
Рассмотренная структура называется цепочкой и является частным случаем динамической структуры, называемой в программировании линейным однонаправленным или односвязным списком, где каждый элемент, входящий в очередное звено списка, снабжается ссылкой на следующее за ним звено:
р
В списке предусмотрено заглавное звено. Указатель списка, значением которого является ссылка на заглавное звено, представляет список как единый объект.
Линейные списки – это данные динамической структуры, представляющие собой совокупность линейно-связанных однородных элементов, для которых разрешены следующие действия:
1) добавление элемента в начало;
2) добавление элемента в конец (хвост) списка (частный случай вставки);
3) вставка элемента между двумя любыми другими элементами;
4) исключение элемента (удаление любого, как крайнего, так и среднего элемента списка).
Пример. Создать односвязный список добавлением элементов в его начало
Пример1. Создать односвязный список добавлением элементов в его начало
Program spis0b; {файл spis0b.pas с адресами}
Type sv = ^struct;
Struct = record
key: integer; {ключевое поле}
next: sv {указатель на следующий элемент}
end;
Var p,t,q: sv;
x: integer;
BEGIN
p := nil; { указатель на начало}
q := nil; { указатель на конец}
writeln('Введите элемент (Число больше 999 признак конца)');
read(x); {ввод первого элемента}
while x<=999 do
begin
new(t); {создание нового элемента списка, t - текущее значение указателя}
t^.key:=x; {заполнение ключевого поля}
if (p=nil) then q:=t; {признак конца}
t^.next:=p;
writeln(' ', longint(t^.next)); { вывод адреса}
p:=t; { writeln(ptr(сегмент,смещение)); p-через Wath }
read(x) ; {ввод очередного элемента}
end;
writeln('элемент - адрес');
while t<>nil{не пусто} do
begin
writeln(t^.key:6,' / ', longint(t^.next)); { dispose(t);}
t:=t^.next; { \ нельзя печатать сам указатель}
end;
END.
Пример 2. Подсчитать число вхождений буквы 't' в заданное слово, завершающееся точкой.
Program spis1atp; {spis1a.pas +}
Type
sv{связь}= ^zv; {звено строки}
Zv = record
info: char; {Информационное поле}
next: sv {Указатель на следующий элемент}
end;
Var P {Указатель на начало}, t {Указатель на текущее звено}: sv;
sym: char;
k: integer;
BEGIN {Формирование заглавного звена}
new(p);
t:=p;
p^.next:=nil; {резервирование памяти}
read(sym); {Чтение первого символа}
Write('Введи остальные символы и точку ');
while sym<>'.' do {Цикл обработки последовательных литер строки}
begin
new(t^.next);
t:=t^.next; {адрес следующего}
t^.info:=sym;
t^.next:=nil;
read(sym)
end; {Исходное слово представлено в виде цепочки}
k:=0; t:=p; {Подсчет}
while t<>nil do
begin
t:=t^.next ;
if t^.info='t' then k:=K+1;
end;
Writeln;
Writeln('Буква t входит в слово ',k,' раз');
END.
Для исключения элемента достаточно изменить ссылку у предшествующего исключаемого элемента на ссылку, содержащуюся в исключаемом элементе. При исключении элементов необходимо освободить соответствующий участок памяти.
Исключенный элемент можно освободить от участия в работе блока и использовать занимаемый им участок памяти для других целей.
Для вставки элемента необходимо:
а) создать новый динамический объект, которым будет представлено новое звено;
б) в ключевое поле key внести значение (литеру),
в) в поле next занести ссылку, взятую из поля next того звена, за которым должно следовать вставляемое;
г) в поле next звена, за которым следует вставка, занести ссылку на это вставляемое звено.
Таким образом, для вставки нового компонента в цепочку данных достаточно изменить две ссылки.
Для работы со связными структурами были разработаны 3 основных динамических структуры, объединенные под общим термином списки.
Список это набор динамических элементов (чаще всего переменных типа «запись»), связанных между собой каким-либо способом. Списки бывают линейными и кольцевыми, односвязными и двусвязными, нелинейными и т.д.
Линейный односвязный список представляет собой обыкновенный список: каждый элемент связан только с одним элементом, который называется элементом, следующим за данным. Сам элемент по отношению к следующему называется предшествующим или предыдущим. Последний элемент списка содержит признак конца списка nil.
начало списка конец списка
р
q
элементы списка
Обязательно должен быть указатель на заглавное звено.
Кольцевые списки – это такие динамические данные, как и линейные списки, но имеющие дополнительную связь между последним и первым элементами списка.
Линейный двусвязный (двунаправленный) список отличается от односвязного тем, что в нем каждый элемент связан не только со следующим элементом, но и с предыдущим. И первый, и последний элементы списка содержат признак конца списка:
В линейном двусвязном списке заглавное звено может также не включать информационного поля:
Информационное поле заглавного звена либо вообще не используется, либо может служить для хранения признака того, что это есть заглавное звено, и некоторой информации о списке в целом (количестве звеньев).
В двунаправленном кольцевом списке элементом, следующим за последним, считается заглавный или первый, а элементом, предшествующим заглавному или первому, считается последний: