第七章 构造数据类型

1、1第7章 构造数据类型第7章 构造数据类型7.1 7.1 构造数据类型概述构造数据类型概述7.2 7.2 结构体与结构体变量的定义结构体与结构体变量的定义7.3 7.3 结构体变量的使用与初始化结构体变量的使用与初始化7.4 7.4 结构体数组结构体数组7.5 7.5 结构体指针结构体指针7.6 7.6 结构体作函数参数结构体作函数参数7.7 7.7 线性表线性表7.8 7.8 共用体共用体7.9 7.9 枚举类型枚举类型7.10 7.10 用用typedeftypedef定义类型定义类型7.11 7.11 位段结构类型位段结构类型本章要点：1. 掌握构造类型数据的定义方法和引掌握构造类型数据

2、的定义方法和引用方法；用方法；2. 了解了解用用typedeftypedef定义类型的定义类型的方法。方法。 一个学生的信息有一个学生的信息有学号学号、姓名姓名、性别性别、年龄年龄、成成绩绩、住址住址等。等。 一本图书的信息有一本图书的信息有分类编号分类编号、书名书名、作者作者、出版出版社社、出版日期出版日期、价格价格、库存量库存量等。等。 如何描述这些类型不同的相关数据？如何描述这些类型不同的相关数据？7.1 构造数据类型概述一种构造类型数据。一种构造类型数据。 结构体结构体由若干不同类型的数据项组成，由若干不同类型的数据项组成， 构成结构体的各个数据项称为构成结构体的各个数据项称为结构体成

3、员结构体成员。 struct 结构体名结构体名 数据类型数据类型1 成员名成员名1; 数据类型数据类型2 成员名成员名2; 数据类型数据类型n 成员名成员名n; ;7.2 结构体与结构体变量的定义结构体类型定义的一般形式：结构体类型定义的一般形式： lstruct为关键字，不能省；为关键字，不能省；l结构体名结构体名是用户定义的是用户定义的类型标识，类型标识，可省（无名可省（无名结构体）结构体）；l 中是组成该结构体的中是组成该结构体的成员成员。成员的。成员的数据类型数据类型可以是可以是C语言所允许的语言所允许的任何数据类型。任何数据类型。例如图书类型的定义：例如图书类型的定义： struct

4、 bookcard char num10; /*图书分类编号是字符数组类型图书分类编号是字符数组类型*/ char name30; /*书名是字符数组类型书名是字符数组类型*/ char author30; /*作者是字符数组类型作者是字符数组类型*/ char publisher60; /*出版社是字符数组类型出版社是字符数组类型*/ float price; /*价格是单精度实型价格是单精度实型*/ int n; /*库存量是整型库存量是整型*/ ;例如学生类型的定义：例如学生类型的定义：struct student int num; /* 学号是整型类型学号是整型类型 */ char n

5、ame20; /* 姓名是字符数组类型姓名是字符数组类型 */ char sex; /* 性别是字符型性别是字符型 */ int age; /* 年龄是整型年龄是整型 */ float score6; /* 成绩是实型数组类型成绩是实型数组类型 */ char addr30; /* 住址是字符数组类型住址是字符数组类型 */ ;7.2 结构体与结构体变量的定义7.2 结构体与结构体变量的定义1、利用已定义的结构体类型名定义变量、利用已定义的结构体类型名定义变量 struct 结构体名结构体名 变量名表列；变量名表列；例如：例如： struct student st30, t1, t2; str

6、uct bookcard book1100; 按照结构体类型的组成，系统为定义的结构体按照结构体类型的组成，系统为定义的结构体变量分配内存单元。结构体变量的各个成员在内存变量分配内存单元。结构体变量的各个成员在内存中占用连续存储区域，中占用连续存储区域，结构体变量结构体变量所占内存所占内存结构体中结构体中每个成员每个成员所占用内存的所占用内存的长度之和长度之和。struct studentnum2个字节name20个字节sex1个字节age2个字节score24个字节addr30个字节例例 struct student int num; char name20; char sex; int a

