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;

   }

}


 

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

43030. Разработка базу дискографии музыкальных коллективов 3.57 MB
  Приведение отношения к 3НФ подразумевает, чтобы отношение было нормализовано по 2НФ и в отношении не существовало бы транзитивных зависимостей. Другими словами третья нормальная форма повышает требования второй нормальной формы: оно не ограничивается составными первичными ключами, а требует, чтобы ни один не ключевой столбец не зависел от другого не ключевого столбца. Любой не ключевой атрибут должен зависеть только от первичного ключа.
43031. Усилитель мощности звуковой частоты 956.5 KB
  Усилители низкой частоты являются одним из важнейших структурных элементов звуковоспроизводящих радиотехнических устройств. Развитие усилительных устройств тесно связано с совершенствованием электронных приборов, сначала ламп, затем транзисторов и интегральных микросхем. Резкий скачок в усовершенствовании усилителей произошел после того, как нашла применение отрицательная обратная связь.
43034. Разработка программы вывода графического изображения с помощью языка PostScript 640 KB
  Для обеспечения печати файлов в ОС UNIX имеются специальные средства, позволяющие выводить файлы на печать последовательно, один за другим, организовывать печать на принтерах, подключенных к компьютеру по сети, регламентировать доступ пользователей к различным печатающим устройствам и контролировать объем печати разными пользователями. В ядро ОС включены только драйверы локального принтера, которые передают ему печатаемые данные и следят за его состоянием.
43037. Разработка технологического процесса обработки детали с заданной годовой программой выпуска 106 KB
  10 Расчет технологических размерных цепей эскиз детали 1.11 Расчет припусков на механическую обработку расчетноаналитическим методом на один самый точный размер 1.12 Расчет припусков на механическую обработку по нормативным данным остальные размеры 1.13 Расчет КИМ 1.
43038. Понятие социального контроля, его виды 16.18 KB
  Социальный контроль — способ саморегуляции системы, обеспечивающий упорядоченное взаимодействие составляющих ее элементов посредством нормативного (в том числе правого) регулирования. Стабилизирующая функция системы социального контроля заключается в воспроизводстве господствующего типа общественных отношений, социальных (групповых, классовых, государственных) структур.