BFPTR算法的实现

BFPTR算法，目前进行到“取中位数的中位数”的阶段，出现了访问冲突的报错；代码如下：

#include 
#include 
#include
#include
#include
using namespace std;

#define MAX 105
#define N 1000

int arr[MAX] = { 0 }; //无序的数组 

void Random()
{
    srand(time(0));
    int a = 0;
    for (int i = 0; i < MAX; i++)
    {
        a = rand() % 1000;
        arr[i] = a;
    }
}

/*显示数组*/
void Show(int a[]) 
{
    int n = 0;
    while (a[n]) //确定数组长度
    {
        n += 1;
    }
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        printf("%-3d  ", a[i]);
        count += 1;
        if (count % 10 == 0)//十个数字换行
        {
            printf("\n");
        }
    }
    printf("\n\n");
}

/*取一组的中位数*/
int Middle(int a[])
{
    int n = 0;
    while (a[n])        //确定数组长度
    {
        n += 1;
    }
    sort(a, a + n);
    //Show(a);
    return a[(n-1)/2];    //下标从0开始，不是1，所以减法
}

/*取中位数的中位数*/
int FindMid(int a[])
{
    int const(num) = MAX / 5;    // 5个一组，共num组
    int Mid[num] = { 0 };        //存储每组的中位数
    int aa[5] = { 0 };            //存储每一组的元素
    int i = 0, j = 0, k = 0, p = 0 , q = 0;
    while (i <= num)
    {
        k = i * 5;
        p = 0;
        for (j = k; j < k + 5; j++)
        {
            aa[p] = a[j];
            p++;
        }
        int aaMid = Middle(aa); //取单个组的中位数
        Mid[q] = aaMid;            //把单个组的中位数存到中位数组里————————报错！
        q++;                    //开始进行下一组中位数的存取
        i++; 
    }
    Show(Mid);
    return Middle(Mid);

}

/*交换(输入下标)*/
void swap(int a, int b) 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void BFPTR(int a[], int k) // 查找数组a中第k小的元素
{





}

int main()
{
    Random();
    Show(arr);
    int a = FindMid(arr);
    printf("  %d\n", a);
    int k = 5; //查找第k大的元素 
    //BFPTR(0, size - 1, k); //调用BFPTR算法 
    system("pause");
    return 0;
}

img


以下是第一次while循环的调试：
（1）

img


（2）

img

想问大家一下问题出在哪，应该怎么修改。

这个报错很可能是因为 Mid 数组的大小没有被正确初始化。因为 num 的值为 MAX / 5，所以 Mid 数组的大小应该是 num，而不是 5。因此，需要修改以下这行代码：

int Mid[5] = { 0 };        //存储每组的中位数

改为：

int Mid[num] = { 0 };        //存储每组的中位数

另外，注意在函数 Middle 和 FindMid 中对数组长度的计算。应该用 n 表示数组长度，而不是 n - 1，因为数组下标是从 0 开始的。因此，需要修改以下这行代码：

return a[(n-1)/2];    //下标从0开始，不是1，所以减法

改为：

return a[n / 2];    //下标从0开始，不是1，所以不需要减法

首先感谢您的答复，其次，有点问题表示疑问：
（1）我的62行是

int Mid[num] = { 0 };

所以“num”这个点应该是没什么问题。
（2）第二个点的话，虽然感觉很有道理，也不知道要怎么反驳，但是我有专门测试过这块，从结果来看是没有问题的，如下图：

img

所以应该是有其他的问题。

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 以下回答来自chatgpt:

    抱歉，根据问题描述无法得知具体情况，需要更多的上下文和代码片段才能确定问题出在哪里。可能是访问数组时下标越界，也可能是在读取数据时出现了争用。建议检查代码并逐步排查出问题所在。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^