7、ge; float score6; char addr30; ; struct student stu1,stu2; 结构体变量的定义形式：结构体变量的定义形式： 7.2 结构体与结构体变量的定义2 2、在定义结构体类型的同时定义变量、在定义结构体类型的同时定义变量例如：例如： struct student int num； char name20,sex,addr30; int age; float score6; st30; struct 结构体名结构体名 成员定义表列；成员定义表列； 变量名表列；变量名表列；7.2 结构体与结构体变量的定义3、直接定义结构体类型变量、直接定义结构体类型变

8、量 例如：例如： struct int num； char name20,sex,addr30; int age; float score6; st30, a, b, c; struct 成员定义表列；成员定义表列； 变量名表列；变量名表列；用用无名结构体无名结构体直接定义直接定义变量变量只能一次。只能一次。7.2 结构体与结构体变量的定义结构体类型与结构体变量的说明结构体类型与结构体变量的说明 类型类型与与变量变量是不同的概念。是不同的概念。应先定义一个结构体类型，而后再定义结构体应先定义一个结构体类型，而后再定义结构体变量。变量。系统对类型不分配空间，仅对变量分配空间。系统对类型不分配空间

9、，仅对变量分配空间。只能对变量赋值、存取或运算，而不能对一个只能对变量赋值、存取或运算，而不能对一个类型赋值、存取或运算。类型赋值、存取或运算。 成员成员也可以是也可以是结构变量（嵌套）结构变量（嵌套）。 对结构中的对结构中的成员（域）成员（域），可以单独使用，它的作，可以单独使用，它的作用与地位相当于用与地位相当于普通变量普通变量。 成员名成员名可与程序中的变量名相同，也可与可与程序中的变量名相同，也可与不同结不同结构体类型的成员名相同，构体类型的成员名相同，二者代表不同的对象。二者代表不同的对象。 struct date int year,month,day; struct student

10、 int num; char name20; char sex; birthday; /* 成员为结构体类型成员为结构体类型 */ float score6; char addr30; ;num2个字节name20个字节sex1个字节birthdayyear2个字节month2个字节day2个字节score24个字节addr30个字节7.3 结构体变量的引用及初始化引用规则：引用规则： 结构体变量结构体变量不能整体引用不能整体引用, ,只能引用只能引用成员成员变量。变量。引用方式：引用方式：结构体变量名结构体变量名. .成员名成员名可以将一个结构体变量可以将一个结构体变量赋值赋值给另一个结构体

11、变量。给另一个结构体变量。结构体嵌套时结构体嵌套时逐级引用。逐级引用。成员成员(分量分量)运算符运算符优先级优先级: 1结合性结合性:从左向右从左向右例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score; stu1.age+;例 struct student int num; char name20; char sex; int age; float scor

12、e; char addr30; stu1,stu2; printf(“%d,%s,%c,%d,%f,%sn”,stu1); ( )stu1=101,“Wan Lin”,M,19,87.5,“DaLian”; ( )例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; if(stu1=stu2). ()例 struct student int num; char name20; char sex; int age; float score; char addr3

13、0; stu1,stu2; stu2=stu1; ( )例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu1,stu2;numnamebirthdaymonthdayyearstu1.birthday.month=12;7.3 结构体变量的引用及初始化初始化：初始化：形式一：形式一：struct 结构体名结构体名 类型名类型名 成员名；成员名； 类型名类型名 成员名；成员名； .；struct 结构体名结构体名 结构体变量结构体变量=初始数据初始数据；例例

14、struct student int num; char name20; char sex; int age; char addr30; ; struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;7.3 结构体变量的引用及初始化形式二：形式二：struct 结构体名结构体名 类型名类型名 成员名；成员名； 类型名类型名 成员名；成员名； .结构体变量结构体变量=初始数据初始数据；例例 struct student int num; char name20; char sex; int age; char addr30; stu1

