Замечания:- Метод DeQueue должен удалять первый элемент очереди. Читайте внимательно задание.
- Я как понимаю нужно было реализовать функции, а не методы. Мне в принципе без разницы, но преподаватель не будет докапываться?
- Как можно удалять из очереди элементы, если Вы не один элемент не удосужились добавить? Поэтому я добавил метод PushBack.
- Вы не написали по какому критерию должен констатироваться факт идентичность элементов (в структуре ведь 2 поля).
- Практически на протяжении всего кода вы забываете об указателе rear, а это не хорошо.
| Код |
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <clocale>
using namespace std;
struct link
{
int position;
int data;
link* next;
link(): position(0), data(0), next(NULL) { ; }
link(int _pos, int _data, link* _next = NULL)
: position(_pos), data(_data), next(_next) { ; }
};
class queue
{
private:
link* front;
link* rear;
public:
queue(): front(NULL), rear(NULL) { ; };
void Makenull();
void Purge();
void DeQueue();
void PushBack(int pos, int data);
void Display() const;
};
//----------------------------------------------//
// Добавление элемента в очередь
void queue::PushBack(int pos, int data)
{
link* node = new link(pos, data);
if (!front)
{
front = rear = node;
}
else
{
rear->next = node;
rear = node;
}
}
//----------------------------------------------//
// Обнуление очереди
void queue::Makenull()
{
link* newl;
while (front)
{
newl = front;
front = front->next;
delete newl;
}
// Про хвост не забываем
rear = NULL;
}
//----------------------------------------------//
// Удаление первого элемента из очереди
void queue::DeQueue()
{
if (front)
{
link* node = front;
front = front->next;
if (front == NULL)
{
rear = NULL;
}
delete node;
}
};
//----------------------------------------------//
// Вывод на экран, хотя лучше было бы перегрузить <<
void queue::Display() const
{
link* newl = front;
while (newl)
{
cout << newl->data << " ";
newl = newl->next;
}
cout << endl;
}
//----------------------------------------------//
// Удаление повторяющихся элементов
void queue::Purge()
{
if (!front && (front == rear))
{
return;
}
// Новыя очередь будет базироваться на старой.
// Для начала добавляем в очередь верхний элемент из старой.
link* newFront = front, * newRear = front;
// Отпускаем первый элемент
front = front->next;
// Первый элемент в новой очереди ни на что не ссылается
newRear->next = NULL;
// Пока в тарой очереди есть узлы
while (front)
{
// Берём текущий элемент из старой очереди
link* node = front;
// Отпускаем верхний элемент из старой очереди
front = front->next;
bool find = false;
// Теперь пытаемся найти в новой очереди похожий элемент
link* newCursor = newFront;
while (newCursor && !find)
{
find = (newCursor->data == node->data);
newCursor = newCursor->next;
}
// Если одниаковый элемент найден в новой очереди,
// то мы его просто удаляем
if (find)
{
delete node;
}
// Иначе добавляем в конец новой очереди
else
{
node->next = NULL;
newRear->next = node;
newRear = node;
}
}
// Старая очередь, теперь новая :-)
front = newFront;
rear = newRear;
}
//----------------------------------------------//
// Забиваем очередь случайными данными
void FillRandom(queue& q, size_t count)
{
::srand(::time(NULL));
q.Makenull();
while (count--)
{
q.PushBack(rand()%10, rand()%10);
}
}
//----------------------------------------------//
int main()
{
::setlocale(LC_ALL, "Russian");
queue q;
unsigned n = 0;
cout << "Введите количество элементов очереди" << endl;
cin >> n;
FillRandom(q, n);
cout << "Элементы очереди:" << endl;
q.Display();
cout << "Удаление первого элемента:" << endl;
q.DeQueue();
q.Display();
cout << "Удаление повторяющихся элементов:" << endl;
q.Purge();
q.Display();
cout << "Очищение очереди..." << endl;
q.Makenull();
q.Display();
::system("pause");
return 0;
}
|
http://s1.ipicture.ru/ |