Динамические структуры данных. Линейный однонаправленный список с головным элементом

Курсовой  проект

по дисциплине "Технологии программирования"

Тема: «Динамические структуры данных. Линейный однонаправленный список с головным элементом».

Москва,  2010

Содержание

1.Введение

2.Задача

3.Ход работы

4.Тестирование

5.Заключение

6.Литература

Листинг функциональных частей

1.Введение

В процессе выполнения данной курсовой работы были реализованы  следующие типы динамических структур данных: список (линейный двунаправленный список с головным элементом), объекты и классы; были изучены основные принципы их функционирования. Графическая часть работы реализована с помощью canvas, графические изображения прорисовывались с помощью стандартных функций (типа rectangle, ellipse и т.д.).

              В языке программирования Delphi существует способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью.

Использование динамических величин предоставляет программисту ряд дополнительных возможностей.

Достоинства динамической памяти:

- экономичность и эффективность ее использования;

- возможность динамического изменения числа элементов в связанных структурах, например, списках (в статической памяти число элементов фиксировано для каждой компиляции);

              - статические переменные существуют только в течение жизни блока, в котором они объявлены, а динамические - и после выхода из блока до окончания программы, а на практике – столько, сколько нужно по  алгоритму;

              - переменная, размещаемая динамически, не объявляется в разделе VAR и не имеет имени в программе («невидимка»). Компилятор не планирует выделение места в памяти под такие переменные.

Наряду  с явными достоинствами стоит также упомянуть про недостатки динамической памяти.

Недостатки динамической памяти:

              - усложняются процессы выделения и освобождения динамической памяти по сравнению со статической;

              - усложняются алгоритмы обработки данных, представленных динамическими структурами.

Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы.

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

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

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

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

Информационная часть в общем случае может быть неоднородной, то есть содержать поля с информацией различных типов.

Ссылки однотипны, но число их может быть различным в зависимости от типа списка.

В связи с этим для описания элемента списка подходит только тип «запись», так как только этот тип данных может иметь разнотипные поля. Например, для однонаправленного списка элемент должен содержать как минимум два поля: одно поле типа «указатель», другое - для хранения данных пользователя. Для двунаправленного - три поля, два из которых должны быть типа «указатель».

Созданием динамических данных должна заниматься сама программа во время своего исполнения. Для этого существует специальная процедура -  New (Current). После выполнения данной процедуры в оперативной памяти ЭВМ создается динамическая переменная, тип которой определяется типом указателя Current. После использования динамического данного и при отсутствии необходимости его дальнейшего использования необходимо освободить оперативную память от этого данного с помощью процедуры – Dispose (Current).

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

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

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

Для доступа к первому элементу списка, а за ним - и к последующим элементам необходимо иметь адрес первого элемента списка. Этот адрес обычно записывается в специальное поле - указатель на первый элемент с именем  first. Если значение first равно nil, это значит, что список пуст, он не содержит ни одного элемента. Список имеет головной элемент (в данном случаи это FIRST), который также имеет ссылочное и информационное поле с информацией о количестве элементов в списке, причем данный элемент при подсчете элементов списка не считается, не участвует в удалении элементов, а удаляется только тогда, когда в списке кроме него нет элементов. 

Как известно, Delphi использует структурный объектно-ориентированный язык. А в основе ООП лежат понятия класса и его физической реализации – объекта.

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

Данные класса называются полями, подпрограммы – методами, а характеристики данных и подпрограмм – свойствами.

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

Класс объявляется на основе общего правила задания типов. Описание структуры класса в языке Delphi начинается с зарезервированного слова class, после которого в круглых скобках указывается имя родительского класса. Если он не указан, то предполагается, что родительским является класс TОbjеct, который в ООП-модели языка по умолчанию считается предком всех объявленных классов. Далее в виде отдельных строк записываются поля данных, методы и свойства. Завершается описание класса зарезервированным словом end. Если ни одного поля, метода или свойства у объявляемого класса нет, но указан непосредственный предок класса, зарезервированное слово end в конце объявления можно не писать. Последовательность записи отдельных элементов (поля, методы, свойства) класса безразлична (с учетом возможности использования одними элементами других), однако чаще всего сначала записываются поля, затем методы и, наконец, свойства.

В общем случае синтаксис объявления класса следующий:

Туре

имя класса = Class(имя класса-родителя)

public             

              // доступно всем

              <поля, методы, свойства, события>

published             

              // видны и изменяемы в Инспекторе Объектов

              <поля, свойства>

protected             

              // доступ    потомкам

              <поля, методы, свойства, события>

private              // доступ только  в модуле

<поля,   методы,   свойства,   события>

end;

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

В ряде случаев может оказаться, что два класса используют характеристики друг друга. В этом случае приходится использовать опережающее объявление одного из этих классов. При опережающем объявлении сначала записывается лишь имя класса и через знак равенства - зарезервированное слово class, например:

TObject = class;

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

Отдельные элементы класса могут иметь различные возможности по их использованию вне рассматриваемого класса (иметь разные области доступности или, иначе, видимости). В ООП DELPHI имеется несколько вариантов задания областей видимости, которые определяют разделы (секции) в описании класса и начинаются с ключевых слов private, public, protected, published и automated. Количество и порядок следования этих разделов могут быть произвольными.

В программе представители класса — объекты, объявляются в разделе var. Например, так:

var

stena:TTRoom;

pol:TTRoom;

Следует обратить особое внимание на то, что в Object Pascal объект — динамическая структура. Переменная-объект содержит не данные, а ссылку на данные объекта. Поэтому программист должен позаботиться о выделении памяти для этих данных и задании для них начальных значений.

Выделение памяти и инициализация объекта осуществляются с помощью специального метода класса — конструктора, которому обычно присваивают имя create (создать). Конструктор – это специальный метод, инициализирующий объект, содержащий виртуальные методы.

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

Пример реализации конструктора

Constructor TMyClass.Create ( Value : Integer );

Begin

              Inherited Create;

              SomeField := Value ;

End;

Реализация конструктора несколько необычна. Во-первых, в теле конструктора нет привычных операторов New, обеспечивающих выделение динамической памяти (всю необходимую работу по выделению памяти выполняет компилятор). Во-вторых, формально конструктор не возвращает значения, хотя в программе обращение к конструктору осуществляется как к методу-функции.

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

Если в программе некоторый объект больше не используется, то можно освободить память, занимаемую полями этого объекта. Для выполнения этого действия используют метод-деструктор free. Например, чтобы освободить память, занимаемую полями объекта pol, достаточно записать

pol.free;

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

В Object Pascal ограничение доступа к полям объекта реализуется с помощью свойств объекта. Свойство объекта характеризуется полем, хранящим значение свойства, и двумя методами, обеспечивающими доступ к полю свойства. Метод установки значения свойства называется методом записи свойства (write), метод получения значения свойства называется методом чтения свойства (read).

В описании класса перед именем свойства записывают ключевое слово property (свойство). После имени свойства указываются его тип, затем имена методов, обеспечивающих доступ к значению свойства. После слова read указывается имя метода, обеспечивающего чтение свойства, после слова write —имя метода, обеспечивающего запись свойства.

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

При переопределении методов различают простой и сложный полимор­физм.

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

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