结构类型数据描述.ppt

《结构类型数据描述.ppt》由会员分享，可在线阅读，更多相关《结构类型数据描述.ppt（45页珍藏版）》请在三一办公上搜索。

1、第11章 结构类型数据描述,第11章 结构类型数据描述,这种多项组合又有内在联系的的数据称为结构体(structure)。它是可以由用户自己定义的。,11.1 结构体,在实际应用中，有时需要将一些有相互联系而类型不同的数据组合成一个有机的整体，以便于引用。如学生学籍档案中的学号、姓名、性别、年龄、成绩、地址等数据，对每个学生来说，除了其各项的值不同外，但表示形式是一样的。,1.概述,2.结构体类型变量的定义,两者缺一不可,1)结构体类型的定义形式,struct 结构体名 分量表；,其中“分量表”中的分量也应进行类型说明，,例如：struct student int num;char name2

2、0;char sex;int age;float score;char addr30;,即:,类型标识符 分量名;,分量描述,由用户定义的“结构体类型”，可以同标准类型一样作为定义变量的类型。相当于PASCAL语言中的记录(record)。,2)定义结构体类型变量的方法,先定义结构体类型再定义变量,定义了结构体类型 struct student 后，可以用它定义变量。,注：不能写成 struct st1,st2;必须同时指定结构体名。,为了方便起见，可以在程序开头定义符号常量进行简化。如：,如：,struct student st1,st2;,则在程序中可以直接写成:STUDENT int n

3、um;char name20;char sex;int age;float score;char addr30;,#define STUDENT struct student,STUDENT st1,st2;,在定义类型的同时定义变量,如：struct student int num;char name20;char sex;int age;float score;char addr30;st1,st2;,struct 结构体名 分量表；变量表；,则一般定义形式为：,直接定义结构类型变量,定义形式为：struct 分量表；变量表；,在 struct 后不出现结构体名，因此也不能再以此定义相同的

4、结构体变量。,3关于结构体类型的几点说明,类型与变量是两个不同的概念。一般先定义结构体类 型，再定义变量为该类型。变量可以赋值、存取或运 算，而类型没有这些操作。在编译时，对变量分配空 间，对类型来说不存在分配空间。,对结构体中的分量可以单独使用。,分量也可以是一个结构体变量。如 student 中要增加 birthday，则可按如下方式进行定义：,struct date int month;int day;int year;,struct student struct date birthday;st1,st2;,先定义一个日期结构,该分量也是一个结构体,分量名可以与程序中的变量名相同，两者

5、之间不会产生混淆。,4.结构体类型变量的引用,引用结构体变量应遵守如下规则：,1)结构体变量中分量的引用方式,结构体变量名 分量名 二级分量名,其中：“”为分量运算符,在所有的运算符中优先级最高。,2)结构体变量的分量本身又属于结构体类型时只能对最 低级分量进行操作。,如：,st1.num;st1.name;st1.birthday.day;,写成 st1.birthday 并不会访问st1中的birthday，只会引起警告错误。,3)不能将一个结构体变量直接进行输入输出，只能对结 构体变量的各分量进行输入输出。,如：,scanf(“%d,%s,%c,%d,%f,%s”,错误,printf(“

6、%d,%s,%c,%d,%f,%s”,st1);,错误,printf(“%s,%d”,st1.name,);,正确,4)分量和结构体变量的地址均可以被引用,如：,scanf(“%d”,输入st1.num的值,printf(“%x”,以十六进制输出st1的首地址,5.结构体变量的初始化,1)外部存储类的结构体变量初始化,例11.1struct studentlong int num;char name20;char sex;char addr30;a=89031,“Li Lin”,M,“123 Beijing Road”;main()printf(“%ld,%s,%c,%sn”,a.num,a.

7、name,a.sex,a.addr);,输出结果：89031,Li Lin,M,123 Beijing Road,2)静态存储类的结构体变量初始化,main()struct student long int num;char name20;char sex;char addr30;a=89031,“Li Lin”,M,“123 Beijing Road”;printf(“%ld,%s,%c,%sn”,a.num,a.name,a.sex,a.addr);,可以将定义部分放在main函数中,6.结构体数组,结构体数组与普通数组的不同之处在于每个数组元素都是一个结构体类型的数据，且这些数据又分别包

