Операции над односвязным списком

Односвязные списки

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

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

В односвязном списке каждый элемент или узел списка состоит из двух различных по назначению полей: поля информации (или поля данных) и поля указателя.

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

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

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

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

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

– список удобно составлять из переменных типа запись, поскольку нужен и доступ к данным элемента, и работа с ним как с единым целым;

– список может иметь произвольный размер;

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

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

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

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

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

Операции над односвязным списком

Выделим типовые операции над списками:

- добавление элемента в начало списка;

- удаление элемента из начала списка;

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

- удаление элемента из произвольного места списка, отличного от начала (например, после элемента, указатель на который задан);

- проверка, пуст ли список;

- перестановка элементов списка;

- слияние двух списков;

- очистка списка;

- печать списка.

 

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

Data – поле данных в элементе списка;

Next – поле указателя в элементе списка;

Start – указатель на на­чало списка;

Work – рабочий указатель;

ВП(Work) – выделить память под элемент списка;

ОП(Work) – освободить память.

Если Work – указатель на элемент списка, то:

Work–>Data – зна­чение информационного поля Data,

Work–>Next – значение адреса (указателя), который хранится в поле Next.

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

Удаление элемента из списка

Удаление элемента, следующего за заданным

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

Процедура Исключить (Work1)

1. Work2 = Work1–>Next (получить адрес исключаемого элемента).

2. Work1–>Next = Work2–>Next.

3. ОП(Work2).

Удаление текущего элемента

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

1. Work2 = Work1–>Next.

2. Work1–>Data = Work2–>Data.

3. Work1–>Next = Work2–>Next.

4. ОП(Work2).

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

 

Просмотр списка

Просмотр списка выполняется с целью обработки его элементов. При последовательном просмотре списка обработка может состоять в:

- печати содержимого информационной части или отдельных ее полей;

- модификации полей информационной части;

- сравнении полей информационной части с образцом при поиске по ключу;

- подсчете количества элементов в списке;

- очистке списка и т.п.

 

Рассмотрим операцию печати элементов списка.

Процедура Печать_Списка (Start)

1. Work1 = Start.

2. Пока Work1 <> 0

3. Печать Work1–>Data.

4. Work1 = Work1–>Next.

5. Конец Пока.

В алгоритме поиска некоторого значения в списке на втором шаге добавляется еще одна проверка информационного поля на равенство искомому значению.

Функция Пусто(Start)

1. Пусто = Ложь.

2. Если Start = 0, то Пусто = Истина.

Процедура Обмен (Work1)

1. Work2 = Work1–>Next { указатель на 1-й элемент пары }

2. Work3 = Work2–>Next { указатель на 2-й элемент пары }

3. Work2–>Next = Work3–>Next; {1-й элемент пары теперь указывает на следующий за парой}

4. Work3–>Next = Work2 { 1-й элемент пары теперь следует за 2-м }

5. Work1–>Next = Work3 { 2-й эл-т пары теперь становится 1-ым }

В приведенном алгоритме не учитывается случай перестановки первого и второго элементов.

Слияние двух списков.

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

Однако алгоритм решения этой задачи содержит некоторые особенности.

Пусть заданы два указателя: Work1 и Work2 на голову первого и второго списков соответственно. Необходимо добавить элементы второго списка в хвост первого.

Односвязные списки

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

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

В односвязном списке каждый элемент или узел списка состоит из двух различных по назначению полей: поля информации (или поля данных) и поля указателя.

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

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

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

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

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

– список удобно составлять из переменных типа запись, поскольку нужен и доступ к данным элемента, и работа с ним как с единым целым;

– список может иметь произвольный размер;

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

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

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

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

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

Операции над односвязным списком

Выделим типовые операции над списками:

- добавление элемента в начало списка;

- удаление элемента из начала списка;

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

- удаление элемента из произвольного места списка, отличного от начала (например, после элемента, указатель на который задан);

- проверка, пуст ли список;

- перестановка элементов списка;

- слияние двух списков;

- очистка списка;

- печать списка.

 

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

Data – поле данных в элементе списка;

Next – поле указателя в элементе списка;

Start – указатель на на­чало списка;

Work – рабочий указатель;

ВП(Work) – выделить память под элемент списка;

ОП(Work) – освободить память.

Если Work – указатель на элемент списка, то:

Work–>Data – зна­чение информационного поля Data,

Work–>Next – значение адреса (указателя), который хранится в поле Next.

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