1

试图了解我的数据结构类的基数排序。我的老师向我们展示了 C++ 中的基数排序示例。我不明白数字的 for 循环是做什么的，她说了一些关于最大数字的事情。此外，当我在 VS 中尝试此操作时，它说 log10 是对重载函数的模棱两可的调用。

void RadixSort(int A[], int size)
{
    int d = 1;
        for(int i = 0; i < size; ++i) 
        {
            int digits_temp;
            digits_temp=(int)log10(abs(A[i]!=0 ? abs(A[i]) : 1)) +1;
            if(digits_temp > d)
                d = digits_temp;
        }
        d += 1;

*rest of the implementation*
}

谁能解释这个 for 循环的作用以及为什么我得到那个模棱两可的调用错误？谢谢

4

5 回答 5

2

那段代码只是搜索“最长”整数所需的位数；这可能需要稍后分配一些缓冲区。

log10为您提供与其参数对应的十的幂，该参数四舍五入到下一个整数（因此+1后跟强制转换(int)，这会导致截断），为您提供数字所需的位数。

的论点log10有点混乱，因为abs只调用一次就足够了。尽管如此，这个想法是传递给log10正在检查的数字的绝对值，如果它不为零，或者如果它为零，则传递 1 - 这是因为，如果参数为零，对数将发散到负无穷大（这在在这种情况下，我认为转换为int会导致奇怪的结果）。

循环的其余部分只是搜索最大值：在每次迭代中，它都会计算当前正在检查的 int 所需的数字，检查它是否大于“当前最大值”（d），如果是，则替换“当前最大值”。

可能是出于警示目的 (?) 或用于分配字符串的d+=1空终止符，这取决于d之后的使用方式。

至于“歧义调用”错误：您得到它是因为您使用参数调用log10，该int参数可以转换为float, doubleand long double（所有类型都log10被重载），因此编译器不清楚要选择的重载。(double)在整个log10论点之前加上一个演员表。

顺便说一句，该代码可以通过查找最大值int（绝对值）然后采用以 10 为底的对数来发现所需的位数来简化/优化。

于 2012-02-09T23:53:47.463 回答
0

您会看到警告，因为 log10 是为 float、double 和 long double 定义的，但不是整数，它是用整数调用的。编译器可以将 int 转换为任何这些类型，因此调用是不明确的。

for 循环对数组中任何数字的最大位数进行线性搜索。它不必要地复杂和缓慢，因为您可以简单地搜索 A 中的最大绝对值，然后取其 log10。

void RadixSort(int A[], int size)
{
    int max_abs = 1;
    for(int i = 0; i < size; ++i) 
    {
        if(abs(A[i] > max_abs)
            max_abs = abs(A[i]);
    }
    int d += log10(float(max_abs));

   /* rest of the implementation */
}
于 2012-02-09T23:51:41.410 回答
0

Log base 10 + 1 为您提供数字中存在的总位数。基本上在这里，您正在检查数组中的每个元素，A[]如果元素为 == 0，则将 1 存储在 digits_temp 变量中。您将 d = 1 初始化为一个数字应该至少有 1 位，如果它超过 1，则将其替换为计算的位数。

希望有帮助。

于 2012-02-09T23:51:55.253 回答
0

log10 函数的定义有 3 种类型，分别是 float、double、long double 输入。

log10( static_cast<double> (abs(A[i]!=0 ? abs(A[i]) : 1)) );

因此，您需要将其静态转换为 double 以避免错误。

(int)log10(x)+1 给出该数字中存在的位数。

Rest 是基数排序的简单实现

于 2012-02-09T23:56:17.477 回答
0

缺少其余代码，因此无法准确确定用法。

但基本上基数排序会遍历所有整数并对它们进行排序，比较数字从最不重要的向上开始。

代码的第一部分仅从数组中的整数确定最大位数 count+1，这可用于将所有数字标准化为相同长度以便于处理。

即（1,239,2134）到（0001,0239,2134）

于 2012-02-10T00:03:57.023 回答