8、括各个分量。结构体数组的定义、初始化等操作和内存中的存放方式与普通数组相类似。,7 指向结构体类型数据的指针,同普通变量一样，也可以定义一个指针变量指向一个结构体变量，则此时该指针变量的值是结构体变量的起始地址。指针变量也可以用来指向结构体数组中的元素，同样也可以用指向结构体的指针作函数参数。,例11.11 用指向结构体的指针作函数参数#include“string.h”main()struct student long int num;char name20;char sex;float score;struct student stu;struct student*p;p=,注意:,(*p

9、)表示 p 指向的结构体变量，不得省去括号。而*p.num 等价于*(p.num)。,称为指向运算符。(*p).num可写成 pnum，使之直观，余类推。“”,结构体变量 分量名、(*p)分量名、p分量名，三 者是等价的。,pn 得到 p 指向的结构体变量中的分量 n 的值。,pn+得到 p 指向的结构体变量中的分量 n 的值，用完该值后加1。,+pn 得到 p 指向的结构体变量中的分量 n 的值，并在用该值前先加1。,8 动态数据结构,静态数据结构(例如数组)占据内存空间的位置和大小是在它们被说明的同时由系统分配的,在程序运行期间是不变的,因此可以有效地访问它们的任何一个元素。但要删除和插入

10、一个元素则比较困难,往往要引起大量的数据移动。而且数据量的扩充更受到它们所占用的有限内存空间的限制。C 中的动态数据结构有效地解决了这一问题,动态数据结构中最基本的形式是链表和二叉树,它们在数据处理中起着十分重要的作用。,动态数据结构中的每个组成数据在逻辑上是连续排列的,但在物理上即在内存中存储时并不占用连续的内存空间,它们可以根据需要随机地增加或减少其元素,相应地占用或释放内存空间。,1.动态存储分配,C语言实现动态存储分配的函数：,malloc(size),在内存的动态存储区中分配一个结点长度为size的连续存储空间，并返回一个指向其起始地址的指针，若分配不成功，则返回值为0。size为整

11、型。,calloc(n,size),在内存的动态存储区中分配 n个结点长度为size的连续存储空间，并返回一个指向其起始地址的指针，若分配不成功，则返回值为0。n、size为整型。,free(ptr),释放由指针ptr所指向的存储空间。ptr是最近一次调用malloc 或calloc函数或链表指针返回的值。ptr 为字符型指针。,2.链表,1)链表概念,单向链表是按照输入数据的顺序建立的。它有一个“头指针”(图中为 head)，指向第一个元素；每一个元素称为“结点”，每个结点包括两个域：数据域和指向下一个结点的指针域；最后一个元素的指针域为“NULL”(“空地址”)，表示链表的结束，称为“表尾

12、”。,链表是一种常见的动态地进行存储分配的数据结构。链表有“单向链表”、“双向链表”、“循环链表”、“双向循环链表”之分。下图是一个“单向链表”的示例。,2)建立链表,例11.12 链表的建立和遍历(队列),#define NULL 0#define LEN sizeof(struct node)struct node int data;struct node*next;main()struct node*head,*rear,*p;int n=0;p=(struct node*)malloc(LEN);pdata=n+1;head=rear=p;,for(n=1;ndata=n+1;rear

