C语言程序设计 第9章 结构体.

Presentation on theme: "C语言程序设计 第9章 结构体."— Presentation transcript:

1 C语言程序设计 第9章 结构体

2 第9章 结构体 9.1 结构体类型 9.2 结构体变量 9.3 结构体数组 9.4 结构体指针 9.5 链表概述 9.6 链表的基本操作
主要内容 9.1 结构体类型 9.2 结构体变量 9.3 结构体数组 9.4 结构体指针 9.5 链表概述 9.6 链表的基本操作

3 9.1 结构体类型 9.1.1 结构体类型概述 9.1.2 结构体类型定义

4 9.1.1 结构体类型概述 学生信息表与结构体数据 在程序中使用结构体数据的一般过程 ⑴ 针对具体的组合数据，定义专门的结构体数据类型。
⑵ 使用定义好的数据类型，定义要使用的结构体变量。 ⑶ 使用定义的结构体变量存储和表示结构体数据。

5 9.1.2结构体类型定义 定义结构体类型的一般格式 struct 结构体名 { 成员表 }; 说明：
⑴ “结构体名”是用户定义的结构体的名字，在以后定义结构体变量时，使用该名字进行类型标识。 ⑵ “成员表”是对结构体数据中每一个数据项的变量说明，其格式与说明一个变量的一般格式相同，如下： 数据类型名 成员名; ⑶ “struct”是关键字，“struct结构体名”是结构体类型标识符，在类型定义和类型使用时“struct”都不能省略。 ⑷ 结构体名称可以省略，此时定义的结构体称为无名结构体。

6 9.1.2结构体类型定义 如下是对学生组合数据的结构体类型定义： struct student { int num; /* 学号 */
char name[20]; /* 姓名 */ char sex; /* 性别 */ int age; /* 年龄 */ int score; /* 成绩 */ char addr[30]; /* 地址 */ };

7 9.1.2结构体类型定义 当结构体的成员又是结构体时，称为结构体的嵌套。 struct date { int month; int day;
int year; }; struct stud int num; char name[20]; char sex; int age; struct date birthday; char addr[30]; }stud1,stud2;

8 9.2结构体变量 9.2.1 定义结构体变量 9.2.2 引用结构体成员 9.2.3 结构体变量初始化

9 9.2.1 定义结构体变量 ⑴ 先定义结构体类型，再定义结构体变量。 一般格式 struct 结构体类型名称 结构体变量名； 如：
struct student student1,student2;

10 9.2.1 定义结构体变量 ⑵ 在定义结构体类型的同时定义结构体变量。 一般格式如下： struct 结构体名 { 成员表
}结构体变量1, 结构体变量2，┅…，结构体变量n; 例如： struct student 　int num; 　char name[20]; 　char sex; 　int age; 　int score; 　char addr[30]; } student1, student2;

11 9.2.1 定义结构体变量 ⑶ 不定义结构体类型名，直接定义结构体类型变量。 一般格式如下： struct { 成员表;
}结构体变量1,结构体变量2,…,结构体变量n; 例如： 　int num; 　char name[20]; 　char sex; 　int age; 　int score; 　char addr[30]; }student1, student2;

12 9.2.2引用结构体成员 引用结构体成员的一般格式 结构体变量名.成员名称 如： student1.age
“.”是结构体成员运算符，“.”操作的优先级在Ｃ语言中是最高的，其结合性为从左到右。

13 9.2.2引用结构体成员 例9-1 输入一个学生的一组数据，然后输出其姓名、年龄和地址。 程序9-1 说明：
⑴ 对结构体变量进行输入输出时，只能以成员引用的方式进行，不能对结构体变量进行整体的输入输出。 ⑵ 当成员又是一个结构体类型时，若要引用它的成员，要从高到低逐级引用。如： stud1.birthday.month ⑶ 与其他变量一样，结构体变量成员可以进行各种运算。

