Очередь и одосвязный список

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

Restart
Сообщения: 3
Зарегистрирован: 08 янв 2016, 01:40

Код: Выделить всё

class Client
{
private:
    char *firstname;
    char *name;
    int number;
    int year;
    int money;
public:
    Client ();
    Client & operator= (const Client & other);
    void setFirstName ();
    void setMoney ();
    void setName ();
    void setNumber ();
    void setYearsInBank ();
    int getPutMoney ();
    int getRemovedMoney ();
    void showClientInfo ();
    ~Client ();
};
Client::Client ()
{
    this->firstname=new char [100];
    this->name=new char [100];
    this->number=this->year=this->money=0;
}
Client &Client: :o perator= (const Client &cl)
{
     {
        if (this != &cl)
        {
           strcpy(firstname, cl.firstname);
           strcpy(name, cl.name);
           number = cl.number;
           year = cl.year;
        }
        return *this;
    }
}
void Client::setFirstName ()
{
    cout<<"Firstname: ";
    cin>>this->firstname;
}
void Client::setMoney ()
{
    this->money=rand ()%1000-200;
    if (this->money>0)
        putMoney+=this->money;
    else
        removedMoney-=this->money;
}
int Client::getPutMoney ()
{
    return putMoney;
}
int Client::getRemovedMoney ()
{
    return removedMoney;
}
void Client::setName ()
{
    cout<<"Name: ";
    cin>>this->name;
}
void Client::setNumber ()
{
    static int _number=1;
    this->number=_number;
    _number++;
}
void Client::setYearsInBank ()
{
    this->year=rand()%12;
}
void Client::showClientInfo ()
{
    cout<<"--------------------------------"<<endl;
    cout<<"Firstname: ";
    cout<<this->firstname<<endl;
    cout<<"Name: ";
    cout<<this->name<<endl;
    cout<<"Number: ";
    cout<<this->number<<endl;
    cout<<"Years in bank: ";
    cout<<this->year<<endl;
    cout<<"Money: ";
    cout<<this->money<<endl;
}
Client::~Client ()
{
    delete this->firstname;
    delete this->name;
}
class Queue
{
private:
    Client *obj;
    int maxSize;
    int currentSize;
    int priority;
public:
    Queue ();
    bool full();
    bool empty();
    int getSize ();
    void push (const Client &cl);
    void show();
    void pop();
    void submitted ();
    void removed ();
    void top();
    ~Queue ();
};
Queue::Queue()
{
    this->maxSize = 10;
    this->obj = new Client[this->maxSize];
    this->currentSize = 0;
}
bool Queue::full()
{
    return this->currentSize == this->maxSize;
}
bool Queue::empty()
{
    return this->currentSize == 0;
}
int Queue::getSize ()
{
    return this->currentSize;
}
void Queue: :p ush(const Client &cl)
{
    this->obj[currentSize] = cl;
    currentSize++;
}
void Queue::show()
{
    for(int i = 0; i < currentSize; i++)
        obj[i].showClientInfo() ;
}
void Queue: :p op()
{
    if (!empty()){
        for (int i = 1;i<this->currentSize;i++)
            obj[i - 1] = obj[i];
        this->currentSize--;
    }
}
void Queue::top()
{
    obj[currentSize-1].showClientInfo ();
}
Queue::~Queue ()
{
    delete [] obj;
}
 
struct Listitem
{
    Client *obj;
    Listitem *pNext;
};
class List
{
private:
    Listitem *head;
    Listitem *tail;
    int count;
public:
    List ();
    void add (const Client &cl);
    void clearList ();
    void showList ();
    ~List ();
};
Мне нужно как-то сделать чтобы после вызова метода pop (); Клиент попал в односвязный список, у меня не выходит написать метод add (); Помогите пожалуйста.
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

А откуда в списке pop? Это стековая операция, а не списочная.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Restart
Сообщения: 3
Зарегистрирован: 08 янв 2016, 01:40

pop (); это из очереди, мне нужно чтобы когда метод pop (); удалил клиента, он записался в односвязный список.
Absurd
Сообщения: 1228
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Код: Выделить всё

void List::add(const Client &cl) {
  Listitem* oldHead = head;
  Listitem* newHead = new Listitem;
  newHead->obj =new Client(cl); //Подразумевается что у класса Client реализован конструктор копирования.
  newHead->pNext = oldHead;
  head = newHead;
  if (!oldHead) {
    tail = head;
  }
}
2B OR NOT(2B) = FF
Absurd
Сообщения: 1228
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

А откуда в списке pop? Это стековая операция, а не списочная.
В чем по-твоему есть непреодолимая сложность в реализации стека через односвязный список? Стек по минимуму требует три операции:

a) Проверить на пустоту
b) Поместить элемент в условную "вершину" коллекции
с) Взять элемент из из условной "вершины" коллекции

