Второй способ статической реализации списка.

Второй способ реализации списка на основе массива использует принцип указателей (но БЕЗ динамического распределения памяти). В этом случае каждый элемент списка (кроме последнего) должен содержать номер ячейки массива, в которой находится следующий за ним элемент. Это позволяет РАЗЛИЧАТЬ физический и логический порядок следования элементов в списке. Удобно (но НЕ обязательно) в начале массива ввести фиктивный элемент-заголовок, который всегда занимает нулевую ячейку массива, никогда не удаляется и указывает индекс первого реального элемента списка. В этом случае последний элемент списка (где бы он в массиве не располагался) должен в связующей части иметь некоторое специальное значение-признак, например – индекс 0.

Схема физического размещения элементов списка в массиве:

Соответствующая схема логического следования элементов списка:

Тогда необходимые объявления могут быть следующими:

const int N=100;
struct ListItem {
int Info;
int Next;
};
ListItem StatList[N];

Рассмотрим реализацию основных списковых операций.

Условие пустоты списка: StatList[0].Next = 0;

Проход по списку:

• ввести вспомогательную переменную Current для отслеживания текущего элемента списка и установить Current = StatList[0].Next;
• организовать цикл по условию Current = 0, внутри которого обработать текущий элемент StatList[Current].Info и изменить указатель Current на следующий элемент: Current=StatList[Current].Next

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

Current = StatList[0].Next;
while (Current!= 0 && StatList[Current].Info!= ‘значение’)
Current = StatList[Current].Next;
if (Current==0)
"поиск неудачен";
else
"элемент найден";

Добавление элемента после заданного:

• проверка возможности добавления с помощью счетчика текущего числа элементов в списке
• определение каким-то образом элемента, после которого надо добавить новый элемент (например – запрос у пользователя)
• поиск этого элемента в списке; пусть его индекс есть i
• определение номера свободной ячейки массива для размещения нового элемента, пусть этот номер равен j
• формирование связующей части нового элемента, т.е. занесение туда номера ячейки из связующей части элемента i: StatList[j].Next = StatList[i].Next;
• изменение связующей части элемента i на номер j: StatList[i].Next = j;
• занесение данных в информационную часть нового элемента StatList[j].Info;

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

Алгоритм добавления элемента перед заданным включает следующие шаги:

• проверка возможности добавления с помощью счетчика текущего числа элементов в списке
• определение каким-то образом элемента, перед которым надо добавить новый элемент (например – запрос у пользователя)
• поиск этого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс заданного элемента есть i, а индекс его предшественника – s
• определение номера свободной ячейки массива для размещения нового элемента, пусть этот номер равен j
• формирование связующей части нового элемента, т.е. занесение туда индекса i: StatList[j].Next = i;
• изменение связующей части элемента-предшественника с индекса i на индекс j: StatList [s].Next = j;
• занесение данных в информационную часть нового элемента StatList[j].Info;

Удаление заданного элемента (естественно, в случае его наличия в списке) также требует изменения связующей части у элемента-предшественника. Это изменение позволяет “обойти” удаляемый элемент и тем самым исключить его из списка.

Необходимые шаги:

• определение каким-то образом удаляемого элемента (например – запрос у пользователя)
• поиск удаляемого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс удаляемого элемента есть i, а индекс его предшественника – s
• изменение связующей части элемента-предшественника с индекса i на индекс-значение связующей части удаляемого элемента i: StatList[s].Next = StatList[i].Next;
• обработка удаляемого элемента (например – вывод информационной части)
• включение удаленного элемента во вспомогательный список без его уничтожения или освобождение ячейки i с включением ее в список свободных ячеек