掌握结构数据类型、结构变量和结构指针的定义-结构成分

1本章学习的目标是：1、掌握结构数据类型、结构变量和结构指针的定义，结构成分的引用方法；2、掌握结构数组的定义和使用方法；3、掌握编写有结构形参、结构指针形参，以及返回结构的函数的方法；4、掌握链接存储线性表的概念和基本操作；5、了解联合、位域、枚举数据类型的概念和使用方法；6、掌握类型定义和变量定义的方法。第7章结构和链表

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第1页。27.1结构类型和结构变量7.2结构数组7.3结构与函数7.4链表7.5联合7.6位域7.7枚举7.8类型定义7.9变量定义掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第2页。3基本类型：如整型、实型、字符型等。构造类型：数组，每个元素都是属于同一个类型。结构类型：不同的数据类型组成一个整体方便使用。例如：一个学生数据实体可能有以下多项信息

学号、姓名、性别、家庭地址

intchar

charchar说明：这类实体的数据因所包含的成员类型不同，不能用单个数组来表示，也不便将它们的成员分拆成多个独立的简单变量，因为这样会失去实体的整体性。

7.1结构类型和结构变量掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第3页。4结构类型形式：

struct结构类型名{

成员说明表

};其中关键字“struct”：引出结构类型的定义。结构类型名：整个结构类型的名称。成员说明表：指明组成此种结构类型的全部成员。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第4页。5学生数据结构类型为：

structstudent{intnumber; /*学号*/charname[20];/*姓名，少于20个字符*/charsex; /*性别*/charaddress[40]; /*家庭地址*/};上述代码定义结构类型有number、name、sex和address共4个成员，各成员的数据类型分别为整型、字符数组、字符型和字符数组。结构类型例掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第5页。6当结构类型中的某个成员又是另一个结构类型时，这种结构类型是一种嵌套的结构类型。例如，给上述学生信息增加出生日期，并将出生日期定义为一种包含日、月、年3项信息的结构类型，则更完整的学生信息类型就被定义成嵌套的结构类型。

structDate /*说明一个日期*/{intday; /*日*/intmonth; /*月*/intyear; /*年*/};structstudent{intnumber; /*学号*/charname[20]; /*姓名*/charsex; /*性别*/Datebirthday;/*采用C++句法，birthday的类型是结构类型Date，如果采用C句法，则在Date之前用struct引导*/charaddress[40];/*家庭地址*/};

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第6页。7上述代码先定义Date结构类型，由day、month和year三个成员组成。然后在定义student结构类型时，将成员birthday指定为Date结构类型，使类型student是一个嵌套的结构类型。在实际应用中，为表示复杂的数据结构，常常用到这种嵌套的结构类型。在结构类型中有数组和结构成员，数组的元素又是结构，结构中又有结构，嵌套层次会有许多层。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第7页。8结构变量在结构类型定义中，详细列出了结构类型所包含的每个成员的名称及其类型。实际上，结构类型定义只是表明一类实体其数据属性的“模式”，并不定义一个特定的数据实体，因此不要求分配存储单元。程序如果要实际使用结构类型所描述的数据信息，就必须定义结构变量。结构变量要占用存储单元，能存放如结构类型所描述的具体数据。对结构类型和结构变量，我们可以简单地理解为，结构类型是表示数据框架的描述文本，结构变量才能存放实际数据。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第8页。9一、先定义结构类型，再定义结构变量形式：struct结构类型名结构变量表；//C句法形式：结构类型名结构变量表；//C++句法例如：利用前面已定义的结构类型structstudent代码：

structstudentst1,st2;//C句法代码：

studentst1,st2;//C＋＋句法表示：定义了两个结构变量st1和st2，它的的元素类型为structstudent结构类型。说明：结构变量st1和st2将具有structstudent类型的结构。结构变量的定义掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第9页。10变量名numbernamesexbirthdayaddressdaymonthyearst110001ZhangpingM2011198515NanjingRdst210002LiyingF08041986100BeijinRd图7.1结构变量st1和st2占用内存情况掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第10页。11二、在定义结构类型的同时定义结构变量结构变量的定义例如：structstuSType{intnumber; /*学号*/charname[20];/*姓名*/intscore; /*成绩*/}stuS;形式：struct结构类型名{

成员说明表

}结构变量表;掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第11页。12在定义结构变量时，同时给它置初值，称为结构变量初始化。

structPoint{/*说明绘图程序的坐标类型*/

intx;inty;}p1={20，50},p2; /*p1的x值为20，p1的y值为50*/也可以在定义结构类型与声明结构变量分开的情况下，在声明结构变量时进行初始化。例如，利用已定义的结构类型Point，结合声明结构变量进行初始化：Pointp3={10,40}，p4={20,50};//采用C++句法定义变量

