《第10讲结构体和链表.ppt》由会员分享，可在线阅读，更多相关《第10讲结构体和链表.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第第第10101010讲讲讲讲 结构体和链表结构体和链表结构体和链表结构体和链表10.1 10.1 结构体类型的定义与变量说明结构体类型的定义与变量说明10.2 10.2 结构体类型变量的引用与初始化结构体类型变量的引用与初始化10.3 10.3 结构体类型与数组结构体类型与数组10.4 10.4 结构体类型与指针结构体类型与指针10.5 10.5 结构体与函数结构体与函数10.6 10.6 链表链表 10.1 10.1 结构体类型定义结构体类型定义10.1 10.1 结构体类型的定义与变量说明结构体类型的定义与变量说明 我们所处理的数据并非总是一个简单的整型、我们所处理的数据并非总是一个简
2、单的整型、实型或字符型数据。如我们要处理的对象是学生，实型或字符型数据。如我们要处理的对象是学生，不可能孤立地考虑学生的成绩，而割裂学生成绩不可能孤立地考虑学生的成绩，而割裂学生成绩与学生其它属性之间的内在联系。与学生其它属性之间的内在联系。学生的成绩、姓名、学号等是一组逻辑相关学生的成绩、姓名、学号等是一组逻辑相关的数据，孤立地考虑这些属性，将导致操作的不的数据，孤立地考虑这些属性，将导致操作的不便或逻辑错误。便或逻辑错误。解决以上问题的方法就是引入结构体类型，解决以上问题的方法就是引入结构体类型，将逻辑相关的数据有机组合在一起，称之为结构将逻辑相关的数据有机组合在一起，称之为结构体。体。一
3、一.结构体类型的定义struct struct 结构体类型名结构体类型名 数据成员列表；数据成员列表；结构体类型的一般定义形式为：结构体类型的一般定义形式为：定义结构体类定义结构体类型的标识符型的标识符用户命名用户命名的标识符的标识符结构体类型定结构体类型定义的结束符义的结束符 10.1 10.1 结构体类型定义结构体类型定义 例例10-110-1，一个学生的数据信息包含有学号、姓名、，一个学生的数据信息包含有学号、姓名、性别、年龄、成绩、住址，可将其定义为一个结构体性别、年龄、成绩、住址，可将其定义为一个结构体类型：类型：struct struct studentstudent long I
4、D long ID；/*/*学生学号学生学号*/*/char name10char name10；/*/*学生姓名学生姓名*/*/char sexchar sex；/*/*学生性别学生性别*/*/int int ageage；/*/*学生年龄学生年龄*/*/float scorefloat score；/*/*学生成绩学生成绩*/*/char char addraddr3030；/*/*学生住址学生住址*/*/；结构体类型定义仅仅是定义了一个特定的复合数据类型，描述了结构体类型定义仅仅是定义了一个特定的复合数据类型，描述了这一类型数据的公共属性，为了在程序中使用该结构体类型的具这一类型数据的公
5、共属性，为了在程序中使用该结构体类型的具体对象，还需要说明这种类型的变量。体对象，还需要说明这种类型的变量。10.1 10.1 结构体类型定义结构体类型定义二.结构体类型变量的定义 结构体类型变量定义的一般形式：结构体类型变量定义的一般形式：struct struct 结构体类型名结构体类型名 结构体变量名；结构体变量名；1.1.先定义结构体类型再定义结构体变量先定义结构体类型再定义结构体变量 struct struct student stu1student stu1，stu2 stu2；ID(4字节)stu1namesex(1字节)age(2字节)score(4字节)addr共10个字节共
6、30个字节IDstu2图10-1 结构体变量的存储结构共51个字节 10.1 10.1 结构体类型定义结构体类型定义2.2.定义结构体类型的同时定义变量定义结构体类型的同时定义变量struct struct studentstudent long ID long ID；char name10 char name10；char sex char sex；int int ageage；float score float score；char char addr addr3030；stu1stu1，stu2stu2；10.1 10.1 结构体类型定义结构体类型定义3.3.直接定义结构体变量直接定义结
7、构体变量struct struct long ID long ID；char name10 char name10；char sex char sex；int int ageage；float score float score；char char addr addr3030；stu1stu1，stu2stu2；结构体变量的三种形式可以任意选用。但在不同函结构体变量的三种形式可以任意选用。但在不同函数中定义说明同一类型的结构体变量时，用第三种数中定义说明同一类型的结构体变量时，用第三种方法不太方便，一般用第一种和第二种定义形式。方法不太方便，一般用第一种和第二种定义形式。10.1 10.1 结
8、构体类型定义结构体类型定义三.结构体类型的嵌套 结构体类型的嵌套是指结构体的成员是一个结构体类型。结构体类型的嵌套是指结构体的成员是一个结构体类型。若定义学生信息为结构体，其成员分别为：学号、姓名、性别、出若定义学生信息为结构体，其成员分别为：学号、姓名、性别、出生年月、成绩。其中出生年月包括出生的年、月、日三个数据，这生年月、成绩。其中出生年月包括出生的年、月、日三个数据，这些数据可以用另一个结构体类型表示。些数据可以用另一个结构体类型表示。例如，定义例如，定义studentstudent结构体。结构体。（1 1）先定义）先定义datedate结构体：结构体：struct struct da
9、tedate int int year;year;int int month;month;int int day day；（2 2）再定义）再定义studentstudent结构体：结构体：struct struct studentstudent long ID long ID；char name10 char name10；char sex char sex；struct struct date birthday date birthday；float score float score；10.1 10.1 结构体类型定义结构体类型定义10.210.2结构体类型变量的引用与初始化结构体类型变
10、量的引用与初始化一.结构体类型变量的引用 对一个结构体类型变量的引用是通过引用它的对一个结构体类型变量的引用是通过引用它的每一个成员来实现的。每一个成员来实现的。引用运算符有两个：引用运算符有两个：.-.-其中，其中，“-”“-”为结构体指针运算符，为结构体指针运算符，引用一个结构体变量的成员有两种方法：引用一个结构体变量的成员有两种方法：结构体变量名、指向结构体的指针变量结构体变量名、指向结构体的指针变量结构体成员运算符结构体成员运算符“.”“.”在所有运算符中优先级最高在所有运算符中优先级最高.结构体变量不能作为一个整体进行输入输出结构体变量不能作为一个整体进行输入输出,只能对只能对其成员
11、分别输出其成员分别输出 。10.2 10.2 结构体变量引用结构体变量引用用结构体变量名引用其成员的一般形式：用结构体变量名引用其成员的一般形式：结构体变量名结构体变量名.成员名成员名 其中，其中，“.”“.”称为结构体成员运算符，将结构体变量称为结构体成员运算符，将结构体变量名与成员名连接起来，它具有最高级别的优先级。名与成员名连接起来，它具有最高级别的优先级。结构体变量可以单独引用其成员，也可作为一个整体结构体变量可以单独引用其成员，也可作为一个整体引用，还可以引用结构体变量或成员的地址。引用，还可以引用结构体变量或成员的地址。1.1.单独引用结构体变量的成员单独引用结构体变量的成员 st
12、ruct struct clockclock intint hour,minute,second hour,minute,second；struct struct datedate intint year,month,day year,month,day；struct struct clock timeclock time；structstruct date today date today；today.year=2004today.year=2004；today.month=4today.month=4；today.day=12today.day=12；today.time.hour=16t
13、oday.time.hour=16；today.time.minute=47today.time.minute=47；today.time.second=15today.time.second=15；10.2 10.2 结构体变量引用结构体变量引用2.2.结构体变量作为一个整体引用结构体变量作为一个整体引用 结构体变量不可以作为整体进行输入输出，但可结构体变量不可以作为整体进行输入输出，但可以作为函数的参数或返回值而被整体引用，也可以将以作为函数的参数或返回值而被整体引用，也可以将一个结构体变量作为一个整体赋给另一个具有相同类一个结构体变量作为一个整体赋给另一个具有相同类型的结构体变量。型的结
14、构体变量。struct struct datedate int int year year，month month，day day；struct struct datedate nextday nextday(day)(day)struct struct date daydate day；struct struct date tempdate temp；.return(temp)return(temp)；函数函数nextdaynextday的形参的形参dayday为结构体类型，为结构体类型，它将整体接受同类它将整体接受同类型实参的值型实参的值 10.2 10.2 结构体变量引用结构体变量引用3
15、.3.引用结构体变量的地址或成员的地址引用结构体变量的地址或成员的地址引用结构体变量的成员地址，要在结构体成员引用引用结构体变量的成员地址，要在结构体成员引用的前面再加的前面再加“&”“&”运算符运算符.结构体变量结构体变量a a的成员的成员t t赋值：赋值：scanfscanf(”%d”(”%d”，&a.t)&a.t)；引用结构体变量的地址引用结构体变量的地址,在结构体变量的前面直接在结构体变量的前面直接加加“&”:“&”:printfprintf(%X(%X，&a)&a)；10.2 10.2 结构体变量引用结构体变量引用二.结构体类型变量的初始化 结构体变量可以在说明的同时初始化。结构体变
16、量可以在说明的同时初始化。structstruct clock clock int int hour hour，minuteminute，secondsecond；structstruct date date intint year year，monthmonth，dayday；struct struct clock time clock time；struct struct date today=2004 date today=2004，4 4，1212，1717，4 4，3030；structstruct date today=2004 date today=2004，4 4，1212，1
17、717，4 4，3030；10.2 10.2 结构体变量引用结构体变量引用10.3 10.3 结构体类型与数组结构体类型与数组 一.结构体数组的定义 1.1.先定义结构体类型，后定义结构体数组先定义结构体类型，后定义结构体数组 struct struct student students100student students100；2.2.结构体数组与结构体类型同时定义结构体数组与结构体类型同时定义structstruct student student long ID long ID；char name10 char name10；int int ageage；float score3 fl
18、oat score3；students100 students100；3.3.不定义结构体类型名，直接定义结构体数组不定义结构体类型名，直接定义结构体数组 struct struct long ID long ID；char name10 char name10；int int ageage；float score3 float score3；students100 students100；10.3 10.3 结构体与数组结构体与数组二.结构体数组的初始化与结构体数组元素的引用 1.1.结构体数组的初始化结构体数组的初始化 structstruct person personlong IDlo
19、ng ID；char name10 char name10；char sex char sex；struct struct date date birthdate birthdate；char department30 char department30；float salary float salary；char address30 char address30；employee3=employee3=1001，”张山张山”，M，1990，3，5，”计算中心计算中心”，545，”长沙长沙”，1002，”李红李红”，F，1989，10，1，”信息学院信息学院”，643，”武汉武汉”，1003，
20、”王武王武”，M，1987，4，15，”人事处人事处”，745，”广广州州”；10.3 10.3 结构体与数组结构体与数组图10-2 结构体数组的存储结构employee11002ID（4字节）李红name（10字节）10sex（1字节）1birthdate(date类型，6字节)信息学院salary（4字节）643address（30个字节）F1989武汉department（30个字节）共85个字节employee21003ID（4字节）王武name（10字节）4sex（1字节）15birthdate(date类型，6字节)人事处salary（4字节）745address（30个字节）M1
21、987广州department（30个字节）共85个字节employee01001ID（4字节）张山name（10字节）3sex（1字节）5birthdate(date类型，6字节)计算中心salary（4字节）545address（30个字节）M1990长沙department（30个字节）共85个字节 10.3 10.3 结构体与数组结构体与数组2.2.结构体数组元素的引用结构体数组元素的引用 一个结构体数组元素相当于一个结构体变量，元一个结构体数组元素相当于一个结构体变量，元素成员的访问使用数组元素的下标来实现。素成员的访问使用数组元素的下标来实现。结构体数组元素成员的访问形式：结构体数
22、组元素成员的访问形式：结构体数组名结构体数组名 元素下标元素下标.结构体成员名结构体成员名 可以将一个结构体数组元素整体赋给同一结构体可以将一个结构体数组元素整体赋给同一结构体数组的另一个元素，或赋给同一结构体类型变量。数组的另一个元素，或赋给同一结构体类型变量。employee0.ID=1001;employee0.ID=1001;employee1=employee2employee1=employee2；与结构体变量一样，结构体数组元素也不能作为一与结构体变量一样，结构体数组元素也不能作为一个整体进行输入输出，只能以单个成员的形式实现。个整体进行输入输出，只能以单个成员的形式实现。10.
23、3 10.3 结构体与数组结构体与数组例例10-2 10-2 计算一个班学生的三门课程的平均成绩，并计算一个班学生的三门课程的平均成绩，并输出该班学生姓名及平均成绩。输出该班学生姓名及平均成绩。分析：分析：将学生姓名、三门成绩、平均成绩定义为一个将学生姓名、三门成绩、平均成绩定义为一个studentstudent结构体类型，使每个学生的各项数据组合成结构体类型，使每个学生的各项数据组合成一个整体进行操作。一个整体进行操作。若有若有n n名学生，则需要名学生，则需要n n个个studentstudent结构体类型变量，结构体类型变量，定义一个结构体数组定义一个结构体数组stustu存放存放n n
24、个学生的信息。个学生的信息。程序见教材第201页 10.3 10.3 结构体与数组结构体与数组10.4 10.4 结构体类型与指针结构体类型与指针 当结构体很大时，结构体变量的整体赋值效率当结构体很大时，结构体变量的整体赋值效率是相当低的。是相当低的。结构体变量名就是分配给该变量的内存空间的结构体变量名就是分配给该变量的内存空间的起始地址，我们可以利用指向结构体变量的指针，起始地址，我们可以利用指向结构体变量的指针，实现在不同程序段对同一内存区域的结构体变量的实现在不同程序段对同一内存区域的结构体变量的数据成员执行各种操作。数据成员执行各种操作。10.4 10.4 结构体与指针结构体与指针一.
25、指向结构体变量的指针 指向结构体变量的指针也称为结构体指针，它指向结构体变量的指针也称为结构体指针，它保存了结构体变量的存储首地址。保存了结构体变量的存储首地址。1.1.结构体指针的定义形式：结构体指针的定义形式：struct struct 结构体类型名结构体类型名 *指针变量名；指针变量名；struct struct studentstudent stu stu，*p*p；p=&p=&stustu；10.4 10.4 结构体与指针结构体与指针2.2.结构体变量成员的三种访问方法结构体变量成员的三种访问方法 （1 1）结构体变量）结构体变量.成员名成员名 stustu.ID.ID（2 2）(*
26、(*结构体指针结构体指针).).成员名成员名 (*(*p).IDp).ID （3 3）结构体指针结构体指针-成员名成员名 p p-IDID 结构体指针结构体指针-结构体成员结构体成员 结构体指针运算符结构体指针运算符“-”“-”10.4 10.4 结构体与指针结构体与指针二.指向结构体数组的指针struct struct personperson char name10 char name10；int int ageage；struct struct person *pperson *p，s s，boy3=boy3=”Zhang”，18，”Wang”，20，”Li”，17；对于已定义的结构体数
27、组，若用一个变量来存放该结对于已定义的结构体数组，若用一个变量来存放该结构体数组在内存中的首地址，则该变量为指向结构体构体数组在内存中的首地址，则该变量为指向结构体数组的指针变量。数组的指针变量。例如，定义结构体类型例如，定义结构体类型personperson和结构体指针变量和结构体指针变量p p。p=boyp=boy；定义了结构体数组定义了结构体数组boyboy和结构体指针变量和结构体指针变量p p，且且p p指向指向数组数组boyboy的首地址。的首地址。10.4 10.4 结构体与指针结构体与指针 将结构体变量与结构体数组的首地址赋给结构体指将结构体变量与结构体数组的首地址赋给结构体指针
28、的不同之处：针的不同之处：p=&sp=&s；/*s /*s为结构体变量为结构体变量*/*/p=boyp=boy；/*boy /*boy为结构体数组，为结构体数组，boyboy为数组的首地址为数组的首地址*/*/结构体指针也可以指向结构体数组的一个元素，这结构体指针也可以指向结构体数组的一个元素，这时结构体指针变量的值是该结构数组元素的首地址。时结构体指针变量的值是该结构数组元素的首地址。注意：注意：若要将结构体成员的地址赋给结构体指针若要将结构体成员的地址赋给结构体指针p p，则必则必须使用强制类型转换操作，转换形式为：须使用强制类型转换操作，转换形式为：p=(p=(struct struct
29、 结构体类型名结构体类型名*)&*)&结构体数组元素结构体数组元素.成员名成员名 10.4 10.4 结构体与指针结构体与指针10.5 10.5 结构体与函数结构体与函数C C语言中，在函数之间传递结构体变量有两种方法：语言中，在函数之间传递结构体变量有两种方法：(1)(1)以结构体变量作为参数，直接传递结构体变量的值以结构体变量作为参数，直接传递结构体变量的值.(2)(2)以结构体指针作为参数，传递结构体变量的地址。以结构体指针作为参数，传递结构体变量的地址。1.1.结构体变量作为函数的参数结构体变量作为函数的参数 在在ANSI CANSI C标准中允许用标准中允许用结构变量结构变量作为作为
30、函数参数函数参数进行进行整体传送整体传送，即直接将实参结构体变量的各个成员的值，即直接将实参结构体变量的各个成员的值逐个传递给形参结构体变量的对应成员。逐个传递给形参结构体变量的对应成员。注意，实参与形参必须是相同结构体类型的变量。注意，实参与形参必须是相同结构体类型的变量。10.5 10.5 结构体与函数结构体与函数struct stustruct stu intint num num；char*name char*name；char sex char sex；float score float score；boy5 boy5；intint pass(pass(struct stustruc
31、t stu p)/*p)/*函数说明函数说明*/*/for(i=0for(i=0；i5i-next=NULL；”。如如图图10-5（b）所所示。示。（3）将）将p结点插入到链表：结点插入到链表：如果链表为空（即如果链表为空（即head=NUUL），），则则p结点为头结点，也是尾结点，即：结点为头结点，也是尾结点，即：head=p；last=p；如图如图10-5（c）所示。所示。否则应将否则应将p结点插入到结点插入到last结点之后，并使结点之后，并使p结点成为当前的尾结点，即：结点成为当前的尾结点，即：last-next=p；last=p；如图如图10-5（d）所示。所示。（4）重复（）重复（
32、2）（3），继续插入新结点直到结束。），继续插入新结点直到结束。10.6 10.6 链表链表所所谓谓头头插插法法，是是指指新新插插入入的的结结点点总总是是作作为为链链表表的的第第一一个个结点。结点。用头插法建立链表的过程如下：用头插法建立链表的过程如下：（1）建建立立一一个个空空链链表表，即即head=NULL；与与尾尾插插法法不不同同的是这里不需定义尾指针。的是这里不需定义尾指针。（2）生生成成新新结结点点p，对对新新结结点点p的的数数据据域域赋赋值值。由由于于新新插插入的结点成为头结点，其指针域不必赋值。入的结点成为头结点，其指针域不必赋值。（3）将）将p结点插入到链表：结点插入到链表：先
33、先p结结点点的的后后继继为为当当前前的的头头结结点点，然然后后使使p结结点点成成为当前的头结点，即：为当前的头结点，即：p-next=head；head=p；（4）重复（重复（2）（3），继续插入新结点直到结束。），继续插入新结点直到结束。2.头插法建立单链表头插法建立单链表 10.6 10.6 链表链表三三.链表的访问链表的访问1.1.输出链表结点输出链表结点将链表中各结点的数据依次输出。输出链表结点的操将链表中各结点的数据依次输出。输出链表结点的操作过程如下：作过程如下：（1 1）取得链表头结点的地址）取得链表头结点的地址headhead；（2 2）用一个跟踪指针用一个跟踪指针p p指向头
34、结点，即指向头结点，即p=headp=head；（3 3）输出输出p p所指结点的成员值；所指结点的成员值；（4 4）移动指针）移动指针p p，使它指向它的后继结点。使它指向它的后继结点。即即p=p-nextp=p-next；（5 5）重复（重复（3 3）（）（4 4），直到指针），直到指针p p为空。为空。10.6 10.6 链表链表2.2.统计链表结点的个数统计链表结点的个数一般情况下，各个单链表中结点个数是随机的，要想知道一般情况下，各个单链表中结点个数是随机的，要想知道表中结点数目，必须从表头开始访问到表尾，逐个统计出表中结点数目，必须从表头开始访问到表尾，逐个统计出结点数目。结点数目
35、。3.3.查找链表的某个结点查找链表的某个结点在链表上查找符合某个条件的结点，也必须从链表头开始在链表上查找符合某个条件的结点，也必须从链表头开始访问链表。访问链表。（1 1）查找链表中第）查找链表中第n n个结点，若找到，则返回它的地址，个结点，若找到，则返回它的地址，否则返回空指针。否则返回空指针。（2 2）在链表中查找指定值的结点，若找到，则返回它的）在链表中查找指定值的结点，若找到，则返回它的地址，否则返回空指针。地址，否则返回空指针。10.6 10.6 链表链表四四.链表的插入操作链表的插入操作 所谓链表的插入操作就是将一个结点插入到一个已有所谓链表的插入操作就是将一个结点插入到一个
36、已有链表的某个位置上。链表的某个位置上。1.1.在第在第n n个结点之后插入个结点之后插入1 1个新结点个新结点(x)x)（1 1）输入）输入n n和和x x（一般在调用函数中处理）；一般在调用函数中处理）；（2 2）申请一个新结点，）申请一个新结点，q q指针指向新结点，指针指向新结点，q q的值为的值为x x（一般在调用函数中处理）；一般在调用函数中处理）；（3 3）p=headp=head，r=NULLr=NULL，r r为为p p的前驱结点，的前驱结点，i=0i=0；（4 4）i+i+，r=pr=p，p=p-nextp=p-next，p p结点往前移动一个结点；结点往前移动一个结点；（
37、5 5）若）若ininext=headq-next=head，head=qhead=q；（7 7）若若ininext=qr-next=q，q-next=NULLq-next=NULL；（8 8）否则，将否则，将q q结点插入到第结点插入到第n n个结点之后，即插入到个结点之后，即插入到r r结点与结点与p p结点之间：结点之间：r-next=qr-next=q，q-next=pq-next=p；（9 9）返回链表头返回链表头headhead。10.6 10.6 链表链表2.2.指定值的结点之后插入一个新结点指定值的结点之后插入一个新结点（1）q指针指向新结点；指针指向新结点；（2）p=head
38、，r指向指向p结点的前一个结点；结点的前一个结点；（3）若若head=NULL，则则链链表表为为空空，没没有有结结点点，q结结点点作作为为链链表表的的第第1个结点插入：个结点插入：head=q；q-next=NULL；（4）r=p，p=p-next，p、r结点往前移动结点往前移动1个结点；个结点；（5）若）若p-score!=x且且p!=NULL，则重复（则重复（4）；）；（6）若若p=NULL，则则未未找找到到score为为x的的结结点点，将将q结结点点插插入入到到链链表表尾尾r结点之后：结点之后：r-next=q，q-next=NULL；（7）否否则则，将将q结结点点插插入入到到第第n个个
39、结结点点之之后后，即即插插入入到到r结结点点与与p结结点之间：点之间：q-next=p-next，p-next=q；（8）返回链表头指针返回链表头指针head。10.6 10.6 链表链表五五.链表的删除操作链表的删除操作 从一个链表中删除一个结点，并不是真正从内存中把它从一个链表中删除一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离出来，即改变链表的链接关抹掉，而是把它从链表中分离出来，即改变链表的链接关系。系。1 1删除第删除第n n个结点个结点 将以将以headhead为头的链表中的第为头的链表中的第n n个结点从链表中移出，其个结点从链表中移出，其后继的结点往前移，使之仍为一
40、个链表，只是结点数目比后继的结点往前移，使之仍为一个链表，只是结点数目比原来少原来少1 1。10.6 10.6 链表链表例例:编写函数，删除学生链表编写函数，删除学生链表headhead中的第中的第n n个结点。个结点。分析：分析：（1 1）p=headp=head，q q指针指向指针指向p p所指结点的前所指结点的前1 1个结点；个结点；（2 2）i i为访问过的结点数目；为访问过的结点数目；（3 3）i+i+，q=pq=p，p=p-nextp=p-next，p p、q q移动移动1 1个结点；个结点；（4 4）若）若p!=NULLp!=NULL且且in-1inexthead=head-ne
41、xt；（6 6）若若head=NULLhead=NULL，链表为空，不能删除；链表为空，不能删除；（7 7）若）若p=NULLp=NULL，第第n n个结点不存在，不能删除；个结点不存在，不能删除；（8 8）找到第）找到第n n个结点，删除个结点，删除p p结点：结点：q-next=p-nextq-next=p-next；p p的前的前1 1个结点的个结点的nextnext值赋值为值赋值为p p的的nextnext域；域；（9 9）返回）返回headhead。10.6 10.6 链表链表2.2.删除指定结点删除指定结点例例:编写函数，删除链表编写函数，删除链表headhead中值为中值为x x
42、的结点。的结点。分析：分析：（1 1）p=headp=head，q q指针指向指针指向p p所指结点的前所指结点的前1 1个结点；个结点；（2 2）若）若head=NULLhead=NULL，链表为空，不能删除；链表为空，不能删除；（3 3）q=pq=p，p=p-nextp=p-next，p p、q q移动移动1 1个结点；个结点；（4 4）若）若p-next!=NULLp-next!=NULL且且p-score!=xp-score!=x，重复（重复（3 3）（5 5）若）若n=1n=1，则删除第则删除第1 1个结点，将下一个结点作为链表头结个结点，将下一个结点作为链表头结点：点：head=head-nexthead=head-next；（6 6）若若p-score=xp-score=x，则找到则找到scorescore值为值为x x的结点，删除的结点，删除p p结点：结点：若若p=headp=head为第为第1 1个结点，让个结点，让headhead指向下一个结点，指向下一个结点，head=p-nexthead=p-next；否则，否则，q-next=p-nextq-next=p-next；p p的前的前1 1个结点的个结点的nextnext值赋值为值赋值为p p的的nextnext域；域；（7 7）返回）返回headhead。10.6 10.6 链表链表