第八部分结构和联合类型.ppt

《第八部分结构和联合类型.ppt》由会员分享，可在线阅读，更多相关《第八部分结构和联合类型.ppt（109页珍藏版）》请在三一文库上搜索。

1、第八章 结构和联合类型,武汉大学计算机学院,主讲：谭成予 ,教 材: C程序设计导论,本讲重点,结构类型是一种构造数据类型 用途：把不同类型的数据组合成一个整体-自定义数据类型,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . ；,成员类型可以是 基本型或构造型 (数组、指针或其 他结构类型）,struct是关键字, 不能省略,合法标识符 可省:无名结构类型,结构类型,例 struct student long int order; char name20; char sex; short int age; int score10; char addr30; ;,结构类型定

2、义描述结构 的组织形式,不分配内存,结构类型定义的作用域,结构类型,例 struct id_card char name30; char sex; char nationality20; struct date int year,month,day; birthday; char *p_addr; struct date signed_date; long number; char *office; ;,同一结构类型各成员不能同名,不同结构类型成员可以同名,结构类型可以嵌套定义,结构类型,例 struct wrong char name30; int count; struct wrong a

3、; ;,结构类型不能递归定义,结构类型,一般形式： struct 结构名 类型标识符 成员名； 类型标识符 成员名； . ； struct 结构名 变量名表列；,结构变量的定义,先定义结构类型，再定义结构变量,例 struct student long int order; char name20; char sex; short int age; int score10; char addr30; ; struct student stu1,stu2;,/*struct coord表示屏幕上一个点的坐标*/ 例 struct coord float x; float y; ; struct

4、coord first,second;,结构变量的定义,例 #define STUDENT struct student STUDENT long int order; char name20; char sex; short int age; int score10; char addr30; ; STUDENT stu1,stu2;,结构变量的定义,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . 变量名表列；,一般形式：,定义结构类型的同时定义结构变量,结构变量的定义,例 struct student long int order; char name20; char

5、 sex; short int age; int score10; char addr30; stu1,stu2;,例 struct coord float x; float y; first,second; /*struct coord表示屏幕上一个点的坐标*/,结构变量的定义,直接定义结构类型变量,结构变量的定义,例 struct long int order; char name20; char sex; short int age; int score10; char addr30; stu1,stu2;,例 struct float x; float y; first,second;

6、 /*struct coord表示屏幕上一个点的坐标*/,结构变量的定义,说明 结构类型与结构类型变量概念不同 类型:不分配内存； 变量:分配内存 类型:不能赋值、存取、运算; 变量:可以 结构类型可嵌套 结构类型成员名与程序中变量名可相同，不会混淆 结构类型及变量的作用域与生存期,结构变量的定义,结构变量的定义,结构变量的定义,结构类型变量的引用,引用规则 结构类型变量不能整体引用,只能引用变量成员 引用方式：结构类型变量名.成员名 可以将一个结构类型变量赋值给另一个结构类型变量 结构类型嵌套时逐级引用,成员(分量)运算符 优先级: 1 结合性:从左向右,结构类型变量不能整体引用,只能引用变

7、量成员 引用方式： 结构类型变量名.成员名,结构类型变量的引用,结构类型变量的引用,不能整体引用,结构类型变量的引用,不能整体引用,结构类型嵌套时逐级引用,结构类型变量的引用,例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu1,stu2;,stu1.birthday.month=12;,结构类型嵌套时逐级引用,结构类型变量的引用,/*L8-1.C: 计算某个同学5门课程成绩的平均分。*/ #include int main(void) struct stu

8、dent char *name; /*姓名*/ long order; /*学号*/ int score5; /*成绩*/ float average; /*平均分*/ who; int sum=0,n; printf(“input name,order and 5 scoresn”); scanf(“%s%ld”,who.name,char name20;,for(n=0;n5;n+) scanf(“%d”, ,/*L8-2.C: 输入矩形左上角和右下角坐标，计算该矩形长和宽及面积。*/ #include #include int main(void) float length,width,

9、area; struct coord float x,y; ; struct rectangle struct coord topleft,bottomrt；mybox; printf(“enter the top left x,y coordinate:n”); scanf(“%f%f”, ,struct 结构类型名 类型标识符 成员名； 类型标识符 成员名； . ； struct 结构类型名 结构类型变量=初始数据；,形式一：,结构变量的初始化,例 struct student int num; char name20; char sex; int age; char addr30; ;

10、struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,结构变量的初始化,例 struct student char name20; long order; int score5; float average; ; struct student who=“Wang Lin”,031112,92,91,89,87,94,0.0;,结构变量的初始化,例 struct coord float x,y; struct rectangle struct coord topleft; struct coord bottomrt; ; str

11、uct rectangle mybox=1.8,8.3,12.4,1.29;,结构变量的初始化,struct 结构类型名 类型标识符 成员名； 类型标识符 成员名； . 结构类型变量=初始数据；,形式二：,结构变量的初始化,例 struct student int num; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,初值表中初值的个数=结构变量长远的个数,结构变量的初始化,例 struct student char name20; long order;

12、int score5; float average; who=“Wang Lin”,031112,92,91,89,87,94,0.0;,例 struct coord float x,y; struct rectangle struct coord topleft; struct coord bottomrt; mybox=1.8,8.3,12.4,1.29 ;,结构变量的初始化,struct 类型标识符 成员名； 类型标识符 成员名； . 结构类型变量=初始数据；,形式三：,结构变量的初始化,例 struct int num; char name20; char sex; int age;

13、char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,结构变量的初始化,例 struct char name20; long order; int score5; float average; who=“Wang Lin”,031112,92,91,89,87,94,0.0;,例 struct coord float x,y; struct struct coord topleft; struct coord bottomrt; mybox=1.8,8.3,12.4,1.29;,结构变量的初始化,本讲重点,指向结构类型变量的指针

14、定义形式：struct 结构类型名 *结构类型指针名; 例 struct student *p;,存放结构类型变量在内存的起始地址,struct student stu1; struct student *p= (*p).num=101,结构类型和指针,结构类型和指针,(*结构类型指针名).成员名,结构类型指针名-成员名,结构类型变量名.成员名,使用结构类型指针变量引用成员形式,指向运算符 优先级: 1 结合方向：从左向右,例 int n; int *p= n=10,结构类型和指针,int main(void) struct student long int num; char name20;

15、 char sex; float score; stu_1,*p; p= ,例8.3 指向结构类型的指针变量,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; int main(void) struct student *p; for(p=stu;pnum,p-name,p-sex,p-age); return 0; ,例 指向结构类型数组的指针,/*L8-3.C: 分析下面程序的运行结果

16、*/ #include int main(void) struct int x; int y; a2=1,2,3,4,*p=a; printf(“%d,”,+p-x); printf(%dn”,(+p)-x); return 0; ,1,2,3,4,2,2,3,结构类型和指针,本讲重点,形式一: struct student int num; char name20; char sex; int age; ; struct student stu2;,结构数组的定义,三种形式：,形式二: struct student int num; char name20; char sex; int ag

17、e; stu2;,结构数组的定义,形式三: struct int num; char name20; char sex; int age; stu2;,结构数组的定义,结构数组初始化,顺序初始化: 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 int num; char name20; char sex; int age; stu

18、=,;,例 struct student int num; char name20; char sex; int age; stu =,;,结构数组初始化,结构数组引用,引用方式： 结构数组名下标.成员名,例8.4 统计后选人选票,struct person char name20; int count; leader3=“Li”,0,“Zhang”,0,”Wang“,0; int main(void) int i,j; char leader_name20; for(i=1;i=10;i+) scanf(“%s“,leader_name); for(j=0;j3;j+) if(strcmp(

19、leader_name,leaderj.name)=0) leaderj.count+; for(i=0;i3;i+) printf(“%5s:%dn“,leaderi.name,leaderi.count); return 0; ,应用举例,例8.5 编程，输入10个学生的姓名和数学、英语和语文三门功课的成绩，计算每个学生的平均成绩，并输出学生姓名和平均成绩。,#include #define N 30 struct student char name20; /*学生姓名*/ float math; /*数学成绩*/ float eng; /*英语成绩*/ float cuit; /*语文成

20、绩*/ float aver; /*平均成绩*/ ;,int main( void) struct student sN; int i; for(i=0;iN;i+) printf(“请输入第%d学生的数据n”,i+1); printf(“姓名：”); gets(si.name); printf(“数学、英语、语文成绩：”); scanf(“%f,%f,%f ”, ,例8.6 输入N个整数，记录输入的数和序号，按从小到大的顺序排列（如果两个整数相同，按输入的先后次序排列）。输出排序以后的每个整数和它原来的序号。,#include #define N 10 struct data int no;

21、 int num; ; int main(void ) struct data xN,temp; int i,j; /*输入10个整数*/ printf(“输入10个整数：”); for(i=0;iN;i+) scanf(“%d”, ,int main( void) struct student sN; int i; for(i=0;iN;i+) printf(“请输入第%d学生的数据n”,i+1); printf(“姓名：”); gets(si.name); printf(“数学、英语、语文成绩：”); scanf(“%f,%f,%f ”, ,例8.7, 问题描述：n个小孩围成一圈，依次编号

22、。老师指定从第w个小孩开始报数，报数为s的小孩出列；然后从下一个小孩开始重新报数，重复上述过程，直到所有小孩都出列。,分析：数据结构，如何表示队列和小孩？ 每个小孩用一个结构类型表示： struct child int ino; /*当前小孩编号*/ int next; ; /*下一个小孩编号*/ n个小孩组成队列用结构数组表示： struct child linkN+1; /*下标为0的元素不使用*/ N为可以容纳的人数上限,约瑟夫问题,分析：算法： （1）初始化队列link: linkk.nextk+1 k=1,n-1 linkn.next1 （2）开始报数 if(linkk.ino!=0

23、) 如果第k个小孩在队列中 I+1I 报数变量I 加1 （3）如果I =s，则第k个人出列，转（5），否则转（4） （4） k更新为下一个小孩编号 klinkk.next, 转（2） （5）输出第k个小孩编号linkk.ino （6）linkk.ino0表示已经出列 （7）已经出列人数加1count （8） 如果count等于总人数n，则转（9） ，否则转（2） （9）算法结束,约瑟夫问题,#include #define N 100 /*程序能够处理的人数上限*/ int main() struct child int ino,next;linkN+1; int I,n_child,whic

24、h,com_out,k,count; /*输入已知数据：小孩实际人数、初始报数小孩编号、出列的编号*/ scanf(“%d%d%d”,/*出列人数*/,while(count!=n_child) I=0;/*报数的数值*/ while(1) if(linkk.ino!=0) I+; if(I=come_out) break; k=linkk.next; printf(“%dt”,linkk.ino);/*输出出队小孩编号*/ linkk.ino=0;/*第k个小孩出队*/ count+; /*出队人数加1*/ if(count%10=0) printf(“n”); printf(“bye!n”

25、); return 0; ,例8.8 编程实现两个复数的乘法运算。,分析： 一个复数由实部和虚部组成，可以用含有两个浮点数类型的成员的结构类型来表示： struct complex float re; /*实部*/ float im; /*虚部*/ ; struct complex x,y; x*y的结果的实部为x.re*y.re-x.im*y.im x*y的结果的虚部为x.re*y.im +x.im*y.re,#include struct complex float re; float im; ; int main( void) struct complex x, y, z; printf

26、(“请输入第1个复数n”); printf(“实部：”); scanf(“%f”, ,例8.9 编程计算当前时间的下一秒的时间。,分析： 时间由时、分、秒构成，采用一个结构类型来表示时间： struct time int hour; /*时*/ int minutes; /*分*/ int second; /*秒*/ ;,#include struct time int hour; int minutes; int second; int main(void ) struct time now,ntime; printf(“请输入当前时间，时间格式：时：分：秒n”); scanf(“%d:%d

27、:%d”, ,本讲重点,引用自身的结构,例如， struct tnode char word20; int count; struct tnode*left; struct tnode*right; ;,结构成员：指向自身所属的结构类型的对象,常用于构造各种数据结构：队列、链表、树、图等。,链接方式存储的线性表简称为链表（Linked List），是常见的数据结构。 链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继

28、结点的地址（或位置）信息（称为指针（pointer）或链(link)）,什么是链表？, datanext data域-存放结点值的数据域 next域-存放结点的直接后继的地址（位置）的指针域（链域） 例如： struct node int data; struct node *next;,链表的结点结构,单链表：每个结点只有一个链域的链表。,head：链表的头指针,链表分类,循环链表,链表分类,双向链表：每个结点有两个链域的链表。,NULL,链表分类,1,2,3,链表中结点都在程序中定义，不是临时开辟的，用完后不能释放，并且，链表中可以创建的结点数有限制。称为“静态链表”,静态链表,#incl

29、ude #include struct node int data; struct node *next; ; int main() struct node a,b,c,*head;*p; a.data=1; b.data=2; c.data=3; head=,c.next=NULL; p=head; do printf(“%dt”,p-data); p=p-next; while(p!=NULL); return 0; ,建立链表 遍历链表 删除链表中的结点 插入结点 以单链表为例进行说明。,对链表的操作,结点类型： struct child char name20; struct chil

30、d *next; *new,*head,*tail;,先进先出链表,(1)头指针置空 head=NULL; (2)创建新结点 new=(struct child*)malloc(sizeof(struct child); new-next=NULL; (3)新结点连入链表 if(head=NULL) head=new; tail=new; else tail-next=new; 重复（2）、（3）步直到链表创建完成。,建立链表(尾插法建表）,建立链表(尾插法建表）,#include #include struct node int data; struct node *next; struct

31、 node * creatrightlink-_1() struct node *head,*new,*tail; int n; head=NULL; scanf(“%d”, ,建立链表(尾插法建表）,#include #include struct node int data; struct node *next; int creatrightlink_2(struct node *phead) struct node *new,*tail; int n,k=0; *phead=NULL; scanf(“%d”, ,(1)头指针置空 head=NULL; (2)创建新结点 new=(stru

32、ct child*)malloc(sizeof(struct child); (3)新结点连入链表 new-next=head; head=new; 重复（2）、（3）步直到链表创建完成。,后进先出链表,建立链表(头插法建表）,建立链表(头插法建表）,#include #include struct node int data; struct node *next; struct node * creatleftlink_1() struct node *head,*new; int n; head=NULL; scanf(“%d”, ,建立链表(头插法建表）,#include #includ

33、e struct node int data; struct node *next; int creatleftlink_2(struct node *phead) struct node *new; int n,k=0; *phead=NULL; scanf(“%d”, ,head=NULL; 创建新结点 new=(struct child*)malloc(sizeof(struct child); 找到标记结点marker（新结点插入在标记结点的后面） 新结点连入链表 new-next=marker-next; marker-next=new; 重复（2）、（3）、（4）步直到链表创建完成

34、。,在链表中间插入结点，一般用于建立有序链表,建立链表,p=head; while(p!=NULL) puts(p-name);/*输出当前结点数据*/ p=p-next;/*p更新为下一个结点地址*/ ,功能：将整个链表的数据从头到尾扫描一遍,遍历链表,#include #include struct node int data; struct node *next; void printlink(struct node *head) struct node *p; p=head; while(p!=NULL) printf(“%dn”,p-data; p=p-next; ,（1）找到要删除

35、的结点，current指向该结点，p指向要删除结点的前趋结点。 （2）如果要删除的结点为头结点，则 head=current-next; （3）如果要删除的结点不是头结点，则 p-next=current-next （4）释放已经删除的结点 free(current);,从链表中删除结点,从链表中删除结点,#include #include struct node int data; struct node *next; ; struct node * deletelink_1(struct node *head,int n) struct node *p,*q; p=head; while(

36、p-data!=n ,从链表中删除结点,#include #include struct node int data; struct node *next; ; int deletelink_2(struct node *phead,int n) struct node *p,*q; p=*phead; while(p-data!=n ,向一个有序链表中插入新结点（new)。 （1）找到要插入结点的位置，插入在r指向的结点前面， p指向的结点后面。 （2）如果要插入在头结点前面，则 new-next=head; head=new; （3）如果要插入的位置不是头结点前面，则 new-next=r

37、; p-next=new;,将一个结点插入一个已经存在的链表中，例如插入在链表尾部、头部或者插入在一个有序链表中。,插入结点,插入结点,#include #include struct node int data; struct node *next; struct node * insertsort(struct node *head, int n) struct node *new,*p,*q; new=(struct node *)malloc(sizeof(struct node); new-data=n; p=head; while(p!=NULL ,插入结点,struct node

38、 * creatsortlink(struct node *head) int n; head=NULL; scanf(“%d”, ,本讲重点,构造数据类型,也叫共用体 用途：使几个不同类型的变量共占一段内存(相互覆盖）,union 联合名 类型标识符 成员名； 类型标识符 成员名； . ；,例 union data int i; char ch; float f; ;,类型定义不分配内存,联合的定义,联合类型定义 定义形式：,形式一: union data int i; char ch; float f; a,b;,形式二: union data int i; char ch; float

39、f; ; union data a,b,c,*p,d3;,形式三: union int i; char ch; float f; a,b,c;,联合变量的定义,联合变量定义分配内存, 长度=最长成员所占字节数,联合变量任何时刻 只有一个成员存在,联合变量的定义,引用方式：,联合变量引用,例 union int i; char ch; float f; a; a=1; (),引用规则 不能引用联合变量，只能引用其成员,联合变量引用,例 a.i=1; a.ch=a; a.f=1.5; printf(“%d”,a.i); (编译通过，运行结果不对),联合变量引用,引用规则 联合变量中起作用的成员是最

40、后一次存放的成员,例 union int i; char ch; float f; a=1,a,1.5; (),联合变量引用,引用规则 不能在定义联合变量时初始化,例 float x; union int i; char ch; float f; a,b; a.i=1; a.ch=a; a.f=1.5; b=a; () x=a.f; (),引用规则 可以用一个联合变量为另一个变量赋值,联合变量引用,例 将一个整数按字节输出,i=60501 ch0=101,ch1=141 ch0=A,ch1=a,int main() union int_char int i; char ch2; x; x.i=

41、24897; printf(“i=%on“,x.i); printf(“ch0=%o,ch1=%on ch0=%c,ch1=%cn“, x.ch0,x.ch1,x.ch0,x.ch1); return 0; ,运行结果：,区别：存储方式不同 联系：两者可相互嵌套,结构类型与联合,例 结构类型中嵌套联合,struct int num; char name10; char sex; char job; union int class; char position10; category; person2;,例联合中嵌套结构类型，机器字数据与字节数据的处理,struct w_tag char low

42、; char high; ; union u_tag struct w_tag byte_acc; int word_acc; u_acc;,例 编程，输入一个长整型的整数，分别取出该数的各字节的值。,分析： 定义一个联合类型如下所示： union data char s5; long n; ;,例 编程，输入一个长整型的整数，分别取出该数的各字节的值。,#include union data char s5; long n; ; int main(void ) union data x; int i; printf(“输入一个长整数：”); scanf(“%x”, ,例 编程存放学生的下述信

43、息：姓名、学号和当前住址，其中学生当前 住址有两种情况：在校住宿学生用学校地址（楼房名和房间号），非在校 学生用家庭住址（街道号、街道名和城市名）。并输出指定姓名学生的当 前住址。,struct off_school int strnum; /*街道号*/ char strname20; /*街道名*/ char city20; /*城市名*/ ; struct in_school int roomnum; /*房间号*/ char dorm20; /*楼房名*/ ; union address struct off_school town; struct in_school gown; ;,

44、struct student int num; /*学号*/ char name20; /*姓名*/ char off_in; /*是否在学校住*/ union address ad; /*当前住址*/ ;,#include include #define N 3 struct off_school int strnum; char strname20; char city20; ; struct in_school int roomnum; char dorm20; ; union address struct off_school town; struct in_school gown;

45、;,struct student int num; char name20; char off_in; union address ad; ;,int main( void) struct student sN; char name20; int i; for (i=0;iN;i+) printf(“请输入第%d个学生数据n”,i+1); printf(“学号：”); scanf(“%d”,printf(“是否在校住宿学生（n在校住宿、其他表示非在校住宿）：”); si.off_in=getchar( ); printf(“请输入当前地址n”); i f (si.off_in=n) printf(“请输入房间名和房间号：”); scanf(“%d%s”, ,printf(“输入姓名”); gets(name); for (i=0;iN;i+) if (! strcmp(si.name, name) if (si.off_in=n) printf(“姓名：%s是在校住宿学生n”,si.name); printf(“楼房名：%s 房间号%dn”,