结构变量初始化掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第12页。131.要注意结构类型名和结构变量名的区别。不能对结构类型名进行赋值、存取或运算，因为类型不占用存储空间；而结构变量会占用存储空间，定义时可以赋初值，定义后可引用。2.结构变量初始化的时间。静态结构变量初始化遵守其它静态变量初始化相同的规则。即静态的和全局的结构变量初始化在程序执行之前完成，静态的结构变量未指定初值时，结构变量的每个成员的值自动置二进制代码为全0的值。局部结构变量初始化是程序控制每次进入它所属辖域时创建并初始化，未指定初值的局部结构变量其初值是不确定的。结构类型和结构变量－说明掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第13页。143.可以定义指向结构的指针变量（结构指针变量简称结构指针）。设有结构变量s和能指向该结构的指针变量p，当把s所占据的存储块的开始地址赋值给p时(p=&s)，就说结构指针p指向结构变量s。定义结构指针的方法与定义一般指针变量一样，当类型区分符是结构类型时，所定义的指针变量即为结构指针。例如，

Date*pd,date3;//采用C++句法定义变量

pd=&date3;定义结构指针pd和结构变量date3，并使结构指针pd指向结构变量date3，即结构指针pd的内容为结构变量date3所占据的存储块的首地址。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第14页。15用结构变量名直接引用结构变量和指向结构变量的指针间接引用结构变量。程序引用结构变量有以下多种应用。●相同类型的结构变量相互赋值●让结构指针指向结构变量●将结构变量作为实参调用带结构形参的函数结构变量的引用掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第15页。16例如：

studentst3={10005,“Zhangxiowen”,‘F’,{20,11,1985},“15NanjingRd”},st4;把一个结构变量赋值给同类型的另一个结构变量。例如

st4=st3; /*将结构变量st3整体赋值给结构变量st4*/假设前面已定义了一个结构类型student和结构变量st1，可以将结构变量st1所占据的存储块的首地址赋值给结构指针变量。例如student*stp=&st1;/*定义指向结构变量st1的结构指针p1*/上述代码定义结构指针变量stp，并让它指向结构变量st1。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第16页。17引用结构成员

引用结构成员有以下3种方法。●使用结构变量和成员运算符●使用结构指针和指针运算符●使用结构指针和成员运算符使用结构变量和成员运算符引用结构成员：结构变量名.成员名在这里，点符号“.”是结构的成员运算符，是优先级最高运算符之一。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第17页。18用代码stuS.name直接引用stuS结构变量的name成员。引用结构变量的成员对该成员进行输入输出、赋值、运算等操作。例如:printf(”学号：%d姓名：%s成绩：%d\n”,stuS.number,stuS.name,stuS.score);输出学生stuS的信息。代码：stuS.score+=5;strcpy(stuS.name,“Liming”);更新学生stuS的成绩，更正学生stuS的姓名。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第18页。19使用结构指针和指针运算符引用结构成员：指针变量名->成员名其中双字符“->”是指针运算符，它是由减号“-”和大于号“>”两个字符组成（请注意中间不能有空格符），其优先级与成员运算符“.”一样，也是最高优先级的运算符。可以使用结构指针间接引用stuS结构变量的成员。例如stuSType*sp=&stuS; /*定义指向结构变量stuS的结构指针sp*/sp->number=10002;sp->score=95;掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第19页。20使用结构指针和成员运算符引用结构成员：(*指针变量名).成员名其中圆括号是必要的。若省略，由于成员运算符“.”优先级高于“*”，将会导致编译错误。例如stuSType*sp=&stuS;/*采用C++句法，定义结构指针sp指向结构stuS*/(*sp).score=95;/*与代码sp->score=95;等价*/

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第20页。21(1)不能直接对结构变量进行输入或输出，只允许对结构变量的成员变量进行输入和输出。以下分别是错误和正确的代码：

printf(”%s”,st1); /*错误，st1是结构变量不能直接输出*/printf(”%s”,);/*正确，仅输出st1变量的name成员*/(2)如果结构中的成员本身也是一个结构类型，在引用该成员的成员时需使用多个成员运算符“.”，将嵌套的结构成员一级一级地连续指定。例如，想引用早先定义的结构变量st1中成员birthday成员year，正确的写法是：

st1.birthday.year掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第21页。22【例7.1】利用结构变量，输入3个学生的姓名、语文成绩和数学成绩，然后计算每个学生的平均成绩并输出。#include<stdio.h>structstuScore{ charname[20]; intchinese; intmath;};掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第22页。23voidmain(){floataver1,aver2,aver3;stuScorest1,st2,st3; /*采用C++句法，定义3个结构变量*/printf(”请输入3位学生的姓名、语文成绩、数学成绩\n”);scanf(”%s%d%d”,,&st1.chinese,&st1.math);scanf(”%s%d%d”,,&st2.chinese,&st2.math);scanf(”%s%d%d”,,&st3.chinese,&st3.math);aver1=(st1.chinese+st1.math)/2.0; /*计算平均成绩*/aver2=(st2.chinese+st2.math)/2.0;aver3=(st3.chinese+st3.math)/2.0;printf("姓名\t语文\t数学\t平均成绩\n");printf("%s\t%4d\t%4d\t%6.2f\n”,,st1.chinese,st1.math,aver1);printf("%s\t%4d\t%4d\t%6.2f\n”,,st2.chinese,st2.math,aver2);printf("%s\t%4d\t%4d\t%6.2f\n”,,st3.chinese,st3.math,aver3);}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第23页。24通常用结构（变量）描述个体，用数组描述个体的集合。当数组的元素是结构时，这种数组就称为结构数组。例如：用结构变量st1描述某学生的有关信息，而用结构数组可表示一个班的学生。

structstudent{intnum;charname[20];charsex;}stu[100];

7.2结构数组掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第24页。25结构数组的定义(1)先定义结构类型，再定义结构数组以下代码先定义结构类型stuScore，然后用这个结构类型定义结构数组：structstuScore{ charname[20]; intchinese; intmath;};stuScorest[3]; /*采用C++句法，定义有3个元素的结构数组*/掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第25页。26(2)在定义结构类型的同时定义结构数组以下代码实现与前面代码同样的效果，在定义结构类型stuScore同时定义结构数组：structstuScore{ charname[20]; intchinese; intmath;}st[3];掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第26页。27与结构变量初始化相仿，在定义结构数组时，也可给结构数组赋初值。例如：structstuScore{ charname[20]; intchinese; intmath;}st[3]={{”Zhang”,80,85},{”Li”,85,90},{”Wang”,90,70}};nameChinesemathst[0]Zhang8085st[1]Li8590st[2]Wang9070图7.2结构数组st的逻辑结构掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第27页。28结构数组的引用

(1)使用结构数组元素和成员运算符使用结构数组元素和成员运算符引用结构数组元素成员的一般形式为：结构数组名[元素下标].结构成员名例如：printf(”%s”,st[0].name);/*输出第1个学生的姓名，即Zhang*/掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第28页。29(2)使用结构指针和指针运算符使用结构指针和指针运算符引用结构数组元素成员的一般形式为：指针变量名->成员名例如：stuScore*sp=st; /*定义结构指针sp,指向结构数组st首元素*/printf(”%s\n”,sp->name);/*输出第1个学生姓名，Zhang*/sp++; /*结构指针指向下一个元素*/printf(”%s\n”,sp->name);/*输出第2个学生姓名，Li*/掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第29页。30(3)使用结构指针和成员运算符使用结构指针和成员运算符引用结构数组元素成员的一般形式为：(*指针变量名).成员名例如：stuScore*spt=st;/*定义stuScore结构指针spt,指向结构数组st首元素*/printf(”%s\n”,(*spt).name);/*输出学生st[0]姓名，Zhang*/spt++;/*结构指针指向下一个元素，指向st[1]*/printf(”%s\n”,spt->name);/*输出学生st[1]姓名，Li*/掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第30页。31【例7.2】利用结构数组，输入3个学生的姓名、语文成绩和数学成绩，然后计算每个学生的平均成绩并输出（即用结构数组替换例7.1中的结构变量）。#include<stdio.h>structstuScore{ charname[20]; intchinese; intmath;};掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第31页。32voidmain(){inti;floataver[3];stuScorest[3];/*定义结构数组，含3个元素*/printf(”请输入3位学生的姓名、语文成绩、数学成绩\n”);for(i=0;i<3;i++)scanf(”%s%d%d”,st[i].name,&st[i].chinese,&st[i].math);printf("姓名\t语文\t数学\t平均成绩\n");for(i=0;i<3;i++){aver[i]=(st[i].chinese+st[i].math)/2.0;/*计算平均成绩*/printf("%s\t%4d\t%4d\t%6.2f\n”,st[i].name,st[i].chinese,st[i].math,aver[i]);}}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第32页。33函数的形参可以是基本类型变量、指针、数组，也允许是结构。将一个结构传递给函数有三种方式：传递单个成员、传递整个结构、传递指向结构的指针。传递单个成员或整个结构给函数在C中认为是值调用，即在被调用的函数中尽管修改了形参的值，但不会改变调用函数时提供的实参变量的值。

