Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Связанные динамические списки






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

 

 

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

§ информационная часть;

§ часть, обеспечивающая связь cо следующим (возможно с предыдущим элементом списка). Список, в котором обеспечивается связь только со следующим элементом, называется односвязанным.

 

 

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

 

Type p_stud=^Student;

{^ Student – тип указателя, который обеспечивает связь между
элементами списка}

Student = record {запись Student описывает тип элемента списка}

Fam: string[20 ];

Name: string[15]; { информационная часть элемента}

Grup: integer;

Adress: string[60];

Next: p_stud; {указатель на следующий элемент списка }

End;

Var head: p_stud; {указатель на первый элемент списка }

Тип Student необходим для описания типа указателя p_stud. Указатель невозможно описать без раздела type, в то же время тип p_stud нужен для описания поля Next в записи Student. Таким образом, идентификатор Student используется до его описания, этим нарушается одно из требований языка Pascal, Это исключение сделано только для описания указателей, чтобы сделать возможным создание связанных структур.

Добавлять данные можно в начало, в конец, в нужное место списка.

Во всех этих случаях необходимо корректировать указатели.

Изобразим схематически процесс добавления элементов в начало односвязанного списка.

1. Список пустой, указатель head ни на что не указывает (nil).

head

 
 


· т

 

2. После добавления первого элемента head указывает на этот элемент.

head

 
 

 

 


3.После добавления второго элемента в начало списка head указывает на этот новый элемент (curr – указатель на текущий элемент).

 

Head

 
 

 


 
 

 

 


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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.