1、n教学目的教学目的：通过本章的学习，要求了解结构型、链表、通过本章的学习，要求了解结构型、链表、共用型和枚举型数据的特点，熟练掌握结构型共用型和枚举型数据的特点，熟练掌握结构型的定义方法，结构型变量、数组、指针变量的的定义方法，结构型变量、数组、指针变量的定义、初始化和成员的引用方法；掌握简单链定义、初始化和成员的引用方法；掌握简单链表的基本操作原理和应用；掌握共用型和枚举表的基本操作原理和应用；掌握共用型和枚举型的定义方法及对应变量的定义与引用；掌握型的定义方法及对应变量的定义与引用；掌握用户自定义类型的定义和使用。学习本章内容用户自定义类型的定义和使用。学习本章内容可以为今后学习数据结构中
2、的链表创建和使用可以为今后学习数据结构中的链表创建和使用打下基础。打下基础。n教学内容教学内容 结构型的引入，很好的处理生活总的各种表格或表格中的记录结构型的引入，很好的处理生活总的各种表格或表格中的记录结构型的定义，结构型变量的定义、赋值、引用及引用链表等方法结构型的定义，结构型变量的定义、赋值、引用及引用链表等方法共用型的定义，共用型变量的定义、赋值、引用共用型的定义，共用型变量的定义、赋值、引用枚举型的定义，共用型变量的定义、赋值、引用枚举型的定义，共用型变量的定义、赋值、引用n重点和难点重点和难点重点：重点：(1)结构型、共用型、枚举型数据的特点和定义结构型、共用型、枚举型数据的特点和
3、定义(2)结构型变量、数组、指针变量的定义、初始化和成员结构型变量、数组、指针变量的定义、初始化和成员引用方法引用方法(3)共用型和枚举型变量的定义和引用方法共用型和枚举型变量的定义和引用方法难点难点:(1)嵌套的结构型数据的处理嵌套的结构型数据的处理 (2)用结构体解决链表问题（建立、插入、删除、输出和用结构体解决链表问题（建立、插入、删除、输出和查询）。查询）。结构型是用户自己定义的数据类型结构型是用户自己定义的数据类型 前面我们学习过了基本数据类型，例如：前面我们学习过了基本数据类型，例如：short、long、int、float、double、char等，这些基本数据类型都是系统等，这
4、些基本数据类型都是系统已经定义好的，用户可以直接使用它们。但现实世界是复已经定义好的，用户可以直接使用它们。但现实世界是复杂的，在我们的日常生活中有很多的表格，各表格之间又杂的，在我们的日常生活中有很多的表格，各表格之间又有关联。因此用户需要自己定义数据类型，用户自己定义有关联。因此用户需要自己定义数据类型，用户自己定义的数据类型一旦定义好之后，就可以像使用系统类型一样的数据类型一旦定义好之后，就可以像使用系统类型一样使用它。例如：对一个新生进行入学登记时，就需要填一使用它。例如：对一个新生进行入学登记时，就需要填一张表格，填写的内容包括姓名、性别、学号、年龄、家庭张表格，填写的内容包括姓名、
5、性别、学号、年龄、家庭住址、联系电话、总分等多个数据项，其中姓名是字符串住址、联系电话、总分等多个数据项，其中姓名是字符串型（可以用字符数组来表示），性别是字符型（用型（可以用字符数组来表示），性别是字符型（用m表示表示男性、用男性、用f表示女性），年龄是整型，总分是实型。表示女性），年龄是整型，总分是实型。如图如图8-1所示，所示，这些数据项之间关系紧密，每一个这些数据项之间关系紧密，每一个学生通过姓名、性别、学号、年龄、家庭地址、联系学生通过姓名、性别、学号、年龄、家庭地址、联系电话、总分等属性构成一个整体反映一个学生的基本电话、总分等属性构成一个整体反映一个学生的基本情况。如果将姓名、性
6、别、学号、年龄、家庭地址、情况。如果将姓名、性别、学号、年龄、家庭地址、联系电话、总分分别定义为互相独立的简单变量，难联系电话、总分分别定义为互相独立的简单变量，难以反映它们之间的内在联系。为了方便处理此类数据，以反映它们之间的内在联系。为了方便处理此类数据，常常把这些关系密切但类型不同的数据项组织在一起，常常把这些关系密切但类型不同的数据项组织在一起，即即“封装封装”起来，并为其取一个名字，在语言中就起来，并为其取一个名字，在语言中就称其为结构体（也人称为构造体），结构体是用户自称其为结构体（也人称为构造体），结构体是用户自定义数据类型的一种。定义数据类型的一种。结构体类型定义的一般形式结构
7、体类型定义的一般形式struct 结构型名结构型名数据类型标识符成员；数据类型标识符成员；数据类型标识符成员；数据类型标识符成员；数据类型标识符成员数据类型标识符成员n；请读者注意结构体定义语句的右花括号后面用分号（；）请读者注意结构体定义语句的右花括号后面用分号（；）做语句结束标记。做语句结束标记。结构体型定义实例结构体型定义实例n例如：为了存放一个人的姓名、性别、年龄、工资，例如：为了存放一个人的姓名、性别、年龄、工资，可以定义如下的结构型：可以定义如下的结构型：struct person char name10;char sex;int age;float wage;/*这个名为这个名为
8、person的结构型共含有的结构型共含有4个成员个成员*/【例8.1】一开始所讲的例题中的birthday类型和person类型。struct birthday /*定义含有定义含有3个整型成员的结构型个整型成员的结构型 birthday*/int year;int month;int day;struct person /*定义含有定义含有4个成员的结构型个成员的结构型 person*/char name20;char sex;struct birthday bir;/*该成员的数据类型是结构型该成员的数据类型是结构型*/float wage;n先定义结构型，后定义变量先定义结构型，后定义变
9、量n定义结构型的同时定义变量定义结构型的同时定义变量 n定义无名称的结构型的同时定义变量定义无名称的结构型的同时定义变量 8.2 结构体变量的定义和引用结构体变量的定义和引用 例如：为学生信息定义例如：为学生信息定义2个变量个变量x和和y,程序段如下：程序段如下：struct studentlong number;char name20;char sex;float score3;struct student x,y;在定义变量的同时，可以变量赋初值，例如上例中的定义语在定义变量的同时，可以变量赋初值，例如上例中的定义语句可以改写如下：句可以改写如下：struct student x=1000
10、01L,”Tom”,m,86,94,89,y=100002L,”Lucy”,f,78,88,45;例如：为学生信息定义例如：为学生信息定义2个变量个变量x和和y,并给他们赋初并给他们赋初值，程序段如下：值，程序段如下：struct studentlong number;char name10;char sex;float score3;x=100001L,”Tom”,m,86,94,89,y=100002L,”Lucy”,f,78,88,45,;这种方法是将类型定义和变量定义同时进行。以后这种方法是将类型定义和变量定义同时进行。以后仍然可以使用这种结构型来定义其它的变量。仍然可以使用这种结构型
11、来定义其它的变量。例如：为学生信息定义例如：为学生信息定义2个变量个变量x和和y,并给它们赋初值，程并给它们赋初值，程序段如下：序段如下：structlong number;char name10;char sex;float score3;x=100001L,”Tom”,m,86,94,89,y=100002L,”Lucy”,f,78,88,45,;这种方法是将类型定义和变量定义同时进行，但结构型的这种方法是将类型定义和变量定义同时进行，但结构型的名称省略，以后将无法使用这种结构型来定义其它变量，名称省略，以后将无法使用这种结构型来定义其它变量，建议尽量少用。建议尽量少用。1.结构型变量成员
12、的引用方法结构型变量成员的引用方法2.结构型变量成员地址的引用方法结构型变量成员地址的引用方法3.结构型变量地址的引用方法结构型变量地址的引用方法结构型变量成员的引用格式如下：结构型变量成员的引用格式如下：n结构型变量名结构型变量名.成员名成员名 其中的其中的“.”称为成员运算符，其运算级别是最称为成员运算符，其运算级别是最高的，和圆括号运算符高的，和圆括号运算符“（）（）”、下标运算符、下标运算符“”是同级别的，运算顺序是自左向右。是同级别的，运算顺序是自左向右。如果某个结构型变量的成员数据类型又是一个结构型，如果某个结构型变量的成员数据类型又是一个结构型，则其成员的引用方法如下：则其成员的
13、引用方法如下：n外层结构型变量外层结构型变量.外层成员名外层成员名.内层成员名内层成员名【例8.2】求Tom的三门课程的成绩总分，并在显示器显示出来（使用结构型变量成员的引用）。#include”string.h”struct student long number;char name10;char sex;float score3;main()struct student stu1;/*定义student类型的变量stu1*/stu1.number=100001L;/*给结构型变量stu1的成员number赋值*/strcpy(stu1.name;”Tom”);/*给结构型变量stu1的成员
14、name赋值*/stu1.sex=f;/*给结构型变量stu1的成员sex赋值*/stu1.score0=89;/*给结构型变量stu1的成员score赋值*/stu1.score1=91;stu1.score2=86;printf(“%s的总分是：%fn”,stu.name,stu1.score0+stu1.score1+stu1.score2);结构型的变量成员地址引用格式如下：结构型的变量成员地址引用格式如下：n&结构型的变量名结构型的变量名.成员名成员名存放结构型变量成员地址的指针变量类型必须和该成存放结构型变量成员地址的指针变量类型必须和该成员的类型相同。员的类型相同。#includ
15、e“string.h”/*程序中使用了字符串处理函数程序中使用了字符串处理函数*/sturct student2 /*定义定义student2结构型结构型*/long number;char name10;main()struct student2 x;/*定义定义student2类型的变量类型的变量x*/long*p_number;/*定义能指向结构型定义能指向结构型student成员成员number的指针变量的指针变量*/char*p_name;/*定义能指向结构型定义能指向结构型student成员成员namer的指针变量的指针变量*/p_number=&x.number;/*让指针变量指
16、向结构型变量让指针变量指向结构型变量x的成员的成员*/*p_ number=100001L;/*用指针变量给结构型变量用指针变量给结构型变量x的所有成员赋值的所有成员赋值*/strucpy(p_ name,”zhongxin”);printf(“number=%1d name=%sn”,*p_number,*p_ name);/*用指针变量输出结构型变量用指针变量输出结构型变量x所有成员的值所有成员的值*/从这个例子可以看出，使用指向结构型变量成员的指针变量来引用成员的方法比较繁从这个例子可以看出，使用指向结构型变量成员的指针变量来引用成员的方法比较繁琐，可以直接使用结构型变量的指针成员来引用
17、成员。具体使用方法请参看第琐，可以直接使用结构型变量的指针成员来引用成员。具体使用方法请参看第8章章8.4节。节。结构型变量地址的引用格式如下：结构型变量地址的引用格式如下：&结构型变量名结构型变量名 例如：借用例例如：借用例8.4中的结构型中的结构型struct student2:struct student2 y,*sty=&y;存放结构型变量地址的指针变量必须是类型相同的结构存放结构型变量地址的指针变量必须是类型相同的结构型指针，关于如何使用结构型变量地址的例子请参见型指针，关于如何使用结构型变量地址的例子请参见8.4节中介绍的指向结构型数据的指针变量。节中介绍的指向结构型数据的指针变量
18、。在实际应用中，我们经常要处理的是具有在实际应用中，我们经常要处理的是具有 相同数据结构的一个群体。比如一批书，所有相同数据结构的一个群体。比如一批书，所有员工的通信地址，一个班级的学生等。由相同员工的通信地址，一个班级的学生等。由相同结构类型变量组成的数组，称为结构型数组。例结构类型变量组成的数组，称为结构型数组。例如，全班有如，全班有40人，在总成绩单上每人占一行，每人，在总成绩单上每人占一行，每行的内容包括学号、姓名、行的内容包括学号、姓名、3门功课的成绩、平门功课的成绩、平均分、名次，这样一个总成绩单就可以用结构型均分、名次，这样一个总成绩单就可以用结构型数组表示。数组表示。1.先定义
19、结构型，然后再定义结构型数组并赋初值先定义结构型，然后再定义结构型数组并赋初值 2.定义结构型的同时定义数组并赋初值定义结构型的同时定义数组并赋初值 3.定义无名称的结构型的同时定义数组并赋初值定义无名称的结构型的同时定义数组并赋初值 struct student /*定义结构型定义结构型*/long number;char name10;char sex;float score3;struct student s3=200001L,”Tom”,m,78,86,92,200002L,”Lucy”,f,85,69,82,200003L,”Jack”,m,84,88,96 ;struct stud
20、ent /*定义结构型定义结构型*/long number;char name10;char sex;float score3;s3=200001L,”Tom”,m,78,86,92,200002L,”Lucy”,f,85,69,82,200003L,”Jack”,m,84,88,96 ;struct /*定义结构型定义结构型*/long number;char name10;char sex;float score3;s3=200001L,”Tom”,m,78,86,92,200002L,”Lucy”,f,85,69,82,200003L,”Jack”,m,84,88,96 ;1.结构型数组
21、元素的引用格式如下；结构型数组元素的引用格式如下；结构型数组名结构型数组名下标下标.成员名成员名2.结构型数组元素成员地址的引用格式如下：结构型数组元素成员地址的引用格式如下：&结构型数组名结构型数组名下标下标.成员名成员名n【例【例8.5】输入】输入3个学生的数据，每个学生的信息个学生的数据，每个学生的信息由学号、姓名和三门功课的成绩组成，然后计算每由学号、姓名和三门功课的成绩组成，然后计算每一个学生的总分，并输出总分最高的学生信息。一个学生的总分，并输出总分最高的学生信息。n分析：将分析：将3个学生定义为结构型类型数组，学号个学生定义为结构型类型数组，学号为长整型、成绩为实型数组，总分存在
22、成绩数组中。为长整型、成绩为实型数组，总分存在成绩数组中。#define N 3struct student /*定义结构型定义结构型*/long number;char name10;float scoreN+1;/*score数组前三个元素用来存放成绩，第四个元素用来存数组前三个元素用来存放成绩，第四个元素用来存 放总分放总分*/stuN;main()float max=0;int i,j,max_i=0;for(i=0;iN;i+)printf(“输入第输入第%d个学生的信息，依次输入学号，姓名，三个成绩，各数个学生的信息，依次输入学号，姓名，三个成绩，各数据之间用据之间用,隔开隔开”,
23、i)；scanf(“%ld,%s,%f,%f,%f”,&stui.number,&stui.name,&stui.score0,&stui.score1,&stui.score2);stui.score3=stui.score0+stui.score1+stui.score2;if(max成员名成员名n 方式方式1比较好理解，其中比较好理解，其中“*指针变量指针变量”就代表了它就代表了它所指向的结构型变量，利用所指向的结构型变量，利用“成员运算符成员运算符”来引用，来引用，其作用相当于其作用相当于“结构型变量结构型变量.成员名成员名”。需要注意的。需要注意的是是“*指针变量指针变量”必须用圆括
24、号括住，因为必须用圆括号括住，因为“*”运算运算符的级别低于符的级别低于“.”运算符，如果不加括号，则优先处运算符，如果不加括号，则优先处理理“.”运算符，将出现运算符，将出现“指针变量指针变量.成员名成员名”，会造，会造成语法错误。成语法错误。n 方式方式2是一种新的引用方法，其中是一种新的引用方法，其中“-”称为称为“指向指向成员运算符成员运算符”，也简称，也简称“指向运算符指向运算符”。其运算级。其运算级别和别和“（）（）”、“”、“.”是同级的。指向运算符是同级的。指向运算符的左边必须是已指向某个结构型变量或数组元素的的左边必须是已指向某个结构型变量或数组元素的指针变量，其右边必须是对
25、应结构型数据的成员名。指针变量，其右边必须是对应结构型数据的成员名。1.指针变量指向数组元素指针变量指向数组元素 如果一个结构型数组元素的地址已赋予相同结构型指针变量（即指针变量如果一个结构型数组元素的地址已赋予相同结构型指针变量（即指针变量指向结构型数组元素），可以使用下列两种方法来引用数组该元素的成指向结构型数组元素），可以使用下列两种方法来引用数组该元素的成员，其作用完全相同。员，其作用完全相同。方式方式1 （*指针变量）。成员名指针变量）。成员名 方式方式2 指针变量指针变量-成员名成员名 注意：这里的指针变量必须是指向某个数组元素的。例如，它指向的数组注意：这里的指针变量必须是指向某
26、个数组元素的。例如，它指向的数组元素为元素为“数组名数组名k”，则上述两种引用方式均代表，则上述两种引用方式均代表“数组名数组名k。成员。成员名名”。2.指针变量指向数组首地址指针变量指向数组首地址 当一个结构型数组的首地址已经赋予相同结构型的指针变量（即指针变当一个结构型数组的首地址已经赋予相同结构型的指针变量（即指针变量指向结构型数组），可以使用下列两种方式来引用下标为量指向结构型数组），可以使用下列两种方式来引用下标为i的数组元素的数组元素成员，其作用完全相同。成员，其作用完全相同。方式方式1（*（指针变量（指针变量+i）.成员名成员名 方式方式2（指针变量（指针变量+i）成员名成员名
27、注意：这里的指针变量必须是指向某个数组首地址的，则上述两种引用注意：这里的指针变量必须是指向某个数组首地址的，则上述两种引用方式均代表方式均代表“数组名数组名i。成员名。成员名1.采用采用“全局外部变量方式传递数据全局外部变量方式传递数据”2.采用采用“返回值方式传递数据返回值方式传递数据”3.采用采用“形式参数和实际参数结合的地址传递方形式参数和实际参数结合的地址传递方式双向传递数据式双向传递数据”我们知道用数组存放数据时，必须事先定义好数我们知道用数组存放数据时，必须事先定义好数组的大小，不能在程序中随便进行调整。比如有的组的大小，不能在程序中随便进行调整。比如有的班有班有100人，有的班
28、只有人，有的班只有30人，如果要用同一个数人，如果要用同一个数组先后存放不同班级的学生数据，则必须定义长度组先后存放不同班级的学生数据，则必须定义长度为为100的数组。如果事先难以确定一个班的最多人的数组。如果事先难以确定一个班的最多人数，则必须把数组定义的足够大，以存放任何班级数，则必须把数组定义的足够大，以存放任何班级的学生数据，这显然非常浪费存储空间。为此的学生数据，这显然非常浪费存储空间。为此C语语言提供了动态数组的构建，即链表。言提供了动态数组的构建，即链表。链表如同一条铁链一样，一环扣一环，中间是不能断开链表如同一条铁链一样，一环扣一环，中间是不能断开的。这好比幼儿园的老师带领孩子
29、出去玩，老师牵着第一个的。这好比幼儿园的老师带领孩子出去玩，老师牵着第一个孩子的手，第一个孩子的另一只手牵着第二个孩子的手孩子的手，第一个孩子的另一只手牵着第二个孩子的手这就是一个这就是一个“链链”，最后一个孩子有一只手空着，他就是，最后一个孩子有一只手空着，他就是“链链尾尾”。要找这个队伍，就必须先找到老师，然后顺序找到每。要找这个队伍，就必须先找到老师，然后顺序找到每一个孩子。一个孩子。链表是一种动态数据结构，在程序的执行过程中可以根据链表是一种动态数据结构，在程序的执行过程中可以根据需要随时间系统申请存储空间，动态地进行存储空间的分需要随时间系统申请存储空间，动态地进行存储空间的分配。动
30、态数据结构最显著的特点是包含的数据对象个数及其配。动态数据结构最显著的特点是包含的数据对象个数及其相互关系都可以按需要改变。常用的动态数据结构有链表、相互关系都可以按需要改变。常用的动态数据结构有链表、循环链表、双向链表三种。本章只介绍动态数据结构中最简循环链表、双向链表三种。本章只介绍动态数据结构中最简单的单链表的建立及其基本操作。单的单链表的建立及其基本操作。链表有一个链表有一个“头指针头指针”head，它存放链表第一个结点的首地址，它存放链表第一个结点的首地址，它没有数据，只是一个指针变量。从图它没有数据，只是一个指针变量。从图8-2中我们看到它指向链表中我们看到它指向链表的第一个元素。
31、链表的每一个元素称为一个的第一个元素。链表的每一个元素称为一个“结点结点”(node)。每。每个结点都分为两个域，一个是数据域，存放各种实际的数据，如个结点都分为两个域，一个是数据域，存放各种实际的数据，如学号学号num、姓名、姓名name、性别、性别sex、和成绩、和成绩score等。另一个域为指等。另一个域为指针域，存放下一个结点的首地址，即指向下一个结点。链表中的针域，存放下一个结点的首地址，即指向下一个结点。链表中的每一个结点都是同一个结构类型。最后一个结点称为每一个结点都是同一个结构类型。最后一个结点称为“链尾链尾”，尾结点无后续点，因此不指向其他的元素，表尾结点的指针为空尾结点无后
32、续点，因此不指向其他的元素，表尾结点的指针为空(NULL)。由于每个结点包含数据域或者指针域两部分内容，所以链表结点采用由于每个结点包含数据域或者指针域两部分内容，所以链表结点采用结构体表示。例如链表结点的数据结构定义如下：结构体表示。例如链表结点的数据结构定义如下：struct node int num;char name10;float score;struct node*next;在链表结构中，除了数据项成员之外，还应包含一个指向本身的指在链表结构中，除了数据项成员之外，还应包含一个指向本身的指针，该指针在使用时指向具有相同类型结构体的下一个结点。针，该指针在使用时指向具有相同类型结构体
33、的下一个结点。在链表结点的数据结构中，比较特殊的一点就是结构体内指针域的数在链表结点的数据结构中，比较特殊的一点就是结构体内指针域的数据类型使用了未定义成功的数据类型。这是在据类型使用了未定义成功的数据类型。这是在C语言中唯一可以先使语言中唯一可以先使用后定义的数据结构。用后定义的数据结构。n【例【例 8.10】建立一个如图】建立一个如图8-3所示的简单链表，它由所示的简单链表，它由三个学生数据结点组成。请输出各结点中的数据。三个学生数据结点组成。请输出各结点中的数据。n分析：为方便操作，将学生定义为一个结构体类型分析：为方便操作，将学生定义为一个结构体类型student，它有三个成员分别用来
34、表示学生的学号、，它有三个成员分别用来表示学生的学号、姓名和下一个结点的地址。在程序中逐个输入各学姓名和下一个结点的地址。在程序中逐个输入各学生的数据，通过地址赋值操作建立链表。利用当型生的数据，通过地址赋值操作建立链表。利用当型循环用循环用printf语句逐个输出个结点中成员的值。语句逐个输出个结点中成员的值。程序如下：程序如下：#includestruct student char no6;char name10;struct student*next;void main()struct student A=“02019”,”tom”,B=“02019”,”jane”,C=“02019”,
35、”henry”;struct srudent*head=NULL,*p;head=&A;A.next=&B;B.next=&C;C.next=NULL;p=head;while(p!=NULL)printf(“No:%stName:%sn”,p-no,p-name);p=p-next;在本例中，所有结点都是在程序中定义的、不是临时开辟的、用完后也不能释放，我们把在本例中，所有结点都是在程序中定义的、不是临时开辟的、用完后也不能释放，我们把这种链表称为这种链表称为“静态链表静态链表”n所谓所谓“动态链表动态链表”就是链表的结构是动态分配就是链表的结构是动态分配和存储的，在程序的执行过程中要根据需
36、要随和存储的，在程序的执行过程中要根据需要随时向系统申请存储空间，动态地进行存储空间时向系统申请存储空间，动态地进行存储空间的分配。在的分配。在C语言中，提供了一下函数完成存储语言中，提供了一下函数完成存储空间的动态分配和释放。空间的动态分配和释放。nmalloc函数函数ncalloc函数函数nfree函数函数n其函数原型为：其函数原型为：void*malloc(unsigned size)n 其作用是在内存的动态存储区中分配一个长度其作用是在内存的动态存储区中分配一个长度为为size的连续空间，并返回指向该空间起始地的连续空间，并返回指向该空间起始地址的指针。若分配失败（如系统不能提供所需址
37、的指针。若分配失败（如系统不能提供所需内存），则返回空指针内存），则返回空指针NULL。n其函数原型为：其函数原型为：void*calloc(unsigned n,unsigned size)n 该函数有两个形参该函数有两个形参n和和size。其作用是在内存。其作用是在内存的动态存储区中分配的动态存储区中分配n个长度为个长度为size的连续空间，的连续空间，并返回指向该空间首地址的指针。如用并返回指向该空间首地址的指针。如用calloc(20,20)可以开辟可以开辟20个（每个大小为个（每个大小为20字字节）的空间，即空间总长为节）的空间，即空间总长为400字节。若分配字节。若分配失败，则返回
38、空指针失败，则返回空指针NULL。n其函数原型为：其函数原型为：void*free(void*ptr)n其作用是释放由其作用是释放由malloc、calloc等函数申请的内等函数申请的内存空间，使这部分内存区能够被其他变量所使存空间，使这部分内存区能够被其他变量所使用。用。ptr是最近一次调用是最近一次调用malloc()或或calloc()函数函数返回的值。返回的值。Free函数没有返回值。函数没有返回值。n在使用上述函数时要注意，函数的原型在文件在使用上述函数时要注意，函数的原型在文件malloc.h和和stdlib.h中定义。在程序中必须包含中定义。在程序中必须包含这两个头文件。下面的程
39、序就是这两个头文件。下面的程序就是malloc()和和free()两个函数配合使用的简单实例。两个函数配合使用的简单实例。#include#include#includemain()char*str;if(str=(char*)malloc(10)=NULL)printf(“Not enough memory to allocate buffern”);exit(1);strcpy(str,”welcome”);printf(“String is%sn”,str);free(str);本例中首先用本例中首先用malloc函数向内存申请一块内存区，并把首地址赋予指针变量函数向内存申请一块内存区，
40、并把首地址赋予指针变量str，是，是str指向该区域。最后用指向该区域。最后用free函数释放函数释放str指向的内存空间。整个程序包含指向的内存空间。整个程序包含了申请内存空间、使用内存空间、释放内存空间三个步骤，实现存储空间的动了申请内存空间、使用内存空间、释放内存空间三个步骤，实现存储空间的动态分配。态分配。n链表有五种基本操作：链表有五种基本操作：n建立建立n插入插入n删除删除n输出输出n查找查找n建立动态链表就是建立结点空间、输入各结点数建立动态链表就是建立结点空间、输入各结点数据和进行结点链接的过程，也就是在程序执行过据和进行结点链接的过程，也就是在程序执行过程中从无到有地建立起一
41、个链表。程中从无到有地建立起一个链表。n通过以下实例来说明如何建立一个动态链表。通过以下实例来说明如何建立一个动态链表。【例【例 8.12】建立一个链表存放学生数据。为简单】建立一个链表存放学生数据。为简单起见，我们假定学生数据结构中有学号和年龄两起见，我们假定学生数据结构中有学号和年龄两项。编写一个建立链表的函数项。编写一个建立链表的函数creat。#define LEN sizeof(struct stu)sruct stu /*结构结构stu定义为外部类型，方便程序中的各个函数使用定义为外部类型，方便程序中的各个函数使用*/int num;int age;struct stu*next;
42、struct stu*creat(void)/*creat函数用语动态建立一个有函数用语动态建立一个有n个结点的链表，返回与结点相同类型的指针个结点的链表，返回与结点相同类型的指针*/struct stu*p1,*p2,*head;/*head为头指针，为头指针，p2指向已建链表的最后一个结点，指向已建链表的最后一个结点，p1始终指向当前新开辟的结点始终指向当前新开辟的结点*/int n=0;p1=p2=(struct stu*)malloc(LEN);/*申请新结点，长度与申请新结点，长度与stu长度相等；同时使指针变量长度相等；同时使指针变量p1、p2指向新结点指向新结点*/scanf(“
43、%d%d”,&p1-num,&p1-page);/*输入结点的值输入结点的值*/head=NULL;while(p1-num!=0)/*输入结点的数值不为输入结点的数值不为0*/n+;if(n=1)head=p1;/*输入的结点为第一个新结点即空表，将输入的结点数据接入表头输入的结点为第一个新结点即空表，将输入的结点数据接入表头*/else p2-next=p1;/*非空表即输入的结点不是第一个结点，将输入的结点数据接到表尾非空表即输入的结点不是第一个结点，将输入的结点数据接到表尾*/p2=p1;p1=(struct stu*)malloc(LEN);/*申请下一个新结点申请下一个新结点*/s
44、canf(“%d%d”,&p1-num,&p1-page);p2-next=NULL;return(head);/*返回链表的头指针返回链表的头指针*/（1）定义链表的数据结构。）定义链表的数据结构。（2）创建一个空表。）创建一个空表。（3）利用）利用malloc()函数向系统申请分配一个结点。函数向系统申请分配一个结点。（4）若是空表，则将新结点接到表头；若是非）若是空表，则将新结点接到表头；若是非空表，则将新结点接到表尾。空表，则将新结点接到表尾。（5）判断一下是否有后续结点要接入链表，若）判断一下是否有后续结点要接入链表，若有则转到步骤（有则转到步骤（3），否则结束。），否则结束。n链表
45、的插入是指将一个结点插入到一个已有的链链表的插入是指将一个结点插入到一个已有的链表中。表中。n【例【例 8.13】以前面建立的动态链表为例，编写一】以前面建立的动态链表为例，编写一个函数，使其能够在链表中指定的位置插入一个个函数，使其能够在链表中指定的位置插入一个结点。结点。n要在一个链表的指定位置插入结点，要求链表本身必须已要在一个链表的指定位置插入结点，要求链表本身必须已按某种规律进行了排序。例如学生数据链表中，各结点的按某种规律进行了排序。例如学生数据链表中，各结点的成员项按学号由小到大顺序排列。如果要求按学号顺序插成员项按学号由小到大顺序排列。如果要求按学号顺序插入一个结点，则要将插入
46、的结点依次与链表中各结点比较，入一个结点，则要将插入的结点依次与链表中各结点比较，寻找插入位置。结点可以插在表头、表中、表尾。结点插寻找插入位置。结点可以插在表头、表中、表尾。结点插入存在以下几种情况。入存在以下几种情况。1.如果原表是空表，只需使链表的头指针如果原表是空表，只需使链表的头指针head指向被插结指向被插结点。点。2.如果被插结点值最小，则应插入第一个结点之前。将头如果被插结点值最小，则应插入第一个结点之前。将头指针指针head指向被插结点，被插结点的指针域指向原来的第指向被插结点，被插结点的指针域指向原来的第一个结点。一个结点。3.如果在链表中某位置插入，使插入位置的前一结点的
47、指如果在链表中某位置插入，使插入位置的前一结点的指针域指向被插结点，使被插结点的指针域指向插入位置的针域指向被插结点，使被插结点的指针域指向插入位置的后一个结点。后一个结点。4.如果被插结点值最大，则在表尾插入，使原表尾结点指如果被插结点值最大，则在表尾插入，使原表尾结点指针域指向被插结点，被插结点指针域置为针域指向被插结点，被插结点指针域置为NULL。struct stu*insert(struct stu*head,struct stu*p1)struct stu*p2,*p3;p2=head;if(head=NULL)/*空表插入空表插入*/head=p1;p1-next=NULL;el
48、se while(p1-nump2-num)&(p2-next!=NULL)p3=p2;p2=p2-next;/*找插入位置找插入位置*/if(p1-numnum)if(head=p2)head=p1;/*在第一结点之前插入在第一结点之前插入*/else p3-next=p1;/*在其他位置插入在其他位置插入*/p1-next=p2;else p2-next=p1;p1-next=NULL;/*在表末插入在表末插入*/return head;/*返回链表的头指针返回链表的头指针*/n定义一个指针变量定义一个指针变量p1指向被插结点。指向被插结点。n首先判断链表是否为空，为空则使首先判断链表是否
49、为空，为空则使head指向被指向被插结点。插结点。n链表若不是空，用当型循环查找插入位置。链表若不是空，用当型循环查找插入位置。n找到插入位置后判断是否在第一个结点之前插找到插入位置后判断是否在第一个结点之前插入，若是则使入，若是则使head指向被插入结点，被插结点指向被插入结点，被插结点指针域指向原第一结点；否则在其他位置插入；指针域指向原第一结点；否则在其他位置插入；若插入的结点大于表中所有结点，则在表末插若插入的结点大于表中所有结点，则在表末插入。入。n函数返回值为链表的头指针。函数返回值为链表的头指针。n链表中不再使用的数据，可以将其从表中删除并链表中不再使用的数据，可以将其从表中删除
50、并释放其所占用的空间，但注意在删除结点的过程释放其所占用的空间，但注意在删除结点的过程中不能破坏链表的结构。中不能破坏链表的结构。n【例【例 8.14】以前面建立的动态链表为例，编写一】以前面建立的动态链表为例，编写一个删除链表中指定结点的函数个删除链表中指定结点的函数delete1。n假设链表按学生的学号排列，当某结点的学号与假设链表按学生的学号排列，当某结点的学号与指定值相同时，将该结点从链表中删除。首先从指定值相同时，将该结点从链表中删除。首先从头到尾依次查找链表中给结点，并与各结点的学头到尾依次查找链表中给结点，并与各结点的学生学号做比较，若相同，则查找成功，否则，找生学号做比较，若相
