Тема 3. Основы реализации списковых структур

3.1. Структуры данных типа “линейный перечень”

Линейный перечень – это набор связанных однотипных частей, в каком каждый элемент каким-то образом определяет последующий за ним элемент. В отличие от стека и очереди, добавление нового элемента может быть в любом месте перечня, также можно удалить хоть какой элемент перечня. Ясно, что списковые структуры являются более гибкими, да Тема 3. Основы реализации списковых структур и мало более сложными в реализации. Практически, стеки и очереди можно считать личными вариантами списков, в каких добавление и удаление частей может производиться лишь на концах.

Стандартный набор операций со перечнем включает:

· добавление нового элемента после данного либо перед данным элементом с проверкой способности прибавления элемента

· удаление данного элемента

· проход по списку Тема 3. Основы реализации списковых структур от первого элемента к последнему с выполнением данных действий

· поиск в перечне данного элемента

Как обычно, вероятна статическая и динамическая реализация списков. При всем этом статическая реализация на базе массива может быть выполнена 2-мя методами.

3.2. 1-ый метод статической реализации перечня.

Он основан на том, что логический номер элемента перечня вполне соответствует номеру Тема 3. Основы реализации списковых структур ячейки массива, где этот элемент хранится: 1-ый элемент перечня – в первой ячейке массива, 2-ой – во 2-ой, 3-ий – в третьей и т.д.

Элемент 1 Элемент 2 Элемент 3 . . . . . . . Элемент N

Проверка наличия в массиве хотя бы 1-го элемента и хотя бы одной свободной ячейки производится тривиально при помощи счетчика Тема 3. Основы реализации списковых структур числа частей перечня. Проход по списку – также прост. Поиск данного элемента сводится к обыкновенному поиску в массиве.

Как выполнить вставку нового элемента снутри перечня, к примеру – в ячейку с номером i < N ? Для освобождения ячейки i все элементы перечня начиная с номера i и до N нужно двинуть на Тема 3. Основы реализации списковых структур право на одну ячейку (естественно, если в массиве еще есть хотя бы одна свободная ячейка). Копирование нужно начинать с последней ячейки, т.е. N – на место N+1, N-1 – на место N, и.т.д. i – на место i+1. В освободившуюся ячейку i записывается новый элемент.

Аналогично (с точностью до напротив) производится удаление хоть Тема 3. Основы реализации списковых структур какого внутреннего элемента: освобождается ячейка i и все следующие элементы сдвигаются на лево на одну ячейку, т.е. i+1 – на место i, i+2 – на место i+1, и т.д., элемент N – в ячейку N-1.

Появляется вопрос о трудозатратности выполнения схожих операций перемещения ячеек массива. Если каждый элемент перечня Тема 3. Основы реализации списковых структур, размещенный в одной ячейке массива представляет собой запись с огромным числом объемистых полей, то издержки на схожее перемещение могут стать очень большенными. Тут выходом может быть изменение структуры элемента перечня: в массиве хранятся ТОЛЬКО УКАЗАТЕЛИ (АДРЕСА) информационных частей и перемещение делается только этих указателей, сами информационные части остаются Тема 3. Основы реализации списковых структур на собственных местах. Беря во внимание все растущие скорости работы современных микропроцессоров и наличие в их архитектуре стремительных команд группового копирования байтов, можно считать данный способ реализации списков полностью работоспособным.

3.3. 2-ой метод статической реализации перечня.

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

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

Номер ячейки
Информац. часть заголовок Элем. 3 Элем. 1 Элем. 2 Элем. 4
Последующий эл-нт Тема 3. Основы реализации списковых структур

Соответственная схема логического следования частей перечня:


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

Const N = 100;

TypeTListItem = record

Inf : ;

Next : integer;

end;

Var StatList : array [0 . . N] of TListItem;

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

Условие пустоты перечня: StatList [ 0 ].Next = 0;

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

· ввести вспомогательную переменную Current для отслеживания текущего элемента перечня и установить Current := StatList [ 0 ].Next;

· организовать цикл по Тема 3. Основы реализации списковых структур условию Current = 0, снутри которого обработать текущий элемент StatList [ Current ].Inf и поменять указатель Current на последующий элемент: Current := StatList [ Current ].Next

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

Current := StatList [ 0 ].Next;

While (Current 0) and (StatList [ Current ].Inf ‘значение’ do

Current := StatList [ Current ].Next;

If Current = 0 then ‘поиск неудачен’ else ‘элемент найден’;

Добавление элемента Тема 3. Основы реализации списковых структур после данного:

· проверка способности прибавления при помощи счетчика текущего числа частей в перечне

· определение каким-то образом элемента, после которого нужно добавить новый элемент (к примеру – запрос у юзера)

· поиск этого элемента в перечне; пусть его индекс есть i

· определение номера свободной ячейки массива для размещения нового элемента (способы определения подвергнутся рассмотрению Тема 3. Основы реализации списковых структур ниже); пусть этот номер равен j

· формирование связывающей части нового элемента, т.е. занесение туда номера ячейки из связывающей части элемента i : StatList [ j ].next := StatList [ i ].next;

· изменение связывающей части элемента i на номер j: StatList [ i ].next := j;

· занесение данных в информационную часть нового элемента StatList[j].inf;


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

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

· проверка способности прибавления при помощи счетчика текущего числа частей в перечне

· определение каким-то образом элемента, перед которым нужно добавить новый элемент (к примеру – запрос у юзера)

· поиск этого элемента в перечне с одновременным отслеживанием Тема 3. Основы реализации списковых структур элемента-предшественника; пусть индекс данного элемента есть i, а индекс его предшественника - s

· определение номера свободной ячейки массива для размещения нового элемента (способы определения подвергнутся рассмотрению ниже); пусть этот номер равен j

· формирование связывающей части нового элемента, т.е. занесение туда индекса i : StatList [ j ].next := i;

· изменение Тема 3. Основы реализации списковых структур связывающей части элемента-предшественника с индекса i на индекс j: StatList [ s ].next := j;

· занесение данных в информационную часть нового элемента StatList[j].inf;


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

Нужные шаги:

· определение каким-то образом удаляемого элемента (к примеру – запрос у юзера)

· поиск удаляемого элемента в перечне с одновременным отслеживанием элемента-предшественника; пусть индекс удаляемого элемента есть i, а индекс его предшественника - s

· изменение связывающей части элемента-предшественника с индекса i на индекс-значение связывающей части удаляемого элемента Тема 3. Основы реализации списковых структур i: StatList [s].next := StatList [ i ].next;

· обработка удаляемого элемента (к примеру – вывод информационной части)

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


tema-3-pravo-prirodopolzovaniya-i-pravovie-formi-rabochaya-programma-disciplini-specialnost-030501-65-yurisprudenciya.html
tema-3-pravovie-formi-ispolzovaniya-zemel-programma-disciplini-zemelnoe-pravo-cikl-opd-f-16-obsheprofessionalnie.html
tema-3-pravovoj-rezhim-obektov-kommercheskogo-prava.html