14 9.2.3结构体变量初始化 例如： struct student { int num; char name[20]; char sex;
结构体变量的初始化，是在定义结构体变量的同时，对其成员赋初值。 结构体变量初始化的一般形式 struct 结构体名 结构体变量={初始化数据}; 说明： ⑴ “{ }”中的初始化数据用逗号“,”分隔。 ⑵ 初始化数据的个数与结构体成员的个数应相同，它们是按成员的先后顺序一一对应赋值的。 ⑶ 每个初始化数据必须符合与其对应的成员的数据类型。 例如： struct student { int num; char name[20]; char sex; int age; int score; char addr[30]; }stu={9901,"liujia",'M',19,87,"shanghai"};

15 9.3结构体数组 9.3.1 结构体数组概述 9.3.2 结构体数组的初始化 9.3.3 结构体数组的应用

16 9.3.1 结构体数组概述 数组元素是结构体类型的数组，称为结构体数组。定义方法与其他结构体变量的定义方法相同 。
⑴ 先定义结构体类型，然后用结构体类型定义数组变量。 如： struct student information[100]; 引用结构体数组成员的一般格式： 结构体数组名[下标].成员名 information[20].score=91; ⑵ 定义结构体类型的同时，定义数组变量。 ⑶ 定义无类型名的结构体数组变量。 例如： struct { int year; int month; int day; }date1[10],date2[10];

17 9.3.2结构体数组的初始化 结构体数组的初始化，就是在定义结构体数组的同时，为结构体数组元素赋初值。 例如：
struct student info[3]={ {9901,"liujia",'M',19,87,"shanghai"}, {9902,"wangkai",'M',18,89,"beijing"}, {9903,"xiaohua",'F',20,81,"qingdao"}};

18 9.3.3 结构体数组的应用 例9-2 按照表9-1的数据情况，输入一个班级的学生信息，并进行如下处理：
⑴ 把学习成绩在85以上的学生找出来，并输出这部分学生如下信息：姓名、成绩、地址。 ⑵ 分别统计出男生和女生人数。 分析： 这个问题可以分成三个步骤处理： ⑴ 定义一个结构体类型，并用它定义一个存储学生信息的结构体数组； ⑵ 向结构体数组中输入学生数据； ⑶ 统计，并输出结果。 程序9-2

19 9.4 结构体指针 指向结构体变量的指针，称为结构体指针。与其他类型的指针一样，结构体指针既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体指针还可以作函数的参数。

20 9.4.1结构体指针变量的定义及使用 定义结构体指针变量的一般形式： struct 结构体名 *结构体指针变量名; 例如：
struct student *p,*q; struct student stud1,info[10]; p=&stud1; / * p指向结构体变量stud1 */ q=info; /* q指向结构体数组变量info */

21 9.4 结构体指针 指向结构体变量的指针，称为结构体指针。与其他类型的指针一样，结构体指针既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体指针还可以作函数的参数。

22 9.4.1结构体指针变量的定义及使用 定义结构体指针变量的一般形式： struct 结构体名 *结构体指针变量名; 例如：
struct student *p,*q; struct student stud1,info[10]; p=&stud1; / * p指向结构体变量stud1 */ q=info; /* q指向结构体数组变量info */

23 9.4.1结构体指针变量的定义及使用 对指向结构体数组的指针，当指针进行加1或减1运算时，其结果就是将指针指向上一个或者下一个结构体数组元素。

24 9.4.1结构体指针变量的定义及使用 例9-4 结构体指针用法示例。 #include "stdio.h"
#include "string.h" struct stud { char *number; char name[20]; int score; }; main() struct stud student,*p; p=&student; p->number="991001"; strcpy(p->name,"changjiang"); student.score=91; printf("\n"); printf("student No.%s\nname:%s\nscore:%d\n",p->number,p->name,p->score); }

25 9.4.1结构体指针变量的定义及使用 例9-5指向结构体数组指针的应用示例。 #include "stdio.h"
struct stud { char *number; char name[20]; int score; }stu[3]={"990103","xiaohua",81,"990104","zhangli",82,"990105","wangfeng",88}; main() { struct stud *p; printf("\nstudent No. name score\n"); for(p=stu;p<stu+3;p++) printf("%-15s%-20s%4d\n",p->number,p->name,p->score); }

26 9.4.2结构体指针作函数的参数 例9-8用结构体指针作函数的参数，改写例9-7的程序。 #include "stdio.h"
#define N /* 全班学生数 */ struct stu_info { char num[7]; /* 学生学号 */ int score; }stu[]={"990101",87,"990102",89,"990103",81,"990104",82,"990105",88}; main ( ) void sort_stu(struct stu_info *,int); /* 排序函数声明 */ int i; sort_stu(stu,N); for(i=0;i<N;i++) /* 输出结构体数组元素 */ printf("%-10s%d\n",stu[i].num,stu[i].score); } void sort_stu(struct stu_info *p,int n) { int i,j; struct stu_info temp; /* 定义结构体变量，用于结构体数据的交换 */ for(i=1;i<n;i++) /* 冒泡法排序，降序 */ for (j=0;j<N-i;j++) if(p[j].score<p[j+1].score) { /* 交换两个结构体元素的数据 */ temp=p[j]; p[j]=p[j+1]; p[j+1]=temp; }}

27 9.5链表概述 9.5.1 链表的概念 9.5.2 链表的特点 9.5.3 定义链表结构

28 9.5.1 链表的概念 链表是结构体最重要的应用，它是一种非固定长度的数据结构，是一种动态存储技术，它能够根据数据的结构特点和数量使用内存，尤其适用于数据个数可变的数据存储。 使用链表存储表9-1中前3个学生数据。

29 9.5.2 链表的特点 ⑴ 链表中的结点具有完全相同的结构，每一个结点存储一个独立的结构体数据；
⑵ 链表的结点由系统随机分配，它们在内存中的位置可能是相邻的，也可能是不相邻的，结点之间的联系是通过指针域实现的； ⑶ 为了能准确的定位第一个结点，每个链表要有一个表头指针，从第一个结点开始，沿指针链能遍历链表中的所有结点； ⑷ 链表中的结点是在需要时用calloc()申请的，当不再需要时，应有free()函数释放所占用的内存段。 ⑸ 一个链表不需要事先说明它要包括的结点数目，在需要存储新的数据时，就可增加结点，需要删除数据时，就减少结点，链表结点是动态变化的。

30 9.5.3 定义链表结构 要定义一个链表结点的结构，需要包括两个方面： 定义数据存储所对应的各个成员； 定义指向其他结点的指针成员。 例如：
假若要用链表逐个存储一批整数，其结点结构可定义如下： struct node { int data; struct node *next; /* 指向struct node类型的指针 */ };

31 9.6链表的基本操作 9.6.1 链表结点的插入 9.6.2 链表结点的删除 9.6.3 链表结点的查找 9.6.4 Josephus问题

32 9.6.1 链表结点的插入 在链表中插入结点，就是把一个新结点连接到链表中。 通常有两种情况： 在空链表中插入一个结点；
链表的p结点之后插入一个新结点。

33 9.6.1 链表结点的插入 1．在空链表中插入一个结点 空链表就是头指针head为空的链表。 ⑴ 申请一个new结点。
new=(struct node *)calloc(1,sizeof(struct node)); ⑵ 为p结点填充数据。 将要存储的数据对应赋值给p结点数据域的各个成员。 ⑶ 修改有关指针的指向。 ① 将new的next成员置空，使new结点成为链表的最后一个结点。 ② 将head指向new结点。

34 9.6.1 链表结点的插入 2．在head链表的p结点之后插入一个结点
设head链表和要插入结点new如图所示。要将new结点插入在p结点之后，就是将new结点变成结点C的下一个结点，而使new的下一个结点成为结点D。 ⑴ 使new的指针域存储结点D的首地址。 new->next=p->next; ⑵ 把new的首地址存储到结点p的指针域中。 p->next=new;

35 9.6.1 链表结点的插入 例9-9 用插入结点的方法建立图示的学生成绩链表，链表head有10个结点，每个结点存储一个学生的学号和学习成绩数据。 程序9-9 函数的功能 creat_node()函数：生成一个链表结点。 creat_list()函数：生成有n个struct s_node型结点的链表，函数的返回值是链表的头指针。 out_list()函数：用于输出head链表的各结点值。

36 9.6.2链表结点的删除 从链表中删除结点，就是撤销结点在链表中的链接，把结点从链表中孤立出来。在链表中删除结点一般有两个过程： 把指定的结点从链表中拿下来，它需要通过修改有关结点的指针域来实现； 释放该结点使用的内存空间，它需要使用free()函数来实现。 删除p结点的过程：

37 9.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); 删除结点p后的head链表 ：

