《计算机C语言教程第10章结构体和共同体.ppt》由会员分享，可在线阅读，更多相关《计算机C语言教程第10章结构体和共同体.ppt（168页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、结构体与共用体结构体与共用体第十章第十章结构体由若干成员组成，各成员可有不同的类型。结构体由若干成员组成，各成员可有不同的类型。在程序中要使用结构体类型，必须先对结构体的组在程序中要使用结构体类型，必须先对结构体的组成进行描述。例如，学生信息可用结构体描述为：成进行描述。例如，学生信息可用结构体描述为：structstudentintnum;/*学号*/charname20;/*姓名*/charsex;/*性别*/intage;/*年龄*/floatscore;/*成绩*/charaddr40;/*家庭住址*/;需要特别指出的是“structstudent”是程序设计者自己定义的类型，它与系统
2、预定义的标准类型(如int、char等)一样，可以用来定义变量，使变量具有structstudent类型。例如：structstudentst1,st220;分别定义了structstudent结构体类型的变量st1和structstudent结构体类型的数组变量st2。其中，关键字struct引入结构体类型的定义。struct之后任选的标识符是结构体类型的名字。用花括号括起来的是结构体成员说明。上例说明结构体类型structstudent有6个成员，分别命名为num、name、sex、age、score和addr。这6个成员分别表示学生的学号、姓名、性别、年龄、成绩和家庭住址，显然它们的类型
3、是不同的。结构体类型的定义形式为：struct 结构体类型名结构体类型名成员说明表列成员说明表列;其中，花括号内的内容是该结构体类型的成员说明，每个成员说明的形式为：类型名类型名 成员名成员名;实际上，凡是相关的若干数据对象都可组合成一个结构体，在一个结构体名下进行管理。例如，由日、月、年组成的结构体类型为：structdateintday;intmonth;intyear;又如，某职工信息结构体类型为：structpersoncharname20;/*姓名*/charaddress40;/*地址*/floatsalary;/*工资*/floatcost;/*扣款*/structdatehir
4、edate;/*聘任日期*/;其中，结构体类型structperson含有一个结构体类型成员hiredate。该例子说明结构体类型可以嵌套定义，即一个结构体类型中的某些成员又是其他结构体类型。但是这种嵌套不能包含自身，即不能由自己定义自己。结构体类型说明中，详细列出了一个结构体的组成情况、结构体的各成员名及其类型。结构体类型说明了一个数据结构的“模式”，但不定义“实物”，并不要求分配实际的存储空间。程序要实际使用结构体，必须定义结构体变量。编译程序在为结构体变量分配存储空间时，其中各成员的存储格式及其意义与结构体类型保持一致。10.2 结构体类型变量结构体类型变量 要定义一个结构体类型的变量，
5、可采取以下要定义一个结构体类型的变量，可采取以下3种方法。种方法。10.2.1结构体类型变量的定义1.先定义结构体类型，再定义变量如上面已定义了一个结构体类型structstudent，可以用它来定义变量。例如：structstudentstudent1,student2;定义student1和student2为structstudent类型变量，即它们具有structstudent类型的结构体变量。应当注意，将一个变量定义为标准类型(基本数据类型)与定义为结构体类型不同之处在于：后者不仅要求指定变量为结构体类型，而且要求指定为某一特定的结构体类型。例如，对structstudent，不能只指
6、定为struct型而不指定结构体名。而在定义变量为整型时，只需指定为int型即可。例如：structstudentintnum;charname20;charsex;intage;floatscorecharaddr40;student1,student2;2.在定义类型的同时定义变量在定义类型的同时定义变量：struct结构体类型名结构体类型名成员说明表列成员说明表列变量名表列变量名表列;它的作用与前面定义的相同。即定义了两个struct student类型的变量student1和student2。这种定义方法的一般形式为：3.直接定义结构体类型变量直接定义结构体类型变量其一般形式为：str
7、uct 成员说明表列成员说明表列变量名表列变量名表列;即在结构体定义时不出现结构体类型名，这种形式虽然简单，但不能在再需要时，使用所定义的结构体类型。(1)类型与变量是不同的概念，不要混同。对结构体变量来说，在定义时一般先定义一个结构体类型，然后定义变量为该类型。只能对变量赋值、存取或运算，而不能对一个类型赋值、存取或运算。在编译时，对类型是不分配存储空间的，只对变量分配存储空间。关于结构体类型，有几点需要说明：关于结构体类型，有几点需要说明：(2)对结构体中的成员，可以单独使用，它的作用与地位相当于普通变量。(3)成员也可以是一个结构体变量。例如：structdateintmonth;int
8、day;intyear;structmemberintnum;charname20;charsex;intage;structdatebirthday;/*成员变量是一个结构体变量*/charaddr40;stu1,stu2;(4)成员名可以与程序中的其他变量名相同，两者不代表同一对象。例如，程序中可以另定义一个变量num，它与structmember中的num是两回事，互不干扰。先定义一个struetdate结构体类型，它包括3个成员：month、day、year，分别代表月、日、年。然后在定义struetmember结构体类型时，成员birthday的类型定义为struetdate类型。已
9、定义的类型structdate与其他类型(如int、char)一样可以用来定义成员的类型。10.2.2结构体变量的使用引用一个结构体变量有两种方式：通过结构体变量名和通过指向结构体的指针变量。与之对应的，引用结构体成员的标记形式也有两种，分别用运算符“”和“”来标记。(1)由结构体变量名引用其成员的标记形式为：结构体变量名结构体变量名.成员名成员名例如，stu1.num表示引用结构体变量stu1中的num成员，因该成员的类型为int型的，所以可以对它施行任何int型变量可以施行的运算。例如：stu1.num20312;(2)由指向结构体的指针变量引用结构体成员的标记形式为：指针变量名指针变量名
10、-成员名成员名例如，如下变量定义：structnodefloatx,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.1通过指向结构体的指针引用结构体上述例子说明结构体的成员可以像普通变量一样使用。根据其类型决定其所有合法的运算。如果结构体成员本身又是结构体类型的，则可继续使用
11、成员运算符取结构体成员的结构体成员，逐级向下，引用最低一级的成员。程序能对最低一级的成员进行赋值或存取;例如，对stu1某些成员的访问：stu1.birthday.day=23;stu1.birthday.month=8;stu1.birthday.year=2003;在早期的C语言中，程序只能对结构体变量(包括结构体变量的结构体成员)取地址运算，不允许对结构体进行赋值运算。ANSIC已经取消了这个限制，允许结构体值赋给相同类型的结构体变量。程序也能对结构体的最低一级的成员进行其他运算，包括取地址运算，引用成员的地址。例如：scanf(”%”,&stu1.age);10.2.3结构体变量的初始
12、化结构体变量和其他变量一样，可以在定义变量的同时进行初始化。1.对外部存储类型的结构体变量进行初始化例10.1 分析下列程序的输出结果。#includestructstudentlongnum;charname20;charsex;charaddr40;a=3021103,”JiangLinpad”,M,”123ShaoshanRoad”;main()printf(”No:%ldnName:%snSex:%cnAddress:%sn”,a.num,a.name,a.sex,a.addr);程序运行结果如下：No:3021103Name:JiangLinpanSex;MAddress:123Sh
13、aoshanRoad2.在函数内部的结构体变量进行初始化上面例子的定义部分可以放到main函数中。程序如下：main()staticstructstudentlonghum;charname20;charsex;charaddr40;a=3021103,”JiangLinpan”,M,”123ShaoshanRoad”;printf(”No:%ldnName:%snSex:%cnAddress:%sn”,a.num,a.name,a.sex,a.addr);程序运行结果与上面例子程序相同。注意,对自动结构体变量不能在定义时赋初值,只能在函数执行时用赋值语句对各成员分别赋值。10.2.4结构体变
14、量的输入和输出C语言不能把一个结构体变量作为一个整体进行输入或输出,应该按成员变量输入输出。例如,若有一个结构体变量：structcharname12;charaddr18;longnum;stud=”WangDawei”,”125BeijingRoad”,3021118;变量stud在内存中存储情况如图10.2所示。是按成员变量存放的。W a n gD a w e i 01 2 5B e i j i n gR o a d 03021118name12addr18 图10.2结构体变量在内存中的存储情况为两个字符串数据和一个长整型数据,因此输出stud变量,应该使用如下方式：printf(”%
15、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型,故应当用&stud.num。当然也可以用gets函数和puts函数输入和输出一个结构体变量中的字符数组成员。例如：gets(stud.name);puts(stud.name);gets函数输入一个字符串给stud.name,puts函数输出stud
16、.name数组中的字符串。10.3 10.3 结构体类型数组结构体类型数组一个结构体变量中可以存放一组数据(如一个学生的学号、姓名、成绩等数据)。如果有10个学生的数据需要参加运算和处理,显然应该用数组,这就是结构体数组。结构体数组与以前介绍过的数值型数组不同之处在于每个数组元素都是一个结构体类型的数据,它们都分别包括各个成员项。10.3.1结构体类型数组的定义与定义结构体变量的方法一样,在结构体变量名之后指定元素个数,就能定义结构体数组。例如：structstudentstudents30;structpersonemployees100;structcharname20;intnum;fl
17、oatprice;floatquantity;parts200;以上定义了一个数组students,它有30个元素,每个元素的类型为structstudent的结构体类型。定义数组employees,有100个元素,每个元素是structperson结构体类型。定义数组parts,有200个元素,每个元素也是一个结构体类型。它们都是结构体数组,分别用于表示一个班级的学生、一个部门的职工、一个仓库的产品。如同元素为标准数据类型的数组一样,结构体数组各元素在内存中也按顺序存放,也可初始化,对结构体数组元素的访问也要利用元素的下标。特别地,访问结构体数组元素的成员的标记方法为：例如,访问parts数
18、组元素的成员：parts10.price=37.5;scanf(”%s”,parts3.name);结构体数组名结构体数组名元素下标元素下标结构体成员名结构体成员名10.3.2结构体类型数组的初始化在对结构体数组初始化时,要将每个元素的数据分别用花括号括起来。例如：structstudentcharname20;longnum;intage;charsex;floatscore;students5;”ZhuDongfen”,3021101,18,M,93,”ZhangFachong”,3021102,19,M,90.5,”WangPeng”,3021103,16,M,85,”ZhanHong”
19、,3021104,16,F,95,”LiLinggou”,3021105,20,F,67;这样,在编译时将一个花括号中的数据赋给一个元素,即将第一个花括弧中的数据送给students0,第二个花括弧内的数据送给students1,。如果赋初值的数据组的个数与所定义的数组元素相等,则数组元素个数可以省略不写。这和前面有关章节介绍的数组初始化相类似。此时系统会根据初始化时提供的数据组的个数自动确定数组的大小。如果提供的初始化数据组的个数少于数组元素的个数,则方括弧内的元素个数不能省略,例如：structstudentstudents3:,;只对前3个元素赋初值,其他元素未赋初值,系统将对数值型成员
20、赋以零,对字符型数据赋以“空”串即“0”。10.3.3结构体数组的使用一个结构体数组的元素相当于一个结构体变量。引用结构体数组元素有如下规则：(1)引用某一元素的一个成员。例如：studentsi.num这是序号为i的数组元素中的num成员。如果数组已如上初始化,且i=2,则相当于students2.num,其值为3021103。(2)可以将一个结构体数组元素赋给同一结构体类型数组中的另一个元素,或赋给同一类型的变量。例如：structstudentstudents3,student1;现在定义了一个结构体数组students,它有3个元素,又定义了一个结构体变量student1,则下面的赋值
21、合法。student1=students0;students2=students1;students1=student1,(3)不能把结构体数组元素作为一个整体直接进行输入或输出,只能以单个成员对象进行输入输出。例如：scanf(”%s”,students0.name);printff(”%ld”,&students0.num);10.4 10.4 结构体与函数结构体与函数10.4.1结构体变量作函数参数 旧的C标准不允许用结构体变量作函数参数,只允许指向结构体变量的指针作函数参数,即传递结构体变量的首地址。新的标准以及许多C编译都允许用结构体变量作为函数参数,即直接将实参结构体变量的各个成员
22、的值全部传递给形参的结构体变量。当然,实参和形参的结构体变量类型应当完全一致。例10.2输入三个学生的信息并输出，其中输出的功能用一函数实现。#include#includestructstud_typecharname20;longnum;intage;charsex;main()voidlist(structstud_typestudent);structstud_typestudent3,*p;inti;for(i=0,p=student;iname,&p-num,&p-age,&p-sex);for(i=0;inum,p-name,p-sex,p-score指向结构体变量的指针作为函数
23、参数上一节介绍的用结构体变量作为函数参数，这是ANSIC新标准的扩充功能。在过去的C版本中不能这样用，而是通过指针来传递结构体变量的地址给形参，再通过形参指针变量引用结构体变量中成员的值。例10.3 有一结构体变量stu，内含学生学号、姓名和3门课的成绩。要求在main函数中给变量赋值，在另一函数print中将它们打印输出。#include#includestructstudentlongnum;charname20;floatscore3;main()voidprint(structstudent*);structstudentstu;stu.num=3021210;strcpy(stu.n
24、ame,”LiDong”);stu.score0=67.5;stu.score1=89;stu.score2=78.6;print(&stu);voidprint(structstudent*p)printf(”%ldn%sn%fn%fn%fn”,p-num,p-name,p-score0,p-score1,p-score2);printf(”n”);程序运行结果如下：3021210LiDong67.50000089.00000078.599998structstudent被定义为外部类型，这样同一文件中的各个函数都可以用它来定义变量的类型。main函数中的stu变量定义为structstud
25、ent类型，printf函数中的形参p被定义为指向structstudent类型数据的指针变量。在main函数中对stu的各成员赋值。注意在调用print函数时，用&stu作实参，&stu是结构体变量stu的地址。在调用函数时将该地址传递给形参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);输入时用下面形式输入：
26、3021210LiDong67.58978.6注意，输入项表列中stu.name前没有“&”符号，因为stu.name是字符数组名本身代表地址，不应写成&stu.name。ANSIC允许用整个结构体作为函数的参数传递，但是必须保证实参与形参的类型相同。上例中的main函数中的最后一行调用printf函数，也可以改用：print(stu);即实参改用结构体变量(而不是指针)。同时print函数也应相应改为：voidprint(structstudentstud)printf(”%ldn%sn%fn%fn%fn”,stu.num,stu.name,stu.score0,stu.score1,slu
27、.score2);printf(”n”);把一个完整的结构体变量作为参数传递，虽然合法，但是要将全部成员值一个一个传递，费时间又费空间，开销大。如果结构体类型中的成员很多，或者有一些成员是数组，则程序运行效率会大大降低。在这种情况下，用指针做函数参数比较好，能提高运行效率。10.4.3函数的返回值为结构体类型函数的返回值可以是结构体类型。例如，定义了结构体数组：structstudentstud100;数据输入可由如下形式的语句实现：for(i=0;i100;i+)studi=input();函数input()的功能是输入一个结构体数据，并将输入结构体数据作为返回值，返回给第i个学生记录，实现
28、第i个学生的数据输入。函数定义如下：structstudentinput()/*输入一个学生的数据*/inti;structstudentstud;scanf(”%ld”,&stud.no);/*输入学号*/gets(stud.name);/*输入学生姓名*/for(i=0;i结构体成员名结构体成员名例如,通过pd引用结构体变量date3的day成员,写成pd-day,引用date3的month,写在pd-month等。“*指针变量”表示指针变量所指对象,所以通过指向结构体的指针变量引用结构体成员也可写成以下形式：(*指针变量指针变量)结构体成员名结构体成员名这里圆括号是必须的,因为运算符“*
29、”的优先级低于运算符“.”。从表面上看,*pd.day等价于*(pd.day),但这两种书写形式都是错误的。采用这种标记方法,通过pd引用date3的成员可写成(*pd).day、(*pd).month、(*pd).year。但是很少场合采用这种标记方法,习惯都采用运算符“-”来标记。例10.4 写出下列程序的执行结果。#Include#includemain()structstudentlongnum;charname20;charsex;floatscore;structstudentstu1,*p;p=&stu1;stu1.num=3021118;strcpy(stu1.name,”Li
30、Lin”);stu1.sexM;stu1.score=91.5;printf(”No:%ldnName:%snSex:%cnScore:%fn”,stu1.num,stu1.name,stu1.sex,stu1.score);printf(”No:%ldnName:%snSex:%cnScore:%fn”,(*p).num,(*p).name,(*p).sex,(*p).score);在主函数中定义了structstudent类型,然后定义一个structstudent类型的变量stu1。同时又定义了一个指针变量p,它指向structstudent结构体类型。在函数的执行部分,将stu1的起始
31、地址赋给指针变量p,也就是使p指向stu1,然后对stu1中的成员num,其余类推。第二个printf函数也是用来输出stu1的各成员的值,但使用的是(*p).num这样的形式。程序运行结果如下：No:3021118Name:LiLinSex:MScore:91.500000No:302lll8Name:LiLinSex:MScore:91.500000可见两个printf函数输出的结果是相同的。上面程序中最后一个printf函数中的输出项列表可改为：p-num,p-name,p-sex,p-score2指向结构体数组元素的指针一个指针变量可以指向一个结构体数组元素,也就是将该结构体数组的数组
32、元素地址赋给此指针变量。例如：structinta;floatb;arr3,*p;p=arr;此时使p指向arr数组的第一个元素,“p=arr;”等价于“p=&arr0”。若执行“p+;”则此时指针变量p此时指向arr1,指针指向关系如图10.3所示。Pp+arr0arr1arr2图10.3指向结构体数组元素的指针10.5.2链表到目前为止,程序中的变量都是通过定义引入的,这类变量在其存在期间,它固有的数据结构是不能改变的。本节将介绍系统程序中经常使用的动态数据结构,其中包括的变量不是通过变量定义建立的,而由程序根据需要向系统申请获得。动态数据结构由一组数据对象组成,其中数据对象之间具有某种特
33、定的关系。动态数据结构最显著的特点是它包含的数据对象个数及其相互关系可以按需要改变。经常遇到的动态数据结构有链表、树、图等,限于程序设计初学者,在此只介绍其中简单的单向链表动态数据结构。链表概述链表是最简单也是最常用的一种动态数据结构。它是对动态获得的内存进行组织的一种结构。我们知道,用数组存放数据时,必须事先定义固定的长度(即数组元素个数)。比如,有的班级有50人,而有的班只有30人,如果要用同一个数组先后存放不同班级的学生数据,则必须定义长度为50的数组。如果事先难以确定一个班的最多人数,则必须把数组定义得足够大,以能存放任何班级的学生数据。显然这将会浪费内存空间。链表则没有这种缺限,它根
34、据需要开辟内存单元。图10.4表示最简单的一种链表(单向链表)的结构。链表有一个头指针变量,图中以head表示,它存放一个地址。该地址指向一个链表元素。链表中每一个元素称为结点,每个结点都应包括两部分：一是用户需要用的实际数据,二是下一个结点的地址。可以看出,head指向第一个结点,第一个结点又指向第二个结点,一直到最后一个结点,该结点不再指向其他结点,它称为表尾,它的地址部分放一个NULL(表示“空地址”)。链表到此结束。head2101图10.4链表结构示意图 由图10.4所示,一个结点的后继结点位置由结点所包含的指针成员所指,链表中各结点在内存中的存放位置是可以任意的。如果寻找链表中的某
35、一个结点,必须从链表头指针所指的第一个结点开始,顺序查找。另外,图10.4所示的链表结构是单向的,即每个结点只知道它的后继结点位置,而不能知道它的前驱结点。在某些应用中,要求链表的每个结点都能方便地知道它的前驱结点和后继结点,这种链表的表示应设有两个指针成员,分别指向它的前驱和后继结点,这种链表称为双向链表。为适应不同问题的特定要求,链表结构也有多种变形。head2101链表与数组的主要区别是:(1)数组的元素个数是固定的,而组成链表的结点个数可按需要增减;(2)数组元素的存贮单元在数组定义时分配,链表结点的存贮单元在程序执行时动态向系统申请;(3)数组中的元素顺序关系由元素在数组中的位置(即
36、下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。对于不是固定长度的列表,用可能最大长度的数组来描述,会浪费许多内存空间。(4)对于元素的插入、删除操作非常频繁的列表处理场合,用数组表示列表也是不适宜的。若用链表实现,会使程序结构清晰,处理的方法也较为简便。例如在一个列表中间要插入一个新元素,如用数组表示列表,为完成插入工作,插入处之后的全部元素必须向后移动一个位置,空出的位置用于存储新元素。对于在一个列表中删除一个元素情况,为保持取组中元素相对位置连续递增,删除处之后的元素都得向前移一个位置。如用链表实现列表,链表结点的插入或删除操作不再需要移动结点,只需改变相关的结点中的后继结点指
37、针的值即可,与结点的实际存储位置无关。操作细节见有关链表插入和删除操作的程序例子。链表的结点是结构体变量,它包含若干成员,其中有些成员可以是任何类型,如标准类型、数组类型、结构体类型等;另一些成员是指针类型,是用来存放与之相连的结点的地址。单向链表的结点只包含一个这样的指针成员。下面是一个单向链表结点的类型说明：structstudentlongnum;floatscore;structstudent*next;其中next是成员名,它是指针类型的,它指向structstudent类型数据(这就是next所在的结构体类型)。用这种方法可以建立链表,链表的每一个节点都是structstudent
38、类型,它的next成员存放下一节点的地址。这种在结构体类型的定义中引用类型名定义自己的成员的方法只允许定义指针时使用。10.5.2.2内存动态管理函数前面已经提及,链表结点的存储空间是程序根据需要向系统申请的。C系统的函数库中提供了程序动态申请和释放内存存储块的库函数,下面分别介绍。1.malloc函数它的作用是在内存开辟指定大小的存储空间,并将此存储空间的起始地址作为函数值带回。malloc函数的原型为：void*malloc(unsignedintsize)它的形参size为无符号整型。函数值为指针(地址),这个指针是指向void类型的,也就是不规定指向任何具体的类型。如果想将这个指针值赋
39、给其他类型的指针变量,应当进行显式的转换(强制类型转换)。例如：malloc(8)用来开辟一个长度为8个字节的内存空间,如果系统分配的此段空间的起始地址为81268,则malloc(8)的函数返回值为81268。如果内存缺乏足够大的空间进行分配,则malloc函数值为“空指针”,即地址为0。2.calloc函数其函数原型为：vold*calloc(unsignedintnum,unsignedintsize)它有两个形参num和size。其作用是分配num个大小为size字节的空间。例如用calloc(20,30)可以开辟20个(每个大小为30字节)的空间,即总长为600字节。此函数返回值为该
40、空间的首地址。成员也可以是一个结构体变量。3.free函数free函数的原型为：voidfree(void*ptr)其作用是将指针变量ptr指向的存储空间释放,即交还给系统,系统可以另行分配作它用。应当强调,ptr值不能是任意的地址项,而只能是由在程序中执行过的malloc或calloc函数所返回的地址。如果随便写：free(100)是不行的,系统怎么知道释放多大的存储空间呢?下面这样用是可以的：p=(long*)malloc(18);free(p);free函数它把原先开辟的18个字节的空间释放,虽然p是指向long型的,但可以传给指向void型的指针变量ptr,系统会使其自动转换。free
41、函数无返回值。10.5.2.3链表的基本操作链表的基本操作包括建立链表、链表的插入、删除、输出和查找等。1.建立链表所谓建立链表是指一个一个地输入各结点数据,并建立起各结点前后相链的关系。建立单向链表的方法有插表头(先进后出)方法和链表尾(先进先出)方法两种。插表头方法的特点是：新产生的结点作为新的表头插入链表;链表尾方法的特点是：新产生的结点接到链表的表尾。图10.5a表示用插表头方法建立链表,图10.5b表示用链表尾方法建立链表。从图10.5a可知,用插表头的方法,链表只需要用head指针指示,产生的新结点的地址存人指针变量p,使用赋值语句：p-next=head;将head指示的链表接在
42、新结点之后;用head=p;使头指针指向新结点。插表头算法抽象描述如下：(1)head=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;/*新结点作为表尾*
43、/(3)如果head为NULL则head=p;/*新结点作为表头,这时链表只有一个结点*/否则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,它们都
44、指向结构体类型数据。(2)head和p2的初始值为NULL(即等于0),p2作为表尾指针。(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,此新结点不被连接到链表中,循环终止。建立链表的
45、函数如下：#delfinNULL0#defineLENsizeof(structstudent)structstudentlongnum;floatscore;structstudent*next;intn;structstudent*creat()/*此函数带回一个指向链表头的指针*/structstudent*head,*p1,*p2;n=0;head=NULL;pl=(structstudent)malloc(LEN);/*创建第一个结点*/scanf(“%1d,%f”,&p1-num,&pl-score);p1-next=NULL;while(p1-num!=0)/*应该将结点加入链表
46、*/+n;if(n=1)head=pl;/*是第一个结点,作表头*/elsep2-next=pl;/*不是第一个结点,作表尾*/p2=pl;p1=(structstudent*)malloc(LEN);/*开辟下一个结点*/scanf(“%ld,%f”,&p1-num,&p1-score);p1-next=NULL;free(p1);/*释放最后一个结点所占的内存*/return(head);/*返回链表的头指针*/关于函数的说明：(1)第一行为#define命令行,令NULL代表0,用它表示“空地址”。第二行令LEN代表structstudent结构体类型数据的长度,sizeof是“求字节数
47、运算符”。(2)creat函数是指针类型,即此函数带回一个指针值,它指向一个structstudent类型数据。实际上treat函数带回一个链表起始地址。(3)在一般系统中,malloc带回的是指向字符型数据的指针。而p1、p2是指向structstudent类型数据的指针变量,两者所指的是不同类型的数据。因此必须用强制类型转换的方法使之类型一致,在malloc(LEN)之前加了“(structstudent*)”,它的作用是使malloc返回的指针转换为指向structstudent类型数据的指针。注意“*”号不可省略,否则变成转换成structstudent类型了,而不是指针类型了。(4)
48、函数返回的是head的值,也就是链表的头地址。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
49、和p2-next=p0顺序颠倒呢？举个简单的例子，我们在放风筝的时候，发现手中的线太短了，想接上一段，如果我们不先连接好与风筝相连的一端，风筝就会随风飘走。我们在插入节点的时候，必须先让待插节点指向后续节点，不然我们在段开p1，p2之间的“线索”时，后续节点就不知道跑到什么地方去了。两个步骤如图10.6所示。链表的插入操作算法描述如下：仍然以例10.5建立一个有n名学生数据的单向链表为例。用指针变量p0指向待插入的结点,设已有的链表各结点是按学号由小到大顺序排序的。最初p1=head找插入点步骤如下：当p0-numpl-num且p1-next!=NULLp2=p1；p1=p1-next;插入结
50、点操作如下：如果p1=head则结点作为表头插入否则插入在p2所指的结点之后;headP2P1P0headP2P1图10.6链表插入操作插入结点的函数insert如下：structstudent*insert(structstudent*head,structstudent*stud)structstudent*p0,*pl,*p2;p1=head;/*p1指向第一个结点*/p0=stud;/*p0指向要插入的结点*/if(head=NULL)/*原来是空表*/head=p0;p0-next=NULL;/*使p0指向的结点作为链表第一个结点*/elsewhile(p0-nump1-num)&(