Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Односвязные списки

Автор: Nike0 27.12.2010 16:34

Доброго времени суток. Появился вопрос: создаю 2 линейных односвязных списка списка, нужно найти максимальную последовательность элементов первого списка во втором. Например: если первый список у нас -12 -3 2 6 9 14, а второй -4 0 2 6 10, то максимальной последовательностью будет являться 2 6. Также в условии сказано, чтобы список был неубывающим, но это пока не реализовал. И еще: если ввести список 1 2 3 4 5, то выводит с конца, т.е. 5 4 3 2 1. Там в конце есть жалкая попытка smile.gif нахождения подпоследовательности, если есть что подсказать или исправить, прошу помочь.

#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;
}


тут у меня процедура для формирования списка make_list, вот её-то и нужно использовать, но я не знаю как правильно, т.к. я не знаю точного количества элементов одинаковых.

Автор: volvo 27.12.2010 18:16

Цитата
И еще: если ввести список 1 2 3 4 5, то выводит с конца, т.е. 5 4 3 2 1.
Как создаешь - так и выводит. Создавай правильно:
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;
}
, будет правильно выводить...

По поводу решения задачи - это LCS (largest common sequence, не subsequence)... Если решать "в лоб", полным перебором - то вот так:
	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;
}
}

Идея понятна?

Автор: Nike0 27.12.2010 18:32

Цитата(volvo @ 27.12.2010 13:16) *

Идея понятна?

да, разобрался, спасибо