38 9.6.3链表结点的查找 在链表中进行查找，就是从链表的第一个结点开始，沿着指针链，用查找值与链表结点逐个比较的过程。找到符合要求的结点之后，停止查找过程，返回相应结点的指针，否则返回一个空指针。 在head链表中查找data值为m的结点的过程，其中p为struct node型指针： ⑴ p=head； ⑵ 当p≠NULL时，若p->data==m，则找到要求结点，查找结束，返回结点地址p；否则，执行下一步⑶；当p== NULL时，链表中不存在要找的结点，查找结束，返回空指针NULL； ⑶ p=p->next； ⑷ 重复⑵、⑶步骤。 查找函数find() ： #include "stdio.h" struct node *find(struct node *head,int m) { struct node *p=head; while(p!=NULL&&p->data!=m) p=p->next; if(p==NULL) return(NULL) else return(p); }

39 9.6.3链表结点的查找 例9-10对图示的head链表，删除其值是x的结点。具体要求如下： ⑴ 输出被删除结点的值；
⑵ 当指定值结点不存在时，显示一个提示信息； ⑶ x的值由键盘输入。 分析： 该问题的关键点有两点： 查找data等于x的结点p； 删除p结点。 程序e9-10

40 9.6.4 Josephus问题 例9-11 Josephus问题
有n个人围成一圈，从1开始顺序编号到n，现在从1号开始顺时针从1数数，数到m者自动出列，然后从下一个人开始重新数数，仍然每次数到m者自动出列。请给出这n个人出列的顺序。 方法：用循环链表 解决Josephus问题

