Top-office11.ru

IT и мир ПК
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Html задания для практики

Рассмотрим основные операции с линейными односвязными списками и приведем реализацию для указателей (слева) и ссылок (справа). Всюду считается, что переменная 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. Разрушение списка.

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

Списки

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

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

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

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

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

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

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

Читать еще:  Html dropdownlist selected

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

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, 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

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

    Связный список.

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

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

    По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки.

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

    На изображении каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil.

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

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

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

    Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

    Ссылка на основную публикацию
    Adblock
    detector
    ×
    ×