北京邮电大学C语言课件第9章-结构体与链表.ppt

1、第九章第九章 结构体与链表结构体与链表内容提要内容提要 结构体类型的定义结构体类型的定义 结构体类型变量结构体类型变量 结构体类型数组结构体类型数组 结构体类型指针结构体类型指针 结构体与函数结构体与函数 链表链表C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体概述结构体概述(1) 结构体结构体1.什么叫结构体：什么叫结构体：把不同类型的数据组合成一个整体的自定把不同类型的数据组合成一个整体的自定义义数据类型数据类型, 是是一种构造数据类型一种构造数据类型。2.结构体类型定义结构体类型定义struct 结构体名结构体

2、名 类型标识符类型标识符 成员名成员名1； 类型标识符类型标识符 成员名成员名2； .；成员类型可以是成员类型可以是基本型或构造型基本型或构造型struct是是关键字关键字,不能省略不能省略合法标识符合法标识符可省可省:无名结构体无名结构体C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体概述结构体概述(2) 定义结构体类型，描述下列数据定义结构体类型，描述下列数据 (1) (1) 学生情况学生情况: : 包含学生的学号、包含学生的学号、 姓名、姓名、 性别、性别、 年龄、年龄、C C语言语言课程成绩课程成绩: :st

3、ruct studentint no； /*学号学号*/ char name10； /*姓名姓名*/ char sex； /*性别性别*/ int age； /*年龄年龄*/ float score； /*C成绩成绩*/；注：注：；不能省不能省结构体类型定义描述结构结构体类型定义描述结构的组织形式的组织形式, ,不分配内存不分配内存C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计如考虑如考虑1010门课程成绩，门课程成绩， 加上总成绩与平均加上总成绩与平均成绩，可作如下定义成绩，可作如下定义: : struct stude

4、ntint no； /*学号学号*/ char name10； /*姓名姓名*/ char sex； /*性别性别*/ int age； /*年龄年龄*/ float score10； /*10门课程成绩门课程成绩*/ float tcj， acj； /*总成绩，总成绩， 平均成绩平均成绩*/； C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计 定义结构体类型，描述下列数据定义结构体类型，描述下列数据 (2)(2)个人数据个人数据: : 包含姓名、性别、年龄、身高、体重、包含姓名、性别、年龄、身高、体重、住址住址: :st

5、ruct personchar name20； /*姓名姓名*/char sex； /*性别性别*/int age； /*年龄年龄*/float height； /*身高身高*/float weight； /*体重体重*/char addr50； /*住址住址*/； C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计(3)(3)日期结构体类型包括日期结构体类型包括年、月、日年、月、日: :struct dateint year； /*年年*/month； /*月月*/day； /*日日*/；(4)(4)如职工信息结构体类型如

6、职工信息结构体类型: :struct personchar name20; /*姓名姓名*/char address40; /*地址地址*/float salary; /*工资工资*/float cost; /*扣款扣款*/struct date hiredate; /*聘任日期聘任日期*/; 结构体类型可以嵌套定义即一个结结构体类型可以嵌套定义即一个结构体类型中的某些成员又是其他结构体类型中的某些成员又是其他结构体类型构体类型C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体类型变量的定义结构体类型变量的定义(1)

7、先定义结构体类型，再定义结构体变量先定义结构体类型，再定义结构体变量一般形式：一般形式：例例 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu1,stu2; struct 结构体名结构体名 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .；struct 结构体名结构体名 变量名表列变量名表列；例例 #define STUDENT struct student STUDENT int num; char na

8、me20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2; C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体类型变量的定义结构体类型变量的定义(2) 定义结构体类型的同时定义结构体变量定义结构体类型的同时定义结构体变量一般形式：一般形式：struct 结构体名结构体名 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .变量名表列变量名表列；例例 struct student int num; char

9、name20; char sex; int age; float score; char addr30; stu1,stu2; C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体类型变量的定义结构体类型变量的定义(3) 直接定义结构体变量（匿名定义）直接定义结构体变量（匿名定义）一般形式：一般形式：struct 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .变量名表列变量名表列；例例 struct int num; char name20; char sex; int age; fl

10、oat score; char addr30; stu1,stu2; 用用无名结构体无名结构体直接定义直接定义变量变量只能一次只能一次C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体类型声明的说明结构体类型声明的说明 说明说明结构体类型与结构体变量概念不同结构体类型与结构体变量概念不同 类型类型:不分配内存不分配内存； 变量变量:分配内存分配内存 类型类型:不能赋值、存取、运算不能赋值、存取、运算; 变量变量:可以可以结构体可嵌套结构体可嵌套结构体成员名与程序中变量名可相同，不会混淆结构体成员名与程序中变量名可相同，

11、不会混淆结构体类型及变量的作用域与生存期结构体类型及变量的作用域与生存期例例 struct date int month; int day; int year; ; struct student int num; char name20; struct date birthday; stu;numnamebirthdaymonthdayyear例例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu;numnamebirthdaymonthdayyearC C语

