《结构体程序设计》PPT课件.ppt

C语言程序设计 第8章 结构体程序设计,第8章 结构体程序设计,8.1 结构体数据概述 8.2 结构体类型和结构体变量 8.3 结构体数组 8.4 结构体指针变量 8.5 使用链表存储数据 8.6 链表的基本操作 8.7 结构体应用举例,8.1 结构体数据概述,结构体数据是由多个数据项组合而成的数据，如表8-1所示的学生信息表，当把每一行视为一个完整数据时，该数据就是一个结构体数据。为了有效地处理这样一类组合数据，C语言提供了“结构体”技术，它可以把多个数据项组合起来，作为一个数据整体进行处理。,8.1 结构体数据概述,8.2 结构体类型和结构体变量,8.2.1 使用结构体变量存储学生信息 8.2.2 定义结构体数据类型 8.2.3 结构体变量的定义及使用,8.2.1使用结构体变量存储学生信息,例8-1 利用结构体变量存储表8-1中第1行的学生信息，并输出其姓名和成绩。,#include struct student /* 定义结构体数据类型 */ int num; char name20; char sex; int score; ; int main() struct student stu=9011,“liujia“,M,87; printf(“Name: %sn“,); printf(“Score: %dn“,stu.score); return 0; ,8.2.2 定义结构体数据类型,定义结构体类型的一般格式 struct 结构体名 成员表 ; 说明： “结构体名”是用户定义的结构体的名字，在以后定义结构体变量时，使用该名字进行类型标识。 “成员表”是对结构体数据中每一个数据项的变量说明，其格式与说明一个变量的一般格式相同： 数据类型名 成员名; “struct”是关键字，“struct 结构体名”是结构体类型标识符，在类型定义和类型使用时“struct”都不能省略。 结构体名称可以省略，此时定义的结构体称为无名结构体。,9.1.2 结构体类型定义,学生组合数据的结构体类型定义： struct student int num; char name20; char sex; int score; ;,8.2.3 结构体变量的定义及使用,1. 定义结构体变量 先定义结构体类型，再定义结构体变量。 一般格式 struct 结构体类型名称 结构体变量名； 如： struct student student1,student2;,8.2.3结构体变量的定义及使用, 在定义结构体类型的同时定义结构体变量。 一般格式 struct 结构体名 成员表 结构体变量1, 结构体变量2，结构体变量n; 例如： struct student int num; char name20; char sex; int score; student1, student2;,8.2.3 结构体变量的定义及使用, 不定义结构体类型名，直接定义结构体类型变量。 一般格式 struct 成员表; 结构体变量1,结构体变量2,结构体变量n; 例如： struct int num; char name20; char sex; int score; student1, student2;,8.2.3 结构体变量的定义及使用,2. 引用结构体成员 引用结构体成员的一般格式 结构体变量名.成员名称 例如： student1.score 例8-2 输入两个学生的信息，然后输出学习成绩高的学生的姓名和成绩信息。若成绩相同时，只输出第1个学生的信息。,#include struct student int num; char name20; char sex; int score; stu1,stu2; int main() printf(“Data1: “); scanf(“%d %s %c %d“, ,8.2.3 结构体变量的定义及使用,3.结构体变量的初始化：定义结构体变量时对其成员赋初值。 初始化的一般形式 struct 结构体名 结构体变量=初始化数据;,例如：,说明： “ ”中的初始化数据用逗号“,”分隔。 初始化数据的个数与结构体成员的个数应相同，它们是按成员的先后顺序一一对应赋值的。 每个初始化数据必须符合与其对应的成员的数据类型。,struct student int num; char name20; char sex; int score; stu=9901,“liujia“,M,87;,8.3 结构体数组,8.3.1 结构体数组的定义及元素引用 8.3.2 结构体数组的初始化 8.3.3 利用结构体数组管理学生信息,8.3.1 结构体数组的定义及元素引用,数组元素是结构体类型的数组，称为结构体数组。 定义方法与其他结构体变量的定义方法相同 。 先定义结构体类型，然后用结构体类型定义数组变量。 例如： struct student information100; 定义结构体类型的同时，定义数组变量。 定义无类型名的结构体数组变量。 例如： struct int year; int month; int day; date110,date210; 引用结构体数组成员的一般格式 结构体数组名下标.成员名 information20.score=91;,例如： struct student int year; int month; int day; date110,date210;,8.3.2结构体数组的初始化,结构体数组的初始化 例如： struct student info3= 9901,“liujia“,M, 87,9902, “wangkai“, M, 89, 9903, “xiaohua“,F,81;,8.3.3 利用结构体数组管理学生信息,例8-3 按照表8-1的数据，输入一个班级的学生信息，并进行以下处理： 把学习成绩在85以上的学生找出来，并输出这部分学生的姓名和成绩。 分别统计男生和女生人数。 分析 定义一个结构体类型，并用它定义一个存储学生信息的结构体数组； 向结构体数组中输入学生数据； 统计，并输出结果。,8.3.3 利用结构体数组管理学生信息,/* program e8-3.c */ #include #define N 5 struct student int num; char name20; char sex; int score; ;,int main() struct student stuN; int i,count_m=0,count_f=0; printf(“Input Data:n“); for(i=0;i85) printf(“ %s,%dn“,,stui.score); if(stui.sex=M|stui.sex=m) count_m+; else count_f+; printf(“Boys=%d,Girls=%dn“,count_m,count_f); return 0; ,8.4 结构体指针变量,指向结构体数据的指针变量，称为结构体指针变量 。与其他类型的指针一样，结构体指针变量既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体指针还可以作函数的参数。,8.4 结构体指针变量,8.4.1 结构体指针变量的定义及使用 8.4.2 结构体指针作函数的参数,8.4.1 结构体指针变量的定义及使用,定义结构体指针变量的一般形式： struct 结构体名 *结构体指针变量名; 例如： struct student *p,*q; struct student stud1,info10; p=,成员引用 std1.num与p-num等价 info1.num与q1-num等价,8.4.1 结构体指针变量的定义及使用,int main() struct student stu,*p; p= ,例8-4 结构体指针用法示例。 /* program e8-4.c */ #include #include struct student int num; char name20; char sex; int score; ;,8.4.1 结构体指针变量的定义及使用,例8-5 指向结构体数组的指针应用示例。 #include #include struct student int num; char name20; char sex; int score; stu3=9913,“xiaoli“,F,81,9914,“zhanghua“,M,82,9915,“wangjun“,F,88; int main() struct student *p; for(p=stu;pnum,p-name,p-sex,p-score); return 0; ,共3组初始化数据,结构体指针变量,int main() void output(struct sudent *,int); output(stu,N); return 0; void output(struct student *p,int n) int i; for(i=0;inum,p-name,p-sex,p-score); return; ,/* program e8-6.c */ #include #include #define N 3 struct student int num; char name20; char sex; int score; stuN=9913,“xiaoli“,F,81,9914, “zhanghua“,M,82,9915,“wangjun “,F,88;,结构体指针,8.4.2 结构体指针作函数的参数,例8-6 结构体指针作函数参数示例。,结构体数组名,8.5 链表概述,8.5.1 使用链表存储学生信息 8.5.2 链表的特点 8.5.3 动态内存管理函数 8.5.4 定义链表结构,8.5.1 链表的概念,链表是结构体最重要的应用，它是一种非固定长度的数据结构，是一种动态存储技术，它能够根据数据的结构特点和数量使用内存，尤其适用于数据个数可变的数据存储。 使用链表存储表中前3个学生数据。, 用calloc()申请一段内存M，并把它分成两部分：一部分存储数据；另一部分存储下一个内存段的地址。 将一个学生数据存储在M的数据区中。 若当前是第一个数据，则将M的首地址保存在指针变量head中；否则将M的首地,保存在上一个内存段中。 重复、的过程，直到所有数据存储完毕，在最后一段内存的地址区存储结束标志。,8.5.2 链表的特点, 链表中的结点具有完全相同的结构，每一个结点存储一个独立的结构体数据； 链表的结点由系统随机分配，它们在内存中的位置可能是相邻的，也可能是不相邻的，结点之间的联系是通过指针域实现的； 为了能准确的定位第一个结点，每个链表要有一个表头指针，从第一个结点开始，沿指针链能遍历链表中的所有结点； 链表中的结点是在需要时用calloc()申请的，当不再需要时，应有free()函数释放所占用的内存段。 一个链表不需要事先说明它要包括的结点数目，在需要存储新的数据时，就可增加结点，需要删除数据时，就减少结点，链表结点是动态变化的。,8.5.3 动态内存管理函数,动态分配内存 按需分配内存，申请获得制。 C语言通过动态内存管理函数，实现动态内存管理。链表每一个结点的建立和删除过程，都需要使用动态内存管理函数。,8.5.3 动态内存管理函数,1malloc()函数 函数原型 void *malloc(unsigned int size); 功能 分配一块长度为size字节的连续空间，并将该空间的首地址作为函数的返回值。如果函数没有成功执行，返回值为空指针（NULL或0）。由于返回的指针的基类型为void，应该通过显式类型转换后才能存入其他基类型的指针变量中，否则会有警告提示。 例如： int *p; p=(int *)malloc(sizeof(int);,8.5.3 动态内存管理函数,2free()函数 函数原型 void free(void *block); 功能 释放以前分配给指针变量block的动态空间，但指针变量block不会自动变成空指针。 3. calloc()函数 函数原型 void *calloc(unsigned n,unsigned size); 功能 以size为单位大小共分配n*size个字节的连续空间，并将该空间的首地址作为函数的返回值。如果函数没有成功执行，返回值为空指针(NULL或0)。 例如：int *p; p=(int *)calloc(10,sizeof(int);,8.5.4 定义链表结构,要定义一个链表结点的结构，须有两项内容： 定义数据存储所对应的各个成员； 定义指向其他结点的指针成员。 例如： 假若要用链表逐个存储一批整数，其结点结构可定义如下： struct node int data; struct node *next; ;,存储具体数据,存储下一个节点的地址,struct node类型的结点形成的链表,头指针,空指针,8.5.4 定义链表结构,struct student int num; char name20; char sex; int score; struct student *next; ;,必须的成员，否则构不成链表,学生链表的结点定义,结点,8.6 链表的基本操作,8.6.1 链表结点的插入 8.6.2 链表结点的删除 8.6.3 链表结点的查找,8.6.1 链表结点的插入,在链表中插入结点，就是把一个新结点连接到链表中。 两种情况： 在空链表中插入一个结点； 在链表的p结点之后插入一个新结点。,8.6.1 链表结点的插入,1在空链表中插入一个结点 空链表就是头指针head为空的链表。 申请一个new结点。 new=(struct node *)calloc(1,sizeof(struct node);, 为p结点填充数据。 将要存储的数据对应赋值给p结点数据域的各个成员。 修改有关指针的指向。 将new的next成员置空，使new结点成为链表的最后一个结点。 将head指向new结点。,8.6.1 链表结点的插入,2在head链表的p结点之后插入一个结点 head链表和要插入结点new如图所示。要将new结点插入在p结点之后，就是将new结点变成结点C的下一个结点，而使new的下一个结点成为结点D。, 使new的指针域存储结点D的首地址。 new-next=p-next; 把new的首地址存储到结点p的指针域中。 p-next=new;,8.6.1 链表结点的插入,insert()函数 功能：在head链表的p结点之后插入值为x的结点,struct student *insert(struct node *head,struct node *p,int x) struct node *new; new=(struct node *)calloc(1,sizeof(struct node); new-data=x; if(head=NULL) head=new; head-next=NULL; else new-next=p-next; p-next=new; return(head); ,8.6.1 链表结点的插入,例8-7 用插入结点的方法建立图示的学生成绩链表，链表head有10个结点，每个结点存储一个学生的学号和学习成绩数据。,程序: e8-7.c,所需函数的功能 creat_node()函数：生成一个链表结点。 creat_list()函数：生成有n个struct s_node型结点的链表，函数的返回值是链表的头指针。 out_list()函数：用于输出head链表的各结点值。,8.6.1 链表结点的插入,#include #define N 10 struct s_node /* 定义结点类型 */ char num4; int score; struct s_node *next; ; int main() struct s_node *create_node(void); struct s_node *create_list(int n); void out_list(struct s_node *head); struct s_node *head=NULL; head=create_list(N); out_list(head); return 0; ,8.6.1 链表结点的插入,/* 生成一个链表结点的函数*/ struct s_node *create_node(void) struct s_node *p; p=(struct s_node *)calloc(1,sizeof(struct s_node); scanf(“%s%d“,p-num, ,8.6.1 链表结点的插入,struct s_node *create_list(int n) struct s_node *new,*p; struct s_node *head; int i; if(n=1) new=create_node(); head=new; p=new; for(i=2;inext=new; p=new; if(n=1) return(head); else return(NULL); ,建立含有n个结点的链表的函数,8.6.1 链表结点的插入,/* 输出head链表中所有结点的函数 */ void out_list(struct s_node *head) struct s_node *p; if(head!=NULL) p=head; while(p!=NULL) printf(“%s %dn“,p-num,p-score); p=p-next; ,8.6.2 链表结点的删除,从链表中删除结点，就是撤销结点在链表中的链接，把结点从链表中孤立出来。 删除结点过程： 把指定的结点从链表中拿下来，通过修改有关结点的指针域实现； 释放该结点使用的内存空间，使用free()函数来实现。,删除p结点时指针变化情况,删除p结点后的head链表,8.6.2 链表结点的删除, 若p结点是链表的第一个结点，则将p指针域的地址保存到head中，使p的后继结点成为head链表的第一个结点，然后转步骤。 修改指针操作： head=head-next;或head=p-next; 若p结点不是链表的第一个结点，则首先从head开始，找到p结点的前一个结点q，然后使q的指针域存储p的后继结点的地址，这样沿链表的指针访问链表中的结点时，p结点将不会被访问到，亦即p结点从链表head中被删除了。 修改指针操作： q-next=p-next; 释放p结点使用的内存空间free(p);,在head链表中删除p结点的delete()函数,删除结点步骤,/* delete()函数 */ struct node *delete(struct node *head,struct node *p) struct node *q; if(p=NULL) return(head); if(p=head) head= head-next; else q=head; while(q-next!=p) q=q-next; q-next=p-next; free(p); return(head); ,8.6.3 链表结点的查找,链表查找是从链表的第一个结点开始，沿着指针链，用查找值与链表结点逐个比较的过程。找到符合要求的结点之后，停止查找过程，返回相应结点的指针，否则返回一个空指针。 在head链表中查找data值为m的结点的过程，其中p为struct node型指针： p=head； 当pNULL时，若p-data=m，则找到要求结点，查找结束，返回结点地址p；否则，执行下一步；当p= NULL时，链表中不存在要找的结点，查找结束，返回空指针NULL； p=p-next,转步骤。,8.6.3 链表结点的查找,查找函数find() struct node *find(struct node *head,int m) struct node *p=head; while(p!=NULL ,8.6.3 链表结点的查找,例8-8 对图示的head链表，删除其值是x的结点。具体要求： 输出被删除结点的值； 当指定值结点不存在时，显示一个提示信息； x的值由键盘输入。,程序e8-8.c,分析 该问题的关键点有两点： 查找data等于x的结点p； 删除p结点。,8.7 结构体应用举例,8.7.1 字符串加密 8.7.2 学生成绩排序 8.7.3 Josephus问题,8.7.1 字符串加密,例8-9 将输入的一个字符串加密后输出，加密表中未出现的源字符原样输出。,1问题分析与算法设计 设计数据结构存储字母加密对照表。 struct table char input; char output; ;, 定义struct table型数组用于存储密码表。 输入一个字符串，在密码表的input成员中查找每一个输入的字符，查找成功后使用对应的output成员加密输出，否则，原样输出源字符。,2实现程序,#include struct table char input; /* 存储输入的源字符 */ char output; /* 存储加密后的字符 */ ; int main( ) char ch; int length,i; struct table encrypt10= a,f,b,g,w,d,f,9,v,*,x,s,m,3, h,k,p,t,u,? ; while(ch=getchar()!=n) for(i=0;encrypti.input!=ch ,8.7.2 学生成绩排序,例8-10 用结构体表示学生的姓名和成绩，编写程序，对一个班级的学生信息按成绩进行降序排序，并输出结果。 问题分析与算法设计 定义结构体数据类型。 struct stu_info char name20; int score; ； 定义struct stu_info类型的结构体数组stu用于存储一个班级的学生数据。 定义学生数据输入函数input()，用于建立结构体数组stu。 定义学生数据输出函数output()，用于输出数组stu。 定义排序函数sort_stu()，用于对stu数组排序，