13、next=p;rear=p;rearnext=NULL;p=head;while(p!=NULL)printf(“%3d”,pdata);p=pnext;,1,2,3,4,5,6,7,8,9,10,0,例11.13 链表的建立和遍历(栈),#define NULL 0#define LEN sizeof(struct node)struct node int data;struct node*next;main()struct node*base,*p;int n;base=NULL;for(n=0;n10;n+)p=(struct node*)malloc(LEN);,pdata=n+1;p

14、next=base;base=p;p=base;while(p!=NULL)printf(“%3d”,pdata);p=pnext;,输出结果：10 9 8 7 6 5 4 3 2 1,3)删除链表元素,例11.14 删除链表中指定的结点。,struct node*delete(head,data)struct node*head;int data;struct node*p1,*p2;if(head!=NULL)p1=head;while(p1data!=data,4)链表的插入操作,例11.15 在链表中插入一个新结点。,struct node*insert(head,new)struct

15、 node*head,*new;struct node*p,*p1,*p2;p=new;p1=head;if(head=NULL)head=p;pnext=NULL;else while(p1data!=pdata&p1next!=NULL),p2=p1;p1=p1next;if(p1next=NULL)p1next=p;pnext=NULL;else p2next=p;pnext=p1;n=n 1;,11.2 共用体,1.共用体的概念,二个以上不同类型的变量采用“覆盖技术”占用同一段内存单元的结构称为共用体。,共用体类型变量的定义形式如下：,union 共用体名 分量表;变量表；,例如：,u

16、nion data int i;char ch;float f;a,b,c;,union data int i;char ch;float f;union data a,b,c;,union int i;char ch;float f;a,b,c;,说明：虽然“共用体”与“结构体”的定义形式相似，但是：,一个结构体变量所需的存储容量为每个分量所需存储容 量之和，而一个共用体变量所需的存储容量为各个分量 中占用存储容量最多的分量所需的存储容量。,一个结构体变量的各个分量在任何时刻都同时存在，且 可同时引用。而一个共用体变量的各个分量在同一时刻 只存在其中一个，也只能引用其中的一个分量。即起作 用

17、的只是最后一次存放的分量，在存入一个新的分量后,原有分量的值被覆盖而失去作用。,一个结构体变量的各个分量的地址各不相同，分别拥有 各自的存储空间。而一个共用体变量的各个分量的地址 相同，共同拥有同一存储空间。,共用体变量可作为参数传递给函数，也可以作函数的返 回值。同样，可以使用地址传送方式将共用体变量的地 址作为参数或返回值在函数间传递。,共用体类型可以出现在结构体类型定义中，也可以定 义共用体类型数组，数组也可以作为共用体的分量。同样，结构体类型也可以出现在共用体类型定义中。,不能在定义共用体变量时对其初始化，也不能对共用 体变量名赋值，更不能企图引用共用体变量名去得到 分量的值。,2.共

18、用体变量的引用,不能引用共用体变量，只能采用分量运算符“”引用共用体变量的分量。与引用结构体变量的方法是一致的。,通常，在定义嵌套有共用体变量的结构体变量时，在其中附加一个类型标志，以方便对共用体分量的操作。,如：,struct union int i;char ch;float f;double d;data;int type;a;,switch(a.type)case 0:/*int*/printf(“%dn”,a.data.i);break;case 1:/*char*/printf(“%dn”,a.data.ch);break;case 2:/*float*/printf(“%dn”,

19、a.data.f);break;case 3:/*double*/printf(“%dn”,a.data.d);break;,11.3 枚举类型,所谓“枚举”是指变量的取值只限于所列举出来的值的范围内。,枚举类型的定义以enum开头。,如：,enum weekdaysun,mon,tue,wed,thu,fri,sat;,enum weekday workday,week_end;,enum weekdaysun,mon,tue,wed,thu,fri,satworkday;,说明：,中的枚举元素是常量而不是变量，也不代表什么实 际的含义。,枚举型变量 workday,week_end 的取值

20、只限于 中 列举的元素范围内。,中枚举元素的值按其排列顺序为0、1、2、，可 用于输出。,枚举值可按其定义时的顺序号用作判断比较。,不得直接将一个整数赋给一个枚举变量。如：Workday=2;是不对的，因为它们不属于同一数据类型。,但可以进行强制类型转换赋值。如：workday=(enum weekday)2;,甚至可以是表达式，如：workday=(enum weekday)(5-3);,可用如下定义改变枚举元素中的序号值：enum weekday sun,mon,tue,wed,thu=7,fri,sat;则枚举元素的序号值依次为：0、1、2、3、7、8、9。,例11.2 口袋中有若干个红

21、、黄、蓝、白、黑五种颜色 的球，试编程求出每次从口袋中取出三个不同 颜色的球的可能取法，并输出每种组合的三种 颜色。,main()enum color red,yellow,blue,white,black;enum color i,j,k,pri;int n,loop;n=0;for(i=red;i=black;i+)for(j=red;j=black;j+)if(i!=j)for(k=red;k=black;k+)if(k!=i),default:break;switch(pri)case red:printf(“%10s”,“red”);break;case yellow:printf(

22、“%10s”,“yellow”);break;case blue:printf(“%10s”,“blue”);break;case white:printf(“%10s”,“white”);break;case black:printf(“%10s”,“black”);break;default:break;printf(“n”);printf(“ntotal:%5dn”,n);,使用关键字typedef说明一个新的类型名，往往可以在程序中简化变量的类型定义。,例如：typedef struct student int num;REC;REC x,y,*p;,语句：p=(struct stud

23、ent*)malloc(sizeof(struct student);可以写成：p=(REC*)malloc(sizeof(REC),11.4 用 typedef 定义类型名,相当于struct student x,y,*p;,说明：用 typedef 不是也不能建立新的数据类型，也不能 用来定义变量，只是以一个新的类型名(通常用大写 字母表示)代替已存在的类型名，以此简化程序中变 量的类型定义。,使用typedef 有利于程序的通用性和可移植性。例如：程序中有：int a,b,c;要修改为：long a,b,c;,则可用 typedef 定义：typedef int INTEGER;,在程序

24、中用INTEGER定义变量，当修改程序时再用 typedef 定义即可：typedef long INTEGER;,11.5 位段结构,1.位运算,C 既具有高级语言的特点，又具有低级语言的功能,位运算能力就是其特色之一。所谓位运算就是指进行二进制位的运算。,C提供的位运算符有：运算符 含义&按位与 按位或 按位异或 取反 右移,说明：位运算符中除“”外，其余均为二目运算符，即要求 两侧各有一个运算量。,运算量只能是整型或字符型的数据,不能为实型数据。,1)“按位与”运算符&,参加运算的两个运算量之对应位都为1，则该位的结果为1，否则为0。,例：3&5=13的补码：000000115的补码：0

25、0000101,&00000001,即：0&0=0 0&1=0 1&0=0 1&1=1,&运算符的用途：,清零 如果想将一个单元清零(全部二进位为)，则只要找一个数的补码的对应位0与被清零数的对应位1刚好对应，然后使两者进行&运算。,如：00101011&10010100,00000000,取一个数中的某些指定位如：b:0000000011111111(377)8,&0000000010101100 得到 a 的低 8 位,保留一个数的某一位如：01010100(84)10&00111011(59)10,00010000(16)10,2)“按位或”运算符,参加运算的两个运算量之对应位只要有一位

26、为1，则该位的结果为1。即：0 0=0 0 1=1 1 0=1 1 1=1,如：00110000(060)8 00001111(017)8,00111111(077)8,即一个数与017进行按位或运算，就可将该数的低4位全置为1;与0377进行按位或运算，就可将该数的低8位全置为1。,3)“异或”运算符,参加运算的两个运算量的对应位相同，则该位的结果为0。否则为1。即：00=0 01=1 10=1 11=0,如：00111001(57)10、(071)8 00101010(42)10、(052)8,00010011(19)10、(023)8,运算符的用途:,使指定的位翻转如：01111010

