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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. {указательный тип данных на элемент двухсвязного списка}
  2.     Tptr = ^Telem;
  3. {запись, состоящая из трех полей, описывающая элемент списка}
  4. Telem = record
  5. {информационное поле - отвечает за хранение целых чисел}
  6.     inf   : integer;
  7. {указательное поле на левый элемент}
  8.     left  : Tptr;
  9. {указательное поле на правый элемент}
  10.     right : Tptr;
  11. 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.

  1. {заголовок программы}
  2. program DoubleList;
  3. {раздел подключения сторонних модулей и расширений}
  4. uses
  5. {подключаем модуль crt - console run time, чтобы можно было использовать
  6.  подпрограммы для работы с консолью}
  7.     crt;
  8. {раздел декларации собственных типов даннных}
  9. type
  10. {специальный тип данных, описывающий автомобиль, состоящий из трех полей}
  11.     Tavto = record
  12. {марка автомобиля, например: Audi, Ford, Vaz, Jaguar}
  13.         mark  : string;
  14. {год выпуска автомобиля, например: 2001, 2011, 1998}
  15.         year  : integer;
  16. {стоимость автомобиля, например: 35000, 800000, 40000}
  17.         price : longInt;
  18.     end;
  19. {указательный тип данных на элемент двухсвязного списка}
  20.     Tptr = ^Telem;
  21. {запись, состоящая из трех полей, описывающая элемент списка}
  22.     Telem = record
  23. {информационное поле - хранит сведения об автомобиле}
  24.         inf   : Tavto;
  25. {указательное поле на левый элемент}
  26.         left  : Tptr;
  27. {указательное поле на правый элемент}
  28.         right : Tptr;
  29.     end;
  30. {глобальный раздел описания переменных}
  31. var
  32. {указатель на начало двухсвязного списка}
  33.     beg2L : Tptr;
  34. {---------------------------------------------------------------------------}
  35. {Добавление нового автомобиля в гараж(в начало гаража)}
  36. {---------------------------------------------------------------------------}
  37. procedure addAvto;
  38. var
  39. {вспомогательный указатель для добавления элемента}
  40.     add : Tptr;
  41. {начало тела процедуры}
  42. begin
  43. {выделяем память под добавляемый автомобиль}
  44.     new(add);
  45. {линковочные поля элемента устанавливаем в NIL, чтобы элемент не указывал
  46.  на недопустимую область памяти}
  47.     add^.left := NIL;
  48.     add^.right := NIL;
  49. {последовательно запрашиваем информацию об автомобиле вводом с клавиатуры:
  50.  марка авто, год выпуска, стоимость}
  51.     write('Введите марку автомобиля      : ');
  52.     readln(add^.inf.mark);
  53.     write('Введите год выпуска автомобиля: ');
  54.     readln(add^.inf.year);
  55.     write('Введите стоимость автомобиля  : ');
  56.     readln(add^.inf.price);
  57. {если список не содержит ни одного элемента, то добавляется самый первый узел}
  58.     if(beg2L = NIL) then
  59.         beg2L := add
  60. {иначе в списке имеется хотя бы один элемент}
  61.     else
  62.     begin
  63. {правое линковочное поле добавляемого элемента устанавливаем на первый элемент}
  64.         add^.right := beg2L;
  65. {левое линковочное поле первого элемента устанавливем на добавляемый узел}
  66.         beg2L^.left := add;
  67. {указатель на начало списка ставим на "новый первый" элемент}
  68.         beg2L := add;
  69.     end;
  70. {вставка пустой строки для повышения читабельности вывода}
  71.     writeln;
  72. {диалог об успешном добавлении автомобиля в гараж}
  73.     writeln('Автомобиль успешно добавлен в гараж!');
  74. end;
  75. {---------------------------------------------------------------------------}
  76. {Продать крайний автомобиль}
  77. {---------------------------------------------------------------------------}
  78. procedure sellAvto;
  79. var
  80. {вспомогательный указатель для проведения операции удаления}
  81.     p : Tptr;
  82. {начало тела процедуры}
  83. begin
  84. {устанавливаем указатель-помощник на первый элемент списка}
  85.     p := beg2L;
  86. {если в списке нет ни одного элемента, то выпечатываем оповещение пользователю}
  87.     if(p = NIL) then
  88.         writeln('В гараже нет ни одного автомобиля!')
  89. {иначе в списке содержится хотя бы один элемент}
  90.     else
  91.     begin
  92. {если список содержит РОВНО ОДИН УЗЕЛ, то}
  93.         if(p^.right = NIL) then
  94.         begin
  95. {удаляем данный элемент}
  96.             dispose(p);
  97. {указатель на начало списка ставим в NIL}
  98.             beg2L := NIL;
  99.         end
  100. {список содержит больше одного элемента}
  101.         else
  102.         begin
  103. {необходимо вспомогательный указатель установить на предпоследний элемент}
  104.             while(p^.right^.right <> NIL) do
  105. {переход к следующему элементу списка}
  106.                 p := p^.right;
  107. {удаляем последний элемент, используя указатель, установленный на предпоследний
  108.  узел списка. Обратите внимание на запись данной операции}
  109.             dispose(p^.right);
  110. {необходимо, чтобы правое линковочное поле последнего элемента ссылалось в NIL}
  111.             p^.right := NIL;
  112.         end;
  113. {вставка пустой строки для повышения читабельности}
  114.         writeln;
  115. {оповещение пользователя об успешном удалении авто из гаража}
  116.         writeln('Автомобиль успешно удален из гаража!');
  117.     end;
  118. {конец тела процедуры}
  119. end;
  120. {---------------------------------------------------------------------------}
  121. {Вывод всех автомобилей на экран}
  122. {---------------------------------------------------------------------------}
  123. procedure printAllAvto;
  124. var
  125. {вспомогательный указатель, помогающий провести операцию визуализации}
  126.     p : Tptr;
  127. begin
  128. {устанавливаем указатель-помощник на первый элемент списка}
  129.     p := beg2L;
  130. {если список не содержит ни одного элемента}
  131.     if(p = NIL) then
  132. {оповещаем пользователя, что в гараже не обнаружено ни одного авто}
  133.         writeln('В гараже нет ни одного автомобиля!')
  134. {иначе список содержит минимум один элемент}
  135.     else
  136.     begin
  137. {диалог пользователю}
  138.         writeln('Автомобили гаража: ');
  139.         writeln('-----------------------------------------------');
  140. {до тех пор, пока указатель не пробежит по всем элементам списка начинаем
  141.  циклически его просматривать}
  142.         while(p <> NIL) do
  143.         begin
  144. {выпечатываем информацию о текущем узле (в данном случае автомобиле)}
  145.             writeln('Марка      : ', p^.inf.mark);
  146.             writeln('Год выпуска: ', p^.inf.year);
  147.             writeln('Стоимость  : ', p^.inf.price);
  148.             writeln('-----------------------------------------------');
  149. {переход к следующему элементу списка}
  150.             p := p^.right;
  151.         end;
  152.     end;
  153. {конец тела процедуры}
  154. end;
  155. {---------------------------------------------------------------------------}
  156. {Получение общего количества машин в гараже}
  157. {---------------------------------------------------------------------------}
  158. function getCountAvto : integer;
  159. var
  160. {вспомогательный указатель, помогающий определить количество авто в гараже}
  161.     p : Tptr;
  162. {хранит количество автомобилей в гараже}
  163.     k : integer;
  164. {начала тела функции}
  165. begin
  166. {так как рассчет количества еще не начался, то обнулем счетчик}
  167.     k := 0;
  168. {устанавливаем указатель р на первый элемент списка}
  169.     p := beg2L;
  170. {пока указатель не выйдет в NIL начинаем циклически бежать по списку}
  171.     while(p <> NIL) do
  172.     begin
  173. {увеличиваем счетчик автомобилей в гараже на единицу}
  174.         k := k + 1;
  175. {переход к следующему элементу списка}
  176.         p := p^.right;
  177.     end;
  178. {функция в качестве ответа возвращает количество авто в гараже}
  179.     getCountAvto := k;
  180. {конец тела функции}
  181. end;
  182. {---------------------------------------------------------------------------}
  183. {Получение машин со стоимостью выше средней}
  184. {---------------------------------------------------------------------------}
  185. procedure avtoPrice;
  186. var
  187. {вспомогательный указатель для обработки списка}
  188.     p    : Tptr;
  189. {отвечает за среднюю стоимость всех автомобилей гаража}
  190.     aver : real;
  191. {начало тела процедуры}
  192. begin
  193. {устанавливаем указатель р на первый элемент списка}
  194.     p := beg2L;
  195. {если в гараже есть хотя бы один автомобиль, то}
  196.     if(p <> NIL) then
  197.     begin
  198. {обнуляем переменную, отвечающую за среднее значение стоимости}
  199.         aver := 0;
  200. {пока р не прошел по всем автомобилям}
  201.         while(p <> NIL) do
  202.         begin
  203. {считаем сумму стоимости всех авто в гараже}
  204.             aver := aver + p^.inf.price;
  205. {переход к следующей автомашине}
  206.             p := p^.right;
  207.         end;
  208. {средняя стоимость - сумма всех автомашин, деленная на их количество, то есть}
  209.         aver := aver / getCountAvto;
  210. {выпечатываем значение средней стоимости авто на экран пользователя}
  211.         writeln('Средняя стоимость автомашины: ', aver:5:2);
  212. {вставка пустой строки для повышения читабельности}
  213.         writeln;
  214. {снова ставим вспомогательный указатель р на начало списка}
  215.         p := beg2L;
  216. {пока не будут просмотрены все автомашины гаража}
  217.         while(p <> NIL) do
  218.         begin
  219. {если стоимость текущего авто больше средней стоимости, то}
  220.             if(p^.inf.price > aver) then
  221.             begin
  222. {выпечатываем информацию о данной машине на дисплей пользователя}
  223.                 writeln('Марка      : ', p^.inf.mark);
  224.                 writeln('Год выпуска: ', p^.inf.year);
  225.                 writeln('Стоимость  : ', p^.inf.price);
  226.                 writeln('-----------------------------------------------');
  227.             end;
  228. {переходим к анализу следующего автомобиля}
  229.             p := p^.right;
  230.         end;
  231.     end
  232. {иначе в гараже отсутствуют машины}
  233.     else
  234. {диалог пользователю об отсутствии машин}
  235.         writeln('В гараже нет ни одной автомашины!');
  236. {конец тела процедуры}
  237. end;
  238. {---------------------------------------------------------------------------}
  239. {Продажа всех машин из гаража}
  240. {---------------------------------------------------------------------------}
  241. procedure sellAllAvto;
  242. var
  243. {вспомогательный указатель, помогающий провести продажу всех авто из гаража}
  244.     p : Tptr;
  245. {начало тела процедуры}
  246. begin
  247. {устанавливаем указатель-помощник на первый элемент списка}
  248.     p := beg2L;
  249. {до тех пор, пока не будут проданы все авто начинаем их по одной продавать}
  250.     while(beg2L <> NIL) do
  251.     begin
  252. {перемещаем указатель на начало списка на второй элемент}
  253.         beg2L := p^.right;
  254. {удаляем первый элемент}
  255.         dispose(p);
  256. {указатель-помощник опять позиционируем на "новый" первый элемент}
  257.         p := beg2L;
  258.     end;
  259. {конец тела процедуры}
  260. end;
  261. {---------------------------------------------------------------------------}
  262. {Главное меню программы}
  263. {---------------------------------------------------------------------------}
  264. function menu : integer;
  265. var
  266. {хранит пункт меню выбранный пользователем}
  267.     sel : integer;
  268. {начало тела функции}
  269. begin
  270. {циклически визуализируем меню программы до тех пор, пока пользователь не
  271.  укажет допустимый пункт}
  272.     repeat
  273.         clrscr;
  274.         writeln('1 - ДОБАВИТЬ НОВЫЙ АВТОМОБИЛЬ В ГАРАЖ');
  275.         writeln('2 - ПРОДАТЬ ВЫБРАННЫЙ АВТОМОБИЛЬ');
  276.         writeln('3 - ПРОСМОТРЕТЬ ВСЕ АВТОМОБИЛИ В ГАРАЖЕ');
  277.         writeln('4 - УЗНАТЬ ОБЩЕЕ КОЛИЧЕСТВО В ГАРАЖЕ');
  278.         writeln('5 - ВЫВЕСТИ АВТОМОБИЛИ СО СТОИМОСТЬЮ ВЫШЕ СРЕДНЕЙ');
  279.         writeln('6 - ЗАКРЫТЬ ГАРАЖ (РАСПРОДАТЬ ВСЕ МАШИНЫ)');
  280.         writeln('7 - ВЫХОД');
  281.         write('Выбор: ');
  282.         readln(sel);
  283.     until((sel >= 1) and (sel <= 7));
  284.     writeln;
  285. {функция в качестве ответа возвращает номер выбранного пункта}
  286.     menu := sel;
  287. {конец тела функции}
  288. end;
  289. {---------------------------------------------------------------------------}
  290. {раздел описания локальных переменных}
  291. var
  292. {отвечает за пункт меню выбранный пользователем}
  293.     sel : integer;
  294. {начало главного блока программы}
  295. begin
  296. {инициализируем список - устанавливаем указатель на начало списка в NL}
  297.     beg2L := NIL;
  298. {отображем меню программы перед пользователем и после выбора пользователя
  299.  выполняем соответствующее действие}
  300.     repeat
  301. {вызов главного меню}
  302.         sel := menu;
  303.         case sel of
  304.         1:
  305.         begin
  306. {добавление автомобиля в гараж}
  307.             addAvto;
  308.             readkey;
  309.         end;
  310.         2:
  311.         begin
  312. {продажа автомобиля}
  313.             sellAvto;
  314.             readkey;
  315.         end;
  316.         3:
  317.         begin
  318. {вывод информации обо всех машинах, находящихся в гараже}
  319.             printAllAvto;
  320.             readkey;
  321.         end;
  322.         4:
  323.         begin
  324. {получение количества автомашин в гараже}
  325.             writeln('В гараже автомашин: ', getCountAvto, ' шт.');
  326.             readkey;
  327.         end;
  328.         5:
  329.         begin
  330. {полуение информации об авто, имеющий стоимосить выше средней стоимости}
  331.             avtoPrice;
  332.             readkey;
  333.         end;
  334.         6:
  335.         begin
  336. {распродажа всех автомобилей}
  337.             sellAllAvto;
  338.             writeln('Все автомобили успешно проданы!');
  339.             readkey;
  340.         end;
  341.         end;
  342.     until(sel = 7);
  343. {если машины не были распроданы, то распродаем их}
  344.     sellAllAvto;
  345. {финализирующий оператор программы}
  346. end.

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