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;

   }

}


 

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

9876. Растворы на неводной (УВ) основе. Область их применения 15.43 KB
  Растворы на неводной (УВ) основе. Область их применения. В целях сохранения коллекторских свойств пластов и предупреждения осложнений при бурении стали применять БР на нефтяной основе. Они предназначены для вскрытия и освоения продуктивных пластов и...
9877. Долота режущего режуще-истирающего типа 19.19 KB
  Долота режущего режуще-истирающего типа 1)Пилообразные однолопастное долото. Существует два типа таких долот: Ц и Р. Используется для расширения и проработки скважины, как правило в не очень твердых породах. 2)Двух лопастное долото, обозначается 2Л ...
9878. Конструкция шарошечных долот. Правила эксплуатации и отработка 19.04 KB
  Конструкция шарошечных долот. Правила эксплуатации и отработка. Изобретение шарошечного долота внесло переворот во вращательное бурение. Это наиболее применяемый тип долот при бурении сплошным забоем. Отличается от других типов долот следующим: 1)Ме...
9879. Осложнение в процессе бурения. Виды осложнений и причины их возникновения 18.45 KB
  Осложнение в процессе бурения. Виды осложнений и причины их возникновения. Нарушение нормального процесса бурения, которые требуют без отлагательных и эффективных мер называется осложнением (О). К О относятся: 1)Поглощение буровых и тампонажных раст...
9880. Легкосплавные бурильные трубы. Область их использования. Легко-сплавные бурильные трубы (ЛБТ) 15.41 KB
  Легкосплавные бурильные трубы. Область их использования. Легко-сплавные бурильные трубы (ЛБТ) Увеличение глубины скважины поставило задачу снижения нагрузки на крюке, были созданы трубы из легких сплавов - дюралюминия Д16Т, механические свойств...
9881. УБТ и ведущие трубы, их назначение и конструкция 14.46 KB
  УБТ и ведущие трубы, их назначение и конструкция. Ведущие трубы. Передают вращение от ротора к бурильным трубам. Состоят из толстостенной квадратной штанги, верхнего переводника для соединения с вертлюгом, и нижнего штангового переводника. Наиболее ...
9882. НГВП при бурении скважин. Причины и признаки НГВП 15.48 KB
  НГВП при бурении скважин. Причины и признаки НГВП. Наиболее серьезен из видов осложнений, т.к. не ликвидированные НГВП может переходит в неуправляемый открытый фонтан, на ликвидацию которого тратится много времени и средств, иногда эти фонтаны возго...
9883. Меры предупреждения и ликвидации НГВП при бурении скважин 50.64 KB
  Меры предупреждения и ликвидации НГВП при бурении скважин. Действия при получении первых признаков НГВП: Может быть 3 ситуации: 1)когда инструмент находится на забое и в скважине 2)когда инструмент находится в процессе подъема или спуска 3)инструм...
9884. Обвалообразования, осыпи стенок и сужение ствола скважины в процессе бурения. Причины, признаки, меры предупреждения 16.38 KB
  Обвалообразования, осыпи стенок и сужение ствола скважины в процессе бурения. Причины, признаки, меры предупреждения. Осыпи и обвалы: Осыпи - это медленно текущий процесс нарушения ствола скважины из-за взаимодействия с БР (происходит набухание...