算法与数据结构前置知识(2)—c语言结构化类型
1. 结构
1.1. 结构的基本逻辑
结构体在c语言中相当于一栋房子的主体框架，也是学习数据结构必需要掌握的，这是数据结构系统文章的前置知识第二篇。
1.1.1 结构声明
c语言的结构体声明有很多种方式，非常灵活。下面我们来看几个例子。
struct {
int age;
char *name;
} group[5], *james;
上面声明并且创建了结构体group,james。group是一个数组，包含了5个结构体。james是一个结构体指针。要注意的是，group和james的类型并不一样，group是一个数组，james是一个指针。
我们可以使用结构标签来表示一个结构体，达到类型统一的目的。
struct USER{
int age;
char *name;
};
以上我们声明了一个标签名为user的结构体，这样我们就可以通过标签来创建结构体变量了。
struct USER group[20];
struct USER james;
可以看到，我们创建了group数组，和james结构体变量，这时候group和james的类型就是一致的了，都是struct USER类型。
进一步，我们可以使用typedef给结构定义一个别名来简化结构的使用，如下：
typedef struct _USER {
int age;
char *name;
} USER;
我们定义了一个结构体_USER并为它取了一个别名USER。这时候，我们就可以使用别名来创建结构体变量了。如下：
USER group[20];
USER james;
以上就是关于结构体的声明，以及当中可能出现的坑。
1.1.2. 结构成员
在上面，我们声明了一个结构体，包含了一个整型的age和一个字符型name成员。实际上，结构成员可以任意c语言当中的类型，包含结构、联合、枚举，在我们后面的一个小实战就使用到了多种类型的结构成员。
typedef struct _USER{
int age;
char *name;
} USER;
struct _GROUP {
int num;
char *group_name;
int quarer[4];
float average;
USER leader;
USER *admin;
};
上面创建了一个_GROUP结构，其中包含了一个_USER结构和一个_USER结构指针
1.1.3. 结构初始化
结构的初始化和数组的初始化很类似。以上面_GROUP为例
USER le = {24,"张三"};
USER ad = {32,"管理员"};
struct _GROUP group = {30, "技术中心",{20,40}, 12000.00, le, &ad};
上面初始化了一个USER类型的le，一个USER类型的ad。然后初始化了一个struct _GROUP类型的group，包含了成员：
整形num，字符型group_name，长度为4的整形数组quarter，USER类型的结构体leader和USER类型的结构体指针admin。当然，上面的USER leader和USER *admin也可以写成struct _USER leader和struct _USER *admin，一般我们为了简化都可以使用别名，但也有例外，我们会在自引用那一节详细探讨。
我们也可以部分初始化，例如：
struct _GROUP group ={30, "技术中心"};
上面没有被初始化到的结构会使用缺省值进行初始化，例如上面的quarer我们没有初始化，那么group里的quarer就是长度为4元素值为0的数组，admin就是一个指针，leader就是一个成员age为0，name为NULL的结构。
既然结构成员有名字，我们也可以使用"."操作符选择性初始化结构成员。例如：
struct _GROUP group = {.age=30,.admin=&ad};
1.1.4. 访问结构成员
上面我们通过各种方式初始化了结构，下面我们来看怎么使用有结构成员。
同样，我们可以使用“.”操作符来访问结构成员，例如：
int gage;
gage = group.age;
同样的，我们可以通过这种方式修改结构成员，例如：
group.age = 40;
group.quarer[0] = 30;
针对结构指针的访问要稍微复杂一点，但如果有前面指针的基础，应该也不难。例如：
int gage;
struct _GROUP *g1 = &group;
gage = (*g1).age;
(*g1).age = 33;
在c语言中，“.”操作符优先级要高于“*”解引用操作符，所以要用括号括起来。
c编译器还提供了一个“->”符号通过结构体指针进行间接访问。例如：
int uage;
USER *u1 = ≤
uage = u1->age;
u1->age = 45;
注意：“->”操作符只能使用于结构指针，在结构变量使用“->”操作符是编译不通过的。
1.1.5. 结构自引用
上面说到结构成员也可以是一个结构。当然，结构成员也可以是结构自己，这类技巧是后面的比如：链表、树等数据结构的基础。
下面来实现一个简单的链表：
typedef struct _NODE{
int data;
Node *next;
} Node;
上面的定义是有问题的，c编译器在编译的时候是从上往下找的，在Node *next这一行的时候编译器还不知道Node是谁，所以编译不通过，正确的声明应该是下面这样的：
typdef struct _NODE{
int data;
struct _NODE *next;
} Node;
可以看到，struct _NODE是在next之前就定义了，这个时候编译器就知道是要用哪个结构体了。下面我们来简单初始化一个链表：
Node a = {1, NULL};
Node b = {2, &a};
Node c = {3, &b};
上面我们初始化了一个长度为3的链表。当然，实际开发中，链表的长度远远不止3，可能是成千上万，我们不可能一条一条去初始化，这部分在后面的数据结构的链表会详细讨论。
不完全声明，如果有两个结构a和b它相互引用，那应该先声明谁呢？
struct a{
int a;
int b;
struct b sb;
};
struct b{
int a;
int b;
struct a sa;
}
上面的声明是非法的，前面我们说，编译器会从头到尾顺序找，当到struct b sb这一行的时候结构b并没有声明，所以编译不通过。我们可以使用不完全声明来解决这个问题，例如：
struct b; struct a{
int a;
int b;
struct b sb;
};
struct b{
int a;
int b;
struct a sa;
}
上面的struct b就是一个不完全声明。
1.1.6. 结构内存分配
编译器按照结构成员的顺序挨个分配内存，在存储成员时需要满足正确的边界对齐时，成员之间会出现用于填充的额外空间。来看下面的结构：
struct ALIGN{
char a;
int b;
char c;
};
如果某个机器的整形值长度为4个字节，且它的起始位置必须能被4整除，在内存中的结构如下：
系统禁止编译器在结构起始位置跳过几个字节来满足边界对齐的要求，因此所有结构的起始存储位置必须是结构中边界要求最严格的数据类型要求的位置。所以，a必须存储在一个能被4整除的地址。b是一个整形，所以a必须跳过3个字节到达合适的边界才能存储。在整型值之后是最后一字符c。
如果声明了相同类型的第2个变量，它的起始位置也必须满足能被4整除这个边界，所以它也必须路过3个字节来满足边界。这个结构体实际上只使用了6个字节，但最终却使用了12个字节，在空间利用率上是不划算的。
可以对结构稍作一下调整：
struct ALIGN{
int b;
char a;
char c;
};
成员b占用4个字节，a和c共占2个字节，由于需要边界对齐，c后面还要往后移2个字符凑齐4个字节，这样这个结构就只占用了8个字节，比上面的方式减少了4个字节。这在有大量结构体的程序中是很可观的。
1.1.7. 结构作为函数参数
在c语言中结构变量和其它变量一样，也可以作为函数的参数。但直接用结构变量当作参数在大多数情况下是不合适的。例如：
typedef _PARMAP{
int a;
char name[20];
float b;
} param;
void fn(param pa){}
param p = {10, "张三", 22.22}；
fn(p);
上面函数参数pa实际上每次调用传的都是一结构p的一个完整拷贝，我们知道，函数在调用被调用的时候都会把参数值压入到栈空间中的，如果结构体很大的话，性能是很差的。
通常推荐的做法是使用结构体指针，例如：
void fn(param *pa){}
param p = {10, "张三", 22.22};
fn(&p);
这样，我们每次传入的参数是一个固定大小的指针变量。一般情况下没有理由使用结构变量作为参数，除非结构大小和指针大小相当的情况下有一些意义。否则都要使用结构指针作为函数参数。
1.1.8. 位段
位段解决的问题其实就是合理利用空间。例如在32位机器上我们只需要1字节或者3字节这类奇数空间，如果我们使用int或者unsigned int这类声明，那么不管我们用不用都会占用4字节空间。
位段的声明和结构声明类型，只是中间使用”:“分隔，例如：
struct CHAR {
unsigned ch : 7;
unsigned font : 6;
unsigned size : 19;
}; struct CHAR ch1;
这是一个文本格式化程序，可以处理128个不同字符（7位），64种不同字体（6位）,以及0到524287个单位的长度。位段能利用ch和font剩余的位来增加size的位数，这样就避免了声明一个32位整数来存储size位段。
使用位段还可以很方便的访问一个整形值的部分内容。来看一个操作软盘与磁盘控制器通信的代码。这些设备控制器常常包含了几个寄存器，每个寄存器又包含了许多包装在一个整形值内的不同值。假定磁盘控制器其中一个寄存器定义如下：
图1-1
前5个位段每个都占1位，在一个从右向左分配位段的机器上，下面这个声明可以对这个寄存器的不同位段进行访问。
struct DISK_REGISTER_FORMAT {
unsigned command : 5;
unsigned sector : 5;
unsigned track : 9;
unsigned error_code : 1;
unsigned head_loaded : 1;
unsigned write_protect : 1;
unsigned disk_spinning : 1;
unsigned error_occurred: 1;
unsigned ready : 1;
};
#define DISK_REGISTER \
((struct DISK_REGISTER_PFORMAT *)0xc0200142)
// 告诉控制器从哪个扇区哪个磁道开始读取
DISK_REGISTER->sector = new_sector;
DISK_REGISTER->track = new_track;
DISK_REGISTER->command = READ;
// 等待，直到操作完成（ready变量变成真）
while(! DISK_REGISTER->ready) {}
// 检查错误
if (DISK_REGISTER->error_occurred) {
switch(DISK_REGISTER->error_code) { .... }
}
要注意的是：
如果使用int声明，在不同的操作系统是被当作有符号还是无符号是不确定的。
如果声明了64位，但机器只有16位或者32位可能无法运行。
位段中的成员在不同操作系统中是从左到右还是从右到左分配是有区别的。
以上例子均参考了《C和指针》里的第10章，例子足够经典，更容易帮助理解。在这里也推荐一下这本书，不要被这本书的名字误导了，虽然叫c和指针，但里面其实讲到了c的方方页面，一共400多页，个人觉得只要把这本书啃完了，应该可以说就掌握了c的精髓。
1.3. 结构再探
下面来深度拆解一个实例，通过画图的方式深入理解结构声明、初始化、访问等操作。
typedef struct _USER {
int age;
char *name;
} USER;
typedef struct _GROUP {
char* group_name;
int qutar[4];
USER admin;
struct _GROUP *child;
} GROUP;
上面可以用图表示如下：
图1-2
访问结构指针
GROUP g = {"技术中心",{1,2},{12,"小芳"}, NULL};
GROUP child = &g;
图1-3
访问变量
int admin_age;
admin_age = g.admin.age;
图1-4
访问结构指针
GROUP child_g = {"测试",{2,3}, {23,"小张"}, NULL};
g.child = &child_g;
child_g.child->group_name;
图1-5
2. 联合
至于联合解决了什么问题，这里不做深入探讨。
2.1. 联合的声明
联合的声明和结构差不多，例如：
union {
int a;
float b;
} fi;
或者也可以使用typedef
typedef union {
int a;
float b;
} fi;
联合的成员和结构一样，可以是任务类型，也可以是结构、联合、枚举。
2.2. 联合的初始化
联合的初始化在不同的标准下有一些差别，在c89标准和c++下：
fi u_fi = {10};
上面表示将10赋值给第一个成员a，在c89标准以和c++只有这一种初始化方式。
c99标准支持指定初始化，例如：
fi u_fi = {.a=100,.b=12.0}
最后一种方法是使用"."操作符，例如：
int a1;
fi u_fi;
a1 = fi.a;
2.3. 联合的访问
联合的访问通样可以通过"."操作符来操作，例如：
fi u_fi;
fi.a = 100;
fi.b = 122.33;
3. 枚举
3.1. 枚举的声明及初始化
枚举使用符号来初始化，例如：
enum colors {RED, BLUE, GREEN};
同样，枚举也可以使用typedef来设置别名，例如：
typedef enum colors{ RED, BLUE, GREEN } c;
注意：枚举元素符号需在作用域内全局唯一
3.2. 枚举的使用
枚举只能访问已存在的符号，例如：
enum colors c = RED;
上面声明了一个枚举c，并给它赋值为RED
