时间戳

首页 > 解决方案 > C - 递归函数丢失数组地址的轨道？

arrays - C - 递归函数丢失数组地址的轨道？

问题描述

我正在实现二进制搜索。我似乎已经解决了我的问题，但我想了解发生了什么。

这是我最初为搜索所做的：

void find_index(double *list, int val, int low, int high, int *target)
{

  int mid;
  
  if (list[low] == val)
  {
    target[0] = low;
    return;
  } 

  if (list[high] == val)
  {
    target[0] = high;
    return;
  }
  
  mid = (int)((double)(low + high) / 2.0);
  if (list[mid] == val || mid == low || mid == high)
  { 
    target[0] = mid;
    return;
  }

  if (list[low] < val && val < list[mid])
  {
    high = mid;
    find_index(list, val, low, high, target);
  }

  if (list[mid] < val && val < list[high])
  {
    low = mid;
    find_index(list, val, low, high, target);
  }


  return;

}

在上面的代码中，list 是一个有序的双精度数组。我主要动态分配它，

double *list = malloc((N+1)*sizeof(double));

并且val是要搜索的值（保证在 中list）。主叫func1，哪个叫find_index。这是故事：

  1. 最初我静态分配了一个 size1 数组，int target[1]并将func1其传递给find_index. 我遇到了分段错误。使用 valgrind 跟踪错误的根源，我发现在 中func1，我使用了未初始化的值，并且在 中创建了未初始化的值func1。target是我在此类函数中分配的唯一数组，所以它必须是它。
  2. 我更改了find_index. 具体来说，我int *target似乎 int target[1]从这个问题中了解到这是传递静态分配数组的正确方法（尽管它处理二维数组）。我再次收到分段错误和来自 valgrind 的相同消息。
  3. 我target在 main int *target = malloc(1*sizeof(int));中动态声明，将其传递给func1然后传递给find_index. 我将它传递给两个函数的方式与我最初的方式相同，即两个函数都将 a 作为参数int *target。它奏效了，valgrind 没有抱怨。

但是我现在很怀疑，所以我决定更改 to 的类型find_index并将其int声明target为find_index本身的标量。根据我对递归的理解，它应该是安全的。

但是，我不明白步骤 1-3 中发生了什么，我想这样做，以防止将来出现错误。我唯一的猜测是，在实现的众多递归调用中find_index，它丢失了我最初分配的数组的地址。这是可能发生的事情吗？在什么情况下？它可能与我如何将数组传递给函数和/或我最初声明的位置有关吗？

我已经搜索但找不到真正相关的问题。

编辑：最小的可重现示例表明情况更复杂

我可以构建的最小可重现示例如下：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
#include <time.h>

void func1(double **list, double **another_list, int N);
void func2(double **list, double **another_list, int N);
void find_index(double *list, int val, int low, int high, int *target);
void q_sort_with_doublelst(double *ary,double *lst,int low,int high);
int q_partition_with_doublelst(double *ary,double *lst,int low,int high);
void swap_with_doublelst(double *ary,double *lst,int i,int j);

////////////////////////////////////////////////////////////////////////

// quick sort 

void q_sort_with_doublelst(double *ary,double *lst,int low,int high)
{
    int pivotloc;

    if(low<high)
    {
        pivotloc=q_partition_with_doublelst(ary,lst,low,high);
        q_sort_with_doublelst(ary,lst,low,pivotloc-1);
        q_sort_with_doublelst(ary,lst,pivotloc+1,high);
    }
}

int q_partition_with_doublelst(double *ary,double *lst,int low,int high)
{
    int i,pivotloc;
    int pivotkey;

    swap_with_doublelst(ary,lst,low,(low+high)/2);
    pivotkey=ary[low];
    pivotloc=low;

    for(i=low+1;i<=high;i++)
    {
        if(ary[i]<pivotkey) swap_with_doublelst(ary,lst,++pivotloc,i);
    }
    swap_with_doublelst(ary,lst,low,pivotloc);
    return pivotloc;
}

