Однонаправленные линейные списки паскаль

Однонаправленные линейные списки паскаль

На этом шаге мы рассмотрим однонаправленные списки .

Под списком мы будем понимать конечный упорядоченный набор объектов произвольных размера и природы.

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

Связанные списки могут иметь одиночные или двойные связи.

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

Однонаправленные списки

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

Построим модель списка при помощи определенной структуры данных, состоящей из динамических переменных. Каждый элемент списка представим записью языка Pascal, которая состоит из двух полей:

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

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

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

Рассмотрим схематичное изображение однонаправленного списка:

Рис.1. Схематичное изображение однонаправленного списка без заглавного звена

Над списками выполняются следующие операции :
• начальное формирование списка (запись первой компоненты);
• добавление компоненты в конец списка;
• определение первого элемента в линейном списке;
• чтение компоненты с заданным ключом; с заданным свойством;
• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
• исключение компоненты с заданным ключом из списка.
• упорядочивание узлов линейного списка в определенном порядке.

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

Для формирования однонаправленного списка и работы с ним необходимо описать четыре переменных типа указатель на запись. Договоримся, что pBegin определяет начало списка, а pCKey, pPredRec, pAux определим как вспомогательные (указатель на компоненту с заданным ключем, указатель на компоненту перед заданным ключем, временный указатель):

На следующем шаге мы рассмотрим формирование списка с сохранением порядка поступающих элементов .

Динамические структуры данных: однонаправленные и двунаправленные списки

Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

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

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

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

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

Линейные связные списки являются простейшими динамическими структурами данных . Из всего многообразия связанных списков можно выделить следующие основные:

• однонаправленные (односвязные) списки;
• двунаправленные ( двусвязные ) списки;
• циклические (кольцевые) списки.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

Однонаправленные (односвязные) списки

Наиболее простой динамической структурой является однонаправленный список , элементами которого служат объекты структурного типа .

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

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

struct имя_типа поле ; адресное поле ; >;

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Информационных полей может быть несколько.

Каждый элемент списка содержит ключ , который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

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

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке
• проверка пустоты списка;
• удаление списка.

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

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

Для описания алгоритмов этих основных операций используется следующее объявление:

Создание однонаправленного списка

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

Печать (просмотр) однонаправленного списка

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

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Занятие №15. Часть 1: Динамические структуры данных: указатели и списки

Динамические структуры данных

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

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

Указатели

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

• Типизированные указатели:

Универсальные нетипизированные указатели могут хранить адрес переменной любого типа:

Таким образом, указатель может находиться в одном из трех состояний:

• пока не инициализирован;
• содержит адрес размещения;
• содержит значение константы NIL; такой указатель называется пустым, то есть не указывает ни на какую переменную.

var n, k: integer; pI: ^integer; begin n := 4; pI := @n; writeln(‘Адрес n =’ , pI); writeln(‘n = ‘, pI^); k := 4*(7 — pI^); // k = 4*(7 — 4) = 12 pI^ := 4*(k — n); // n = 4*(12 – 4) = 32 end.

Другой вариант присваивания значений — использование служебного слова NEW:

var pI: ^integer; begin new(pI); pI^ := 4; writeln(‘Адрес =’ , pI); writeln(‘Значение = ‘, pI^); end.

Type rec = Record Name : string[30]; Surname: string[30]; end; var P: ^rec; begin new(P); P^.Name:=’Иван’; write(P^.Name); // Иван end.

Списки

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

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

type ukazatel = ^elem_spiska; elem_spiska = record znach:integer; next: ukazatel; end; .

Рассмотрим потребность использования динамических структур — списков на примере:

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

Алгоритм выполнения программы:

1. создать список;
2. если слова в файле закончились, то остановка;
3. считать слово и искать его в списке;
4. если слово найдено, то увеличить счетчик повторов слов, иначе добавить слово в список;
5. перейти к шагу 2.

• Список состоит из начального узла — головы — и связанного с ним списка.
• Каждый элемент списка содержит информационную и ссылочную части. Т.е. каждый элемент имеет информационное поле (поля) — полезная информация — и ссылку (ссылки), то есть адрес на другой элемент списка.
• Односвязный (линейный) список: структура, каждый элемент которой «знает» адрес только следующего за ним элемента.

Для доступа к списку достаточно необходимо знать адрес его головного элемента:

var Head: PNode; . Head := nil;

Для решения нашей задачи запрограммируем функцию для создания узла. На вход функции подается новое слово, возвращает функция адрес нового узла, созданного в памяти.

function CreateNode(NewWord: string): PNode; var NewNode: PNode; begin New(NewNode); NewNode^.word := NewWord; NewNode^.count := 1; NewNode^.next := nil; Result := NewNode; end;

Добавить узел можно:

• в начало списка;
• в конец списка;
• после заданного узла;
• до заданного узла.

Чтобы добавить узел в начало списка:

Установить ссылку нового узла на голову списка:

Обозначить новый узел как голову списка:

Выполним добавление узла списка на Паскале в виде процедуры:

