Дан список из n целых чисел a1, a2,...,an.
1) Вывести на экран элементы списка в указанной последовательности: an, an-1,...,a1.
2) Удалить из списка все элементы, входящие в него в точности 2 раза.
Желательно вывести список до и списки после, это тут получается 2 задачи в одной.
В решениях задач этого раздела необходимо использовать динамические структуры данных - линейные одно- или двусвязные списки(последовательности значений). Следует заметить, что реорганизация списка(включение, исключение, перестановка элементов) должна осуществляться изменением ссылочных, а не информационных полей элементов списка. Кроме того считается, что перед выполнением любой операции со списком его длина(количество элементов) явно не задана.
(Версия Visual Studio 2013)
Код: Выделить всё
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <locale.h>
#include <map>
using namespace std;
struct list
{
int info;
list *pred, *next;
};
/*Определяем прототипы будущих функций*/
void insert(list * head, list * tail, list * p);
void makelist(list * & head, list * & tail);
void printlist(list* head, list* tail);
void Invertlist(list* head, list* tail);
void Del_Sam(list * & head, list * & tail);
/**/
void main()
{
setlocale(LC_ALL, "Russian");
list *head, *tail;
makelist(head, tail);
cout << "Исходный список:" << endl;
printlist(head, tail);
cout << endl << "Перевернутый список:" << endl;
Invertlist(head, tail);
Del_Sam(head, tail);
cout << endl << "Удалены элементы, входящие в точностии 2 раза:" << endl;
printlist(head, tail);
cout << "" << endl;
system("pause");
}
/**/
void insert(list * head, list * tail, list * p)
{
if (p)
{
p->next = tail;
p->pred = tail->pred;
tail->pred = p;
p->pred->next = p;
}
else
cout << "Ошибка!" << endl;
}
/*Процедура создания списка*/
void makelist(list * &head, list * &tail)
{
head = new list;
tail = new list;
head->next = tail;
tail->pred = head;
cout << "Введите числа до 0:" << endl;
int k;
cin >> k;
while (k != 0){
list*p = new list;
p->info = k;
insert(head, tail, p);
cin >> k;
}
return;
}
/*Процедура вывода списка на экран*/
void printlist(list* head, list* tail)
{
if (head && tail)
{
list * p = head->next;
while (p != tail){
cout << p->info << ends;
p = p->next;
}
}
return;
}
/*Процедура удаления списков элемента, входящие в него в точности 2 раза*/
void Del_Sam(list * & head, list * & tail)
{
list * p = head; // Указываем на голову
map <int, int> myMap; // Используем map для хранение пары значение -> количество
while (p)
{
myMap[p->info]++; // Считаем количество одинаковых элементов
p = p->next;
}
p = head; // p присваиваем к голове
while (p)
{
if (myMap[p->info] == 2) // Если элементов было два
{
(p->next)->pred = p->pred; // Переставляем указатель следующего элемента
(p->pred)->next = p->next; // Переставляем указатель предыдущего элемента
list * t = p;
p = p->next;
delete p;
}
else
p = p->next;
}
}
/*Процедура перевертывания списка*/
void Invertlist(list* head, list* tail)
{
if (head && tail)
{
list * p = tail->pred; // Идем с конца списка
while (p != head) // Пока p не дошел до головы
{
cout << p->info << ends;
p = p->pred;
}
}
return;
}
