Основы проектирования программ

ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

80

 

Этапы проектирования программ:

техническое задание;
разработка технического проекта;
разработка рабочего проекта;
отладка отдельных модулей и программы в целом
Разработка документации

81

 

I. Техническое задание (примерный план)

1.Организационно-экономическая сущность задачи:

• наименование задачи, место ее решения;
• цель решения;
• назначение (для каких объектов подразделений и пользователей она предназначена);
• периодичность решения и требования к срокам решения;
• источники и способы поступления данных;
• потребители результатной информации и способы ее отправки
• информационная связь с другими задачами.

82

 

2. Описание исходной (входной) информации:
• перечень исходной информации;
• формы представления (электронная форма или бумажный документ) по каждой позиции перечня; примеры заполнения форм (документов); описание структурных единиц информации (каждого элемента данных, реквизита);
• способы контроля ввода исходной информации;
3. Описание выходной информации:
• перечень результатной информации;
• формы представления, (печатная сводка, видеограмма, машинный носитель и его макет и т.д.);
• перечень пользователей результатной информации (подразделение и персонал)
• перечень регламентной и запросной информации;
• описание структурных единиц информации (каждого элемента данных, реквизита) по аналогии с исходными данными;
• способы контроля результатной информации;
• контроль разрядности;
• контроль интервала значений реквизита;
• контроль соответствия списку значений.

83

 

