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;

   }

}


 

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

46301. Методика экономического анализа 15.5 KB
  В экономическом анализе методика представляет собой совокупность аналитических способов и правил исследования экономики предприятия определенным образом подчиненных достижению цели анализа. Методика экономического анализа совокупность специфических приемов и способов исследования которые применяются при обработке экономической информации в соответствии с поставленными задачами. Она содержит следующие моменты: задачи и формулировки целей анализа; объекты анализа; системы показателей с помощью которых будет исследоваться каждый...
46302. Понятие языковой идиоматики: пословицы, поговорки, афоризмы и речевое клише 15.48 KB
  Понятие языковой идиоматики: пословицы поговорки афоризмы и речевое клише. Можно говорить о пословичном стиле существующем как бы вне времени: традиционность настолько неотъемлемая его черта что сама мысль об истоках пословицы кажется в чемто противоречивой. Пословицы изучает паремиология. Определение Даля складная короткая речь ходячая в народе но не составляющая полной пословицы вполне подходит к поговорке отмечая в то же время особый и очень распространенный вид поговорки ходячее выражение недоразвившееся до полной...
46303. С. Выготский «Проблема обучения и умственного развития в школьном возрасте» 15.45 KB
  Выготский Проблема обучения и умственного развития в школьном возрасте Хрестоматия по возрастной психологии. схематически сводит все существующие решения вопроса об отношении развития и обучения ребенка к трем основным группам. Первая группа имеет своим центром положение о независимости процессов детского развития от процессов обучения. Обучение в этих теориях рассматривается как чисто внешний процесс который должен быть так или иначе согласован с ходом детского развития но сам по себе не участвующий активно в детском развитии ничего в...
46304. Методика обучения словообразованию 15.44 KB
  Изучение морфемики и словообразования это основа формирования представлений о языке как развивающейся системе постоянно пополняющейся новыми словами. Элементарные знания даются в начальной школе в 57 классах ученики знакомятся с основными понятиями структуры слова и словопроизводства в 89 классах полученные сведения закрепляются и обобщаются. познавательные цели: ознакомление учащихся со структурой русского слова основными способами русского словообразования показать взаимосвязь между единицами разных уровней языка:...
46305. Noun 15.41 KB
  Noun hs ctegoricl mening of thingness becuse noun effects nomintion of the fullest vlue. The N is chrcterized by specific set of wordbuilding ffixes nd wordbuilding models which unmistkbly mrk noun mong them: suffixes of the doer worker nturlist etc. s for wordchnging ctegories the noun is chnged ccording to the ctegories of number boyboys cse boyboys nd rticle determintion boy boy the boy.
46306. Слово в системе языка: статус системная функция, коммуникативная необходимость 15.3 KB
  Внутренним содержанием слова является его лексическое значение. Значение слова это соотнесенность слова с определенным понятием. Основная функция слова назывная или номинативная лат. Значение семантика слова это явление историческое: оно не является раз и навсегда данным а может изменяться в процессе функционирования слова в речи; некоторые слова постепенно приобретают новое или новые значение при этом происходит расширение значения слова; некоторые из значений слова могут исчезать забываться происходит сужение значения слова [ср.
46307. Выбор продуктов в продуктовых инновациях 15.27 KB
  Существуют различные подходы к продуктовым инновациям: консервативный и радикальный.Консервативный подход к выбору новых более выгодных продуктов или услуг наиболее приемлем для финансовокризисных фирм ограниченных как в возможностях финансировать значительные стартовые инвестиции в новый бизнес так и в сроке окупаемости этих инвестиций.Консервативный подход к продуктовым инновациям сводится к выбору для освоения таких продуктов услуг или операций которые бы опирались на: уже созданный технологический а также коммерческий задел фирмы...
46308. Сущность и классификация затрат 15.26 KB
  Группировка по экономическим элементам отражает затраты которые распределяются по видам характеризующим их экономическое содержание их природное назначение. Все остальные являются комплексными собирающими затраты по обслуживанию и управлению производством. Прямые затраты непосредственно связаны с производством определенного вида продукции работ услуг и могут быть учтены в себестоимости данного вида продукции работ услуг сырье материалы полуфабрикаты комплектующие зарплата станочников и др.
46309. Эксплуатация машинно-тракторного парка при возделывании сахарной свеклы в СПК «Авангард» Сергачского района Нижегородской области 978.5 KB
  Огромное экономическое значение сахарной свеклы в народном хозяйстве. Она является главным источником доходов свеклосеящих хозяйствах. При удельном весе ее в пашне ≈ 8,6% удельный вес доходов составляет ≈ 44% от доходов растениеводства.