15、=112,“Wang Lin”,M,19, “200 Beijing Road”; 7.3 结构体变量的引用及初始化形式三：形式三：struct 类型名类型名 成员名；成员名； 类型名类型名 成员名；成员名； .结构体变量结构体变量=初始数据初始数据；例例 struct int num; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”; 7.3 结构体变量的引用及初始化【例【例7.1】结构体变量的初始化。】结构体变量的初始化。 struct date int ye

16、ar, month, day; struct student char num8, name20, sex; struct date birthday; float score; a=“0506011,Li ming,M,1977,12,9,83, b=“0508025,Zhang li,F,1978,5,10,87, c; 如果初值个数少于结构体成员个数，如果初值个数少于结构体成员个数，则将无初值对应的成员赋以则将无初值对应的成员赋以0值。值。 如果初值个数多于结构体成员个数，如果初值个数多于结构体成员个数，则编译出错。则编译出错。7.4 结构体数组 7.4.1结构体数组的定义结构体数组的定

17、义三种形式：三种形式：形式一形式一: : struct student int num; char name20; char sex; int age; ;struct student stu2;形式二形式二: : struct student int num; char name20; char sex; int age; stu2;形式三形式三: struct int num; char name20; char sex; int age; stu2;numnamesexagenumnamesexagestu0stu125B7.4 结构体数组分行初始化分行初始化: struct stude

18、nt int num; char name20; char sex; int age; ;struct student stu =100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 全部初始化时维数可省全部初始化时维数可省顺序初始化顺序初始化: struct student int num; char name20; char sex; int age; ;struct student stu =100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 例例 s

19、truct student int num; char name20; char sex; int age; stu =,; 7.4.2 结构体数组初始化结构体数组初始化7.4 结构体数组7.4.3 结构体数组引用结构体数组引用引用方式：引用方式：结构体数组名结构体数组名下标下标.成员名成员名 struct student int num; char name20; char sex; int age; str3;stu1.age+;strcpy(,”ZhaoDa”);例7.2a 统计后选人选票struct person char name20; int count;lead

