Работа со списком.

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

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

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

Динамические структуры данных отличаются от статических двумя основными свойствами:

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

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

Для обращения к динамическим данным применяют указатели.

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

Mytype* element= new Mytype;

После выполнения данной процедуры в оперативной памяти ЭВМ создается динамическая переменная, тип которой определяется типом указателя Mytype.

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

delete element;

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

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

последнего элемента.

Основные операции, осуществляемые с линейным однонаправленным списком:

– вставка элемента;

– просмотр;

– поиск;

– удаление элемента.

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

В противном случае часть или весь список будет недоступен.

Для работы со списком будем использовать следующую структуру:

struct element //Структура элемента списка

{

int x; //поле с данными

element *Next; //указатель на следующий элемент списка

};

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

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

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

Пример использования:

void InsFirst_LineSingleList(element*& pHead)

{

element *temp_element= new element;

………………………………………………………………//код функции

pHead=temp_element;

}

Вызов в основной программе:

int main()

{

element *pHead= new element;//указатель на начало списка

………//код основной программы

InsFirst_LineSingleList(pHead);

………//код основной программы

delete pHead;//очистка памяти

system("pause");

return 0;

}

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

Операция просмотра списка заключается в последовательном просмотре всех элементов списка.

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

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