Добавление элемента в список паскаль

Списки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме «Указатели». С другой стороны, в языке 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. Разрушение списка.

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

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

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

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

Добавление элемента в список

Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.

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

Рис. 8.8. Добавление элемента в упорядоченный список

Рис. 8.9. Диалоговое окно программы Упорядоченный динамический список 2

Следующая программа, ее текст приведен в листинге 8.5, а диалоговое окно — на рис. 8.9, формирует список, упорядоченный по полю Фамилия. Данные вводятся в поля редактирования (есїітці и есїіі;2) и нажатием кнопки Добавить (Витопі) добавляются в список таким образом, что список всегда упорядочен по полю Фамилия.

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

procedure ButtonlClick(Sender: TObject); procedure Button2Click(Sender: TObject); procedure FormActivate(Sender: TObject); private < Private declarations >public

<$R *.DFM>type TPStudent=/4TStudent; //указатель на тип TStudent

f_name:string[20]; // фамилия l_name:string[20]; // имя

next: TPStudent; // следующий элемент списка

end; var head: TPStudent; // начало (голова) списка

procedure TForml.ButtonlClick(Sender: TObject); var node: TPStudent; // новый узел списка curr: TPStudent; // текущий узел списка

pre: TPStudent; // предыдущий, относительно curr, узел begin new(node); // создание нового элемента списка node74. f_name:=Editl.Text; // фамилия node74.1 name:=Edit2 .Text; // имя

// добавление узла в список

Если приведенное ниже условие заменить на (node. f_name>curr». f_name) and (curroNIL), то при добавлении первого узла возникает ошибка времени выполнения, т, к, curr = NIL и, следовательно, переменной curr. лпате нет!

В используемом варианте условия ошибка не возникает, т. к. сначала проверяется условие (curr о NIL), значение которого FALSE, и второе условие в этом случае не проверяется.

procedure TForml.Button2Click(Sender: TObject); var curr: TPStudent; // текущий элемент списка n:integer; // длина (кол-во элементов) списка st:string; // строковое представление списка

curr:=сиггл.next; end; if n о 0

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

Вывод списка выполняет процедура TForml. Button2ciick, которая запускается нажатием кнопки Показать. После запуска программы и ввода нескольких фаМИЛИЙ, Например, В ТаКОЙ Последовательности: Иванов, Яковлев, Алексеев, петров, список выглядит так, как показано на рис. 8.10.

Рис. 8.10. Пример упорядоченного списка, сформированного программой