12

По предмету "Алгоритмы и структуры данных" дали задание создать:

Структуру данных для организации линейного односвязного списка

Структура данных: очередь (FIFO) с барьером.

Представление памяти - динам. память.

Все, в принципе понятно, кроме барьера.

Кто то может простым языком объяснить, что это, и с чем его едят?

4
  • В первый раз слышу такое название — может, вам лучше спросить у лектора, что он имел в виду?
    – VladD
    Commented 20 февр. 2016 в 13:12
  • @VladD Не, я уже однажды такое слышал, сейчас попробую описать в ответе. Commented 20 февр. 2016 в 13:13
  • Наверно, имеется в виду sentinel узел, который показывает конец списка. И почему "список, представляющий очередь" а не "очередь, реализованная в виде списка"? Первая формулировка шизофреническая.
    – typemoon
    Commented 20 февр. 2016 в 13:15
  • Да, действительно немного шизофренично, сейчас поправлю, спасибо.
    – user203050
    Commented 20 февр. 2016 в 13:31

1 ответ 1

12

У вас имеется линейный неупорядоченный список элементов, а именно, в данном случае - FIFO (не будем заморачиваться с тем, что такая структура хранения данных - это очередь, будем называть списком).

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

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

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

8
  • Спасибо, разъяснили. Только вот зачем он в очереди не очень понятно, ведь очередь на то и очередь, что мы имеем доступ только к первому элементу... Хотя, наверно, все учебные задания немного не практичны и бессмысленны..
    – user203050
    Commented 20 февр. 2016 в 13:38
  • 3
    @ANUCHEEKIBREEKI Ну, барьер - это несколько абстрактная вещь. Например, в плюсах, если элементы вашего списка представляют собой указатели на узлы (node'ы), то вместо какого-то "особого" узлового элемента в качестве барьера можно воспользоваться просто nullptr'ом (т.е. стандартные средства языка позволяют это легко сделать и программист может даже не задумываться о том, что он применил такой подход). Commented 20 февр. 2016 в 13:43
  • 1
    @ANUCHEEKIBREEKI На счет вашего вопроса из комментария выше непосредственно: да, вы имеете доступ лишь к первому элементу, который имеет ссылку на второй элемент и так далее, но как при обходе списка вы узнаете, что вы обошли его весь? Либо вы выставляете в конец списка барьер, либо, например, имеете поле внутри вашего списка, в котором хранится количество элементов списка и при каждом добавлении/удалении элемента в список вы это поле увеличиваете/уменьшаете и перед обращением к следующему элементу списка сравниваете номер этого элемента в списке с количеством элементов в нем вообще. Commented 20 февр. 2016 в 13:55
  • @VladD Да я одновременно с вами поясняющий комментарий написал, вы даже раньше были :) Commented 20 февр. 2016 в 13:58
  • 2
    @zRrr, да, с очередью sentinel выглядит искусственно, а вот в описанной здесь реализации rb-tree все листья дерева являются “сторожевыми ” (sentinel), что сильно упрощает код.
    – avp
    Commented 20 февр. 2016 в 16:27

Ваш ответ

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