Здравствуйте, Viator, Вы писали:

V>Нужен односвязный список с фиктивным элементом, перерыл весь интернет что это такое понял, но вот как реализовать ума не приложу...
V>хотелось бы примерчик создать такого списка)))

Гм... Т.е. как создать обычный список ты знаешь, и только фиктивный элемент ставит тебя в тупик? Это как-то странно...

Здравствуйте, Viator, Вы писали:

V>Нужен односвязный список с фиктивным элементом, перерыл весь интернет что это такое понял, но вот как реализовать ума не приложу...
V>хотелось бы примерчик создать такого списка)))

Зачем вообще нужен фиктивный узел?
Обычный одно- или двусвязный список работает (не устроен, а именно работает) так:

void insert_in_begin(List* list, ListNode* new_node) {...}
void insert_after_node(List* list, ListNode* after_what, ListNode* new_node) {...}
// где-то внутри
void insert_in_empty_list(List* list, ListNode* new_node) {...}

void remove_from_bidi_list(ListNode* dead_node)
{
  if(dead_node->right) dead_node->right->left = dead_node->left;
  if(dead_node->left)  dead_node->left->right = dead_node->right;
}

ну и так далее.
То есть, нужно все краевые случаи отслеживать и обрабатывать.

Фиктивный узел (или фиктивные узлы) позволяют любые операции делать так, как будто это операции где-то посреди непустого списка.

Естественно, что фиктивный узел не содержит данных, а только служебную информацию (указатели).
Поэтому возникает иерархия

struct NodeBase
{
  NodeBase *left;
  NodeBase *right;
};

struct Node : NodeBase
{
  ValueType value;
};

Здравствуйте, Don Reba, Вы писали:

К>>Естественно, что фиктивный узел не содержит данных, а только служебную информацию (указатели).
DR>Интересней, когда содержит.
DR>

DR>Node * find(int data)
DR>{
DR>    nil.data = data;
DR>

Минус реентерабельность (многопоточность). Минус честная константность, mutable хак.

Здравствуйте, Кодт, Вы писали:

К>Минус реентерабельность (многопоточность). Минус честная константность, mutable хак.

Обмен реентерабельности на производительность, другими словами.

Нужен односвязный список с фиктивным элементом, перерыл весь интернет что это такое понял, но вот как реализовать ума не приложу...
хотелось бы примерчик создать такого списка)))

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, Viator, Вы писали:

V>>Нужен односвязный список с фиктивным элементом, перерыл весь интернет что это такое понял, но вот как реализовать ума не приложу...
V>>хотелось бы примерчик создать такого списка)))

R>Гм... Т.е. как создать обычный список ты знаешь, и только фиктивный элемент ставит тебя в тупик? Это как-то странно...

что странного??? я только начал изучать С++, и как создать обычный список куча примеров есть, а про фиктивный элемент нигде не нашел...

Здравствуйте, Viator, Вы писали:

V>что странного??? я только начал изучать С++, и как создать обычный список куча примеров есть, а про фиктивный элемент нигде не нашел...

Так список с фиктивным элементом это и есть обычный список. С единственной лишь особенностью — в нем присутствует один элемент, недоступный из вне, используемый в служебных целях (организация циклических списков, маркеры конца и пр.).

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, Viator, Вы писали:

V>>что странного??? я только начал изучать С++, и как создать обычный список куча примеров есть, а про фиктивный элемент нигде не нашел...

R>Так список с фиктивным элементом это и есть обычный список. С единственной лишь особенностью — в нем присутствует один элемент, недоступный из вне, используемый в служебных целях (организация циклических списков, маркеры конца и пр.).

прямо как во всех книгах... я это уже прочитал не раз и не два, а как реализовать односвязный кольцевой список додумаваете сами называется...

Здравствуйте, Viator, Вы писали:

V>прямо как во всех книгах... я это уже прочитал не раз и не два, а как реализовать односвязный кольцевой список додумаваете сами называется...


я создал вот такой список

struct  Node {
int data;
Node* link;
};
   Node* first;
   Node* last;
   int size;
   public:
      linklist( )
         { first=NULL;
           last=NULL;
           size=0; }

      int AddEnd (int d)
           {
           size++;
           Node* newlink = new Node;
           newlink->data = d;
           newlink->link = first;
           if (first!=NULL)
           {
              last->link=newlink;
              last=newlink;
           }
           else
           {
              first=last=newlink;
           }
           return 0;
        }

как сюда добавить фиктивный элемент?

Здравствуйте, Viator, Вы писали:

V>>прямо как во всех книгах... я это уже прочитал не раз и не два, а как реализовать односвязный кольцевой список додумаваете сами называется...

V>я создал вот такой список
V>как сюда добавить фиктивный элемент?

