Страницы

Поиск по вопросам

пятница, 12 июля 2019 г.

Найти самую длинную последовательность повторяющихся чисел в списке

Задание: "Создать однонаправленный или двунаправленный список и найти самую длинную последовательность повторяющихся чисел в списке, сохранить повторяющееся значение и количество повторений"
Список вроде создал, да и на примере массивов понятно, как выполнить вторую (интересующую) часть задания, но вот с реализацией алгоритма под списки возникли трудности. Проблема в том, что я знаю, как написать код для нахождения повторяющихся значений в массиве, а как это делается для списков - не имею понятия.
Буду рад любой помощи, ибо уже немного отчаялся найти решение :(
#include #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 можно "замять" при небольших дополнительных действиях и проверку после цикла на посл., которая в конце списка - тоже можете организовать покрасивее в цикле. Удачи.

Комментариев нет:

Отправить комментарий