procedure AddFirst ( var Head: PNode; NewNode: PNode ); begin NewNode^.next := Head; Head := NewNode; end;

Чтобы добавить узел после заданного:

Установить ссылку нового узла на узел, следующий за конкретным (p):

Установить ссылку узла p на новый узел:

Для добавления узла в конец списка или перед заданным узлом необходимо уметь перемещаться по списку.

• устанавливаем дополнительный указатель pp на голову списка;
• в случае когда дошли до конца списка, т.е.если указатель pp равен значению nil, то делаем остановку;
• производим необходимые действия над узлом с адресом pp;
• делаем переход к следующему узлу — pp^.next.

var pp: PNode; . pp := Head; // начинаем с головы while pp <> nil do begin // цикл пока не достигнут конец . // выполняем действия с pp pp := pp^.next; // переходим к следующему узлу end;

Чтобы добавить узел в конец списка:

• определить последний узел pp, для которого pp^.next равен nil;
• использовать процедуру AddAfter для добавления узла после узла с адресом pp.

Если список пуст, то алгоритм выполнения изменяется:

procedure AddLast ( var Head: PNode; NewNode: PNode ); var pp: PNode; begin if Head = nil then AddFirst ( Head, NewNode ) // добавляем в пустой список else begin pp := Head; while pp^.next <> nil do // поиск последнего узла pp := pp^.next; AddAfter ( pp, NewNode ); // после узла pp добавляем узел end; end;

Чтобы добавить узел перед заданным:

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

procedure AddBefore(var Head: PNode; p, NewNode: PNode); var pp: PNode; begin pp := Head; if p = Head then AddFirst ( Head, NewNode ) // добавление в начало списка else begin while (pp <> nil) and (pp^.next <> p) do // поиск узла, за которым следует узел p pp := pp^.next; if pp <> nil then AddAfter ( pp, NewNode ); // добавляем после узла pp end; end;

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

function Find(Head: PNode; NewWord: string): PNode; var pp: PNode; begin pp := Head; // пока не конец списка и слово в просматриваемом узле не равно искомому while (pp <> nil) and (NewWord <> pp^.word) do pp := pp^.next; Result := pp; end;

Вставка слова в определенное место списка по алфавиту

Алгоритм выполнения:
Создадим функция для поиска «подходящего» места MakePlace.
На вход функции подается вставляемое слово, возвращает же функция адрес узла, перед которым необходимо добавить слово; возвращается nil, если слово должно быть вставлено в конец списка.

function FindPlace(Head: PNode; NewWord: string): PNode; var pp: PNode; begin pp := Head; while (pp <> nil) and (NewWord > pp^.word) do pp := pp^.next; Result := pp; // слово NewWord в алфавитном порядке находится перед pp^.word end;

Для удаления конкретного узла списка необходимо знать адрес предыдущего узла pp:

Для этого создадим функцию TakeWord().
Будем игнорировать все ненужные символы, код которых ‘ ‘) do begin Result := Result + c; read(F, c); end; end;

1. Открываем файл в режиме на чтение ( var F: Text; )
2. Считывание очередного слова из файла.
3. Если слов больше не осталось (достигнут конец файла), то переходим к шагу номер 7.
4. Слово нашлось — значит, увеличиваем счетчик слов.
5. Если в списке искомого слова не существует, то выполняем:
   • создание нового узла с заполнением необходимых полей: функция CreateNode();
   • поиск узла, перед которым добавляем слово: функция MakePlace();
   • добавление узла: функция AddBefore().
6. Возвращаемся к шагу номер 2.
7. Закрываем рабочий файл.
8. Печатаем на экран список слов: для этого используем алгоритм перемещения по списку.

Двусвязные списки (двунаправленные)

Двусвязный список позволяет двигаться в обоих направлениях.
При работе с двусвязными списками создаются два указателя.

«Обнуляем» адреса головы и хвоста:

var Head, Tail: PNode; . Head := nil; Tail := nil;

Списки

Тема: Список. Создание списка путем добавления элементов в конец списка. Просмотр списка.

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

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

Схематически это выглядит так:

Попробуем вместе сформировать небольшой список путем добавления элементов в конец списка.

Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5 , 1 и 9), а в другом поле будет находится адрес следующего за ним элемента.

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

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

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

А теперь опишем переменные для решения нашей задачи:

Создадим первый элемент:

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

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

Поэтому можно записать равенства:

Выделим область памяти для следующего элемента списка.

Присвоим переменной х значение адреса выделенной области памяти, иначе, переставим указатель на вновь выделенную область памяти:

Определим значение этого элемента списка, иначе, заполним поля:

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

Задание. Запишите в тетрадь ответы на вопросы:

Какие операции требуется выполнить для вставки в список его элемента?

Можно ли для построения списка обойтись одной переменной?

Сколько элементов может содержать список?

Когда прекращать ввод элементов списка?

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

Рассмотрите формирование списка несколько другим способом.

Задание. Перепишите эту процедуру в тетрадь, дополните ее комментарием, составьте чертеж и приготовьте учителю подробное объяснение работы данной процедуры.

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

Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть

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