20、er3=“Li”,0,“Zhang”,0,”Wang“,0; main() int i,j; char leader_name20; for(i=1;i=10;i+) scanf(%s,leader_name); for(j=0;j3;j+)if(strcmp(leader_name,)=0) leaderj.count+; for(i=0;i=1 & n=5) listn.count+; /* 有效票，则相应候选人计票成员加有效票，则相应候选人计票成员加1 1 */ else printf(invalidn); list0.count+; /* 无效票无效票，

21、list0的计票成员加的计票成员加1 */ scanf(%d,&n); /* 输入所投候选人编号输入所投候选人编号 */ for (i=1; i成员名成员名结构体变量名结构体变量名. .成员名成员名指向运算符优先级: 1结合方向：从左向右p=&例7.3 指向结构体的指针变量main() struct student long int num; char name20; char sex; float score; stu_1,*p; p=&stu_1; stu_1.num=10212; strcpy(stu_1.name,Li Lin); p-sex=

22、M; p-score=89.5; printf(nNo:%ldnname:%snsex:%cnscore:%fn, (*p).num,p-name,stu_1.sex,p-score); 举例 例例7.4 输入今天的日期，然后输出该日期。输入今天的日期，然后输出该日期。 main( ) struct date /* 在函数中定义结构体类型在函数中定义结构体类型 */ int year, month, day;today,*p=&today; /* 定义结构体变量及其指针定义结构体变量及其指针 */ printf (Enter today date(YYYY/MM/DD):); scan

23、f(%d/%d/%d,&today.year,&today.month, &today.day); printf(Today:%d/%d/%dn,p-year,p-month, p-day); 7.5.2 指向结构体数组的指针例例7.5 指向结构体数组的指针指向结构体数组的指针struct student int num; char name20; char sex; int age;stu3=10101,Li Lin,M,18, 10102,Zhang Fun,M,19, 10104,Wang Min,F,20;main() struct student *p; fo

24、r(p=stu;pnum,p-name,p-sex,p-age);numnamesexagestu0pstu1stu2p+17.5.2 指向结构体数组的指针例例7.6 利用结构体指针输出一组化学利用结构体指针输出一组化学 元素名称及其原子量。元素名称及其原子量。 struct list int i; char name4; float w; tab4=1,H,1.008,2,He,4.0026, 3,Li,6.941,4,Be,9.01218;tab数组1Htab01.0082Hetab14.00263Litab26.9414Betab39.012187.5.2 指向结构体数组的指针main(

25、 ) struct list *p; printf(NotNametAtomic Weightn); for (p=tab; p-i, p-name, p-w); tab数组1Htab01.0082Hetab14.00263Litab26.9414Betab39.01218ppppp1 H 1.0082 He 4.00263 Li 6.9414 Be 9.012187.5.2 指向结构体数组的指针例例7.7 分析自增自减运算对程序结果的影响。分析自增自减运算对程序结果的影响。 struct code int i; char c; a =100,A,200,B, 300,C,400,D;a数组1

26、00a0A200a1B300a2C400a3D7.5.2 指向结构体数组的指针main( ) struct code *p=a; printf(%dt,+p-i); printf(%ct,(+p)-c); printf(%dt,(p+)-i); printf(%ct,+p-c); printf(%dt,p-i+); printf(%dn,p-i); a数组100a0A200a1B300a2C400a3Dp101301101B200D3003017.6 结构体作函数参数方法一：方法一： 用结构体变量的成员作参数用结构体变量的成员作参数-值传递值传递 函数的函数的形参形参定义为定义为普通变量普通变

27、量。函数调用时，。函数调用时，可可将主调函数的将主调函数的结构体变量的成员值作结构体变量的成员值作实参实参传递给传递给被调函数的被调函数的形参形参。 如果如果将函数定义为将函数定义为结构体类型函数结构体类型函数，可，可利用利用returnreturn语句将一个结构体数据结果返回到主调函语句将一个结构体数据结果返回到主调函数数中中。7.6 结构体作函数参数方法二：方法二：用指向结构体变量或数组的指针作参数用指向结构体变量或数组的指针作参数-地址传递地址传递 形参形参定义为定义为指向结构体类型的指向结构体类型的指针指针变量变量，可可将主调函将主调函数的数的结构体指针结构体指针传递给被调函数的传递给

28、被调函数的形参形参变量变量，通过指针形，通过指针形参的指向域的扩展，操作主调函数中参的指向域的扩展，操作主调函数中结构体变量及其成员结构体变量及其成员。 如果如果将函数定义为将函数定义为结构体指针型函数结构体指针型函数，可可利用利用returnreturn语语句将被调函数中结构体变量的句将被调函数中结构体变量的指针指针返回给主调函数的返回给主调函数的结构结构体指针变量体指针变量。方法三：方法三： 利用利用结构体变量结构体变量传递结构体数据传递结构体数据-多值传递多值传递（效率低）（效率低）例7.8 用结构体变量作函数参数struct data int a, b, c; ;main() void

29、 func(struct data); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c); printf(Call Func().n); func(arg); printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c);void func(struct data parm) printf(parm.a=%d parm.b=%d parm.c=%dn,parm.a,parm.b,pa

30、rm.c); printf(Process.n); parm.a=18; parm.b=5; parm.c=parm.a*parm.b; printf(parm.a=%d parm.b=%d parm.c=%dn,parm.a,parm.b,parm.c); printf(Return.n);arga :27b: 3c :30(main)(func)parma :27b: 3c :30copyarga :27b: 3c :30(main)(func)parma :18b: 5c :90arga :27b: 3c :30(main)arga :27b: 3c :30(main)例7.9 结构体指

