《结构类型数据描述》由会员分享，可在线阅读，更多相关《结构类型数据描述（45页珍藏版）》请在金锄头文库上搜索。
1、第11章 结构类型数据描述,第11章 结构类型数据描述,这种多项组合又有内在联系的的数据称为结构体 (structure)。它是可以由用户自己定义的。,11.1 结构体,在实际应用中，有时需要将一些有相互联系而类型 不同的数据组合成一个有机的整体，以便于引用。如学 生学籍档案中的学号、姓名、性别、年龄、成绩、地址 等数据，对每个学生来说，除了其各项的值不同外，但 表示形式是一样的。,1. 概述,2. 结构体类型变量的定义,两者缺一不可,1) 结构体类型的定义形式,struct 结构体名 分量表 ；,其中“分量表”中的分量也应进行类型说明，,例如： struct student int num;
2、 char name20; char sex; int age; float score; char addr30; ;,即:,类型标识符 分量名;,分量描述,由用户定义的“结构体类型”，可以同标准类型一样作为定义变量的类型。相当于PASCAL语言中的记录(record)。,2) 定义结构体类型变量的方法, 先定义结构体类型再定义变量,定义了结构体类型 struct student 后，可以用它 定义变量。,注：不能写成 struct st1,st2; 必须同时指定结构体名。,为了方便起见，可以在程序开头定义符号常量进行 简化。如：,如：,struct student st1, st2;,则在
3、程序中可以直接写成: 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 结构体名 分量表； 变量表；,则一般定义形式为：, 直接定义结构类型变量,定义形式为： struc
4、t 分量表； 变量表；,在 struct 后不出现结构体名，因此也不能再以此定 义相同的结构体变量。,3关于结构体类型的几点说明, 类型与变量是两个不同的概念。一般先定义结构体类 型，再定义变量为该类型。变量可以赋值、存取或运 算，而类型没有这些操作。在编译时，对变量分配空 间，对类型来说不存在分配空间。, 对结构体中的分量可以单独使用。, 分量也可以是一个结构体变量。如 student 中要增加 birthday，则可按如下方式进行定义：,struct date int month; int day; int year; ;,struct student struct date birthd
5、ay; st1, st2;,先定义一个日期结构,该分量也是一个结构体,分量名可以与程序中的变量名相同，两者之间不会 产生混淆。,4. 结构体类型变量的引用,引用结构体变量应遵守如下规则：,1) 结构体变量中分量的引用方式,结构体变量名 分量名 二级分量名 ,其中：“”为分量运算符, 在所有的运算符中优先级最高。,2) 结构体变量的分量本身又属于结构体类型时只能对最 低级分量进行操作。,如：,st1.num; st1.name; st1.birthday.day;,写成 st1.birthday 并不会访问st1中的birthday，只会 引起警告错误。,3) 不能将一个结构体变量直接进行输入输
6、出，只能对结 构体变量的各分量进行输入输出。,如：,scanf(“%d,%s,%c,%d,%f,%s”,错误,printf(“%d,%s,%c,%d,%f,%s”,st1);,错误,printf(“%s,%d”,st1.name,st1.birthday.day);,正确,4) 分量和结构体变量的地址均可以被引用,如：,scanf(“%d”,输入st1.num的值,printf(“%x”,以十六进制输出st1的首地址,5. 结构体变量的初始化,1) 外部存储类的结构体变量初始化,例11.1 struct student long int num; char name20; char sex;
7、char addr30; a=89031,“Li Lin”,M,“123 Beijing Road”; main( ) printf(“%ld,%s,%c,%sn”,a.num,a.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,%s
8、n”,a.num,a.name,a.sex,a.addr); ,可以将定义部分放在main函数中,6. 结构体数组,结构体数组与普通数组的不同之处在于每个数组元 素都是一个结构体类型的数据，且这些数据又分别包括 各个分量。结构体数组的定义、初始化等操作和内存中 的存放方式与普通数组相类似。,7 指向结构体类型数据的指针,同普通变量一样，也可以定义一个 指针变量指向一个结构体变量，则此时 该指针变量的值是结构体变量的起始地 址。指针变量也可以用来指向结构体数 组中的元素，同样也可以用指向结构体 的指针作函数参数。,例11.11 用指向结构体的指针作函数参数 #include “string.h”
9、 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 的值
10、， 用完该值后加1。, +pn 得到 p 指向的结构体变量中的分量 n 的值， 并在用该值前先加1。,8 动态数据结构,静态数据结构 (例如数组) 占据内存空间的位置和大 小是在它们被说明的同时由系统分配的, 在程序运行期间 是不变的, 因此可以有效地访问它们的任何一个元素。但 要删除和插入一个元素则比较困难, 往往要引起大量的数 据移动。而且数据量的扩充更受到它们所占用的有限内存 空间的限制。C 中的动态数据结构有效地解决了这一问题,动态数据结构中最基本的形式是链表和二叉树, 它们 在数据处理中起着十分重要的作用。,动态数据结构中的每个组成数据在逻辑上是连续排列的, 但在物理上即在内存中存储
11、时并不占用连续的内存空间, 它们可以根据需要随机地增加或减少其元素, 相应地占用 或释放内存空间。,1. 动态存储分配,C语言实现动态存储分配的函数：, malloc(size),在内存的动态存储区中分配一个结点长度为size的 连续存储空间，并返回一个指向其起始地址的指针，若 分配不成功，则返回值为0。size为整型。, calloc(n, size),在内存的动态存储区中分配 n个结点长度为size的 连续存储空间，并返回一个指向其起始地址的指针，若 分配不成功，则返回值为0。n、size为整型。, free(ptr),释放由指针ptr所指向的存储空间。ptr是最近一次 调用malloc
12、或calloc函数或链表指针返回的值。ptr 为 字符型指针。,2. 链表,1) 链表概念,单向链表是按照输入数据的顺序建立的。它有一 个 “头指针” (图中为 head )，指向第一个元素；每一 个元素称为“结点”，每个结点包括两个域：数据域和 指向下一个结点的指针域；最后一个元素的指针域为 “NULL”(“空地址”)，表示链表的结束，称为“表尾”。,链表是一种常见的动态地进行存储分配的数据结 构。链表有 “单向链表”、“双向链表”、“循环链表”、 “双向循环链表”之分。下图是一个“单向链表”的示例。,2) 建立链表,例11.12 链表的建立和遍历(队列),#define NULL 0 #d
13、efine 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
14、,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(“
15、%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; pne
