Динамическая структура данных двусвязный список

Главное меню статьи

Что же такое "Двусвязный список"
Указатель на начало двусвязного списка
Вспомогательные инструменты для проведения операций над двусвязным списком
Добавление нового элемента в начало двусвязного писка
Удаление элемента из конца двусвязного списка
Визуализация всех элементов двусвязного списка (из начала в конец)
Реализация двусвязного списка на языке программирования Pascal (ПРОГРАММА)

Чтобы более глубоко понимать материал, представленный в данной статье, ознакомьтесь с кратким очерком о классификации динамических структур данных.

Двусвязный список

Что же такое "Двусвязный список"

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

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

  2. Удаление элемента из любой позиции списка.

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

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

Указатель на начало двусвязного списка

Для корректной обработки двусвязного списка вводят понятие - указатель на начало списка. Как правило, именуется в программе подобный указатель словом beg2L (в переводе с английского begin-2-list означает - начало двойного списка). Данный указатель обязан указывать или ссылаться только на первый элемент списка, иначе список будет находиться в несогласованном состоянии. Если список не содержит ни одного элемента, то beg2L указывает в специальный участок памяти NIL.

Иногда в программах вводят указатель и на последний элемент списка, называемый end2L. Но формально стараются проводить программирование двусвязного списка только с одним указателем - beg2L.

В программе на языке Pascal декларация указателя на первый элемент двухсвязного списка выглядит примерно так:

var
{указатель на начало двухсвязного списка}
    beg2L : Tptr;

Необходимо очень отчетливо понимать, что собою представляет тип данных Tptr. Ниже представлен один из вариантов описания данного типа:

{указательный тип данных на элемент двухсвязного списка}
    Tptr = ^Telem;
{запись, состоящая из трех полей, описывающая элемент списка}
Telem = record
{информационное поле - отвечает за хранение целых чисел}
    inf   : integer;
{указательное поле на левый элемент}
    left  : Tptr;
{указательное поле на правый элемент}
    right : Tptr;
end;

Вспомогательные инструменты для проведения операций над списком

Абсолютно во всех операциях, производимых над двусвязным списком, требуется вспомогательный указатель, помимо указателя beg2L, ссылающего на первый элемент. Во всех программах и фрагментах программного кода, представленных ниже, будем обозначать вспомогательный указатель идентификатором p. Почему "p"? Потому что с английского слово pointer переводится на русский как указатель. Если требуется несколько вспомогательных указателей, то будем именовать их по принципу p1, p2, p3 и т. д.

Что же такое "NIL"?

NIL - специальный зарезервированный участок памяти, служащий "бухтой" для динамических переменных - указателей. Чтобы указатели "не болтались" в памяти, их обычно "привязывают" к NIL.

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

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

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

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

На схеме, представленной справа, динамический список состоит из трех элементов, а указателем на добавляемый элемент выступает идентификатор add.

Обратите внимание на то, что линковочные поля добавляемого элемента ссылаются в NIL - правило хорошего тона.

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

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

Удаление элемента из конца списка

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

Допустим, что заданный двусвязный список состоит из пяти динамических элементов:

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

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

Очевидно, чтобы указательную переменную p переместить на предпоследний элемент исходного списка, нам потребуется применить циклическую конструкцию. Как правило, приходится прибегать к циклу с предусловием, называемому в Pascal циклом While-Do.

Затем производим удаление крайнего элемента, используя указатель p.

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

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

В итоге двусвязный список пребывает в согласованном состоянии.

Вывод: операция удаления последнего элемента из двусвязного списка успешно проведена.

Визуализация всех элементов двусвязного списка (из начала в конец)

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

Данный линейный список пребывает в абсолютно согласованном состоянии.

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

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

Желтыми областями помечено значение информационного поля, печатаемого на дисплей пользователя элемента.

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

Реализация списка на языке программирования Pascal (ПРОГРАММА)

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

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

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

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

  • с точки зрения предметной области;

  • с научной точки зрения.

 

