面试算法题：C语言指针、数组和结构体

terry 2年前 (2023-09-27) 阅读数 67 #数据结构与算法

在用C语言实现一些常见的数据结构和算法时，需要C语言的基础知识，尤其是指针和结构体的知识。

1。关于ELF文件

在Linux中，C翻译得到的目标文件和可执行文件都是ELF格式。可执行文件分为多个部分，目标文件也分为多个部分。一个段包含一个或多个部分，您可以通过 readelf 命令查看部分和段的完整详细信息。看栗子：

char pear[40];
static double peach;
int mango = 13;
char *str = "hello";

static long melon = 2001;

int main()
{
    int i = 3, j;
    pear[5] = i;
    peach = 2.0 * mango;
    return 0;
}
复制代码

这是简单的C代码。现在分析一下各个变量的存储位置。其中mango和melon属于信息部分，pear和Future属于公共部分，将Future和melon添加为static，表示只能在本文件中使用。与str对应的字符串“helloworld”存储在rodata部分中。

main函数属于文本部分，函数的局部变量i和j在运行时在栈上预留空间。注意前面提到的全局未初始化变量Kongzi和pear在common部分，为强符号和弱符号设置。事实上，当最后一个链接成为可执行文件时，它就属于BSS段。相应地，文本部分和rodata部分在可执行文件中属于同一段。

更多ELF内容，请参阅书《程序猿的自我修养》。

2。指针

我想我在学习指针时最害怕的是C。当然，《c与指针》和《c专家编程》和《高质量C编程》很好地解释了指针。对于系统的概述，让我们看一下这本书，其中我收集了一些基本的和容易出错的点。环境为32位ubuntu14.10系统，编译工具为GCC。

2.1 容易出现指针错误的点

/***
指针易错示例1 demo1.c
***/

int main()
{
    char *str = "helloworld"; //[1]
    str[1] = 'M'; //[2] 会报错
    char arr[] = "hello"; //[3]
    arr[1] = 'M';
    return 0;
}
复制代码

Demo1.c 分别定义了一个指向字符串的指针和一个数组，然后更改字符串的字符值。编译运行后，会发现错误如[2]。为什么是这样？使用命令 gcc -S demo1.c 生成汇编代码。您会注意到[1]处的helloworld存储在rodata分区中并且是只读的，而[3]处的helloworld存储在堆栈上。。所以[2]报错，[3]正常。在C中，使用[1]中的方法创建一个字符串常量并将其分配给一个指针，然后将该字符串常量存储在rodata段中。如果定义在数组中，则存储在堆栈或数据段中（例如，[3] 存储在堆栈中）。示例 2 显示了更多需要注意的容易出错的点。

/***
指针易错示例2 demo2.c
***/
char *GetMemory(int num) {
    char *p = (char *)malloc(sizeof(char) * num);
    return p;
}

char *GetMemory2(char *p) {
    p = (char *)malloc(sizeof(char) * 100);
}

char *GetString(){
    char *string = "helloworld";
    return string;
}

char *GetString2(){
    char string[] = "helloworld";
    return string;
}

void ParamArray(char a[])
{
    printf("sizeof(a)=%d\n", sizeof(a)); // sizeof(a)=4，参数以指针方式传递
}

int main()
{
    int a[] = {1, 2, 3, 4};
    int *b = a + 1;
    printf("delta=%d\n", b-a); // delta=4，注意int数组步长为4
    printf("sizeof(a)=%d, sizeof(b)=%d\n", sizeof(a), sizeof(b)); //sizeof(a)=16, sizeof(b)=4
    ParamArray(a); 
        
        
    //引用了不属于程序地址空间的地址，导致段错误
    /*
    int *p = 0;
    *p = 17;         
    */
        
    char *str = NULL;
    str = GetMemory(100);
    strcpy(str, "hello");
    free(str); //释放内存
    str = NULL; //避免野指针

	//错误版本，这是因为函数参数传递的是副本。
	/*
    char *str2 = NULL;
    GetMemory2(str2);
    strcpy(str2, "hello");
    */

    char *str3 = GetString();
    printf("%s\n", str3);

    //错误版本，返回了栈指针，编译器会有警告。
    /*
    char *str4 = GetString2();
    */
    return 0;
}
复制代码

2.2 指针和表格

2.1 节中还提到了一些指针和表格内容。在C中，指针和数组在某些情况下是可以互相转换的，比如 char *str="helloworld" 第二个字符可以通过键str[1]访问或通过 *(str+1 )。此外，在函数参数中使用数组和指针是等效的。 但是指针和表格有的地方不匹配，需要特别注意。

例如，如果我定义数组char a[9] = "abcdefgh";（注意字符串后面会自动添加\0），使用a[1]读取字符' b'是这样的：

首先，数组a有一个地址，假设是9980。
然后取偏移值，即索引值*元素大小。这里索引为1，字符大小也为1，所以将9980加9981，得到数组a第一个元素的地址。（如果是int类型的数组，这里的偏移量是1 * 4 = 4）
从地址9981中取出值，即'b'。

然后如果我们定义指针char *a = "abcdefgh";，我们使用a[1]来获取第一个元素的值。与数组过程的区别在于：

首先，指针a如果是4541，就有自己的地址。
然后从4541中取出a的值，即字符串“abcdefgh”的地址。假设是 5081。
然后按照前面相同的步骤，将偏移量 1 添加到 5081，并从 5082 中取出值，即此处的“b”。

通过上面的解释，我们可以看到指针比数组多了一步，虽然结果看起来是一致的。因此，下面的错误更容易理解。如果在demo3.c中定义了一个数组，然后在demo4.c中通过指针声明并引用了该数组，则会清楚地报告错误。如果改成extern char p[];，那就对了（当然你也可以写成external char p[3]，语句数组大小不一致也没关系与实际大小），您需要确保定义和声明匹配。

/***
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]那样使用typedef定义struct foo时，实际上除了foo结构体标签本身之外，你还定义了struct类型foo，所以你可以直接使用foo来声明变量。正如[2]中所定义的，bar不能用来声明变量，因为它只是一个结构体变量，而不是一个结构体类型。

另外需要说明的是，结构体有自己的命名空间，因此结构体的字段可以与结构体同名。例如，它是合法的，如[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 数组的 2 字声明是合法的：

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)，则取最宽成员的较小值。 length 和 n，默认 pragma (n=8) 是一个整数倍它本身是每个成员大小的整数倍（如果 pragma package(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 灵活数组的最后一个成员表示 Flex 结构可以是一个未知大小的数组，在这种情况下，可以在结构中存储可变长度的字符串，如代码所示。注意，柔性数组必须是结构体的最后一个成员，并且柔性数组不会填满结构体的大小。当然，你也可以将数组写成`char str[0]`，意义相同。

注：在学习Python源码时，我注意到灵活数组定义并没有使用空数组或char str[0]，而是char str[1] 即数组的大小为1。这是因为ISO C标准不允许指定大小为0的数组（参数gcc pedant可以检查是否是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;
}
复制代码