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;

   }

}


 

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

47762. Становлення культурології як самостійної галузі гуманітарного знання 133.03 KB
  Без світу культури важко собі уявити світ особистості. До культури в цілому відноситься широкий діапазон людських почуттів і думок від пошуку смислу життя до естетики. Той чи інший досягнутий рівень культури людства визначає кожен раз заново окультурення кожної народженої людини в результаті чого врештірешт відбувається окультурення людської природи. Потрібні були століття розвитку культури щоб рука сучасної людини змогла навчитися виготовляти складну техніку створювати високодосконалі твори скульптури твори живопису чи...
47763. Культура мови. Опорний конспект лекцій 2.73 MB
  Кожна людина повинна знати мову своєї держави, душею відчувати причетність до культури нації, а через свою культуру - причетність до вселюдської культури
47764. Управление персоналом и трудовые отношения 1.68 MB
  Оценка выполняемой работы. Введение схемы оценки выполняемой работы. Кроме того что данный курс слишком краток Вы просто и не должны быть таким специалистом если не посвятили себя целиком вопросам работы с кадрами. Каждая из вышеперечисленных функций включает в себя: планирование: постановка целей и стандартов разработка правил и последовательности действий разработка планов и прогнозирование некоторых возможностей в будущем; организация: постановка определенных задач перед каждым подчиненным разделение на отделы...
47765. ОРГАНИЗАЦИЯ И ТЕХНОЛОГИЯ РЕКЛАМНОЙ ДЕЯТЕЛЬНОСТИ 1.9 MB
  Данное учебное пособие по дисциплине «Организация и технология рекламной деятельности» предназначено для обучения студентов СПО третьего курса повышенного уровня обучения
47766. Курс лекцій. Історія української культури 3.28 MB
  Вивчення цього предмету повязане з необхідністю гуманізації університетської освіти поєднаних глибоких професійних звань з опануванням багатої історії культури України та людства в цілому Історія української культури†належить до обов’язкових до вивчення в вищому навчальному закладі дисциплін. Зокрема акцентується увага на формуванні української народності та нації на етнічному складі населення сучасної України. Етнічний склад населення України
47767. Ситуаційний і диспозиційний підходи у психології особистості 259.5 KB
  Кожна людина у силу свої індивідуальних властивостей особливостей онтогенезу соціалізації стає самостійним суб’єктом діяльності сфера активності якого соціально обумовлена. Коли йдеться про передбачуваність поведінки то маються на увазі не окремі поведінкові реакції і не вся діяльність в цілому а вчинки і система вчинків суб’єктом яких є особистість як соціальна індивідуальність. Це система структурована за ступенем узагальненості – від зв’язків особистостісуб’єкта до всієї дійсності до зв’язків з її окремими сторонами і...
47768. Загальна характеристика царства Тварин 3.62 MB
  Амеба не має постійної форми тіла що пояснюється здатністю плазми скорочуватись та відсутністю оболонки. Цисти зовні мають різноманітні випини можуть чіплятися наприклад до тіла водоплавних птахів що сприяє поширенню виду. Ектоплазма утворює пелікулу під якою містяться дуже тонкі скоротливі волоконця – міонеми розміщені у напрямку поздовжньої осі тіла. Відрізняються кулястою формою тіла тонкими довгими псевдоніжками що розходяться від клітини радіально а також наявністю черепашки з карбонату кальцію та органічних речовин або...
47769. Житлове право. Курс лекцій 1.5 MB
  У вузькому значенні житлове право традиційно розглядається як частина цивільного права яка врегульовує правові відносини які виникають в процесі користування жилими приміщеннями. Так наприклад для відносин користування жилими приміщеннями характерним є цивільноправовий метод регулювання рівність сторін їх майнова самостійність; для відносин розподілу надання житла управління житловим фондом інших відносин організаційного та управлінського характеру – метод адміністративноправового регулювання метод владипідпорядкованості. Таким...
47770. ІНВЕСТИЦІЙНИЙ АНАЛІЗ. ОПОРНИЙ КОНСТПЕКТ ЛЕКЦІЙ 1.3 MB
  Аналіз і прогнозування фінансового стану підприємства та оцінювання його інвестиційної привабливості . Методологічні засади інвестиційного аналізу Інвестиції у виробництво та у ринки збуту створюючи умови для підвищення якості продукції мінімізації витрат збільшення обсягів продажу забезпечують підвищення конкурентоспроможності підприємства. Цілі що їх за інвестування ставить перед собою підприємство відповідають стратегічним для великих проектів і тактичним для малих проектів цілям підприємства на ринку. До таких цілей можна...