Программа реализует следующие операции над списком:

  1. Добавление нового автомобиля в гараж.

  2. Продажа крайнего автомобиля из гаража.

  3. Просмотр информации обо всех автомашинах, находящихся в гараже.

  4. Получение общего количества автомашин в гараже.

  5. Получение автомобилей со стоимостью выше средней стоимости.

  6. Распродажа всех автомашин гаража.

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

Если вас интересует реализация дополнительного функционала по структуре данных двусвязный список, или вы хотите познакомиться с какой-либо функцией или процедурой, не представленной в этой статье, то сообщите об этом мне, написав на электронный адрес administrator@videoege.ru.

{заголовок программы}
program DoubleList;
{раздел подключения сторонних модулей и расширений}
uses
{подключаем модуль crt - console run time, чтобы можно было использовать
 подпрограммы для работы с консолью}

    crt;
{раздел декларации собственных типов даннных}
type
{специальный тип данных, описывающий автомобиль, состоящий из трех полей}
    Tavto = record
{марка автомобиля, например: Audi, Ford, Vaz, Jaguar}
        mark  : string;
{год выпуска автомобиля, например: 2001, 2011, 1998}
        year  : integer;
{стоимость автомобиля, например: 35000, 800000, 40000}
        price : longInt;
    end;
{указательный тип данных на элемент двухсвязного списка}
    Tptr = ^Telem;
{запись, состоящая из трех полей, описывающая элемент списка}
    Telem = record
{информационное поле - хранит сведения об автомобиле}
        inf   : Tavto;
{указательное поле на левый элемент}
        left  : Tptr;
{указательное поле на правый элемент}
        right : Tptr;
    end;
{глобальный раздел описания переменных}
var
{указатель на начало двухсвязного списка}
    beg2L : Tptr;
{---------------------------------------------------------------------------}
{Добавление нового автомобиля в гараж(в начало гаража)}
{---------------------------------------------------------------------------}
procedure addAvto;
var
{вспомогательный указатель для добавления элемента}
    add : Tptr;
{начало тела процедуры}
begin
{выделяем память под добавляемый автомобиль}
    new(add);
{линковочные поля элемента устанавливаем в NIL, чтобы элемент не указывал
 на недопустимую область памяти}

    add^.left := NIL;
    add^.right := NIL;
{последовательно запрашиваем информацию об автомобиле вводом с клавиатуры:
 марка авто, год выпуска, стоимость}

    write('Введите марку автомобиля      : ');
    readln(add^.inf.mark);
    write('Введите год выпуска автомобиля: ');
    readln(add^.inf.year);
    write('Введите стоимость автомобиля  : ');
    readln(add^.inf.price);
{если список не содержит ни одного элемента, то добавляется самый первый узел}
    if(beg2L = NIL) then
        beg2L := add
{иначе в списке имеется хотя бы один элемент}
    else
    begin
{правое линковочное поле добавляемого элемента устанавливаем на первый элемент}
        add^.right := beg2L;
{левое линковочное поле первого элемента устанавливем на добавляемый узел}
        beg2L^.left := add;
{указатель на начало списка ставим на "новый первый" элемент}
        beg2L := add;
    end;
{вставка пустой строки для повышения читабельности вывода}
    writeln;
{диалог об успешном добавлении автомобиля в гараж}
    writeln('Автомобиль успешно добавлен в гараж!');
