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;

   }

}


 

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

80035. Океанология. Физические явления и процессы в океане 14.3 MB
  Показан исторический опыт и современный уровень представлений о районировании и классификации подразделений Мирового океана. Приводятся основные сведения о физических явлениях и процессах в океане: рассматриваются вопросы перемешивания и устойчивости вод термики оптики акустики океана...
80036. Океанология. Динамические явления и процессы в океане 5.52 MB
  Свободная поверхность Мирового океана, не возмущенная динамическими факторами (приливы, течения и др.), определяет фигуру, называемую геоидом. Но наблюдения над уровнем моря в любой точке Мирового океана показывают, что его действительная поверхность не остается в покое, а находится в непрерывном...
80037. Навчальний проект з виявлення, дослідження та впорядкування джерел рідного краю «До чистих джерел» 69.5 KB
  «Не можна двічі увійти в одну і ту ж річку», — сказав знаменитий грецький філософ дві тисячі років тому. У наш час ми розуміємо глибокий зміст цього висловлювання не тільки як метафори, розуміємо буквально — води, що нас оточують, дійсно змінюються прямо на очах, у результаті антропогенного впливу.
80038. Формування інформаційної компетентності особистості в шкільній бібліотеці 72 KB
  Сьогодні шкільна бібліотека володіє значними можливостями щодо вдосконалення освітнього процесу. Нові навчальні програми, нові концепції, різноманітність навчальних курсів, зростаючий інтелектуальний рівень читачів висувають нові вимоги до якості інформаційного забезпечення навчально–виховного процесу.
80039. Школа Успіху, або формуємо компетентності 68.5 KB
  Завдання проекту Виявлення ключових проблем які гальмують підвищення якості освіти та надання рекомендацій щодо розв’язання основних проблем змісту освіти. Створення системи моніторингу формування ключових компетентностей на всіх ступенях освіти дітей.
80040. Довкілля – казка чарівна! 55 KB
  Мета: вчити оцінювати негативне і бездумне ставлення до природи; формувати інтерес до навколишнього середовища; поглиблювати знання про довкілля рідного краю; розвивати комунікативні, творчі здібності, вміння робити висновки, відстоювати свою, думку, презентувати свої дослідження...
80041. Край, у якому ти живеш. Україна – наша Батьківщина 417.5 KB
  Мета: збагачувати знання учнів про Україну, а також активний словниковий запас учнів; пробудити інтерес до вивчання рідного краю; розширити знання народні, історичні та культурні символи українського народу; сприяти формування національної свідомості, осмисленню себе як частини...
80042. Н.В.Гоголь и Т.Г.Шевченко: две судьбы, две личности, два пути великих сыновей украинского народа 134.5 KB
  В своих исследованиях, представленных на конференции по заявленной теме, учащиеся проследили, как среда и время определили разницу в судьбах и литературных путях двух великих украинцев Н.Гоголя и Т.Шевченко. Прилагается электронная презентация темы в формате Pover Point.
80043. Декоративна таця 473 KB
  Необхідність таці люди зрозуміли дуже давно, саме тому її почали використовувати як столове приладдя вже в стародавні часи. Перші таці були зроблені не з каменя, як можна було припустити, а з обпаленої глини, оскільки їм не була потрібна міцність. Представляла вона собою напівкулю.