Просто возьми и добавь, прямо при создании списка. Можешь даже создавать его не оператором new, а разместить прямо в объекте списка. И замкни этот узел сам на себя. Это специальный скрытый элемент, список, не содержащий узлов, кроме этого, считается пустым. Элемент следующий сразу за ним — это начало списка. Вставка нового элемент ПЕРЕД этим элементом, будет соответствовать вставке в конец списка, а вставка сразу ПОСЛЕ него — это вставка в начало списка.

Здравствуйте, rg45, Вы писали:


R>Просто возьми и добавь, прямо при создании списка. Можешь даже создавать его не оператором new, а разместить прямо в объекте списка. И замкни этот узел сам на себя. Это специальный скрытый элемент, список, не содержащий узлов, кроме этого, считается пустым. Элемент следующий сразу за ним — это начало списка. Вставка нового элемент ПЕРЕД этим элементом, будет соответствовать вставке в конец списка, а вставка сразу ПОСЛЕ него — это вставка в начало списка.

я понимаю что для вас это просто, но с этим ни разу не сталкивался и для меня это тоже самое что инопланетная форма жизни (которую я никогда не видел), если это так просто почему нельзя написать несколько строк кода, вместо 5 строк текста???

Здравствуйте, Viator, Вы писали:

V>я понимаю что для вас это просто, но с этим ни разу не сталкивался и для меня это тоже самое что инопланетная форма жизни (которую я никогда не видел), если это так просто почему нельзя написать несколько строк кода, вместо 5 строк текста???

Где-то так:

struct Node
{
    int    data;
    Node * next;

    Node(int data, Node * next) : data(data), next(next) { }
};

class List
{
private:
    Node * begin;
    Node   nil;
public:
    List() : begin(&nil), nil(0, &nil) { }
    ~List()
    {
        while (begin != &nil)
        {
            Node * next = begin.next;
            delete begin;
            begin = next;
        }
    }
    void push_front(int data)
    {
        begin = new Node(data, begin);
    }
    Node * begin() { return begin; }
    Node * end()   { return &nil;  }
};

Вопросы?

Здравствуйте, Viator, Вы писали:

R>>Просто возьми и добавь, прямо при создании списка. Можешь даже создавать его не оператором new, а разместить прямо в объекте списка. И замкни этот узел сам на себя. Это специальный скрытый элемент, список, не содержащий узлов, кроме этого, считается пустым. Элемент следующий сразу за ним — это начало списка. Вставка нового элемент ПЕРЕД этим элементом, будет соответствовать вставке в конец списка, а вставка сразу ПОСЛЕ него — это вставка в начало списка.

V>я понимаю что для вас это просто, но с этим ни разу не сталкивался и для меня это тоже самое что инопланетная форма жизни (которую я никогда не видел), если это так просто почему нельзя написать несколько строк кода, вместо 5 строк текста???

Если бы твой код был оформлен хотя бы как этот: http://rsdn.ru/forum/cpp/5365676.1

Автор: Don Reba
Дата: 18.11.13

, то можно было бы и вставить. А так твой код сначала надо полностью переписать. Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, Viator, Вы писали:

V>>>прямо как во всех книгах... я это уже прочитал не раз и не два, а как реализовать односвязный кольцевой список додумаваете сами называется...

V>>я создал вот такой список
V>>как сюда добавить фиктивный элемент?

R>Просто возьми и добавь, прямо при создании списка. Можешь даже создавать его не оператором new, а разместить прямо в объекте списка. И замкни этот узел сам на себя. Это специальный скрытый элемент, список, не содержащий узлов, кроме этого, считается пустым. Элемент следующий сразу за ним — это начало списка. Вставка нового элемент ПЕРЕД этим элементом, будет соответствовать вставке в конец списка, а вставка сразу ПОСЛЕ него — это вставка в начало списка.

Вот так?

struct  Node {
int data;
Node* link;
};
   Node*dummy;
   Node* first;
   Node* last;
   int size;
   public:
      linklist( )
         {
           last=NULL;
           dummy=new Node;
           dummy->link=dummy;
           first=dummy;
           size=0; }

      void CreateNewList()
      {Node* Q;
           for (int i=0; i<5; i++)
           {
              Q=new Node;
              Q->data=rand()%230;
              dummy->link=Q;
              dummy=Q;
              size++;
           }
           last=Q;
           last->link=dummy;
      }

Здравствуйте, rg45, Вы писали:

R>Если бы твой код был оформлен хотя бы как этот: http://rsdn.ru/forum/cpp/5365676.1

Автор: Don Reba
Дата: 18.11.13

, то можно было бы и вставить. А так твой код сначала надо полностью переписать. Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому

Вы что думаете, что мне надо только список создать, нет там еще около 10-ти функций которые надо написать, и я не прошу их вас писать, я пытаюсь написать их сам, но чтобы начать их писать надо сначало этот список создать...

Здравствуйте, Don Reba, Вы писали:

DR>Здравствуйте, Viator, Вы писали:

V>>я понимаю что для вас это просто, но с этим ни разу не сталкивался и для меня это тоже самое что инопланетная форма жизни (которую я никогда не видел), если это так просто почему нельзя написать несколько строк кода, вместо 5 строк текста???

DR>Где-то так:
DR>

DR>struct Node
DR>{
DR>    int    data;
DR>    Node * next;

DR>    Node(int data, Node * next) : data(data), next(next) { }
DR>};

DR>class List
DR>{
DR>private:
DR>    Node * begin;
DR>    Node   nil;
DR>public:
DR>    List() : begin(&nil), nil(0, &nil) { }
DR>    ~List()
DR>    {
DR>        while (begin != &nil)
DR>        {
DR>            Node * next = begin.next;
DR>            delete begin;
DR>            begin = next;
DR>        }
DR>    }
DR>    void push_front(int data)
DR>    {
DR>        begin = new Node(data, begin);
DR>    }
DR>    Node * begin() { return begin; }
DR>    Node * end()   { return &nil;  }
DR>};
DR>

DR>Вопросы?

спасибо, пока разберусь, может потом появятся)

Здравствуйте, Viator, Вы писали:

R>>Если бы твой код был оформлен хотя бы как этот: http://rsdn.ru/forum/cpp/5365676.1

Автор: Don Reba
Дата: 18.11.13

, то можно было бы и вставить. А так твой код сначала надо полностью переписать. Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому

V>Вы что думаете, что мне надо только список создать, нет там еще около 10-ти функций которые надо написать, и я не прошу их вас писать, я пытаюсь написать их сам, но чтобы начать их писать надо сначало этот список создать...

фиктивный узел нужен для того, чтобы тебе не приходилось проверять граничные условия вроде равенства на нуль.
соответственно, фиктивный узел это узел который появляется при создании списка и существует на протяжении всего времени его существования.
работай с ним как с обычным элементом списка, но никогда не удаляй. вот и вся наука.

Здравствуйте, Viator, Вы писали:

V>>>>прямо как во всех книгах... я это уже прочитал не раз и не два, а как реализовать односвязный кольцевой список додумаваете сами называется...

V>>>я создал вот такой список
V>>>как сюда добавить фиктивный элемент?

R>>Просто возьми и добавь, прямо при создании списка. Можешь даже создавать его не оператором new, а разместить прямо в объекте списка. И замкни этот узел сам на себя. Это специальный скрытый элемент, список, не содержащий узлов, кроме этого, считается пустым. Элемент следующий сразу за ним — это начало списка. Вставка нового элемент ПЕРЕД этим элементом, будет соответствовать вставке в конец списка, а вставка сразу ПОСЛЕ него — это вставка в начало списка.

V>Вот так?
V>...

Ну типа того. Только поле "first" здесь совершенно лишнее — вместо него (везде, где оно используется) лучше использовать dummy->link. Само же поле "dummy" лучше встроить прямо в структуру списка, а не выделять в динамике (смотри поле "nil" в примере Don Reba). Поле "last" тоже можно выкинуть (пока, по крайней мере) — оно нужно только для операции вставки В КОНЕЦ списка, без которого, вероятно можно обойтись.

Здравствуйте, rg45, Вы писали:


R>Ну типа того. Только поле "first" здесь совершенно лишнее — вместо него (везде, где оно используется) лучше использовать dummy->link. Само же поле "dummy" лучше встроить прямо в структуру списка, а не выделять в динамике (смотри поле "nil" в примере Don Reba). Поле "last" тоже можно выкинуть (пока, по крайней мере) — оно нужно только для операции вставки В КОНЕЦ списка, без которого, вероятно можно обойтись.

Спасибо.

Здравствуйте, rg45, Вы писали:

R>Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому

Может, глаз замылился. Где ошибся?

Здравствуйте, Don Reba, Вы писали:

R>>Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому

DR>Может, глаз замылился. Где ошибся?

Да просто компильни и увидишь: имя begin используется повторно (как член-данные и как член-функция).

Здравствуйте, rg45, Вы писали:

R>>>Кстати, Don Reba, видимо, специально внес в свой код ошибку, чтоб дать тебе возможность хоть что-то сделать самому
DR>>Может, глаз замылился. Где ошибся?
R>Да просто компильни и увидишь: имя begin используется повторно (как член-данные и как член-функция).

Я бы begin (как член-данные) вообше не стал бы заводить — вместо него вполне можно использовать nil.next.

Здравствуйте, Кодт, Вы писали:

К>Естественно, что фиктивный узел не содержит данных, а только служебную информацию (указатели).

Интересней, когда содержит.

Node * find(int data)
{
    nil.data = data;
    Node * i = begin;
    while (i->data != data)
        i = i->next;
    return i;
}