Неправильное поведение рекурсии в слиянии - PullRequest
Новая
       28

Неправильное поведение рекурсии в слиянии

1 голос
/ 10 июля 2019

Вторая рекурсия в моей программе передает странный массив, а затем весь процесс разрушается. Я передаю массив и его размер, который затем делится на два массива left_arr и right_arr . Продолжаем описанный выше процесс для левого массива, пока он не достигнет базового условия. Есть похожий вопрос, когда программа передает высокие, низкие значения и вносит изменения в один и тот же массив. Я хочу знать, почему мой код дает резкий вывод. Не обращайте внимания на функцию завоевания, так как мне не удалось проверить, произошла ли ошибка, прежде чем приблизиться к ней.

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

#include<bits/stdc++.h>

using namespace std;


 int conquer(int left_arr[],int right_arr[], int arr[]){
    int i=0,j=0,k=0;
    int length_left = sizeof(left_arr)/sizeof(left_arr[0]);
    int length_right = sizeof(right_arr)/sizeof(right_arr[0]);

                                               //int l = length_left + 
 length_right;

  while(i<length_left && j<length_right)
  {
      if(left_arr[i]<=right_arr[j])
      {
          arr[k++] = left_arr[i++];
      }
      else
      {
          arr[k++] = right_arr[j++];
      }
  }
  while(i<length_left)
  {
      arr[k++] = left_arr[i++];
  }

  while(j<length_right)
  {
      arr[k++] = right_arr[j++];
  }


                                                  for(int i=0; i<l;i++)
                                                  cout<<arr[i]<<" ";
                                                    cout<<endl;
return 0;
}

int divide(int *arr,int n)
{

 if(n<2)
  return 0;




  int mid=n/2;
  int x = n-mid;

  cout<<"  n ="<<n<<"  mid ="<<mid<<endl;

  int left_arr[mid];
  int right_arr[n-mid];             //for debug
                                    cout<<"arr:";
                                    for(int m=0;m<n;m++)
                                        cout<<arr[m]<<"  ";
                                    cout<<endl;


  for(int i=0;i<mid;i++)
      left_arr[i]=arr[i];          //for debug
                                   cout<<"Larr:";
                                   for(int k=0;k<mid;k++)
                                    cout<<left_arr[k]<<" ";

                                    cout<<endl;



  for(int j=mid;j<n;j++)
      right_arr[j] = arr[j];
                                cout<<"Rarr:";      //for debug
                                for(int j=mid;j<n;j++)
                                    cout<<right_arr[j]<<" ";

                                    cout<<endl<<endl;


   divide(left_arr,mid);
   divide(right_arr,x);

   //conquer(left_arr,right_arr,arr);


  return 0;
}


int main()
{
  int n,arr[]={2,5,4,6,1,8,3};


  divide(arr,7);

  for(int i=0;i<7;i++)
  {
      cout<<arr[i]<<" ";
  }
    return 0;
}

n = 7 mid = 3 обр: 2 5 4 6 1 8 3 Larr: 2 5 4 Рарр: 6 1 8 3

n = 3 mid = 1 обр: 2 5 4 LARR: 2 Рарр: 5 4

n = 2 mid = 1 обр .: 7536080 5 LARR: 7536080 Rarr: 5 // ошибка отсюда

n = 4 mid = 2 обр .: -1 0 4200483 6 Larr: -1 0 Rarr: 4200483 6

n = 2 mid = 1 обр: -1 0 LARR: -1 Rarr: 0

n = 2 mid = 1 обр: 7536080 5 LARR: 7536080 Rarr: 5

Ответы [ 2 ]

1 голос
/ 10 июля 2019

Do, 

    for(int j=mid;j<n;j++)
    right_arr[j-mid] = arr[j];

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

   conquer(left_arr,right_arr,arr,n);

В функции завоевания, 

    int length_left = n/2;
    int length_right = n-length_left;

, так как вы не можете найти длинумассив из его указателя.

0 голосов
/ 10 июля 2019

Это простая ошибка доступа к массиву за пределами границ (и, следовательно, неопределенное поведение). 

for(int j=mid;j<n;j++)
    right_arr[j] = arr[j];

должно быть 

for(int j=mid;j<n;j++)
    right_arr[j-mid] = arr[j];

Кроме того, как уже указывалось в комментариях, вы используете массивы переменной длины (VLA), которые не являются допустимыми в C ++.

...