41 9.6.4 Josephus问题 用循环链表实现Josephus问题的基本算法
首先设置p指针，其初值为head。然后开始对p指向的结点数数，每数一个结点后，p指针便沿指针链下移一个位置（p=p->next），指向下一个结点。当p指向的结点数到m时，输出该结点的值并将其从链表中删除（出列），这时使p指向下一个结点，然后从1开始重新数数。当链表中只有一个结点时，数数结束，输出该结点。 只有一个结点的循环链表 程序9-11

42 本章小结 1．结构体是一种新型的数据类型，它与前面使用的数据类型的主要区别有两点：
结构体数据类型不是系统固有的，它需要由用户自定义，在一个程序中可以有多个各不相同的结构体类型； 一个结构体数据类型是多个不同成员的集合，这些成员可以具有不同的类型。 2．“struct”是结构体数据类型的关键字，定义和使用结构体类型时都必须使用该关键字。 3．结构体变量的定义有3种方法：先定义结构体类型，再定义结构体变量；在定义结构体类型的同时定义结构体变量；不定义结构体类型名，直接定义结构体类型变量。 4．引用结构体成员的方法主要有两种：使用结构体变量名引用结构体成员；通过指向结构体变量的指针引用结构体成员。 5．数组元素是结构体类型的数组，称为结构体数组，结构体数组具有数组的一切性质。

43 本章小结 6．指向结构体变量的指针，称为结构体指针，结构体指针既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体指针也可以作函数的参数。使用结构体指针作函数的实参时，实参和形参必须是同一种结构体类型。 7．链表是一种动态的数据存储结构，它的每一个结点都是结构体类型的数据，同一个链表中的所有结点具有相同的数据类型。一个链表结点包括数据域和指针域两部分，数据域存储需要处理的数据，指针域存储下一个结点的位置。链表结点在物理位置上没有相邻性，结点之间的联系通过指针实现。 8．对链表施行的基本操作有插入结点、删除结点、查找结点、结点数据读写等，向链表插入结点前必须先用动态内存分配函数获得存储空间，从链表中删除的结点要进行释放操作。 9．从空链表开始不断地插入结点即可建立一个链表，任何一个链表必须有一个头指针，只有通过头指针才能访问链表结点。当一个链表结点的指针域为空时，表明是链表的最后一个结点，当最后一个结点的指针指向开头结点时，便形成一个循环链表。