46537

Двусвязные (двунаправленные) списки

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-11-23

19.28 KB

7 чел.

Вопрос 9. Двусвязные (двунаправленные) списки

В двусвязных списках (doubly linked list) к узлам добавляется ещё один указатель - на предыдущий узел. Это существенно повышает гибкость структуры данных по сравнению с односвязными списками.

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

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

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

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

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

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

Ещё один вид списков (частный случай двусвязного списка) - замкнутый или ещё встерачающееся название - кольцевой или закольцованный список. Это, кстати, наиболее полезный и часто встречающийся вариант связных списков. При этом у последнего элемента списка в поле next хранится head, а у первого элемента в поле previous - tail.

Заключение.

Ну, вот в общем-то, по спискам и всё. Несколько заключительных слов:

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

Также можно без проблем изменить размер списков, добавив/удавлив новые узлы.

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

Кроме того, для хранения списков требуется больше памяти.

В списках удобно хранить объекты больших сложных классов. Если у вас множество мелких объектов, будет эффективнее сохнанить их в массиве. Кроме того, доступ к элементам списков происходит медленнее чем к элементам массива, так как узлы списков хранятся в разных участках памяти.

Из лекции

struct Node

   {

       float data;

       Node *next;

Node *prev;

   };

// конструктор

LinkedList()

{

       first = 0;

last = 0;

   }

// деструктор

~LinkedList()

   {

       Node* cur = first;

while(cur != 0)

{

           Node* tmp = cur;

cur = cur->next;

           delete tmp;

       }

   }

Вывод содержимого

void Print()

{

wcout << L"Содержимое: ";

Node* cur = first;

while(cur != 0)

{

wcout << cur->data << L" ";

cur = cur->next;

}

wcout << endl;

}

(Содержимое: 0  1  2)

Добавление элемента

void Add(float data)

{

   Node *tmp = new Node;

   tmp->data = data;

   tmp->next = 0;

   tmp->prev = 0;

   if(first == 0)

{

       first = tmp;

last = tmp;

   }

else

{

       last->next = tmp;

       tmp->prev = last;

       last = tmp;

   }

}


 

А также другие работы, которые могут Вас заинтересовать

18089. ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ 79.5 KB
  ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ Тема 1.1. ЗМІСТ ЦІЛІ І ЗАДАЧІ ОХОРОНИ ПРАЦІ Навчальні питання лекції Місце і роль охорони праці в трудовій діяльності нашого суспільства. Законодавчі та нормативноправові акти з охорони праці. Основні п
18090. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ 70 KB
  Тема 1.2. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години. Навчальні питання занять: Гарантії прав громадян з охорони праці. Нормування праці і відпочинку. Трудова дисципліна. Література: Законодавство України про охорону праці // Зб...
18091. ОХОРОНА ПРАЦІ ЖІНОК, НЕПОВНОЛІТНІХ, ТА ІНВАЛІДІВ 72.5 KB
  Тема 1.3 ОХОРОНА ПРАЦІ ЖІНОК НЕПОВНОЛІТНІХ ТА ІНВАЛІДІВ Лекція 2 години Навчальні питання лекції: Охорона праці жінок. Охорона праці неповнолітніх. Охорона праці інвалідів.. Література: Законодавство України про охорону праці // Збірни
18092. МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ 56 KB
  Тема 1.4 МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години Навчальні питання занять: Види медичного забезпечення охорони праці. Порядок організації і проведення медичних оглядів. Права та обовязки підприємств і працівників щодо медичног...
18093. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ 119 KB
  Тема 1.5. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ Лекція 2 години. Навчальні питання лекції: Державне соціальне страхування. Соціальний захист громадян на ринку праці. Регулювання трудових відносин Література: Законодавство України про охорону праці //...
18094. ПСИХОФІЗІОЛОГІЯ ПРАЦІ 119 KB
  Тема 2.1. ПСИХОФІЗІОЛОГІЯ ПРАЦІ Лекція 2 години. Навчальні питання лекції: Психофізіологічні аспекти праці. Критерії тяжкості та напруженості праці. Адаптація трудової діяльності людини. Література: М.П.Гандзюк Є.П.Желібо М.О.Халімовський. Основи охо
18095. ГІГІЄНА ПРАЦІ І ВИРОБНИЧА САНІТАРІЯ 56.5 KB
  Тема 2.2 ГІГІЄНА ПРАЦІ І ВИРОБНИЧА САНІТАРІЯ Практичне заняття 2 години Навчальні питання занять: Основні поняття гігієни праці і виробничої санітарії. Класифікація умов праці. Пільги і компенсації за шкідливі і важкі умови праці. Література: ...
18096. ОЗДОРОВЛЕННЯ ПОВІТРЯ ВИРОБНИЧОГО СЕРЕДОВИЩА 50 KB
  Тема 2.3. ОЗДОРОВЛЕННЯ ПОВІТРЯ ВИРОБНИЧОГО СЕРЕДОВИЩА Практичне заняття 2 години. Навчальні питання занять: Дія шкідливих речовин на організм людини. Гігієнічне нормування повітря робочої зони. Захист працівників від шкідливих речовин у повітрі. ...
18097. ОСВІТЛЕННЯ ВИРОБНИЧОГО СЕРЕДОВИЩА 90.5 KB
  Тема 2.4. ОСВІТЛЕННЯ ВИРОБНИЧОГО СЕРЕДОВИЩА Практичне заняття 2 години. Навчальні питання занять: Загальні вимоги до освітлення виробничого середовища. Природне освітлення та його розрахунок. Штучне освітлення та його нормування. Література: З