这个系列是我多年前找工作时对数据结构和算法总结&＃xff0c;其中有基础部分&＃xff0c;也有各大公司的经典的面试题&＃xff0c;最早发布在CSDN。现整理为一个系列给需要的朋友参考&＃xff0c;如有错误&＃xff0c;欢迎指正。本系列完整代码地址在这里。

0 概述
在用C语言实现一些常见的数据结构和算法时&＃xff0c;C语言的基础不能少&＃xff0c;特别是指针和结构体等知识。

1 关于ELF文件
linux中的C编译得到的目标文件和可执行文件都是ELF格式的&＃xff0c;可执行文件中以segment来划分&＃xff0c;目标文件中&＃xff0c;我们是以section划分。一个segment包含一个或多个section&＃xff0c;通过readelf命令可以看到完整的section和segment信息。看一个栗子&＃xff1a;

`char pear[40]; static double peach; int mango &＃61; 13; char str &＃61; "hello";static long melon &＃61; 2001;int main() {int i &＃61; 3, j;pear[5] &＃61; i;peach &＃61; 2.0 mango;return 0; }`
这是个简单的C语言代码&＃xff0c;现在分析下各个变量存储的位置。其中mango&＃xff0c;melon属于data section&＃xff0c;pear和peach属于common section中&＃xff0c;而且peach和melon加了static&＃xff0c;说明只能本文件使用。而str对应的字符串"helloworld"存储在rodata section中。main函数归属于text section&＃xff0c;函数中的局部变量i,j在运行时在栈中分配空间。注意到前面说的全局未初始化变量peach和pear是在common section中&＃xff0c;这是为了强弱符号而设置的。那其实最终链接成为可执行文件后&＃xff0c;会归于BSS segment。同样的&＃xff0c;text section和rodata section在可执行文件中都属于同一个segment。

更多ELF内容参见《程序猿的自我修养》一书。

2 指针
想当年学习C语言最怕的就是指针了&＃xff0c;当然《c与指针》和《c专家编程》以及《高质量C编程》里面对指针都有很好的讲解&＃xff0c;系统回顾还是看书吧&＃xff0c;这里我总结了一些基础和易错的点。环境是ubuntu14.10的32位系统&＃xff0c;编译工具GCC。

2.1 指针易错点