4.Описание алгоритма решения задачи (последовательности действий и логики решения задачи):
• описание способов формирования результатной информации с указанием последовательности выполнения логических и арифметических действий;
• описание связей, между частями, операциями, формулами алгоритма;
• требования к порядку расположения (сортировке) ключевых реквизитов, например; по возрастанию значений табельных номеров.
5.Описание используемой условно-постоянной и справочной информации:
• перечень единиц условно-постоянной информации, классификаторов, справочников, таблиц, списков с указанием их полных наименований;
• формы представления;
• описание структурных единиц информации (по аналогии с исходными записями;
• способы взаимодействия с переменной информацией;
• содержание справочной информации, ее структура и способы обращения к ней.

84

 

Описание данных (входной, выходной и справочной информации) свести в таблицу 1.
 
Таблица 1 - Описание данных, используемых в программе.
 
 
 
 
 

В столбце «Назначение переменной» может быть указан один из трёх вариантов: 
исходные данные;
вспомогательная переменная;
результат.
В столбце «Ограничения» необходимо указать тип переменной и ее вид (простая или элемент массива или записи), а также ограничения на значения, например, «значение больше нуля».

85

 

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

Структурная методология включает следующие методы:

Метод нисходящего проектирования («сверху-вниз»);

Метод восходящего проектирования («снизу-вверх»)

86

 

Метод нисходящего проектирования («сверху-вниз») – подход функциональной декомпозиции на основе 2 стратегий:
пошагового уточнения, при котором на каждом следующем этапе декомпозиции определяются модули очередного более низкого уровня;
анализа сообщений, при котором анализируются потоки данных, обрабатываемых модулями.

Метод восходящего проектирования («снизу-вверх») – подход, при котором в первую очередь определяются вспомогательные модули,
которые потребуются при проектировании программы.

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

87


 



































При проектировании программы

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














Рис. 1 Примерный состав модулей, выделяемых в программном продукте при декомпозиции

88

 

На этом этапе также необходимо:
установить какие справочные данные требуются для решения поставленной задачи,
разработать форму представления и ввода для них.
определить в виде каких объектов данных будут представлена используемая информация.
Под объектом данных программы подразумевается переменные, структуры (записи), массивы, файлы, используемые в программе.
Обычно объекты данных, используемые в программе, формируются на основе объектов предметной области, участвующих в задаче.
Выделенные подзадачи (рис.1) являются прообразами будущих программных модулей.
Для разработки программных модулей необходимо разработать алгоритм для каждой выделенной подзадачи.
На рис. 2 приведена типовая структура программного продукта, состоящего из отдельных программных модулей, процедур, встроенных функций.

89


 

90

 

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

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

91

 

Общие рекомендации при декомпозиции:
не пытайтесь разбивать на модули очень простые задачи;
рекомендуемый размер модуля от 15 до 60 программных строк;
обязательно выделяйте в виде модуля ту часть программы, которая может быть полезна в других программах или в нескольких частях данной программы;
переменные, общие для нескольких модулей должны быть определены в вызывающей программе;
стремитесь к независимости модулей.
Выделим преимущества модульного программирования:
единичный модуль легче написать, отладить, проверить;
один модуль можно использовать в разных частях программы и в других программах;
изменения в программе могут затрагивать только один модуль, а не всю программу;
разработку отдельных модулей можно поручить различным людям.

92


 



































Пример. – Разработка информационно-поисковой

системы «Склад». Созданная программа должна обеспечивать:
ввод исходных данных;
редактирование и модификацию данных;
просмотр результатов;
выдачу данных по запросам пользователя (поиск товара по наименованию, подсчет общей стоимости продуктов);
выход в ОС.
Выделим сущность предметной области - Товар. В качестве объекта данных, соответствующего сущности предметной области, выбираем структуру данных – запись, включающую поля:
номер,
наименование,
стоимость единицы товара,
количество единицы товара.
Для хранения и организации последовательной обработки информации о товарах наиболее удобной структурой представляется файл из записей.

93


 



































Зададим описания основных структур

данных:

Type tovar =record
nom: 0..100; {номер или индекс товара}
nt: string[20]; {наименование товара}
ed_iz : string[10]; {единица измерения }
s_ed, kol : real; {цена 1 единицы, количество единиц}
end;
tov=tovar;
file_type= file of tov; {файл из записей}
var t :tov; { описание переменной типа запись}
copf, f: file_type; { описание двух переменных типа файл}
p: byte; {пункт меню}

94


 



































На рис. 3 приведена

примерная структурная схема информационно-поисковой системы (ИПС) «Склад», полученная в результате декомпозиции поставленной задачи на подзадачи первого и второго уровней.

95


 



































III. Разработка рабочего

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

В общих сведениях о программе необходимо указать обозначение и наименование программы; программное обеспечение, необходимое для функционирования программы; язык программирования, на котором будет написана программа.

96


 



































Функциональное назначение должно содержать

описание классов решаемых задач и (или) назначение программы и сведения о функциональных ограничениях на применение.
В описании логической структуры должны быть указаны используемые методы, представлена модульная структура программы с описанием функций составных частей и связей между ними.
Для одного из модулей должна быть представлена блок-схема алгоритма его реализации, описаны виды организации диалога.
В описании логической структуры также должны быть представлены описания созданных процедур и функций, а также описания используемых данных.
Описания созданных процедур и функций должны быть представлены в виде таблицы 2.
Таблица 2 - Характеристика созданных подпрограмм.







 
 

97


 



































Продолжение примера – Головной

модуль
BEGIN
Assign(f, 'sclad'); { назначение переменной типа файл имени физического {файла}
Writeln(‘Нужно ли создавать файл? (д/н)'); Readln(c);
If (с='д') or (с='Д') Then sozdfile(f);{вызов п/п создания файла}
Repeat
Quit:=false; {переменная типа boolean}
Clrscr;
Writeln (' Программа "СКЛАД" ');
Writeln ('Что будете делать?');
Writeln (‘1. Работа с записями о товарах'); {вывод пунктов меню}
Writeln ('2.Обработка запросов');
Writeln (‘3. Выход из программы');
Readln(p); {ввод пункта }
Case p of
1: RabZap;{вызов п/п записей}
2: ObrZapr;
3: Quit:=True; {выбран пункт выхода из программы}
End; {Case}
Untile quit;
END.
 

98


 



































Пример 1 – Управляющий

модуль работы с записями
Procedure RabZap;
Var m:byte; qrab: boolean;
BEGIN
Repeat
qrab :=false; {переменная типа boolean}
Clrscr;
Writeln (' Работа с записями');
Writeln (‘Что будете делать?');
Writeln (‘1. Добавление записи'); {вывод пунктов меню}
Writeln (‘2.Просмотр записей');
Writeln (‘3.Изменение записи');
Writeln (‘4.Удаление записи');
Writeln (‘5. Выход из режима работы с записями');
Readln(p); {ввод пункта }
Case m of
1: dobav(f); {вызов п/п записей}
………………..
5: qrab :=True; {выбран пункт выхода из управляющего модуля}
End; {Case}
Untile qrab;
END.
 

99


 



































Пример 2 – Управляющий

модуль обработки запросов
Procedure ObrZapr;
Var m:byte; qobr: boolean;
BEGIN
Repeat
Qobr:=false; {переменная типа boolean}
Clrscr;
Writeln (' Работа с записями');
Writeln (‘Что будете делать?');
Writeln (‘1. Поиск товара по наименованию '); {вывод пунктов меню}
Writeln (‘2.Подсчет общей стоимости товаров');
Writeln (‘3. Выход из режима обработки запросов');
Readln(p); {ввод пункта }
Case m of
1: poisk (f); {вызов п/п записей}
………………..
3: Qobr:=True; {выбран пункт выхода из управляющего модуля}
End; {Case}
Untile qobr;
END.
 

100


 



































Пример 3 - Процедура ввода

одной записи.
Procedure vvodzap( Var t: tov);
begin
Clrscr;
With t do begin
Writeln(‘Конец ввода номер=0');
Write('Нoмep товара'); Readln(nom);
Write('Название товара'); Readln(nt);
............................. {ввод значений остальных полей}
end;
end; {конец п/п}
 
Пример 4 - Процедура вывода одной записи.
 
Procedure vivodzap(Var t: tov);
Begin
With t do begin
Writeln('Hoмep’,nom:4, 'название ', nt:20);
........................ {вывод остальных полей с пояснениями}
end;
end; { конец п/п}

101


 



































Пример 5 – Процедура создания

файла и записи в него.
 
Procedure sozdfile( var f: file_type);
Var t: tov;
Begin
Rewrite(f); {установка указателя на начало файла для записи }
Vvodzap(t); {ввод одной записи с клавиатуры}
While t.nom<>0 do {выполнять, пока номер записи не будет равен 0}
Begin
Write(f,t); {запись в файл}
Vvodzap(t); {ввод следующей записи с клавиатуры}
End;
Close(f); {закрытие файла}
End; {конец п/п}

102

 

Пример 6 – Процедура удаления записи из файла.
Procedure udal(var i:file_type);
Var t: tov; k: 1..100; с: char; found: boolean;
Begin
Assign(copf, 'copsc');
Writeln('Какую запись удалить? Введите номер товара'); Readln(k);
Reset(f); Rewrite(copf); {позиционирование файлов}
Found:=False;
While Not Eof(f) do begin
Read(f,t); {читаем запись из файла}
If t.nom < > k then write(copf,.t) {если номер записи не k, записываем ее в файл-{копию}
Else begin found:=true; {запись для удаления найдена}
Vivod(t); write(‘Именно эту запись удалить?'); Writeln(‘Д/H'); Readln(c);
Case с of
'д','Д','у','У : ; {пустой оператор, запись k в файл-копию не записываем}
Else Write(copf,t); {раздумали удалять, записываем запись k в файл-копию }
End; {case}
End; {else}
End; {while}
Close(f); Close(copf); {закрываем файлы }
If not found { если запись не найдена} Then begin
Writeln('Запись с номером ', k : 3, ' не найдена'); Erase(copf); {удаляем файл-копию}
End
Else begin
Erase(f); Rename(copf,’sclad’);
End;
End; {конец п/п}

103

 

Пример 7 – Процедура просмотра всех записей файла.
Procedure prosmotr(var f:file_type);
Var t:tov;
Begin
Reset(f); {установка указателя на начало файла для чтения из него}
While not eof(f) do begin {выполнять, пока не достигнут конец файла}
Read(f, t); {чтение записи из файла}
Vivodzap(t); {вывод записи}
end;
End; {конец п/п}
 
Пример 8 – Процедура добавления новой записи в файл.
Procedure dobav( Var f: file_type);
Var t:Tov; с: Char;
Begin
Reset(f);
Seek(f,Filesize(f)); {указатель перемещаем на конец файла}
Vvodzap(t);
Write(f, t); Close(f);
End; {конец п/п}

104

 

Пример 9 – Процедура изменения. записи
procedure izmen( var f : file_type); {изменение записи в файле}
var t:tov; k: 1..100; c: char;
begin
writeln(‘Какую запись нужно изменить (номер товара)?’); readln(k);
reset(f);
while not eof(f) and (t.nom < >k) do read(f,t); {считываем записи из файла, пока не достигнем искомой записи}
if t.nom = k then begin
vivod(t); write(‘новая цена ед.’?);readln(t.s_ed);
write(‘новое количество?’); readln(t.kol);…………………..
seek(f,filepos(f)-1); {поместить указатель перед изменяемой записью}
write(f,t); {записываем в файл исправленную запись}
end
else writeln(‘Запись с номером ‘, k : 3, ‘ не найдена’);
close(f);
end; {конец п/п}

104

 

Пример 10 – Процедура нахождения общей стоимости товаров
Procedure Sum(Var f: File_type);
Var t:Tov; s:Real;
Begin
Reset(f); s:=0;
While not eof(f) do begin
Read(f, t); {читаем запись из файла}
s:=s+t.s_ed * t.kol; {суммируем стоимости отдельных товаров}
End;
Writeln('Ha складе хранятся товары на сумму – ‘, s:8:2, 'руб');
Readln;
End; {конец п/п}

105

 

Пример 11 – Процедура поиска данных о товаре по наименованию.
Procedure poisk(var f: file_type);
Var t:tov; name: String[20]; z: Boolean;
Begin
Writeln('Введите название искомого товара?'); Readln(name);
Reset(f); z:=false;
While not eof(f) do Begin
Read(f,t); {читаем запись из файла}
If t.nt = name {товар с искомым наименованием найден}
then begin {выводим данную запись}
z:=true; vivod(t);
end;
end; {while}
if not z then Writeln('3апись с наименованием ', name:20, ' не найдена');
readln;
close(f);
end; {конец п/п}

106

 

На этапе создания рабочего проекта решаются вопросы
организации диалога
Виды диалога:
Выбор действий из меню
Ответ «да» или «нет»
Ответ числовой или символьной информацией
Использование специального входного языка
Использование части разговорного языка

Выбора хорошего стиля программирования:
Правильный выбор имен объектов программы
Запись текста программы с пробелами и отступами, чтобы отразить вложенность блоков
Разумное использование комментариев – вводных, оглавлений, пояснительных
Отсутствие трюков, заумного программирования

107

 

Исследование эффективности программ


Программа считается эффективной, если она занимает минимальную память и выполняется за минимальное время
Поэтому x+x быстрее, чем 2*x
x*0.1 быстрее, чем x / 10
x* x быстрее, чем sqr(x)

Необходимо выполнить «чистку» циклов – вынести за пределы тела цикла все действия, не зависящие от параметра цикла

108

 

Отладка и тестирование отдельных модулей и программы в целом
Тестирование – процесс выполнения программ с целью обнаружения факта наличия ошибок
Отладка – процесс локализации и устранения ошибок

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

109

 

Алгоритм тестирования
Разработка тестов (набора тестовых примеров)
Исполнение программы
Соответствуют ли результаты эталонным? Если да, то перейти к действию 4, иначе перейти к 5
Достаточно ли полноты тестирования? Если да, то перейти к действию 7, иначе перейти к действию 1
Диагностика искажений
Причина искажений локализована? Если да, то
Разработка дополнительных тестов для локализации ошибок и переход к действию 2,
иначе Исправление программы. Разработка дополнительных тестов и переход к действию 2
Завершение тестирования. Регистрация результатов
Конец

110

 

Виды тестирования
Тестирование программы как «черного» ящика
Тестирование программы как «белого» ящика
Детерминированное тестирование
Стохастическое тестирование
Ручное ( без компьютера) тестирование

Виды ошибок, выявляемых при тестировании:
Неправильная постановка задачи
Неверный алгоритм
Ошибки анализа
Ошибки при выполнении операций
(деление на 0, переполнение и т.д.)
5. Ошибки ввода данных

111

 

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

 





































В предыдущих лекциях мы рассматривали программирование, связанное с обработкой

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

Операционная система MS - DOS все адресуемое пространство делит на сегменты. Сегмент - это пронумерованный участок памяти размером
64 К байт. Причем сегмент может начинаться с любого физического адреса оперативной памяти. Для задания адреса объекта программы необходимо определить адрес начала сегмента и смещение относительно начала сегмента, т.е. номер байта от начала сегмента
Адрес хранится как два слова, одно из них определяет сегмент, второе – смещение:
сегмент : смещение

Например 5Е87:0058

113

Схема распределения памяти программ на Turbo Pascal

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. П.6.1 Распределение памяти для программы на Turbo Pascal.
 
Префикс сегмента программы (Program Segment Prefix - PSP) - это 256-ти байтовая область, создаваемая DOS при загрузке программы. Адрес сегмента PSP хранится в переменной PrefixSeg.

 




































Префикс сегмента программы (Program Segment Prefix - PSP) - это

256-ти байтовая область, создаваемая DOS при загрузке программы. Адрес сегмента PSP хранится в переменной PrefixSeg.
Каждый модуль (и главная программа) имеет свой кодовый сегмент. Главная программа занимает первый кодовый сегмент; кодовые сегменты, которые следуют за ним, занимают модули (в порядке, обратном тому, как они следовали в операторе uses), и последний кодовый сегмент занимает библиотека времени выполнения (модуль System).
Сегмент данных cодержит все глобальные переменные и затем все типизированные константы. Размер сегмента данных не может превышать 64К.
Размер стекового сегмента не может превышать 64К; размер по умолчанию - 16К, он может быть изменен директивой компилятора $M.
Буфер оверлеев используется стандартным модулем Overlay для хранения оверлейного кода. Размер оверлейного буфера по умолчанию соответствует размеру наибольшего оверлея в программе; если в программе нет оверлеев, размер буфера оверлеев равен 0.

 




































Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый

раздел памяти называется динамической памятью (динамически распределяемой памятью или кучей).
Куча хранит динамические переменные. Куча занимает всю или часть свободной оперативной памяти, оставшейся после загрузки программы. Фактически размер кучи зависит от минимального и максимального значений кучи, которые могут быть установлены директивой компилятора $M:
{$M стек, мин.размер кучи, максим. размер кучи}
по умолчанию предполагаемая директива
{$M 16384, 0, 655360}
Использование динамических величин предоставляет программисту ряд дополнительных возможностей:
позволяет увеличить объем обрабатываемых данных;
если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации;
позволяет создавать динамические структуры данных.
позволяет создавать структуры данных переменного размера

 




































Объект данных обладает динамической структурой, если его размер изменяется в

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

 




































Указатели
Для работы с динамическими программными объектами в Паскале предусмотрен

ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект - адрес объекта.
Указатель – это переменная, которая в качестве своего значения содержит адрес байта памяти.
Объявление указателей
Указатель, связанный с некоторым определенным типом данных, называют типизированным указателем. Его описание имеет вид:
<Имя_переменной>: ^ <базовый-тип>;
Например:
Пример фрагмента программы объявления указателя
Type A= array [1..100] of integer;    TA= ^ A ; {тип указатель на массив} Var    P1: ^ integer; {переменная типа указатель на целое число}    P2: ^ real; {переменная типа указатель на вещественное число}
Указатель, не связанный с каким-либо конкретным типом данных, называется нетипизированным указателем. Для описания нетипизированного указателя в Паскале существует стандартный тип pointer. Описание такого указателя имеет вид:
<Имя-переменной>: pointer;

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

меняются в ходе выполнения программы.
Значения указателей – адреса переменных в памяти. Адрес занимает четыре байта и хранится в виде двух слов, одно из которых определяет сегмент, второе – смещение.
Можно передавать значения только между указателями, связанными с одним типом данных. Указатели на различные типы данных имеют различный тип, причем эти типы несовместимы.
Пример фрагмента программы объявления указателя различных типов
Var p1,p2: ^integer;    p3: ^real;    pp: pointer;    ………    p1:= p2; {допустимое действие }    p1:= p3; {недопустимое действие}
Однако это ограничение не распространяется на нетипизированный указатель. В программе допустимы будут следующие действия:
pp:= p3; p1:= pp;

и освобождение динамической памяти
Вся ДП рассматривается как сплошной массив байтов,

который называется кучей. Существуют стандартные переменные, в которых хранятся значения адресов начала, конца и текущей границы кучи:
Heaporg – начало кучи; Heapend – конец кучи;
Heapptr – текущая граница незанятой ДП.
Выделение памяти под динамическую переменную осуществляется процедурой: New (<переменная_типа_указатель>)
В результате обращения к этой процедуре указатель получает значение, соответствующее адресу в динамической памяти, начиная с которого можно разместить данные.
Пример фрагмента программы объявления указателя различных типов
Var i, j: ^integer;    r: ^real; begin    new( i); {после этого указатель i приобретает значение адреса Heapptr, а Heapptr смещается на 2 байта}    ……………    new( r) ; { r приобретает значение Heapptr, а Heapptr смещается на 6 байт}

с динамическими структурами данных

120

Освобождение динамической памяти осуществляется процедурой:
Dispose (переменная_типа_указатель)
Пример фрагмента программы
Dispose (i); {возвращает в кучу 2 байта} Dispose (r); {возвращает в кучу 6 байт}
Следует помнить, что повторное применение процедуры dispose к свободному указателю может привести к ошибке.

121

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

Присваивание значений указателю
Для инициализации указателей существует несколько возможностей.
процедура new отводит блок памяти в области динамических переменных и сохраняет адрес этой области в указателе;
специальная операция @ ориентирует переменную-указатель на область памяти, содержащую уже существующую переменную. Эту операцию можно применять для ориентации на статическую и динамическую переменную. Например, type A=array[0..99] of char; var X: array [0..49] of integer; pA:^ A; {указатель на массив символов}
Объявлены переменные разных типов: массив из 50 целых чисел и указатель на массив символов. Чтобы указатель pA указывал на массив X, надо присвоить ему адрес X pA:= @ X;

 




































Существует единственная константа ссылочного типа nil, которая обозначает «пустой»

адрес. Ее можно присваивать любому указателю.
Переменной-указателю можно присвоить значение другого указателя того же типа. Используя указательный тип pointer как промежуточный, можно присвоить значение одного указателя другому при несовпадении типов. Операции с указателями
Для указателей определены только операции присваивания и проверки на равенство и неравенство. В Паскале запрещаются любые арифметические операции с указателями, их ввод-вывод и сравнение на больше-меньше.
Еще раз повторим правила присваивания указателей:
любому указателю можно присвоить стандартную константу nil, которая означает, что указатель не ссылается на какую-либо конкретную ячейку памяти;
указатели стандартного типа pointer совместимы с указателями любого типа;
указателю на конкретный тип данных можно присвоить только значение указателя того же или стандартного типа данных.
Указатели можно сравнивать на равенство и неравенство, например:
If p1=p2 then ….. If p1<>p2 then …..

123

 

В Паскале определены стандартные функции для работы с указателями:
addr( x) – тип результата pointer, возвращает адрес x (аналогично операции @), где x – имя переменной или подпрограммы;
seg( x) – тип результата word, возвращает адрес сегмента для x;
ofs( x) – тип результата word, возвращает смещение для x;
ptr( seg, ofs) – тип результата pointer, по заданному сегменту и смещению формирует адрес типа pointer.
Присваивание значений динамическим переменным
После того, как динамическая переменная объявлена, ей можно присваивать значения, изменять их, использовать в выражениях и т.д. Для этого используют следующее обращение: <переменная_указатель>^.
Такое обращение называется операция разадресации (разыменования). Таким образом происходит обращение к значению, на которое указывает указатель, т.е. к данным. Если же за <переменной_указателем> значок ^ не стоит, то имеется в виду адрес, по которому расположены данные.
Динамически размещенные данные можно использовать в любом месте программы, где допустимо использование выражений соответствующего типа.
Например: R^:= sqr( R^) + I^ -17; q^:= 2; inc(q^); writeln(q^) :

124
Рассмотрим

пример работы с указателями:

 




































Серия последовательных обращений к New и Dispose обычно приводит
к

фрагментации памяти - память разбивается на небольшие фрагменты с
чередованием свободных и занятых участков. Дпя уменьшения явления фрагментации используют специальные процедуры.
Процедура Mark (Var p:pointer) запоминает значение HeapPtr в указателе
р, полученном в качестве параметра.
Процедура Release (Var p:pointer) - освобождает весь фрагмент памяти,
начиная с адреса р, зафиксированного в указателе процедуры Mark. Например:
new(pl); new(p2); mark(p);
new(p3); new(p4);
release(p);.,.
Динамическую память можно выделять фрагментами, указывая их размер.
Процедура GetMem (Var p:pointer; size:word) - запрашивает у системы
память размера, указанного в параметре size (запрашиваемый объем не
должен превышать 64КБ), и помещает адрес выделенного системой фрагмента
в переменную типа pointer с именем р.
Функция SizeOf(x): word- возвращает длину указанного объекта х в байтах.
Процедура FreeMem (p:pointer; size:word) - освобождает область памяти,
вьделенную процедурой GetMem.

126

 




































Динамические структуры данных
Переменные типа «указатель» обычно используют при реализации

динамических переменных, в том числе и динамических структур данных.
Динамические структуры данных могут быть организованы линейно и в
виде дерева и в виде сети.
Линейная динамическая структура представляет собой изменяемую последовательность элементов. Частными случаями таких структур являются:
• стеки, в которых разрешено добавлять элементы только в конец и удалять только последние элементы (LIFO – last in first out);
• очереди, в которых добавление элементов осуществляется в конец, а
удаление - из начала (FIFO – first in first out);
• деки, которые допускают добавление и удаление элементов и с начала, и с конца.
Списком называют структуру, в которой помимо данных хранятся также адреса элементов. Элемент списка состоит из двух частей: информационной, содержащей данные, и адресной, где хранятся указатели на следующие элементы.

 




































В зависимости от количества полей в адресной части и

порядка связывания элементов различают:
• линейные односвязные списки - единственное адресное поле содержит адрес следующего элемента, если следующий элемент отсутствует, то в адресное поле заносят константу nil ;
• кольцевые односвязные списки - единственное адресное поле содержит адрес следующего элемента, а последний элемент ссылается на первый;
• линейные двусвязные списки - каждый элемент содержит адреса предыдущего и последующих элементов, соответственно первый элемент в качестве адреса предыдущего, а последний - в качестве адреса следующего элемента содержат nil ;
• кольцевые двусвязные списки - каждый элемент содержит адреса предыдущего и последующих элементов, причем первый элемент в качестве предьщущего содержит адрес последнего элемента, а последний элемент в качестве следующего - адрес первого элемента
В древовидной структуре каждый элемент (вершина) ссылается на один или более элементов следующего уровня

129

Исходные установки
В начале программы работы с линейными динамическими структурами необходимо описать элемент и его тип:
Туре tpel=^element; {тип «указатель на элемент»}
element= record
num:mteger; {число}
p:tpel; {указатель на следующий элемент}
end;
В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан.
Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.
В статической памяти описываем переменную-указатель списка и несколько переменных-указателей, используемых при выполнении операций со списком:
Var first, {указатель списка - адрес первого элемента списка}
n,f,q:tpel; {вспомогательные указатели}
Исходное состояние «список пуст»:
first :=ml;

 





































Пример1 Разработать программу, которая строит список по типу стека

из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации клавиш CTRL-Z (конец файла на устройстве ввода). Обычно построение списка по типу стека выполняется в два этапа: в список заносится первый элемент, а затем организуется цикл добавления элементов перед первым:

Program stek;
Туре tpel=^element; {тип «указатель на элемент»}
Element = record
num : integer; {число}
p:tpel; {указатель на следующий элемент}
end;
Var first, q,f:p;
a:integer;

поле}
first ^.р:=nil; {записываем nil в поле, «адрес следующего»}
while not EOF

do
begin
ReadLn(a);
new(q); {запрашиваем память под элемент}
q^.num:=a; {заносим число в информационное поле}
q^.p:=first; {в поле «адрес следующего» переписываем адрес
первого элемента}
first:=q; {в указатель списка заносим адрес нового элемента}
end; ...

7 Работа с динамическими структурами данных 131

nil do
begin
a:=q^.num; {заносим информационное поле

в переменную a}
q:= first; {в поле «адрес следующего» переписываем адрес первого элемента}
first:=q^.p;
Dispose(q);
Writeln(‘a=‘, a);
end; ...

7 Работа с динамическими структурами данных 132

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

но отлично от нуля. Конец ввода - по комбинации CTRL-Z (конец файла на устройстве ввода). При построении списка по типу очереди сначала мы заносим в стек первый элемент, а затем организуем цикл добавления элементов после последнего, приняв во внимание, что nil необходимо разместить в адресном поле только последнего элемента:
ReadLn(a);
new(first); {запрашиваем память под элемент}
first ^.num:=а; {заносим число в информационное поле}
f:=first; {f - текущий элемент, после которого добавляется следующий}
while not EOF do
begin
ReadLn(a);
new(q); {запрашиваем память под элемент}
q^.num:-a; {заносим число в информационное поле}
f^.p:=q; {в поле «адрес следующего» предыдущего элемента
заносим адрес нового элемента}
f:= f^.p; {теперь новый элемент стал последним}
end;
q^.p:=nil; (в поле «адрес следующего» последнего элемента записываем nil}

7 Работа с динамическими структурами данных 133

 




































Динамические структуры
Линейные односвязные списки (однонаправленные цепочки).
Списком называется структура данных,

каждый элемент которой посредством указателя связывается со следующим элементом.
Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.
Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.

 




































Описание списка
Пример описания списка
Type ukazat= ^ S;    S= record       Inf:

integer;       Next: ukazat;    End;
Var u: ukazat;
Формирование списка
Создадим первый элемент списка:
New (u); {выделяем место в памяти} u^. Next:= nil; {указатель пуст} u^. Inf:=3;

136
Продолжим формирование списка.

Для этого нужно добавить элемент либо в конец списка, либо в голову.
А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:
получить память для нового элемента;
поместить туда информацию;
присоединить элемент к голове списка.
New(x); Readln(x^.Inf); x^. Next:= u; u:= x;

137
Б) Добавление элемента

в конец списка. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).
x:= hv;

Работа с динамическими структурами данных

138

x:= x^.next; x^.next:= nil; x^. inf:= 5; hv:=x;

динамическими структурами данных

139

Удаление элемента из списка
А)Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.

140

x:= u; u:= u^.next; dispose(x);
Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.

141

x:= u; while ( x<> nil) and ( x^. inf<> digit) do begin dx:= x; x:= x^.next; end; dx:= x^.next: dispose(x);

u; dx:= u; while x^.next nil do begin dx:= x;

x:= x^.next; end; dx^.next:= nil; dispose(x);
Просмотр списка.
Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.
summa:= 0; x:= u; while x<> nil do begin summa:= summa+ x^.inf; x:= x^.next; end;

7 Работа с динамическими структурами данных 142

звена из начала списка;
добавление звена в произвольное место списка,

отличное от начала (например, после звена, указатель на которое задан);
удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
проверка, пуст ли список;
очистка списка;
печать списка.

7 Работа с динамическими структурами данных 143