VPF::[C] Слияние двух упорядоченных массивов

Rockie

Дата 27.9.2006, 22:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31

Цитата(anad @ 27.9.2006, 19:20

)

Заданы два одномерных упорядоченных массива а и b. Получить новый массив, состоящий из чисел массивов а и b без повторений, упорядоченный по возрастанию.

Без поторений это уже динамической памятью. А вообще это imho метод слияния. То есть пробегаемся по обоим массивам, и добавляем в результирующий наименьшее из одного из них. Дойдя до границы одного из массивов, просто дописываем то, что осталось в другом (ведь массивы уже упорядочены до этого).

Код

#include<stdio.h>
#include<conio.h>

#define N 7
#define M 6
#define R M+N

int main(){

 int array_one[N] = { 0, 1, 2, 4, 5, 14, 15 };
 int array_two[M] = { -2, 5, 8, 9, 10, 110};
 int array_result[R];

 int ptr_one = 0, ptr_two = 0, ptr_result = 0;

  while(1)
   {
     if (array_one[ptr_one] < array_two[ptr_two])    // пишем наименьшее в третий массив 
       array_result[ptr_result++] = array_one[ptr_one++];
     else
       array_result[ptr_result++] = array_two[ptr_two++];

      // если дошли до границы массива
      if(ptr_one==N)                                 // дописываем то, что осталось во втором
        { while(ptr_two<M)
           array_result[ptr_result++] = array_two[ptr_two++];
          break;
        }

      if(ptr_two==M)                                 // дописываем то, что осталось в первом
        {  while(ptr_one<N)
            array_result[ptr_result++] = array_one[ptr_one++];
           break;
        }
   }

  for(ptr_result=0; ptr_result<R; ptr_result++)
   printf("%d ",array_result[ptr_result]);

 getch();
 return 0;
}

Это сообщение отредактировал(а) Cr@$h - 4.10.2006, 05:39

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

darkart

Дата 27.9.2006, 22:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 379
Регистрация: 9.11.2005

Репутация: 26
Всего: 31

Rockie,
После добавления элемента в результирующий массив нужно сдвигать индексы в обоих массивах до большего элемента , чем в результирующем.

Это сообщение отредактировал(а) darkart - 27.9.2006, 22:47

Rockie

Дата 27.9.2006, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31

darkart, чтобы избежать повторений? можно, хотя imho легче перед добавлением проверить - нет ли этого числа в результирующем массиве.

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

Oleg_Ci

Дата 1.10.2006, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Friend

Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30

Код


#include <stdio.h>
#include <stdlib.h>
#define len1 10 // количество чисел в перпвом массиве
#define len2 10 // во втором массиве
#define len3 len1 + len2 // в результирующем массиве

int cmp( const void * a, const void * b )
{   return *(int*)a - *(int*)b;  }

void PrintArray( int* Arr, int size )//функция печати
{
  int i;
    for( i=0; i<size; i++)
        printf("%d ",Arr[i]);
    printf("\n\n");
}

void main()
{
  int
    m1[len1]={ 2, 3, 4, 5, 6, 7, 8, 1, 2, 4 },
    m2[len2]={ 6, 7, 8, 9, 10, 11, 0, 20, 200, 3000 },
    m3[len3]={0},
    num, n_min,
    size = 0, // количество чисел в m3
    i = 0,
    j = 0;

  qsort( m1, len1, sizeof(int), cmp );
  qsort( m2, len2, sizeof(int), cmp );

  num = max( m1[0], m2[0] );
  while ( i<len1 && j<len2 )
  {
    n_min = min( m1[i], m2[j] );
    if ( num != n_min )
    {
      num = m3[size] = n_min;
      ++size;
    }
    if ( m1[i] < m2[j] ) i++;
    else j++;
  }

    while( i<len1 ) m3[size++] = m1[i++];
    while ( j<len2 ) m3[size++] = m2[j++];

  PrintArray( m1, len1 );
  PrintArray( m2, len2 );
  PrintArray( m3, size );
  system("pause");
}

Это сообщение отредактировал(а) Cr@$h - 4.10.2006, 05:42

Cr@$h

Дата 4.10.2006, 05:40 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Профиль
Группа: Участник Клуба
Сообщений: 1693
Регистрация: 3.4.2005
Где: Санкт-Петербург, Россия

Репутация: 3
Всего: 41

!
Cr@$h

На будущее, прошу обратить внимания на мои замачания:

Модератор: Пожалуйста, один топик - один вопрос.
Модератор: Название темы должно отражать ее суть!

M
Cr@$h

Выделено из темы "[Turbo C] Вычисление косинуса угла треугольника, используя TPoint, TTriangle и функ. Leng".

Это сообщение отредактировал(а) Cr@$h - 4.10.2006, 05:51

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »