《第10章结构体与链表ppt课件》由会员分享，可在线阅读，更多相关《第10章结构体与链表ppt课件（46页珍藏版）》请在金锄头文库上搜索。
1、第第10章章 构造体与链表构造体与链表10.1 构造体类型的定义与变量阐明构造体类型的定义与变量阐明10.2 构造体类型变量的援用构造体类型变量的援用10.3 构造体与数组构造体与数组10.4 构造体与指针构造体与指针10.5 构造体与函数构造体与函数10.6 链表链表 10.1 构造体类型的定义与变量阐明构造体类型的定义与变量阐明10.1.110.1.1构造体类型的定义构造体类型的定义构造体类型的定义构造体类型的定义构造体是具有不同类型的数据的有序集合构造体是具有不同类型的数据的有序集合构造体是具有不同类型的数据的有序集合构造体是具有不同类型的数据的有序集合构造体定义：构造体定义：构造体定义
2、：构造体定义：struct struct 构造体类型名构造体类型名构造体类型名构造体类型名 类型标识符类型标识符类型标识符类型标识符 成员名成员名成员名成员名1;1; 类型标识符类型标识符类型标识符类型标识符 成员名成员名成员名成员名2;2; 类型标识符类型标识符类型标识符类型标识符 成员名成员名成员名成员名n;n; ；JJ struct struct：JJ定义构造体类型的关键字；定义构造体类型的关键字；定义构造体类型的关键字；定义构造体类型的关键字；JJ域：域：域：域：JJ 构造体类型定义中的每构造体类型定义中的每构造体类型定义中的每构造体类型定义中的每1 1个成员；个成员；个成员；个成员；
3、JJ 成员名的命名规那么和成员名的命名规那么和成员名的命名规那么和成员名的命名规那么和变量一样，同一构造体的变量一样，同一构造体的变量一样，同一构造体的变量一样，同一构造体的同层成员不可同名。同层成员不可同名。同层成员不可同名。同层成员不可同名。 例：定义构造体类型例：定义构造体类型studentstruct studentstruct student int num; int num; char name20; char name20; char sex; char sex; int age; int age; float score; float score; char addr30; c
4、har addr30; ; ;num name sex age score addrnum name sex age score addr101 WGJ M 28 88.5 CS101 WGJ M 28 88.5 CSstruct studentstruct student应作为一个应作为一个应作为一个应作为一个整体对待，整体对待，整体对待，整体对待，“;“;号不能少号不能少号不能少号不能少! !10.1.2 定义构造体类型变量的定义定义构造体类型变量的定义一、先定义构造体类型再定义变量名一、先定义构造体类型再定义变量名方式：方式： struct 构造体名构造体名 构造体变量名表构造体变量名表
5、 例：在前面已定义构造体类型例：在前面已定义构造体类型struct student 那么可定义：那么可定义：struct student stu1,stu2; stu1,stu2即为即为struct student类型的变量类型的变量二、在定义类型的同时二、在定义类型的同时二、在定义类型的同时二、在定义类型的同时 定义变量定义变量定义变量定义变量普通方式为：普通方式为：普通方式为：普通方式为：struct struct 构造体名构造体名构造体名构造体名 成员表列成员表列成员表列成员表列 变量名表列变量名表列变量名表列变量名表列; ;struct studentstruct student in
6、t num; int num; char name20; char name20; char sex; char sex; int age; int age; float score; float score; char addr30; char addr30; student1,student2; student1,student2;三、直接定义构造类型三、直接定义构造类型三、直接定义构造类型三、直接定义构造类型 的变量的变量的变量的变量普通方式为：普通方式为：普通方式为：普通方式为：structstruct 成员表列成员表列成员表列成员表列 变量名表列变量名表列变量名表列变量名表列; ;
7、* * 不出现构造体名不出现构造体名不出现构造体名不出现构造体名structint num; char name20; char sex; int age; float score; char addr30; student1,student2;10.1.3 构造体类型的嵌套构造体类型的嵌套定义：构造体成员又是一个构造体变量定义：构造体成员又是一个构造体变量定义：构造体成员又是一个构造体变量定义：构造体成员又是一个构造体变量例例例例: struct date int month; int day; int year;: struct date int month; int day; int y
8、ear; struct student struct student char name20; char name20; char sex; char sex; int age; int age; struct date birthday; struct date birthday; stu1,stu2; stu1,stu2; 嵌套构造体变量的援用：点标志法，但只能对嵌套构造体变量的援用：点标志法，但只能对嵌套构造体变量的援用：点标志法，但只能对嵌套构造体变量的援用：点标志法，但只能对最低成员进展赋值或存取、运算。最低成员进展赋值或存取、运算。最低成员进展赋值或存取、运算。最低成员进展赋值或存
9、取、运算。 例：例：例：例：stu1.age=20;stu1.age=20; stu1.dirthday.month=7; stu1.dirthday.month=7; stu1.dirthday.day=31; stu1.dirthday.day=31; 思索以下的援用思索以下的援用思索以下的援用思索以下的援用 printf(“%d%d%d printf(“%d%d%d,stu1.birthday);(,stu1.birthday);( ) ) stu1.birthday=12, 31, 1988 ; ( stu1.birthday=12, 31, 1988 ; ( ) )10.2 构造体类
10、型变量援用与初始化构造体类型变量援用与初始化10.2.1 10.2.1 援用援用援用援用 不能将一个构造体变量作为一个整体进展输入不能将一个构造体变量作为一个整体进展输入不能将一个构造体变量作为一个整体进展输入不能将一个构造体变量作为一个整体进展输入和输出，只能对各个成员分别输入输出和输出，只能对各个成员分别输入输出和输出，只能对各个成员分别输入输出和输出，只能对各个成员分别输入输出例如：例如：例如：例如：printf(printf(%d,%s,%c,%d,%f,%sn%d,%s,%c,%d,%f,%sn,student1);(,student1);( ) )援用：援用：援用：援用： stud
11、ent1.num=102;( student1.num=102;( ) )成员的援用方式为：构造体变量名成员的援用方式为：构造体变量名成员的援用方式为：构造体变量名成员的援用方式为：构造体变量名. . 成员名成员名成员名成员名 留意：成员运算符留意：成员运算符留意：成员运算符留意：成员运算符. . 在一切运算符中优先级最高在一切运算符中优先级最高在一切运算符中优先级最高在一切运算符中优先级最高构造体变量援用方法：构造体变量援用方法：structclockstructclockinthour,minute,second;inthour,minute,second;structdatestruct
12、dateintyear,month,day;intyear,month,day;structclocktime;structclocktime;today,nextday;today,nextday;1.1.单独援用构造体变量的成员单独援用构造体变量的成员单独援用构造体变量的成员单独援用构造体变量的成员 today.year=2019;today.year=2019;today.time.second=15;today.time.second=15;2.2.构造体变量作为一个整体援用构造体变量作为一个整体援用构造体变量作为一个整体援用构造体变量作为一个整体援用 nextday=today;ne
13、xtday=today;10.2.2 构造体类型变量的初始化构造体类型变量的初始化定义时初始化：将各元素初值放在定义时初始化：将各元素初值放在“ 里赋值给变量。里赋值给变量。例：例： struct student char name20; char sex; int age; float score; stu1, stu2=“Wangwu,m,20,88.5;10.3 构造体与数组构造体与数组10.3.110.3.1构造体数组变量的定义构造体数组变量的定义构造体数组变量的定义构造体数组变量的定义 与构造体变量定义类似，只是构造体变量名现为与构造体变量定义类似，只是构造体变量名现为与构造体变量定
14、义类似，只是构造体变量名现为与构造体变量定义类似，只是构造体变量名现为构造体数组变量名构造体数组变量名构造体数组变量名构造体数组变量名如：如：如：如： struct student struct student int num; int num; char name20; char name20; char sex; char sex; int age; int age; float score; float score; stu30; stu30;J数组各元素在内存中数组各元素在内存中数组各元素在内存中数组各元素在内存中延续存放，如右图所延续存放，如右图所延续存放，如右图所延续存放，如右图所
15、示。示。示。示。stu0stu0stu1stu1stu2stu2101101“ “WGJ”WGJ” MM282888.588.5“CS”“CS”102102“ “DYH”DYH” FF262688.088.0“ “CS”CS”103103“ “DYC”DYC” MM242478.578.5“ “CS”CS”10.3.2构造体数组变量的初始化与援用构造体数组变量的初始化与援用J初始化：数组初始化：数组初始化：数组初始化：数组=初值表列初值表列初值表列初值表列; ;J援用：援用：援用：援用： 构造体数组分量构造体数组分量构造体数组分量构造体数组分量 . . 构造体成员构造体成员构造体成员构造体成员
16、struct studentstruct student int num; int num; char name20; char name20; char sex; char sex; int age; int age; float score; float score; char addr30; char addr30; stu3=101, stu3=101,WGJWGJ,M,28,88.5,“CS,M,28,88.5,“CS, , 102, 102,DYHDYH,F,26,88.0,F,26,88.0,CSCS, , 103, 103,DYCDYC,M,24,78.5,M,24,78.5,
17、CZCZ;构造体数组程序举例构造体数组程序举例【例【例10-5】计算一个班学生的三门课程的】计算一个班学生的三门课程的平均成果，并输出该班学生姓名及平均平均成果，并输出该班学生姓名及平均成果。成果。 程序见下页。程序见下页。程序#include#include#defineMAXSIZE100#defineMAXSIZE100structstudentstructstudentcharname16;/*charname16;/*学生姓名学生姓名学生姓名学生姓名*/ */intgrade3,average;/*intgrade3,average;/*三门成果，平均分三门成果，平均分三门成果，平均
18、分三门成果，平均分*/ */;程序voidmain()voidmain()inti,j,num,s;inti,j,num,s;structstudentstuMAXSIZE;structstudentstuMAXSIZE;printf(Enternumberofstudents:);printf(Enternumberofstudents:);scanf(%d,&num);scanf(%d,&num);for(i=0;inum;i+)for(i=0;inum;i+)printf(Entername:);printf(Entername:);scanf(%s,stui.name);scanf(%
19、s,stui.name);printf(Enterthegrades(3):);printf(Enterthegrades(3):);for(j=0,s=0;j3;j+)for(j=0,s=0;j3;j+)scanf(%d,&stui.gradej);scanf(%d,&stui.gradej);s=s+stui.gradej;s=s+stui.gradej;stui.average=s/3;stui.average=s/3;for(i=0;inum;i+)for(i=0;i-成员名成员名成员名成员名: pst-num=1001;: pst-num=1001;: pst-num=1001;:
20、pst-num=1001;留意：留意：留意：留意：pstpstpstpst不能指向成员：不能指向成员：不能指向成员：不能指向成员：pst=&stu1.numpst=&stu1.numpst=&stu1.numpst=&stu1.num非法非法非法非法; ; ; ; 但是但是但是但是: int *q; q=&stu1.num: int *q; q=&stu1.num: int *q; q=&stu1.num: int *q; q=&stu1.num合法合法合法合法【例【例10-610-6】用指向构造体变量的指针来访】用指向构造体变量的指针来访问学生的各项数据。问学生的各项数据。#includes
21、tring.h#includestring.hstructstustructstuintnum;intnum;char*name;char*name;charsex;charsex;floatscore;floatscore;boy=102,Zhangping,M,78.5,*p;boy=102,Zhangping,M,78.5,*p; voidmain()voidmain()p=&boy;p=&boy;printf(Number=%dnName=%sn,boy.num,boy.name);printf(Number=%dnName=%sn,boy.num,boy.name);printf(S
22、ex=%cnScore=%4.1fnn,boy.sex,boy.score);printf(Sex=%cnScore=%4.1fnn,boy.sex,boy.score);printf(Number=%dnName=%sn,(*p).num,(*p).name);printf(Number=%dnName=%sn,(*p).num,(*p).name);printf(Sex=%cnScore=%4.1fnn,(*p).sex,(*p).score);printf(Sex=%cnScore=%4.1fnn,(*p).sex,(*p).score);printf(Number=%dnName=%s
23、n,p-num,p-name);printf(Number=%dnName=%sn,p-num,p-name);printf(Sex=%cnScore=%4.1fnn,p-sex,p-score);printf(Sex=%cnScore=%4.1fnn,p-sex,p-score); 10.4.2指向构造体数组的指针指向构造体数组的指针 例例例例10-7 10-7 输出数组中各元素中各成员的值。输出数组中各元素中各成员的值。输出数组中各元素中各成员的值。输出数组中各元素中各成员的值。struct studentstruct student int num; int num; char name
24、20; char name20; char sex; char sex; int age; int age; ; ; struct student stu3 struct student stu3 =10101,Zhang,M,18, =10101,Zhang,M,18, 10102,Li,M,19, 10102,Li,M,19, 10103,Wang,F,20; 10103,Wang,F,20;/ /续续续续stu0stu0P Pstu1stu1PPstu2stu2P P1010110101“ “ZhangZhang” ” MM18181010210102“ “Li”Li” MM191910
25、10310103“ “WangWang” ” FF2020main() /*main() /*续上页续上页续上页续上页*/*/ struct student *p; struct student *p; printf(No. Name Sex Agen); printf(No. Name Sex Agen); for (p=stu; pstu+3; p+) for (p=stu; pnum, p-name, p-num, p-name, p-sex, p-age); p-sex, p-age); stu0stu0P Pstu1stu1PPstu2stu2P P1010110101“ “Zhan
26、gZhang” ” MM18181010210102“ “Li”Li” MM19191010310103“ “WangWang” ” FF2020本卷须知本卷须知:假设假设假设假设p p的初值为的初值为的初值为的初值为stustu，即指向构造体数组的第，即指向构造体数组的第，即指向构造体数组的第，即指向构造体数组的第1 1个个个个元素元素元素元素stu0stu0，那么，那么，那么，那么p+1p+1指向下指向下指向下指向下1 1个元素的起始地个元素的起始地个元素的起始地个元素的起始地址址址址stu1stu1。区别：区别：区别：区别：(+p)-num (+p)-num 和和和和 (p+)-num
27、(p+)-nump p已定义为指向已定义为指向已定义为指向已定义为指向struct studentstruct student类型的指针变量，类型的指针变量，类型的指针变量，类型的指针变量，那么那么那么那么p p只能指向只能指向只能指向只能指向1 1个构造体类型数据，而不能指个构造体类型数据，而不能指个构造体类型数据，而不能指个构造体类型数据，而不能指向构造体类型的某一成员即向构造体类型的某一成员即向构造体类型的某一成员即向构造体类型的某一成员即p p的地址不是成的地址不是成的地址不是成的地址不是成员的地址。员的地址。员的地址。员的地址。如：如：如：如：p=&stu.namep=&stu.na
28、me；( ( 错误错误错误错误) )Go5.3.7Go5.3.710.5 构造体与函数构造体与函数10.5.1构造体变量作为函数的参数构造体变量作为函数的参数将将1个构造体变量的值传送给个构造体变量的值传送给1个函数，个函数，方法有二：方法有二：用构造体变量的成员作参数。用法和普通变用构造体变量的成员作参数。用法和普通变量作实参是一样的，属量作实参是一样的，属“值传送方式。值传送方式。用指向构造体变量用指向构造体变量/数组的指针作实参，将数组的指针作实参，将构造体变量构造体变量/数组的地址传给形参。数组的地址传给形参。10.5.2 用指向构造体的指针作函数参数用指向构造体的指针作函数参数例例
29、编写一个函数，计算指定学生的编写一个函数，计算指定学生的6科平科平均成果，根据平均成果评定登记。均成果，根据平均成果评定登记。构造类型：构造类型：构造类型：构造类型： struct student struct student char name20; char name20; char num10; char num10; float score6; float score6; float ave; float ave; ; ; main() main() struct student a100; struct student a100; int I,j,n; int I,j,n;float
30、 sum;float sum; scanf(“%d scanf(“%d,&n);,&n); for(I=0;In;I+) for(I=0;In;I+) scanf(“%s scanf(“%s, aI.name);, aI.name); scanf(“%s scanf(“%s, aI.num);, aI.num); for(j=0; j6; j+) for(j=0; j6; j+) scanf(“%f scanf(“%f ,&aI.scorej);,&aI.scorej); sum=sum+aI.scorej; sum=sum+aI.scorej; aI.ave=sum/6; aI.ave=su
31、m/6; 将将6门课程数据输入定义为函数门课程数据输入定义为函数input( )，函数的前往值为构外型地址函数的前往值为构外型地址struct student input(void)struct student input(void) struct student stud; struct student stud; int I; float sum int I; float sum scanf(“%s scanf(“%s,stud.name);,stud.name); scanf(“%s scanf(“%s,stud.num);,stud.num); for(I=0;I6;I+) for(I
32、=0;I6;I+)scanf(“%fscanf(“%f,&stud.scoreI);,&stud.scoreI); sum=sum+stud.scoreI; sum=sum+stud.scoreI; Stud.ave=sum/6;Stud.ave=sum/6;return stud;return stud; main()main() struct student a100; struct student a100; int I,j,n; int I,j,n; struct student struct student input(void);input(void); scanf(“%d sca
33、nf(“%d,&n);,&n); for(I=0;In;I+) for(I=0;In;I+) aI=input(); aI=input(); 假设有：假设有：假设有：假设有： struct point int x,y; ;struct point int x,y; ;函数定义如下：函数定义如下：函数定义如下：函数定义如下：void enter(struct point void enter(struct point *p,int n)*p,int n) int I,j; int I,j; for(I=0;In;I+) for(I=0;In;I+) printf(“Enter p%d print
34、f(“Enter p%d,I);,I);scanf(“%d,%dscanf(“%d,%d,&pI.x,&pI.y);,&pI.x,&pI.y); 假设在主控函数中定义了构造假设在主控函数中定义了构造假设在主控函数中定义了构造假设在主控函数中定义了构造体数组：体数组：体数组：体数组：struct point a100;struct point a100;那么调用语句为那么调用语句为那么调用语句为那么调用语句为 enter(a,30); enter(a,30); 10.5.3 构造体类型函数JJ编写程序，查找分数大编写程序，查找分数大编写程序，查找分数大编写程序，查找分数大于或等于于或等于于或等于
35、于或等于9090的学生数据的学生数据的学生数据的学生数据JJ # include # include JJ struct student struct student JJ char name20; char name20;JJ int score; int score;JJ struct student struct student *find(struct student *find(struct student st)st)JJ int I; int I;JJ for(I=0;I4;I+) for(I=0;I=90) if(stI.score=90)JJ return &stI; ret
36、urn &stI;JJ retuen NULL; retuen NULL;JJ JJ main() main() int I; int I; struct student struct student st4,*pst;st4,*pst; for(I=0;I4;I+) for(I=0;Iname,pst- pst-name,pst-score);score); 10.6 链表链表10.6.1概述概述链表存储构造是一种动态数据构造，其特链表存储构造是一种动态数据构造，其特点是它包含的数据对象的个数及其相互点是它包含的数据对象的个数及其相互关系可以按需求改动，存储空间是程序关系可以按需求改动，存储
37、空间是程序根据需求在程序运转过程中向系统恳求根据需求在程序运转过程中向系统恳求获得，链表也不要求逻辑上相邻的元素获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储在物理位置上也相邻，它没有顺序存储构造所具有的弱点。构造所具有的弱点。1链表构造链表构造1 1头指针变量头指针变量头指针变量头指针变量headhead指向链表的首结点。指向链表的首结点。指向链表的首结点。指向链表的首结点。2 2每个结点由每个结点由每个结点由每个结点由2 2个域组成：个域组成：个域组成：个域组成：1 1数据域数据域数据域数据域存储结点本身的信息。存储结点本身的信息。存储结点本身的信息。存储结点本身的信
38、息。2 2指针域指针域指针域指针域指向后继结点的指针。指向后继结点的指针。指向后继结点的指针。指向后继结点的指针。3 3尾尾尾尾结结结结点点点点的的的的指指指指针针针针域域域域置置置置为为为为“NULL“NULL空空空空，作作作作为链表终了的标志为链表终了的标志为链表终了的标志为链表终了的标志QianSunLiZhouWuWangHead7131432537链表构造的定义链表构造的定义structstudentstructstudentcharname10;charname10;structstudent*next;structstudent*next;nextnext为为为为students
39、tudent类型指针变量，指向下一个结点的指类型指针变量，指向下一个结点的指类型指针变量，指向下一个结点的指类型指针变量，指向下一个结点的指针域。针域。针域。针域。结点的变量或指针变量的定义：结点的变量或指针变量的定义：结点的变量或指针变量的定义：结点的变量或指针变量的定义：structstudentnode,*head;structstudentnode,*head;nodenode可以存放一个学生结点可以存放一个学生结点可以存放一个学生结点可以存放一个学生结点指针指针指针指针headhead可以存放学生结点的地址。可以存放学生结点的地址。可以存放学生结点的地址。可以存放学生结点的地址。 动
40、态分配存储空间库函数动态分配存储空间库函数1void *malloc(unsigned int size); malloc在内存的动态存储区中分配一个在内存的动态存储区中分配一个size长度的延续存储空间。长度的延续存储空间。例如：例如：int *p;p=(int *)malloc(8); p指示系统分配的指示系统分配的4个整型存储单元的起始个整型存储单元的起始地址地址也可看成包含也可看成包含4个数组元素的个数组元素的p数组：数组：p0,p1,p2,p32. void free(void *ptr); J函数函数free释放由指针变量释放由指针变量ptr所指示的内所指示的内存区域。存区域。 J
41、例如：例如：free(p); J经过函数经过函数free将已分配的内存区将已分配的内存区域交还系统，使系统可以重新对其进展域交还系统，使系统可以重新对其进展分配。分配。 【例【例10-12】动态定义数组。】动态定义数组。#include#includevoidmain()voidmain()intn,i,*p;intn,i,*p;printf(n=);printf(n=);scanf(%d,&n);scanf(%d,&n);p=(int*)malloc(n*sizeof(int);p=(int*)malloc(n*sizeof(int);for(i=0;in;i+)for(i=0;in;i+)
42、pi=i*i;pi=i*i;for(i=0;in;i+)for(i=0;inext=NULL;p-next=NULL;3 3假设假设假设假设headhead为为为为NULLNULL，那么，那么，那么，那么head=p;head=p;否那么否那么否那么否那么last-next=p;last-next=p;4 4last=p;last=p;5 5反复反复反复反复2 2 4 4，继续建立新结点。，继续建立新结点。，继续建立新结点。，继续建立新结点。2. 头插法建立单链表头插法建立单链表特点特点特点特点: :新产生的结点作为新的链表头插入链表。新产生的结点作为新的链表头插入链表。新产生的结点作为新的链
43、表头插入链表。新产生的结点作为新的链表头插入链表。操作步骤：操作步骤：操作步骤：操作步骤：1 1head=NULL;head=NULL;2 2生成新结点，指针变量生成新结点，指针变量生成新结点，指针变量生成新结点，指针变量p p指向该结点；指向该结点；指向该结点；指向该结点；3 3p-next=head;head=p;p-next=head;head=p;4 4反复反复反复反复2 2 3 3，继续生成下一个链表结，继续生成下一个链表结，继续生成下一个链表结，继续生成下一个链表结点。点。点。点。 10.6.3 链表的访问链表的访问1.输出链表结点输出链表结点操作步骤：操作步骤：1得到链表头结点的
44、地址得到链表头结点的地址head；2指针变量指针变量p=head;3输出输出p所指结点的成员值所指结点的成员值;4p后移一个结点，后移一个结点，p=p-next;5反复反复34，直到链表为空。，直到链表为空。2. 统计链表结点的个数统计链表结点的个数普通情况下，各个单链表中结点个数是随机的，普通情况下，各个单链表中结点个数是随机的，普通情况下，各个单链表中结点个数是随机的，普通情况下，各个单链表中结点个数是随机的，要想知道表中结点数目，必需从表头开场访要想知道表中结点数目，必需从表头开场访要想知道表中结点数目，必需从表头开场访要想知道表中结点数目，必需从表头开场访问到表尾，逐个统计出结点数目。
45、问到表尾，逐个统计出结点数目。问到表尾，逐个统计出结点数目。问到表尾，逐个统计出结点数目。 3. 3. 查找链表的某个结点查找链表的某个结点查找链表的某个结点查找链表的某个结点在链表上查找符合某个条件的结点，也必需从在链表上查找符合某个条件的结点，也必需从在链表上查找符合某个条件的结点，也必需从在链表上查找符合某个条件的结点，也必需从链表头开场访问链表。链表头开场访问链表。链表头开场访问链表。链表头开场访问链表。 10.6.4 链表的插入操作链表的插入操作 在第在第在第在第n n个结点之后插入个结点之后插入个结点之后插入个结点之后插入1 1个新结点个新结点个新结点个新结点, ,插入操作步骤：插
46、入操作步骤：插入操作步骤：插入操作步骤：1 1q q指针指向新结点，指针指向新结点，指针指向新结点，指针指向新结点，i i为已访问过的结点数；为已访问过的结点数；为已访问过的结点数；为已访问过的结点数；2 2p=headp=head，r r指向指向指向指向p p结点的前一个结点；结点的前一个结点；结点的前一个结点；结点的前一个结点；3 3i+i+，r=pr=p，p=p-nextp=p-next，p p结点往前挪动一个结点；结点往前挪动一个结点；结点往前挪动一个结点；结点往前挪动一个结点；4 4假设假设假设假设ininext=headq-next=head，head=q;head=q;6 6假设
47、假设假设假设ininext=qr-next=q，q-q-next=NULL;next=NULL;7 7否那么，将否那么，将否那么，将否那么，将q q结点插入到第结点插入到第结点插入到第结点插入到第n n个结点之后，即插入到个结点之后，即插入到个结点之后，即插入到个结点之后，即插入到r r结点与结点与结点与结点与p p结点之间：结点之间：结点之间：结点之间：r-next=qr-next=q，q-next=p;q-next=p;8 8前往链表头前往链表头前往链表头前往链表头headhead。图10-7 将指针q所指结点插入第n个结点之后(b) 插入到第2个结点之后Headp101Zhang9010
48、3Wang80NULL105Li70(a) head指示已有链表，q指示待插入结点 q101Zhao70Headr101Zhang90q104Zhao60103Wang80pNULL105Li7010.6.5 链表的删除操作链表的删除操作 删除第删除第删除第删除第n n个结点个结点个结点个结点 1 1p=headp=head，q q指针指向指针指向指针指向指针指向p p所指结点的前所指结点的前所指结点的前所指结点的前1 1个结点；个结点；个结点；个结点；2 2i i为访问过的结点数目；为访问过的结点数目；为访问过的结点数目；为访问过的结点数目；3 3i+i+，q=pq=p，p=p-nextp=
49、p-next，p p、q q挪动挪动挪动挪动1 1个结点；个结点；个结点；个结点；4 4假设假设假设假设p!=NULLp!=NULL且且且且in-1inext;head=head-next;6 6假设假设假设假设head=NULLhead=NULL，链表为空，不能删除；，链表为空，不能删除；，链表为空，不能删除；，链表为空，不能删除；7 7假设假设假设假设p=NULLp=NULL，第，第，第，第n n个结点不存在，不能删除；个结点不存在，不能删除；个结点不存在，不能删除；个结点不存在，不能删除；8 8找到第找到第找到第找到第n n个结点，删除个结点，删除个结点，删除个结点，删除p p结点：结点：结点：结点：q-next=p-next;pq-next=p-next;p的前的前的前的前1 1个结点的个结点的个结点的个结点的nextnext值赋值为值赋值为值赋值为值赋值为p p的的的的nextnext域；域；域；域；9 9前往前往前往前往headhead。 图10-9 删除第n个结点(a) head指示已有链表Headp101Zhang90103Wang80NULL105Li60101Zhao70(b) 删除第3个结点qpHead101Zhang90103Wang80NULL105Li60101Zhao70
