Программная реализация списков, стеков и очередей в ООП

# include <iostream.h>

# include <assert.h>

//----------------------------------------------------------------

//Следующие 2 строки кода нужны в консольном приложении C++Builder

//для правильной работы класса List в роли друга класса Node

//----------------------------------------------------------------

template <class T>

class List;

//----------------------------------------------------------------

//Шаблонный класс Node, представляющий узел односвязного списка

//----------------------------------------------------------------

template <class T>

class Node {

friend class List <T>; //класс-друг

private:

T data; //элемент данных узла

Node *next; //указатель на следующий узел

public:

Node(T &); //конструктор с параметром

T getData(); //чтение элемента данных узла

};

template <class T>

Node <T> :: Node(T &d)

{

data = d;

next = NULL;

}

template <class T>

T Node <T> :: getData()

{

return data;

}

//----------------------------------------------------------------

//Шаблонный класс List, представляющий односвязный список

//----------------------------------------------------------------

template <class T>

class List {

Node <T> *first; //указатель на первый узел

Node <T> *last; //указатель на последний узел

Node <T> *newNode(T &); // указатель на новый узел

public:

List(); //конструктор

~List(); //деструктор

void addHead(T &); //добавляет узел в начало списка

void addTail(T &); //добавляет узел в конец списка

int removeHead(T &); //удаляет узел из начала списка

int removeTail(T &); //удаляет узел из конца списка

int isEmpty(); //проверяет, пуст ли список

void print(); //печатает содержимое списка

};

template <class T>

List <T> :: List()

{

first = last = NULL;

}

template <class T>

List <T> :: ~List()

{

if(!isEmpty()) { //если список не пуст

Node <T> *curr = first; //указатель на текущий узел

Node <T> *temp; //указатель на удаляемый узел

cout << endl << "Deletion of nodes:" << endl;

while(curr != NULL) { //пока не конец списка

temp = curr; //запомнить удаляемый узел

curr = curr->next; //обновить текущий узел

cout << temp->data << ’ ’; //печать удаляемого узла

delete temp; //удалить узел

}

}

cout << endl << "All nodes are deleted" << endl;

}

template <class T>

void List <T> :: addHead(T &val)

{

Node <T> *newPtr = newNode(val); //создать новый узел

if(isEmpty()) //если список пуст

first = last = newPtr; //вставить в пустой список

else { //если список не пуст

newPtr->next = first; //вставить в начало списка

first = newPtr;

}

}

template <class T>

void List <T> :: addTail(T &val)

{

Node <T> *newPtr = newNode(val); //создать новый узел

if(isEmpty()) //если список пуст

first = last = newPtr; //вставить в пустой список

else { //если список не пуст

last->next = newPtr; //вставить в конец списка

last = newPtr;

}

}

template <class T>

int List <T> :: removeHead(T &val)

{

if(isEmpty()) //если список пуст

return 0; //неудачное удаление

else { //если список не пуст

Node <T> *temp = first; //запомнить удаляемый узел

if(first == last) //если конец списка

first = last = NULL; //сделать список пустым

else //если не конец списка

first = first->next; //обновить первый узел

val = temp->data; //передать элемент данных

delete temp; //удалить узел

return 1; //успешное удаление

}

}

template <class T>

int List <T> :: removeTail(T &val)

{

if(isEmpty()) //если список пуст

return 0; //неудачное удаление

else { //если список не пуст

Node <T> *temp = last; //запомнить удаляемый узел

if(first == last) //если конец списка

first = last = NULL; //сделать список пустым

else { //если не конец списка

Node <T> *curr = first; //сделать текущим первый узел

while (curr->next != last) //сделать текущим

curr = curr->next; //предпоследний узел

last = curr; //обновить последний узел

curr->next = NULL;

}

val = temp->data; //передать элемент данных

delete temp; //удалить узел

return 1; //успешное удаление

}

}

template <class T>

int List <T> :: isEmpty()

{

return first == NULL; //возвратить NULL, если список пуст

}

template <class T>

Node <T> *List <T> :: newNode(T &val)

{

Node <T> *p = new Node <T> (val); //создать новый узел

assert(p != NULL);

return p;

}

template <class T>

void List <T> :: print()

{

if(isEmpty()) {

cout << "List is empty" << endl << endl;

return;

}

Node <T> *curr = first; //сделать текущим первый узел

cout << "List:" << endl;

while (curr != NULL) //пока список не пуст

{

cout << curr->data << " -> "; //напечатать текущий узел

curr = curr->next; //обновить текущий узел

}

cout << endl << endl;

}

//----------------------------------------------------------------

