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;

   }

}


 

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

6215. Сифилис. Общие сведения и клиническая форма протекания венерических заболеваний 115.5 KB
  Общие сведения о венерических заболеваниях. Венерология (от латинского Venus - Венера, богиня любви, и греческого Logos - наука) изучает венерические или приобретаемые преимущественно (но не исключительно) половым путём инфекционные болезни. Термин...
6216. Философия Б. Спинозы и Г.В. Лейбница: проблема единства и множественности субстанций 108.5 KB
  Философия Б. Спинозы и Г.В. Лейбница: проблема единства и множественности субстанций. Вопрос 1 Философия логического монизма Б. Спинозы. В природе ничто не случайно, и все вещи обусловлены в существовании и определённых действиях необходимостью боже...
6217. Формирование и хранение дел в делопроизводстве 61.5 KB
  Формирование и хранение дел в делопроизводстве Формирование дел - это группирование исполненных документов в дело в соответствии с номенклатурой дел и систематизация документов внутри дела. Порядок формирования и оформления дел должен быть изло...
6218. Формализация задачи принятия решения 120 KB
  Постановка задачи Характерным примером практической реализации методов формализованного представления систем является формализация и решение задачи принятия решения. Рассмотрим применение данных методов на фоне формализации данной задачи. Введ...
6219. Основы медицинской генетики. Человек как объект генетических исследований 52.5 KB
  Основы медицинской генетики. Человек как объект генетических исследований. Генетика человека изучает явления наследственности и изменчивости в популяциях людей, особенности наследования нормальных и патологических признаков, влияние генетической кон...
6220. Программное обеспечение для института селекции растений 535 KB
  Аннотация В данной курсовом проекте разработано программное обеспечение для института селекции растений на языке программирования С++. Эта программа создана для хранения, ввода-вывода и обработки информации о покупках (номер покупки растения, ...
6221. Лекарственные средства неорганической природы. Классификация. Вода очищенная и вода для инъекций. Фармакопейный анализ препаратов водорода пероксида 87 KB
  Лекарственные средства неорганической природы. Классификация. Вода очищенная и вода для инъекций. Фармакопейный анализ препаратов водорода пероксида Лекарственные препараты неорганической природы составляют значительную часть ассортимента лекарствен...
6222. Генетика онтогенеза 109.5 KB
  Генетика онтогенеза 1. Общая характеристика онтогенеза (самостоятельно) 2. Генетическая детерминация онтогенеза. Генотип и среда. Поливариантность онтогенеза. Программы онтогенеза 3. Механизмы реализации программ онтогенеза 1. Общая характеристика о...
6223. Гонорея. Хламидиоз. Трихомониаз 130.5 KB
  Содержание Гонорея. Хламидиоз. Трихомониаз. Определение Этиология Тактика среднего медицинского работника при данных заболеваниях Принципы лечения Особенности ухода за пациентами Диспансеризация Профилактика...