c - C中如何进行就地计算

Question

我正在研究一个简单的就地傅里叶变换。但我不知道就地是如何发生的。例如以下代码片段，取自 https://rosettacode.org/wiki/Fast_Fourier_transform#C

由于函数声明void fft(cplx buf[], int n)，没有任何输出，子函数中buf的变化怎么传回来进入主函数？

#include <stdio.h>
#include <math.h>
#include <complex.h>

double PI;
typedef double complex cplx;

void _fft(cplx buf[], cplx out[], int n, int step)
{
if (step < n) {
    _fft(out, buf, n, step * 2);
    _fft(out + step, buf + step, n, step * 2);

    for (int i = 0; i < n; i += 2 * step) {
        cplx t = cexp(-I * PI * i / n) * out[i + step];
        buf[i / 2]     = out[i] + t;
        buf[(i + n)/2] = out[i] - t;
    }
}
}

void fft(cplx buf[], int n)
{
cplx out[n];
for (int i = 0; i < n; i++) out[i] = buf[i];

_fft(buf, out, n, 1);
}


void show(const char * s, cplx buf[]) {
printf("%s", s);
for (int i = 0; i < 8; i++)
    if (!cimag(buf[i]))
        printf("%g ", creal(buf[i]));
    else
        printf("(%g, %g) ", creal(buf[i]), cimag(buf[i]));
}

int main()
{
PI = atan2(1, 1) * 4;
cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};

show("Data: ", buf);
fft(buf, 8);
show("\nFFT : ", buf);

return 0;
}

我不确定我是否把问题说清楚了。我在下面写了一个片段，与上面的结构相同。但是，它在就地模式下不起作用，我的意思是子函数中变量的值变化没有传递到主函数中。

#include <stdio.h>

void _sumab(int a, int b, int c)
{
printf("2: %d, %d, %d\n", a, b, c );
a = 2*a + b+c;
b = 12;
// if(a<800) _sumab(a, b, c);
printf("3: %d, %d, %d\n", a, b, c );
}

void sumab(int a, int b, int c)
{
printf("1: %d, %d, %d\n", a, b, c );
_sumab(a, b, c);
a = a*4;
printf("4: %d, %d, %d\n", a, b, c);
}


int main()
{
int out1 = 0;
int out2 = 1;
int out3 = 2;
sumab(out1+100, out2, out3);
printf("5: %d, %d, %d\n", out1, out2, out3);
return 0; 
}

在前面的代码中，调用子函数后，存储在buf中的值发生变化，即使在主函数中也是如此。但在后面的代码中，调用子函数后，a, b, c 的值保持不变，因为它们在主函数范围内。为什么？

我是否遗漏了一些重要的问题或其他问题？就地如何进行？

如果fft(buf, 8)表示计算buf的傅立叶变换，并且仍然存储在buf中，表达式如何fft(buf+2, 8)，它会计算buf+2的傅里叶变换，但存储在什么地方？

提前致谢。

Answer 1

你的问题的关键在于，在 C 中，你不能将数组传递给函数。

当你这样写的时候:

void fft(cplx buf[], int n)

根据 C11 标准的 §6.7.6.3 p7 中定义的规则(引用最新的公开草案，n1570，在这里):

A declaration of a parameter as ‘‘array of type’’ shall be adjusted to ‘‘qualified pointer to type’’, where the type qualifiers (if any) are those specified within the [ and ] of the array type derivation. [...]

这意味着，真正的声明看起来像这样:

void fft(cplx *buf, int n)

所以，您实际上是在传递一个指针，函数可以通过该指针操作原始数组。

---

*) 人们常说数组像指针一样衰减。这不是标准的官方措辞，但被广泛理解。如果你有这样的数组:

char a[5];

你只需编写 a，它被评估为指向 a 的第一个元素的指针，类型为 char *。因此，使用这样声明的函数:

void foo(char x[]);

你可以这样调用它

foo(a);

真正传递的是指向 a 的第一个元素的指针，因此，a 作为指针“衰减”。