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

第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 链表的基本操作

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

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

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

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

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;

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

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

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;

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

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

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

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"};

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

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

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"}};

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

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

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

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

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

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

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); }

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); }

9.4.2结构体指针作函数的参数 例9-8用结构体指针作函数的参数，改写例9-7的程序。 #include "stdio.h" #define N 5 /* 全班学生数 */ 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; }}

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

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

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

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

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

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

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

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;

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

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

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链表 ：

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); }

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

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

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

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

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