《C语言程序设计教学课件：第10章 结构体与共用体》由会员分享，可在线阅读，更多相关《C语言程序设计教学课件：第10章 结构体与共用体（51页珍藏版）》请在金锄头文库上搜索。
1、共 50 页 第 1 1 页第十章C C语言程序设计语言程序设计共 50 页 第 2 2 页本章要点本章要点 掌握结构类型数据的定义和引用；掌握结构类型数据的定义和引用； 了解共用体类型数据的定义和引用。了解共用体类型数据的定义和引用。共 50 页 第 3 3 页10.1 10.1 结构体类型结构体类型 如果将这些属性分别定义为互相独立的简单变量，则难以如果将这些属性分别定义为互相独立的简单变量，则难以反映相互间的反映相互间的内在联系内在联系( (同一个学生的属性同一个学生的属性) ) 可采用可采用结构体数据结构结构体数据结构描述上述信息描述上述信息, ,将不同类型的数据将不同类型的数据组合成
2、一个有机的整体，这些数据是相互联系的。组合成一个有机的整体，这些数据是相互联系的。问题：问题：l结构是逻辑上相互联系的一组分量的集合。结构是逻辑上相互联系的一组分量的集合。l结构中的分量可以是不同类型的数据，结构中的分结构中的分量可以是不同类型的数据，结构中的分量称为结构的成员量称为结构的成员一个学生有学号一个学生有学号/姓名姓名/性别性别/年龄年龄/地址等属性地址等属性在使用结构之前，首先要对结构的组成进行描述，称为在使用结构之前，首先要对结构的组成进行描述，称为结构结构的定义的定义。结构定义说明了该结构的组成成员，以及每个成员。结构定义说明了该结构的组成成员，以及每个成员的类型。的类型。共
3、 50 页 第 4 4 页10.1.1 10.1.1 结构体类型的定义结构体类型的定义例例: :structstruct student student int num; int num; char name20; char name20; char sex; char sex; int age; int age; char addr30; char addr30; ；定义一个结构体类型定义一个结构体类型的一般形式为：的一般形式为：struct 结构体结构体类型名类型名 成员表列成员表列 ；对各成员都要进行类型说明；对各成员都要进行类型说明；成员名定名规则与变量名同。成员名定名规则与变量名同。
4、共 50 页 第 5 5 页10.1.2 10.1.2 结构体变量的定义结构体变量的定义方法一：方法一：先定义结构体类型再定义变量名先定义结构体类型再定义变量名structstruct student student int num; int num; char name20; char name20; char sex; char sex; int age; int age; char addr30; char addr30; ；struct student struct student student1, student2;student1, student2;定义定义studet1和和s
5、udent2为为struct student类型变量类型变量不能只指定一个变不能只指定一个变量为量为“struct型型”而不而不指定结构体名指定结构体名共 50 页 第 6 6 页方法二：方法二：在定义类型的同时定义变量，在定义类型的同时定义变量，如：如：struct studentstruct student int num; int num; char name20; char name20; char sex; char sex; int age; int age; char addr30; char addr30;student1, student2;student1, student
6、2;一般形式：一般形式：struct 结构体名结构体名 成员表列成员表列 变量名表列；变量名表列；共 50 页 第 7 7 页方法三：方法三：直接定义结构类型变量。直接定义结构类型变量。其一般形式是：其一般形式是：structstruct 成员表列成员表列 变量名表列；变量名表列；此时，不出现结构体名此时，不出现结构体名共 50 页 第 8 8 页几点说明：几点说明：1. 1. 类型与变量是不同概念，不要混淆；类型与变量是不同概念，不要混淆；2. 2. 结构体中的成员，可以单独使用，其作用与结构体中的成员，可以单独使用，其作用与地位相当于普通变量；地位相当于普通变量；3. 3. 结构体成员也可
7、以是一个结构体变量；形成结构体成员也可以是一个结构体变量；形成结构类型嵌套。结构类型嵌套。struct date int month; int day; int year; ;struct student int num; char name20; int age; struct date birthday;student1,student2;4. 成员名可以与程序中的变量名相同，二者不代成员名可以与程序中的变量名相同，二者不代表同一对象。表同一对象。5. C只对变量分配单元，不对类型分配存储单元。只对变量分配单元，不对类型分配存储单元。共 50 页 第 9 9 页可用符号常量代表一个结构体类
8、型，如：可用符号常量代表一个结构体类型，如：#define #define STUDENTSTUDENT struct student struct studentSTUDENTSTUDENT int num; int num; char name20; char name20; char sex; char sex; int age; int age; char addr30; char addr30;这样，可直接用这样，可直接用STUDENT定义变量，如：定义变量，如：STUDENT student1, student2;此时，不必再写关键字此时，不必再写关键字struct共 50 页 第
9、 1010 页10.1.3 10.1.3 结构体变量的引用结构体变量的引用规则：规则：1.1.不能将一个结构体变量作为一个整体进行赋值和不能将一个结构体变量作为一个整体进行赋值和输出；只能对其各个成员分别输出输出；只能对其各个成员分别输出 引用形式为：引用形式为：结构体变量名结构体变量名. .成员名成员名printf(“”,student1);printf(“”,student1);printf(“ %d”, student1.num); printf(“ %d”, student1.num); 输出输出 1001010010错！正确！2 . 若成员本身又属于一个结构体类型，只能对最低若成员本
10、身又属于一个结构体类型，只能对最低级的成员进行赋值、存取以及运算。级的成员进行赋值、存取以及运算。 如：如：student1.birthday.year共 50 页 第 1111 页（接上）（接上）（接上）（接上）3.3. 对成员变量可以象普通变量一样进行各种运算，对成员变量可以象普通变量一样进行各种运算，如：如： sumage=student1.age+student2.age;sumage=student1.age+student2.age;4.4. 可以引用成员的地址，也可以引用结构体变量的可以引用成员的地址，也可以引用结构体变量的地址地址, ,如如 scanf(“%d”,&studen
11、t1.num);scanf(“%d”,&student1.num); printf(“%o”,&student1); printf(“%o”,&student1); scanf(“%d,%s,%c,%d,%s”,&student1); scanf(“%d,%s,%c,%d,%s”,&student1);错！错！输入输入student1.num的值的值输出输出student1的首地址的首地址共 50 页 第 1212 页 10.1.4 10.1.4 结构体变量的初始化结构体变量的初始化 structstruct student student long int num; long int num
12、; char name20; char name20; char sex; char sex; char addr20; char addr20;a=9801,”Wang hong”,W,”2 Linggong Road”;a=9801,”Wang hong”,W,”2 Linggong Road”;main( )main( )printf(“No.:%ldnname:%snsex:%cnaddress:%sn”,printf(“No.:%ldnname:%snsex:%cnaddress:%sn”,a.num,a.name,a.sex,a.addr);a.num,a.name,a.sex,a
13、.addr); 运行结果为：No.:9801name:Wang hongsex:Waddress:2 Linggong Road共 50 页 第 1313 页10.2 10.2 结构体数组结构体数组l 在结构体在结构体中中使用使用数组数组类型类型作为作为结构的一个结构的一个成员成员；l 用结构体用结构体类型类型作为作为数组元素的数组元素的基类型构成数组基类型构成数组。结构与数组的关系结构与数组的关系例：例：structstruct student student int xh; int xh; char xm14; char xm14; char xb; char xb; float sx;
14、float sx; xscj96; xscj96;96个元素都具有结构数据类型共 50 页 第 1414 页结结构构体体数数组组是是一一个个数数组组，数数组组中中的的每每一一个个元元素素都都是结构类型。是结构类型。说说明明结结构构数数组组的的方方法法：先先定定义义一一个个结结构构，再再用用结结构类型说明一个数组变量。构类型说明一个数组变量。例例：为为记记录录100个个人人的的基基本本情情况况，说说明明一一个个有有100个个元元素的数组。数组的基类型为结构素的数组。数组的基类型为结构. struct person char name 30; char sex; struct date birth
15、day manman100100; ;man就就是是有有100个个元元素素的的结结构构数数组组，数数组组的的每每个个元素为元素为 person 型。型。10.2.110.2.1结构体数组的定义结构体数组的定义共 50 页 第 1515 页例如例如: :structstruct student student int num; int num; char name20; char name20; char sex; char sex; int age; int age; char addr30; char addr30; struct student struct student stu3;st
16、u3;struct student int num; stu3;或或struct int num; stu3;一般形式:struct struct 结构体类型名结构体类型名 元素个数元素个数 ;struct struct 结构体类型名结构体类型名 结构体数组名结构体数组名; ;共 50 页 第 1616 页10.2.2 10.2.2 结构体数组的引用结构体数组的引用l访问访问结构体数组结构体数组中的具体元素，必须遵中的具体元素，必须遵守守数组数组使用的规定使用的规定按按下标下标进行访问。进行访问。l要访问结构体数组中某个具体元素下的要访问结构体数组中某个具体元素下的成员，又要遵守有关访问结构成
17、员的规定成员，又要遵守有关访问结构成员的规定 使用使用“. .”访问运算符访问运算符和成员名和成员名共 50 页 第 1717 页strcpy ( man3.name, Fangjin” );strcpy ( man3.name, Fangjin” );man3.sex = M;man3.sex = M;man3.birthday.year = 1963;man3.birthday.year = 1963;man3.birthday.month = 9;man3.birthday.month = 9;man3.birthday.day = 13;man3.birthday.day = 13;例
18、如：例如：要将数组要将数组manman中的中的3 3号元素赋值为：号元素赋值为：Fangjin, M, 1963, 9, 13Fangjin, M, 1963, 9, 13，使用下列语句：使用下列语句：为数组中一个元素的一个成员赋值为数组中一个元素的一个成员赋值共 50 页 第 1818 页结结构构数数组组存存放放在在连连续续的的内内存存区区域域中中，所所占占内内存存大大小小为为结结构类型的大小构类型的大小乘以数组元素的乘以数组元素的数量数量。（以标准。（以标准C C为例）为例）struct person man100: struct person man100: sizeof(struct
19、person) *100 sizeof(struct person) *100 字节字节,TC,TC系统系统=370=370字节字节301 222301 222301 222.ns ymdns ymdns ymdman0man1man99 将将“FangjFangji in n”改为改为“FangjFangju un n”： manman3 3.name.name5 5 = = u u;/*/*为数组中元素的数组成员中的一个字符赋值为数组中元素的数组成员中的一个字符赋值* */ /共 50 页 第 1919 页10.2.3 10.2.3 结构体数组的初始化结构体数组的初始化structstru
20、ct student student int num; int num; char name20; char name20; char sex; int age; char sex; int age; char addr30; char addr30; stu3=111,”Li”,M,18,”Dalian”,; stu3=111,”Li”,M,18,”Dalian”,;也可采用：也可采用：structstruct student student int num; int num; ; ; struct student struct student stu=,;stu=,;结构体数组的初始化的一
21、般形式是在结构体数组的初始化的一般形式是在定义数组后面加上：定义数组后面加上：=初值表列初值表列；共 50 页 第 2020 页例例10-1: 10-1: 编写一个编写一个3030名学生信息状况的示意性检索程名学生信息状况的示意性检索程序，每名学生的信息包括：序，每名学生的信息包括：xh(xh(学号学号) )、xbxb（性别）、（性别）、cjcj（成绩）、（成绩）、xm(xm(姓名姓名) )。要求：要求：（1 1）输入）输入3030名学生信息；名学生信息；（2 2）输出男同学中成绩大于）输出男同学中成绩大于9090的学生的的学生的xmxm、xbxb、cjcj。 共 50 页 第 2121 页#
22、include #include struct studentstruct student int xh; int xh; char xb; char xb; int cj; int cj; char xm20; char xm20; ;main()main() struct studentstruct student stu30; stu30; int i; int i; for(i=0;i30;i+) for(i=0;i30;i+) scanf(%d%c%d,&stui.xh,&stui.xb,&stui.cj); scanf(%d%c%d,&stui.xh,&stui.xb,&stui.
23、cj); gets(stui.xm); gets(stui.xm); for(i=0;i30;i+) for(i=0;i=90) if(stui.xb=m&stui.cj=90) printf(%s,%c,%dn,stui.xm,stui.xb,stui.cj);printf(%s,%c,%dn,stui.xm,stui.xb,stui.cj); 共 50 页 第 2222 页例例10-210-2：设有三个候选人，每次输入一个得票的候选人的名：设有三个候选人，每次输入一个得票的候选人的名字，要求最后输出各人得票结果。字，要求最后输出各人得票结果。#include #include “stdio
24、.hstdio.h”#include #include “string.hstring.h”struct personstruct person char name10; char name10; int count; int count;leader3=leader3=“LiLi”,0,0,”zhangzhang”,0,0,”LiuLiu”,0;,0;main( )main( ) int i, j; int i, j; char leader_name10; char leader_name10; for( i=1;i=100;i+) for( i=1;i=100;i+) scanf( sc
25、anf(“%s%s”,leader_name);,leader_name); for(j=0;j3;j+) for(j=0;j3;j+) if(strcmp(leader_name,leaderj.name)=0) if(strcmp(leader_name,leaderj.name)=0) leaderj.count+; leaderj.count+; for(i=0;i3;i+) for(i=0;i”-”进行操作。进行操作。结构指针结构指针-成员名成员名“-”-”运算符优先级最高运算符优先级最高(15(15级级) )，从左至右结合。，从左至右结合。 如如: p-: p-成员名成员名分析以下
26、运算：分析以下运算：p-np-n 得到得到p p指向的结构体变量中的成员指向的结构体变量中的成员n n的值的值p-n+ p-n+ 得到得到p p指向的结构体变量中的成员指向的结构体变量中的成员n n的值的值用完后使它加用完后使它加1 1； 相当于：相当于：(p-n)+ (p-n)+ +p-n +p-n 得到得到p p指向的结构体变量中的成员指向的结构体变量中的成员n n的值的值 使其先加使其先加1 1；相当于：；相当于：+(p-n)+(p-n) 常用方法共 50 页 第 2525 页例如：例如：main( )main( ) struct studentstruct studentlong in
27、t num;long int num; char name20; char name20; char sex; char sex;struct student struct student stu_1;stu_1;struct studentstruct student *p*p; ;p=&stu_1p=&stu_1；stu.num=9901;strcpy(stu_1.name,”Li Min”);stu_1.sex=W;printf(“No.:%ldnname%snsex:%cn”,stu_1.num,stu_1.name,stu_1.sex);printf(“nNo.:%ldnname%s
28、nsex:%cn”,(*p).num,(*p).name,(*p).sex);共 50 页 第 2626 页阅读程序：阅读程序：阅读程序：阅读程序：main() struct student int num; int age; ; struct student stu3=1000,20,2000,19,3000,23; struct student *p; p=stu; printf(“%dn”,p-num+); printf(“%dn”,+p-num); printf(“%dn”,(*p+).num); printf(“%dn”,(*+p).num);输出结果：输出结果：共 50 页 第 2
29、727 页例例: : printf(printf( %d%d , , man1.birthday.yearman1.birthday.year); ); 传递结构成员的传递结构成员的值值 scanf(scanf( %d%d , , & &manman11.birthday.year.birthday.year); ); 传递结构成员的传递结构成员的地址地址 gets ( gets ( manman11.name .name ); ); 传递结构成员的传递结构成员的地址地址10.4 10.4 结构体类型数据在函数间的传递结构体类型数据在函数间的传递l 结构体与函数的关系结构体与函数的关系 向函数
30、中传递结构的向函数中传递结构的成员成员；在函数之间传递整个在函数之间传递整个结构结构；将结构作为整体，在函数将结构作为整体，在函数之间传递之间传递;向函数传递结构的向函数传递结构的地址地址（指针指针）。）。在函数中在函数中传递结构成员传递结构成员的方法与的方法与传递简单变量传递简单变量的方法相同：的方法相同：在函数之间在函数之间传递成员的值传递成员的值；在函数之间在函数之间传递成员的地址。传递成员的地址。共 50 页 第 2828 页#include “stdio.h”struct student int num; char name20; float score3;stu=20701,”li
31、li”,67.5,88,79.6; void print(struct student p) printf(“%d %s %5.1f %5.1f %5.1fn”, p.num,p.name,p.score0, p.score1,p.score2); main() print(stu);例例:用结构体变量作参数。用结构体变量作参数。共 50 页 第 2929 页#include “stdio.h”struct student int num; char name20; float score3;stu=20701,”lili”,67.5,88,79.6; void print(struct st
32、udent *p) printf(“%d %s %5.1f %5.1f %5.1fn”,p-num,p-name,p-score0,p-score1,p-score2); main() print (&stu); 例例:用指向结构体变量的指针作参数。用指向结构体变量的指针作参数。共 50 页 第 3030 页 10.4 10.4 共用体共用体10.4.1 10.4.1 共用体的概念共用体的概念共用体：共用体：使几个不同的变量占用同一段内存的结构，使几个不同的变量占用同一段内存的结构，称为称为“共用体共用体”类型的结构。类型的结构。“共用体共用体”类型变量的定义形式为：类型变量的定义形式为：un
33、ion union 共用体名共用体名 成员表列成员表列 变量表列；变量表列；例如：例如：unionunion datadataint i;int i; char ch; char ch; float f;a,b,c; float f;a,b,c;或或union dataint i;char ch;float f;union data a,b,c;或或union int i;char ch;float f; a,b,c;直接直接定义定义先定义先定义类型类型共 50 页 第 3131 页注意注意注意注意: : : :共用体类型变量与结构体类型变量的共用体类型变量与结构体类型变量的共用体类型变量与结
34、构体类型变量的共用体类型变量与结构体类型变量的区别区别区别区别: : : :结构体类型变量所占内存长度是各成员占结构体类型变量所占内存长度是各成员占的内存的内存长度之和长度之和。共用体类型变量所占内存长度等于共用体类型变量所占内存长度等于最长的最长的成员的长度成员的长度。成员成员分量分量之间是之间是相互联系相互联系的，所进行的操的，所进行的操作相互依赖。作相互依赖。共 50 页 第 3232 页10.4.2 10.4.2 共用体变量的引用方式共用体变量的引用方式注意：注意：只能引用共用体变量中的成员，不能引用只能引用共用体变量中的成员，不能引用共用体变量本身。如：共用体变量本身。如：可以引用可
35、以引用 a .i(a .i(引用共用体变量中的整型变量引用共用体变量中的整型变量i)i) a .ch( a .ch(引用共用体变量中的字符变量引用共用体变量中的字符变量ch)ch) a .f( a .f(引用共用体变量中的实型变量引用共用体变量中的实型变量f)f)不能只引用共用体变量，如：不能只引用共用体变量，如： printf(“%d”,a);printf(“%d”,a);错！错！共 50 页 第 3333 页阅读程序阅读程序 #include #include union pp union pp short int i; short int i; char ch2; char ch2; a
36、; a; main() main() a.ch0=1; a.ch0=1; a.ch1=3; a.ch1=3; printf( printf(“%dn%dn”,a.i);,a.i); printf( printf(“%on%on”,a.i);,a.i); a的内存存储情况如下：的内存存储情况如下：a.ia.ch1a.ch00 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1输出结果：输出结果：769 1401低低字字段段高高字字段段(1401)8共 50 页 第 3434 页10.4.3 10.4.3 共用体类型数据的特点共用体类型数据的特点1.1.每一瞬时只有一个成员起作用每一瞬时只
37、有一个成员起作用 ；2.2.共用体变量中起作用的成员是最后一次存放的成员；共用体变量中起作用的成员是最后一次存放的成员；3.3.共用体变量的地址和它的各成员的地址都是同一地址；共用体变量的地址和它的各成员的地址都是同一地址；4.4.不能对共用体变量名赋值，也不能通过引用变量名来得到成不能对共用体变量名赋值，也不能通过引用变量名来得到成员的值，不能在定义共用体变量时对它初始化。员的值，不能在定义共用体变量时对它初始化。5.5.不能把共用体变量作为函数参数，也不能使函数带回共用体不能把共用体变量作为函数参数，也不能使函数带回共用体变量，但可使用指向共用体变量的指针；变量，但可使用指向共用体变量的指
38、针；6.6.共用体类型可以出现在结构体类型定义中，也可以定义共用共用体类型可以出现在结构体类型定义中，也可以定义共用体数组。而结构体也可以出现在共用体类型定义中，数组体数组。而结构体也可以出现在共用体类型定义中，数组也可以作为共用体的成员。也可以作为共用体的成员。共 50 页 第 3535 页 10.5 10.5 枚举类型枚举类型若一个变量只有几种可能的值，可以定义为若一个变量只有几种可能的值，可以定义为枚举类型枚举类型。所。所谓谓“枚举枚举”是指将变量的值一一列举出来，变量的值只限是指将变量的值一一列举出来，变量的值只限于列举出来的值的范围内。于列举出来的值的范围内。定义方法：定义方法：先定
39、义枚举类型先定义枚举类型 enum weekday sun, mon, tue, wed, thu, fri, sat;enum weekday sun, mon, tue, wed, thu, fri, sat;再用此类型定义变量，如：再用此类型定义变量，如：enum weekday workday, week_end;enum weekday workday, week_end;或或直接定义枚举变量。如：直接定义枚举变量。如：enum weekday sun, mon, tue, wed, thu, fri, sat enum weekday sun, mon, tue, wed, thu
40、, fri, sat workday,week_end;workday,week_end;共 50 页 第 3636 页说明：说明：枚举元素为常量，不是变量，故不能对它们赋值枚举元素为常量，不是变量，故不能对它们赋值枚举常量有值。如上面定义中，枚举常量有值。如上面定义中，sun sun 、 mon mon 、 tue tue sat sat的值依次为的值依次为0 0、1 1、2727也可改变枚举元素的值，在定义时指出，如：也可改变枚举元素的值，在定义时指出，如： enum weekdaysun=7,mon=1,tue,wed,thu,fri,sat;enum weekdaysun=7,mon=
41、1,tue,wed,thu,fri,sat;枚举值可用来作判断比较，如：枚举值可用来作判断比较，如： if(workday=mon) if(workdaysun)if(workday=mon) if(workdaysun)一个整数不能直接赋值给一个枚举变量，应先进行强制类一个整数不能直接赋值给一个枚举变量，应先进行强制类型转换才能赋值，如：型转换才能赋值，如： workday=(enum weekday)2; (workday=(enum weekday)2; (相当于将序号为相当于将序号为2 2的枚举的枚举元素值赋给元素值赋给workday , workday , 即：即：workday=t
42、ue;workday=tue;共 50 页 第 3737 页10.6 10.6 用用typedeftypedef定义数据类型定义数据类型10.6.1 自定义类型自定义类型l 标准类型（如标准类型（如intint、charchar、longlong、doubledouble等）系等）系统已经定义好的类型，用户可以直接使用，无须再进统已经定义好的类型，用户可以直接使用，无须再进行定义。行定义。l 用户自定义类型：用户根据自己的实际要求，将已用户自定义类型：用户根据自己的实际要求，将已有的类型重新命名为一个新的简单类型。有的类型重新命名为一个新的简单类型。除除结构结构和和联合联合等类型之外，还可以用
43、类型说明等类型之外，还可以用类型说明语句语句typedeftypedef定义新的类型来代替已有的类型。定义新的类型来代替已有的类型。共 50 页 第 3838 页l例例 typedeftypedef intint INTEGER;INTEGER; typedeftypedef floatfloat REAL;REAL;在具有上述在具有上述typedeftypedef语句的程序中，下列语语句的程序中，下列语句是等价的：句是等价的： int i,j; float paiint i,j; float pai； 等价于等价于 INTEGER i, j; REAL pai;INTEGER i, j; R
44、EAL pai; 10.6.2 typedef 10.6.2 typedef语句的一般形式语句的一般形式typedeftypedef 已定义的类型已定义的类型 新的类型新的类型共 50 页 第 3939 页l例例 typedeftypedef struct nodestruct node int data; int data; struct *link; struct *link; JD JD定义了一个新的结构体类型定义了一个新的结构体类型JDJD, ,它代表结构体它代表结构体struct node .struct node .以后可以使用以后可以使用JDJD来定义变量来定义变量: : JD
45、*s; JD *s; 定义指向结点类型的指针定义指向结点类型的指针s s共 50 页 第 4040 页综合练习：折半查找（二分法查找）综合练习：折半查找（二分法查找）思思想想：先先确确定定待待查查找找记记录录所所在在的的范范围围，然然后后逐逐步步缩缩小小范范围，直到找到或确认找不到该记录为止。围，直到找到或确认找不到该记录为止。前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表中进行有序表中进行。分三种情况：分三种情况：1 1）若中间项的值等于）若中间项的值等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在
46、线性表的前半部分查找；3 3）若）若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。特点：比顺序查找方法效率高。共 50 页 第 4141 页查找查找23的过程如下图：的过程如下图：mid=(low+high)/2( 8, 14, 23, 37, 46, 55, 68, 79, 91 )( 8, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 8, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 8, 14, 23, 37, 46,
47、55, 68, 79, 91 )low=mid+1highmid共 50 页 第 4242 页typedef struct int num; char name10; float score;Student;main() int j,num; Student s4=10,Li,98,40,Wang,88,55,Zhang,89,60,Lin,95; scanf(%d,&num); j=search(s,num,4); if(j!=-1)printf(Name=%s,Score=%f,sj.name,sj.score); else printf(No Number);int search(Stu
48、dent s,int key, int n)/*折半查找*/ int low,high,mid; low=1;high=n; while(low=high) mid=(low+high)/2; if(smid-1.num=key) return (mid-1); else if(keynum1,&p1-score); scanf(%d,%f,&p1-num1,&p1-score); head=NULL; head=NULL; while(p1-num!=0) while(p1-num!=0) n=n+1; n=n+1; if(n=1) head=p1; if(n=1) head=p1; els
49、e p2-link=p1; else p2-link=p1; p2=p1; p2=p1; p1=(stu *)malloc(sizeof(stu); p1=(stu *)malloc(sizeof(stu); scanf(%d,%f,&p1-num,&p1-score); scanf(%d,%f,&p1-num,&p1-score); p2-link=NULL; p2-link=NULL; return(head); return(head); 共 50 页 第 4747 页 遍历就是逐一的访问链表中的每个结点。设线性链表头遍历就是逐一的访问链表中的每个结点。设线性链表头指针为指针为h h，设
50、指针变量，设指针变量p p指向不同的结点。沿着链头开始向指向不同的结点。沿着链头开始向后查找结点中学号为后查找结点中学号为x x的结点的结点, ,若找到，则返回该结点在链若找到，则返回该结点在链表中的位置，否则返回空地址。表中的位置，否则返回空地址。NODE *lbcz (NODE *L, int x)NODE *lbcz (NODE *L, int x) NODE *p; NODE *p; p=L-link ; /* p p=L-link ; /* p先指向第一个结点先指向第一个结点 * */ / while (p!=NULL & p-num!=x) while (p!=NULL & p-n
51、um!=x) p=p-link; /* pp=p-link; /* p指向下一结点指向下一结点 * */ / return(p);return(p); (2)(2)单链表的遍历单链表的遍历共 50 页 第 4848 页void ListInsert_L(NODE *L,int i,int x) /* 在带头结点的线性链表在带头结点的线性链表L 中第中第i个位置之前插入元素个位置之前插入元素x */ NODE *p=L.*s; int j=0; while( p & jlink;+j ； /* 寻找第寻找第i-1个结点个结点*/ if(!p | ji-1) return (0); /* 插入位置
52、错误插入位置错误 */ s=(NODE *)malloc(sizeof(NODE)； /* 生成新结点生成新结点*/ s-data=x;s-link=p-link;p-link=s; /* 插入到表中插入到表中 */ return (1); (3) (3) 单链表的插入单链表的插入a an na ai ia a1 1a a2 2a ai-1i-1x xL共 50 页 第 4949 页void ListDelete(NODE *L,int i,int x) /* 在带头结点的线性链表在带头结点的线性链表L 中中,删除第删除第i个元素个元素 */ NODE *p=L,*q; int j=0; wh
53、ile( p-link & jlink;+j ； /* 寻找第寻找第i个结点，并令个结点，并令p指向其前驱指向其前驱*/ if(!(p-link) | ji-1) return (0); /* 删除位置错误删除位置错误*/ q=p-link;p-link=q-link;free(q); /* 删除并释放结点删除并释放结点*/ return (1); （4 4）单链表的删除）单链表的删除ai-1a1aiai+1Lpq共 50 页 第 5050 页（5 5）求链表的长度）求链表的长度 由于链表的长度不是事先确定的，是动态建立的，因此求由于链表的长度不是事先确定的，是动态建立的，因此求链表的长度需要
54、遍历链表的所有结点才能完成。链表的长度需要遍历链表的所有结点才能完成。int lblenth (NODE *L) NODE *p=L; int count=0; while (p!=NULL) count+; /* 结点计数器加结点计数器加1 */ p=p-link; /* p指向下一结点指向下一结点 */ return(count);共 50 页 第 5151 页(6) (6) 循环链表循环链表 首尾相接的链表。首尾相接的链表。 将将最最后后一一个个结结点点的的空空指指针针改改为为指指向向头头结结点点，从从任任一一结点出发均可找到其它结点。结点出发均可找到其它结点。v操作与单链表基本一致操作与单链表基本一致, ,循环条件不同循环条件不同l 单链表单链表p p或或p-link=NULLp-link=NULLl 循环链表循环链表p p或或p-link=hp-link=hhh空表
