программа зависает после ввода массива

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

int* mergeSort(int*,int);
int* merge(int*,int*,int);

void main()
{
  int n;int i=0;
  int *a,*b;

  scanf("%d",&n);
  a=(int)malloc(n*sizeof(int));
  for(;i<n;i++)
     scanf("%d",&a[i]);

  b=mergeSort(a,n);
  for(i=0;i<n;i++)
     printf("%d ",b[i]);

}

int* mergeSort(int *b,int n)
{
  int temp,*s;

  if(n>2)
  {
     mergeSort(b,n/2);
     mergeSort(b+n/2,n-n/2);
     s=merge(b,b+n/2,n);

     return s;
  }
  else if(n==2)
  {
     if(b[0]>b[1])
     {
         temp=b[0];
         b[0]=b[1];
         b[1]=temp; 
     }
     return;
  }
}

int* merge(int* a,int* c,int n)
{
  int i=0,j=0,k=0,
  int* x;

  while( (j ! =n/2) && (k != (n-n/2)) && (i < n))
  {
       if(a[j]<c[k])
       {
             x[i]=a[j];
             j++; 
             i++;
       }
       else
       {
             x[i]=c[k];
             k++;
             i++;
       }
   }
   for( ; j<n/2; j++,i++)
      x[i]=a[j];

   for( ; k < (n-n/2); k++,i++)
      x[i]=c[k];

   return x;
}

когда я запускаю этот код, он зависает после ввода всех элементов массива в первый цикл for. Пожалуйста, помогите мне, как я могу исправить это, чтобы он работал успешно? он зависает при вызове функции mergeSort из функции main().


person yoda    schedule 06.02.2013    source источник
comment
@Shark Устаревший заголовок только для DOS.   -  person    schedule 06.02.2013
comment
Это довольно страшный код. В качестве побочного комментария: не преобразуйте возвращаемое значение malloc() в C.   -  person unwind    schedule 06.02.2013
comment
отладка отладка отладка отладка!   -  person Dariusz    schedule 06.02.2013
comment
conio.h => Консольный ввод/вывод   -  person NullPoiиteя    schedule 06.02.2013
comment
Кроме того, стиль кодирования, отступы и пробелы, пожалуйста!   -  person    schedule 06.02.2013
comment
Теперь, когда он отформатирован, я бы сказал, что ваша рекурсия никогда не закончится, поэтому, если вы позволите ей работать достаточно долго, вы должны попасть в stackoverflow. Кроме этого, сказать, что мой код останавливается после ввода элементов, не очень помогает, поместите несколько prinfs, чтобы локализовать, ГДЕ он зависает, и тогда мы сможем понять, почему... @H2CO3: спасибо.   -  person Shark    schedule 06.02.2013
comment
1) Функция mergeSort() имеет пути кода, которые не возвращают значение. 2) Функция merge() использует неинициализированный указатель (int *x). Могут быть и другие проблемы, но я перестал искать.   -  person Blastfurnace    schedule 06.02.2013


Ответы (3)


it hangs after inputting all the elements of the array in first for loop.

зависает? Вы уверены... это довольно хорошо, учитывая, что ваш код слияния объявляет указатель на int:

int *x;

и никогда не инициализирует его, а затем пытается перейти к смещению (i) за ним:

x[i]=a[j];

Измените свой код на это:

int *x = malloc(n * sizeof(int));

и он должен перестать падать / зависать.

К вашему сведению, всякий раз, когда вы malloc() должны free() прямо сейчас, у вас есть утечки памяти.

