【9.0】C-结构体与共用体
前言
C语言的数据类型分为基本数据类型和构造数据类型，之前的int,float等数据类型都是基本数据类型，都是C语言事先定义好的数据类型，编程时直接使用即可。C语言还允许用户自定义数据类型，称为构造数据类型，例如：数组，以及下面的结构体和共用体。
结构体
结构体(structure)是由不同数据类型的数据所组成的集合体，是构造数据类型，其特点是可以由不同的数据类型构成。
每一个结构体有一个名字，称为结构体名。一个结构体由若干成员组成，每个成员都有自己的名字，称为结构体成员名。结构体成员是组成结构体的要素，每个成员的数据类型可以不同。
简单来描述结构体来说如下表：
| 学号 | 姓名 | 性别 | 成绩 |
|---|---|---|---|
| xxx | xxx | xxx | xxx |
对于一个结构体来说就是头行，我们现在定义他的名称为：学生信息，那么组成学生信息的成员就是：学号，姓名，性别，成绩。这几个元素就是学生信息结构体的成员/元素。对于各种元素他们的类型是可以不同的。
结构体类型的定义
语法格式如下：
1 | struct 结构体名 |
struct是结构体类型标识符，是关键词。结构体名由标识符组成，称为结构体类型名，由用户指定。大括号{}中的结构体成员表，称为结构体。
【实例】对于上面的举例表格的结构体实现如下：
【代码示例】
1 | struct studentInfo //结构体名studentInfo |
【说明】
如上定义的studentInfo是一种自定义的新数据类型，系统不会对它分配实际的存储空间，只是一种自定义数据模板。
声明结构体需要注意以下几点：
结构体声明描述了结构体的组织形式，在程序编译时并不为它分配存储空间。只是规定了一种特定的数据结构类型以及它所占用的存储空间。
结构体成员可以是任意类型。所以，结构体可以嵌套使用，即一个结构体可以称为另一个结构体的成员，代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14struct studentInfo //学生信息结构体
{
int Num; //学号
char name; //姓名
int sex; //性别
float score; //分数
struct data birthday; //出生日期
};
struct data
{
int year; //年份
int mouth; //月份
int day; //日份
};结构体声明可以在任意位置，如果声明在自定义函数内，则只可以在自定义函数内调用，如果声明在自定义函数外，则可以在从声明点到最后范围内调用。一般情况下，是在源文件的开头对结构体进行声明。
结构体成员名可以与程序中其他变量同名，系统会自动识别它们，两种不会混淆。
结构体变量的定义
结构体变量定义一般采用下面三种形式：
先声明结构体类型再定义变量，其定义形式：
1
2
3
4
5
6
7
8struct studentInfo //结构体声明
{
int Num;
char name;
int sex;
float score;
};
struct studentInfo test; //结构体定义在定义了结构体变量后，系统会为结构体变量分配存储空间。
若程序规模比较大，可将对结构体类型的声明集中放到一共文件中（以
.h为后缀的头文件）。若其他源文件需要用到此结构体类型，则可以用#include命令将该头文件包含到本文件中，便于修改和使用。在声明结构体类型同时定义结构体变量，其定义形式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//语法结构
struct 结构体名
{
数据类型 成员1的名字;
数据类型 成员2的名字;
数据类型 成员3的名字;
···
}结构体变量名表;
//代码示例
struct studentInfo //结构体声明
{
int Num;
char name;
int sex;
float score;
}a,b,c; //定义三个studentInfo类型的结构体变量直接定义结构体变量，不出现结构体名，其定义形式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//语法结构
struct //注意：此处结构体名没了
{
数据类型 成员1的名字;
数据类型 成员2的名字;
数据类型 成员3的名字;
···
}结构体变量名表;
//代码示例
struct //结构体声明
{
int Num;
char name;
int sex;
float score;
}a,b,c;
结构体变量定义需要注意：
- 结构体数据类型的定义描述了结构体的类型的模式，不分配存储空间；而结构体变量定义则是在编译时为结构体变量分配存储空间。
- 结构体变量中的成员可以单独使用，其作用和地位与一般变量一致
- **结构体变量占用存储空间的大小是各成员所需内存量的总和，在程序中可以用
sizeof()函数来实现，即sizeof(结构体名)**。需要注意的是：有时与sizeof()函数计算出来的值不是完全一样的，这个实际的内存量，不仅与所定义的结构体类型有关，还与计算机系统以及编译系统有关。通常系统为结构体变量分配内存大小，会大于或等于所有成员所占用内存字节数的总和。
用typedef定义数据类型
关键字typedef用于为系统固有的或者自定义数据类型定义一个别名。数据类型的别名通常使用大写字母，这不是强制性的，只是为了与已有数据类型区分。例如：
1 |
|
输出：2
同样的也可以使用typedef来定义结构体数据类型，代码示例：
1 |
|
结构体变量的引用
在定义结构体变量后，如果需要引用结构体变量，需要注意的是不可以将结构体整体作为输入和输出，只能对具体成员进行输入输出，例如：
1 | //这是错误的,S是结构体变量 |
也就是说，访问结构体成员变量的语法格式如下：
1 | //通用格式 |
结构体变量不能进行整体输入和输出，当时允许相同结构体类型的结构体变量赋值，例如：
S1=S2。
结构体变量的初始化
可以在定义结构体变量的同时初始化，语法格式如下：
1 | //语法格式 |
需要注意的是：
- 初始化数据与数据之间用逗号隔开
- 初始化数据的数量要和结构体成员对应且相等
- 初始化数据对应的数据类型一致
结构体变量初始化代码示例：
1 | //方法一 |
结构体数组
一个结构体变量中可以存放一组数据，即excel表中“一行”数据。如果数据有很多行，即对应很多个对象，这时就可以使用结构体数组来表示。结构体数组的元素是一个结构体类型的变量。
结构体数组的定义
结构体数组必须先定义，后引用。代码格式：
1 | //方法一 |
结构体数组的初始化
结构体数组也可以在初始化的同时进行初始化，代码示例：
1 | struct StudnentInfo stfinfo[10]={{1,"test",0},{1,"test1",0},{1,"test2",0}}; |
上述示例代码是对结构图数组前三个元素进行初始化。
结构体数组的引用
【实例】求下表成绩平均值
| 姓名 | 性别 | 成绩 |
|---|---|---|
| 张三 | 1 | 98 |
| 李四 | 1 | 80 |
| 小明 | 0 | 68 |
【代码示例】
1 |
|
【输出结果】
结构体指针变量
结构体指针变量是指向结构体变量的指针，该指针变量的值是结构体变量的起始地址。
指向结构体变量的指针
代码示例：
1 |
|
同样的可以在声明就初始化：
1 | struct StudentInfo *p=&a; |
C语言规定了两种用于访问结构体成员的运算符，一种是成员运算符，也就是.；另一种是指向运算符，也称为箭头运算符，其语法格式如下：
1 | //语法格式 |
指向结构体数组的指针
定义一个结构体数组S s[30]，若要定义结构体指针变量p.将其指向结构体数组，方法如下：
1 | //方法一 |
它们都是获取了结构体数组s的首地址，如下图，可以通过改变指针的指向位置来实现不同元素的访问。
例如：使用p->sC引用的是s[0].sC的值，同样的使用(p+1)->sC引用的是s[1].sC的值。
结构体变量和结构体指针变量作为函数参数
与其他普通的数据类型一样，既可以定义结构体类型的变量，数组，指针，也可以将结构体类型作为函数参数的类型和返回值的类型。将一个构造体变量的值传递给另一个函数，有如下三种方法：
用结构体的单个成员作为函数参数，向一个结构体传递结构体的单个成员
用单个结构体成员作为函数实参，与其他普通数据类型的变量作函数实参完全一样，都是值传递调用，在函数内部对其进行操作，不会引起结构体成员值的变化。
用结构体变量作为函数参数，向函数传递结构体的完整结构
用结构体变量作为函数实参，向函数传递是结构体的完整结构，即将整个结构体成员的内容复制给被调函数。在函数内可用成员运算符引用其结构体成员。因为这种传递方式也是值传递调用，所以，在函数内对形参结构体成员值的修改不会影响相应实参结构体成员的值
用结构体指针或者结构体数组作为函数参数，向函数传递结构体的地址。
用指向结构体的指针变量或结构体数组作为函数实参的实质是向函数传递结构体的地址，因为是地址调用，所以在函数内部对形参的成员值的修改会影响到实参结构体成员的值。
【实例】如下学生成绩信息表
| 学号 | 高数成绩 | 英语成绩 |
|---|---|---|
| 101 | 87 | 80 |
| 102 | 59 | 69 |
| 103 | 97 | 83 |
要求在主函数中输入学生信息，编写一个自定义函数，将高数成绩为59分的同学成绩改为60，然后将修改后的学生信息在主函数中输出。
【代码示例】
1 |
|
【输出】
链表
这是一种常见的线性数据结构，它是动态进行内存分配的一种结构，链表根据需要开辟存储空间。
在没学习链表之前，如果存储数量较多同类型数据时，通常会使用数组。比如要存储一个班级相关成绩的信息。例如：
1 | int score[40]; |
在使用数组的时候，总有一个问题困扰我们：数组应该有多大？
在大多数情况下，我们并不能确定要使用多大的数组，所以一般情况下，我们将数组定义的足够大。这样，程序在运行时就申请了固定大小的足够大的存储空间。即使知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，又必须重新修改程序，扩大和缩小数组的存储空间。这种分配固定大小的内存分配方法称为静态内存分配。这种内存分配方法存在比较严重的缺陷：在大多数情况下会浪费大量的内存空间，在少数情况下，当定义数组不够大时，还可能出现下标越界错误，甚至导致严重后果。
这时候动态分配内存的链表就可以解决如上问题：
动态内存分配是指在程序执行过程中根据需要动态地分配或者回收存储空间的内存分配方法。动态内存分配不像数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序需求临时分配，且分配的大小就是程序要求的大小。
链表数据集合中的每个数据存储在称为结点的结构体中，一个结点通过该结点中存储的另一个结点的存储地址（指针）来访问另一个结点，如果按照这种方法把所有结点依次串联起来，称为链表。
链表是由结点组成的数据集合，而结点存储空间的建立与撤销是采用动态内存分配与撤销函数在程序运行时完成的。因此，链表是一种动态数据结构。
链表的类型及定义
链表是用一组任意的存储单元存储线性表元素的一种数据结构。
链表又分为单链表，双向链表和循环链表等。
链表一般采用图形方式直观描述结点之间的连接关系。这种描述链表逻辑关系的结构图形称为链表图。
单链表
单链表是最简单的一种链表，其数据元素是单项排列的，如下图
从上图可以看出，单链表有一个“头指针”变量，图中用
h表示，它存放一个地址，该地址指向单链表中的第一个元素。单链表中每个元素称为结点，每个结点都包括两部分：一部分数据域——存放用户要用的实际数据；另一部分是指针域——存放下一个结点的地址，用指针变量表示。单链表中最后一个结点的指针域位空（NULL），表面单链表到此结束。空链表表示单链表中没有结点信息，它用一个值NULL的指针变量表示。
单链表中各元素在内存中可以不是连续存放的。要查找某一元素，必须先找到上一个元素，根据它的指针域找到下一个元素的存储地址。如果不提供头指针，则整个链表都无法访问。
单链表的数据结构可以用结构体来实现，一个结构体变量可以包含若干成员，这些成员可以是数值类型，字符类型，数组类型，也可以是指针类型。利用指针类型成员存放下一个结点的指针。例如：
1
2
3
4
5struct node
{
int data; //数据域
struct node *next; //指针域
};上述代码实现了一个数据域为
int类型变量的结点类型，成员变量next是一个指针变量，一般称为后继指针，该指针所指向的数据类型是该结构体类型。或者可以利用
typedef给这个自定义的数据类型起个名字：1
typedef struct node Node;
一个单链表就是由内存中若干个
Node类型的结构体变量构成的。在实际应用时，单链表的数据域不限于单个的整型，实型或者字符型，它可能由若干个成员变量组成。在单链表中，知道指向某个结点的指针，很容易得到该结点的后继结点的位置，但是要得到该结点的直接去前驱结点位置，则须从头指针出发进行搜索。循环单链表
循环链表如下图，它的特点是最后一个结点的指针域存放着第一个结点的存储地址，这样一来，链表中所有的结点构成一个环，从每个结点都能搜索到其直接前驱和直接后继结点。
循环单链表的优点是从任何一个结点出发，都能到达其他任何结点。
双向链表
如果为每个结点增加一个指向直接前驱结点的指针域，就可以构成双向链表 。双向链表可以沿着求前驱和求后继两个方向搜索结点。
双向链表的结点数据结构实现如下：
1
2
3
4
5
6struct node
{
int data;
struct node *next; //后继结点
struct node *previous; //前驱结点
};
处理动态链表的函数
链表结构是动态分配存储空间的，即在需要时才开辟一个结点的存储空间。动态分配和释放存储空间需要用到以下几个库函数：
malloc()函数。函数原型为：1
void * malloc(unsigned int size);
其作用是在内存的动态存储区中分配一个长度为
size的连续空间。其参数是一个无符号整型数，返回值是一个指向所分配的连续存储区域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。malloc全称：memory allocation（内存分配）calloc()函数。函数原型为：1
void * calloc(unsigned int n,unsigned int size);
其作用是在内存的动态区存储中分配
n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功（如内存空间不足），返回NULL。用
calloc()函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为size。calloc全称：clear allocation（内存清空）free()函数。由于内存区域是有限的，不能无限制的分配下去，而且一个程序要尽量节省资源，所以当所分配的内存区域不在需要时，就要释放它，以便其他的变量或者程序使用。这时要用到
free()函数。函数原型为：1
void free(void *p);
其作用是释放由
p指向的内存区，这部分内存区能被其他变量使用。p是调用calloc()或者malloc()函数返回的指针值，free()函数无返回值。
动态链表的基本操作
单链表的建立（含头结点的尾插法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct node //结点的结构体
{
int data;
struct node *next;
}NODE;
//自定义创建单链表函数
NODE * createList(int n){
NODE *head; //单链表的头指针
NODE *p; //指向当前要插入列表的结点
NODE *r; //指向单链表最后一个结点
int i = 0;
//为头结点申请存储空间并检测是否分配成功
if ((head=malloc(sizeof(NODE)))==NULL)
{
printf("error");
return 0;
}
head->next = NULL; //头结点的指针域设置为空
r = head; //将r的指针指向head的地址
for (i = 0; i < n; i++)
{
//p结点总指向当前处理结点
if ((p=malloc(sizeof(NODE)))==NULL) //创建新结点
{
printf("error");
return 0;
}
scanf("%d", &p->data); //从键盘读入数据，存入当前结点的数据域
r->next = p; //将r的指针指向的指针域指向p,形成单链表
r = p; //再将r指向最新的尾结点
}
r->next = NULL; //将未结点赋NULL表示最后一个
return head; //返回头结点
}
//自定义遍历输出单链表元素数值的函数
void printList(NODE *L){
NODE *p;
p = L->next;
while (p!=NULL)
{
printf("%5d", p->data);
p = p->next;
}
printf("\n");
}
int main(){
NODE *h;
printf("请输入%d个整数，建立单链表\n", N);
h = createList(N);
printf("单链表内容如下：\n");
printList(h);
return 0;
}输出：
单链表的查找运算
对单链表进行查找的思路为：从单链表中第一个结点开始依次向后扫描，检测其数据域是否是所要查找的数值，如果是要查找的值着查找成功，反之则继续查找至单链表的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//自定义查找方法,传入单链表和要查找的值
int locate(NODE *L,int x){
NODE *p = L->next;
int i = 1; //记录位置
while (p!=NULL && p->data!=x) //判断是否为空链表以及值是否相同
{
p = p->next;
i++; //如果不符合，index+1
}
if (p=NULL) //如是空链表则直接返回0
{
return 0;
}else{
return i; //反之将记录位置返回
}
}单链表的插入操作
单链表的插入：假设在一个单链表中存在两个连续结点p,q(其中p为q的直接前驱)，若我们需要在p于q之间插入一个新结点s,那么需要先为s分配存储空间并完成数据域的赋值，然后让p的指针指向存储s的地址，将s的指针指向q的地址，这样就完成了插入操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//单链表插入操作
int insert(NODE *L,int x){
NODE *s, *p, *q;
if ((s=malloc(sizeof(NODE)))==NULL)
{
printf("error");
return 0;
}
s->data = x; //将要插入元素的值赋值给s
p = L->next; //p指向链表的第一个元素
while (p!=NULL) //如果p的指针不是空，则继续遍历单链表元素
{
q = p; //直到最后一个元素，则q是最后一个元素
p = p->next;
}
s->next = q->next; //将新插入的指针域获取原指针域指向
q->next = s; //将原来的指针域指向新指针域
}单链表的删除操作
删除结点只需要让前驱结点指向后继结点即可，如下示意图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//删除单链表元素
void deleteList(NODE *L,int x){
NODE *q, *p;
p = L;
q = L->next;
while (q!=NULL && q->data!=x)
{
p = q;
q = q->next;
}
if (q==NULL)
{
printf("链表中没有要删除的元素");
}else{
p->next = q->next;
free(q);
printf("删除一个元素后的单链表如下：\n");
printList(L);
}
}
栈和队列
栈，队列和链表都属于线性结构。线性结构的特点是，在数据元素的非空有限集中：
- 存在唯一的一个被称为“第一个”的数据元素
- 存在唯一的一个被称为“最后一个”的数据元素
- 除第一个之外，集合中的每个数据元素均只有一个前驱
- 除最后一个之外，集合中每个数据元素都只有一个后继
栈和队列都是操作受限制的特殊线性表。
栈是一种只允许在表头进行插入和删除的特殊线性表，其操作的原则是后进先出，故栈又称为后进先出表，称为LIFO（Last In First Out）表。
队列是删除操作只在表头进行，插入操作只在表尾进行的特殊线性表，其操作原则是先进先出，简称FIFO（First In First Out）。
共用体
共用体，有的也称为联合体（Union），是将不同类型的数据组织在一起共同占用同一段内存的一种构造数据类型。同样都是将不同类型的数据组织在一起，但与结构体不同的是，共用体是从同一起始地址开始存放成员的值，即让所有成员共享同一段存储空间。共用体与结构体的类型定义方法相似，只是关键字变为union。
1 | //语法格式 |
共用体数据类型和结构体数据类型都属于构造数据类型，都可以由程序员根据实际需要来定义，其不同之处在于，共用体的所有成员共同占用一段内存，共用体变量所占用内存空间大小取决于其他成员中占内存空间最多的那个成员变量；而结构体的每个成员各自占用一段内存，结构体变量所占用的内存空间大小取决于所有成员占用内存空间的大小总和。
【实例】查看共用体和结构体占用情况
【代码示例】
1 |
|
【输出】
利用
sizeof()函数测得的值一般会大于或者等于成员所需的内存量总和
枚举类型
枚举，即“一个一个列举”之意，当某些变量仅由有限个数据值组成时，通常使用枚举类型表示。枚举数据表示描述的是一组整型值的集合。声明枚举类型需要使用关键字enum。示例：
1 | //语法格式 |
枚举类型如果做不做的规定，默认从0开始对应到枚举元素上，代码示例：
1 |
|
输出：0
如果想要自定义的，可以使用如下：
1 |
|
输出：2
上述代码中
sun实际对应0，而mon规定是2，后面的tue则是3，wed是4…依次类推