12、言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量的使用结构体变量的使用(1) 由结构体变量名引用其成员由结构体变量名引用其成员结构体变量结构体变量不能整体引用不能整体引用,只能引用变量只能引用变量成员成员可以将可以将一个结构体变量赋值给另一个结构体变量一个结构体变量赋值给另一个结构体变量结构体嵌套时结构体嵌套时逐级引用逐级引用引用方式：引用方式： 结构体变量名结构体变量名.成员名成员名成员成员( (分量分量) )运算符运算符优先级优先级: : 1 1结合性结合性: :从左向右从左向右例例 struct student i

13、nt 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 score; char addr30; stu1,stu2; printf(“%d,%s,%c,%d,%f,%sn”,stu1); ( )stu1=101,“Wan Lin”,M,19,87.

14、5,“DaLian”; ( )例例 struct student int num; char name20; char sex; int age; float score; char addr30; 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;例例 struct student int n

15、um; char name20; char sex; int age; float score; char addr30; stu1,stu2; if(stu1=stu2). ( )C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量的初始化（结构体变量的初始化（1） 形式一形式一：struct 结构体名结构体名 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .；struct 结构体名结构体名 结构体变量结构体变量=初始数据初始数据；例例 struct student int num

16、; char name20; char sex; int age; char addr30; ; struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量的初始化（结构体变量的初始化（2） 形式二形式二：struct 结构体名结构体名 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .结构体变量结构体变量=初始数据初始数据；例例 struct student int nu

17、m; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”; C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量的初始化（结构体变量的初始化（3） 形式三形式三：struct 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； .结构体变量结构体变量=初始数据初始数据；例例 struct int num; char name20; char sex; int ag

18、e; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”; C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量存储分配示意图结构体变量存储分配示意图stru110001020100110231026name20sexagescoreC C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计例例 9.1 求某同学上学期求某同学上学期8门课程的总成绩与平均成绩。门课程的总成绩与平均成绩。 程序如

19、下：程序如下：main（ ） int i； struct st char xm8； float cj9； float tcj， acj； stu； C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计scanf（%s， stu.xm）；）； /*输入输入*/for（i=1； i=8;i+) scan（%f， &stu.cji）；）； stu.tcj=0.0； /*求总成绩求总成绩*/for（i=1； i=8;i+) stu.tcj+=stu.cji； stu.acj=stu.tcji/8； /*求平均成绩求平均成绩*/prin

20、tf（%s的总成绩的总成绩=%6.2f, 平均成绩平均成绩=%6.2f,stu.xm,stu.tcj,stu.acj）；）； 输入数据：输入数据： CHEN 80 86 79 98 88 72 96 66运行结果：运行结果： CHEN的总成绩的总成绩=577.00， 平均成绩平均成绩= 72.13C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体类型数组结构体类型数组 结构体数组的定义结构体数组的定义三种形式：形式一: struct student int num; char name20; char sex; int

21、 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;numnamesexagenumnamesexagestu0stu125BC C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体数组初始化与引用结构体数组初始化与引用 结构体数组初始化结构体数组初始化例例 struct int

22、 num; char name20; char sex; int age; stu =,;顺序初始化顺序初始化: 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; 例例 struct student int num; char name20; char sex; int age; stu =,;分行初始化分行初始化: struct student int num; cha

23、r 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; str3;stu1.age+;strcpy(stu0.name,”ZhaoDa”);C C语言程序设计语言程序设计C C语言程

