Линейные списки паскаль

Связные списки — новый стиль

Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме «Указатели». С другой стороны, в языке PascalABC.NET переменные класса являются ссылками на объекты, выделяемыми в динамической памяти, и являются по-существу скрытыми указателями. Поэтому заманчиво рассказать основные операции со списками, используя ссылки вместо указателей. Остроты ощущений добавляет тот факт, что в PascalABC.NET для объектов производится автоматическая сборка мусора, поэтому освобождаемую память не надо возвращать явно.

Рассмотрим основные операции с линейными односвязными списками и приведем реализацию для указателей (слева) и ссылок (справа). Всюду считается, что переменная p имеет тип PNode для указателей и Node для ссылок.

1. Предварительные описания.

Реализация с указателями — явно более «многословная». К тому же функция NewNode является внешней, и связь ее с типом PNode определяется только близостью к нему в тексте программы.

2. Вставка элемента со значением x в начало списка, на который указывает p.

Почти одинаково. Во втором случае вызывается конструктор класса Node, возвращающий ссылку на созданный объект.

3. Удаление элемента из начала непустого списка, на который указывает p.

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

4. Вставка элемента со значением x после текущего, на который указывает p.

Одно и то же. Только ^ не надо ставить — красота! Ссылка — это разыменованный указатель. Шапочки вовсе не нужны!

5. Удаление элемента, следующего за текущим, на который указывает p.

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

6. Вставка элемента со значением x перед текущим, на который указывает p.

Трюк. Вставляем после текущего элемента его копию, после чего меняем в текущем элементе значение на x. Решения равноценны.

7. Удаление текущего элемента, на который указывает p.

Элемент, следующий за текущим, должен существовать. В случае указателей мы можем скопировать оба поля за одно присваивание: p^:= t^. Но и это не помогает — код со ссылками все равно короче!

8. Вывод списка, на первый элемент которого указывает p.

9. Поиск элемента со значением x. На первый элемент списка указывает p.

Равноценные решения. Шапочек справа — нет

10. Разрушение списка.

Вот здесь — все преимущества сборки мусора. Присвоил указателю на первый узел списка нулевое значение — и все узлы стали недоступны. При следующей сборке мусора они будут собраны.

Линейные списки

Дата добавления: 2013-12-23 ; просмотров: 4315 ; Нарушение авторских прав

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

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

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

Рис. 1.1. Линейный список (связанный список)

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

current, last : ^element;

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

В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^, размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список.

В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти ⌠heap-область■. Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов.

Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New

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

Current^.data:= ‘данные в первом элементе списка ‘ ;

Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^. Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current.

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

Last^.data:= ‘данные во втором элементе списка ‘ ;

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

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

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

Рис.1.2. Двунаправленный список

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

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

Списки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Занятие №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;