Очередь на основе связного списка на C++
Здравствуйте.
Недавно начал потихоньку изучать C++, СИ уже более-менее знаю. В процессе чтения самоучителя Шилдта появились вопросы по очередному примеру. Пример из раздела про виртуальные функции, но вопрос в другом.
Вот часть кода:
Вопрос вот в чем - правильно ли я понимаю, что указатели на начало и конец нужны в количестве 1шт. на очередь?
При добавлении элемента в функции store память выделяется для объекта класса queue, т.е. не только для самого хранимого числа и указателя на следующей элемент, но и для указателей на начало/конец очереди. Но для конкретной очереди достаточно одного указателя на начало/конец, а в нашем случае каждый элемент очереди имеет месте для хранения этих указателей, хоть они и не используются.
Я чего-то не так понимаю, или это недоработка конкретно этого примера?
Недавно начал потихоньку изучать C++, СИ уже более-менее знаю. В процессе чтения самоучителя Шилдта появились вопросы по очередному примеру. Пример из раздела про виртуальные функции, но вопрос в другом.
Вот часть кода:
Код:
class list {
public:
list *head; // указатель на начало списка
list *tail; // указатель на конец списка
list *next; // указатель на следующий элемент списка
int num; // число для хранения
list() { head = tail = next = NULL; }
virtual void store(int i) = 0;
virtual int retrieve() = 0;
};
// Создание списка типа очередь
class queue : public list {
public:
void store(int i);
int retrieve();
};
void queue::store(int i) {
list *item = new queue;
item->num = i;
// добавление элемента в конец списка
if (tail) tail->next = item;
tail = item;
item->next = NULL;
if(!head) head = tail;
}
int queue::retrieve() {
int i;
list *p;
if(!head) {
cout << "Queue is empty";
return 0;
}
// удаление элемента из начала списка
i = head->num;
p = head;
head = head->next;
delete p;
return i;
}
int main() {
// демонстрация очереди
queue q_ob;
q_ob.store(1);
q_ob.store(2);
q_ob.store(3);
cout << "Очередь : ";
cout << q_ob.retrieve();
cout << q_ob.retrieve();
cout << q_ob.retrieve();
return 0;
}
public:
list *head; // указатель на начало списка
list *tail; // указатель на конец списка
list *next; // указатель на следующий элемент списка
int num; // число для хранения
list() { head = tail = next = NULL; }
virtual void store(int i) = 0;
virtual int retrieve() = 0;
};
// Создание списка типа очередь
class queue : public list {
public:
void store(int i);
int retrieve();
};
void queue::store(int i) {
list *item = new queue;
item->num = i;
// добавление элемента в конец списка
if (tail) tail->next = item;
tail = item;
item->next = NULL;
if(!head) head = tail;
}
int queue::retrieve() {
int i;
list *p;
if(!head) {
cout << "Queue is empty";
return 0;
}
// удаление элемента из начала списка
i = head->num;
p = head;
head = head->next;
delete p;
return i;
}
int main() {
// демонстрация очереди
queue q_ob;
q_ob.store(1);
q_ob.store(2);
q_ob.store(3);
cout << "Очередь : ";
cout << q_ob.retrieve();
cout << q_ob.retrieve();
cout << q_ob.retrieve();
return 0;
}
При добавлении элемента в функции store память выделяется для объекта класса queue, т.е. не только для самого хранимого числа и указателя на следующей элемент, но и для указателей на начало/конец очереди. Но для конкретной очереди достаточно одного указателя на начало/конец, а в нашем случае каждый элемент очереди имеет месте для хранения этих указателей, хоть они и не используются.
Я чего-то не так понимаю, или это недоработка конкретно этого примера?
Тут есть один момент виртуальные функции , находятся в одном пространстве памяти и не имеет постоянного адреса и плюс к этому, отдать данные куда нужно. Памяти по барабану , что данные , что функции для памяти это 1 or 0.
Вообще ничего не понял из того, что Вы хотели сказать.
При чем тут функции, пусть и виртуальные?
Меня не интересует абсолютный размер.
Я говорю о том, что в каждом элементе очереди тратится зря память, равная суммарному размеру двух указателей, т.е. ,к примеру, для 32 разрядной машины это 4 + 4 = 8байт - на один элемент.
Если в очереди, например, 100 элементов, то зря расходуется 800байт.
Возможно, я не прав.
При чем тут функции, пусть и виртуальные?
Меня не интересует абсолютный размер.
Я говорю о том, что в каждом элементе очереди тратится зря память, равная суммарному размеру двух указателей, т.е. ,к примеру, для 32 разрядной машины это 4 + 4 = 8байт - на один элемент.
Если в очереди, например, 100 элементов, то зря расходуется 800байт.
Возможно, я не прав.
Это не недоработка, а наоборот, тщательно разработанный Шилдтом пример.
В данном примере, Вас должно было бы больше смутить отсутствие деструктора, который освободил бы память, выделяемую под элементы списка, а не сами по себе, лишние 8 байт/эл-т. Но по счастливому стечению обстоятельств, в функции main, число вызовов new из store() совпадает с числом вызовов delete из retrieve()! Удивительно, не правда ли? Но т.к. это Шилдт, то Вы сосредотачиваетесь на виртуальных функциях и их применении, а не на каких-то там деструкторах, которые не имеют прямого отношения к данной теме, хотя и они могут быть виртуальными.
Теперь, к сути Вашего вопроса. Нет, Вы впадете в заблуждение, если будете считать,
В функции int retrieve():
Вы правы в том, что функционал queue может быть богаче, а использование указателей - разнообразнее. Но пример-то, про виртуальные функции.
В данном примере, Вас должно было бы больше смутить отсутствие деструктора, который освободил бы память, выделяемую под элементы списка, а не сами по себе, лишние 8 байт/эл-т. Но по счастливому стечению обстоятельств, в функции main, число вызовов new из store() совпадает с числом вызовов delete из retrieve()! Удивительно, не правда ли? Но т.к. это Шилдт, то Вы сосредотачиваетесь на виртуальных функциях и их применении, а не на каких-то там деструкторах, которые не имеют прямого отношения к данной теме, хотя и они могут быть виртуальными.
Теперь, к сути Вашего вопроса. Нет, Вы впадете в заблуждение, если будете считать,
На самом деле, они используются, и делают список очередью, а не простым одномерным массивом.
В функции void store(int):
Код:
//если в списке уже есть последний элемент,
//то следующий за ним будет новым добавляемым (здесь используется указатель tail)
//
if (tail) tail->next = item;
// данный элемент будет новым добавленным
tail = item;
//за текущим элементом пока ничего не добавлено
//это признак конца очереди
item->next = NULL;
//если текущий элемент не голова списка, то head не должен быть
//равен нулю (пусть он будет равен tail, т.к. tail уже явно не нуль)
//это признак тела очереди, т.е. не-головы
if(!head) head = tail;
//то следующий за ним будет новым добавляемым (здесь используется указатель tail)
//
if (tail) tail->next = item;
// данный элемент будет новым добавленным
tail = item;
//за текущим элементом пока ничего не добавлено
//это признак конца очереди
item->next = NULL;
//если текущий элемент не голова списка, то head не должен быть
//равен нулю (пусть он будет равен tail, т.к. tail уже явно не нуль)
//это признак тела очереди, т.е. не-головы
if(!head) head = tail;
Код:
if(!head) {//используется признак начала очереди
//...
}
// удаление элемента из начала списка
i = head->num;
p = head;
//текущий head будет указывать на следующий эл-т
//а предыдущий head, хранимый в p, будет удален и обнулен
head = head->next;
//...
}
// удаление элемента из начала списка
i = head->num;
p = head;
//текущий head будет указывать на следующий эл-т
//а предыдущий head, хранимый в p, будет удален и обнулен
head = head->next;
Вообще, Вы правы. Нужны только два указателя. Один на начало, другой - на конец очереди.
Просто Шилдт, предлагает проработать полиморфизм на примере списка, очереди, стека и сортированного списка, которые реализуются на основе структуры с тремя указателями. Для очереди, самой по себе, это избыточно. Но в условиях наследования, избавляет программиста производных классов добавлять новые указатели. Все необходимые указатели уже присутствуют в базовом классе и остается написать алгоритм для реализации новых методов.
Код:
struct cell {
datatype data;
cell *next;
};
class queue {
private:
cell *head,
*tail;
public:
//...
};
datatype data;
cell *next;
};
class queue {
private:
cell *head,
*tail;
public:
//...
};
Код:
#include <cstdio>
using namespace std;
template<typename T>
class tqueue {
struct node {
T val;
node* next;
};
private:
node* a, *b;
public:
tqueue(void):a(NULL), b(NULL){}
~tqueue() {
this->clear();
}
public:
void push(const T& v) {
node* n = new node();
n->next = NULL;
n->val = v;
if(a != NULL) {
b->next = n;
b = n;
} else
a = b = n;
}
void pop(void){
node* t = a;
if(t != NULL){
a = a->next;
delete t;
}
if(a == NULL)
b = NULL;
}
void clear(void){
while(!empty())
pop();
}
T& front(void) { return a->val; }
T& front(void) const { return a->val; }
bool empty(void) const {
return (a == NULL);
}
};
int main(void){
tqueue<int> q;
for(int i = 0; i < 20; ++i)
q.push(i);
while(! q.empty()){
printf("fifo: %dn", q.front());
q.pop();
}
return 0;
}
using namespace std;
template<typename T>
class tqueue {
struct node {
T val;
node* next;
};
private:
node* a, *b;
public:
tqueue(void):a(NULL), b(NULL){}
~tqueue() {
this->clear();
}
public:
void push(const T& v) {
node* n = new node();
n->next = NULL;
n->val = v;
if(a != NULL) {
b->next = n;
b = n;
} else
a = b = n;
}
void pop(void){
node* t = a;
if(t != NULL){
a = a->next;
delete t;
}
if(a == NULL)
b = NULL;
}
void clear(void){
while(!empty())
pop();
}
T& front(void) { return a->val; }
T& front(void) const { return a->val; }
bool empty(void) const {
return (a == NULL);
}
};
int main(void){
tqueue<int> q;
for(int i = 0; i < 20; ++i)
q.push(i);
while(! q.empty()){
printf("fifo: %dn", q.front());
q.pop();
}
return 0;
}