Шаблон иерархической структуры данных в памяти (односвязный список, содержащий статический массив указателей на объекты)

Новосибирский государственный технический университет

Кафедра вычислительной техники

Курсовая работа

по дисциплине «Программирование»

Факультет: АВТФ
Группа: АП-218
Выполнил: Ильин М.Э.
Проверил: Романов Е. Л.

Новосибирск, 2004 г.

Содержание:

1.  Задание.

2.  Теоретический материал.

3.  Структурное описание разработки.

4.  Функциональное описание.

5.  Тесты.

6.  Выводы.

7.  Приложение: текст программы с комментариями.

Задание

Шаблон иерархической структуры данных в памяти

Для заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций  (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение строк в текстовом файле, балансировка выравнивание размерностей структур данных нижнего уровня) (см. bk57.rtf). Предполагается, что операции сравнения хранимых объектов переопределены стандартным образом (в виде операций <,> и т.д..). Программа должна использовать шаблонный класс с объектами- строками и реализовывать указанные выше действия над текстом любого объема, загружаемого из файла.

Вариант

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

Теоретический материал

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

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

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

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

Рассмотрим некоторые примеры:

- список, элемент которого содержит массив указателей

struct elem                 // Элемент односвязного списка

{

elem *next;

void *pp[20]; // Массив указателей на элементы данных

};

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

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

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

-   -в первом -"системная" и "прикладная" части структуры данных разделяются на отдельные переменные и связываются через указатель. Поскольку при работе с "системной" частью "прикладная" является неопределенной (произвольной), то такой указатель будет иметь тип void*. Но тогда при работе с "прикладной" частью потребуется преобразовать указатель void* к конкретному типу указателя на "прикладную" часть, и обратно. В "классическом" Си это может производиться по умолчанию, сопровождаясь предупреждением транслятора, в Си++ это должно быть сделано явно;