Страница 1 из 2
Очередь и одосвязный список
Добавлено: 09 янв 2016, 05:09
Restart
Код: Выделить всё
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 (); Помогите пожалуйста.
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 15:04
Сионист
А откуда в списке pop? Это стековая операция, а не списочная.
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 15:15
Restart
pop (); это из очереди, мне нужно чтобы когда метод pop (); удалил клиента, он записался в односвязный список.
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 15:17
Absurd
Код: Выделить всё
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;
}
}
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 15:25
Absurd
А откуда в списке pop? Это стековая операция, а не списочная.
В чем по-твоему есть непреодолимая сложность в реализации стека через односвязный список? Стек по минимуму требует три операции:
a) Проверить на пустоту
b) Поместить элемент в условную "вершину" коллекции
с) Взять элемент из из условной "вершины" коллекции
Если принять за условную "вершину" коллекции "голову" (head) односвязного списка, то все три операции реализуются тривиально, и имеют они алгоритмическую сложность O(1). Но у списка есть серьезная проблема в том что элементы в списке хаотично разбросаны по пямяти, что провоцирует частые промахи мимо кеша. При этом чтобы перемножить два числа лежащие в кеше L0 требуется 20 пиковатт и несколько тактов, а чтобы загрузить одно число из оперативной памяти в кеш L0 требуется 4000 пиковатт и несколько сотен тактов. При этом более 90 процентов из этих 4000 пиковатт уйдет на прогрев медных дорожек в печатной плате соединяющих банки ОЗУ с процессором. Поэтому в данный момент грамотные программисты стараются использовать
std::vector для стека и
std::deque для очереди FIFO. В них промахи случаются в несколько раз реже, так как соседние элементы массива занимают соседние ячейки памяти и вместе попадают в линейку кеша L0. У
std::deque смежные элементы могут лежать в разных блоках памяти в вероятностью 1/(размер блока), где размер блока это одна из небольших степеней двойки, но все равно вероятность промаха при работе с декой на практике очень низка.
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 16:10
Сионист
В чем по-твоему есть непреодолимая сложность в реализации стека через односвязный список? Стек по минимому требует три операции:
a) Проверить на пустоту
b) Поместить элемент в условную "вершину" коллекции
с) Взять элемент из из условной "вершины" коллекции
Если принять за условную "вершину" коллекции "голову" (head) односвязного списка, то все три операции реализуются тривиально, и имеют они алгоритмическую сложность O(1).
Вот только не надо путать внутренности с междухарей. Даже если стек реализован на списке, списком он не называется. А то, что так называется, имеет одну особенность: читаемый элемент не удаляется из списка.
Re: Очередь и одосвязный список
Добавлено: 09 янв 2016, 19:08
Absurd
Вот только не надо путать внутренности с междухарей.
Стек это и есть то что, как сударь соизолил выразиться, "междухаря". В STL шаблон std::stack<> принимает любой тип коллекции у которой методы push_back и erase(back()) имеют сложность, по меньшей мере, амортизированный O(1). К ним относятся std::vector, std::deque и std::list.
А то, что так называется, имеет одну особенность: читаемый элемент не удаляется из списка.
Что "так называется"? std::stack? Саттер объяснял почему: объединять методы top() и pop() опасно, так как невозможно обеспечить атомарность такой операции. Стековая память? В ней вообще две вершины: вершина стека и текущий стековый фрейм.
Re: Очередь и одосвязный список
Добавлено: 10 янв 2016, 06:38
Сионист
В STL шаблон std::stack<> принимает любой тип коллекции у которой методы push_back и erase(back()) имеют сложность, по меньшей мере, амортизированный O(1). К ним относятся std::vector, std::deque и std::list.
Вы ещё про мелкомягкие именованные пайпы расскажите. Стек есть динамический контейнер, в который данные помещаются только с одного конца, каждый раз увеличивая стек на один элемент, читаются с того же конца и в процессе чтения последний добавленный элемент удаляется. Именно разрушающее чтение - отличительный признак стека и очереди от остальных контейнеров, а вовсе не сложность ерайза. Второй отличительный признак стека уже от очереди - чтение с того же конца, куда происходит запись.
Re: Очередь и одосвязный список
Добавлено: 10 янв 2016, 10:42
Absurd
Сионист писал(а):Именно разрушающее чтение - отличительный признак стека и очереди от остальных контейнеров, а вовсе не сложность ерайза.
В том стеке, который на x86 организуется через регистры RSP/RBP, при помощи функции
_alloca() вообще запросто создаются массивы с произвольным доступом . То есть по вашему на архитектуре x86 стека нет, а есть какой-то другой контайнер.
И вообще - зачем по-вашему нужен стек? Я всегда думал что для обхода графов. При посещении каждой вершины графа складываешь все ее ребра в стек, потом берешь первое ребро из стека, переходишь в смежную вершину и повторяешь до тех пор пока стек не пуст. Для графа имеющего циклы надо запоминать уже посещенные вершины чтобы избежать бесконечного цикла, для чего сгодится std::unordered_set. Каким-то образом раздельный top()/pop() может помешать реализации этого алгоритма? Я думаю - нет. Добавляется одна строчка.
Re: Очередь и одосвязный список
Добавлено: 10 янв 2016, 11:57
Romeo
Сионист, зачем так много слов, не подтверждённых фактами? Можно же всё просто решить: пруфлинк от нас и от тебя.
Вот
ссылка от программистов C++ (то есть нас с
Absurd'ом). Здесь видно, что в интерфейсе STL-евского стека методы
pop и
top раздельны. STL, как известно, стандартизирован и является частью С++, так что сказать фразу наподобие "нашли где смотреть, это же олух какой-то интерфейс создал" не получится.
Теперь предоставь ссылку от себя, где сказано, что стек может быть организован исключительно через "разрушающее чтение" и никак иначе.