МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Южно-Российский государственный технический университет (НПИ)
____________________________________________
Кафедра «Aвтоматикa и телемеханикa»
Малашенко А.Г., Малашенко Л.И., Дереча С.В, Онышко Д.А., Левшин А.Г..
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к практическим занятиям по дисциплине
"ПРОГРАММИРОВАНИЕ И ОСНОВЫАЛГОРИТМИЗАЦИИ"
Часть 2
Var
AiT: integer;
Begin
AiT:=1951+50;
End.
НОВОЧЕРКАССК 2011
УДК 519.6 (076.3)
Методические указания к практическим занятиям по дисциплине «Программирование и основы алгоритмизации". Часть 2»
Методические указания содержат цель, программу выполнения лабораторных работ, контрольные вопросы, указания по выполнению лабораторной работы, требования к содержанию отчета, сведения о литературе, необходимой для подготовки к выполнению работы.
Методические указания предназначены для студентов второго курса специальности «Управление и информатика с технических системах» всех форм обучения.
Объем стр., тираж экз.
Методические указания обсуждены и одобрены
на заседании кафедры
"Автоматика и телемеханика"
ФИТУ ЮРГТУ(НПИ)
протокол №
Южно-Российский государственный технический
университет (НПИ), 2011
Введение
Для проведения лабораторных работ необходимы любые IBM РС-совместимые компьютеры. В качестве системного программного обеспечения (ПО) требуется операционная среда Windows, а в качестве инструментального ПО–интегрированная среда для работы с программами на языке Паскаль, а также среда для работы на языке С.
При подготовке к работе рекомендуется ознакомиться с методическими указаниями, а после выполнения работы для самоконтроля следует использовать контрольные вопросы.
Каждый студент приобретает практические навыки разработки программ, выполняя индивидуальное заданию и производит отладку с помощью инструментального ПОдо получения правильного решения контрольных вариантов.
Цель каждой лабораторной работы заключается не только в получении работоспособной программы, но, прежде всего, в приобретении навыков программирования путем применения в программах возможно большего количества конструкций языка. Поэтому в индивидуальных заданиях должен быть сделан акцент на обязательное использование в разрабатываемых программах определенных типов, операторов и структур данных. Кроме того, в программах должны быть предусмотрены содержательный ввод и вывод данных в терминах постановки задачи.
Практическое занятие №1
Программирование списков
Продолжительность занятия 6 часов.
Цель занятия: приобрести умения и навыки программирования списков с использованием динамических переменных.
Подготовка к работе: самостоятельное изучение сведений об указателях, динамических переменных, списках.
Программа работы
1. Рассмотреть примеры использования указателей.
2. Изобразить структуры списков.
3. Составить фрагменты подпрограмм, реализующих обработку элементов списка.
4. Составить программу основной программы и модуля по индивидуальному заданию.
5. В рамках самостоятельной работы отладить составленную программу.
Контрольные вопросы
1. Что такое указатель и как он описывается?
2. Что размещается в сегменте кода?
3. Что размещается в сегменте стека?
4. Где размещаются данные Паскаль-программы?
5. Где размещаются динамические переменные?
6. Как создается динамическая переменная?
7. Как удаляется динамическая переменная?
8. Что такое односвязный список?
9. Что такое стек?
10. Что такое очередь?
11. Что такое кольцо?
12. Как были Вами реализованы процедуры для обработки списка?
Варианты индивидуальных заданий
- Варианты формируются из таблиц 1…3.
Таблица 1 - Варианты задания структуры односвязного списка
| Номер варианта | |||
| Структура односвязного списка | Очередь | Стек | Кольцеобразный список |
Таблица 2 - Варианты задания типа информационного поля односвязного списка
| Номер варианта | ||||||
| Тип информационного поля | Целый тип | Вещественный тип | Символьный тип | Тип-диапазон | Перечисляемый тип | Логический тип |
Таблица 3 - Варианты задания обработки односвязного списка
| Номер варианта | ||||||||||||
| Поиск | минимального элемента списка | максимального элемента списка | среднего по положению элемента списка | среднего по значению элемента списка | 1-го элемента, имеющего значение < среднего | 1-го элемента, имеющего значение < заданного | 1-го элемента, имеющего значение > заданного | 1-го элемента, имеющего значение > среднего | 1-го элемента, принадлежащего заданному интервалу значений | 1-го элемента, значение которого вне заданного интервала значений | ||
| Номер варианта | ||||||||||||
| Перемещение найденного элемента | на один элемент вправо | на один элемент влево | на два элемента влево | на два элемента вправо | в начало списка | в конец списка | на место за 1-ым элементом | на место перед последним элементом | в середину списка | на место после 2-го элемента | ||
| Номер варианта | ||||||||||||
| Удаление | элемента, расположенного за найденным | элемента перед найденным | последнего элемента | первого элемента | элемента, расположенного за 1-ым | элемента, расположенного за 2-ым | предпоследнего элемента | элемента, расположенного слева от середины найденным | элемента, расположенного справа от середины | среднего по положению элемента | ||
Методические указания
К п.1. Вся оперативная память делится на сегменты размером, не превышающим 65536 байт(64К). Сегменты, в которых размещаются главная программа и ее модули, а также стандартный библиотечный модуль SYSTEM, называются сегментами кода. В сегменте данных размещаются глобальные переменные и типизированные константы, объявленные в главной программе и секциях связи модулей. Сегмент стека служит для размещения локальных данных подпрограмм и внутренних данных модулей. Сегмент стека загружается при каждом обращении к подпрограмме и освобождается при выходе из нее. Таким образом максимальный размер определяется количеством вложенных вызовов процедур и суммарным количеством их локальных переменных.
Размеры сегмента кода и сегмента данных определяются в процессе компиляции компоновщика (Linker) и во время работы не меняются. Размер сегмента стека устанавливается по умолчанию равным 16К и может быть изменен (не более 64К) опцией Option/Memory/Sizes установкой размера в поле Stack size.
Сегменты программы располагаются в памяти в определенном порядке: сначала сегмент кода главной программы, затем сегментыкода неоверлейных модулей, следом сегмент данных и, наконец, сегмент стека. За сегментом стека следует оверлейный буфер, размер которого может устанавливаться программистом. Оставшаяся свободной область частично или полностью может быть занята динамической памятью. В ней размещаются динамические переменные .( см. рисунок 1). Эта часть памяти называется “heap ” (“куча”)
Динамические переменные создаются и уничтожаются во время выполнения программы в отличие от статических переменных, память под которые резервируется в сегменте данных еще на этапе компиляции. Размер кучи (минимальный и максимальный размер) можно установить уже известной опцией Option/Memory/Sizes в двух других полях. Эти размеры определяются реальными потребностями программы в динамической области. Если установить максимально возможный размер в 655360 байт(640К), то такая программа займет всю доступную оперативную память. По умолчанию минимальное значение динамической памяти равно 0.
| Плавающие границы | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Динамическая память ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Оверлейный буфер ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Сегмент стека |
| Сегмент данных | |
| Сегмент кода модуля SYSTEM | |
| Сегмент кода первого модуля программы | |
| ... | |
| Сегмент кода последнего модуля программы | |
| Сегмент кода главной программы | |
Рисунок 1
Карта распределения памяти является выходным документом компоновщика Linker и может быть сформирована при установке следующей опции среды ТР
Option/Linker/Map File/Segments.
К п.2. Динамические переменные не имеют имени. Для работы с ними введены специальные ссылочные типы, или указатели. По существу указатель - это адрес, начиная с которого динамическая переменная размещена в памяти.
Указатель связывается не с конкретной переменной, а с определенным типом данных. Для описания указателя используется знак “^”.
Пример описания
Type
IP = ^Integer; {тип указателя на целое}
P = ^Zap; {тип указателя на запись Zap}
Zap = record
...
end;
Var
Pointer1: ^Char; {указатель на Char}
Pointer2: ^Real; {указатель на Real}
В Турбо Паскале определена лишь одна операция над указателями - присваивание. Можно присвоить значение одного указателя другому указателю на тот же тип данных. Существуют также нетипизированные указатели, которые совместимы с указателями на любой тип. Для объявления переменной нетипизированным указателем нужно употреблять ключевое слово Pointer
Var
TypePointer: Pointer;
Значением нетипизированного указателя может являться либо адрес, либо NIL. NIL -специальное значение, обозначающее пустой указатель, который ни на что не указывает.
Для того, чтобы выделить место в куче под динамическую переменную, используется процедура NEW.
Type
PE = ^Extended;
Begin
...
New(PE);
...
End.
В приведенном примере в куче выделяется 10 байтов (в соответствии с размером типа Extended) и адрес начала этой области возвращается в указателе PE. Для обращения к полученной динамической переменной используется конструкция вида <имя указателя>^:
PE^:=3.1415;
PE^:=sqr(PE^);
Для освобождения динамической памяти используется процедура Dispose -
Dispose(PE); {освобождает 10 байтов в куче}
Более подробно с набором подпрограмм для работы с динамической памятью, а также с правилами работы с указателями можно ознакомиться в [1].
Одной из областей, где необходимо использование указателей, является работа со списками, например, односвязными и двусвязными. Списки имеют начало и конец. Основные действия: создание, просмотр, вставка и удаление элемента в указанном месте списка.
Широкое распространение среди односвязных списков получили такие динамические структуры данных, как стеки, очереди и кольцеобразные списки.. Стек организован таким образом, что программе доступна лишь его вершина: оттуда можно взять элемент или записать его туда. Таким образом, элементы можно извлечь из стека в порядке, обратном порядку их записи -"последний вошел - первый вышел". Очередь же реализует другой вариант доступа к данным - "первый вошел - первый вышел’. Новый элемент добавляется в конец очереди, а выбирается первый. Если последний элемент очереди связать с первым элементом, то получится замкнутый, кольцеобразный список..
Для работы с такими структурами при выполнении индивидуального задания рекомендуется использовать базовые процедуры:
Init - создать список;
Clear - очистить список;
PutData - поместить элемент в список;
GetData - взять элемент из списка;
LookData - просмотр элементов списка.
Рассмотрим реализацию этих процедур:
Type
Ukaz = ^TStack;
TStack = record
Inf: Integer;
Next: Ukaz;
End;
Procedure Init (var Top: Ukaz
Begin
Top:=Nil;
End;
Procedure Clear (var Top: Ukaz);
Var
Kon: Ukaz;
Begin
While Top<>Nil Do
Begin
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
End;
End;
procedure PutData(var S: Ukaz; Data: Integer);
Var
P: Ukaz;
Begin
New(P);
P^.Inf:=Data;
P^.Next:=S;
S:=P;
end;
procedure GetData(var S: Ukaz; Data: Integer);
Var
P:Ukaz;
Begin
Data:=S^.Inf;
P:=S;
S:=S^.Next;
S^.Inf:=Data;
Dispose(P);
end;
procedure LookData (var Top: Ukaz);
Var
Kon: Ukaz;
Begin
While Top<>Nil Do
Begin
Writeln(Top^.Inf);
Kon:=Top;
Top:=Top^.Next;
End;
End;
Следует обратить особое внимание на следующие детали, связанные с выделением и освобождением динамической области через вызовы стандартных процедур New и Getmem, Dispose, Mark и Release. Если в системе нет памяти для кучи, равной минимальному значению, программа не будет выполняться.
Куча имеет стековую структуру, растущую от нижних адресов в сегменте кучи. Нижняя граница кучи хранится в переменной HeapOrg, а вершина - в HeapPtr. Когда динамическая переменная размещается в куче так назывыемый администратор кучи передвигает HeapPtr вверх на размер этой переменной. Максимальный размер переменной, который может быть распределен в куче, равен 65519 байт, поскольку каждая переменная должна полностью находиться в одном сегменте.
Динамическую переменную легче всего удалить с помощью процедур Mark и Release. В фрагменте программы
New (Ptr1);
Mark (P);
New (Ptr2);
New (Ptr3);
процедура Mark (P) помечает состояние кучи перед распределением переменной Ptr2:
Если выполнить оператор Release (P), то состояние кучи станет как на рисунке ниже:
Выполнение операции Release (HeapOrg) полностью очищает всю кучу, так как HeapOrg - нижняя граница кучи.
Для программ, которые освобождают указатели в порядке, обратном их распределению, процедуры Mark и Release очень эффективны. При случайном распределении и освобождении динамической области памяти используют процедуры Dispose и FreeMem (например, Dispose (Ptr3) - освобождает блок содержимого Ptr3, т.е. образовывает свободное пространство) позволяют программе освобождать динамические переменные в любое время. При этом “куча” становится фрагментированной (“c дырками”), свободные блоки памяти, создаваемые и разрушаемые в этом режиме, фиксируются для последующего использования.
Существует, так называемый, список свободных блоков, который растет сверху вниз от верхней границы сегмента кучи.
При распределении динамической переменной проверяется список свободных блоков и если есть свободный блок подходящего размера (больше или равен размеру распределяемого блока), то он используется.
Необходимо помнить, что процедура Release всегда очищает список свободных блоков, т.е. администратор “кучи” забывает все свободные блоки ниже указателя кучи. При смешивании вызовов Mark и Release с вызовами Dispose и FreeMeì не должно быть свободных блоков.
Переменная FreeList из стандартного модуля System указывает на первый свободный блок в куче. Этот блок содержит указатель на следующий свободный блок и т.д. Последний свободный блок содержит указатель на вершину кучи (т.е. на положение, указываемое HeapPtr. Если нет свободных блоков, то FreeList равна HeapPtr. Размер каждого блока округляется с избытком до величины, кратной 8. Например, блок в 50 байт будет округлен до 56 байт и при следующем запросе на распределение, например, от 49 до 55 байт будет полностью использовать этот блок (56 байт), не оставляя от 7 до 1 байт свободных, которые могли бы фрагментировать кучу.
Когда администратор кучи не может обработать запрос на распределение памяти, то вызывается функция обработки ошибок кучи HeapFunc:
Function HeapFunc (Size:word):Integer; far;
Функция обработки устанавливается присваиванием ее адреса переменной HeapFrror:
HeapFrror:= @HeapFunc.
Функция HeapFunc возвращает 0,1 или 2.
· 0- возникает ошибка времени выполнения;
· 1- программы New или GETMEM возвращают указатель, равный Nil без аварийного завершения программы:
· 2- успешное распределение памяти.
Для многих программ будет удобнее следующая функция обработки ошибок
Function HeapFunc (Size:word):Integer; bar;
Begin
HeapFunc:=1;
end;
Когда эта функция установлена, New и GetMem будет возвращать Nil при невозможности распределить память, не приводя к аварийному завершению программы, что позволяет провести анализ состояния следующим образом:
HeapFrror:= @HeapFunc{перехват функции контроля состояния кучи}
GetMem(p,size);{выделить Size байт в динамической области}
If p=Nil Then
Begin
writeln(‘Ошибка кучи’);
Release(p1);{освобождение Heap с адреса Р1, заранее помеченного Mark(p1)}
GetMem(p1,size);{повторение выделения нужного размера области с адреса р1}
p:=p1;
End;