面试题：C语言结构体指针在数组中的应用及优化

Question

给定一个结构体数组struct Book { char title[50]; char author[30]; int pages; } books[10]; 请使用结构体指针遍历该数组，找出页数最多的书籍，并输出其标题和作者。同时，说明相比普通数组访问方式，使用结构体指针在这里有什么优势，在时间复杂度和空间复杂度方面如何体现。

Answer 1

#include <stdio.h>
#include <string.h>

struct Book {
    char title[50];
    char author[30];
    int pages;
};

int main() {
    struct Book books[10] = {
        {"Book1", "Author1", 100},
        {"Book2", "Author2", 150},
        {"Book3", "Author3", 120},
        {"Book4", "Author4", 200},
        {"Book5", "Author5", 90},
        {"Book6", "Author6", 180},
        {"Book7", "Author7", 130},
        {"Book8", "Author8", 160},
        {"Book9", "Author9", 110},
        {"Book10", "Author10", 140}
    };
    struct Book *ptr = books;
    struct Book *maxBook = ptr;
    for (int i = 0; i < 10; i++) {
        if ((*(ptr + i)).pages > maxBook->pages) {
            maxBook = ptr + i;
        }
    }
    printf("Title: %s\nAuthor: %s\n", maxBook->title, maxBook->author);
    return 0;
}

结构体指针的优势

1. 灵活性：结构体指针可以方便地进行动态内存分配和释放，而数组的大小在定义时就固定了。
2. 效率：在传递结构体时，传递指针比传递整个结构体要高效，因为传递指针只需要传递地址，而传递结构体需要复制整个结构体的内容。

时间复杂度

• 结构体指针遍历：时间复杂度为O(n)，因为需要遍历数组中的每一个元素来找出页数最多的书籍。
• 普通数组访问：时间复杂度同样为O(n)，因为同样需要遍历每一个元素，在时间复杂度方面两者没有差异。

空间复杂度

• 结构体指针：空间复杂度为O(1)，除了数组本身占用的空间外，只额外使用了一个指针变量。
• 普通数组访问：空间复杂度也为O(1)，同样除了数组本身占用空间外，没有额外的空间开销，在空间复杂度方面两者基本相同，不过在动态内存分配场景下，结构体指针优势明显。