结构类型数据描述.ppt

第11章 结构类型数据描述,第11章 结构类型数据描述,这种多项组合又有内在联系的的数据称为结构体 (structure)。它是可以由用户自己定义的。,11.1 结构体,在实际应用中，有时需要将一些有相互联系而类型 不同的数据组合成一个有机的整体，以便于引用。如学 生学籍档案中的学号、姓名、性别、年龄、成绩、地址 等数据，对每个学生来说，除了其各项的值不同外，但 表示形式是一样的。,1. 概述,2. 结构体类型变量的定义,两者缺一不可,1) 结构体类型的定义形式,struct 结构体名 分量表 ；,其中“分量表”中的分量也应进行类型说明，,例如： struct student int num; char name20; char sex; int age; float score; char addr30; ;,即:,类型标识符 分量名;,分量描述,由用户定义的“结构体类型”，可以同标准类型一样作为定义变量的类型。相当于PASCAL语言中的记录(record)。,2) 定义结构体类型变量的方法, 先定义结构体类型再定义变量,定义了结构体类型 struct student 后，可以用它 定义变量。,注：不能写成 struct st1,st2; 必须同时指定结构体名。,为了方便起见，可以在程序开头定义符号常量进行 简化。如：,如：,struct student st1, st2;,则在程序中可以直接写成: STUDENT int num; 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 后不出现结构体名，因此也不能再以此定 义相同的结构体变量。,3关于结构体类型的几点说明, 类型与变量是两个不同的概念。一般先定义结构体类 型，再定义变量为该类型。变量可以赋值、存取或运 算，而类型没有这些操作。在编译时，对变量分配空 间，对类型来说不存在分配空间。, 对结构体中的分量可以单独使用。, 分量也可以是一个结构体变量。如 student 中要增加 birthday，则可按如下方式进行定义：,struct date int month; int day; int year; ;,struct student struct date birthday; st1, st2;,先定义一个日期结构,该分量也是一个结构体,分量名可以与程序中的变量名相同，两者之间不会 产生混淆。,4. 结构体类型变量的引用,引用结构体变量应遵守如下规则：,1) 结构体变量中分量的引用方式,结构体变量名 分量名 二级分量名 ,其中：“”为分量运算符, 在所有的运算符中优先级最高。,2) 结构体变量的分量本身又属于结构体类型时只能对最 低级分量进行操作。,如：,st1.num; ; st1.birthday.day;,写成 st1.birthday 并不会访问st1中的birthday，只会 引起警告错误。,3) 不能将一个结构体变量直接进行输入输出，只能对结 构体变量的各分量进行输入输出。,如：,scanf(“%d,%s,%c,%d,%f,%s”,错误,printf(“%d,%s,%c,%d,%f,%s”,st1);,错误,printf(“%s,%d”,,st1.birthday.day);,正确,4) 分量和结构体变量的地址均可以被引用,如：,scanf(“%d”,输入st1.num的值,printf(“%x”,以十六进制输出st1的首地址,5. 结构体变量的初始化,1) 外部存储类的结构体变量初始化,例11.1 struct student long 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.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.sex,a.addr); ,可以将定义部分放在main函数中,6. 结构体数组,结构体数组与普通数组的不同之处在于每个数组元 素都是一个结构体类型的数据，且这些数据又分别包括 各个分量。结构体数组的定义、初始化等操作和内存中 的存放方式与普通数组相类似。,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) 表示 p 指向的结构体变量，不得省去括号。而 *p.num 等价于 *(p.num)。,称为指向运算符。 (*p).num可写成 pnum，使之直观，余类推。“”, 结构体变量 分量名、(*p) 分量名、p分量名，三 者是等价的。, pn 得到 p 指向的结构体变量中的分量 n 的值。, pn+ 得到 p 指向的结构体变量中的分量 n 的值， 用完该值后加1。, +pn 得到 p 指向的结构体变量中的分量 n 的值， 并在用该值前先加1。,8 动态数据结构,静态数据结构 (例如数组) 占据内存空间的位置和大 小是在它们被说明的同时由系统分配的, 在程序运行期间 是不变的, 因此可以有效地访问它们的任何一个元素。但 要删除和插入一个元素则比较困难, 往往要引起大量的数 据移动。而且数据量的扩充更受到它们所占用的有限内存 空间的限制。C 中的动态数据结构有效地解决了这一问题,动态数据结构中最基本的形式是链表和二叉树, 它们 在数据处理中起着十分重要的作用。,动态数据结构中的每个组成数据在逻辑上是连续排列的, 但在物理上即在内存中存储时并不占用连续的内存空间, 它们可以根据需要随机地增加或减少其元素, 相应地占用 或释放内存空间。,1. 动态存储分配,C语言实现动态存储分配的函数：, malloc(size),在内存的动态存储区中分配一个结点长度为size的 连续存储空间，并返回一个指向其起始地址的指针，若 分配不成功，则返回值为0。size为整型。, calloc(n, size),在内存的动态存储区中分配 n个结点长度为size的 连续存储空间，并返回一个指向其起始地址的指针，若 分配不成功，则返回值为0。n、size为整型。, free(ptr),释放由指针ptr所指向的存储空间。ptr是最近一次 调用malloc 或calloc函数或链表指针返回的值。ptr 为 字符型指针。,2. 链表,1) 链表概念,单向链表是按照输入数据的顺序建立的。它有一 个 “头指针” (图中为 head )，指向第一个元素；每一 个元素称为“结点”，每个结点包括两个域：数据域和 指向下一个结点的指针域；最后一个元素的指针域为 “NULL”(“空地址”)，表示链表的结束，称为“表尾”。,链表是一种常见的动态地进行存储分配的数据结 构。链表有 “单向链表”、“双向链表”、“循环链表”、 “双向循环链表”之分。下图是一个“单向链表”的示例。,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; rearnext=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; pnext = 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 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 共用体名 分量表; 变量表；,例如：,union 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;,说明：虽然“共用体”与“结构体”的定义形式相似，但是：, 一个结构体变量所需的存储容量为每个分量所需存储容 量之和，而一个共用体变量所需的存储容量为各个分量 中占用存储容量最多的分量所需的存储容量。, 一个结构体变量的各个分量在任何时刻都同时存在，且 可同时引用。而一个共用体变量的各个分量在同一时刻 只存在其中一个，也只能引用其中的一个分量。即起作 用的只是最后一次存放的分量，在存入一个新的分量后, 原有分量的值被覆盖而失去作用。, 一个结构体变量的各个分量的地址各不相同，分别拥有 各自的存储空间。而一个共用体变量的各个分量的地址 相同，共同拥有同一存储空间。, 共用体变量可作为参数传递给函数，也可以作函数的返 回值。同样，可以使用地址传送方式将共用体变量的地 址作为参数或返回值在函数间传递。, 共用体类型可以出现在结构体类型定义中，也可以定 义共用体类型数组，数组也可以作为共用体的分量。 同样，结构体类型也可以出现在共用体类型定义中。, 不能在定义共用体变量时对其初始化，也不能对共用 体变量名赋值，更不能企图引用共用体变量名去得到 分量的值。,2. 共用体变量的引用,不能引用共用体变量，只能采用分量运算符 “ ” 引用 共用体变量的分量。与引用结构体变量的方法是一致的。,通常，在定义嵌套有共用体变量的结构体变量时， 在其中附加一个类型标志，以方便对共用体分量的操作。,如：,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”,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 的取值只限于 中 列举的元素范围内。, 中枚举元素的值按其排列顺序为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 口袋中有若干个红、黄、蓝、白、黑五种颜色 的球，试编程求出每次从口袋中取出三个不同 颜色的球的可能取法，并输出每种组合的三种 颜色。,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(“%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 student *)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;,在程序中用INTEGER定义变量，当修改程序时再用 typedef 定义即可： typedef long INTEGER;,11.5 位段结构,1. 位运算,C 既具有高级语言的特点，又具有低级语言的功能, 位运算能力就是其特色之一。所谓位运算就是指进行二 进制位的运算。,C提供的位运算符有： 运算符 含义 & 按位与 按位或 按位异或 取反 右移,说明： 位运算符中除“”外，其余均为二目运算符，即要求 两侧各有一个运算量。, 运算量只能是整型或字符型的数据, 不能为实型数据。,1) “按位与” 运算符 &,参加运算的两个运算量之对应位都为1，则该位的结 果为1，否则为0。,例： 3&5=1 3的补码： 00000011 5的补码： 00000101,& 00000001,即： 0&0=0 0&1=0 1&0=0 1&1=1,& 运算符的用途：, 清零 如果想将一个单元清零(全部二进位为)，则只要找一个数的补码的对应位0与被清零数的对应位1刚好对应，然后使两者进行 & 运算。,如： 00101011 & 10010100,00000000, 取一个数中的某些指定位 如： a: 0010110010101100 b: 0000000011111111 (377)8,& 0000000010101100 得到 a 的低 8 位, 保留一个数的某一位 如： 01010100 (84)10 & 00111011 (59)10,00010000 (16)10,2) “按位或”运算符 ,参加运算的两个运算量之对应位只要有一位为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 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) 右移运算符 ,用来将一个数的各二进制位全部右移若干位，移 到右边的低位被舍弃，对无符号数，高位补0。,如： a 为00001111，则 a2为00000011 11,右移一位相当于除以2 ，右移 n 位相当于除以2 n。,注意：在右移时，需要注意符号位问题。若为无符号数, 右移时左边高位移入0。若为有符号数, 如果原来符号位 为0 (正数)，则左边移入0 ；如果原来符号位为1 ，左边 移入0的称为“逻辑右移”，移入1的称为“算术右移”。大 多数C语言均采用算术移位。,a：1001011111101101 (113755)8 a1：0100101111110110 逻辑右移, 得(045766)8 a1：1100101111110110 算术右移, 得(145766)8,如：,2. 位运算举例,例11.23 取一个整数 a 从右端开始的 4 7 位。,main( ) unsigned a, b, c, d ; scanf(“%o”, ,b=a(m-n+1),c=(0n),运行情况： 331 331 13,例11.24 循环移位。将 a 右循环移 3 位。,main( ) unsigned a,b,c; int n; scanf(“a=%o,n=%d”, ,运行情况： a=57653,n=3 ,b：0110000000000000,c：0000101111110101,0011101111110101,57653 35765,此题为无符号数逻辑右移，若为有符号数则最高位移入 1,3