C 结构
设计一个程序时，最重要的步骤之一是选择表示数据的方法；C 语言的基本数据类型 甚至是 数组 array 在许多情况都不够用。C 语言提供了派生类型 结构变量（structure variables）:它创造新的形势，提高我们表示数据的能力。
1、结构变量
例子，我们想要表示一部电影的各种信息：如名片、发行年份、导演、主演、片长、影片的种类、评级等。这时，简单变量甚至是数组都无法表示这个数据形式，我们可以使用结构：
#define TSIZE 45//存储名片的数组大小
struct film {
char title[TSIZE];//电影的片名
int rating;//电影的评分
};
上述代码声明的结构有 2 部分：每个部分称为成员；使用结构需要掌握：
- 为结构建立一个格式或样式
- 声明一个适合该样式的变量
- 访问结构变量的各个部分
1.1、声明结构
结构声明：描述了一个结构的组织布局。
下述声明描述了一个由字符数组和 int 类型变量组成的结构：
#define TSIZE 45//存储名片的数组大小
struct film {
char title[TSIZE];//电影的片名
int rating;//电影的评分
};
该声明并未创建实际的数据结构，仅仅是描述了该结构由什么组成：
- 关键字
struct：它表明跟在其后的是一个结构； - 可选标记
film：使用该标记引用该结构；如struct film piggod; - 结构成员使用自己的声明来描述：如电影名称
title是一个内含TSIZE个元素的char类型数组； - 结构成员可以是任意一种 C 的数据类型，甚至可以是其它结构
- 结构体右花括号后的分号表明结构布局定义结束。
可以把这个声明置于所有函数外部，在该声明之后的所有函数都可以使用它；也可以将它放在一个函数内部定义，它的标记只限于该函数内部使用
#define TSIZE 45//存储名片的数组大小
//函数外部声明一个结构
struct film {
char title[TSIZE];//电影的片名
int rating;//电影的评分
};
1.2、定义结构
结构有两层含义：
- 结构布局：告诉编译器如何表示数据，但是编译器并没有为数据分配内存空间。
- 创建一个结构变量；
void filmMain(void)
{
/* 编译器执行该行代码，创建了一个结构变量piggod，
* 该变量的结构布局是 film；
* 编译器使用 film 模板为该变量分配内存空间：一个内含 TSIZE 个元素的 char 数组和一个 int 型的变量
* 这些结构成员的存储空间与变量 piggod 结合在一起
*/
struct film piggod;
}
在结构变量的声明中，struct film所起的作用相当于一般声明中的 int 或 float。我们可以声明一个指向结构的指针：
struct film piggod ,dogs , * clapton;
1.2.1、声明与定义结构
如果该结构模板 film 不打算多次使用，我们可以将声明结构和定义结构的过程组合为一个步骤
struct {
char title[TSIZE];//电影的片名
int rating;//电影的评分
} piggod;
上述声明没有使用结构标记（结构标记是可选的），在定义结构时，并未初始化结构变量
1.2.2、初始化结构
与初始化数组类似，我们以类似的语法初始化结构：
struct film piggod = {
"变形金刚",
8
};
使用一对花括号中括起来的初始化列表进行初始化，各初始化项用逗号分隔。
注意：如果初始化是一个静态存储期的结构，初始化列表的值必须是常量。如果是自动存储期，初始化列表的值可以不是常量。
1.2.3、访问结构成员
数组可以使用下标访问数组中的各个元素，那么如何访问结构中的成员呢？
a、点访问 (结构成员运算符)
我们可以通过结构成员运算符访问结构成员： piggod.title
b、-> 访问 (间接成员运算符)
后文再讲。
1.2.4、结构的初始化器
结构的指定初始化器使用点运算符和成员名标识特定的元素：
struct film cats = {
.rating = 9
};
可以按照任意顺序指定初始化器：
struct film cats = {
.rating = 9,
.title = "猫"
};
与数组类似，在指定初始化器后面的普通初始化器，为指定成员后面的成员提供初始值。另外，对特定成员的最后一次赋值才是它实际获得的值。
1.3、结构的复合字面量
C99 的复合字面量特性可用于数组和结构：当需要一个临时结构值时，我们可以选择使用复合字面量。
语法：类型名放在圆括号中，后面紧跟一个用花括号括起来的初始化列表
//使用复合字面量为一个结构变量提供两个可替换的值
(struct film){"dogs",8};
还可以把结构字面量作为函数的参数传递：字面量在所有函数外部，则具有静态存储期；在块中，则具有自动存储期。
1.4、嵌套结构
有时，需要在一个结构中包含另一个结构，即嵌套结构。如统计一个人的爱好：可能有电影、音乐等：
struct music {
char title[TSIZE];//音乐名字
char singer[TSIZE];//歌手
};
//爱好 hobby中嵌套另外的结构
struct hobby{
struct film movie;
struct music song;
};
和一般声明类似，在结构声明中创建嵌套结构如下：
struct hobby myHobby = {
{
"变形金刚",
8
},
{
"大象",
"花伦"
}
};
访问嵌套结构中的成员，需要多次使用点运算符
/* 点运算符从左往右运算
* 先找到 myHobby，然后找到 myHobby 的 movie 成员；
* 再找到 movie 的 title 成员 (myHobby.movie).title
*/
myHobby.movie.title;
myHobby.song.singer;
注意：结构不能嵌套与本身类型相同的结构，但是可以含有指向同类型结构的指针。
1.5、匿名结构
匿名结构是一个没有名称的结构成员：
struct hobby{
struct film movie;
struct {//匿名结构
char muTitle[TSIZE];//音乐名字
char singer[TSIZE];//歌手
};
};
上述结构 hobby 是一个嵌套结构，通过点运算符访问其成员：
struct hobby myHobby = {{"变形金刚",8},{"大象","花伦"}};
myHobby.movie.title;
myHobby.muTitle;
在访问匿名结构中的成员时，将 muTitle看做hobby成员直接使用它。
1.6、结构指针
为何要使用指向结构的指针？
- 类似于指向数组的指针比数组本身更容易操控（排序问题），指向结构的指针通常比结构本身更容易操控；
- 在早期的 C 实现中，结构不能作为参数传递给函数；可以传递结构指针；
- 相对于传递一个结构，传递指针显然效率更高；
- 某些用于表示数据的结构中包含指向其它结构的指针
1.6.1、声明与初始化结构指针
声明结构指针与其它指针声明一样：
struct film *sky;
以上声明并没创建一个新的结构，但是指针 sky 可以指向任意现有的 film 类型的结构；
sky = &piggod;
注意：与数组不同的是，结构变量名并不是结构的地址；获取结构变量地址需要在结构变量名前加 & 运算符
1.6.2、用结构指针访问成员
我们可以使用间接成员运算符 -> 访问结构成员：
sky -> title;
sky -> rating;
此处不能写成 sky.title ，因为 sky 不是结构;
1.7、向函数传递结构
函数的参数把值传递给函数，ANSI C 允许把结构作为参数使用；我们可以选择传递结构本身，或者传递指向结构的指针，甚至只传递结构的某一成员。
1.7.1、传递结构成员
只要结构成员是一个具有单个值的数据类型（int 、char、float），便可以把它作为参数传递给接受该特定类型的函数。
int sum(int a ,int b){
return a + b;
}
如上述sum()函数，既不知道也不关心实参是否是结构成员，它只要求传入int类型；
如果需要在被调函数中修改主调函数中结构成员的信息，需要传递成员的地址：
char * resertTitle(char * title)
{
title = NULL;
return title;
}
1.7.2、传递结构地址
void showMovie(const struct film * movie)
{
printf("电影 : %s 评分 : %d",movie ->title,movie->rating);
}
由于该函数不需要改变结构成员，所以使用一个指向const的指针。
1.7.3、传递结构
我们还是使用上述函数来展示：
void showMovie(struct film movie)
{
printf("电影 : %s 评分 : %d",movie.title,movie.rating);
}
我们知道，在程序调用 showMovie() 函数时，编译器根据该函数实参创建了一个名为 movie 的自动结构变量，为实参的副本，存储在栈区。
也就是说，即使我们在该函数中修改movie 的成员信息，也是修改的副本信息，而非主调函数中结构成员的信息。
同时，如果结构占用内存过大，传递结构也对内存开销是一种浪费。
1.7.4、结构与结构指针的选择
如果我们需要编写一个处理结构的函数，那么传递结构作为参数，还是传递结构指针呢？这两者皆有优缺点：
| 优点 | 缺点 | |
|---|---|---|
| 传递结构指针 | 执行效率高 | 无法保护数据（被调函数的某些操作可能影响原来结构中的数据），可以使用const限定符解决 |
| 传递结构 | 函数处理的是原始数据的副本，保护了原始数据；代码风格清晰 | 传递结构浪费时间和存储空间；对于大型数据结构，为了使用某几个成员信息而传递整个结构是一种极大的性能浪费 |
为了效率，我们一般使用结构指针作为函数参数，如果不需要修改原始数据，使用const限定符防止数据被以外篡改。
1.8、结构中的字符数组和字符指针
在前面的 struct film，笔者使用字符数组来存储字符串，字符串存储在结构内部。当然，也可以使用指向 char 的指针来代替字符数组，此时结构内存只存储该字符串的指针：
struct film {
char title[TSIZE];//字符串存储在结构内存
char *director;//结构内存只存储字符串指针
int rating;
};
我们来看以下语句：
scanf("%s",piggod.director);
scanf() 函数将输入的字符串放入piggod.director地址上。如果piggod.director未初始化，则该字符串地址可能是任意值，因此程序执行该语句时可能把输入的字符串放在任意位置，这一操作可能导致程序崩溃。
使用结构存储字符串，字符串数组作为成员比较简单；而指向 char 的指针可能会犯错，导致严重问题。
1.9、结构、指针、malloc()
使用 malloc() 函数为结构变量分配内存并使用指针存储该地址，可以为字符串分配合适的存储空间
2、结构与数组
| 结构 | 数组 | |
|---|---|---|
| 赋值 | C 允许把一个结构赋值给另一个结构 | 不能把一个数组赋值给另一个数组 |
| 变量名 | 结构变量名并不是结构的地址 | 数组名是数组首元素的地址 |
struct film piggod = {
"变形金刚",
8
};
/* 该语句将 piggod 的每个成员赋值给 cat 的相应成员
* 即使成员是数组，如title，也能完成赋值
*/
struct film cat = piggod;
假如我们要收集多部电影的信息，我们可以使用数组来存储这多个电影结构。
2.1、声明结构数组
声明结构数组与声明其它类型的数组类似：
//数组 filmList 中每个元素都是 struct film 类型的结构变量
struct film filmList[100];
2.2、标识结构数组的成员
为了标识结构数组的成员，可以采用访问单独结构的规则：在结构名后面加一个点运算符，再在点运算符后面写上成员名。
filmList[0];//访问第 1 个位置的结构变量
filmList[1].rating;//访问第 2 个位置的结构变量的 rating 成员
filmList[3].title;//访问第 4 个位置的结构变量的 title 成员
filmList[5].title[7];//访问第 6 个位置的结构变量的 title 字符串的第 8个字符
2.3、函数中使用结构数组传参
我们需要计算结构数组中所有电影的平均评分，将结构数组作为实参换地给以下函数：
float average(const struct film movies[],int count)
{
int total = 0;
for (int i = 0; i < count; i ++)
total = total + movies[i].rating;
return (float)total / (float)count;
}
数组名movies是该数组的地址，movies[0]是数组中第1个结构变量，通过点运算符访问结构成员。
3、链式结构
学习计算机语言和学习音乐一样：首先学会使用工具，学习如何演奏音阶、如何使用锤子等；然后解决各种问题；接着，对于更高层次，工具是次要的，需要设计和创建一个项目。
我们已经学习了 C 语言的基本数据类型int、float等以及派生类型 数组、指针、结构等，我们可以使用这些基础类型与派生型解决一些常见的问题。
然而，对于复杂的问题，这些数据类型显然并不能完全处理我们遇到的问题。
针对上文的struct film，需要统计一个人一年看过的电影。我们如何存储这些数据呢？使用结构数组？或者使用malloc()动态分配内存？还是其他的形式？
是否需要按字母排序？是否需要按评分排序？如何快速查找到一部电影？
3.1、使用结构数组
我们不妨使用一个数组存储一年看过的电影，每部电影使用结构表示：
#define TSIZE 45 //存储名片的数组大小
#define FMAX 5 //影片的最大数量
struct film {
char title[TSIZE];//电影的片名
int rating;//电影的评分
};
char * s_gets(char str[], int lim);
void filmMain1(void)
{
struct film movies[FMAX];//创建一个结构数组
int i = 0;//当前输入电影位置
/* 将用户输入的数据存储在数组中
* 数组已满(FMAX)、达到文件末尾(NULL)、或者按下Enter键('\0')；输入终止
*/
puts("输入第一部电影标题:");
while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL &&
movies[i].title[0] != '\0')
{
puts("输入你的评价等级 <0-10>:");
scanf("%d", &movies[i++].rating);
while(getchar() != '\n')
continue;
puts("输入下一个电影标题 (遇到空行停止):");
}
if (i == 0)
printf("没有数据输入. ");
else
printf ("以下是电影列表:\n");
for (int j = 0; j < i; j++)
printf("电影: %s 评价: %d\n", movies[j].title,movies[j].rating);
printf("结束!\n");
}
char * s_gets(char * st, int n)
{
char * ret_val;
char * find;
ret_val = fgets(st, n, stdin);
if (ret_val)
{
find = strchr(st, '\n'); // 查找换行符
if (find) // 如果地址不是 NULL,
*find = '\0'; //在此处放置一个空字符
else
while (getchar() != '\n')
continue; // 处理剩余输入行
}
return ret_val;
}
上述程序创建了一个结构数组，然后将输入的数据存储在数组中。
我们可以明显感觉到该程序的缺陷：首先，该程序浪费存储空间；大部分电影名不会超过 40 个字母，但是有些电影名超过 40 个字母；其次，只记录 5 部电影，限制太严格；限制小了无法满足用户需求，限制大了浪费内存。
总的来说，该程序的最大问题，就是 数据表示死板、不太灵活。可以在编译时确定所需内存量，使用malloc()函数分配需要的内存，这或许会灵活些。
3.2、链表
我们的需求是可以不确定的添加数据，而不是指定输入多少项、指定程序分配多大的空间。我们有两种方式使用malloc()函数分配内存：
- 一次性分配足够的内存，前面已经尝试过，太死板不灵活；
- 每次存储电影时使用
malloc()分配一个内存，这时我们需要知道每个电影struct film的内存地址。
我们可以重新定义结构struct film，每个结构中包含指向 next的结构指针，当创建结构时，将该结构的地址存储在上一个结构中。
struct film {
char title[TSIZE];
int rating;
struct film * next;
};
结构不能嵌套与本身类型相同的结构，但是可以含有指向同类型结构的指针。这是定义链表的基础，链表中每一项都包含着指向下一项的信息。
3.2.1、链表定义
链表是一个能存储一系列项且可以对其进行所需操作的数据对象。
链表具有哪些属性？首先，链表应该能存储一系列的项；其次，链表类型应该提供一些操作。一般的链表包含以下操作：
- 初始化一个空链表；
- 在链表末尾添加一个新项；
- 确定链表是否为空；
- 确定链表是否为已满；
- 确定链表中的项数；
- 访问链表中的每一项执行某些操作，如显示该项；
- 在链表的任意位置插入一个项；
- 移除链表中的一个项；
- 在链表中检索一个项（不改变链表）；
- 用另一个项替换链表中的一个项；
- 在链表中搜索一个项
链表类型.png
3.2.2、使用链表
我们已经简单了解链表，现在使用链表解决问题：由于代码过多，请点击查看 Demo
3.3、队列
队列是具有两个属性的链表：
- 第一，新项只能添加到链表的末尾；
- 第二，只能从链表的开头移除项。
队列是一种先进先出(FIFO)的数据形式。
