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

Страницы работы

Фрагмент текста работы

текущий обьект и ссылку на следующий обьект и непосредственно сам обьект.

Особенностью циклического двусвязного списка является то, что не надо решать проблемы концов списка, то есть  вместо указателей NULL записывать:

 -указатель на последний элемент в качестве указателя на предыдущий в первом элементе списка;

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

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

Положительной стороной использования списков является меньшая трудоемкость вставки элемента по логическому номеру, а отрицательной – извлечение по логическому номеру и поиск значения.


В данном проекте реализована работа со структурой данных, создаваемым классом сstring(подключается библиотекаcstring.h).

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

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

В начале работы создается новый элемент списка.

Добавление объекта в конец списка.

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

Добавление объекта по логическому номеру

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

Добавление с сохранением порядка.

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

Извлечение по логическому номеру.

Все начинается с того, что вводится некоторый логический номер, по которому и нужно инайти объект.

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

Похожие материалы

Информация о работе