结构与联合.ppt

1、第八章 结构与联合,8.1 结构 结构是一种构造数据类型 用途：把不同类型的数据组合成一个整体-自定义数据类型,例如，在一张学生情况表中，每个记录有很多的项目：num、name、sex、age、score、addr等，这些项都与某个学生相联系。如果将这些项目分别定义为简单变量，难以反映它们之间的内在联系。为了能反映多种不同类型的变量之间存在内在联系，我们可以将它们定义为结构。,结构类型定义,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . ；,成员类型可以是 基本型或构造型,struct是关键字, 不能省略,合法标识符 可省:无名结构,例 struct student in

2、t num; char name20; char sex; int age; float score; char addr30; ;,结构类型定义描述结构 的组织形式,不分配内存,例 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu1,stu2;,8.2 结构变量的定义 先定义结构类型，再定义结构变量 一般形式：,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . ； struct 结构名 变量名表列；,例 #define

3、 STUDENT struct student STUDENT int num; char name20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2;,定义结构类型的同时定义结构变量 一般形式：,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . 变量名表列；,例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2;,直接定义结构变量 一般形式：,struct

4、 类型标识符 成员名； 类型标识符 成员名； . 变量名表列；,例 struct int num; char name20; char sex; int age; float score; char addr30; stu1,stu2;,用无名结构直接定义 变量只能一次,说明 结构类型与结构变量概念不同 类型:不分配内存； 变量:分配内存 类型:不能赋值、存取、运算; 变量:可以 结构可嵌套 结构成员名与程序中变量名可相同，不会混淆,8.3 结构变量的引用 引用规则 结构变量不能整体引用,只能引用变量成员,可以将一个结构变量赋值给另一个结构变量 结构嵌套时逐级引用,成员(分量)运算符 优先级:

5、 1 结合性:从左向右,引用方式： 结构变量名.成员名,8.4 结构变量的初始化 形式一：,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . ； struct 结构名 结构变量=初始数据；,例 struct student int num; char name20; char sex; int age; char addr30; ; struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,形式二：,struct 结构名 类型标识符 成员名； 类型标识符 成员名； . 结构变量=初始数据；,例 struct s

6、tudent int num; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,形式三：,struct 类型标识符 成员名； 类型标识符 成员名； . 结构变量=初始数据；,例 struct int num; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,8.5 结构数组 结构数组的定义 三种形式：,形式一: struct st

7、udent 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;,结构数组初始化,例 struct int num; char name20; char sex; int age; stu =,;,顺序初始化: struct student int num; char na

8、me20; 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 person char name20; int count; leader3=“Li”,0,“Zhang”,0,”Wang“,0; main() int i,j; ch

9、ar 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;i3;i+) printf(%5s:%dn,,leaderi.count); ,8.6 结构和指针 指向结构变量的指针 定义形式：struct 结构名 *结构指针名; 例 struct student *p;,使用结构指针变量引用成员形式,存放结构变量在内存的起始地址,指向运算符 优先级: 1 结合方向

10、：从左向右,例 指向结构的指针变量,main() struct student long int num; char name20; char sex; float score; stu_1,*p; p= ,指向结构数组的指针,例 指向结构数组的指针,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-s

11、ex,p-age); ,用指向结构的指针作函数参数 用结构变量的成员作参数-值传递 用指向结构变量或数组的指针作参数-地址传递 用结构变量作参数-多值传递，效率低,struct data int a, b, c; ; main() void 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

12、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,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); ,例 用结构变量作函数参数,struct data int a