//Шаблонный класс Stack, представляющий стек и

//реализованный как класс-наследник класса List

//----------------------------------------------------------------

template <class T>

class Stack: public List <T> {

public:

void push(T &d) //помещает элемент в стек

{

addHead(d);

}

int pop(T &d) //извлекает элемент из стека

{

return removeHead(d);

}

};

//----------------------------------------------------------------

//Шаблонный класс Queue, представляющий очередь и

//реализованный как класс-наследник класса List

//----------------------------------------------------------------

template <class T>

class Queue: public List <T> {

public:

void enqueue(T &d) //помещает элемент в очередь

{

addTail(d);

}

int dequeue(T &d) //извлекает элемент из очереди

{

return removeHead(d);

}

};

//----------------------------------------------------------------

//Прототипы внешних функций – драйверов классов

//----------------------------------------------------------------

template <class T>

void testList(List <T> &l); //шаблонная функция обработки списка

void menuList(); //печать меню обработки списка

template <class T>

void testStack(Stack <T> &s); //шаблонная функция обработки стека

void menuStack(); //печать меню обработки стека

template <class T>

void testQueue(Queue <T> &s); //шаблонная функция обработки очереди

void menuQueue(); //печать меню обработки очереди

//----------------------------------------------------------------

//Демонстрационная программа.

//Создает список, стек и очередь целых и вещественных чисел и //через меню предоставляет доступ к функциям обработки //соответствующей динамической структуры данных

//----------------------------------------------------------------

int main()

{

cout << "List of integer numbers:" << endl << endl;

List <int> intList; //создание списка целых чисел

testList(intList); //обработка списка целых чисел

cout << "List of real numbers:" << endl << endl;

List <float> floatList; //создание списка веществ. чисел

testList(floatList); //обработка списка веществ. чисел

cout << "Stack of integer numbers:" << endl << endl;

Stack <int> intStack; //создание стека целых чисел

testStack(intStack); //обработка стека целых чисел

cout << "Stack of real numbers:" << endl << endl;

Stack <float> floatStack; //создание стека веществ. чисел

testStack(floatStack); //обработка стека веществ. чисел

cout << "Queue of integer numbers:" << endl << endl;

Queue <int> intQueue; //создание очереди целых чисел

testQueue(intQueue); //обработка очереди целых чисел

cout << "Queue of real numbers:" << endl << endl;

Queue <float> floatQueue; //создание очереди веществ. чисел

testQueue(floatQueue); //обработка очереди веществ. чисел

return 0;

}

//----------------------------------------------------------------

template <class T>

void testList(List <T> &l)

{

int choice;

T val;

menuList();

do {

cout << "? ";

cin >> choice;

switch (choice) {

case 1:

cout << "Input number: ";

cin >> val;

l.addHead(val);

l.print();

break;

case 2:

cout << "Input number: ";

cin >> val;

l.addTail(val);

l.print();

break;

case 3:

if (l.removeHead(val))

cout << val << " is deleted" << endl;

l.print();

break;

case 4:

if (l.removeTail(val))

cout << val << " is deleted" << endl;

l.print();

break;

}

} while (choice != 5);

}

void menuList()

{

cout << "1 - addHead()" << endl

<< "2 - addTail()" << endl

<< "3 - removeHead()" << endl

<< "4 - removeTail()" << endl

<< "5 - exit()" << endl << endl;

}

//----------------------------------------------------------------

template <class T>

void testStack(Stack <T> &s)

{

int choice;

T val;

menuStack();

do {

cout << "? ";

cin >> choice;

switch (choice) {

case 1:

cout << "Input number: ";

cin >> val;

s.push(val);

s.print();

break;

case 2:

if (s.pop(val))

cout << val << " is deleted" << endl;

s.print();

break;

}

} while (choice != 3);

}

void menuStack()

{

cout << "1 - push()" << endl

<< "2 - pop()" << endl

<< "3 - exit()" << endl << endl;

}

//----------------------------------------------------------------

template <class T>

void testQueue(Queue <T> &q)

{

int choice;

T val;

menuQueue();

do {

cout << "? ";

cin >> choice;

switch (choice) {

case 1:

cout << "Input number: ";

cin >> val;

q.enqueue(val);

q.print();

break;

case 2:

if (q.dequeue(val))

cout << val << " is deleted" << endl;

q.print();

break;

}

} while (choice != 3);

}

void menuQueue()

{

cout << "1 - enqueue()" << endl

<< "2 - dequeue()" << endl

<< "3 - exit()" << endl << endl;

}

Дата добавления: 2014-11-14; просмотров: 445; Нарушение авторских прав

Мы поможем в написании ваших работ!