Если принять за условную "вершину" коллекции "голову" (head) односвязного списка, то все три операции реализуются тривиально, и имеют они алгоритмическую сложность O(1). Но у списка есть серьезная проблема в том что элементы в списке хаотично разбросаны по пямяти, что провоцирует частые промахи мимо кеша. При этом чтобы перемножить два числа лежащие в кеше L0 требуется 20 пиковатт и несколько тактов, а чтобы загрузить одно число из оперативной памяти в кеш L0 требуется 4000 пиковатт и несколько сотен тактов. При этом более 90 процентов из этих 4000 пиковатт уйдет на прогрев медных дорожек в печатной плате соединяющих банки ОЗУ с процессором. Поэтому в данный момент грамотные программисты стараются использовать std::vector для стека и std::deque для очереди FIFO. В них промахи случаются в несколько раз реже, так как соседние элементы массива занимают соседние ячейки памяти и вместе попадают в линейку кеша L0. У std::deque смежные элементы могут лежать в разных блоках памяти в вероятностью 1/(размер блока), где размер блока это одна из небольших степеней двойки, но все равно вероятность промаха при работе с декой на практике очень низка.
2B OR NOT(2B) = FF
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

В чем по-твоему есть непреодолимая сложность в реализации стека через односвязный список? Стек по минимому требует три операции:

a) Проверить на пустоту
b) Поместить элемент в условную "вершину" коллекции
с) Взять элемент из из условной "вершины" коллекции

Если принять за условную "вершину" коллекции "голову" (head) односвязного списка, то все три операции реализуются тривиально, и имеют они алгоритмическую сложность O(1).
Вот только не надо путать внутренности с междухарей. Даже если стек реализован на списке, списком он не называется. А то, что так называется, имеет одну особенность: читаемый элемент не удаляется из списка.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Absurd
Сообщения: 1228
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Вот только не надо путать внутренности с междухарей.
Стек это и есть то что, как сударь соизолил выразиться, "междухаря". В STL шаблон std::stack<> принимает любой тип коллекции у которой методы push_back и erase(back()) имеют сложность, по меньшей мере, амортизированный O(1). К ним относятся std::vector, std::deque и std::list.
А то, что так называется, имеет одну особенность: читаемый элемент не удаляется из списка.
Что "так называется"? std::stack? Саттер объяснял почему: объединять методы top() и pop() опасно, так как невозможно обеспечить атомарность такой операции. Стековая память? В ней вообще две вершины: вершина стека и текущий стековый фрейм.
2B OR NOT(2B) = FF
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

В STL шаблон std::stack<> принимает любой тип коллекции у которой методы push_back и erase(back()) имеют сложность, по меньшей мере, амортизированный O(1). К ним относятся std::vector, std::deque и std::list.
Вы ещё про мелкомягкие именованные пайпы расскажите. Стек есть динамический контейнер, в который данные помещаются только с одного конца, каждый раз увеличивая стек на один элемент, читаются с того же конца и в процессе чтения последний добавленный элемент удаляется. Именно разрушающее чтение - отличительный признак стека и очереди от остальных контейнеров, а вовсе не сложность ерайза. Второй отличительный признак стека уже от очереди - чтение с того же конца, куда происходит запись.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Absurd
Сообщения: 1228
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сионист писал(а):Именно разрушающее чтение - отличительный признак стека и очереди от остальных контейнеров, а вовсе не сложность ерайза.

В том стеке, который на x86 организуется через регистры RSP/RBP, при помощи функции _alloca() вообще запросто создаются массивы с произвольным доступом . То есть по вашему на архитектуре x86 стека нет, а есть какой-то другой контайнер.

И вообще - зачем по-вашему нужен стек? Я всегда думал что для обхода графов. При посещении каждой вершины графа складываешь все ее ребра в стек, потом берешь первое ребро из стека, переходишь в смежную вершину и повторяешь до тех пор пока стек не пуст. Для графа имеющего циклы надо запоминать уже посещенные вершины чтобы избежать бесконечного цикла, для чего сгодится std::unordered_set. Каким-то образом раздельный top()/pop() может помешать реализации этого алгоритма? Я думаю - нет. Добавляется одна строчка.
2B OR NOT(2B) = FF
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Сионист, зачем так много слов, не подтверждённых фактами? Можно же всё просто решить: пруфлинк от нас и от тебя.

Вот ссылка от программистов C++ (то есть нас с Absurd'ом). Здесь видно, что в интерфейсе STL-евского стека методы pop и top раздельны. STL, как известно, стандартизирован и является частью С++, так что сказать фразу наподобие "нашли где смотреть, это же олух какой-то интерфейс создал" не получится.

Теперь предоставь ссылку от себя, где сказано, что стек может быть организован исключительно через "разрушающее чтение" и никак иначе.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Ответить