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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
septe-mber
0 / 0 / 0
Регистрация: 02.01.2013
Сообщений: 123
#1

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

07.02.2013, 01:53. Просмотров 620. Ответов 1
Метки нет (Все метки)

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

Двоичное дерево: как, зная данный узел дерева, изменить его родительский узел? - C++
как зная данный узел дерева измениь его родтельский узел? спасибо.

Железнодорожный сортировочный узел C++ - C++
Железнодорожный сортировочный узел устроен так, как показано на ри-сунке. На правой стороне собрано в произвольном порядке несколько...

Удалить узел бинарного дерева - C++
необходимо удалить узел, у которого нет потомков нужно обнулить ссылку предка и освободить память, но не совсем понимаю, как это сделать....

Добавить узел в бинарное дерево - C++
Мне нужно добавить узел в бинарное дерево, чтобы вышло так: "Binary Tree is a kind of orderly table". Условие задачи: Вот мой код: ...

Удалить узел в бинарном дереве - C++
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре...

Как удалить узел в связном списке? - C++
привет всем! подскажите пожалуйста в подробностях как происходит удаление узла в алгоритме связного списка ?? #include "stdafx.h" ...

Неправильно удаляет узел из бинарного дерева - C++
Помогите подправить фунцию SearchDelete...Почему-то не работет. //13. Побудувати довільне бінарне дерево, зчитавши числові значення...

Не выходит из цикла. Не переходит на след. узел. - C++
Доброго времени суток всем! Как видно из названия проблема проста, но почему то не решаема для меня. Собственно проблема в присвоении. ...

Как запихнуть в очередь указатель на узел дерева? - C++
как запихнуть в очередь указатель на узел дерева Добавлено через 16 минут up? Добавлено через 4 минуты как создать из узлов...

Удалить из односвязного линейного списка определенный узел - C++
Построить односвязный список из входной последовательности целых чисел. Написать программу, которая удаляет из линейного списка входной...

Функция удаляющая первый узел из связного списка - C++
Реализуйте и протестируйте функцию: template <class T> void DeleteFront(Node<T>* &head);удаляющую первый узел из связного списка,...

Бинарное дерево выводит только последний узел - C++
дерево выводит только последний узел а не все #include <iostream> #include <vector> using namespace std; struct Node //звено {...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
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     фиктивный узел
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru