《第10章结构体与链表》由会员分享,可在线阅读,更多相关《第10章结构体与链表(46页珍藏版)》请在金锄头文库上搜索。
1、第第10章章 结构体与链表结构体与链表10.1 结构体类型的定义与变量说明结构体类型的定义与变量说明10.2 结构体类型变量的引用结构体类型变量的引用10.3 结构体与数组结构体与数组10.4 结构体与指针结构体与指针10.5 结构体与函数结构体与函数10.6 链表链表皮疆禹莱鲸水锅戒尾钱缠牟帧蜕诽柳匈昭浊务彦偷憾隘姿农馁能漠肤昌蚌第10章结构体与链表第10章结构体与链表 10.1 结构体类型的定义与变量说明结构体类型的定义与变量说明10.1.110.1.1结构体类型的定义结构体类型的定义结构体类型的定义结构体类型的定义结构体是具有不同类型的数据的有序集合结构体是具有不同类型的数据的有序集合结
2、构体是具有不同类型的数据的有序集合结构体是具有不同类型的数据的有序集合结构体是具有不同类型的数据的有序集合结构体是具有不同类型的数据的有序集合结构体定义:结构体定义:结构体定义:结构体定义:struct struct struct 结构体类型名结构体类型名结构体类型名结构体类型名结构体类型名结构体类型名 类型标识符类型标识符类型标识符类型标识符类型标识符类型标识符 成员名成员名成员名成员名成员名成员名1;1;1; 类型标识符类型标识符类型标识符类型标识符类型标识符类型标识符 成员名成员名成员名成员名成员名成员名2;2;2; 类型标识符类型标识符类型标识符类型标识符类型标识符类型标识符 成员名成
3、员名成员名成员名成员名成员名n;n;n; ;JJ struct struct:定义结构体类型的关键字;定义结构体类型的关键字;定义结构体类型的关键字;定义结构体类型的关键字;JJ域:域:域:域: 结构体类型定义中的每结构体类型定义中的每结构体类型定义中的每结构体类型定义中的每1 1个成员;个成员;个成员;个成员; 成员名的命名规则和变量成员名的命名规则和变量成员名的命名规则和变量成员名的命名规则和变量相同,同一结构体的同层相同,同一结构体的同层相同,同一结构体的同层相同,同一结构体的同层成员不可同名。成员不可同名。成员不可同名。成员不可同名。 丙纬忱们仔入赂羹柞癸剥箍寨铱璃浊湖犊快署余咒玉呈头
4、抵觅趣趟瑚炉嘱第10章结构体与链表第10章结构体与链表例:定义结构体类型例:定义结构体类型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; char addr30; ; ;num name sex age score addrnum name sex age score addr101 WGJ M 28 88.5 CS101 WGJ
5、M 28 88.5 CSstruct studentstruct student应作为一个应作为一个应作为一个应作为一个整体对待,整体对待,整体对待,整体对待,“;”“;”“;”“;”号不能少号不能少号不能少号不能少! ! ! !殉醉接瀑察笆右晴窄渊踞甩终斋扭记顽挞醇衫斩允憋刘铆沦鳖拳涅蚤鞘并第10章结构体与链表第10章结构体与链表10.1.2 定义结构体类型变量的定义定义结构体类型变量的定义一、先定义结构体类型再定义变量名一、先定义结构体类型再定义变量名形式:形式: struct 结构体名结构体名 结构体变量名表结构体变量名表 例:例:在前面已定义结构体类型在前面已定义结构体类型struct
6、 student 则可定义:则可定义:struct student stu1,stu2; stu1,stu2即为即为struct student类型的变量类型的变量觅态姓绍淖诞畏爆搐汕棋诀抵陌狂臀饿稚悼橱蔑乘释净躁收休羚闺锥参罐第10章结构体与链表第10章结构体与链表二、在定义类型的同时二、在定义类型的同时 定义变量定义变量一般形式为:一般形式为:struct 结构体名结构体名 成员表列成员表列 变量名表列变量名表列;struct student int num; char name20; char sex; int age; float score; char addr30; student
7、1,student2;堰烛毁诅咒斟慎惯付黑副艘麓咐斤摇鞘取男熬向签啼淳啪鳖杠逻兹困窟镰第10章结构体与链表第10章结构体与链表三、直接定义结构类型三、直接定义结构类型 的变量的变量一般形式为:一般形式为:struct 成员表列成员表列 变量名表列变量名表列; * 不出现结构体名不出现结构体名structint num; char name20; char sex; int age; float score; char addr30; student1,student2;吟党挤垛根欣琴墟臭悉悉销佐抱厨袁撂闺区熬盗然鞋衬揉淄移巾当该釜燃第10章结构体与链表第10章结构体与链表10.1.3 结构体类
8、型的嵌套结构体类型的嵌套定义:结构体成员又是一个结构体变量定义:结构体成员又是一个结构体变量例例: struct date int month; int day; int year; struct student char name20; char sex; int age; struct date birthday; stu1,stu2;暗牲芥退充汽厄矮慈岳恿钓钵锰颇蛆姐彩嗓押屡竹梗致寅荫谓诉蹭踊夯鱼第10章结构体与链表第10章结构体与链表 嵌套结构体变量的引用:点标记法,但只能对嵌套结构体变量的引用:点标记法,但只能对最低成员进行赋值或存取、运算。最低成员进行赋值或存取、运算。 例:例:s
9、tu1.age=20; stu1.dirthday.month=7; stu1.dirthday.day=31;B 思考以下的引用思考以下的引用思考以下的引用思考以下的引用 printf(“%d%d%d”,stu1.birthday);( printf(“%d%d%d”,stu1.birthday);( ) ) stu1.birthday=12, 31, 1988 ; ( stu1.birthday=12, 31, 1988 ; ( ) )第墒现搂戚酉考衰倡荣腻罚扒绝抵氨酶疼垦苹秒滑莱婚瘪樊思非临琅芬政第10章结构体与链表第10章结构体与链表10.2 结构体类型变量引用与初始化结构体类型变量引
10、用与初始化10.2.1 引用引用 不能不能将一个结构体变量作为将一个结构体变量作为一个整体一个整体进行输入进行输入和输出,只能对和输出,只能对各个成员分别输入输出各个成员分别输入输出例如:例如:printf(”%d,%s,%c,%d,%f,%sn”,student1);( )引用:引用: student1.num=102;( )成员的引用方式为:结构体变量名成员的引用方式为:结构体变量名. 成员名成员名 注意:注意:成员运算符成员运算符. 在所有运算符中优先级在所有运算符中优先级最高最高扁袁劲弹游邮列凋肄寥杖海慈是誊搐途公耕百念扰孽寇崩恼什节留佐炬凉第10章结构体与链表第10章结构体与链表结构
11、体变量引用方法:结构体变量引用方法:structclockinthour,minute,second;structdateintyear,month,day;structclocktime;today,nextday;1. 1. 单独引用结构体变量的成员单独引用结构体变量的成员单独引用结构体变量的成员单独引用结构体变量的成员 today.year=2004;today.year=2004;today.time.second=15;today.time.second=15; 2. 2. 结构体变量作为一个整体引用结构体变量作为一个整体引用结构体变量作为一个整体引用结构体变量作为一个整体引用 ne
12、xtday=today;nextday=today;社捷绊炭伶季方藻字龄樟来辰梆跪橡宛茄幽侗蔚孰怀恋顾蕴呕缀浆柒畜持第10章结构体与链表第10章结构体与链表10.2.2 结构体类型变量的初始化结构体类型变量的初始化定义时初始化:将各元素初值放在定义时初始化:将各元素初值放在“ ”里里赋值给变量。赋值给变量。例:例: struct student char name20; char sex; int age; float score; stu1, stu2=“Wangwu”,m,20,88.5;疟潘臭缺黄湛币璃成遣杖诌楷萨佩垮苔枫桔今甥酣驶俺俺绚请撰跪颤横芍第10章结构体与链表第10章结构体与链
13、表10.3 结构体与数组结构体与数组10.3.1结构体数组变量的定义结构体数组变量的定义 与与结构体变量定义类似,只是结构体变量名结构体变量定义类似,只是结构体变量名现为结构体数组变量名现为结构体数组变量名如:如: 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;狂态海属娠袁旭亩保颗翟空周士吱闺柯拜饭俊授灶欢胸鹃恿茎碉茂帝纠栽第10章结构体与链
14、表第10章结构体与链表J数组各元素在内存中数组各元素在内存中连续存放,如右图所连续存放,如右图所示。示。stu0stu0stu1stu1stu2stu2101“WGJ”M2888.5“CS”102“DYH”F2688.0“CS”103“DYC”M2478.5“CS”全趟羊标赡绦仍烘穴执肤亮共顶磋衫嗣赴穆拖瞳厅桔给忧霞夸俱四皋听属第10章结构体与链表第10章结构体与链表10.3.2结构体数组变量的初始化与引用结构体数组变量的初始化与引用J初始化:数组初始化:数组=初值表列初值表列;J引用:引用: 结构体数组分量结构体数组分量 . 结构体成员结构体成员struct studentstruct st
15、udent 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,”WGJ”,M,28,88.5,“CS”, stu3=101,”WGJ”,M,28,88.5,“CS”, 102,”DYH”,F,26,88.0,”CS”, 102,”DYH”,F,26,88.0,”CS”, 103,”DYC”,M,24,78.5,”CZ”; 103,”DYC”,M,24,78.5,
16、”CZ”;湍懈姜雇教搂匪百椎躲至铸把铆旦乡另国喧情毒嘱辜亩聚宋宣耘李诡全椒第10章结构体与链表第10章结构体与链表结构体数组程序举例结构体数组程序举例【例【例10-5】计算一个班学生的三门课程的】计算一个班学生的三门课程的平均成绩,并输出该班学生姓名及平均平均成绩,并输出该班学生姓名及平均成绩。成绩。 程序见下页。程序见下页。虽饶抚希善呸骏豌赘涎澜障择琵剃鼎揍挂十盎修讶拦琢秤蚜筋衙檄寐彭今第10章结构体与链表第10章结构体与链表程序#include#defineMAXSIZE100structstudentcharname16;/*学生姓名学生姓名*/intgrade3,average;/*三
17、门成绩,平均分三门成绩,平均分*/;雇蔬械瘪合髓滦曹冶影猪童域陀兽汀件氟抢膨狞愁掸曰诧拿园陨鸵晰孟焚第10章结构体与链表第10章结构体与链表程序voidmain()inti,j,num,s;structstudentstuMAXSIZE;printf(Enternumberofstudents:);scanf(%d,&num);for(i=0;inum;i+)printf(Entername:);scanf(%s,stui.name);printf(Enterthegrades(3):);for(j=0,s=0;j3;j+)scanf(%d,&stui.gradej);s=s+stui.gra
18、dej;stui.average=s/3;for(i=0;i-成员名成员名成员名成员名: pst-num=1001;: pst-num=1001;: pst-num=1001;: pst-num=1001;BB注意注意注意注意: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 *
19、q; q=&stu1.num合法合法合法合法蛇付阎费糜悲刹时蹦期攘啄扳崖睬表变吼涛佐挝仆骄腿瘸挠懒兰熟腑惋璃第10章结构体与链表第10章结构体与链表【例【例10- -6】用指向结构体变量的指针来访用指向结构体变量的指针来访问学生的各项数据。问学生的各项数据。#includestring.hstructstuintnum;char*name;charsex;floatscore;boy=102,Zhangping,M,78.5,*p;赦碍铅勺趴翠璃阮蒂踊框某步缝潮雏壹缅樊俘纲锹吠置渍贺赊辱缝澈茵媚第10章结构体与链表第10章结构体与链表 voidmain()p=&boy;printf(Numbe
20、r=%dnName=%sn,boy.num,boy.name);printf(Sex=%cnScore=%4.1fnn,boy.sex,boy.score);printf(Number=%dnName=%sn,(*p).num,(*p).name);printf(Sex=%cnScore=%4.1fnn,(*p).sex,(*p).score);printf(Number=%dnName=%sn,p-num,p-name);printf(Sex=%cnScore=%4.1fnn,p-sex,p-score);牡带枕轮扣椰闲层秩万酉酷畸饿获各蔽脂缝渺旺鹅眉陌拖督粗罚焉牲试灰第10章结构体与链表第
21、10章结构体与链表10.4.2指向结构体数组的指针指向结构体数组的指针例例10-7 输出数组中各元素中各成员的值。输出数组中各元素中各成员的值。struct student int num; char name20; char sex; int age; ; struct student stu3 =10101,Zhang,M,18, 10102,Li,M,19, 10103,Wang,F,20;/续续stu0stu0P Pstu1stu1PPstu2stu2P”P”10101“Zhang”M1810102“Li”M1910103“Wang”F20砾辰霹陌狰爹阶贰隆堕琐型践婚堆冻售吭复入住景练
22、斯观妮狙严蒂鬃舒浊第10章结构体与链表第10章结构体与链表main() /*续上页续上页*/ struct student *p; printf(No. Name Sex Agen); for (p=stu; pnum, p-name, p-sex, p-age); stu0stu0P Pstu1stu1PPstu2stu2P”P”10101“Zhang”M1810102“Li”M1910103“Wang”F20削讳份蟹磕相泡抱孩耪淄旬硝蕾浮蹈傍垦整池谢湖童瘴气据干粱朝院勾迸第10章结构体与链表第10章结构体与链表注意事项注意事项:如果如果p的初值为的初值为stu,即指向结构体数组的第,即指向
23、结构体数组的第1个个元素元素stu0,则,则p+1指向下指向下1个元素的起始地址个元素的起始地址stu1。区别:区别:(+p)- -num 和和 (p+)- -nump p已定义为指向已定义为指向已定义为指向已定义为指向struct studentstruct student类型的指针变量,类型的指针变量,类型的指针变量,类型的指针变量,则则则则p p只能指向只能指向只能指向只能指向1 1个结构体类型数据,而不能指向个结构体类型数据,而不能指向个结构体类型数据,而不能指向个结构体类型数据,而不能指向结构体类型的某一成员(即结构体类型的某一成员(即结构体类型的某一成员(即结构体类型的某一成员(即
24、p p的地址不是成员的地址不是成员的地址不是成员的地址不是成员的地址)。的地址)。的地址)。的地址)。如:如:如:如:p=&stu.namep=&stu.name;( ( 错误错误错误错误) )Go5.3.7Go5.3.7河售貉醇争豌癸儡著被晌必锚漓膘沮后统每攻笑毯隋惫图冀剁烷魔弹淳弓第10章结构体与链表第10章结构体与链表10.5 结构体与函数结构体与函数10.5.1结构体变量作为函数的参数结构体变量作为函数的参数将将1个结构体变量的值传递给个结构体变量的值传递给1个函数,个函数,方法有二:方法有二:B用结构体变量的成员作参数。用法和普用结构体变量的成员作参数。用法和普通变量作实参是一样的,
25、属通变量作实参是一样的,属“值传递值传递”方式。方式。B用指向结构体变量用指向结构体变量/数组的指针作实参,数组的指针作实参,将结构体变量将结构体变量/数组的地址传给形参。数组的地址传给形参。黔旅车弟她仑舞予帛茶忙列迭巳法招凶苏贿芬滇炔划租访锄合梢塌公配邻第10章结构体与链表第10章结构体与链表10.5.2 用指向结构体的指针作函数参数用指向结构体的指针作函数参数例 编写一个函数,计算指定学生的编写一个函数,计算指定学生的6科平科平均成绩,根据平均成绩评定登记。均成绩,根据平均成绩评定登记。结构类型:结构类型:结构类型:结构类型: struct student struct student c
26、har name20; char name20; char num10; char num10; float score6; float score6; float ave; float ave; ; ;元琴唯绘混哆饥蒂淌票强瑞枚送嫂圃模敬她之精嗡带辑最隧馁控缅从快床第10章结构体与链表第10章结构体与链表 main() struct student a100; int I,j,n;float sum; scanf(“%d”,&n); for(I=0;In;I+) scanf(“%s”, aI.name); scanf(“%s”, aI.num); for(j=0; j6; j+) scanf
27、(“%f ”,&aI.scorej); sum=sum+aI.scorej; aI.ave=sum/6; 巩爷求升厉搽寒白斤行韵匠虽排谗疵吹搐阮汐趾蜂穷氓舷栅秉骆羞埋靖障第10章结构体与链表第10章结构体与链表将将6门课程数据输入定义为函数门课程数据输入定义为函数input( ),函数的返回值为结构型地址函数的返回值为结构型地址struct student input(void) struct student stud; int I; float sum scanf(“%s”,stud.name); scanf(“%s”,stud.num); for(I=0;I6;I+)scanf(“%f”,
28、&stud.scoreI); sum=sum+stud.scoreI; Stud.ave=sum/6;return stud; main() struct student a100; int I,j,n; struct student input(void); scanf(“%d”,&n); for(I=0;In;I+) aI=input();秀师胞中便跑价锐刮钦吱疆团国绝毋解泽瞪帮攀拙溜脸壁闰拭匿恳驾廷惮第10章结构体与链表第10章结构体与链表 假设有:假设有: struct point int x,y; ;函数定义如下:函数定义如下:void enter(struct point *p,i
29、nt n) int I,j; for(I=0;In;I+) printf(“Enter p%d”,I);scanf(“%d,%d”,&pI.x,&pI.y); 如果在主控函数中定义了结构如果在主控函数中定义了结构体数组:体数组:struct point a100;则调用语句为则调用语句为 enter(a,30); 诊悔嚏天络币场迢证早剪昌烦蜜磁骋或抠祁媒宇丽浸饶衅算雌笑辖列供帅第10章结构体与链表第10章结构体与链表10.5.3 结构体类型函数J编写程序,查找分数大编写程序,查找分数大于或等于于或等于90的学生数据的学生数据 # include struct student char name
30、20; int score; struct student *find(struct student st) int I; for(I=0;I=90) return &stI; retuen NULL; main() int I; struct student st4,*pst; for(I=0;Iname,pst-score);市狗泉经炮盐卯刹乾襄似栗笨懈魁岔道猴文武闭断评擒矢宅机靖忱芳猾驼第10章结构体与链表第10章结构体与链表10.6 链表链表10.6.1概述概述 链表存储结构是一种动态数据结构,其特点链表存储结构是一种动态数据结构,其特点链表存储结构是一种动态数据结构,其特点链表存储结
31、构是一种动态数据结构,其特点是它包含的数据对象的个数及其相互关系可是它包含的数据对象的个数及其相互关系可是它包含的数据对象的个数及其相互关系可是它包含的数据对象的个数及其相互关系可以按需要改变,存储空间是程序根据需要在以按需要改变,存储空间是程序根据需要在以按需要改变,存储空间是程序根据需要在以按需要改变,存储空间是程序根据需要在程序运行过程中向系统申请获得,链表也不程序运行过程中向系统申请获得,链表也不程序运行过程中向系统申请获得,链表也不程序运行过程中向系统申请获得,链表也不要求逻辑上相邻的元素在物理位置上也相邻,要求逻辑上相邻的元素在物理位置上也相邻,要求逻辑上相邻的元素在物理位置上也相
32、邻,要求逻辑上相邻的元素在物理位置上也相邻,它没有顺序存储结构所具有的弱点。它没有顺序存储结构所具有的弱点。它没有顺序存储结构所具有的弱点。它没有顺序存储结构所具有的弱点。 观祷声藻们形票驼沼描胯摈呻旺忧驼白肝希氓贮将霄敖籽锐剂衔嵌神耕学第10章结构体与链表第10章结构体与链表1链表结构链表结构(1)头指针变量)头指针变量head指向链表的首结点。指向链表的首结点。(2)每个结点由)每个结点由2个域组成:个域组成:1)数据域)数据域存储结点本身的信息。存储结点本身的信息。2)指针域)指针域指向后继结点的指针。指向后继结点的指针。(3)尾尾结结点点的的指指针针域域置置为为“NULL(空空)”,作
33、作为为链表结束的标志链表结束的标志QianSunLiZhouWuWangHead7131432537史谬指硝彼先流村紊掷萧罐襄诱寇瑶倒琳沥芥武旭琶编戴酬靶宏钻范径娜第10章结构体与链表第10章结构体与链表链表结构的定义链表结构的定义structstudentcharname10;structstudent*next;JJnextnext为为为为studentstudent类型指针变量,指向下一个结点的指类型指针变量,指向下一个结点的指类型指针变量,指向下一个结点的指类型指针变量,指向下一个结点的指针域。针域。针域。针域。JJ结点的变量或指针变量的定义:结点的变量或指针变量的定义:结点的变量或指
34、针变量的定义:结点的变量或指针变量的定义:structstudentnode,*head;structstudentnode,*head;BBnodenode可以存放一个学生结点可以存放一个学生结点可以存放一个学生结点可以存放一个学生结点BB指针指针指针指针headhead可以存放学生结点的地址。可以存放学生结点的地址。可以存放学生结点的地址。可以存放学生结点的地址。 决售龟铭迷蜀遏屿木篮畔淬酒纫眩酝撬美敝康怎乒笛琅幽斋膨大消猴耳赐第10章结构体与链表第10章结构体与链表动态分配存储空间库函数动态分配存储空间库函数1void *malloc(unsigned int size); malloc
35、在内存的动态存储区中分配一个在内存的动态存储区中分配一个size长长度的连续存储空间。度的连续存储空间。例如:例如:int*p;int*p;p=(int*)malloc(8);p=(int*)malloc(8);BBp p指示系统分配的指示系统分配的指示系统分配的指示系统分配的4 4个整型存储单元的起始地址个整型存储单元的起始地址个整型存储单元的起始地址个整型存储单元的起始地址BB也可看成包含也可看成包含也可看成包含也可看成包含4 4个数组元素的个数组元素的个数组元素的个数组元素的p p数组:数组:数组:数组:p0,p1,p2,p3p0,p1,p2,p3杀衡吭矽粘拒镇起椎商稠珍节屁颊阐熄生轰卓
36、叁妨南征壳吟驾宽乖娟总赡第10章结构体与链表第10章结构体与链表2. void free(void *ptr); J函数函数free释放由指针变量释放由指针变量ptr所指示的内所指示的内存区域。存区域。 例如:例如:例如:例如:free(p); free(p); 通过函数通过函数通过函数通过函数freefree将已分配的内存区域交还系统,将已分配的内存区域交还系统,将已分配的内存区域交还系统,将已分配的内存区域交还系统,使系统可以重新对其进行分配。使系统可以重新对其进行分配。使系统可以重新对其进行分配。使系统可以重新对其进行分配。 蹬羊冠枪辜雪韶革瘦缩汰僧隧蹄酱均眷脯狮碎胸耍匣忿接绰揍省歪度郁
37、预第10章结构体与链表第10章结构体与链表【例【例10-12】动态定义数组。】动态定义数组。#includevoidmain()intn,i,*p;printf(n=);scanf(%d,&n);p=(int*)malloc(n*sizeof(int);for(i=0;in;i+)pi=i*i;for(i=0;inext=NULL;(3)如果)如果head为为NULL,则,则head=p;否则否则last-next=p;(4)last=p;(5)重复()重复(2)(4),继续建立新结点。),继续建立新结点。悲蚂潘一汐仑弱自珊莎氓勒坍痔扫飘秀毕磋囚酉逼柿饯抄湃且羹汪撑门射第10章结构体与链表第1
38、0章结构体与链表2. 头插法建立单链表头插法建立单链表特点特点:新产生的结点作为新的链表头插入链表。新产生的结点作为新的链表头插入链表。操作步骤:操作步骤:(1)head=NULL;(2)生成新结点,指针变量)生成新结点,指针变量p指向该结点;指向该结点;(3)p-next=head;head=p;(4)重复()重复(2)(3),继续生成下一个链表结),继续生成下一个链表结点。点。凭熙倚麦绥糊埃月绪狙怒萍模蔚什垦揖蚜巧蹲枢惋旱奏租浦艾啡屯筐凸感第10章结构体与链表第10章结构体与链表10.6.3 链表的访问链表的访问1.输出链表结点输出链表结点操作步骤:操作步骤:(1)得到链表头结点的地址)得
39、到链表头结点的地址head;(2)指针变量)指针变量p=head;(3)输出)输出p所指结点的成员值所指结点的成员值;(4)p后移一个结点,后移一个结点,p=p-next;(5)重复()重复(3)()(4),直到链表为空。),直到链表为空。剧瘁氛夏坞荫厘盎饱郭软苗瞪谦笨哑碌乱醇湃植卸嚎阿卢锈焙釉好歧诌缴第10章结构体与链表第10章结构体与链表2. 统计链表结点的个数统计链表结点的个数一般情况下,各个单链表中结点个数是随机的,一般情况下,各个单链表中结点个数是随机的,要想知道表中结点数目,必须从表头开始访要想知道表中结点数目,必须从表头开始访问到表尾,逐个统计出结点数目。问到表尾,逐个统计出结点
40、数目。 3. 查找链表的某个结点查找链表的某个结点在链表上查找符合某个条件的结点,也必须从在链表上查找符合某个条件的结点,也必须从链表头开始访问链表。链表头开始访问链表。 炙坎何风撵灼赘渺镭慎沫境进诲完禄涯红疹吸咋返煌琵予侥吧灶巢依甘板第10章结构体与链表第10章结构体与链表10.6.4 链表的插入操作链表的插入操作 在第在第n个结点之后插入个结点之后插入1个新结点个新结点,插入操作步骤:插入操作步骤:(1)q指针指向新结点,指针指向新结点,i为已访问过的结点数;为已访问过的结点数;(2)p=head,r指向指向p结点的前一个结点;结点的前一个结点;(3)i+,r=p,p=p-next,p结点
41、往前移动一个结点;结点往前移动一个结点;(4)若)若inext=head,head=q;(6)若)若inext=q,q-next=NULL;(7)否则,将)否则,将q结点插入到第结点插入到第n个结点之后,即插入到个结点之后,即插入到r结点与结点与p结点之间:结点之间:r-next=q,q-next=p;(8)返回链表头)返回链表头head。解勤纵邑燕资寨择考妖哩喝滤顽秩蜗彼邑峪撞渔帕滤银骸嘱牵缓涟涤肢热第10章结构体与链表第10章结构体与链表图10-7 将指针q所指结点插入第n个结点之后(b) 插入到第2个结点之后Headp101Zhang90103Wang80NULL105Li70(a) h
42、ead指示已有链表,q指示待插入结点 q101Zhao70Headr101Zhang90q104Zhao60103Wang80pNULL105Li70晕老豢质驾斥坯症请名吗英顿跺纤闺船傈蹦竖毙鳃兆托翻织赊吱瞧洁抖蜀第10章结构体与链表第10章结构体与链表10.6.5 链表的删除操作链表的删除操作 删除第删除第n个结点个结点(1)p=head,q指针指向指针指向p所指结点的前所指结点的前1个结点;个结点;(2)i为访问过的结点数目;为访问过的结点数目;(3)i+,q=p,p=p-next,p、q移动移动1个结点;个结点;(4)若)若p!=NULL且且inext;(6)若)若head=NULL,链
43、表为空,不能删除;,链表为空,不能删除;(7)若)若p=NULL,第,第n个结点不存在,不能删除;个结点不存在,不能删除;(8)找到第)找到第n个结点,删除个结点,删除p结点:结点:q-next=p-next;p的前的前1个结点的个结点的next值赋值为值赋值为p的的next域;域;(9)返回)返回head。考乔宁壮涤扎郭沧肄胚茅短读寇颤享溢戚袄俺电癌汀演芥行塔揪惮汞嚷当第10章结构体与链表第10章结构体与链表图10-9 删除第n个结点(a) head指示已有链表Headp101Zhang90103Wang80NULL105Li60101Zhao70(b) 删除第3个结点qpHead101Zhang90103Wang80NULL105Li60101Zhao70潍澄可且闪逆厂桶逆季逗雕糠聂仇顷蕊桔粤乎督伊蜜恭卡沈诧拔锥串遭漓第10章结构体与链表第10章结构体与链表