面试题：C语言复杂数据结构下指针解引用优化

Question

假设我们有一个复杂的数据结构，由多层嵌套的结构体和指针构成，如下所示： ```c struct Inner { int data[100]; }; struct Middle { struct Inner *inner; }; struct Outer { struct Middle *middle[50]; }; ``` 现在需要遍历所有 `Inner` 结构体中的 `data` 数组元素并进行求和操作。请设计一个高效的算法，尽可能减少指针解引用次数以提升性能，同时分析该算法在时间复杂度和空间复杂度上的表现。

Answer 1

#include <stdio.h>

// 计算Inner结构体中data数组元素的和
int sumInnerData(struct Inner *inner) {
    int sum = 0;
    for (int i = 0; i < 100; i++) {
        sum += inner->data[i];
    }
    return sum;
}

// 遍历所有Inner结构体中的data数组元素并求和
int sumAllInnerData(struct Outer *outer) {
    int totalSum = 0;
    for (int i = 0; i < 50; i++) {
        if (outer->middle[i] != NULL && outer->middle[i]->inner != NULL) {
            totalSum += sumInnerData(outer->middle[i]->inner);
        }
    }
    return totalSum;
}

时间复杂度分析

• 最内层循环遍历Inner结构体中的data数组，长度为100，时间复杂度为$O(100)$，可视为$O(1)$。
• 外层循环遍历Outer结构体中的middle数组，长度为50，每次循环调用sumInnerData函数，时间复杂度为$O(50)$。
• 整体时间复杂度为$O(50 \times 1) = O(1)$ ，因为50是常数。

空间复杂度分析

• 算法中使用了几个临时变量sum、totalSum和循环变量i，这些变量占用的空间是常数级别的。
• 没有使用额外的与输入规模相关的空间。
• 所以空间复杂度为$O(1)$。

使用示例

int main() {
    struct Inner inner1 = {0};
    struct Inner inner2 = {0};
    struct Middle middle1 = {&inner1};
    struct Middle middle2 = {&inner2};
    struct Outer outer = {&middle1, &middle2};

    int sum = sumAllInnerData(&outer);
    printf("Sum of all Inner data elements: %d\n", sum);
    return 0;
}