void swap_with_doublelst(double *ary,double *lst,int i,int j)
{
    int tmp_ary;
    double tmp_lst;

    tmp_ary=ary[i]; tmp_lst=lst[i];
    ary[i]=ary[j]; lst[i]=lst[j];
    ary[j]=tmp_ary; lst[j]=tmp_lst;
}


////////////////////////////////////////////////////////////////////////


void func2(double **list, double **another_list, int N)
{

  int i, j;
  double x;

  for(i=0; i<=N; i++)
  {
    j = (int) lrand48()%(N+1);
    x = lrand48();
    list[0][i] = j;
    list[1][i] = x;

    j = (int) lrand48()%(N+1);
    x = lrand48();
    another_list[0][i] = j;
    another_list[1][i] = x;

  }




}

void func1(double **list, double **another_list, int N)
{

  int i, j;
  int binary_index[1];

  double x, y;

  for(i=0; i<=N; i++)
  {

    find_index(list[0], i, 0, N, binary_index); 

    j = binary_index[0];

    x = another_list[0][j];
    y = another_list[1][j];

  }
  return;
}





void find_index(double *list, int val, int low, int high, int *target)
{

  int mid;
  
  if (list[low] == val)
  {
    target[0] = low;
    return;
  } 

  if (list[high] == val)
  {
    target[0] = high;
    return;
  }
  
  mid = (int)((double)(low + high) / 2.0);
  if (list[mid] == val || mid == low || mid == high)
  { 
    target[0] = mid;
    return;
  }

  if (list[low] < val && val < list[mid])
  {
    high = mid;
    find_index(list, val, low, high, target);
  }

  if (list[mid] < val && val < list[high])
  {
    low = mid;
    find_index(list, val, low, high, target);
  }

  return;

}


int main (int argc, char **argv)
{

  int i, N;
  int seed=time(0);
  srand48(seed);

  N = 1000000;


  double **list = (double **)malloc(2*sizeof(double *)); 
  list[0] = (double *)malloc((N+1)*sizeof(double));                       // contains only ints
  list[1] = (double *)malloc((N+1)*sizeof(double));                       // contains double

  double **another_list = (double **)malloc(2*sizeof(double *)); 
  another_list[0] = (double *)malloc((N+1)*sizeof(double));               // contains only ints
  another_list[1] = (double *)malloc((N+1)*sizeof(double));               // contains double

  for(i=0; i<=N; i++) list[0][i] = i;

  while(1 < 2)
  {
    func2(list, another_list, N);
    q_sort_with_doublelst(list[0], list[1], 0, N);
    func1(list, another_list, N);
  }

  free(list[0]);
  free(list[1]);
  free(list);

  free(another_list[0]);
  free(another_list[1]);
  free(another_list);

  return 0;

}

我试图通过list[0]在主程序（第 173 行）中确定性地填充 for 循环来重现错误，以便对其进行排序。事实证明它不会崩溃。我发布的代码与我的真实代码更相似，但现在我担心（正如评论所暗示的那样）我遇到了递归问题。最小示例所做的摘要（与我的代码非常相似）：

  1. list[0]在 [0, N] 中填充随机整数。用随机双精度填充列表1 。
  2. 以同样的方式填写another_list。
  3. list[0]通过保留与 的关系进行排序list[1]。
  4. 二进制搜索list[0]并使用找到的索引从list[1]和中获取值another_list。

此示例与我的真实代码之间存在差异：此处list[0]不保证包含我正在搜索的值。此外，此处list[0]可能包含重复项。原则上，搜索是根据搜索的值不需要存在以及没有重复的想法编写的。因此，我会说如果该值不存在，搜索应该给我找到的最接近的值，但我不知道如果有重复会发生什么。我想它应该给我一个可能重复的索引，但我绝对不确定。在我的原始代码中没有重复。

我担心目前的代码会因为存在重复而崩溃。不过，如果有人能找出不同的问题，那就太好了。让我强调一下 valgrind 给了我同样的确切信息：错误应该是target，因为它是唯一分配在func1.

标签： arrayscrecursion

解决方案

推荐阅读