27、00001111 对应原数的低4位均置为1,01110101 原数的低4位被翻转,若 a=3,b=4。有 a=ab;b=ba;a=ab;则 a,b 的值多少？,4)“取反”运算符,运算是对一个二进制数按位取反，即将0变为1，1变为0。,8位全1用377；16位全1用177777；32位全1用37777777777。,5)左移运算符,用来将一个数的各二进制位全部左移若干位，并在右边补若干个0。高位左移后溢出，舍弃不起作用。,运算的最大用途是做乘法运算。将乘以 2n 的幂运算处理为左移 n 位。,如:,6)右移运算符,用来将一个数的各二进制位全部右移若干位，移到右边的低位被舍弃，对无符号数，高位补

28、0。,如：a 为00001111，则 a2为00000011 11,右移一位相当于除以2，右移 n 位相当于除以2 n。,注意：在右移时，需要注意符号位问题。若为无符号数,右移时左边高位移入0。若为有符号数,如果原来符号位为0(正数)，则左边移入0；如果原来符号位为1，左边移入0的称为“逻辑右移”，移入1的称为“算术右移”。大多数C语言均采用算术移位。,8逻辑右移,得(045766)8算术右移,得(145766)8,如：,2.位运算举例,例11.23 取一个整数 a 从右端开始的 4 7 位。,main()unsigned a,b,c,d;scanf(“%o”,b=a(m-n+1),c=(0n

29、),运行情况：331 33113,例11.24 循环移位。将 a 右循环移 3 位。,main()unsigned a,b,c;int n;scanf(“a=%o,n=%d”,运行情况：a=57653,n=3,b：0110000000000000,c：000,5765335765,此题为无符号数逻辑右移，若为有符号数则最高位移入 1,3.位段,有时存储一个信息不必用一个或多个字节，可以在一个字节中存放几个信息。例如,“真”或“假”用1或 0 表示，只需要 1 位就够了。,1)在一个字节中存放几个数据,图中：a、b、c、d分别占2位、6位、4位、4位。假定c原来的值为0，现要变为12，则：,将数

30、 12 左移 4 位，使 1100 成为右边起第 47 位。,将 data 与 124 按位或即可(设 data 中第 47 位 原来为0)。,若 c 的原值不为0，则应先使 c 为0。方法如下：,data=data&0177417,0177417 称为“屏蔽字”,当然也可以用：data=data&(154)来实现，而不必计算屏蔽码。,从而可以得到:,data=data&(154)(n&15)4,n 为赋给 c 的值,2)位段,位段是以位为单位定义长度的结构体类型中的成员。,struct packed_data unsigned a:2;unsigned b:6;unsigned c:4;un

31、signed d:4;int i;data;,几点说明：,位段也是一种结构体分量，其引用方法与结构体相同。,如:,data.a=2;data.b=3;,必须注意位段分量允许的最大取值范围。,长度为 的位段可以使其后的位段从下一个存储单元 开始存放。,如:,unsigned a:1;unsigned b:2;unsigned:0;unsigned c:3;,在同一存储单元,在另一存储单元,一个位段不得跨 2 个存储单元。如:,unsigned a:6;unsigned b:6;unsigned c:5;,unsigned a:6;unsigned b:6;unsigned:0;unsigned c:5;,一个位段的长度不得大于一个存储单元的长度，也不能定 义位段数组。,位段可以用整型格式符输出。如：printf(“%d,%d,%d”,data.a,data.b,data.c);也可以用%u,%o,%x 等格式符输出。,位段可以在数值表达式中引用，它会被系统自动地转换成 整型数。如：data.a+data.b 是合法的。,可以定义无名位段。如:unsigned a:1;unsigned:2;unsigned b:3;,