24、序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计例例 统计候选人选票统计候选人选票struct person char name20; int count;leader3=“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,leaderj.name)=0) leaderj.count+; for(i=0;i成员名成员名结构体变量名结构体变量名

25、.成员名成员名指向运算符优先级: 1结合方向：从左向右例例 指向结构体的指针变量指向结构体的指针变量main() struct student long int num; char name20; char sex; float score; stu_1,*p; p=&stu_1; stu_1.num=89101; strcpy(stu_1.name,Li Lin); p-sex=M; p-score=89.5; printf(nNo:%ldnname:%snsex:%cnscore:%fn, (*p).num,p-name,stu_1.sex,p-score);例例 int n; int *

26、p=&n; *p=10; n=10struct student stu1;struct student *p=&stu1;stu1.num=101; (*p).num=101C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计总结：总结：结构体成员变量引用方式结构体成员变量引用方式结构体变量结构体变量.成员名成员名(*p).成员名成员名p-成员名成员名其中，其中，-称为指向运算符称为指向运算符 请分析下列几种运算：请分析下列几种运算：p-np-n+p-nC C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序

27、设计语言程序设计C C语言程序设计语言程序设计指向结构体数组元素的指针指向结构体数组元素的指针例例 指向结构体数组的指针指向结构体数组的指针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; for(p=stu;pnum,p-name,p-sex,p-age);numnamesexagestu0pstu1stu2p+1C C语言程序设计语言程序设计C C语

28、言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计结构体变量作为函数参数结构体变量作为函数参数 用结构体变量的成员作参数用结构体变量的成员作参数-值传递值传递用指向结构体变量或数组的指针作参用指向结构体变量或数组的指针作参数数-地址传递地址传递用结构体变量作参数用结构体变量作参数-多值传递多值传递，效，效率低率低C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表概述（链表概述（1） 所谓链表链表是指若干个数据项数据项按一定的原则连接起来。 每个数据项都包含有若干个数据若干个数据和一个指向下

29、一个数据项的指针，依靠这些指针将所有的数据项连接成一个链表。 每个数据项称为一个“结点结点”。C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表概述（链表概述（2）a1 a2 a3 .anheadstruct studentdata nextaistruct student long num; float score;sturct student *next ;struct student *head;C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计

30、1620head李为李为2004101850586数据项数据项A数据项数据项C刘娜刘娜2004102933818数据项数据项B张三张三20041259501620 05863818一个简单链表示例：一个简单链表示例：C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表的基本操作链表的基本操作 链表的建立链表的建立 从链尾到链头：新结点插入到链头从链尾到链头：新结点插入到链头 从链头到链尾：新结点插入到链尾从链头到链尾：新结点插入到链尾 链表的插入操作链表的插入操作 根据一定的条件，把新结点插入到指定位根据一定的条件，把新结

31、点插入到指定位置置 链表的删除操作链表的删除操作 根据一定的条件，删除一个或多个结点根据一定的条件，删除一个或多个结点 链表的输出操作链表的输出操作 链表的查找操作链表的查找操作C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计建立链表操作建立链表操作(从链尾到链头从链尾到链头)headai-1. head = p; p = malloc(sizeof (struct node); p-data = ai; for(i=0; inext = head;C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序

32、设计语言程序设计C C语言程序设计语言程序设计建立链表操作建立链表操作 (从链头到链尾从链头到链尾)ai-1. p-next = q; q = malloc(sizeof (struct node); q-data = ai; for(i=0; inext = NULL;p p = q;C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表的插入操作链表的插入操作.aiai+1. p-next = q; q = malloc(sizeof (struct node); q-data = x; p if(p满足插入条件满足插入

33、条件)qx q-next = p-next;C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表的删除操作链表的删除操作.ai-1aiai+1. p-next = q-next; free(q); q = p-next;pq if(p-next满足删除条件满足删除条件)C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表的输出操作链表的输出操作.ai-1aiai+1. p = p-next;p while(p) printf(%d, p-data);C

34、 C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计链表的查找操作链表的查找操作.ai-1aiai+1. p2=p1;p1=p1-nxet ;p1 while(num!=p1-num & p1!=NULL ) printf (find: %ld %5.2fn，num，p1-score); p2C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计arga :27b: 3c :30(main)(func)parma :27b: 3c :30copyarga :27b

35、: 3c :30(main)(func)parma :18b: 5c :90arga :27b: 3c :30(main)arga :27b: 3c :30(main)C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计arga :18b: 5c :90(main)arga :27b: 3c :30(main)arga :27b: 3c :30(main)(func)parm*arga :18b: 5c :90(main)(func)parm*C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程

36、序设计C C语言程序设计语言程序设计内存动态管理函数内存动态管理函数 动态分配存储动态分配存储根据需要开辟或释放存储单元根据需要开辟或释放存储单元相关函数相关函数malloc函数函数calloc函数函数free函数函数说明说明应包含应包含malloc.h或或stdlib.hC C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计malloc函数函数 函数原型函数原型 typedef unsigned size_t; void *malloc(size_t size); 参数参数 size:分配存储空间的字节数分配存储空间的字节数

37、返回值返回值 若成功，返回指向分配区域起始地址的指若成功，返回指向分配区域起始地址的指针针 若失败，返回若失败，返回NULLC C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计calloc函数函数 函数原型函数原型 void *calloc(size_t n, size_t size); 参数参数 n :分配内存的项目数分配内存的项目数 size:分配内存的每个项目的字节数分配内存的每个项目的字节数 返回值返回值 若成功，返回指向分配区域起始地址的指若成功，返回指向分配区域起始地址的指针针 若失败，返回若失败，返回NULLC

38、C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计free函数函数 函数原型函数原型 void free(void *ptr); 参数参数 ptr:要释放的内存区地址要释放的内存区地址 说明说明 释放释放prt指向的内存区指向的内存区 释放后的内存区能够分配给其他变量使用释放后的内存区能够分配给其他变量使用C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计realloc函数函数 函数原型函数原型 void *realloc(void *ptr，unsigned int size) 参数参数 ptr:需要改变存储空间的内存区地址需要改变存储空间的内存区地址 size:将将ptr所指的存储区的大小改为所指的存储区的大小改为size个大小个大小 说明说明 用来使已分配的空间用来使已分配的空间ptr改变大小，即重新分配改变大小，即重新分配 C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计C C语言程序设计语言程序设计再见！再见！同学们：同学们：