8.8 链表
8.8.1 链表概述
问题的提出：我们要设计存放一个班级的学生信息，可以采用数组的方法，要存放30个学生就设计长度为30的数组，要存放50个学生就设计长度为50的数组。假如我们事先并不知道学生人数，就必须将数组设计得足够大，例如，设计长度为100的数组，但实际学生数只有30，这样就会造成内存的浪费。显然用数组只适合于已知长度的数据，因此数组对内存的占用是静态的，程序运行过程中长度是不变的。
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构，可以动态的分配存储空间，需要多少就分配多少。
一种简单链表如图8.14所示：
图8.14
这个简单链表很像一队手拉着手地小朋友，有头，有尾，中间的小朋友手拉着手，我们可以从头依次查找到尾。
在C语言中怎样实现这种链表呢？，要回答这个问题我们再来看一看结构体类型的定义，我们知道结构体类型可以嵌套定义，什么叫嵌套定义呢？请看下面的例子。
struct date
{
int month;
int day;
int year;
};
struct student
{
int num;
char name[20];
char sex;
int age;
char addr[30];
struct date birthday; //嵌套定义
};
在结构体student中，定义了结构体类型的成员变量，这种定义叫结构体类型的嵌套定义，这种定义也遵循先定义后使用的原则。
按规定在一个结构体的定义中，其成员类型可以是除本身结构类型之外的任何已有类型。也可以是任何已有类型（包括本身类型在内）的指针类型。这就告诉我们结构体不能进行除指针类型数据成员的递归定义。
struct F
{
float data;
struct F maxdata; //递归定义
};
上述递归定义在C语言中是不允许的。但指针类型的递归定义又是允许的，如：
struct F
{
float data;
struct F *next;
};
这是因为用上述类型定义变量时是要开辟存贮空间的，开辟空间的大小由成员所占空间大小之和决定，如果是非指针的递归定义，结构体类型的成员并不知道自己所占空间的实际大小，因此就无法确定结构体变量所占空间的大小，所以这种定义是非法的。为什么结构体指针成员却可以递归定义呢？这是因为无论什么类型的指针变量所占的空间是确定的，都是2个字节，（16位的编译系统是2个字节，32位的编译系统是4 个字节）因此结构体变量所占空间的大小是可以确定的，所以这种定义是合法的。
让我们再回过头来看看这个简单链表：
链表有一个“头指针”变量，图中以head表示，它存放一个地址，请同学注意这个地址。该地址指向一个“结点”（在链表中将元素称为“结点”），每个结点包括两部分：一部分是用户需要用的实际数据（如A、B、C、D），另一部分为下一个结点的地址。可以看出，head指向第一个结点，第一个结点指向第二个结点，直到最后一个结点，最后一个结点不再指向其他结点，称它为“表尾”，它的地址部分为“NULL”（表示“空地址”），链表到此结束。同学想一想“空地址”指向什么地方？
可以看到，这种链表的数据结构，必须利用指针特性才能实现。即一个结点中应包含一个指针变量，用它存放下一结点的地址，如图8.15所示。
图8.15
结点中的数据域用来存放数据，地址域用来存放下一个结点的地址。
我们用结构体类型定义“结点”。
struct student
{
long num;
float score;
struct srudent *next;
};
数据域中的数据我们采用给成员变量赋值的办法来赋值：如
struct student stu;
stu.num=200401;
stu.score=89.5;等等。
指针域怎样赋值呢？指针域中的值是下一个结点的地址，请看图8.16。
图8.16
8.8.2 静态链表
例 8.6 建立一个如上图所示的简单链表，它由3个学生数据的结点组成，输出结点中的数据。
1 #define NULL 0
2 #include <stdio.h>
3 struct student
4 {
5 long num;
6 float score;
7 struct student *next;
8 };
9 void main()
10 {
11 struct student a,b,c,*head,*p;
12 a.num=200401;
13 a.score=89.5;
14 b.num=200402;
15 b.score=80;
16 c.num=200403;
17 c.score=78;
18 head=&a; /*建立链表*/
19 a.next=&b;
20 b.next=&c;
21 c.next=NULL;
22 p=head; /*打印链表中的数据*/
23 while(p!=NULL)
24 {
25 printf("%ld\t%5.1f\n",p->num,p->score);
26 p=p->next;
27 }
28 }
下面首先分析这个链表是如何形成的，请看图8.17
图8.17
其中：第18行 head=&a;将a的地址送给head,使head指向a，
第19行a.next=&b;将b的地址送给a的指针域，使a.next指向b，
第20行b.next=&c;将c的地址送给b的指针域，使b.next指向c，
第21行c.next=NULL;因为c结点没有后继结点，将NULL送给c的指针域，使c.next指向NULL。
这样就连成了一个以head为表头，有三个结点的链表。
再介绍链表打印是如何进行的，
由第22行 p=head; 将head送给p，使p也指向a结点，如图8.18所示。
图8.18
再执行第23行循环开始，首先判断p等不等于NULL，结论是不等于，执行第25行输出语句。接着执行第26行p=p->next;语句，请注意此时p->next是存放的是什么地址呢?显然是b的地址，结果使p指向了b结点 ,p指针发生了移动。如图8.19所示。
图8.19
再判断p等不等于NULL，结论是不等于，执行输出语句。接着执行p=p->next;语句，请注意此时p->next是存放的是什么地址呢?显然是c的地址，结果使p指向了c ,p指针又发生了移动。如图8.20所示。
图8.20
再判断p等不等于NULL，结论是不等于，执行输出语句。接着执行p=p->next;语句，请注意此时p->next是存放的是什么地址呢?显然是NULL，结果使p指向了NULL ,p指针又发生了移动。再判断p!=NULL，结论为假，退出循环。如图8.21所示。
图8.21
从而完成了链表的遍历（输出打印）。
8.8.3 动态链表
例8.6所生成的链表还是一种静态的链表，前面讲过，链表结构可以是动态地分配存储的，即在需要时才开辟结点的存储空间，实现动态链接。怎样开辟存贮空间呢？C语言的库函数提供了以下几个函数。
1.malloc 函数
原形为：
该函数如果成功调用，可以在内存中开辟size指定大小的连续空间。返回值类型为void，请注意这不是表示没有返回值，而是表示返回值可以指向任何类型。该函数是一个返回指针值的函数，如果成功调用，返回所开辟空间的首地址，如果失败返回NULL。该函数的参数可以用unsigned int size定义空间大小，也可以用变量类型名作参数来定义空间大小。
如：malloc(sizeof(int));开辟2个字节的存储空间，molloc(sizeof(struct student));开辟10个(4+4+2)字节。该函数返回值是void类型，因此调用时需要强制转换成需要的类型。
如：（int *）malloc(sizeof(int));
(struct people *)malloc(sizeof(struct student));
2. free 函数
原型为：
其作用是释放由p指向的内存区，即将这部分内存还给系统。我们要注意动态开辟的内存在不用之后应及时还给系统，以免造成内存“遗漏”。free函数无返回值。
这里要说明的是，这种能动态开辟存贮空间的区域是内存的堆栈区。
实际上只有建立动态链表才是有意义的。
例8.7 写一个函数建立一个有若干个学生数据的单向动态链表，并用num是否为0来判断输入是否结束。算法的N-S图如下：
例8.7N-S图
建立动态链表的步骤如下：
第一步：定义一个头指针head并指向NULL，如图8.22所示。同时定义p1,p2两个指向结构体指针变量，再设计全局变量n=0。
图8.22
第二步：开辟新结点，并使p1,p2指向它，然后输入一个学生数据给新结点，并使指针域指向NULL。因为n=1，所以head=p1;使head指向第一个结点，如图8.23所示。
图8.23
第三步：由于p1->num!=0，所以再开辟一个新结点，并使p1指向新结点，然后输入一个学生数据给新结点，并使指针域指向NULL。因为n=2，p2->next=p1;然后p2=p1;。如图8.24 所示。
图8.24
第四步：由于p1->num!=0，所以再开辟一个新结点，并使p1指向新结点，然后输入一个学生数据给新结点，并使指针域指向NULL。因为n=3，p2->next=p1;然后p2=p1;。如图8.25所示。
图8.25
第五步：由于p1->num!=0，所以再开辟一个新结点，并使p1指向新结点，然后输入一个学生数据给新结点，并使指针域指向NULL。因为p1->num==0,故退出循环。如图8.26所示。
图8.26
程序实现:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define LEN sizeof(struct people)
4 struct people
5 {
6 long num;
7 float score;
8 struct people *next;
9 };
10 int n;
11 struct people *creat(void)
12 {
13 struct people *head;
14 struct people *p1,*p2;
15 n=0;
16 head=NULL;
17 p1=p2=(struct people *)malloc(LEN);
18 scanf("%ld",&p1->num);
19 scanf("%f",&p1->score);
20 p1->next=NULL;
21 while(p1->num!=0)
22 {
23 n=n+1;
24 if(n==1)
25 head=p1;
26 else
27 p2->next=p1;
28 p2=p1;
29 p1=(struct people *)malloc(LEN);
30 p1->next=NULL;
31 scanf("%ld",&p1->num);
32 if(p1->num==0)
33 continue;
34 scanf("%f",&p1->score);
35 }
36 free(p1);
37 return(head);
38 }
39 void main()
40 {
41 struct people *p;
42 int i;
43 p=creat();
44 for(i=1;i<=n;i++)
45 {
46 printf("%ld\n%f\n",p->num,p->score);
47 p=p->next;
48 }
49 }
有关链表的其它运算，我们将在《数据结构》一书中介绍。
8.9 共用体
问题的提出：设计一个people结构体，用来存放学生或教师信息：
学生和教师信息中前五项都可以相同（类型），但后二项就不同了，如果是学生就要填写整型的班级号，如果是教师就要填写字符串型的职称了。
怎么具体实现这一结构体呢，如果我们这样定义如下：
struct people
{
……
int class;
char office[10];
};
很显然，在某种具体情况下，一个people变量只能是学生或者是教师，不可能两样都是，所以是学生给出班级号，是教师给出职称，不会两样同时都占。这就造成两个成员在同一时刻只使用一个的情况，另一个空闲了，就浪费了。如果定义的变量较多，造成内存浪费就越大，这不是一个好办法。
造成上述浪费的根本原因是因为无论班级号还是职称都有各自独立的存储空间。
怎么解决上述问题，能否做到是学生只分配班级号空间，是教师就分配职称空间，下面介绍的共用体可以基本做到这一点，以达到节省内存和更符合实际的目的。
8.9.1 共用体的概念
有时需要使几种不同类型的变量存放到同一段内存单元中。这些变量怎么占用同一单元呢，这里有以下几个因素要考虑：
第一：这些不同的变量它们起始地址都相同。
第二：每次只能存放其中一个变量。也就是使用覆盖技术，几个变量互相覆盖。
第三：共用体变量所占内存大小取几个不同类型变量所占内存中最大的那一个。
这种使几个不同的变量共占同一段内存的结构，称为“共用体”类型。如图8.27所示。
图8.27
共用体也是属于构造类型，也要先定义类型再定义变量。
共用体类型的定义
其中，union为定义共用体类型的关键字。
例：
union data
{
int i;
chat ch;
float f;
}a,b,c;
同学们想一想a,b,c共用体变量各占多大的存储空间？是2+1+4=7bit？还是取最大的成员所占的空间4bit?
也可以先定义类型，再定义变量，方法同结构体变量的定义相似。
8.9.2 共用体变量的引用方法
共用体变量的引用方法同结构体变量的引用方法一样，即不能整体引用共用体变量，只能引用共用体成员。
格式：
或
如：printf(“%d”,a);//整体引用了共用体变量，是错误的。
只能这样引用：a.i;或 b.ch;或 c.f;
如果p是指向共用体的指针变量，也可以这样引用：p->i ;或p->ch;或p->f; 。
8.9.3 共用体类型的特点
在使用共用体类型数据时要注意以下一些特点：
（1）同一个内存段可以用来存放几种不同类型的成员，但在某一时刻只能存放其中一种，而不能同时存放几种。
（2）内存中存放的数据是最后一次存入的内容，在此之前的内容全部被冲掉（覆盖），因此起作用的成员是最后一次存放的成员。
如：a.i=12;a.ch=‘c’;a.f=12.5;同学们想一想此时内存中存放的是什么？
（3）共用体变量的地址和它的各成员的地址都是同一地址。例如：&a, &a.i,&a.ch,&a.f都是同一地址值。
（4）不能对共用体变量名赋值，也不能企图引用变量名来得到一个值，也不能初始化共用体变量。例如以下这些都是错误的：
union
{
int i;
char ch;
float f;
}a={12,’c’,12.5}; /*不能初始化共用体变量*/
a=12; /*不能对共用体变量赋值*/
m=a; /*不能引用共用体变量名以得到一个值*/
（5）不能用共用体变量作为函数参数（共用体成员可以），也不能使函数带回共用体变量，但可以使用指向共用体变量的指针（与结构体变量这种用法相仿）。
（6）共用体和结构体可以互相嵌套定义。
例8.12：设有若干个人员的数据，其中有学生和教师。学生的数据中包括：姓名、学号、性别、职业、班级。教师的数据包括：姓名、号码、性别、职业、职务或职称，现在要将它们放在同一的表格中。如果“job”项为“s”则第6顶为class，如果“job”项为“t”，则第6项为office。显然对第6项要处理成共用体的形式将class和office放在同一段内存中，如图8.28所示。
图8.28
要求输入人员的数据，然后再输出。先看下面的N-S图。
例8.12N_S图
程序实现：
1 #include <stdio.h>
2 #include <stdlib.h>
3 struct
4 {
5 int num;
6 char name[10];
7 char sex;
8 char job;
9 union
10 {
11 int classa;
12 char office[10];
13 }category;
14 }person[2];
15 void main()
16 {
17 int i;
18 char numstr[20];
19 for(i=0;i<2;i++)
20 {
21 printf("请输入编号：");
22 gets(numstr);
23 person[i].num=atoi(numstr);
24 printf("请输入姓名：");
25 scanf("%s",person[i].name);
26 getchar(); //用来接收输入姓名后的“回车”符，下同。
27 printf("请输入性别(M/F)：");
28 scanf("%c",&person[i].sex);
29 getchar();
30 printf("请输入职业(t/s)：");
31 person[i].job=getchar();
32 if(person[i].job=='s')
33 {
34 printf("请输入班级号：");
35 scanf("%d",&person[i].category.classa);
36 getchar();
37 }
38 else
39 if(person[i].job=='t')
40 {
41 printf("请输入职称：");
42 scanf("%s",person[i].category.office);
43 getchar();
44 }
45 else
46 printf("input error!");
47 }
48 printf("\n\n");
49 printf(" No. Name Sex Job class/office\n");
50 for(i=0;i<2;i++)
51 {
52 printf("%-10d%-11s%",person[i].num,person[i].name);
53 if(person[i].sex=='M'||person[i].sex=='m')
54 printf("男");
55 if(person[i].sex=='F'||person[i].sex=='f')
56 printf("女");
57 if(person[i].job=='s')
58 printf("\t\t学生");
59 if(person[i].job=='t')
60 printf("\t\t教师");
61 if(person[i].job=='s')
62 printf("\t\t%d\n",person[i].category.classa);
| 