31、针作函数参数struct data int a, b, c; ;main() void func(struct data *parm); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c); printf(Call Func().n); func(&arg); printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c);void func(struct data *parm)

32、 printf(parm-a=%d parm-b=%d parm-c=%dn,parm-a,parm-b,parm-c); printf(Process.n); parm-a=18; parm-b=5; parm-c=parm-a*parm-b; printf(parm-a=%d parm-b=%d parm-c=%dn,parm-a,parm-b,parm-c); printf(Return.n);arga :18b: 5c :90(main)arga :27b: 3c :30(main)arga :27b: 3c :30(main)(func)parm*arga :18b: 5c :90(

33、main)(func)parm*7.7 线性表7.7.1 7.7.1 线性表的顺序存储与实现线性表的顺序存储与实现 顺序表中所有结点类型相同，每个结点占用存储顺序表中所有结点类型相同，每个结点占用存储空间也相同。空间也相同。 LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *c (1=i=n)c (1=inum,p-score); p=p-next; while(p!=NULL); C语言提供了相关的存储管理库函数。这里仅介语言提供了相关的存储管理库函数。这里仅介绍其中三个，它们的原型说明在绍其中三个，它们的原型说明在“stdlib.h”头文头文件和件

34、和“alloc.h”头文件中，使用这三个函数时，头文件中，使用这三个函数时，应选择其中一个头文件包含到源程序中。应选择其中一个头文件包含到源程序中。 动态分配存储区函数动态分配存储区函数malloc( ) 函数原型：函数原型：void *malloc(unsigned size); 调用格式：调用格式：malloc(size) 功能：在动态存储区分配一个长度为功能：在动态存储区分配一个长度为size字节的字节的连续存储区。调用结果为新分配的存储区的首地连续存储区。调用结果为新分配的存储区的首地址，是一个址，是一个void 类型指针。若分配类型指针。若分配失败失败，则返回，则返回NULL（即（即

35、0）。 处理链表所需的函数 在在ANSI C标准中，关键字标准中，关键字void有两种用法。有两种用法。第一种用法，可将无返回值的函数定义为第一种用法，可将无返回值的函数定义为void类型类型第二种用法，用第二种用法，用void * 定义指针，这是一个指向定义指针，这是一个指向非具体数据类型的指针，称为无类型指针。非具体数据类型的指针，称为无类型指针。 【例【例7.11】调用】调用malloc函数分配所需存储单元。函数分配所需存储单元。 #include main( ) struct st int n; struct st *next; *p; p=(struct st *)malloc(si

36、zeof(struct st); p-n=5; p-next=NULL; printf(p-n=%dtp-next=%xn,p-n,p-next); 处理链表所需的函数将函数返回值转换将函数返回值转换成结构体指针成结构体指针 动态分配存储区函数动态分配存储区函数calloc( ) 函数原型：函数原型： void *calloc(unsigned int n,unsigned int size); 调用格式：调用格式：calloc(n,size) 功能：在动态存储区分配功能：在动态存储区分配n个长度为个长度为size字节的连字节的连续存储区。调用结果为新分配的存储区的首地址，续存储区。调用结果为

37、新分配的存储区的首地址，是一个是一个void类型指针。若分配类型指针。若分配失败失败，则返回，则返回NULL（即（即0）。 处理链表所需的函数【例【例7.12】调用】调用calloc函数分配所需存储单元。函数分配所需存储单元。 #include main( ) int i,*ip; ip=(int *)calloc(10,2); for (i=0; i10; i+) scanf(%d,ip+i); for (i=0; iname,name) gets(p-tel) p-next=NULL h=NULL T F h指向第一个指向第一个 连接新结点连接新结点 结点结点 h=p q-next=p q