end;
{---------------------------------------------------------------------------}
{Продать крайний автомобиль}
{---------------------------------------------------------------------------}
procedure sellAvto;
var
{вспомогательный указатель для проведения операции удаления}
    p : Tptr;
{начало тела процедуры}
begin
{устанавливаем указатель-помощник на первый элемент списка}
    p := beg2L;
{если в списке нет ни одного элемента, то выпечатываем оповещение пользователю}
    if(p = NIL) then
        writeln('В гараже нет ни одного автомобиля!')
{иначе в списке содержится хотя бы один элемент}
    else
    begin
{если список содержит РОВНО ОДИН УЗЕЛ, то}
        if(p^.right = NIL) then
        begin
{удаляем данный элемент}
            dispose(p);
{указатель на начало списка ставим в NIL}
            beg2L := NIL;
        end
{список содержит больше одного элемента}
        else
        begin
{необходимо вспомогательный указатель установить на предпоследний элемент}
            while(p^.right^.right <> NIL) do
{переход к следующему элементу списка}
                p := p^.right;
{удаляем последний элемент, используя указатель, установленный на предпоследний
 узел списка. Обратите внимание на запись данной операции}

            dispose(p^.right);
{необходимо, чтобы правое линковочное поле последнего элемента ссылалось в NIL}
            p^.right := NIL;
        end;
{вставка пустой строки для повышения читабельности}
        writeln;
{оповещение пользователя об успешном удалении авто из гаража}
        writeln('Автомобиль успешно удален из гаража!');
    end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Вывод всех автомобилей на экран}
{---------------------------------------------------------------------------}
procedure printAllAvto;
var
{вспомогательный указатель, помогающий провести операцию визуализации}
    p : Tptr;
