Доброго времени суток. Появился вопрос: создаю 2 линейных односвязных списка списка, нужно найти максимальную последовательность элементов первого списка во втором. Например: если первый список у нас -12 -3 2 6 9 14, а второй -4 0 2 6 10, то максимальной последовательностью будет являться 2 6. Также в условии сказано, чтобы список был неубывающим, но это пока не реализовал. И еще: если ввести список 1 2 3 4 5, то выводит с конца, т.е. 5 4 3 2 1. Там в конце есть жалкая попытка нахождения подпоследовательности, если есть что подсказать или исправить, прошу помочь.
#include <iostream.h>
#include <conio.h>
struct point
{
int key;
point *next;
};
point *make_point()
{
point *p = new (point);
cin >> p -> key;
p -> next = 0;
return p;
}
point *make_list1(int n)
{
point *beg = make_point();
point *r;
for ( int i=1; i<n; i++)
{
r = make_point();
r -> next = beg;
beg = r;
}
return beg;
}
void print_list (point *beg)
{
point *p=beg;
if (!p)
{
cout << " Spisok pust";
return;
}
while (p != 0)
{
cout << p -> key<< " ";
p = p -> next;
}
}
int main ()
{
clrscr();
int n, m, kol;
point *l1,*l2, *l;
cout << "Vvedite kol-vo elementov spiska #1 :";
cin >> n;
cout << "\nZapolnite spisok #1\n" << endl;
l1 = make_list1(n);
cout << "\nSpisok #1\n" << endl;
print_list(l1);
cout << "\n\nKol-vo elementov spiska #2 :";
cin >> m;
cout << "\nZapolnite spisok #2\n";
l2 = make_list1(m);
cout << "\nSpisok #2\n" << endl;
print_list(l2);
//тут начинаю искать подпоследвательность
while (l1 != NULL)
{
while(l2 != NULL)
{
if (l1==l2)
{
l=l1;
}
else if (l1 < l2)
{
l1=l1->next;
}
else if (l1 > l2)
{
l2=l2->next;
}
}
}
if (l != NULL)
print_list(l);
else
cout << "\nU spiskov net obschih elementov.\n";
getch();
return 0;
}
point *make_list1(int n), будет правильно выводить...
{
point *beg = 0, *end = 0, *r;
for ( int i = 0; i < n; i++)
{
r = make_point();
if(!beg) beg = r;
else end->next = r;
end = r;
}
return beg;
}
int max = 1, count;Идея понятна?
point* save = 0;
for(point* curr_L1 = l1; curr_L1; curr_L1 = curr_L1->next)
{
point* curr_L2 = l2;
while(curr_L2)
{
count = 1;
for(; curr_L2 && (curr_L2->key != curr_L1->key); curr_L2 = curr_L2->next);
if(curr_L2)
{
for(; curr_L2 && (curr_L2->key == curr_L1->key); curr_L2 = curr_L2->next)
{
count += 1;
}
if(count > max)
{
max = count; save = curr_L1;
}
}
}
}
if(!save)
cout << "no matches" << endl;
else
{
for(int i = 0; i < max; i++)
{
cout << save->key << " ";
save = save->next;
}
}