7452. Вывод Связного Списка

Задан массив целых чисел. Создайте Связный Список из этих чисел. Выведите Связный Список в прямом и обратном направлении.

Напишите код согласно следующего интерфейса:

class Node

{

public:

int data;

Node *next;

Node() : next(NULL) {};

Node(int data, Node *next = NULL) : data(data), next(next) {};

};

class List

{

public:

Node *head, *tail;

List() : head(NULL), tail(NULL) {};

// Добавьте число val в конец Связного Списка

void addToTail(int val);

// Выведите элементы Связного Списка

void Print(void);

// Выведите элементы Связного Списка в обратном порядке

void PrintReverse(void);

};

Вы можете создавать (использовать) по необходимости дополнительные методы.

Вход. Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n целых чисел.

Выход. В первой строке выведите элементы Связного Списка используя метод Print. Во второй строке выведите элементы Связного Списка в обратном порядке используя метод PrintReverse.

Пример входа	Пример выхода
4 1 2 3 4	1 2 3 4 4 3 2 1

РЕШЕНИЕ

Структуры данных - Списки

Анализ алгоритма

Читаем входные данные, строим список. Выводим список в прямом и обратном порядке.

Реализация алгоритма

Объявим класс Node.

class Node

{

public:

int data;

Node *next;

Node() : next(NULL) {};

Node(int data, Node *next = NULL) : data(data), next(next) {};

};

Класс List (список) содержит указатели на начало head и конец tail.

class List

{

public:

Node *head, *tail;

Конструктор устанавливает голову и хвост равными NULL.

List() : head(NULL), tail(NULL) {};

Добавление числа val в конец списка.

void addToTail(int val)

{

Если список не пустой, то создаем объект Node со значением val и устанавливаем указатель tail на него.

if (tail != NULL) // list is not empty

{

tail->next = new Node(val);

tail = tail->next;

}

Если список пустой, то создаем объект Node со значением val и устанавливаем указатели head и tail на него.

else head = tail = new Node(val);

}

Вывод списка начиная с элемента node.

void PrintForw(Node *node)

{

if (node == NULL) return;

printf("%d ",node->data);

PrintForw(node->next);

}

Вывод списка.

void Print(void)

{

PrintForw(this->head);

printf("\n");

}

Вывод списка начиная с элемента node в обратном порядке: с конца до node.

void PrintRev(Node *node)

{

if (node == NULL) return;

PrintRev(node->next);

printf("%d ",node->data);

}

void PrintReverse(void)

{

PrintRev(this->head);

printf("\n");

}

};

Основная часть программы. Объявим список.

List list;

Читаем входные данные. Строим список.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&val);

list.addToTail(val);

}

Выводим список с начала до конца.

list.Print();

Выводим список в обратном порядке.

list.PrintReverse();