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)的数据形式。