Форум программистов [Powered by Invision Power Board]

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

Форум программистов > C/C++: Общие вопросы > найти пересечение массивов

Автор: Sparco 25.1.2006, 13:44

Помогите с нахождением пересечения массивов... Я вот попробовал, но препод говорит что неправильно! Надо найти одинаковые числа в двух массивах и записать эти одинаковые в третий,перебирать числа надо попорядку, если совпадает то переносим в третий, если не возвращаем 0....

Автор: Earnest 25.1.2006, 19:22

Массивы упорядоченные?
если да (или можно предварительно отсортировать), то:
Вариант 1:
Ptr1 = адрес первого массива, Ptr2 = адрес второго
ЦИКЛ (пока один из указателей не вышел за пределы своего массива)
IF *Ptr1 == *Ptr2,
копируем в третий массив,
Ptr1++, Ptr2++
ELSE IF *Ptr1 < *Ptr2
Ptr1++
ELSE Ptr2++;

Если массивы не упорядочены, и сортировать нельзя, то остается только
Вариант 2:
Для каждого элемента первого массива
Ищем его во втором массиве...

Автор: Fighter 29.1.2006, 02:25

А значения в массивах повторяются?

Автор: nikitao 29.1.2006, 11:33

Sparco,покажи тот код ,что преподу показавал.Его переделовать будем smile

Автор: Chaos A.D. 29.1.2006, 15:59

Есть пара стандартных алгоритмов из STL, можно заюзать их. На память название не помню, но по-моему это adjacent_difference из <numeric>. Посмотри этот алгоритм.

Автор: Sparco 30.1.2006, 15:23

Цитата

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
int i,j,k;
bool flag;
Mnogestva c(0);
for (i=0; i<size; i++) {
for (j=0; j<a.size; j++)
if (m_a[i]==a.m_a[j]) {
flag=false;
for (k=0; k<c.size; k++)
if (c.m_a[k]==m_a[i]) flag=true;
if (!flag) c.Add(m_a[i]);
}
}
c.Sort();
return c;
}

Вот что я пытался сделать. Использовать библиотеку нельзя....

Автор: threef 30.1.2006, 18:41

Возможно, в множествах у тебя не может быть повторяющихся элементов, тогда нет смысла в поиске совпадений в новом массиве. Возможно, они сразу отсортированы, тогда задача еще упрощается.
Есть ли у тебя конструктор копирования, чтобы возвращать "с" по значению ?
Могут ли твои множества сортироваться в принципе ?

вот два варианта, второй - это твой без флага

Код



#define WITH_SORT

#ifdef WITH_SORT

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
  Sort();
  a.Sort();
  int i=0,j=0,k=0;
  Mnogestva c(0);
  while(i<size && j< a.size )
  {
      m_a[i]<a.m_a[j] ?  i++ :
               m_a[i]>a.m_a[j] ? j++ :
               //проверяем с последним вставленным элементом,
               // т.к. множества отсортированы
               (m_a[i]!=c.m_a[c.size-1] ? c.Add(m_a[i]) : 0)
                ,i++,j++ ;
  }
   //  c already sortet
   return c;
}

#else

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
  int i,j,k;
  Mnogestva c(0);
 
  for (i=0; i<size; i++) {
      for (j=0; j<a.size; j++)
        if (m_a[i]==a.m_a[j]) 
        {
            for (k=0; k<c.size; k++)
              if (c.m_a[k]==m_a[i]) break;
            if (k==c.size) c.Add(m_a[i]);
        }
}
c.Sort();
return c;
}

#endif

если нет конструктора копирования, то "с" лучше сделать динамическим

Mnogestva *c=new Mnogestva (0);

и возвращать указатель...