Односвязные списки, с++ Опции

[Nike0]

Доброго времени суток. Появился вопрос: создаю 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;
}

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

Сообщение отредактировано: Nike0 - 27.12.2010 12:36

[volvo]

И еще: если ввести список 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]

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

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