Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Занятие 3. Список. Создание списка путем добавления элементов в конец списка. Просмотр спискаСодержание книги
Поиск на нашем сайте
Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil). Схематически это выглядит так: Попробуем вместе сформировать небольшой список путем добавления элементов в конец списка. Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9. Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5, 1 и 9), а в другом поле будет находится адрес следующего за ним элемента. Примечание. Нужно понимать, что поле данных вообще говоря может содержать в себе сколько угодно полей; это зависит от конкретно поставленной задачи. Type Ukazatel = ^S; S = record Data: integer; Next: Ukazatel; end; Таким образом, мы описали ссылочный тип, с помощью которого можно создать наш связанный однонаправленный список. Заметим, что все элементы списка взаимосвязаны, т. е. где находится следующий элемент, "знает" только предыдущий. Поэтому самое главное в программе, это не потерять, где находится начало списка. Поэтому на начало списка будем ставить указатель с именем Head и следить за тем, чтобы на протяжении выполнения программы значение этого указателя не менялось. А теперь опишем переменные для решения нашей задачи: Var Head, {указатель на начало списка} x {вспомогательный указатель для создания очередного элемента списка} : Ukazatel; Создадим первый элемент: new(x); {выделим место в памяти для переменной типа S} x^.Data:= 3; {заполним поле Data первого элемента} x^.Next:= Nil; {заполним поле Next первого элемента: указатель в Nil} Head:= x; {поставим на наш первый элемент указатель головы списка} Таким образом, к выделенной области памяти можно обратиться через два указателя. Продолжим формирование списка, для этого нужно добавить элемент в конец списка. Поэтому вспомогательная переменная указательного типа х будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом. Поэтому можно записать равенства: Head^.Next = x^.Next; Head^.Data = x^.Data; Head = x; Выделим область памяти для следующего элемента списка. new(x^.Next);
Присвоим переменной х значение адреса выделенной области памяти, иначе, переставим указатель на вновь выделенную область памяти: x:= x^.Next;
Определим значение этого элемента списка, иначе, заполним поля: x^.Data:= 5; x^.Next:= Nil;
Итак, теперь у нас список содержит два элемента. Понятно, чтобы создать третий и четвертый элементы, нужно проделать те же самые операции. Задание. Запишите в тетрадь ответы на вопросы: 1. Какие операции требуется выполнить для вставки в список его элемента? 2. Можно ли для построения списка обойтись одной переменной? 3. Сколько элементов может содержать список? 4. Когда прекращать ввод элементов списка? 5. Запишите в тетрадь рассмотренные операторы и дополните их операторами, создающими третий и четвертый элементы списка (1, 9). Теперь попробуем подытожить наши рассуждения.Оформим создание списка в виде процедуры, в которой его элементы вводятся с клавиатуры. Procedure Init(Var u: Ukazatel); Var x: Ukazatel; Digit: integer; {Значение информационной части элемента списка} Begin writeln('Введите список '); Head:= Nil; {Список пуст} writeln ('Введите элементы списка. Конец ввода 0'); read (Digit); if Digit <> 0 then {Формируем и вставляем первый элемент списка} begin new(x); x^.Next:= Nil; x^.Data:= Digit; Head:= x read (Digit); while Digit<>0 do begin new(x^.Next); {Формируем и вставляем элемент в конец списка} x:= x^.Next; x^.Next:= Nil; x^.Data:= Digit; read(Digit); end; writeln; End; Рассмотрите формирование списка несколько другим способом. Procedure Init(Var u: Ukazatel); Var x, y: Ukazatel; Digit: integer; Begin writeln('Введите список '); Head:= Nil; writeln ('Введите элементы списка. Конец ввода 0'); read (Digit); while Digit<>0 do begin new(y); y^.Next:= Nil; y^.Data:= Digit; if u=Nil then u:= y else x^.Next:= y; x:= y; read(Digit); end; writeln; End; Задание. Перепишите эту процедуру в тетрадь, дополните ее комментарием, составьте чертеж и приготовьте учителю подробное объяснение работы данной процедуры. Просмотр списка Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть while p<>Nil do begin write(p^.Data, ' '); p:= p^.Next; end; Задание. Составьте программу, содержащую процедуру создания списка путем вставки элементов в конец списка и процедуру просмотра списка и вывода на экран его элементов. Процедуры должны содержать параметр, в который передается начало списка. Покажите протестированную программу и листинг учителю для оценки.
|
||||
Последнее изменение этой страницы: 2016-08-12; просмотров: 182; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.239.209 (0.006 с.) |