38、指向新的尾结点指向新的尾结点 q=p 读入一个学生姓名读入一个学生姓名NULLhpChang62783410NULLWang63212986NULLpq strcpy(p-name,name); /* 为新结点中的成员赋值为新结点中的成员赋值 */ printf(tel: ); gets(p-tel); p-next=NULL; if (h=NULL) /* h为空，表示新结点为第一个结点为空，表示新结点为第一个结点 */ h=p; /* 头指针指向第一个结点头指针指向第一个结点 */ else /* h不为空不为空 */ q-next=p; /* 新结点与尾结点相连接新结点与尾结点相连接 *

39、/ q=p; /* 使使q指向新的尾结点指向新的尾结点 */ printf(name: ); gets(name); return h; struct node *create( ) static struct node *h; struct node *p,*q; char name20; h=NULL; printf(name: ); gets(name); while (strlen(name)!=0) /* 当输入的姓名不是空串循环当输入的姓名不是空串循环 */ p=NEW; /* 开辟新结点开辟新结点 */ if (p=NULL) /* p为为NULL，新结点分配失败新结点分配失败

40、*/ printf(Allocation failuren); exit(0); /* 结束程序运行结束程序运行 */ #include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ;单链表的基本操作main( ) struct node *head; head=create( ); 【例【例7.14】输出学生电话簿链表函数。】输出学生电话簿链表函数。 单链表的基本操作输出单向链表中各结点信息输出单向链表中各结点信息

41、hpChang62783410Li68752341NULLWang63212986 p指向第一个结点指向第一个结点 p=head 当当p不为不为NULL 输出结点数据输出结点数据 p指向下一个结点指向下一个结点 p=p-nextpppNULLNULLvoid prlist(struct node *head) struct node *p; p=head; while (p!=NULL) printf(%st%sn,p-name,p-tel); p=p-next; #include #include #define NEW (struct node *)malloc(sizeof(struct

42、 node)struct node char name20,tel9; struct node *next; ;单链表的基本操作main( ) struct node *head; head=create( ); prlist(head); 在链表中，如果要删除第在链表中，如果要删除第i个结点，一般是将个结点，一般是将第（第（i-1）个结点直接与第（）个结点直接与第（i+1）个结点相连接，）个结点相连接，然后再释放第然后再释放第i个结点的存储单元个结点的存储单元 。对链表的删除操作hNULLNULL第第i-1个结点个结点 第第i个结点个结点 第第i+1个结点个结点 【例【例7.15】删除学生电

43、话簿链】删除学生电话簿链 表中指定学生的信息。表中指定学生的信息。对链表的删除操作 p=head while(strcmp(x,p-name)!=0 & p-next!=NULL) q指针跟随指针跟随p指针后移查找指针后移查找 (q=p;p=p-next;) strcmp(x,p-name)=0 T F p=head T F head=p-next q-next=p-next 没找到没找到 free(p)删除删除第一个第一个结点结点 删除中间结删除中间结点或尾结点点或尾结点 删除结点工删除结点工作分两步：作分两步：查找结点查找结点删除结点删除结点学生姓名学生姓名当姓名不同并且当姓名不同

44、并且不是尾结点循环不是尾结点循环【例【例7.15】删除学生电话簿链表中指定学生的信息。】删除学生电话簿链表中指定学生的信息。对链表的删除操作hpChang62783410Li68752341NULLWang63212986(a) 删除删除第一个结点第一个结点 (head=p-next)【例【例7.15】删除学生电话簿链表中指定学生的信息。】删除学生电话簿链表中指定学生的信息。对链表的删除操作hpChang62783410Li68752341NULLWang63212986(b) 删除删除中间结点或尾结点中间结点或尾结点 (q-next=p-next)p q【例【例7.15】删除学生电话簿链表中

