Курсовая работа: Односвязный список на основе указателей

5.Распечатка списка

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

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

2. Общие положения

Абстрактный список можно реализовать в виде массива – на первый взгляд, очевидный шаг. Массив имеет фиксированный размер (в большинстве языков программирования), в то время как длина абстрактного списка неограничена. Таким образом, структура данных становится статической, что является недостатком.

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

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

Каждый узел связанного списка состоит из двух частей: непосредственно данных и указателя на следующий элемент – такой же узел или константу NULL .

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

Механизм выделения памяти под элементы списка, основанного на указателях, предполагает динамическое выделение памяти при помощи операторов new и delete . Таким образом, при создании нового элемента имеет смысл выделять память только лишь под новые данные, а не под уже определенные методы – операции списка. Следовательно, необходимо вынести методы из структуры данных. В данной работе, была применена методика расширения интерфейса созданием структуры методов – дружественного класса, методы которого имеют доступ к закрытым членам класса узла.

Подробней о принципах объектно-ориентированного программирования можно узнать из [1, 3].

Указатели на голову и хвост списка объявлены в классе List поскольку по сути необходимы для реализации методов АТД, в то время как для самой структуры данных они не имеют ни малейшего смысла.

Методы, которые не должны никоим образом модифицировать данные, объявлены с использованием ключевого слова const.

3. Описание операций

3.1 Разработка операции добавления элемента

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

Предусловие: список существует

Постусловие: указатель на хвост указывает на созданный элемент

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

Следует отметить, что указатели в С++ должны быть инициализированы. Так как список изначально создается пустым, указатели должны быть инициализированы константой NULL. Это операция реализуется в конструкторе по умолчанию класса List:

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

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

Процесс связываения узлов отличается в зависимости от того, пуст ли список или нет.

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

Операция добавления (по умолчанию) элемента в пустой список:

Операция добавления элемента в конец списка:

Макрос assert, определенный в библиотеке cassertпроверяет была ли выделена память под узлы корректным образом.