C语言程序设计 结构ppt课件.pptx

第9章 结构,第9章 结构,本章主要内容1.了解结构数据类型的定义及使用。2. 了解结构数据类型的意义及作用。3. 了解结构变量与函数的关系。4. 掌握链表的作用及操作。5. 了解联合数据类型的定义及使用。6. 了解枚举类型的定义及使用。,第9章 结构,结构体数据类型：一种自定义的数据类型。 由不同数据类型的数据组合而成的数据整体。结构体中所包含的数据元素称之为成员。如：“职员”一种结构体 描述职员的信息有： 编号、姓名、年龄、性别、身份证号码、民族、文化程度、职务、住址、联系电话等。,9.1 结构体数据类型,9.1.1 结构体的定义结构类型的定义形式：struct 结构体名 成员项表列;成员项表列同简单变量的定义形式相同。,例如：对“职员”数据，可以定义如下的结构体类型：struct person long no; /*职员号*/ char name12; /*姓名*/ int age; /*年龄*/ char sex; /*性别*/ long indentityNo; /*身份证号*/ char education12; /*学历*/ char addr40; /*住址*/ long telno; /*电话号码*/;,9.1 结构体数据类型,9.1.2 结构体变量的定义定义了结构体之后，就可以定义结构体变量。结构变量的定义形式。（1）类型标识符 ;例如： struct person stu, worker; （2）在定义一个结构体类型的同时定义结构体类型变量：struct 成员项列表;,（3）直接定义结构体类型的变量： struct 成员项列表; ;,9.1 结构体数据类型,9.1.3 结构体变量的初始化（略）9.1.4 结构体变量成员的引用（1）引用结构体变量中的成员。引用格式：.例如： stu.no、 stu.age、 stu.name0等。成员名不能单独代表变量，不能直接使用结构中的成员名。若结构体类型中含有另一个结构类型，访问该成员时，应采取逐级访问的方法。（2）将结构体变量作为一个整体来使用。结构体变量可以相互赋值。 (条件是这两个变量必须具有相同的结构体类型。),9.1 结构体数据类型,例1：阅读程序example9_1.c，了解结构体成员的使用方法。9.1.5 结构体变量成员的输入/输出只允许对结构变量的成员进行输入输出。不允许将结构体变量作为整体进行输入或输出操作。,9.2 结构体数组,9.2.1 结构体数组的定义结构体数组的定义：（1）先定义结构体，再定义结构体数组。struct ;struct ;（2）在定义结构体的同时，定义结构体数组。struct ;,9.2 结构体数组,（3）直接定义结构体变量而不定义结构体名。struct ;9.2.2 结构体数组成员的初始化和引用（略）,9.3 结构体变量与函数,9.3.1 函数的形参与实参为结构体作用：传值例2：阅读程序example9_2.c，了解结构变量作为函数参数的作用。9.3.2 函数的返回值类型为结构体新的C标准中允许函数的返回值为结构体类型的值。例3：修改例9-2所示的程序，将“输入购书信息” 模块的返回值修改成结构类型。,9.4 联合体数据类型,9.4 联合体数据类型联合体又称为共用体。联合体类型与结构体类型的同异： 相同之处：定义形式与结构体类型的定义形式相同。 不同之处： 关键字不同，共用体的关键字为union。 占用的内存单元不同。特点： 不同类型的数组项在内存中所占用的起始单元是相同的。提示： 注意联合类型变量的使用特点。,9.4 联合体数据类型,比较结构类型变量和联合类型变量占用的内存情况：,结构类型：struct memb float v; int n; char c;stag;,联合类型：union memb float v; int n; char c;utag;,9.4 联合体数据类型,例4：阅读程序example9_4.c，分析和了解联合体变量成员的取值情况。例5：阅读程序example9_5.c，了解联合体类型变量的赋值情况。,9.5 枚举数据类型,枚举数据类型： 用标识符表示的整数常量的集合。枚举类型定义的一般形式： enum 标识符1,标识符2,标识符n; 枚举常量的起始值为0。例如： enum monthsJAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC;标识符的值被依次自动设置为整数011。可以改变标识符的取值，例如： enum monthsJAN1, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC;标识符的值被依次自动设置为整数112。,9.5 枚举数据类型,几点说明：枚举类型定义中的标识符必须是唯一的。可以在枚举类型定义时为每一个枚举常量指定不同的值。也可以对中间的某个枚举常量指定不同的值。例如： enum clolorred, blue, green, yellow=5, black, white;由于只指定了yellow的值，则枚举常量的取值情况为：red=0，blue=1，green=2，yellow=5，black=6，while=7。枚举常量的值不可更改，但可以作为整型数使用。,9.5 枚举数据类型,枚举变量的定义形式： enum 变量名1,变量名2,变量名n;例如： enum month work_day, rest_day;也可以在定义枚举类型的同时定义枚举变量。例如： enum color red, yellow, green light;枚举常量标识符是不能直接输入/输出的，要通过其他方式来输出枚举常量标识符。,9.5 枚举数据类型,例6：阅读程序example9_6.c，了解枚举变量的输出方式。,9.6 链表的概念,基本概念：链表指的是将若干个数据项按一定的规则连接起来的表。链表中的数据项称为结点。链表中每一个结点的数据类型都有一个自引用结构自引用结构就是结构成员中包含一个指针成员，该指针指向与自身同一个类型的结构。例如：struct node int data； struct node * nextPtr;；,9.6 链表的概念,链表是用链节指针连接在一起的结点的线性集合。其结构如图所示：自引用结构成员的变量通常是指针型的。结构成员的引用与成员的类型相关。假如有： struct node int data； struct node * nextPtr;；,定义结构变量：struct node *pt;结构成员的引用：pt-data;pt-nextptr;或：(*pt).data;(*pt).nextptr;,9.6 链表的概念,链表可以组成较为复杂的数据结构。根据数据之间的相互关系，链表又可分为单链表、循环链表、双向链表等。链表的可以建立动态的数据结构，可以将不连续的内存数据连接起来。本章重点：单链表。其他链表参见“数据结构”等教程。,9.6 链表的概念,9.6.1 动态分配内存 动态分配内存空间的系统函数： malloc()和free()函数以及sizeof运算符的配合使用 (注： malloc()和free()函数在头文件stdlib.h或alloc.h)。函数原型及功能如下。1函数原型：void *malloc(unsigned size) 功能：从内存分配一个大小为size个字节的内存空间。若成功，返回新分配内存的首地址；若没有足够的内存分配，则返回NULL。通常函数malice()通常和运算符sizeof一起使用。,9.6 链表的概念,例如： int * p; p=mallce(20*sizeof(int)；*分配20个整型数所需的内存空间*系统分配能存放20个整型数连续空间， p指向该存储空间的首地址。例如：struct student int no; int score; struct student *next;struct student *stu;stu=mallco(sizeof(struct student);通过sizeof计算struct student的字节数，分配sizeof（struct student）个字节数的内存空间， stu指向该存储空间的首地址。,9.6 链表的概念,2函数原型：void free(void*p) 功能：释放由mallco函数所分配的内存块，无返回值。例如：free(stu);作用：将stu所指的内存空间释放。几点注意： 结构类型占用的内存空间不一定是连续的，因此，应该用sizeof运算符来确定结构类型占用内存空间的大小。 使用mallco()函数时，应对其返回值进行检测是否为NULL，以确保程序的正确。 要及时地使用free()函数释放不再需要的内存空间，避免系统资源过早地用光。 不要引用已经释放的内存空间。,9.6 链表的概念,9.6.2 单链表的建立链表：通过自引用结构的指针域，将各节点相互连接。关于链表的基本概念：(1) 链表的第一个结点称头指针或头结点，它指向链表在内存中的首地址，(2)其后的结点是通过结点中的链节指针成员访问的。(3)链表的最后一个结点称为尾节点。尾节点的指针域通常被设置成NULL。(4)链表中的每一个结点是在需要的时候建立的。(5)各结点在内存中的存储地址不一定是连续的，由系统自动分配的，即有可能是连续分配内存空间，也有可能是跳跃式的不连续分配内存空间。,9.6 链表的概念,建立单链表的主要步骤： 定义单链表的数据结构（定义自引用结构）。 建立表头（建立一个空表）。 利用malloc函数向系统申请分配一个结点空间。 将新结点的指针成员的值赋为空（NULL），若是空表，将新结点连接到表头；若非空表，则将新结点连接到表尾。 若有后续结点要接入链表，则转到，否则结束。输出一个单链表的主要步骤： 找出表头结束，结点指针P指向头结点。 若P非空，循环执行下列操作。 输出结点值； P指向下一结点；,9.6 链表的概念,例7：编写程序，创建一个链表，该链表可以存放从键盘输入的任意长度的字符串，以按下回车键作为输入的结束。统计输入的字符个数并将其字符串输出。程序： example9_7.c例8：编写程序，用链表的结构建立一条公交线路的站点信息，从键盘依次输入从起点到终点的各站站名，以单个“#”字符作为输入结束，统计站的数量并输出这些站点。分析：站点信息结构设计如下：struct station char name8; struct station *nextSta;设计函数：struct station *creat_sta(struct station *h)； /* 将键盘输入的站点名依次插入到链表h中 */程序： example9_8.c,9.6 链表的概念,9.6.3 从单链表中删除结点在链表中删去一个结点，不允许破坏原链表的结构。例如，对于这样的自引用结构：struct node int n; struct node *next;假定已建好链表：删除s节点后的链表：,9.6 链表的概念,删除节点方法：修改指针域的值。根据被删节点的位置，修改指针域的方法要分3种不同情况： s结点在表的中间（即不在表头，也不在表尾）：p-next=s-next; s结点位于表头：head=s-next; s结点位于表尾：p-next=NULL;结点删除后，用free( )函数释放被删除结点所占用的内存空间。例如：free(s); /* 释放了节点s所占用的空间。 */,9.6 链表的概念,例9：修改例9-8的程序，再从键盘输入一个要删除的站点名，并将删除后的站点依次输出。分析：在例9-8程序的基础上增加一个删除节点的函数：struct station *del_sta(struct station *h, char *str)；函数功能：在h所指的链表中，删除结点值为str所指字符串的结点。程序： example9_9.c请分析函数： struct station *del_sta(struct station *h,char *str);的算法。思考程序中存在的问题，怎样处理可以使程序更加完善？,9.6 链表的概念,9.6.4 向链表中插入结点插入节点方法：修改指针域的值。根据节点插入的位置，修改指针域的方法要分3种不同情况： s结点插入到表中（即不在表头，也不在表尾）修改指针：s-next=t;p-next=s;,9.6 链表的概念, s结点插入到表头。 图(a)所示为插入前的链表，图(b)所示为插入后的链表。修改指针：s-next=t;head=s;,9.6 链表的概念, s结点插入到表尾。 图(a)所示为插入前的链表，图(b)所示为插入后的链表。修改指针：p-next=s;s-next=NULL;,9.6 链表的概念,例10：修改例9-8的程序，从键盘输入一个要加入的站点名，并将加入后的站点依次输出。分析：可以在例9-8程序的基础上增加一个增加节点的函数：struct station *add_sta(struct station *h,char *stradd, char *strafter);函数功能： 将stradd所指的站点插入到h链表中站点原有的站点strafter的后面。程序：example9_10.c,9.7 程 序 范 例,例11：编写程序，从键盘输入一个矩形的左下角和右上角的坐标，输出该矩形的中心点坐标值，再输入任意一个点的坐标，判断该点是否在矩形内。分析：用xd、yd代表矩形的左下角坐标；用xu、yu代表矩形的右上角坐标；用xm、ym代表矩形的中点坐标；设计函数：int ptin（struct point p,struct rect r），用于判断输入的点p是否在矩形r的内部。程序：example9_11.c,9.7 程 序 范 例,例12：改进例8-25的程序。采用结构，设计一个洗牌和发牌的程序，用H代表红桃，D代表方片，C代表梅花，S代表黑桃，用113代表每一种花色的面值。分析：可用结构类型来表示扑克牌的花色和面值：struct card char *face; /* 扑克牌的面值 */ char *suit; /* 扑克牌的花色 */;设计函数：void shuffle（Card *）完成对扑克牌洗牌。程序：example9_12.c,9.7 程 序 范 例,例13：修改例9-12，用位段结构成员表示一副牌，发牌时显示每张牌的颜色。分析：因为牌的面值只有13种，牌的花色只有4种，牌的颜色只有2种，因此，可用一个位段结构来表示一副牌：struct bitCard unsigned face: 4; unsigned suit: 2; unsigned color: 1;face表示面值；suit表示花色；color表示颜色。程序：example9_13.c,9.7 程 序 范 例,例14：编写程序，求解另1种变化的约瑟夫问题：由n个人围成一圈，对他们从1开始依次编号，现指定从第m个人开始报数，报到第s个数时，该人员出列，然后从下一个人开始报数，仍是报到第s个数时，人员出列，如此重复，直到所有人都出列，输出人员的出列顺序。分析：可采用结构成员记录每个人的序号和邻近的下一个人的序号：struct child int num; int next; ;设计函数void OutQueue（int m,int n,int s,struct child ring）求出队序列。函数OutQueue()的算法如下：（1）用i、j表示结构数组ring的下标值，count作为循环变量；（2）如果m=1（即从第一个人开始报数），则队尾的下标值j=n；否则队尾的下标值j=m1；（3）用二层循环输出出列的人。 第一层用循环变量count控制总的出列人数；第二层用循环变量i寻找下一个出列的间隔数；若第j个人出列，则置ringj.num=0;。程序：example9_14,9.8 本 章 小 结,本章重要内容1. 结构数据类型的定义、使用及作用。2. 自引用结构的意义。3. 链表的建立。4. 链表节点的插入和删除。,