45、指定学生的信息。】删除学生电话簿链表中指定学生的信息。 对链表的删除操作hpChang62783410Li68752341NULLWang63212986pp(c) 未找到指定的结点未找到指定的结点 (strcmp(x,p-name)!=0) qq if (strcmp(x,p-name)=0) if (p=head) head=p-next; /* 删除头结点删除头结点 */ else q-next=p-next; /* 删除中间或尾结点删除中间或尾结点 */ free(p); /* 释放被删除的结点释放被删除的结点 */ else printf(Not found.); /* 未找到指定的

46、结点未找到指定的结点 */ h=head; return h;#include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ; 对链表的删除操作struct node *delnode(struct node *head, char *x) struct node *p,*q; static struct node *h; if (head=NULL) printf(This is a empty list.); /*

47、 空链表情况空链表情况 */ return head; p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q=p;p=p-next; /* q指针尾随指针尾随p指针向表尾移动指针向表尾移动 */查找结点查找结点 将一个新结点插入到链表中，首先要寻找插入的将一个新结点插入到链表中，首先要寻找插入的位置。如果要求在第位置。如果要求在第i个结点前插入，可设置三个工个结点前插入，可设置三个工作指针作指针p0、p和和q，p0是指向待插入结点的指针。利是指向待插入结点的指针。利用用p和和q指针查找第指针查找第i个结点，找到后再将新结点链接个结点，

48、找到后再将新结点链接到链表上。到链表上。 对链表的插入操作 在单向链表中插入结点在单向链表中插入结点 hNULL第第i个结点个结点ppqqp0p新的第新的第i个结点个结点 head=NULL T F p=head head=p0 while(strcmp(x,p-name)!=0 & p-next!=NULL) p0-next q指针跟随指针跟随p指针后移查找指针后移查找 (q=p;p=p-next;) =NULL strcmp(x,p-name)=0 T F p=head T F p-next=p0 head=p0 q-next=p0 p0-next=NULL p0-next=p【例

49、【例7.16】在学生电话簿链表中插入一个学生的信息。】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。找到指定学生，则追加在链表尾部。 对链表的插入操作当姓名不同并且当姓名不同并且不是尾结点循环不是尾结点循环空表时空表时插入插入结点结点在表尾在表尾追加结点追加结点 插入结点工插入结点工作分两步：作分两步：查找插查找插入位置入位置连接连接新结点新结点在表头在表头插入结点插入结点 在表中间在表中间插入结点插入结点 【例【例11.16】在学生电话簿链表中插入一个学生的信息。要】在学生电话簿链

50、表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。定学生，则追加在链表尾部。对链表的插入操作hpChang62783410Li68752341NULLWang63212986(a) 在在表头表头插入结点插入结点 (head=p0; p0-next=p)Zhao62758421p0【例【例7.16】在学生电话簿链表中插入一个学生的信息。要求】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。

51、定学生，则追加在链表尾部。对链表的插入操作hChang62783410Li68752341NULLWang63212986(b) 在表中间插入结点在表中间插入结点 (q-next=p0; p0-next=p)pqZhao62758421p0【例【例7.16】在学生电话簿链表中插入一个学生的信息。要求】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。学生，则追加在链表尾部。对链表的插入操作hpChang62783410Li68752341NULLWang63212986pp(c) 在

52、表尾追加结点在表尾追加结点 (p-next=p0; p0-next=NULLNULL) qq Zhao62758421p0Zhao62758421NULL if (strcmp(x,p-name)=0) if (p=head) head=p0; /* 在表头插入结点在表头插入结点 */ else q-next=p0; /* 在表中间插入结点在表中间插入结点 */ p0-next=p; else p-next=p0; /* 在表尾插入结点在表尾插入结点 */ p0-next=NULL; h=head; return h; struct node *insert(struct node *head

53、, struct node *p0, char *x) struct node *p,*q; static struct node *h; if (head=NULL) head=p0; /* 空表时，插入结点空表时，插入结点 */ p0-next=NULL; else p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q=p;p=q-next; 查找插入点查找插入点 对链表的插入操作#include #include #define NEW (struct node *)malloc(sizeof(struct node)struc

