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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



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



Последнее изменение этой страницы: 2016-08-15; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.239.170.169 (0.008 с.)