1、结构体与共用体结构体与共用体10.1 结构体类型的定义结构体类型的定义 结构体由若干成员组成，各成员可有不同的类型。结构体由若干成员组成，各成员可有不同的类型。在程序中要使用结构体类型，必须先对结构体的组在程序中要使用结构体类型，必须先对结构体的组成进行描述。例如，学生信息可用结构体描述为：成进行描述。例如，学生信息可用结构体描述为：struct studentint num;/*学号*/char name20;/*姓名*/char sex;/*性别*/int age;/*年龄*/float score;/*成绩*/char addr40;/*家庭住址*/;需要特别指出的是“struct st
2、udent”是程序设计者自己定义的类型，它与系统预定义的标准类型(如int、char等)一样，可以用来定义变量，使变量具有struct student类型。例如：struct student st1,st220;分别定义了struct student结构体类型的变量st1和struct student结构体类型的数组变量st2。其中，关键字struct引入结构体类型的定义。struct之后任选的标识符是结构体类型的名字。用花括号括起来的是结构体成员说明。上例说明结构体类型struct student有6个成员，分别命名为num、name、sex、age、score和addr。这6个成员分别表示
3、学生的学号、姓名、性别、年龄、成绩和家庭住址，显然它们的类型是不同的。结构体类型的定义形式为：struct 结构体类型名结构体类型名成员说明表列成员说明表列;其中，花括号内的内容是该结构体类型的成员说明，每个成员说明的形式为：类型名类型名 成员名成员名;实际上，凡是相关的若干数据对象都可组合成一个结构体，在一个结构体名下进行管理。例如，由日、月、年组成的结构体类型为：struct dateint day;int month;int year;又如，某职工信息结构体类型为：struct personchar name20;/*姓名*/char address40;/*地址*/float sala
4、ry;/*工资*/float cost;/*扣款*/struct date hiredate;/*聘任日期*/;其中，结构体类型struct person含有一个结构体类型成员hiredate。该例子说明结构体类型可以嵌套定义，即一个结构体类型中的某些成员又是其他结构体类型。但是这种嵌套不能包含自身，即不能由自己定义自己。结构体类型说明中，详细列出了一个结构体的组成情况、结构体的各成员名及其类型。结构体类型说明了一个数据结构的“模式”，但不定义“实物”，并不要求分配实际的存储空间。程序要实际使用结构体，必须定义结构体变量。编译程序在为结构体变量分配存储空间时，其中各成员的存储格式及其意义与结构
5、体类型保持一致。10.2 结构体类型变量结构体类型变量 要定义一个结构体类型的变量，可采取以下要定义一个结构体类型的变量，可采取以下3种方法。种方法。10.2.1 结构体类型变量的定义 1.先定义结构体类型，再定义变量如上面已定义了一个结构体类型struct student，可以用它来定义变量。例如：struct student student1,student2;定义student1和student2为struct student类型变量，即它们具有struct student类型的结构体变量。应当注意，将一个变量定义为标准类型(基本数据类型)与定义为结构体类型不同之处在于：后者不仅要求指定
6、变量为结构体类型，而且要求指定为某一特定的结构体类型。例如，对struct student，不能只指定为struct型而不指定结构体名。而在定义变量为整型时，只需指定为int型即可。例如：struct studentint num;char name20;char sex;int age;float scorechar addr40;student1,student2;2.在定义类型的同时定义变量在定义类型的同时定义变量：struct结构体类型名结构体类型名成员说明表列成员说明表列变量名表列变量名表列;它的作用与前面定义的相同。即定义了两个struct student类型的变量student1
7、和student2。这种定义方法的一般形式为：3.直接定义结构体类型变量直接定义结构体类型变量其一般形式为：struct 成员说明表列成员说明表列变量名表列变量名表列;即在结构体定义时不出现结构体类型名，这种形式虽然简单，但不能在再需要时，使用所定义的结构体类型。(1)类型与变量是不同的概念，不要混同。对结构体变量来说，在定义时一般先定义一个结构体类型，然后定义变量为该类型。只能对变量赋值、存取或运算，而不能对一个类型赋值、存取或运算。在编译时，对类型是不分配存储空间的，只对变量分配存储空间。关于结构体类型，有几点需要说明：关于结构体类型，有几点需要说明：(2)对结构体中的成员，可以单独使用，
8、它的作用与地位相当于普通变量。(3)成员也可以是一个结构体变量。例如：struct date int month;int day;int year;struct member int num;char name20;char sex;int age;struct date birthday;/*成员变量是一个结构体变量*/char addr40;stu1,stu2;(4)成员名可以与程序中的其他变量名相同，两者不代表同一对象。例如，程序中可以另定义一个变量num，它与struct member中的num是两回事，互不干扰。先定义一个struet date结构体类型，它包括3个成员：month、
9、day、year，分别代表月、日、年。然后在定义struet member结构体类型时，成员birthday的类型定义为struet date类型。已定义的类型struct date与其他类型(如int、char)一样可以用来定义成员的类型。10.2.2 结构体变量的使用 引用一个结构体变量有两种方式：通过结构体变量名和通过指向结构体的指针变量。与之对应的，引用结构体成员的标记形式也有两种，分别用运算符“”和“”来标记。(1)由结构体变量名引用其成员的标记形式为：结构体变量名结构体变量名.成员名成员名例如，stu1.num表示引用结构体变量stu1中的num成员，因该成员的类型为int型的，所
10、以可以对它施行任何int型变量可以施行的运算。例如：stu1.num20312;(2)由指向结构体的指针变量引用结构体成员的标记形式为：指针变量名指针变量名-成员名成员名例如，如下变量定义：struct nodefloat x,y;p,u,*pt;定义了两个结构体变量p、u和一个指向该结构体的指针变量pt，分析以下语句：p.x=12.2;p.y=24.3;pt=&u;pt-x23.7;pt-y=3.5;语句“pt&u;”使pt指向结构体变量u，可用pt-x和pt-y访问结构体变量u的两个成员。上述语句执行情况可用图10.1描述各变量之间的关系。23.7 3.512.2 24.3ptup图10.
11、1 通过指向结构体的指针引用结构体 上述例子说明结构体的成员可以像普通变量一样使用。根据其类型决定其所有合法的运算。如果结构体成员本身又是结构体类型的，则可继续使用成员运算符取结构体成员的结构体成员，逐级向下，引用最低一级的成员。程序能对最低一级的成员进行赋值或存取;例如，对stu1某些成员的访问：stu1.birthday.day=23;stu1.birthday.month=8;stu1.birthday.year=2003;在早期的C语言中，程序只能对结构体变量(包括结构体变量的结构体成员)取地址运算，不允许对结构体进行赋值运算。ANSI C已经取消了这个限制，允许结构体值赋给相同类型的
12、结构体变量。程序也能对结构体的最低一级的成员进行其他运算，包括取地址运算，引用成员的地址。例如：scanf(”%”,&stu1.age);10.2.3 结构体变量的初始化 结构体变量和其他变量一样，可以在定义变量的同时进行初始化。1.对外部存储类型的结构体变量进行初始化例10.1 分析下列程序的输出结果。#include struct student long num;char name20;char sex;char addr40;a=3021103,”Jiang Linpad”,M,”123 Shaoshan Road”;main()printf(”No:%ldnName:%snSex:%
13、cnAddress:%sn”,a.num,a.name,a.sex,a.addr);程序运行结果如下：No:3021103Name:Jiang LinpanSex;MAddress:123 Shaoshan Road2.在函数内部的结构体变量进行初始化上面例子的定义部分可以放到main函数中。程序如下：main()static struct student long hum;char name20;char sex;char addr40;a=3021103,”Jiang Linpan”,M,”123 Shaoshan Road”;printf(”No:%ldnName:%snSex:%cnA
14、ddress:%sn”,a.num,a.name,a.sex,a.addr);程序运行结果与上面例子程序相同。注意,对自动结构体变量不能在定义时赋初值,只能在函数执行时用赋值语句对各成员分别赋值。10.2.4 结构体变量的输入和输出 C语言不能把一个结构体变量作为一个整体进行输入或输出,应该按成员变量输入输出。例如,若有一个结构体变量：struct char name12;char addr18;long num;stud=”Wang Dawei”,”125 Beijing Road”,3021118;变量stud在内存中存储情况如图10.2所示。是按成员变量存放的。Wa n gD a w e
15、 i 01 2 5B e i j i n gR o a d 03021118 name12 addr18 图10.2 结构体变量在内存中的存储情况 为两个字符串数据和一个长整型数据,因此输出stud变量,应该使用如下方式：printf(”%s,%s,%1dn”,stud.name,stud.addr,stud.num);输入stud变量的各成员值,则用：scanf(”%s%s%ld”,stud.name,stud.addr,&stud.num);由于成员项name和addr是字符数组,按s字符串格式输入,故不要写成&stud.name和&stud.addr,而num成员是long型,故应当用&
16、stud.num。当然也可以用gets函数和puts函数输入和输出一个结构体变量中的字符数组成员。例如：gets(stud.name);puts(stud.name);gets函数输入一个字符串给stud.name,puts函数输出stud.name数组中的字符串。10.3 10.3 结构体类型数组结构体类型数组 一个结构体变量中可以存放一组数据(如一个学生的学号、姓名、成绩等数据)。如果有10个学生的数据需要参加运算和处理,显然应该用数组,这就是结构体数组。结构体数组与以前介绍过的数值型数组不同之处在于每个数组元素都是一个结构体类型的数据,它们都分别包括各个成员项。10.3.1 结构体类型数
17、组的定义与定义结构体变量的方法一样,在结构体变量名之后指定元素个数,就能定义结构体数组。例如：struct student students30;struct person employees100;struct char name20;int num;float price;float quantity;parts200;以上定义了一个数组students,它有30个元素,每个元素的类型为struct student的结构体类型。定义数组employees,有100个元素,每个元素是struct person结构体类型。定义数组parts,有200个元素,每个元素也是一个结构体类型。它们都是
18、结构体数组,分别用于表示一个班级的学生、一个部门的职工、一个仓库的产品。如同元素为标准数据类型的数组一样,结构体数组各元素在内存中也按顺序存放,也可初始化,对结构体数组元素的访问也要利用元素的下标。特别地,访问结构体数组元素的成员的标记方法为：例如,访问parts数组元素的成员：parts10.price=37.5;scanf(”%s”,parts3.name);结构体数组名结构体数组名元素下标元素下标结构体成员名结构体成员名10.3.2 结构体类型数组的初始化 在对结构体数组初始化时,要将每个元素的数据分别用花括号括起来。例如：struct student char name20;long
19、num;int age;char sex;float score;students5;”Zhu Dongfen”,3021101,18,M,93,”Zhang Fachong”,3021102,19,M,90.5,”Wang Peng”,3021103,16,M,85,”Zhan Hong”,3021104,16,F,95,”Li Linggou”,3021105,20,F,67;这样,在编译时将一个花括号中的数据赋给一个元素,即将第一个花括弧中的数据送给students0,第二个花括弧内的数据送给students1,。如果赋初值的数据组的个数与所定义的数组元素相等,则数组元素个数可以省略不写
20、。这和前面有关章节介绍的数组初始化相类似。此时系统会根据初始化时提供的数据组的个数自动确定数组的大小。如果提供的初始化数据组的个数少于数组元素的个数,则方括弧内的元素个数不能省略,例如：struct studentstudents3:,;只对前3个元素赋初值,其他元素未赋初值,系统将对数值型成员赋以零,对字符型数据赋以“空”串即“0”。10.3.3 结构体数组的使用 一个结构体数组的元素相当于一个结构体变量。引用结构体数组元素有如下规则：(1)引用某一元素的一个成员。例如：studentsi.num这是序号为i的数组元素中的num成员。如果数组已如上初始化,且i=2,则相当于students2
21、.num,其值为3021103。(2)可以将一个结构体数组元素赋给同一结构体类型数组中的另一个元素,或赋给同一类型的变量。例如：struct student students3,student1;现在定义了一个结构体数组students,它有3个元素,又定义了一个结构体变量student1,则下面的赋值合法。student1=students0;students2=students1;students1=student1,(3)不能把结构体数组元素作为一个整体直接进行输入或输出,只能以单个成员对象进行输入输出。例如：scanf(”%s”,students0.name);printff(”%ld
22、”,&students0.num);10.4 10.4 结构体与函数结构体与函数10.4.1 结构体变量作函数参数 旧的C标准不允许用结构体变量作函数参数,只允许指向结构体变量的指针作函数参数,即传递结构体变量的首地址。新的标准以及许多C编译都允许用结构体变量作为函数参数,即直接将实参结构体变量的各个成员的值全部传递给形参的结构体变量。当然,实参和形参的结构体变量类型应当完全一致。例10.2 输入三个学生的信息并输出，其中输出的功能用一函数实现。#include#include struct stud_type char name20;long num;int age;char sex;mai
23、n()void list(struct stud_type student);struct stud_type student3,*p;int i;for(i=0,p=student;iname,&p-num,&p-age,&p-sex);for(i=0;inum,p-name,p-sex,p-score10.4.2指向结构体变量的指针作为函数参数 上一节介绍的用结构体变量作为函数参数，这是ANSI C新标准的扩充功能。在过去的C版本中不能这样用，而是通过指针来传递结构体变量的地址给形参，再通过形参指针变量引用结构体变量中成员的值。例10.3 有一结构体变量stu，内含学生学号、姓名和3门课的
24、成绩。要求在main函数中给变量赋值，在另一函数print中将它们打印输出。#include#include struct studentlong num;char name20;float score3;main()void print(struct student*);struct student stu;stu.num=3021210;strcpy(stu.name,”Li Dong”);stu.score0=67.5;stu.score1=89;stu.score2=78.6;print(&stu);void print(struct student*p)printf(”%ldn%sn
25、%fn%fn%fn”,p-num,p-name,p-score0,p-score1,p-score2);printf(”n”);程序运行结果如下：3021210Li Dong67.50000089.00000078.599998 struct student被定义为外部类型，这样同一文件中的各个函数都可以用它来定义变量的类型。main函数中的stu变量定义为struct student类型，printf函数中的形参p被定义为指向struct student类型数据的指针变量。在main函数中对stu的各成员赋值。注意在调用print函数时，用&stu作实参，&stu是结构体变量stu的地址。在
26、调用函数时将该地址传递给形参p(p是指针变量)。这样p就指向stu。在printf函数中输出p所指向的结构体变量的各个成员值，它们也就是stu的成员值。main函数中的对各成员赋值也可以改用scan函数输入。即：scanf(”%ld%s%f%f%f”,&stu.num,stu.name,&stu.score0,%stu.score1,&stu.score2);输入时用下面形式输入：3021210 LiDong 67.5 89 78.6注意，输入项表列中stu.name前没有“&”符号，因为stu.name是字符数组名本身代表地址，不应写成&stu.name。ANSIC允许用整个结构体作为函数的
27、参数传递，但是必须保证实参与形参的类型相同。上例中的main函数中的最后一行调用printf函数，也可以改用：print(stu);即实参改用结构体变量(而不是指针)。同时print函数也应相应改为：void print(struct student stud)printf(”%ldn%sn%fn%fn%fn”,stu.num,stu.name,stu.score0,stu.score1,slu.score2);printf(”n”);把一个完整的结构体变量作为参数传递，虽然合法，但是要将全部成员值一个一个传递，费时间又费空间，开销大。如果结构体类型中的成员很多，或者有一些成员是数组，则程序运
28、行效率会大大降低。在这种情况下，用指针做函数参数比较好，能提高运行效率。10.4.3 函数的返回值为结构体类型函数的返回值可以是结构体类型。例如，定义了结构体数组：struct student stud100;数据输入可由如下形式的语句实现：for(i=0;i100;i+)studi=input();函数input()的功能是输入一个结构体数据，并将输入结构体数据作为返回值，返回给第i个学生记录，实现第i个学生的数据输入。函数定义如下：struct student input()/*输入一个学生的数据*/int i;struct student stud;scanf(”%ld”,&stud.n
29、o);/*输入学号*/gets(stud.name);/*输入学生姓名*/for(i=0;i结构体成员名结构体成员名例如,通过pd引用结构体变量date3的day成员,写成pd-day,引用date3的month,写在pd-month等。“*指针变量”表示指针变量所指对象,所以通过指向结构体的指针变量引用结构体成员也可写成以下形式：(*指针变量指针变量)结构体成员名结构体成员名这里圆括号是必须的,因为运算符“*”的优先级低于运算符“.”。从表面上看,*pd.day等价于*(pd.day),但这两种书写形式都是错误的。采用这种标记方法,通过pd引用date3的成员可写成(*pd).day、(*p
30、d).month、(*pd).year。但是很少场合采用这种标记方法,习惯都采用运算符“-”来标记。例10.4 写出下列程序的执行结果。#Include#include main()struct studentlong num;char name20;char sex;float score;struct student stu1,*p;p=&stu1;stu1.num=3021118;strcpy(stu1.name,”Li Lin”);stu1.sexM;stu1.score=91.5;printf(”No:%ldnName:%snSex:%cnScore:%fn”,stu1.num,st
31、u1.name,stu1.sex,stu1.score);printf(”No:%ldnName:%snSex:%cnScore:%fn”,(*p).num,(*p).name,(*p).sex,(*p).score);在主函数中定义了struct student类型,然后定义一个struct student类型的变量stu1。同时又定义了一个指针变量p,它指向struct student结构体类型。在函数的执行部分,将stu1的起始地址赋给指针变量p,也就是使p指向stu1,然后对stu1中的成员num,其余类推。第二个printf函数也是用来输出stu1的各成员的值,但使用的是(*p).n
32、um这样的形式。程序运行结果如下：No:3021118Name:Li LinSex:MScore:91.500000No:302lll8Name:Li LinSex:MScore:91.500000可见两个printf函数输出的结果是相同的。上面程序中最后一个printf函数中的输出项列表可改为：p-num,p-name,p-sex,p-score2指向结构体数组元素的指针一个指针变量可以指向一个结构体数组元素,也就是将该结构体数组的数组元素地址赋给此指针变量。例如：struct int a;float b;arr3,*p;p=arr;此时使p指向arr数组的第一个元素,“p=arr;”等价于
33、“p=&arr0”。若执行“p+;”则此时指针变量p此时指向arr1,指针指向关系如图10.3所示。P p+arr0arr1arr2图10.3 指向结构体数组元素的指针10.5.2 链表 到目前为止,程序中的变量都是通过定义引入的,这类变量在其存在期间,它固有的数据结构是不能改变的。本节将介绍系统程序中经常使用的动态数据结构,其中包括的变量不是通过变量定义建立的,而由程序根据需要向系统申请获得。动态数据结构由一组数据对象组成,其中数据对象之间具有某种特定的关系。动态数据结构最显著的特点是它包含的数据对象个数及其相互关系可以按需要改变。经常遇到的动态数据结构有链表、树、图等,限于程序设计初学者,
34、在此只介绍其中简单的单向链表动态数据结构。10.5.2.1链表概述 链表是最简单也是最常用的一种动态数据结构。它是对动态获得的内存进行组织的一种结构。我们知道,用数组存放数据时,必须事先定义固定的长度(即数组元素个数)。比如,有的班级有50人,而有的班只有30人,如果要用同一个数组先后存放不同班级的学生数据,则必须定义长度为50的数组。如果事先难以确定一个班的最多人数,则必须把数组定义得足够大,以能存放任何班级的学生数据。显然这将会浪费内存空间。链表则没有这种缺限,它根据需要开辟内存单元。图10.4表示最简单的一种链表(单向链表)的结构。链表有一个头指针变量,图中以head表示,它存放一个地址
35、。该地址指向一个链表元素。链表中每一个元素称为结点,每个结点都应包括两部分：一是用户需要用的实际数据,二是下一个结点的地址。可以看出,head指向第一个结点,第一个结点又指向第二个结点,一直到最后一个结点,该结点不再指向其他结点,它称为表尾,它的地址部分放一个NULL(表示“空地址”)。链表到此结束。head2101图10.4 链表结构示意图 由图10.4所示,一个结点的后继结点位置由结点所包含的指针成员所指,链表中各结点在内存中的存放位置是可以任意的。如果寻找链表中的某一个结点,必须从链表头指针所指的第一个结点开始,顺序查找。另外,图10.4所示的链表结构是单向的,即每个结点只知道它的后继结
36、点位置,而不能知道它的前驱结点。在某些应用中,要求链表的每个结点都能方便地知道它的前驱结点和后继结点,这种链表的表示应设有两个指针成员,分别指向它的前驱和后继结点,这种链表称为双向链表。为适应不同问题的特定要求,链表结构也有多种变形。head2101链表与数组的主要区别是:(1)数组的元素个数是固定的,而组成链表的结点个数可按需要增减;(2)数组元素的存贮单元在数组定义时分配,链表结点的存贮单元在程序执行时动态向系统申请;(3)数组中的元素顺序关系由元素在数组中的位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。对于不是固定长度的列表,用可能最大长度的数组来描述,会浪费许多内存
37、空间。(4)对于元素的插入、删除操作非常频繁的列表处理场合,用数组表示列表也是不适宜的。若用链表实现,会使程序结构清晰,处理的方法也较为简便。例如在一个列表中间要插入一个新元素,如用数组表示列表,为完成插入工作,插入处之后的全部元素必须向后移动一个位置,空出的位置用于存储新元素。对于在一个列表中删除一个元素情况,为保持取组中元素相对位置连续递增,删除处之后的元素都得向前移一个位置。如用链表实现列表,链表结点的插入或删除操作不再需要移动结点,只需改变相关的结点中的后继结点指针的值即可,与结点的实际存储位置无关。操作细节见有关链表插入和删除操作的程序例子。链表的结点是结构体变量,它包含若干成员,其
38、中有些成员可以是任何类型,如标准类型、数组类型、结构体类型等;另一些成员是指针类型,是用来存放与之相连的结点的地址。单向链表的结点只包含一个这样的指针成员。下面是一个单向链表结点的类型说明：struct studentlong num;float score;struct student*next;其中next是成员名,它是指针类型的,它指向struct student类型数据(这就是next所在的结构体类型)。用这种方法可以建立链表,链表的每一个节点都是struct student类型,它的next成员存放下一节点的地址。这种在结构体类型的定义中引用类型名定义自己的成员的方法只允许定义指针时
39、使用。10.5.2.2 内存动态管理函数 前面已经提及,链表结点的存储空间是程序根据需要向系统申请的。C系统的函数库中提供了程序动态申请和释放内存存储块的库函数,下面分别介绍。1.malloc函数它的作用是在内存开辟指定大小的存储空间,并将此存储空间的起始地址作为函数值带回。malloc函数的原型为：void*malloc(unsigned int size)它的形参size为无符号整型。函数值为指针(地址),这个指针是指向void类型的,也就是不规定指向任何具体的类型。如果想将这个指针值赋给其他类型的指针变量,应当进行显式的转换(强制类型转换)。例如：malloc(8)用来开辟一个长度为8个
40、字节的内存空间,如果系统分配的此段空间的起始地址为 81268,则malloc(8)的函数返回值为81268。如果内存缺乏足够大的空间进行分配,则malloc函数值为“空指针”,即地址为0。2.calloc函数其函数原型为：vold*calloc(unsigned int num,unsigned int size)它有两个形参num和size。其作用是分配num个大小为size字节的空间。例如用calloc(20,30)可以开辟20个(每个大小为30字节)的空间,即总长为600字节。此函数返回值为该空间的首地址。成员也可以是一个结构体变量。3.free函数free函数的原型为：void fr
41、ee(void*ptr)其作用是将指针变量ptr指向的存储空间释放,即交还给系统,系统可以另行分配作它用。应当强调,ptr值不能是任意的地址项,而只能是由在程序中执行过的malloc或calloc函数所返回的地址。如果随便写：free(100)是不行的,系统怎么知道释放多大的存储空间呢?下面这样用是可以的：p=(long*)malloc(18);free(p);free函数它把原先开辟的18个字节的空间释放,虽然p是指向long型的,但可以传给指向void型的指针变量ptr,系统会使其自动转换。free函数无返回值。10.5.2.3 链表的基本操作链表的基本操作包括建立链表、链表的插入、删除、
42、输出和查找等。1.建立链表 所谓建立链表是指一个一个地输入各结点数据,并建立起各结点前后相链的关系。建立单向链表的方法有插表头(先进后出)方法和链表尾(先进先出)方法两种。插表头方法的特点是：新产生的结点作为新的表头插入链表;链表尾方法的特点是：新产生的结点接到链表的表尾。图10.5a表示用插表头方法建立链表,图10.5b表示用链表尾方法建立链表。从图10.5a可知,用插表头的方法,链表只需要用head指针指示,产生的新结点的地址存人指针变量p,使用赋值语句：p-next=head;将head指示的链表接在新结点之后;用head=p;使头指针指向新结点。插表头算法抽象描述如下：(1)head=
43、NULL;/*表头指向空,表示链表为空*/(2)产生新结点,地址赋给指针变量p;(3)p-next=head;head=p;/*插表头操作*/(4)循环执行2)可继续。headPheadPpnext=headhead=p顶点表头接在新结点之后，新结点作为表头链表已有K个结点，P指向新结点图10.5a 插表头方法建立链表链表尾算法抽象描述如下：(1)head=last=NULL;/*表头指向空,表示链表为空,last是表尾指针*/(2)产生新结点,地址赋给指针变量p;p-next=NULL;/*新结点作为表尾*/(3)如果head为NULL则head=p;/*新结点作为表头,这时链表只有一个结点
44、*/否则last-next=p;/*链表操作*/(4)last=p;/*表尾指针1ast指向新结点*/(5)循环执行(2),可继续建立新结点。用链表尾方法建立链表如图10.5b所示。headlastPLast-next=p新结点接到表尾headlast链表已有K个结点，P指向新结点。准备接到表尾，表尾由last指针指示p图10.5b 链表尾方法建立链表下面通过一个例子来说明如何建立一个链表。例10.5 写一函数建立一个有n名学生数据的单向链表。链表尾方法思路如下：(1)设3个指针变量：head、p1、p2,它们都指向结构体类型数据。(2)head和p2的初始值为NULL(即等于0),p2作为表
45、尾指针。(3)用malloc函数开辟一个结点,并使p1指向它。(4)从键盘读人一个学生的数据给p1所指的结点。约定学号不会为零,如果输入的学号为0,则表示建立链表的过程完成(约定学号不会为零)。(5)如果n=1,则p2=head=p1;即把pl的值赋给head和p2,新结点既是表头也是表尾,pl所指向的新开辟的结点就成为链表中第1个结点。(6)重复(3)、(4)产生新结点。由于nl,将新结点链接到表尾,表尾指针p2指向新的表尾。当新结点输入的数据为：p1-num=0,此新结点不被连接到链表中,循环终止。建立链表的函数如下：#delfin NULL 0#define LEN sizeof(str
46、uct student)struct studentlong num;float score;struct student*next;int n;struct student*creat()/*此函数带回一个指向链表头的指针*/struct student*head,*p1,*p2;n=0;head=NULL;pl=(struct student)malloc(LEN);/*创建第一个结点*/scanf(“%1d,%f”,&p1-num,&pl-score);p1-next=NULL;while(p1-num!=0)/*应该将结点加入链表*/+n;if(n=1)head=pl;/*是第一个结点
47、,作表头*/else p2-next=pl;/*不是第一个结点,作表尾*/p2=pl;p1=(struct student*)malloc(LEN);/*开辟下一个结点*/scanf(“%ld,%f”,&p1-num,&p1-score);p1-next=NULL;free(p1);/*释放最后一个结点所占的内存*/return(head);/*返回链表的头指针*/关于函数的说明：(1)第一行为#define命令行,令NULL代表0,用它表示“空地址”。第二行令LEN代表struct student结构体类型数据的长度,sizeof是“求字节数运算符”。(2)creat函数是指针类型,即此函数
48、带回一个指针值,它指向一个struct student类型数据。实际上treat函数带回一个链表起始地址。(3)在一般系统中,malloc带回的是指向字符型数据的指针。而p1、p2是指向structstudent类型数据的指针变量,两者所指的是不同类型的数据。因此必须用强制类型转换的方法使之类型一致,在malloc(LEN)之前加了“(struct student*)”,它的作用是使malloc返回的指针转换为指向struct student类型数据的指针。注意“*”号不可省略,否则变成转换成struct student类型了,而不是指针类型了。(4)函数返回的是head的值,也就是链表的头地
49、址。n代表结 点个数。2.链表的插入操作任务：将一个结点插入到二个已有链表中的某个位置。该任务可以分解成两个步骤：(1)找到插入点。方法：从链表头开始逐一查找要插入位置的一前一后两个节点，并分别保存为p2，p1。如果找到链表尾都没找到，说明没有满足条件的插入点。算法：最初p1=head;移动指针为p2=p1;p1=p1-next 直到找到插入点。(2)插入结点。方法：先使待插节点的指针域指向p1，然后再使p2的指针域指向待插节点。算法：p0-next=p1(p0为待插入结点);p2-next=p0;要点：在插入节点时要注意为什么不能把p0-next=p1和p2-next=p0顺序颠倒呢？举个简
50、单的例子，我们在放风筝的时候，发现手中的线太短了，想接上一段，如果我们不先连接好与风筝相连的一端，风筝就会随风飘走。我们在插入节点的时候，必须先让待插节点指向后续节点，不然我们在段开p1，p2之间的“线索”时，后续节点就不知道跑到什么地方去了。两个步骤如图10.6所示。链表的插入操作算法描述如下：仍然以例10.5建立一个有n名学生数据的单向链表为例。用指针变量p0指向待插入的结点,设已有的链表各结点是按学号由小到大顺序排序的。最初p1=head找插入点步骤如下：当p0-numpl-num且p1-next!=NULL p2=p1；p1=p1-next;插入结点操作如下：如果p1=head则 结点