54、t node char name20,tel9; struct node *next; ;对链表的综合操作【例【例7.17】学生电话簿链表管理程序。】学生电话簿链表管理程序。 编制此程序可利用例编制此程序可利用例7.13至例至例7.16的的4个函数完成链表个函数完成链表的建立、输出、删除和插入等功能，这里只需编制一个的建立、输出、删除和插入等功能，这里只需编制一个main函数完成对这函数完成对这4个函数的调用。个函数的调用。 #include #define NEW (struct node *)malloc(sizeof(struct node) struct node char name2

55、0,tel9; struct node *next; ;11.7.8 对链表的综合操作main( ) struct node *create( ),*delnode(struct node *, char *); struct node *insert(struct node *, struct node *, char *); void prlist(struct node *); struct node *head=NULL,*stu; char s80,name20; int c;11.7.8 对链表的综合操作do do printf(n * * * * MENU * * * * n);

56、 printf( 1. Create a list n); printf( 2. Print a list n); printf( 3. Delete a node n); printf( 4. Insert a node n); printf( 0. Quit n); printf( Enter your choice(0-4): ); gets(s); c=atoi(s); while(c4); 可以先选择可以先选择1 1建建立一个链表，然立一个链表，然后根据需要选择后根据需要选择功能功能2 2、功能、功能3 3、功能功能4 4、直到选、直到选择择0 0退出程序的退出程序的运行运行 11.

57、7.8 对链表的综合操作 switch(c) case 1: head=create( ); break; case 2: prlist(head); break; case 3: printf(nInput a name deleted:n); gets(name); head=delnode(head,name); break; case 4: stu=NEW; printf(nInput a new noden); printf(name: ); gets(stu- -name); printf(tel: ); gets(stu- -tel); stu- -next=NULL; prin

58、tf(nInsert positionn); printf(name: ); gets(name); head=insert(head,stu,name); while (c); 结构体类型解决了如何描述一个逻辑上相关，但结构体类型解决了如何描述一个逻辑上相关，但数据类型不同的一组分量的集合。数据类型不同的一组分量的集合。 在需要节省内存储空间时，在需要节省内存储空间时，c c语言还提供了一种语言还提供了一种由若干个不同类型的数据项组成，但由若干个不同类型的数据项组成，但共享同一存储空共享同一存储空间间的构造类型。的构造类型。7.8 共用体7.8.1 7.8.1 共用体及共用体变量的定义共用体

59、及共用体变量的定义一种构造类型数据一种构造类型数据 共用体共用体由若干不同类型的数据项组成，由若干不同类型的数据项组成， 构成共用体的各个数据项称为构成共用体的各个数据项称为共用体成员共用体成员。由于共享的特性，由于共享的特性，只有最新只有最新存储的数存储的数据是有效的。据是有效的。 union 共用共用体名体名 数据类型数据类型1 成员名成员名1; 数据类型数据类型2 成员名成员名2; 数据类型数据类型n 成员名成员名n; ;7.8.1 共用体及共用体变量的定义lunion为关键字；为关键字；l共用体名共用体名是用户定义是用户定义的的类型标识类型标识。l 中是组成该共用体中是组成该共用体的的

60、成员成员。成员的。成员的数据数据类型类型可以是可以是C语言所允语言所允许的任何数据类型。许的任何数据类型。共用体类型定义的一般形式：共用体类型定义的一般形式：例如：例如： union utype int i; char ch; long l; char c4; ;7.8.1 共用体及共用体变量的定义 定义了一个定义了一个union utypeunion utype共用体共用体类型，类型，共用体类型定义不分配内存共用体类型定义不分配内存空间空间，只是说明此类型数据的组成，只是说明此类型数据的组成情况。情况。 共用体变量的定义形式一形式一: : union data int i; char ch; float f; a,b;形式二形式二: : union data int i; char