7.3结构和函数掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第33页。34【例7.3】日期转换程序，根据输入的年月日，输出是该年中的第几天。#include<stdio.h>intdayTable[][12]={{31,28,31,30,31,30,31,31,30,31,30,31},/*平年*/ {31,29,31,30,31,30,31,31,30,31,30,31}};/*闰年*/structDate /*定义一个Date结构类型*/{intday;intmonth;intyear;intyearDay;}date;/*定义一个Date结构类型的结构变量*/

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第34页。35intdayofYear(intd,intm,inty)/*计算年中第几天函数*/{inti,leap,day=d;leap=(y%4==0&&y%100)||y%400==0;/*是否闰年*/for(i=0;i<m-1;i++)day+=dayTable[leap][i];returnday; /*返回计算的结果*/}voidmain(){intleap,days;printf("\tDateConversionProgram\n");printf("Year=");scanf("%d”,&date.year); /*输入年份*/掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第35页。36

for(;;) /*输入月份，并检查是否在1～12之间*/{printf("Month=");scanf("%d”,&date.month);if(date.month>=1&&date.month<=12)break;printf("输入的月份必须在1到12之间\n");}/*leap=1是闰年，leap=0不是闰年*/leap=(date.year%4==0&&date.year%100)||date.year%400==0;days=dayTable[leap][date.month-1];for(;;) /*输入日期，并检查是否输入正确*/{printf("Day=");scanf("%d”,&date.day);if(date.day>=1&&date.day<=days)break;printf("输入的天必须在1到%d之间\n",days);}/*调用dateofYear函数，实参为结构date的3个成员*/date.yearDay=dayofYear(date.day,date.month,date.year);printf("Thedaysoftheyearare:%d\n",date.yearDay);}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第36页。37在上述主函数中，调用dayofYear函数使用了date结构的3个成员:day、month和year作为实参。在dayofYear函数中用3个形参：

d、m和y与之对应，并将最后的计算结果通过执行“returnday;”语句返回给主函数，并赋值给Date结构类型变量的yearDay成员。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第37页。38结构作为函数参数

用结构作为实参，将这个结构的所有成员都传递给了被调用函数的形参。以例7.3程序为例，对主函数中对函数dayofYear的调用，原来使用表示日、月、年的3个结构成员作为实参改为用一个结构变量date作为实参。即将代码

date.yearDay=dayofYear(date.day,date.month,date.year);改写成

date.yearDay=dayofYear(date);掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第38页。39当然，对应的dayofYear函数也要作如下的修改：intdayofYear(Dated)/*计算年中第几天，设有结构形参*/{inti,leap,day=d.day;leap=(d.year%4==0&&d.year%100)||d.year%400==0;/*计算是否闰年*/for(i=0;i<d.month-1;i++)day+=dayTable[leap][i];returnday; /*返回计算的结果*/}在主函数中，对dayofYear函数的调用直接使用了date为实参，在dayofYear函数中用结构形参Dated。结构变量或结构成员作为实参传递给函数形参是值传递。dayofYear函数只能把计算结果返回给主函数，而不能简单地将计算结果直接赋值给形参的yearDay成员。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第39页。40结构指针作为函数参数

使用结构变量作为函数的形参，在函数调用时，系统要为结构形参分配存储单元，并为实参结构向形参结构完成值传递等。为了减少系统开销并提高效率，C语言也允许指向结构的指针作为函数的形参。实参可以是结构的地址，也可以是指向结构的指针变量。仍以例7.3程序为例，主函数中对函数dayofYear的调用，由使用结构变量date作为实参现改为用结构变量date的地址作为实参。即，将代码

date.yearDay=dayofYear(date);改写成

dayofYear(&date);对应的dayofYear函数也要作如下的修改：掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第40页。41

voiddayofYear(Date*dp)/*计算年中第几天函数，设有结构指针形参，无返回值*/{inti,leap,day=dp->day; /*确定是闰年或平年*/leap=(dp->year%4==0&&dp->year%100)||dp->year%400==0;for(i=0;i<dp->month-1;i++)day+=dayTable[leap][i];dp->yearDay=day; /*计算结果回填到yearDay成员，没有return语句*/}在主函数中，对dayofYear函数的调用使用date结构变量的地址作为实参，因此在dayofYear函数中必须用结构指针形参Date*dp与之对应。被调用函数dayofYear通过结构指针形参引用所指向的结构成员，并将计算结果存放到所指结构的相应成员yearDay，不必再返回结果。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第41页。42(1)结构或结构成员作为函数参数是值传递方式，在被调用函数dayofYear中必须用return语句返回结果。如果不用return语句，写成“d.yearDay=day；”，主函数不能获得函数结果。因为函数的形参是函数的局部变量，函数调用时，将结构date的各成员值依次送给形参d的各成员中，以后函数对d作任何的改变与date无关。见图7.3所示。main函数调用语句 dayofYear函数

date结构（实参） d结构（形参）图7.3结构作为函数参数daymonthyearyearDaydaymonthyearyearDay掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第42页。43(2)使用结构地址或结构指针作为函数的参数，函数调用时，虽只传递结构的地址给结构指针形参，但通过该结构指针形参间接引用所指向的结构变量。因此，函数既可以引用结构指针形参所指向结构的成员，也可把计算结果存储于结构指针形参所指向结构的成员中。见图7.4所示。

date结构形参dp

图7.4结构地址作为函数参数daymonthyearyearDay掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第43页。44函数返回结构类型值在7.3的2中，将结构date作为实参传递给dayofYear函数的结构类型形参d，但计算结果是通过returnday;语句返回到主函数的调用语句。如果希望将计算的结果先保存到结构类型形参d的成员yearDay中，然后返回结构类型形参d的值，可以对函数dayofYear重新改写如下：DatedayofYear(Dated){inti,leap;d.yearDay=d.day;leap=(d.year%4==0&&d.year%100)||d.year%400==0;/*计算是否闰年*/for(i=0;i<d.month-1;i++)d.yearDay+=dayTable[leap][i];returnd; /*返回结构类型*/}

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第44页。45经上述改动后，主函数调用dayofYear函数后，需要把返回的结构赋值给结构变量date，调用语句也作相应的修改。即将

date.yearDay=dayofYear(date);改写成

date=dayofYear(date);调用带有结构类型形参的函数时，实参结构的各成员的值需要全部拷贝给形参结构的相应成员，费时间又费空间。一般情况下，以传递结构地址或指针为好。有时为了程序的安全性，确保函数不能修改实参结构情况下，可使用结构作为形参。调用函数返回结构值的函数，需要将函数的返回值赋值保存于某个结构变量。对于复杂的结构类型，实现的效率较低。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第45页。46变量：通过变量定义引入。程序执行时，不能显式地用语句随意生成变量和消去变量，并且变量之间的关系也不能由变量本身的成分来表达。数组：必须事先定义固定的长度（即元素个数），有时存放的数据不确定时，往往把数组定得足够大。按数据对象可能最多情况来设定变量或数组，称为静态方法。而按需要用随时生成和消去数据对象，数据之间的关系也能由程序随时设定和改变，这种实现方法称为动态方法，如链表。7.4链表掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第46页。47由数据对象中的某个成员表示某个元素之后是哪一个元素。链表的元素个数可按需要任意增删，链表元素的后继元素也能由元素自已指定。具有链表这样两项特性的数据结构称为动态数据结构，链表是最简单的动态数据结构。在链表上，可以非常方便地增加一个表元（或称元素、结点）或删除一个表元。图7.5(a)列出了只有3个表元的单链表结构。什么是链表图7.5单链表结构掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第47页。48head：链表的“头指针”变量，存放的是地址，指向链表的第一个元素（或称表元、结点）。链表元素：分成两部分，存放实际的数据和后继表元指针。1000headA1100B1200CNULL100011001200单向链表结构示意图NULLhead空链表示意图掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第48页。49链表一环扣一环地将多个表元链接在一起，即头指针head指向第1个表元，第1个表元又指向第2个表元，……，直到链表的最后一个表元。我们一般称链表的第1个表元为“首表元”，链表的最后一个表元为“尾表元”（尾表元的后继指针一般为“NULL”，表示链表不再有后继表元）。当链表中没有任何一个表元时称为空链表，此时链表头指针为“NULL”，如图7.5(b)所示。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第49页。50图7.5所示的链表结构是单向的，即每个表元只存储它的后继表元的位置，而不存储它的前驱表元的位置。这种形式的链表称为单链表。在单链表中，一个表元的后继表元位置存储在它所包含的某个指针成员中，单链表的每个表元在内存中的存放位置是可以任意的。如果某个算法要对链表作某种处理，必须从链表的首表元开始、顺序处理链表的表元。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第50页。51在某些应用中，要求链表的每一个表元都能方便地知道它的前驱表元和后继表元，这种链表的表元需包含两个指针，分别指向它的前驱表元和后继表元，这种链表称为双向链表。如图7.6所示。在双向链表中，插入或删除一个表元比单向链表更为方便，但结构也较为复杂。常见的链表还有循环链表，在循环链表中，链表尾表元的后继指针指向链表的首表元。限于篇幅，在这一节中仅介绍单链表的基本操作。图7.6双链表结构

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第51页。52链表与数组相比较，主要的区别：(1)数组的元素个数在数组定义时指定，元素个数是固定的；链表表元的存储空间是在程序执行时由程序动态向系统申请的，链表的表元个数可按需要增减。(2)数组的元素顺序关系由元素在数组中的下标确定，链表表元顺序关系由表元的指针实现。(3)在数组中插入或删除表元，要移动部分表元的存储位置。在链表中插入或删除表元，不要移动表元，仅改变表元的指针指向即可。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第52页。53动态变量

动态数据结构中的数据对象是一种结构变量，有一些成员存储数据信息，还有存储指针的成员。最简单情况是结构包含有指向与自己同样结构的指针。例如

structintNode/*整数链表表元类型*/{intvalue;/*存放整数*/intNode*next;/*存放后继表元的指针*/};掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第53页。54在结构类型intNode中，有两个成员，value和指向后继表元的指针成员next。其中指针成员next能指向的结构类型就是正在定义的intNode。这种结构又称为自引用结构。利用指针成员next，可把一个intNode类型的结构与另一个同类型的结构链接起来，用于描述动态数据结构中两数据对象之间的关系。在这种有成员引用自身的结构类型定义中，允许引用自身的成员只能是指针类型。动态数据结构中的变量称为动态变量，动态变量能由程序调用库函数，显式地随意生成和释放(消去)。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第54页。55在C语言中，有malloc和calloc两个库函数用于生成动态变量，另有一个库函数free用于释放动态变量。

1.malloc(size)功能：从系统提供的动态存储区域中分配size个字节的连续空间，函数返回该连续空间的开始地址。如果因动态存储区域已分配完，而不能满足这次申请要求，函数将返回0(NULL)值。说明：因函数malloc()的返回值是无类型指针值，程序可将该返回值强制转换成某种特定的指针类型。例如：intNode*p;p=(intNode*)malloc(sizeof(intNode));申请能存储类型为intNode的结构的存储空间，并将该结构指针存于指针变量p。动态变量没有名字，只能通过指针引用它。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第55页。562.calloc(n,size)功能：在动态存储区中分配n个size个字节的连续空间，函数返回该连续空间的开始地址；如果分配不成功，则返回0。例如：申请分配能存储100个整数的存储块。

p =(int*)malloc(100*sizeof(int));q =(int*)calloc(100,sizeof(int));3.free(ptr)功能：释放由ptr所指向的存储块。说明：ptr的值必须是调用函数malloc()或calloc()申请到的连续存储空间中的地址。sizeof运算掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第56页。57以上三个函数中，形参size和n为unsigned类型，ptr为指针类型。函数malloc()和calloc()返回的是系统分配的连续存储空间的首地址，其类型为void*的（即无类型的指针值，程序应将返回值强制转换成某种特定的指针类型），程序将这返回值赋给某个指针变量，然后用该指针变量间接引用存储空间的相应成分。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第57页。58单链表的基本操作主要包括建立空的单链表、创建一个表元、遍历单链表、查找指定值的表元、往单链表插入一个表元、从单链表删除一个表元等。下面以学生单链表为例，说明各种操作的实现算法。structstuS /*学生链表表元结构类型*/{intnumber; /*学号*/charname[20]; /*姓名*/intscore; /*成绩*/stuS*next;/*指向后继表元的指针*/};stuS*head,*p,*p1,*p2;/*head是链表的头指针，其余是工作指针*/

单链表上的基本操作

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第58页。591.建立空链表链表的建立过程是从空链表(没有链表表元)出发，逐渐插入链表新表元的过程。要使以变量head为头指针的链表为空链表，让head取NULL值即可。语句：head=NULL;说明：建立以head为链表头指针的空链表。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第59页。60假设要创建一个新的学生，该生的学号、姓名和成绩从键盘输入。程序应首先向系统申请对应该生的表元的存储空间，然后输入该生的信息存入这个表元。例如p=(stuS*)malloc(sizeof(stuS));//p指向申请到的存储块scanf(“%d%s%d”,&p->number,p->name,&p->score);/*输入并存储本表元的值*/p->next=NULL; /*后继表元地址为空*/函数调用malloc()的实参表达式sizeof(stuS)是单链表上一个表元所需的字节数。malloc()函数的返回值是一个新的动态变量的开始地址，返回值作强制类型转换(stuS*)，使返回的(void*)无类型指针转换成structstuS*类型的指针，并将该指针赋给指针变量p。就可使用p->number和p->next间接引用动态变量的成员number和next。

2、创建一个表元掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第60页。61【例7.4】编写创建一个学生表元的函数。设学生的学号、姓名和成绩由函数的形参指定，函数返回新表元的指针。函数首先调用malloc()申请新表元的空间，空间所需的字节数为sizeof(stuS)。然后将形参值存入新表元的相应成员中。最后，函数返回新表元的指针。stuS*createStudent(intnum,char*name,ints){stuS*p=(stuS*)malloc(sizeof(stuS));p->number=num;strcpy(p->name,name);p->score=s;p->next=NULL;returnp;}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第61页。62所谓遍历链表是顺序访问链表中的表元，对各表元作某种处理。例如，顺序输出链表各表元的数据。遍历单链表需从链表的首表元开始，沿着表元的链接顺序逐一考察链表的每个表元，直至链表结束。遍历链表的过程是一个循环，访问表元用输出表元的值示意。假设用工作指针p遍历整个链表，p的初值应该是链表的头指针，循环条件是指针p还指向某个表元，即p不等于NULL。循环要做的工作包括输出p所指向的表元的值，和准备考察下一个表元(p=p->next实现)。3、遍历链表掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第62页。63【例7.5】编写遍历学生单链表的函数。函数应设学生链表的头指针为形参。函数首先检查链表是否为空，如果是空链表，输出链表中没有学生字样后返回。否则，函数从链表的首表元开始，顺序输出每个学生的信息。voidtravelStuLink(stuS*head){stuS*p=head;if(head==NULL){printf("\n目前在链表中没有学生\n");return;}printf("\n目前在链表中的学生如下\n");while(p!=NULL){printf("%d\t%s\t%d\n",p->number,p->name,p->score);p=p->next;/*准备访问下一个表元*/}}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第63页。64在链表中查找指定值的表元可能有以下几个目的：获取该表元的详细信息，或对找到的表元进行修改，或将查到的表元删除，或在查到的表元之前插入一个新表元等。查找过程的实现又可分为两种情况：无序链表上的查找，有序链表上的查找。●无序单链表上的查找无序单链表上的查找函数需设置两个形参：已知链表的头指针和要寻找的表元的值。函数使用工作指针变量v，让它从链表的首表元开始顺序考察链表各表元。循环条件是v不等于NULL且v所指表元的值不等于指定值。循环要做的工作非常简单，只是准备考察下一个表元(即v=v->next)。查找循环结束后，函数返回指针变量v的值。4、在链表中查找表元掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第64页。65【例7.6】编写无序学生单链表上的查找函数searchSLink()。函数应设两个形参：学生链表的头指针要寻找的学生的学号。函数的寻找过程是一个循环，设循环工作变量为v。v的初值是链表的头指针，循环条件是v!=NULL&&v->number!=num。因为还没有找到指定学号的学生，循环体要做的工作:让v指向下一个学生。寻找循环结束后，函数返回v。如果找到，v指向找到的表元；如果未找到，v的值是NULL，表示链表中没有要找的学生。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第65页。66

stuS*searchSLink(stuS*h,intnum){stuS*v=h;while(v!=NULL&&v->number!=num)v=v->next;returnv;}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第66页。67如果单链表的表元是按表元值从小到大顺序链接的，在顺序考察链表表元的查找循环中，当发现还有表元，并且该表元的值比寻找值小时，应继续查找，准备去考察下一个表元。反之，若不再有表元，或当前表元值不比寻找值小，则查找应结束。查找循环结束后，仅当还有表元，并且当前表元的值与寻找值相等情况下，才算找到，函数返回当前表元的指针。否则，链表中没有要寻找的表元，函数应该返回NULL。

●有序单链表上的查找

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第67页。68【例7.7】编写学号从小到大有序学生链表上查找指定学号的函数searchSOLink()。【解题思路】与函数searchSLink()一样，也应设链表的头指针和要寻找学号两个形参。函数的寻找循环也是从链表的首表元开始，循环条件是还有表元，且表元的值小于寻找值。循环体要做的工作是准备考察下一个学生。寻找循环结束后，还有当前表元，且当前表元的值是要寻找值情况下，函数才返回当前表元的指针。否则，函数返回NULL。

stuS*searchSOLink(stuS*h,intkey){stuS*v=h;while(v!=NULL&&v->number<key)v=v->next;returnv!=NULL&&v->number==key?v:NULL;}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第68页。69往单链表插入一个表元是建立单链表的主要操作之一，它又可按表元插入在单链表中的位置不同分两种情况：可以插在链表的最前面（作为首表元）、可以插在指定的表元之后。以下所有的示意图都以整数链表为例，说明在链表上各基本操作的基本原理。5、在链表中插入新表元掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第69页。70在原来的首表元之前插入一个新表元，插入的表元将成为链表新的首表元。这个工作包括将链表原来的首表元接在新插入的表元之后，并修改链表的头指针，使链表的头指针指向新插入的表元。设指针p指向新申请到的表元地址，实现这个功能的代码如下：p->next=head; /*新表元指向原首表元地址，使原首表元成为后继表元*/head=p; /*头指针指向新表元，使新表元成为首表元*/执行了上述代码后，原链表的首表元接在新表元的后面，而链表头指针head指向了新表元。图7-8显示在首表元之前插入新表元，程序执行的代码和链表插入前后的状态变化。

●在首表元之前插入新表元掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第70页。71在首表元之前插入新表元图7.8在首表元之前插入新表元的实现代码和链表状态变化图p->next掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第71页。72对于单链表，一个表元的前驱表元不是直接可引用的，所以表元一般要求插在某表元之后。假设指针w指向指定的表元(w不为NULL)，指针p指向要插入的表元。在单链表的w所指表元之后插入p所指表元，图7-9显示在指定表元之后插入新表元，程序执行的代码和链表插入前后的状态变化。插入前，表元联结用有向直线段表示，插入后，表元联结用有向弧线表示。插入工作包含两个基本动作：①将w所指向的表元的后继表元指针复制给p所指向的表元的后继指针域，即原先w所指向表元的后继表元成为p所指向表元的后继表元，用代码p->next=w->next实现。②将p的值复制给w所指表元的后继指针域，即让p所指的表元成为w所指表元的后继表元，用代码w->next=p实现。

p->next=w->next;w->next=p;●在指定的表元之后插入新表元

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第72页。73在指定的表元之后插入新表元

图7.9在指定表元之后插入新表元的实现代码和链表状态变化图p->nextw->next掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第73页。74【例7.8】编写在学生链表中，在指定学生之后插入一个新学生的函数。【解题思路】函数设有一个表示学生链表头指针的形参head和指定学生学号的形参num。函数首先在链表中寻找指定学号的学生。如果链表中没有指定学号的学生，则不做插入工作，直接返回。如果有指定学号的学生，函数申请存储新学生信息的空间，输入新的学生信息，并完成插入工作。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第74页。75voidinsert(stuS*head,intnum)/*key为要查找的学号*/{stuS*w=head,*p;while(w!=NULL&&w->number!=num)w=w->next; /*后移一个表元*/if(w==NULL){ /*未找到*/printf("学号%d没有找到！\n",num);return;}/*找到，w指向找到的表元*/p=(stuS*)malloc(sizeof(stuS));//p指向新申请的表元

printf("请输入学号、姓名、成绩：");scanf("%d%s%d",&p->number,p->name,&p->score);p->next=w->next;/**w的后继表元作为*p的后继表元*/w->next=p; /**p作为*w的后继表元*/}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第75页。76设要插入的新表元由指针p所指，将p所指表元添加到链表末尾的操作可由以下3个操作步骤完成：①从头指针开始依次找到最后的表元，由指针w指向最后的表元。②将指针p所指表元成为指针w所指的后继表元，用代码w->next=p实现。③将新表元的后继表元设置为空，用代码p->next=NULL实现。图7-10显示在末表元之后插入表元，程序执行的代码和链表插入前后的状态变化。

●在链表末尾添加新表元掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第76页。77在链表末尾插入新表元图7.10在末表元之后插入新表元的实现代码和链表状态变化图掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第77页。78【例7.9】编写在学生链表的末尾接上一个新学生的函数。函数设有一个表示学生链表头指针的形参head。函数首先申请存储学生信息的空间，并输入新的学生信息。函数在发现原链表是空时，简单地将新表元指针作为链表的头指针返回。否则，用循环寻找链表的末尾表元，然后将新表元接在末尾表元之后，返回原链表的头指针。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第78页。79stuS*append(stuS*head){stuS*w=head,*p;p=(stuS*)malloc(sizeof(stuS));//p2指新申请的表元

printf("请输入学号、姓名、成绩：");scanf("%d%s%d",&p->number,p->name,&p->score);p->next=NULL;/*p为最后一个表元*/if(head==NULL)returnp;/*原链表是空链表，直接返回新表元指针*/while(w->next!=NULL)//非空链表，顺序向后找尾表元

w=w->next;/*后移一个表元，直到w指向尾表元*/w->next=p;/**p作为*w的后继表元*/returnhead; /*返回头指针*/}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第79页。806.

从链表中删除表元要将一表元从链表中删除，首先要在链表中查找该表元。若未找到，则不用做删除工作；在删除时还要考虑两种不同的情况：如果删除的是首表元要修改链表头指针。如果删除的表元不是链表的首表元，则要更改删除表元的前驱表元的后继指针。假设指针变量p1的初值指向首表元，通过循环，p1依次指向下一个表元（使用p1=p1->next实现）；指针变量p2总是指向p1的前驱表元（使用p2=p1实现）。

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第80页。81删除单链表的首表元

单链表的首表元删除后，首表元的后继表元成为新的首表元。假设从单链表删除下来的表元由指针变量p指向它。图7.11是单链表删除首表元之前和删除之后的状态变化示意图，有向线段表示删除之前表元之间的联接关系，有向弧线表示删除后的表元联接关系。删除时，首先将首表元的指针保存到p。如果单链表不是空链表，继续要做的工作包括让链表的头指针指向首表元的后继表元，使这个后继表元成为单链表新的首表元。最后，将从单链表删除下来的表元的后继指针置成NULL，使它与原单链表脱离联系。

p=head;/*将首表元的指针保存到某指针变量*/if(p){//如果有首表元

head=head->next;//头指针指向首表元的后继表元

p->next=NULL;/*删除表元与原单链表脱离联系*/}

掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第81页。82图7-11删除链表首表元，删除前后状态变化图掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第82页。83删除单链表中的某表元

在单链表中，表元的前驱表元是不能直接引用的，但要删除一个表元必须更新它的前驱表元的后继指针。所以，一般情况下，在表元删除前，必须知道该表元的前驱表元指针。假设要删除表元的前驱表元的指针是w。如图7-12所示，欲删去值为5的表元，删除后由指针p指向它。删除前的表元联接关系用有向直线段所示，删除后的表元联接关系用有向弧线表示。删除时，先让指针p指向值为5的表元，接着让w所指表元(值为4的表元)的后继表元更改为值为6的表元，最后，值为5的表元的后继指针改为NULL。完成这样的删除操作，可用以下代码实现：

p=w->next;w->next=p->next;p->next=NULL;掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第83页。84图7-12删除链表中w所指表元的后继表元，删除前后状态变化图表元从链表删除后，对删除的表元可有两种不同的处理。或回收删除表元所占的存储空间，这可调用函数free(p)来实现；或将删除表元插入到其他链表中。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第84页。85【例7.10】编写在学生链表中删除指定学号的表元的函数。【解题思路】删除特定的表元必须先做寻找的工作。在寻找过程中，必须记住当前表元的前驱表元，待寻找结束时，不仅找到了要删除的表元，同时得到删除表元的前驱表元。设以p为寻找循环的工作指针，它的初值是链表的头指针，循环条件是还有当前表元，且当前表元的学号不等于要寻找的学号。循环体由两条语句组成，让当前表元的指针保存于变量w(w=p)，当前表元指针指向下一个表元(p=p->next)。其中，先把当前表元指针保存于某个变量是必须的，否则当寻找循环结束时，没有当前表元的前驱表元指针就不能做删除操作。细节见以下函数定义。掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第85页。86stuS*delStu(stuS*head,intnum) /*num为要查找的学号*/{stuS*w,*p;if(head==NULL)returnNULL;p=head; /*让p指向链表的首表元*/while(p!=NULL&&p->number!=num){w=p;p=p->next;/*w指向前驱表元，p指向下一个表元*/} if(p!=NULL){/*找到*/if(p==head)head=p->next;/*删除首表元，改链表头指针*/elsew->next=p->next;/*修改前导表元的的后继指针*/printf("学号%d已被删除\n",num);free(p); /*释放被删表元的存储空间*/}elseprintf("学号%d找不到！\n",num);returnhead; /*返回头指针*/}掌握结构数据类型、结构变量和结构指针的定义-结构成分全文共141页，当前为第86页。87#include<stdio.h>#include<string.h>#include<malloc.h>structstuS{intnumber; /*学