本地指针的奇怪行为

Question

此代码使用分而治之法找到数组中的最小和最大元素:

#include<stdio.h>
#include<stdlib.h>
#define MAX(a, b) ((a>=b)?a:b)
#define MIN(a, b) ((a<=b)?a:b)

void printarr(int *arr, int base, int height){
    int i;
    for (i = base; i <=height; i++){
        printf("arr[%d] = %d \n", i, arr[i]);
    }
}

//This function divides the array into partition recursively until a partition of 1 / 2 element(s) is reached
//and then compares the elements 
int* partition(int *arr, int base, int height){
    printf("\n\n");
    printarr(arr, base, height);
    int mid = (base + height)/2;
    //The local array holds the largest and smallest elements 
    //of the partition in max_min[0] and max_min[1] respectively
    int max_min[2];
    //The next two integer pointers will point to the base 
    //address of the array returned(max_min[2]) by next recursive call
    //Please continue reading to get it 
    int *max_min_temp;
    int *max_min_temp_1;

    //The if block is executed when the partition holds exactly one
    //element the largest and the smallest elements are the same
    if(base == height){
        max_min[0] = arr[base];
        max_min[1] = arr[height];
        //The max_min[0] and max_min[1] holds the same element
        printf("%d %d\n", max_min[0], max_min[1]);
        //The base address of the array is now returned
        return max_min;
    }
    //This else if block is executed when the there's exactly two elements
    //In the partition and a simple comparison is done to find the minimum 
    //and maximum elements of the partition and store in max_min[1] and max_min[0]
    //respectively 
    else if((height - base) == 1){
        max_min[0] = MAX(arr[base], arr[height]);
        max_min[1] = MIN(arr[base], arr[height]);
        printf("%d %d\n", max_min[0], max_min[1]);
        //The base address of the array is now returned
        return max_min;
    }

    //This block is executed when more than two elements are there in the partition 
    else{
        //Now the local partition is divided into two partition from the middle

        //The max_min of the first half of the partition is pointed by max_min_temp
        max_min_temp = partition(arr, base, mid);

        //The max_min of the second half of the partition is pointed by max_min_temp_1
        max_min_temp_1 = partition(arr, mid+1, height);

        //----------------------THE PROBLEM ARISES HERE----------------------------//
        //The max_min_temp and max_min_temp_1 act as if they point to the same array    

        // and hence compares the same elements 
        max_min[0] = MAX(max_min_temp[0], max_min_temp_1[0]);
        max_min[1] = MIN(max_min_temp[1], max_min_temp_1[1]);
        //It can be seen here in the following printf statement
        printf("\nCHECKPOINT #1 - %d %d %d %d\n",max_min_temp[0], max_min_temp[1],max_min_temp_1[0], max_min_temp_1[1]);

        //Check the corresponding output of the printf statement
        printf("\nCHECKPOINT #2 - %d %d\n", max_min[0], max_min[1]);
        return max_min;

    }

}
/*int main(int argc, int *argv[]){
    int i;
    int arr[argc-1];
    int *max_min;
    for(i=1; i<argc; i++)
        sscanf(argv[i],"%d",&arr[i-1]);
    max_min = partition(arr, 0, argc-2);
    printf("\nMax = %d Min = %d\n", max_min[0], max_min[1]);
    return 0;
}*/
int main(){
    int arr[] = {20, 30, 5, 10};
    int *max_min = partition(arr, 0, 3);
    printf("\nMax = %d Min = %d\n", max_min[0], max_min[1]);
    return 0;
}

输出是：

arr[0] = 20 
arr[1] = 30 
arr[2] = 5 
arr[3] = 10 


arr[0] = 20 
arr[1] = 30 
30 20


arr[2] = 5 
arr[3] = 10 
10 5

CHECKPOINT #1 - 10 5 10 5

CHECKPOINT #2 - 10 5

Max = 10 Min = 5

这是不正确的。

现在，如果我用下面的 else 块替换 else 块，它工作正常。

else{

    max_min_temp = partition(arr, mid+1, height);
    max_min[0] = max_min_temp[0];
    max_min[1] = max_min_temp[1];
    max_min_temp_1 = partition(arr, base, mid);
    max_min[0] = MAX(max_min[0],max_min_temp_1[0]);
    max_min[1] = MIN(max_min[1],max_min_temp_1[1]);


    //printf("%d %d\n", max_min[0], max_min[1]);
    return max_min;

}

现在输出是：

arr[0] = 20 
arr[1] = 30 
arr[2] = 5 
arr[3] = 10 


arr[2] = 5 
arr[3] = 10 
10 5


arr[0] = 20 
arr[1] = 30 
30 20

Max = 30 Min = 5

这是想要的。

似乎两个本地指针都持有相同的数组...但是如何？请帮忙。谢谢

Answer 1

数组 max_min 正在返回一个本地地址，每次都产生相同的结果。可能的解决方案是进行动态内存分配。

int *max_min;
max_min = (int*)malloc(sizeof(int)*2);

将第 int* max_min[2] 行替换为以上 2 行。

Answer 2

您正在将指针传回数组 max_min，该数组分配在 previous 堆栈帧上。

现在，在第一个实现中，您连续两次调用 partition。第二次调用将覆盖你的第一个max_min数组的值（即你的max_min_temp是应该指向）。因此，您获得的 max_min 值始终来自第二次调用。

在第二个实现中，您将 max_min 的值复制到 current 堆栈框架上的变量，before 您调用partition 再次。这就是为什么你的价值观是正确的。

最重要的是，要么将当前堆栈帧上的 max 和 min 的指针传递给 partition，要么像 Ajit 所说的那样使用 malloc。

void partition(int* arr, int base, int height, int* max, int* min)
{
    // your code...

    int max_1, max_2, min_1, min_2;
    partition(arr, base, mid, &max_1, &min_1); 
    partition(arr, mid+1, height, &max_2, &min_2);
    *max = MAX(max_1 , max_2);
    *min = MIN(min_1 , min_2);
}

Answer 3

正如其他答案中所解释的那样，您正在做的是覆盖之前分配的堆栈，并且您也有解决方案，分配动态内存。我只想添加一件事，不要忘记 free() 分配的内存，否则你的代码将内存泄漏 .如果函数返回指向动态分配内存的指针，则调用者有责任 free() 内存。所以在 main() 中，在返回 free() 内存之前。

int *max_min = partition(arr, 0, 3);
printf("\nMax = %d Min = %d\n", max_min[0], max_min[1]);
free(max_min); //frees the memory allocated in partition().
max_min = NULL; //Make it point to null, so that it is not pointing to any random location.
return 0;

本地指针的奇怪行为

Weird behaviour of a local pointer

c

sorting

pointers

divide-and-conquer