person Mike    schedule 06.02.2013
comment
большое спасибо ... теперь он работает нормально после инициализации int * x, как вы предложили, и спасибо @blastfurnace - person yoda; 06.02.2013
comment
@mike .... не могли бы вы помочь в выполнении этой сортировки слиянием с рекурсией ... этот код не дает правильного ответа ... пожалуйста, помогите мне! - person yoda; 07.02.2013
comment
@yodh - да, я тоже это заметил, это близко, но не совсем правильно. Вы его вообще отлаживали? У вас есть идеи, почему это не работает? - person Mike; 07.02.2013
comment
да, я отладил его ... и он работает нормально, но дело в том, что он все еще не дает правильного ответа. - person yoda; 08.02.2013
comment
@yodh - отладка означает не только компиляцию;) Это также означает анализ логических ошибок. Я имею в виду, что вы говорите, что это не дает правильного ответа, так какой анализ вам нужен, чтобы показать это? Какие наборы входных данных не дают правильного ответа, когда вы говорите, что это неправильно, это все не по порядку или только определенное подмножество целого? merge() или mergesort() дает неверные данные? (Я предполагаю, что merge()) Если это merge(), то являются ли данные правильными после цикла while(), но неправильными перед for()? - person Mike; 08.02.2013
comment
@yodh - Видишь, что я говорю? Вы можете шагать с отладчиком или данными printf, когда вы идете, чтобы проанализировать, где происходит сбой. Это отладка вашей программы. Даже если вы не можете получить правильный вывод, вы можете выяснить, какие входные данные вызывают плохое поведение и в какой функции/области проблема. - person Mike; 08.02.2013
comment
хе-хе... я не знаю, как отлаживать логические ошибки... спасибо за это, и теперь я попытаюсь сделать это таким образом.... :) и надеюсь, что на этот раз у меня получится! - person yoda; 08.02.2013
comment
@yodh нет проблем. После того, как вы сделали некоторый анализ, если вы все еще не можете найти его, не стесняйтесь опубликовать еще один вопрос, в котором конкретно задается вопрос, почему ваша сортировка слиянием не сортируется, и предоставьте свой анализ отладки, я или другие были бы рады помочь доработать ваш работа ногами. - person Mike; 08.02.2013
comment
спасибо :) я хочу спросить одну вещь, как вы сказали выше, что я должен освободить выделенную память в конце ... но разве сама программа не освобождает эту память после ее завершения ?! - person yoda; 08.02.2013
comment
@yodh - программы C не сами управляют памятью. Операционная система, в которой вы работаете, может сделать это за вас, но это не гарантируется... и если вы когда-либо работали над встроенными проектами или на компьютерах без MMU (блока управления памятью), это почти гарантия что они не будут убирать за вас. Так что освобождать память и закрывать дескрипторы, когда вы закончите с ними, — это хорошая привычка и хороший стиль. - person Mike; 08.02.2013
comment
да, я провел некоторый анализ этого кода... и я публикую вывод, который предполагает, что все работает хорошо, за исключением одного шага... непосредственно перед объединением всех элементов! я покажу вам код и его вывод ниже в качестве комментария :) - person yoda; 08.02.2013

Есть некоторые ошибки, не только основные вещи, такие как void main вместо int main, но и, например, return; в mergeSort(), которые должны возвращать int* и неинициализированные x. Также одна важная вещь об алгоритме: вы, кажется, предполагаете, что n является степенью числа 2: вы рекурсивно делите на 2 и предполагаете, что это всегда неусеченное целое число.

person Bernd Elkemann    schedule 06.02.2013
comment
Для main может быть нормально возвращать void, прочитать это. Хотя, скорее всего, в данном случае речь идет о размещенной программе, и тогда ваш комментарий о main верен. - person Lundin; 06.02.2013
comment
но я взял (n-n/2) во второй раз...так что, даже если он будет усечен, я получу остальные элементы во второй раз...не так ли? - person yoda; 06.02.2013
comment
Верно. Я упустил это из виду. Но, пожалуйста, рассмотрите другие пункты, которые я написал. - person Bernd Elkemann; 06.02.2013

Во-первых, код не компилируется компилятором C++ (я знаю, что это C-код, но все же...),

пара проблем:

строка 11:

a=(int)malloc(n*sizeof(int));

почему вы указываете указатель на int? а - целое *

строка 38:

return;

вы возвращаетесь из mergeSort без возвращаемого значения... это не может быть хорошо

Я рекомендую вам исправить все ошибки и предупреждения компилятора, а затем повторить попытку.

person David Hope    schedule 06.02.2013
comment
на самом деле я не получал ошибок времени компиляции, но ошибки времени выполнения... и да, после удаления приведения int и инициализации *x мой код работает нормально, хотя и не дает правильного результата. - person yoda; 06.02.2013