/*** 指针易错示例1 demo1.c ***/int main() {char *str &＃61; "helloworld"; //[1]str[1] &＃61; &＃39;M&＃39;; //[2] 会报错char arr[] &＃61; "hello"; //[3]arr[1] &＃61; &＃39;M&＃39;;return 0; }

demo1.c中&＃xff0c;我们定义了一个指针和数组分别指向了一个字符串&＃xff0c;然后修改字符串中某个字符的值。编译后运行会发现[2]处会报错&＃xff0c;这是为什么呢&＃xff1f;用命令gcc -S demo1.c 生成汇编代码就会发现[1]处的helloworld是存储在rodata section的&＃xff0c;是只读的&＃xff0c;而[3]处的是存储在栈中的。所以[2]报错而[3]正常。在C中&＃xff0c;用[1]中的方式创建字符串常量并赋值给指针&＃xff0c;则字符串常量存储在rodata section。而如果是赋值给数组&＃xff0c;则存储在栈中或者data section中&＃xff08;如[3]就是存储在栈中&＃xff09;。示例2给出了更多容易出错的点&＃xff0c;可以看看。

/*** 指针易错示例2 demo2.c ***/ char *GetMemory(int num) {char *p &＃61; (char *)malloc(sizeof(char) * num);return p; }char *GetMemory2(char *p) {p &＃61; (char *)malloc(sizeof(char) * 100); }char *GetString(){char *string &＃61; "helloworld";return string; }char *GetString2(){char string[] &＃61; "helloworld";return string; }void ParamArray(char a[]) {printf("sizeof(a)&＃61;%d\n", sizeof(a)); // sizeof(a)&＃61;4&＃xff0c;参数以指针方式传递 }int main() {int a[] &＃61; {1, 2, 3, 4};int *b &＃61; a &＃43; 1;printf("delta&＃61;%d\n", b-a); // delta&＃61;4&＃xff0c;注意int数组步长为4printf("sizeof(a)&＃61;%d, sizeof(b)&＃61;%d\n", sizeof(a), sizeof(b)); //sizeof(a)&＃61;16, sizeof(b)&＃61;4ParamArray(a); //引用了不属于程序地址空间的地址&＃xff0c;导致段错误/*int *p &＃61; 0;*p &＃61; 17; */char *str &＃61; NULL;str &＃61; GetMemory(100);strcpy(str, "hello");free(str); //释放内存str &＃61; NULL; //避免野指针//错误版本&＃xff0c;这是因为函数参数传递的是副本。/*char *str2 &＃61; NULL;GetMemory2(str2);strcpy(str2, "hello");*/char *str3 &＃61; GetString();printf("%s\n", str3);//错误版本&＃xff0c;返回了栈指针&＃xff0c;编译器会有警告。/*char *str4 &＃61; GetString2();*/return 0; }

2.2 指针和数组

在2.1中也提到了部分指针和数组内容&＃xff0c;在C中指针和数组在某些情况下可以相互转换来使用&＃xff0c;比如char *str&＃61;"helloworld"可以通过str[1]来访问第二个字符&＃xff0c;也可以通过*(str&＃43;1)来访问。此外&＃xff0c;在函数参数中&＃xff0c;使用数组和指针也是等同的。但是指针和数组在有些地方并不等同&＃xff0c;需要特别注意。

比如我定义一个数组char a[9] &＃61; "abcdefgh";(注意字符串后面自动补\0),那么用a[1]读取字符&＃39;b&＃39;的流程是这样的&＃xff1a;

首先&＃xff0c;数组a有个地址&＃xff0c;我们假设是9980。
然后取偏移值&＃xff0c;偏移值为索引值*元素大小&＃xff0c;这里索引是1&＃xff0c;char大小也为1&＃xff0c;因此加上9980为9981&＃xff0c;得到数组a第1个元素的地址。&＃xff08;如果是int类型数组&＃xff0c;那么这里偏移就是1 * 4 &＃61; 4&＃xff09;
取地址9981处的值&＃xff0c;就是&＃39;b&＃39;。

那如果定义一个指针char *a &＃61; "abcdefgh";&＃xff0c;我们通过a[1]来取第一个元素的值。跟数组流程不同的是&＃xff1a;

首先&＃xff0c;指针a自己有个地址&＃xff0c;假设是4541.
然后&＃xff0c;从4541取a的值&＃xff0c;也就是字符串“abcdefgh”的地址&＃xff0c;假定是5081。
接着就是跟之前一样的步骤了&＃xff0c;5081加上偏移1&＃xff0c;取5082地址处的值&＃xff0c;这里就是&＃39;b&＃39;了。

通过上面的说明可以发现&＃xff0c;指针比数组多了一个步骤&＃xff0c;虽然看起来结果是一致的。因此&＃xff0c;下面这个错误就比较好理解了。在demo3.c中定义了一个数组&＃xff0c;然后在demo4.c中通过指针来声明并引用它&＃xff0c;显然是会报错的。如果改成extern char p[];就正确了&＃xff08;当然声明你也可以写成extern char p[3],声明里面的数组大小跟实际大小不一致是没有关系的&＃xff09;&＃xff0c;一定要保证定义和声明匹配。

/*** demo3.c ***/ char p[] &＃61; "helloworld";/*** demo4.c ***/ extern char *p; int main() {printf("%c\n", p[1]);return 0; }

3 typedef和#define
typedef和#define都是经常用的&＃xff0c;但是它们是不一样的。一个typedef可以塞入多个声明器&＃xff0c;而#define一般只能有一个定义。在连续声明中&＃xff0c;typedef定义的类型可以保证声明的变量都是同一种类型&＃xff0c;而#define不行。此外&＃xff0c;typedef是一种彻底的封装类型&＃xff0c;在声明之后不能再添加其他的类型。如代码中所示。

`#define int_ptr int * int_ptr i, j; //i是int 类型&＃xff0c;而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; //错误&＃xff0c;typedef声明的类型不能扩展其他类型。`
另外&＃xff0c;typedef在结构体定义中也很常见&＃xff0c;比如下面代码中的定义。需要注意的是&＃xff0c;[1]和[2]是很不同的。当你如[1]中那样用typedef定义了struct foo&＃xff0c;那么其实除了本身的foo结构标签&＃xff0c;你还定义了foo这种结构类型&＃xff0c;所以可以直接用foo来声明变量。而如[2]中的定义是不能用bar来声明变量的&＃xff0c;因为它只是一个结构变量&＃xff0c;并不是结构类型。

还有一点需要说明的是&＃xff0c;结构体是有自己名字空间的&＃xff0c;所以结构体中的字段可以跟结构体名字相同&＃xff0c;比如[3]中那样也是合法的&＃xff0c;当然尽量不要这样用。后面一节还会更详细探讨结构体&＃xff0c;因为在Python源码中也有用到很多结构体。

`typedef struct foo {int i;} foo; //[1] struct bar {int i;} bar; //[2]struct foo f; //正确&＃xff0c;使用结构标签foo foo f; //正确&＃xff0c;使用结构类型foostruct bar b; //正确&＃xff0c;使用结构标签bar bar b; // 错误&＃xff0c;使用了结构变量bar&＃xff0c;bar已经是个结构体变量了&＃xff0c;可以直接初始化&＃xff0c;比如bar.i &＃61; 4;struct foobar {int foorbar;}; //[3]合法的定义`

4 结构体
在学习数据结构的时候&＃xff0c;定义链表和树结构会经常用到结构体。比如下面这个&＃xff1a;

`struct node {int data;struct node* next; };`
在定义链表的时候可能就有点奇怪了&＃xff0c;为什么可以这样定义&＃xff0c;貌似这个时候struct node还没有定义好为什么就可以用next指针指向用这个结构体定义了呢&＃xff1f;

4.1 不完全类型

这里要说下C语言里面的不完全类型。C语言可以分为函数类型&＃xff0c;对象类型以及不完全类型。而对象类型还可以分为标量类型和非标量类型。算术类型&＃xff08;如int&＃xff0c;float&＃xff0c;char等&＃xff09;和指针类型属于标量类型&＃xff0c;而定义完整的结构体&＃xff0c;联合体&＃xff0c;数组等都是非标量类型。而不完全类型是指没有定义完整的类型&＃xff0c;比如下面这样的

struct s; union u; char str[];

具有不完全类型的变量可以通过多次声明组合成一个完全类型。比如下面2词声明str数组是合法的&＃xff1a;

char str[]; char str[10];

此外&＃xff0c;如果两个源文件定义了同一个变量&＃xff0c;只要它们不全部是强类型的&＃xff0c;那么也是可以编译通过的。比如下面这样是合法的&＃xff0c;但是如果将file1.c中的int i;改成强定义如int i &＃61; 5;那么就会出错了。

//file1.c int i;//file2.c int i &＃61; 4;

4.2 不完全类型结构体

不完全类型的结构体十分重要&＃xff0c;比如我们最开始提到的struct node的定义&＃xff0c;编译器从前往后处理&＃xff0c;发现struct node *next时&＃xff0c;认为struct node是一个不完全类型&＃xff0c;next是一个指向不完全类型的指针&＃xff0c;尽管如此&＃xff0c;指针本身是完全类型&＃xff0c;因为不管什么指针在32位系统都是占用4个字节。而到后面定义结束&＃xff0c;struct node成了一个完全类型&＃xff0c;从而next就是一个指向完全类型的指针了。

4.3 结构体初始化和大小

结构体初始化比较简单&＃xff0c;需要注意的是结构体中包含有指针的时候&＃xff0c;如果要进行字符串拷贝之类的操作&＃xff0c;对指针需要额外分配内存空间。如下面定义了一个结构体student的变量stu和指向结构体的指针pstu&＃xff0c;虽然stu定义的时候已经隐式分配了结构体内存&＃xff0c;但是你要拷贝字符串到它指向的内存的话&＃xff0c;需要显示分配内存。

struct student {char *name;int age; } stu, *pstu;int main() {stu.age &＃61; 13; //正确// strcpy(stu.name,"hello"); //错误&＃xff0c;name还没有分配内存空间stu.name &＃61; (char *)malloc(6);strcpy(stu.name, "hello"); //正确return 0; }

结构体大小涉及一个对齐的问题&＃xff0c;对齐规则为&＃xff1a;

结构体变量首地址为最宽成员长度&＃xff08;如果有#pragma pack(n)&＃xff0c;则取最宽成员长度和n的较小值&＃xff0c;默认pragma的n&＃61;8&＃xff09;的整数倍
结构体大小为最宽成员长度的整数倍
结构体每个成员相对结构体首地址的偏移量都是每个成员本身大小&＃xff08;如果有pragma pack(n),则是n与成员大小的较小值&＃xff09;的整数倍因此&＃xff0c;下面结构体S1和S2虽然内容一样&＃xff0c;但是字段顺序不同&＃xff0c;大小也不同&＃xff0c;sizeof(S1) &＃61; 8, 而sizeof(S2) &＃61; 12. 如果定义了#pragma pack(2)&＃xff0c;则sizeof(S1)&＃61;8&＃xff1b;sizeof(S2)&＃61;8

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

4.4 柔性数组

柔性数组是指结构体的最后面一个成员可以是一个大小未知的数组&＃xff0c;这样可以在结构体中存放变长的字符串。如代码中所示。**注意&＃xff0c;柔性数组必须是结构体最后一个成员,柔性数组不占用结构体大小.**当然&＃xff0c;你也可以将数组写成char str[0],含义相同。

注&＃xff1a;在学习Python源码过程中&＃xff0c;发现其柔性数组声明并不是用一个空数组或者char str[0]&＃xff0c;而是用的char str[1]&＃xff0c;即数组大小为1。这是因为ISO C标准不允许声明大小为0的数组(gcc -pedanti参数可以检查是否符合ISO C标准)&＃xff0c;为了可移植性&＃xff0c;所以常常看到的是声明数组大小为1。当然&＃xff0c;很多编译器比如GCC等把数组大小为0作为了一个非标准的扩展&＃xff0c;所以声明空的或者大小为0的柔性数组在GCC中是可以正常编译的。

struct flexarray {int len;char str[]; } *pfarr;int main() {char s1[] &＃61; "hello, world";pfarr &＃61; malloc(sizeof(struct flexarray) &＃43; strlen(s1) &＃43; 1);pfarr->len &＃61; strlen(s1);strcpy(pfarr->str, s1);printf("%d\n", sizeof(struct flexarray)); // 4printf("%d\n", pfarr->len); // 12printf("%s\n", pfarr->str); // hello, worldreturn 0; }