Аналитический обзор литературы

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………………5

1. Аналитический обзор литературы и существующих аналогов

1.1. Аналитический обзор литературы………………..………………….…...6

1.2 Обзор существующих аналогов……………………………………….....12

2. Разработка алгоритма………………………………………………………….14

3. Разработка программного средства ……………………………………….....18

4. Обоснование технических приемов программирования……………………21

5. Тестирование, экспериментальные исследования и анализ полученных результатов………………………………………………………………………...22

6. Руководство пользователя программы ………………………………………25

ЗАКЛЮЧЕНИЕ…………………………………………………………………….29

Список литературы………………………………………………………………..30

Листинг программы……………………………………………………………….31

ВВЕДЕНИЕ

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

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

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

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

Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: снача­ла ищется указатель, затем по нему — величина.

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

Запись

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

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

Абстрактный тип данных «список»

В математике список представляет собой последовательность элементов определенного типа: а₁, а₂, …..а_n, где n≥0 и все а_i имеют один тип. Количество, n – длина списка, если n ≥ 1, то а₁ – первый элемент, а а_n – последний, в случае n = 0 имеем пустой список.

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

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

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

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

1. Аналитический обзор литературы и существующих аналогов

Аналитический обзор литературы

Возможны несколько вариантов представления и хранения необходимых для работы программы данных.

Рассмотрим некоторые из них

1.1.1 Статические массивы.

Массив –это набор однотипных компонентов (элементов), расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (индексам).

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

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

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

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

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

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