13、, 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( ,例 用结构指针变量作函数参数,8.7 动态存储分配和链表,动态数据结构 动态数据结构是在程序运行过程中通过调用系统提供的动态存储分配函数逐步建立起来的，其存储空间（即动态数据结构）的大小在程序执行过程中可以改变，也可以随时教皇

14、诶系统（成为释放空间）；访问动态数据对象只能通过由动态存储分配函数返回的指针，因为动态数据对象不是通过变量说明建立的，它没有相应的变量名。 任何构造类型的数据，包括数组、结构、联合，都可以建成动态数据结构。例如，表示学生登记表的结构数组可以用一个称为链表的动态数据结构来代替。动态数据结构特别适合于那些数据成员不固定、或者说需要经常增加或减少的数据。,最简单的动态数据结构是如下图所示的链表。,3010 3028 4016,Head 3010,结点 A 结点 B 结点 C,下一结点起址,data next,data next,data next,动态数据结构的元素称为“结点”，每个结点是类型相同的

15、一个结构变量，与数组不同的是，每个结点在存储空间上不一定相邻。结点由数据域和指针域两部分组成，数据域存放被处理的数据对象，可以由除该结构以外的任何类型的数据组成即不允许结构递归定义）；指针域用于存放下一结点的地址，即指向下一个结点的指针，结点和结点之间通过指针连接成一个数据整体。访问动态数据结构的元素只能通过存放在上一个元素中的指针进行。,由于每个结点都是类型相同的一个结构变量，所以结点中指向下一个结点的指针是一个指向自身的结构指针，这样的结构称为引用自身的结构。任何动态数据结构的元素的数据类型一定是引用自身的结构（不是结构的递归定义，结构中不允许包含自身结构，但可以包含指向自身的结构指针）。

16、 链表是动态数据结构最基本的形式，在应用软件和系统软件设计中是很有用的数据结构。我们主要学习单向链表的建立、输出、插入和删除的方法。,用于动态存储分配的函数,void *malloc( n ) void *calloc( m,n ) void free( *p ) void *realloc( *p, n ),分配 n 个字节的内存空间 分配 m 个 n 字节的空间 释放指针p所指的存储空间 将指针p所指的空间大小改为n字节,参数中的整数均为无符号整数 若内存分配失败，函数返回 NULL,sizeof 运算符 sizeof 是一个单目运算符，用于计算一个对象的大小。它是在编译时执行的运算。 s

17、izeof 表达式有两种形式： sizeof(类型名或表达式)或sizeof 表达式 其中“表达式”操作数可以是结果为任何数据类型的表达式；“（类型名）”操作数可以是除 void 之外的任何数据类型的类型名。类型名必须用（）括起来，而表达式可以有或无（）。 以“（类型名）”为操作数时，sizeof的运算结果是类型名所示类型的存储字节数；以表达式为操作数时，结果为表达式类型的存储字节数。,若有定义： float x; struct data int a, b, c; arg; 则 sizeof(x) 或 sizeof(float) 结果均为 4 sizeof arg 或 sizeof(struc

18、t data) 结果均为 6 sizeof(char)结果为 1 sizeof(short)结果为 2 sizeof(int)结果为 2（16位机），或 4（32位机） sizeof(float)结果为 4 sizeof(double)结果为 8,3010 3028 4016,Head 3010,链头 结点 B 链尾,下一结点起址,data next,data next,data next,链表：,链表中第一个结点称为链头，最后一个结点称为链尾，整个链表有一个头指针，头指针是一个链表结点类型的指针变量，用于保存链头的地址，链尾的指针域存放的是空指针，表示不指向任何结点。,头指针的作用好比数组名

19、,通过数组名可以引用数组的任一元素，通过头指针可以跟踪找到链表中任何一个结点。链尾指针域NULL的作用好比字符串末尾的空字符0，空字符0用于标志一个字符串的结束，NULL用于标志一个链表的结束。 下面以整数链表（每个结点的数据域是一个整数）为例，说明链表结点结构类型定义、头指针说明及结点引用的形式。 例如： struct intnode int data; struct intnode *next; ; struct intnode *head; 上述说明定义 intnode 为一个整数结点的结构类型，它包含两个成员，一个是结点的数据域，即整型变量 data ;另一个是结点的指针域，即 str

20、uct intnode * 类型的指针变量 next （指向自身的指针）。head 说明为该结点结构类型(struct intnode *)的指针变量。,链表的一些特点,对单向链表中结点的访问只能从“头指针”开始。如果没有“头指针”，就无法进入链表，也无法访问其中各个结点。对单向链表中结点的访问只能顺序地进行 单向链表中最后一个结点中的指针项必须是NULL，不指向任何结点。 如果断开链表中某一处的链，则其后的结点都将“失去联系”，它们虽然在内存中存在，但无法访问到它们。,3010 3028 4016,Head 3010,链头 结点 2 链尾,data next,data next,data n

21、ext,假定 head 已指向链头（即为结点1的地址），d1，d2，.，dn 分别表示链表的结点1至结点n中的数据，则下面的表达式是对该链表中前三个节点的引用： head-data head-next head-next-data head-next-next head-next-next-data head -next-next-next,结点1的数据成员，结果为 d1 结点1的指针成员，结果为结点2的地址 结点2的数据成员，结果为 d2 结点2的指针成员，结果为结点3的地址 结点3的数据成员，结果为 d3 结点3的指针成员，结果为NULL,链表的建立和输出 算法的关键是建立一个结点，建立链

22、表的过程就是重复执行建立一个结点的过程。 首先必须说明头指针（head）并使其具有初值 NULL ，还要说明一个暂时保存当前新建节点存储地址的指针（p）,以及一个指向链尾的指针（tail）；最先建的结点是链头，其地址应保存在头指针中，这与其后建的结点在连接方法上不同，所以第一个结点的建立不能包含在循环语句中，必须在进入循环之前先建立第一个结点。 指针说明与赋值如下： struct intnode *head=NULL, *tail, *p; 使头指针初值为 NULL 以表明头指针当前指向的是一个空链。,建立一个结点的方法和步骤： 1.为新结点分配存储单元，并使 p 指向新结点 p=(struc

23、t intnode *)malloc(sizeof(struct intnode); sizeof(struct intnode)是一个结点的大小;(struct intnode *)是类型强制符，由于malloc的返回值是 void 指针，所以类型强制符不是必须的，只是为了阅读程序时使含义更清楚。,head,p,2.将数据存入新建结点的数据域 scanf(“%d”,data,3.将第一个结点连入链中 p-next=NULL; 每建一个结点时都要保证新结点是链尾 head=p; 使头指针指向建立的第一个结点。,NULL,3010,3010,.使链尾指针指向新结点 tail=p;,3010,30

24、18,head,data,NULL,3010,3010,建其余结点的方法和步骤： 1.与第一个结点相同：为新节点分配存储单元，并使p指向新结点 p=(struct intnode *)malloc(sizeof(struct intnode);,2.与第一个结点相同：将数据存入新建结点的数据域 scanf(“%d”,3.将新建结点连入链表末尾 p-next=NULL; 使新结点成为新的链尾。,.与第一个结点相同：使链尾指针指向新结点 tail=p;,data,tail-next=p; 使链表中原来的链尾指针指向新结点。,NULL,p,data,NULL,0,输出链表所有结点的方法和步骤： 1、

25、开始时使遍历指针指向链头； p = head; 2.如果链表不为空（p 不等于 NULL）,输出当前结点的数据域； printf(“%6d”,p-data); 3.每输出一个元素之后修改 p 的值,使遍历指针移向下一个结点; p = p-next; 4.重复2和3，直到链表为空（p 等于 NULL）。,3018,head,data,3018,3010,3010,4016,P.234.【例 8.6】输入一批整数，以 0 为结束，将它们建成一个链表（0不包含在链中），然后输出链表所有结点的数据域。,#include #include/*函数malloc所需的头文件*/ struct intnode

26、 int data; struct intnode *next; ; void main(void) int n; struct intnode *head=NULL, *tail, *p; printf(“input numbers end of 0:n”); scanf(“ %d”,/*建立其余结点*/ scanf(“ %d”,/*后移语句*/ ,删除链表的一个结点 删除链表结点的操作是指删除某个其数据域值满足给定条件的结点。为了将由于删去一个结点而拆成两段的链连接在一起，删除链表中一个结点的操作需要用两个临时指针。一个是用于检查当前结点的遍历指针，设为 p;另一个是用于记住遍历过程中 p

27、 的上一个结点的地址的指针，设为 last。 删除链表结点的步骤如下： 假定要删除的结点是数据域 data 值为 x 的一个结点。 1、遍历链表，查找被删除结点的位置 从链头开始，如果 p-data 不等于 x 而且遍历指针未到达链尾，则继续查找；如果 p-data 等于 x，则 p 就是指向被删除结点的指针。实现该算法的语句如下： p=head; while(p-data!=x ,2、从链上删去由 p 指向的结点 只需将被删结点的指针域（last-next 或 head）改为指向被删结点的下一个结点的指针（p-next），如果被删结点是链头，则修改头指针：head=p-next；否则，修改被

28、删结点的上一结点的指针域：last-next=p-next。 3、释放被删结点占用的存储空间：free(p)。 后两步的代码如下： if(p-data=x) if(p=head) head=p-next; else last-next=p-next; free(p); ,在链表中插入一个结点 建立链表时，新结点始终添加（插入）到链表中最后一个结点的后面，而在链表中插入一个结点的操作，是在链中满足一定条件的位置（称为插入点）添加一个新结点。 插入点是根据新结点和链中结点在某个数据域上所需满足的关系，通过遍历链表查找得到的。插入点可能位于链头、链尾或链中某两个元素之间，在链头和链尾插入时，将新结点

29、连接到链中的操作与建立链表时相同。连接到链中某两个元素之间时需要连个遍历指针，一个指向当前结点，设为 current，另一个指向上一结点，设为 last，插入点则位于 current 和 last 所指结点之间。设新建结点的指针为 new，则将新建结点连接到链中间的语句为： last-next = new; new-next = current;,例 若在升序链表中插入一个值为 x 的结点，则插入点应满足的条件是 xdata（在链头或中间插入） 或current-next = NULL（在链尾插入） 代码片段为： struct intnode *new,*last,*current; /*创建

30、一个结点*/ new =(struct intnode *)malloc(sizeof(struct intnode); new-data = x; /*查找插入点*/ current = head;/*从链头开始*/ while( xcurrent-data /*后移语句*/ ,/*连入链表*/ if(xdata)/*插入点不在链尾之后*/ if(current = head)/*在第一个结点之前插入*/ new-next = head; *head = new; else/*在中间插入*/ last-next = new; new-next = current; else/*插入点在链尾之

31、后*/ new-next = NULL; current-next = new; ,8.8 联合 构造数据类型,也叫共用体 用途：使几个不同类型的变量共占一段内存(相互覆盖) 联合类型定义 定义形式：,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 f; ; union data a,b,c,*p,d3;,

32、形式三: union int i; char ch; float f; a,b,c;,联合变量的定义,联合变量定义分配内存, 长度=最长成员所占字节数,联合变量任何时刻 只有一个成员存在,联合变量引用 引用方式：,例 a.i=1; a.ch=a; a.f=1.5; printf(“%d”,a.i); (编译通过，运行结果不对),引用规则 不能引用联合变量，只能引用其成员,联合变量中起作用的成员是最后一次存放的成员,例 union int i; char ch; float f; a; a=1; (),不能在定义联合变量时初始化,例 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,main() union int_char int i; char ch2; x; x.i=24897; pri