Форум программистов, компьютерный форум CyberForum.ru

фиктивный узел - C++

Восстановить пароль Регистрация
 
septe-mber
0 / 0 / 0
Регистрация: 02.01.2013
Сообщений: 123
07.02.2013, 01:53     фиктивный узел #1
Привет всем ! вот сижу и разбираюсь со связным списоком, и все никак не понимаю что такое фиктивный узел ... объясните пожалуйста что за фиктивный узел такой ? и пришлите простенький код с фиктивным узлом для больше понимания (желательно односвязной список)...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2013, 01:53     фиктивный узел
Посмотрите здесь:

Не выходит из цикла. Не переходит на след. узел. C++
Двусвязные списки, не могу добавить узел с конца C++
Односвязный список. Узел-запись о книге в библиотеке. C++
удалить узел в алгоритме связного списка ? C++
Неправильно удаляет узел из бинарного дерева C++
C++ удалить узел бинарного дерева
C++ Деревья. Найти длину пути из узла a в узел b
C++ Удалить из односвязного линейного списка определенный узел

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
07.02.2013, 13:06     фиктивный узел #2
Организация списка с фиктивным узлом примечательна тем, что список начинается с узла, который не хранит значение. В основном в таких реализациях используют циклический список и двойное связывание, т.е. фиктивный узел является началом и концом двусвязного списка. В таком случае реализация получается довольно лаконичная.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
 
// ГЄГ«Г*Г±Г± ГґГЁГЄГІГЁГўГ*îãî óçëГ*
// Г*ГҐ ñîäåðæèò Г¤Г*Г*Г*ûå, óìååò Г±Г*ìîâñòГ*âëÿòüñÿ ГЁ Г±Г*ìîóäГ*ëÿòüñÿ äëÿ ïîòîìêîâ
struct NodeBase {
  NodeBase *next, *prev;
  NodeBase(NodeBase *next, NodeBase *prev) : next(next), prev(prev) {
    next->prev = prev->next = this;
  }
  NodeBase() : next(this), prev(this) {}
  virtual ~NodeBase() {
    next->prev = prev;
    prev->next = next;
  }
};
 
// ðåГ*ëüГ*ûé óçåë Г±ГЇГЁГ±ГЄГ*
// ñîäåðæèò Г¤Г*Г*Г*ûå, èñïîëüçóåò ГЄГ®Г*ñòðóêòîð ГЁ äåñòðóêòîð ГЄГ«Г*Г±Г±Г*
// ГґГЁГЄГІГЁГўГ*îãî óçëГ* äëÿ Г±Г*ìîâñòГ*ГўГЄГЁ ГЁ Г±Г*ìîóäГ*ëåГ*ГЁГї
template <class T>
struct Node : public NodeBase {
  T value;
  Node(NodeBase *next, NodeBase *prev, const T &value) : NodeBase(next, prev),
    value(value) {}
};
 
// äëÿ ïðèìåðГ*, äâóñâÿçГ*ûé ñïèñîê Г± îãðГ*Г*ГЁГ·ГҐГ*Г*ûì ГґГіГ*êöèîГ*Г*ëîì
template <class T>
class LinkedList {
 public:
  LinkedList() : base() {}
  virtual ~LinkedList() {
    clear();
  }
  void pushBack(const T &value) {
    // ГўГ±ГІГ*ГўГЄГ* Гў ГЄГ®Г*ГҐГ¶ Г±ГЇГЁГ±ГЄГ*
    new Node<T>(&base, base.prev, value);
    ++size;
  }
  void pushFront(const T &value) {
    // ГўГ±ГІГ*ГўГЄГ* Гў начало Г±ГЇГЁГ±ГЄГ*
    new Node<T>(base.next, &base, value);
    ++size;
  }
  size_t getSize() {
    return size;
  }
  T popBack() {
    if (!isEmpty()) {
      // получение значения последнего элемента
      T value = ((Node<T>*)base.prev)->value;
      // удаление последнего элемента
      delete base.prev;
      --size;
      return value;
    } else {
      throw std::overflow_error("stack is empty");
    }
  }
  T popFront() {
    if (!isEmpty()) {
      T value = ((Node<T>*)base.next)->value;
      delete base.next;
      --size;
      return value;
    } else {
      throw std::overflow_error("stack is empty");
    }
  }
  // список пуст, если фиктивный элемент указывает сам на себя
  bool isEmpty() const { return base.next == &base; }
  void clear() {
    while (!isEmpty()) {
      delete base.next;
    }
    size = 0;
  }
 private:
  size_t size;
  // ГґГЁГЄГІГЁГўГ*ûé óçåë
  NodeBase base;
};
 
int main(int argc, char **argv) {
  srand(time(0));
 
  LinkedList<int> a;
  for (int i = 0; i < 100; ++i) {
    a.pushBack(i);
  }
  
  while (!a.isEmpty()) {
    std::cout << a.popBack() << std::endl;
  }
 
  std::cin.get();
  return 0;
}
Yandex
Объявления
07.02.2013, 13:06     фиктивный узел
Ответ Создать тему
Опции темы

Текущее время: 13:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru