СД типа линейный односвязный список

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

Связный список
линейный	нелинейный
односвязный	двухсвязный	двухсвязный	многосвязный
циклический	нециклический

Простейшим связным списком является линейный односвязный список. Каждый элемент в этом списке состоит из различных по назначению полей: содержательного и поля-указателя. В поле-указателе находится адрес следующего элемента. Поле последнего указателя имеет указание на конец списка – признак nil.

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

1. Инициализация.

2. Включить элемент за рабочий указатель списка.

3. Исключить элемент, находящийся за рабочим указателем списка.

4. Передвинуть рабочий указатель на один шаг.

5. Проверка: список пуст / список не пуст.

6. Поместить рабочий указатель в начало списка (производная операция).

7. Поместить рабочий указатель в конец списка (производная операция).

8. Сделать список пустым.

При инициализации списка эффективно использовать реализацию следующей структуры:

Реализацию списка можно осуществить с помощью отображения на массив.

Рассмотрим операции включения и исключения элементов в общем случае. Введем следующие обозначения полей: Data – поле, куда записываются данные; Link – поле, где находится указатель на следующий элемент списка; Start – указатель на начало списка; Free – указатель указывающий на первый элемент свободного (рабочего) списка.

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

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

Включение элемента в список:

1. Pntr = Free;

2. Free – Link(Pntr);

3. Data(Pntr) = { };

4. Link(Pntr) – Link(Ptr) {формируем указатель в новом элементе};

5. Link(Pntr) = Pntr {модификация указателя}.

Дата добавления: 2014-01-07