Задание: "Создать однонаправленный или двунаправленный список и найти самую длинную последовательность повторяющихся чисел в списке, сохранить повторяющееся значение и количество повторений"
Список вроде создал, да и на примере массивов понятно, как выполнить вторую (интересующую) часть задания, но вот с реализацией алгоритма под списки возникли трудности. Проблема в том, что я знаю, как написать код для нахождения повторяющихся значений в массиве, а как это делается для списков - не имею понятия.
Буду рад любой помощи, ибо уже немного отчаялся найти решение :(
#include
using namespace std;
const int size = 8;
struct Node
{
int Data;
Node *next;
Node *prev;
};
int main()
{
Node *Start = NULL;
Node *End = NULL;
Node *Current = NULL;
int i = 0;
while (i < size)
{ // Создаем
Current = new Node;
Current -> Data = rand() % 5 + 1;
Current -> prev = NULL;
Current -> next = NULL;
// Заполняем
if (Start == NULL)
Start = End = Current;
else
{
End -> next = Current;
Current -> prev = End;
End = Current;
}
i++;
}
// Выводим
Current = Start;
while (Current)
{
cout << Current -> Data << endl;
Current = Current -> next;
}
// Удаляем
Current = End;
while (Current)
{
Node *temp = Current;
Current = Current -> prev;
delete temp;
}
Start = End = NULL;
return 0;
}
Ответ
Вот, набросал нечто такое:
int elem_curr = Start->Data;
int elem_prev = Start->Data;
std::size_t length_curr = 1;
std::size_t length_prev = 1;
for(Current = Start; Current != nullptr; Current = Current->next)
{
if(Current == Start) continue;
if(elem_curr == Current->Data) length_curr++;
else
{
if(length_curr > length_prev)
{
elem_prev = elem_curr;
length_prev = length_curr;
}
elem_curr = Current->Data;
length_curr = 1;
}
}
if(length_curr > length_prev)
{
elem_prev = elem_curr;
length_prev = length_curr;
}
std::cout << elem_prev << ' ' << length_prev << std::endl;
И в начале функции main добавьте строчку srand(unsigned(time(NULL))); для рандомайзера
По коду - оптимизируйте немного, я так совсем грубо накидал, только ради основной идеи - проход по циклу + поиск подпоследовательности. Например, строчку с continue можно "замять" при небольших дополнительных действиях и проверку после цикла на посл., которая в конце списка - тоже можете организовать покрасивее в цикле. Удачи.
Комментариев нет:
Отправить комментарий