C 指针、数组和结构算法面试题

/***
demo3.c
***/
char p[] = "helloworld";

/***
demo4.c
***/
extern char *p;
int main()
{
    printf("%c\n", p[1]);
    return 0;
}
复制代码

3 typedef 和 #define

typedef 和 #define 都很常见，但又有所不同。一个 typedef 可以包含多个声明符，而 #define 通常只能有一个定义。在常量声明中，通过typedef定义的类型可以保证声明的变量都是同一类型，但#define则不能。另外，typedef 是一个完整的封装类型，声明后不能添加其他类型。如代码所示。

#define int_ptr int *
int_ptr i, j; //i是int *类型，而j是int类型。

typedef char * char_ptr;
char_ptr c1, c2; //c1, c2都是char *类型。

#define peach int
unsigned peach i; //正确

typdef int banana;
unsigned banana j; //错误，typedef声明的类型不能扩展其他类型。
复制代码

此外，typedef 在结构体定义中也很常见，例如在下面代码的定义中。应该指出的是，[1]和[2]有很大不同。当您像[1]中那样定义struct foo时，除了结构体标记foo之外，还定义了结构体类型foo，因此您可以直接使用foo来声明变量。正如[2]中所定义的，strip不能用于声明变量，因为它只是一个结构变量，而不是一个结构类型。

另一点需要澄清的是，结构体有自己的命名空间，因此结构体中的字段可以与结构体具有相同的名称。例如，[3] 是合法的。当然，尽量不要这样使用。结构体将在后面的部分中更详细地讨论，因为Python源代码中也使用了许多结构体。

typedef struct foo {int i;} foo; //[1]
struct bar {int i;} bar; //[2]

struct foo f; //正确，使用结构标签foo
foo f; //正确，使用结构类型foo

struct bar b; //正确，使用结构标签bar
bar b; // 错误，使用了结构变量bar，bar已经是个结构体变量了，可以直接初始化，比如bar.i = 4;

struct foobar {int foorbar;}; //[3]合法的定义
复制代码

4 结构

在学习数据结构时，结构常常用来定义链表和树结构。例如：

struct node {
    int data;
    struct node* next;
};
复制代码

定义链表时，可能会有点奇怪。为什么可以这样定义呢？看来结构节点尚未定义。为什么可以被后面的指针所指向并通过其结构体来定义呢？

4.1 不完全类型

这里我们说的是C语言的不完全类型。 C语言可以分为函数类型、对象类型和不完全类型。对象类型还可以分为标量类型和非标量类型。算术类型（如 int、float、char 等）和指针类型是标量类型，而完全定义的结构、联合、数组等是非标量类型。不完整类型是指没有完全定义的类型，比如下面的

struct s;
union u;
char str[];
复制代码

不完整类型的变量可以通过多次声明组合成完整类型。例如，下面的 str 数组的两个字声明是合法的：

char str[];
char str[10];
复制代码

另外，如果两个源文件定义了相同的变量，只要它们不是都是强类型的，就可以编译。例如，以下内容是合法的，但如果将 file1.c 中的参数 int i; 更改为强定义，例如 int i = 5;，则会出现错误。

//file1.c
int i;

//file2.c
int i = 4;
复制代码

4.2 不完全类型结构

不完全类型结构非常重要。比如我们一开始提到的struct node的定义，编译器从前到后处理，发现了struct node *next，则认为struct node是一个不完整类型，next是一个指向不完整类型的指针。然而，指针本身是整数类型，因为在 32 位系统上任何指针都占用 4 个字节。在下一个定义结束时，结构体节点变成整数类型，因此下一个是指向整数类型的指针。

4.3 结构初始化和大小

结构初始化相对简单。需要注意的是，如果结构体中包含指针，则必须为指针分配额外的内存空间，以执行复制字符串等操作。例如，结构体student变量stu和指向结构体pstu的指针定义如下。虽然结构体内存是在定义stu时隐式分配的，但是如果要将字符串复制到它指向的内存中，则必须显式分配内存。 。

struct student {
    char *name;
    int age;
} stu, *pstu;

int main()
{
    stu.age = 13; //正确
    // strcpy(stu.name,"hello"); //错误，name还没有分配内存空间
        
    stu.name = (char *)malloc(6);
    strcpy(stu.name, "hello"); //正确
        
    return 0;
}
复制代码

结构尺寸与走线问题有关。对齐规则如下：

• 结构体变量的首地址为最宽元素的长度（如果有#pragma pack(n)，则取最宽成员的较小值长度和n，默认pragma n=8)
• 结构体的大小是最宽元素长度的整数倍
• 结构体每个成员相对于结构体首地址的偏移量结构体是每个成员本身大小的整数（如果有pragma pack(n)，则为n和成员大小中较小的值）。因此，虽然下面的结构体S1和S2的内容相同，但字段的顺序和大小也不同，sizeof(S1) = 8和sizeof(S2) = 12。如果定义了#pragma pack(2)，则sizeof(S1)=8； sizeof( S2)=8

typedef struct node1
{
    int a;
    char b;
    short c;
}S1;

typedef struct node2
{
    char b;
    int a;
    short c;
}S2;
复制代码

4.4 灵活数组

灵活数组意味着结构体的最后一个成员可以是未知大小的数组，因此该结构体可以存储可变长度的字符串。如代码所示。 **注意，灵活数组必须是结构体的最后一个成员，并且灵活数组不占用结构体的大小。** 当然，你也可以将数组写成 char str[0]，具有相同的含义。

注意。在学习Python源代码时，我发现灵活数组声明不使用空数组或char str[0]，而是使用char str[1] ，即大小数组的值为1。这是因为ISO C标准不允许声明大小为0的数组（参数gcc -pedanti可以检查是否符合ISO C标准）。为了可移植性，经常看到数组的大小为1。。当然，许多编译器，例如GCC，将数组大小0视为非标准扩展，因此声明大小为0的空数组或灵活数组可以在GCC中正常编译。

struct flexarray {
    int len;
    char str[];
} *pfarr;

int main()
{
    char s1[] = "hello, world";
    pfarr = malloc(sizeof(struct flexarray) + strlen(s1) + 1);
    pfarr->len = strlen(s1);
    strcpy(pfarr->str, s1);
    printf("%d\n", sizeof(struct flexarray)); // 4
    printf("%d\n", pfarr->len); // 12
    printf("%s\n", pfarr->str); // hello, world
    return 0;
}
复制代码

5 总结

• 至于const，C中的const不是常量，所以const变量不能用来定义数组，例如const int N = 3; int a[N];这是一个错误。
• 注意分配和释放内存，避免疯狂提示。
• 在 C 语言中，组合弱符号和强符号是合法的。
• 注意指针和数组之间的区别。
• typedef 和 #define 是不同的。
• 注意初始化包含引用的结构体并使用灵活的数组。

作者：ssjhust