begin
{устанавливаем указатель-помощник на первый элемент списка}
    p := beg2L;
{если список не содержит ни одного элемента}
    if(p = NIL) then
{оповещаем пользователя, что в гараже не обнаружено ни одного авто}
        writeln('В гараже нет ни одного автомобиля!')
{иначе список содержит минимум один элемент}
    else
    begin
{диалог пользователю}
        writeln('Автомобили гаража: ');
        writeln('-----------------------------------------------');
{до тех пор, пока указатель не пробежит по всем элементам списка начинаем
 циклически его просматривать}

        while(p <> NIL) do
        begin
{выпечатываем информацию о текущем узле (в данном случае автомобиле)}
            writeln('Марка      : ', p^.inf.mark);
            writeln('Год выпуска: ', p^.inf.year);
            writeln('Стоимость  : ', p^.inf.price);
            writeln('-----------------------------------------------');
{переход к следующему элементу списка}
            p := p^.right;
        end;
    end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Получение общего количества машин в гараже}
{---------------------------------------------------------------------------}
function getCountAvto : integer;
var
{вспомогательный указатель, помогающий определить количество авто в гараже}
    p : Tptr;
{хранит количество автомобилей в гараже}
    k : integer;
{начала тела функции}
begin
{так как рассчет количества еще не начался, то обнулем счетчик}
    k := 0;
{устанавливаем указатель р на первый элемент списка}
    p := beg2L;
{пока указатель не выйдет в NIL начинаем циклически бежать по списку}
    while(p <> NIL) do
    begin
{увеличиваем счетчик автомобилей в гараже на единицу}
        k := k + 1;
{переход к следующему элементу списка}
        p := p^.right;
    end;
{функция в качестве ответа возвращает количество авто в гараже}
    getCountAvto := k;
{конец тела функции}
end;
{---------------------------------------------------------------------------}
{Получение машин со стоимостью выше средней}
{---------------------------------------------------------------------------}
procedure avtoPrice;
var
{вспомогательный указатель для обработки списка}
    p    : Tptr;
{отвечает за среднюю стоимость всех автомобилей гаража}
    aver : real;
{начало тела процедуры}
begin
{устанавливаем указатель р на первый элемент списка}
    p := beg2L;
{если в гараже есть хотя бы один автомобиль, то}
    if(p <> NIL) then
    begin
{обнуляем переменную, отвечающую за среднее значение стоимости}
        aver := 0;
{пока р не прошел по всем автомобилям}
        while(p <> NIL) do
        begin
{считаем сумму стоимости всех авто в гараже}
            aver := aver + p^.inf.price;
{переход к следующей автомашине}
            p := p^.right;
        end;
{средняя стоимость - сумма всех автомашин, деленная на их количество, то есть}
        aver := aver / getCountAvto;
{выпечатываем значение средней стоимости авто на экран пользователя}
        writeln('Средняя стоимость автомашины: ', aver:5:2);
{вставка пустой строки для повышения читабельности}
        writeln;
{снова ставим вспомогательный указатель р на начало списка}
        p := beg2L;
{пока не будут просмотрены все автомашины гаража}
        while(p <> NIL) do
        begin
{если стоимость текущего авто больше средней стоимости, то}
            if(p^.inf.price > aver) then
            begin
{выпечатываем информацию о данной машине на дисплей пользователя}
                writeln('Марка      : ', p^.inf.mark);
                writeln('Год выпуска: ', p^.inf.year);
                writeln('Стоимость  : ', p^.inf.price);
                writeln('-----------------------------------------------');
            end;
{переходим к анализу следующего автомобиля}
            p := p^.right;
        end;
    end
{иначе в гараже отсутствуют машины}
    else
{диалог пользователю об отсутствии машин}
        writeln('В гараже нет ни одной автомашины!');
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Продажа всех машин из гаража}
{---------------------------------------------------------------------------}
procedure sellAllAvto;
var
{вспомогательный указатель, помогающий провести продажу всех авто из гаража}
    p : Tptr;
{начало тела процедуры}
begin
{устанавливаем указатель-помощник на первый элемент списка}
    p := beg2L;
{до тех пор, пока не будут проданы все авто начинаем их по одной продавать}
    while(beg2L <> NIL) do
    begin
{перемещаем указатель на начало списка на второй элемент}
        beg2L := p^.right;
{удаляем первый элемент}
        dispose(p);
{указатель-помощник опять позиционируем на "новый" первый элемент}
        p := beg2L;
    end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Главное меню программы}
{---------------------------------------------------------------------------}
function menu : integer;
var
{хранит пункт меню выбранный пользователем}
    sel : integer;
{начало тела функции}
begin
{циклически визуализируем меню программы до тех пор, пока пользователь не
 укажет допустимый пункт}

    repeat
        clrscr;
        writeln('1 - ДОБАВИТЬ НОВЫЙ АВТОМОБИЛЬ В ГАРАЖ');
        writeln('2 - ПРОДАТЬ ВЫБРАННЫЙ АВТОМОБИЛЬ');
        writeln('3 - ПРОСМОТРЕТЬ ВСЕ АВТОМОБИЛИ В ГАРАЖЕ');
        writeln('4 - УЗНАТЬ ОБЩЕЕ КОЛИЧЕСТВО В ГАРАЖЕ');
        writeln('5 - ВЫВЕСТИ АВТОМОБИЛИ СО СТОИМОСТЬЮ ВЫШЕ СРЕДНЕЙ');
        writeln('6 - ЗАКРЫТЬ ГАРАЖ (РАСПРОДАТЬ ВСЕ МАШИНЫ)');
        writeln('7 - ВЫХОД');
        write('Выбор: ');
        readln(sel);
    until((sel >= 1) and (sel <= 7));
    writeln;
{функция в качестве ответа возвращает номер выбранного пункта}
    menu := sel;
{конец тела функции}
end;
{---------------------------------------------------------------------------}
{раздел описания локальных переменных}
var
{отвечает за пункт меню выбранный пользователем}
    sel : integer;
{начало главного блока программы}
begin
{инициализируем список - устанавливаем указатель на начало списка в NL}
    beg2L := NIL;
{отображем меню программы перед пользователем и после выбора пользователя
 выполняем соответствующее действие}

    repeat
{вызов главного меню}
        sel := menu;
        case sel of
        1:
        begin
{добавление автомобиля в гараж}
            addAvto;
            readkey;
        end;
        2:
        begin
{продажа автомобиля}
            sellAvto;
            readkey;
        end;
        3:
        begin
{вывод информации обо всех машинах, находящихся в гараже}
            printAllAvto;
            readkey;
        end;
        4:
        begin
{получение количества автомашин в гараже}
            writeln('В гараже автомашин: ', getCountAvto, ' шт.');
            readkey;
        end;
        5:
        begin
{полуение информации об авто, имеющий стоимосить выше средней стоимости}
            avtoPrice;
            readkey;
        end;
        6:
        begin
{распродажа всех автомобилей}
            sellAllAvto;
            writeln('Все автомобили успешно проданы!');
            readkey;
        end;
        end;
    until(sel = 7);
{если машины не были распроданы, то распродаем их}
    sellAllAvto;
{финализирующий оператор программы}
end.

 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?
Занятия по информатике