第8章 结构体、共用体和枚举类型 教学目的: 通过本章的学习,要求了解结构型、链表、共用型和枚举型数据的特点,熟练掌握结构型的定义方法,结构型变量、数组、指针变量的定义、初始化和成员的引用方法;掌握简单链表的基本操作原理和应用;掌握共用型和枚举型的定义方法及对应变量的定义与引用;掌握用户自定义类型的定义和使用。学习本章内容可以为今后学习数据结构中的链表创建和使用打下基础。

Slides:



Advertisements
Similar presentations
程序设计导论 ——第15讲 结构与结构数组.
Advertisements

程序设计导论 结构与结构数组.
电子成绩单项目实现.
第10章 结构体与链表 本章要点: 结构体类型与结构体变量的定义 结构体变量的引用与初始化 结构体数组 链表处理 共用体类型和枚举类型
大学实用教程 C语言.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
第11章 结构体与共用体 结构体 共用体 枚举类型 用typedef定义类型 Tc工具. 江南大学控制科学与工程研究中心
第九章 系 统 安 全 性 9.1 结构体 9.2 结构体型数组  9.3 结构体型指针 9.4 内存的动态分配 9.5 共用体
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
第7章 结构体、联合体和枚举类型 本章导读 本章主要知识点 《 C语言程序设计》 (Visual C++ 6.0环境)
C程序设计 第9章 自定义数据类型 主讲教师: 鲁 萍 西安建筑科技大学 理学院.
第九章 结构体 主讲教师 :贾月乐 电话:
第10章 结构体与共用体 概述 结构体 共用体 枚举类型.
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
第9章 结构体.
第 十 章 指 针.
结构体和共用体 2 梁春燕 华电信息管理教研室.
第9章 用户自己建立数据类型 9.1 定义和使用结构体变量 9.2 使用结构体数组 9.3 结构体指针 9.4 用指针处理链表
程序设计专题 第2讲 - 结构 刘新国.
自定义数据类型 潘荣江 山东大学计算机科学与技术学院
程序设计基础.
C语言程序设计 李祥.
走进编程 程序的顺序结构(二).
辅导课程六.
西安交通大学计教中心 ctec.xjtu.edu.cn
第7讲 结构体与共用体 7.1 结构体 7.2 共用体.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第8章 结 构 体.
第11章 结构体和共用体.
第七章 结构体、共同体和枚举类型.
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
C语言复习3----结构体.
第十章 用户自定义数据类型 目录 学生信息管理系统的开发 结构体数据类型的概述 结构体变量的使用 结构体数组
1.3 C语言的语句和关键字 一、C语言的语句 与其它高级语言一样,C语言也是利用函数体中的可执行 语句,向计算机系统发出操作命令。按照语句功能或构成的不 同,可将C语言的语句分为五类。 goto, return.
第十章 结构体与链表 西安工程大学.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
第9章 用户自己建立数据类型 C语言提供了一些系统已定义好的数据类型,如int,float,char,用户可以用它们定义变量。
浙江长征职业技术学院—计算机与信息技术系—相方莉制作
C++大学基础教程 第7章 其它自定义数据类型 北京科技大学 信息基础科学系.
第九章 用户建立的数据类型.
VB与Access数据库的连接.
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
单链表的基本概念.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
C语言程序设计 第一章 数据类型, 运算符与表达式 第二章 顺序程序设计 第三章 选择结构程序设计 第四章 循环控制 第五章 数组.
第 四 讲 线性表(二).
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
C++语言程序设计 C++语言程序设计 第四章 数组及自定义数据类型 C++语言程序设计.
第九节 赋值运算符和赋值表达式.
3.16 枚举算法及其程序实现 ——数组的作用.
本节内容 结构体 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
结构体与共用体 结构体 结构体是一种构造数据类型 用途:把不同类型的数据组合成一个整体 自定义数据类型 结构体类型定义
第十一章 链表.
本节内容 结构体.
本节内容 指针类型的使用 视频提供:昆山爱达人信息技术有限公司.
第15讲 链表 计算机与通信工程学院.
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
C语言程序设计 第9章 结构体.
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
基本知识 数据类型、变量、常量、运算符.
第14讲 结构体和共用体 计算机与通信工程学院.
第八章 结构体和共用体 结构体类型和结构体变量 结构体数组 结构体指针变量 共用体.
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
本节内容 this指针 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
安排座位.
Presentation transcript:

第8章 结构体、共用体和枚举类型 教学目的: 通过本章的学习,要求了解结构型、链表、共用型和枚举型数据的特点,熟练掌握结构型的定义方法,结构型变量、数组、指针变量的定义、初始化和成员的引用方法;掌握简单链表的基本操作原理和应用;掌握共用型和枚举型的定义方法及对应变量的定义与引用;掌握用户自定义类型的定义和使用。学习本章内容可以为今后学习数据结构中的链表创建和使用打下基础。

第8章 结构体、共用体和枚举类型 教学内容 结构型的引入,很好的处理生活总的各种表格或表格中的记录 第8章 结构体、共用体和枚举类型 教学内容 结构型的引入,很好的处理生活总的各种表格或表格中的记录 结构型的定义,结构型变量的定义、赋值、引用及引用链表等方法 共用型的定义,共用型变量的定义、赋值、引用 枚举型的定义,共用型变量的定义、赋值、引用

第8章 结构体、共用体和枚举类型 重点和难点 重点: 难点: (1)结构型、共用型、枚举型数据的特点和定义 第8章 结构体、共用体和枚举类型 重点和难点 重点: (1)结构型、共用型、枚举型数据的特点和定义 (2)结构型变量、数组、指针变量的定义、初始化和成员引用方法 (3)共用型和枚举型变量的定义和引用方法 难点: (1)嵌套的结构型数据的处理 (2)用结构体解决链表问题(建立、插入、删除、输出和查询)。

8.1 结构体类型 结构型是用户自己定义的数据类型

8.1.1 结构体型的实例 前面我们学习过了基本数据类型,例如:short、long、int 、float、double、char等,这些基本数据类型都是系统已经定义好的,用户可以直接使用它们。但现实世界是复杂的,在我们的日常生活中有很多的表格,各表格之间又有关联。因此用户需要自己定义数据类型,用户自己定义的数据类型一旦定义好之后,就可以像使用系统类型一样使用它。例如:对一个新生进行入学登记时,就需要填一张表格,填写的内容包括姓名、性别、学号、年龄、家庭住址、联系电话、总分等多个数据项,其中姓名是字符串型(可以用字符数组来表示),性别是字符型(用m表示男性、用f表示女性),年龄是整型,总分是实型。

如图8-1所示, 这些数据项之间关系紧密,每一个学生通过姓名、性别、学号、年龄、家庭地址、联系电话、总分等属性构成一个整体反映一个学生的基本情况。如果将姓名、性别、学号、年龄、家庭地址、联系电话、总分分别定义为互相独立的简单变量,难以反映它们之间的内在联系。为了方便处理此类数据,常常把这些关系密切但类型不同的数据项组织在一起,即“封装”起来,并为其取一个名字,在C语言中就称其为结构体(也人称为构造体),结构体是用户自定义数据类型的一种。

8.1.2 结构体类型的定义 结构体类型定义的一般形式 struct 结构型名 {数据类型标识符 成员1; 数据类型标识符 成员2; … 8.1.2 结构体类型的定义 结构体类型定义的一般形式 struct 结构型名 {数据类型标识符  成员1; 数据类型标识符  成员2; … 数据类型标识符  成员n; }; 请读者注意结构体定义语句的右花括号后面用分号(;)做语句结束标记。

8.1.2 结构体类型的定义 结构体型定义实例 例如:为了存放一个人的姓名、性别、年龄、工资,可以定义如下的结构型: 8.1.2 结构体类型的定义 结构体型定义实例 例如:为了存放一个人的姓名、性别、年龄、工资,可以定义如下的结构型: struct person { char name[10]; char sex; int age; float wage; }; /*这个名为person的结构型共含有4个成员*/

8.1.2 结构体类型的定义 结构型嵌套定义 【例8.1】一开始所讲的例题中的birthday类型和person类型。 8.1.2 结构体类型的定义 结构型嵌套定义 【例8.1】一开始所讲的例题中的birthday类型和person类型。 struct birthday /*定义含有3个整型成员的结构型 birthday*/ { int year; int month; int day; }; struct person /*定义含有4个成员的结构型 person*/ {char name[20]; char sex; struct birthday bir; /*该成员的数据类型是结构型*/ float wage;

8.2 结构体变量的定义和引用 8.2.1结构型变量的定义和初始化 先定义结构型,后定义变量 定义结构型的同时定义变量 8.2 结构体变量的定义和引用 8.2.1结构型变量的定义和初始化 先定义结构型,后定义变量 定义结构型的同时定义变量 定义无名称的结构型的同时定义变量

1. 先定义结构型,后定义变量 例如:为学生信息定义2个变量x和y , 程序段如下: struct student {long number; char name[20]; char sex; float score[3]; }; struct student x,y; 在定义变量的同时,可以变量赋初值,例如上例中的定义语句可以改写如下: struct student x={100001L,”Tom”,’m’,{86,94,89}}, y={100002L,”Lucy”,’f’,{78,88,45}};

2. 定义结构型的同时定义变量 例如:为学生信息定义2个变量x和y , 并给他们赋初值,程序段如下: struct student {long number; char name[10]; char sex; float score[3]; }x={100001L,”Tom”,’m’,{86,94,89}}, y={100002L,”Lucy”,’f’,{78,88,45},}; 这种方法是将类型定义和变量定义同时进行。以后仍然可以使用这种结构型来定义其它的变量。

3. 定义无名称的结构型的同时定义变量 例如:为学生信息定义2个变量x和y ,并给它们赋初值,程序段如下: struct {long number; char name[10]; char sex; float score[3]; }x={100001L,”Tom”,’m’,{86,94,89}}, y={100002L,”Lucy”,’f’,{78,88,45},}; 这种方法是将类型定义和变量定义同时进行,但结构型的名称省略,以后将无法使用这种结构型来定义其它变量,建议尽量少用。

8.2.2 结构型变量成员的引用 1.结构型变量成员的引用方法 2.结构型变量成员地址的引用方法 3.结构型变量地址的引用方法

1. 结构型变量成员的引用方法 结构型变量成员的引用格式如下: 结构型变量名. 成员名 其中的“.”称为成员运算符,其运算级别是最高的,和圆括号运算符“()”、下标运算符“[]”是同级别的,运算顺序是自左向右。 如果某个结构型变量的成员数据类型又是一个结构型,则其成员的引用方法如下: 外层结构型变量. 外层成员名. 内层成员名

结构型变量成员的引用实例 【例8.2】求Tom的三门课程的成绩总分,并在显示器显示出来(使用结构型变量成员的引用)。 #include”string.h” struct student { long number; char name[10]; char sex; float score[3]; }; main() { struct student stu1; /*定义student类型的变量stu1*/ stu1.number=100001L; /*给结构型变量stu1的成员number赋值*/ strcpy(stu1.name;”Tom”); /*给结构型变量stu1的成员name[]赋值*/ stu1.sex=’f’; /*给结构型变量stu1的成员sex赋值*/ stu1.score[0]=89; /*给结构型变量stu1的成员score[]赋值*/ stu1.score[1]=91; stu1.score[2]=86; printf(“%s的总分是:%f\n”,stu.name,stu1.score[0]+stu1.score[1]+stu1.score[2]); }

&结构型的变量名.成员名 2. 结构型变量成员地址的引用方法 结构型的变量成员地址引用格式如下: 存放结构型变量成员地址的指针变量类型必须和该成员的类型相同。

【例8.4】结构型变量成员地址引用。 #include “string.h” /*程序中使用了字符串处理函数*/ sturct student2 /*定义student2结构型*/ { long number; char name[10]; } main() { struct student2 x; /*定义student2类型的变量x*/ long *p_number; /*定义能指向结构型student成员number的指针变量*/ char *p_name; /*定义能指向结构型student成员namer的指针变量*/ p_number=&x.number; /*让指针变量指向结构型变量x的成员*/ *p_ number=100001L; /*用指针变量给结构型变量x的所有成员赋值*/ strucpy(p_ name,”zhongxin”); printf(“number=%1d name=%s\n”,*p_number,*p_ name); /*用指针变量输出结构型变量x所有成员的值*/ 从这个例子可以看出,使用指向结构型变量成员的指针变量来引用成员的方法比较繁琐,可以直接使用结构型变量的指针成员来引用成员。具体使用方法请参看第8章8.4节。

3. 结构型变量地址的引用方法 结构型变量地址的引用格式如下: &结构型变量名 例如:借用例8.4中的结构型struct student2: struct student2 y,*sty=&y; 存放结构型变量地址的指针变量必须是类型相同的结构型指针,关于如何使用结构型变量地址的例子请参见8.4节中介绍的指向结构型数据的指针变量。

8.3 结构型数组的定义和引用 在实际应用中,我们经常要处理的是具有 相同数据结构的一个群体。比如一批书,所有 8.3 结构型数组的定义和引用 在实际应用中,我们经常要处理的是具有 相同数据结构的一个群体。比如一批书,所有 员工的通信地址,一个班级的学生等。由相同 结构类型变量组成的数组,称为结构型数组。例 如,全班有40人,在总成绩单上每人占一行,每 行的内容包括学号、姓名、3门功课的成绩、平 均分、名次,这样一个总成绩单就可以用结构型 数组表示。

8.3.1 结构型数组的定义和初始化 1.先定义结构型,然后再定义结构型数组并赋初值 2.定义结构型的同时定义数组并赋初值 8.3.1 结构型数组的定义和初始化 1.先定义结构型,然后再定义结构型数组并赋初值 2.定义结构型的同时定义数组并赋初值 3.定义无名称的结构型的同时定义数组并赋初值

1.先定义结构型,再定义结构型数组并赋初值运算 struct student /*定义结构型*/ { long number; char name[10]; char sex; float score[3]; }; struct student s[3]={ {200001L,”Tom”,’m’,{78,86,92} }, {200002L,”Lucy”,’f’,{85,69,82} }, {200003L,”Jack”,’m’,{84,88,96} } };

2. 定义结构型的同时定义数组并赋初值 struct student /*定义结构型*/ {long number; char name[10]; char sex; float score[3]; }s[3]= { {200001L,”Tom”,’m’,{78,86,92} }, {200002L,”Lucy”,’f’,{85,69,82} }, {200003L,”Jack”,’m’,{84,88,96} } };

3. 定义无名称的结构型的同时定义数组并赋初值 struct /*定义结构型*/ {long number; char name[10]; char sex; float score[3]; }s[3]= { {200001L,”Tom”,’m’,{78,86,92} }, {200002L,”Lucy”,’f’,{85,69,82} }, {200003L,”Jack”,’m’,{84,88,96} } };

8.3.2 结构型数组元素成员的引用 1.结构型数组元素的引用格式如下; 结构型数组名[下标] . 成员名 8.3.2 结构型数组元素成员的引用 1.结构型数组元素的引用格式如下; 结构型数组名[下标] . 成员名 2.结构型数组元素成员地址的引用格式如下: &结构型数组名[下标].成员名

1. 结构型数组元素的引用: 结构型数组名[下标] . 成员名 1. 结构型数组元素的引用: 结构型数组名[下标] . 成员名 【例8.5】输入3个学生的数据,每个学生的信息由学号、姓名和三门功课的成绩组成,然后计算每一个学生的总分,并输出总分最高的学生信息。 分析:将3个学生定义为结构型类型数组,学号为长整型、成绩为实型数组,总分存在成绩数组中。

#define N 3 struct student /*定义结构型*/ { long number; char name[10]; float score[N+1]; /*score数组前三个元素用来存放成绩,第四个元素用来存 放总分*/ }stu[N]; main() { float max=0; int i,j,max_i=0; for(i=0;i<N;i++) printf(“输入第%d个学生的信息,依次输入学号,姓名,三个成绩,各数据之间用,隔开”,i); {scanf(“%ld,%s,%f,%f,%f”, ,&stu[i].number,&stu[i].name,&stu[i].score[0], &stu[i].score[1], &stu[i].score[2]); stu[i].score[3]=stu[i].score[0]+ stu[i].score[1]+ stu[i].score[2]; if (max<stu[i].score[3]) max=stu[i].score[3],max_i=i; } printf(“总分最高分的学号是:%ld,姓名是:%s,总分是:%f”,stu[max_i].number, stu[max_i].name,stu[max_i].score[3]);

2. 结构型数组元素成员地址的引用 &结构型数组名[下标].成员名 2. 结构型数组元素成员地址的引用 &结构型数组名[下标].成员名 【例8.6】结构型数组元素成员地址的引用 #include “string.h” struct student3 {long number; char name[10]; }; main() {struct student3 s[2]; long *p_number; char *p_name; p_number=&s[0].number; p_name=s[1].name; *p_number=2009080l; strcpy(p_name,”Mary”); printf(“%ld %s\n”,s[0].number,s[1].name); }

8.4 指向结构型数据的指针变量的定义和引用 前面已经提到,结构型变量或数组元素 的成员可以使用“成员运算符”来直接引用, 也可以使用指向结构型数据成员的指针变量 来引用,但不方便。我们还可以使用指向结 构型变量或数组元素的指针变量来间接引用 其成员。

方式1 (*指针变量).成员名 方式2 指针变量->成员名 8.4.1 指向结构型变量的指针(两种引用方式) 方式1 (*指针变量).成员名 方式2 指针变量->成员名 方式1比较好理解,其中“*指针变量”就代表了它所指向的结构型变量,利用“成员运算符”来引用,其作用相当于“结构型变量.成员名”。需要注意的是“*指针变量”必须用圆括号括住,因为“*”运算符的级别低于“.”运算符,如果不加括号,则优先处理“.”运算符,将出现“指针变量.成员名”,会造成语法错误。 方式2是一种新的引用方法,其中“->”称为“指向成员运算符”,也简称“指向运算符”。其运算级别和“()”、“[]”、“.”是同级的。指向运算符的左边必须是已指向某个结构型变量或数组元素的指针变量,其右边必须是对应结构型数据的成员名。

8.4.2 指向结构型数组的指针 1.指针变量指向数组元素 2.指针变量指向数组首地址 8.4.2 指向结构型数组的指针 1.指针变量指向数组元素 如果一个结构型数组元素的地址已赋予相同结构型指针变量(即指针变量指向结构型数组元素),可以使用下列两种方法来引用数组该元素的成员,其作用完全相同。 方式1 (*指针变量)。成员名 方式2 指针变量->成员名 注意:这里的指针变量必须是指向某个数组元素的。例如,它指向的数组元素为“数组名[k]”,则上述两种引用方式均代表“数组名[k]。成员名”。 2.指针变量指向数组首地址 当一个结构型数组的首地址已经赋予相同结构型的指针变量(即指针变量指向结构型数组),可以使用下列两种方式来引用下标为i的数组元素成员,其作用完全相同。 方式1(*(指针变量+i)).成员名 方式2(指针变量+i)— >成员名 注意:这里的指针变量必须是指向某个数组首地址的,则上述两种引用方式均代表“数组名[i]。成员名

8.4.3 在函数间传递结构型数据 1. 采用“全局外部变量方式传递数据” 2. 采用“返回值方式传递数据” 3. 采用“形式参数和实际参数结合的地址传递方式双向传递数据”

8.5 用指针处理链表 我们知道用数组存放数据时,必须事先定义好数 组的大小,不能在程序中随便进行调整。比如有的 8.5 用指针处理链表 我们知道用数组存放数据时,必须事先定义好数 组的大小,不能在程序中随便进行调整。比如有的 班有100人,有的班只有30人,如果要用同一个数 组先后存放不同班级的学生数据,则必须定义长度 为100的数组。如果事先难以确定一个班的最多人 数,则必须把数组定义的足够大,以存放任何班级 的学生数据,这显然非常浪费存储空间。为此C语 言提供了动态数组的构建,即链表。

8.5.1 什么是链表 链表如同一条铁链一样,一环扣一环,中间是不能断开 的。这好比幼儿园的老师带领孩子出去玩,老师牵着第一个 孩子的手,第一个孩子的另一只手牵着第二个孩子的手…… 这就是一个“链”,最后一个孩子有一只手空着,他就是“链 尾”。要找这个队伍,就必须先找到老师,然后顺序找到每 一个孩子。 链表是一种动态数据结构,在程序的执行过程中可以根据 需要随时间系统申请存储空间,动态地进行存储空间的分 配。动态数据结构最显著的特点是包含的数据对象个数及其 相互关系都可以按需要改变。常用的动态数据结构有链表、 循环链表、双向链表三种。本章只介绍动态数据结构中最简 单的单链表的建立及其基本操作。

1.单链表的结构 链表有一个“头指针”head,它存放链表第一个结点的首地址,它没有数据,只是一个指针变量。从图8-2中我们看到它指向链表的第一个元素。链表的每一个元素称为一个“结点”(node)。每个结点都分为两个域,一个是数据域,存放各种实际的数据,如学号num、姓名name、性别sex、和成绩score等。另一个域为指针域,存放下一个结点的首地址,即指向下一个结点。链表中的每一个结点都是同一个结构类型。最后一个结点称为“链尾”,尾结点无后续点,因此不指向其他的元素,表尾结点的指针为空(NULL)。

2.链表结点的构成 由于每个结点包含数据域或者指针域两部分内容,所以链表结点采用 结构体表示。例如链表结点的数据结构定义如下: struct node { int num; char name[10]; float score; struct node *next; }; 在链表结构中,除了数据项成员之外,还应包含一个指向本身的指 针,该指针在使用时指向具有相同类型结构体的下一个结点。 在链表结点的数据结构中,比较特殊的一点就是结构体内指针域的数 据类型使用了未定义成功的数据类型。这是在C语言中唯一可以先使 用后定义的数据结构。

3.如何建立和输出一个简单静态链表 【例 8.10】建立一个如图8-3所示的简单链表,它由三个学生数据结点组成。请输出各结点中的数据。 分析:为方便操作,将学生定义为一个结构体类型student,它有三个成员分别用来表示学生的学号、姓名和下一个结点的地址。在程序中逐个输入各学生的数据,通过地址赋值操作建立链表。利用当型循环用printf语句逐个输出个结点中成员的值。

程序如下: #include<studio.h> struct student { char no[6]; char name[10]; struct student *next; }; void main() A={“02001”,”tom”}, B={“02002”,”jane”}, C={“02003”,”henry”}; struct srudent *head=NULL,*p; head=&A; A.next=&B; B.next=&C; C.next=NULL; p=head; while (p!=NULL) { printf(“No:%s\tName:%s\n”,p->no,p->name); p=p->next; } 在本例中,所有结点都是在程序中定义的、不是临时开辟的、用完后也不能释放,我们把这种链表称为“静态链表”

4.动态存储分配函数 所谓“动态链表”就是链表的结构是动态分配和存储的,在程序的执行过程中要根据需要随时向系统申请存储空间,动态地进行存储空间的分配。在C语言中,提供了一下函数完成存储空间的动态分配和释放。 malloc函数 calloc函数 free函数

malloc函数 其函数原型为:void * malloc(unsigned size) 其作用是在内存的动态存储区中分配一个长度为size的连续空间,并返回指向该空间起始地址的指针。若分配失败(如系统不能提供所需内存),则返回空指针NULL。

calloc函数 其函数原型为:void * calloc(unsigned n,unsigned size) 该函数有两个形参n和size。其作用是在内存的动态存储区中分配n个长度为size的连续空间,并返回指向该空间首地址的指针。如用calloc(20,20)可以开辟20个(每个大小为20字节)的空间,即空间总长为400字节。若分配失败,则返回空指针NULL。

free函数 其函数原型为:void * free(void * ptr) 其作用是释放由malloc、calloc等函数申请的内存空间,使这部分内存区能够被其他变量所使用。ptr是最近一次调用malloc()或calloc()函数返回的值。Free函数没有返回值。 在使用上述函数时要注意,函数的原型在文件malloc.h和stdlib.h中定义。在程序中必须包含这两个头文件。下面的程序就是malloc()和free()两个函数配合使用的简单实例。

【例 8.11】存储空间的动态分配。 #include<stdlib.h> #include<stdio.h> #include<string.h> main() { char *str; if((str=(char*) malloc(10))==NULL) printf(“Not enough memory to allocate buffer\n”); exit(1); } strcpy(str,”welcome”); printf(“String is %s\n”,str); free(str); 本例中首先用malloc函数向内存申请一块内存区,并把首地址赋予指针变量 str,是str指向该区域。最后用free函数释放str指向的内存空间。整个程序包含 了申请内存空间、使用内存空间、释放内存空间三个步骤,实现存储空间的动 态分配。

8.5.2 动态链表的基本操作 链表有五种基本操作: 建立 插入 删除 输出 查找

1.单链表的创建 建立动态链表就是建立结点空间、输入各结点数据和进行结点链接的过程,也就是在程序执行过程中从无到有地建立起一个链表。 通过以下实例来说明如何建立一个动态链表。 【例 8.12】建立一个链表存放学生数据。为简单起见,我们假定学生数据结构中有学号和年龄两项。编写一个建立链表的函数creat。

创建单链表的算法

单链表创建过程分析

创建单链表实例程序清单 #define LEN sizeof(struct stu) sruct stu /*结构stu定义为外部类型,方便程序中的各个函数使用*/ { int num; int age; struct stu *next; }; struct stu *creat(void) /*creat函数用语动态建立一个有n个结点的链表,返回与结点相同类型的指针*/ struct stu *p1,*p2,*head; /*head为头指针,p2指向已建链表的最后一个结点,p1始终指向当前新开辟的结点*/ int n=0; p1=p2=(struct stu *) malloc(LEN); /*申请新结点,长度与stu长度相等;同时使指针变量p1、p2指向新结点*/ scanf (“%d %d”,&p1->num,&p1->page); /*输入结点的值*/ head=NULL; while (p1->num!=0) /*输入结点的数值不为0*/ n++; if(n==1)head=p1; /*输入的结点为第一个新结点即空表,将输入的结点数据接入表头*/ else p2->next=p1;/*非空表即输入的结点不是第一个结点,将输入的结点数据接到表尾*/ p2=p1; p1=(struct stu *)malloc(LEN); /*申请下一个新结点*/ scanf(“%d %d”,&p1->num,&p1->page); } p2->next=NULL; return(head); /*返回链表的头指针*/

建立链表的具体步骤 (1)定义链表的数据结构。 (2)创建一个空表。 (3)利用malloc()函数向系统申请分配一个结点。 (4)若是空表,则将新结点接到表头;若是非空表,则将新结点接到表尾。 (5)判断一下是否有后续结点要接入链表,若有则转到步骤(3),否则结束。

2.单链表的插入 链表的插入是指将一个结点插入到一个已有的链表中。 【例 8.13】以前面建立的动态链表为例,编写一个函数,使其能够在链表中指定的位置插入一个结点。

单链表插入实例分析 要在一个链表的指定位置插入结点,要求链表本身必须已按某种规律进行了排序。例如学生数据链表中,各结点的成员项按学号由小到大顺序排列。如果要求按学号顺序插入一个结点,则要将插入的结点依次与链表中各结点比较,寻找插入位置。结点可以插在表头、表中、表尾。结点插入存在以下几种情况。 1. 如果原表是空表,只需使链表的头指针head指向被插结点。 2. 如果被插结点值最小,则应插入第一个结点之前。将头指针head指向被插结点,被插结点的指针域指向原来的第一个结点。 3. 如果在链表中某位置插入,使插入位置的前一结点的指针域指向被插结点,使被插结点的指针域指向插入位置的后一个结点。 4. 如果被插结点值最大,则在表尾插入,使原表尾结点指针域指向被插结点,被插结点指针域置为NULL。

单链表插入实例图形分析

单链表插入实例操作步骤

单链表插入实例程序清单 struct stu *insert (struct stu *head,struct stu *p1) { struct stu *p2,*p3; p2=head; if(head=NULL) /*空表插入*/ head=p1; p1->next=NULL; } else while ((p1->num>p2->num)&&(p2->next!=NULL)) p3=p2; p2=p2->next; /*找插入位置*/ if ( p1->num<=p2->num) { if (head==p2) head=p1; /*在第一结点之前插入*/ else p3->next=p1; /*在其他位置插入*/ p1->next=p2; } { p2->next=p1; p1->next=NULL; } /*在表末插入*/ return head; /*返回链表的头指针*/

链表插入操作的具体步骤 定义一个指针变量p1指向被插结点。 首先判断链表是否为空,为空则使head指向被插结点。 链表若不是空,用当型循环查找插入位置。 找到插入位置后判断是否在第一个结点之前插入,若是则使head指向被插入结点,被插结点指针域指向原第一结点;否则在其他位置插入;若插入的结点大于表中所有结点,则在表末插入。 函数返回值为链表的头指针。

3.单链表的删除 链表中不再使用的数据,可以将其从表中删除并释放其所占用的空间,但注意在删除结点的过程中不能破坏链表的结构。 【例 8.14】以前面建立的动态链表为例,编写一个删除链表中指定结点的函数delete1。

单链表的删除实例分析 假设链表按学生的学号排列,当某结点的学号与指定值相同时,将该结点从链表中删除。首先从头到尾依次查找链表中给结点,并与各结点的学生学号做比较,若相同,则查找成功,否则,找不到结点。由于结点在链表中可以有三种不同位置:位于开头,中间或结尾,因此从链表中删除一个结点主要分两种情况,即删除链表头结点和非表头结点。 1. 如果被删除的结点是表头结点,使head指向第二个结点。 2. 如果被删除的结点不是表头结点,使被删结点的前一结点指向被删结点的后一结点。

单链表的删除实例图形分析

单链表 的删除实例操作步骤

单链表的删除实例程序清单 struct stu * delete ( struct stu *head,int num) /*以head为头指针删除num所在结点*/ { struct stu *p1,*p2; if (head=NULL) /*如为空表,输出提示信息*/ printf(“\nempty list!\n”); goto end; } p1=head; while ( p1->num!=num && p1->next!=NULL) /*当不是要删除的结点,而且也不是最后一个结点时,继续循环*/ {p2=p1;p1=p1->next; } /*p2指向当前结点,p1指向下一结点*/ if (p1->num==num) { if (p1==head) head=p1->next; /*如找到被删结点,且为第一结点,则使head指向第二结点,否则使p2所指结点的指针指向下一结点*/ else p2->next=p1->next; free(p1); printf (“ The node is deleted\n”); else printf (“The node not been found!\n”); end: return (head);

链表删除操作的具体步骤 定义一个指针变量p指向链表的头结点。 用循环从头到尾依次查找链表中各结点并与各结点的学生学号做比较,若相同,则查找成功退出循环。 判断该结点是否为表头结点,如果是使head指向第二个结点,如果不是使被删结点的前一结点指向被删结点的后一结点。同时结点个数减1。

4.单链表的输出 链表的输出比较简单,只要将链表中的各个结点数据依次输出即可 【例 8.15】编写一个输出链表的函数print。

设立一个指针变量p,先指向链表的头结点,输出该结点的数据域,然后使指针p指向下一个结点,重复上述工作,直到链表尾部。具体算法如图8-9所示。

单链表的输出实例程序清单 #define LEN sizeof (struct stu) struct stu { int num; int age; struct stu *next; }; void print ( struct stu *head) /*print函数用于输出以head为头的链表各结点的值*/ struct stu *p; p=head; /*取得链表的头指针*/ while (p!=NULL) printf ( “%6d%6d”,p->num,p->page); /*输出链表结点的值*/ p=p->next; /*使指针变量p指向下一个结点,跟踪链表增长*/ }

链表输出操作的具体步骤 定义一个指针变量p。 使p指向链表的头结点。 若是非空表,输出该结点的数据域;若空表则退出。 重复上述操作直到链表尾部。

链表综合实例 【例 8.16】在前面学习的建立链表,输出链表,删除结点,插入结点操作的基础上,试编一主函数将以上的建立链表,输出链表,删除结点,插入结点的函数组织在一起,并输出全部结点的值。

综合实例程序清单 #define NULL 0 main () { struct stu *head; struct stu *stu; int del_num; printf (“input records:\n”); head=creat(); /*建立链表,并返回表头*/ print (head); /*输出链表 */ printf (“\nInput the deleted number:”); scanf (“%d”,&del_num);

综合实例程序清单(续) while (del_num!=0) { head=delete1 (head,del_num); /*从链表中删除del_num结点*/ print (head); /*输出链表 */ printf (“\nInput the deleted number:”); scanf (“%d”,&del_num); } printf (“\nInput the inserted record:”); stu=(struct stu *)malloc(LEN); scanf (“%d,%d”,&stu->num,&stu->age); while (stu->num!=0) head=insert (head,stu); /*在链表中插入一节结点stu*/ stu=( struct student *)malloc (LEN); free (stu) /*对于num=0的结点,未插入,应删除其空间*/

8.6 共 用 型 共用型和结构型的比较

8.6.1 共用型的定义 union共用型名 {数据类型1 成员名1; 数据类型2 成员名2; … 数据类型n 成员名n; }; 8.6.1 共用型的定义 union共用型名 {数据类型1 成员名1; 数据类型2 成员名2; … 数据类型n 成员名n; }; 注意在右花括号的后面有一个语句结束符分号。

共用型的定义实例 例如:为了节省内存,可以将不同的三个数组定义在一个共用型中,总计可节省300个单元: union c_i_f {char c1[100]; /*该成员占用100个单元*/ int i2[100]; /*该成员占用200个单元*/ float f3[100]; /*该成员占用400个单元*/ }; /*该共用型数据共用400个单元*/ 需要提醒读者注意的是,共用型数据中每个成员所占用的内存单元都是连续的,而且都是从分配的连续内存单元中第一个内存单元开始存放的。所以,对共用型数据来说,所有成员的首地址都是相同的。这是共用型数据的一个特点。

8.6.2 共用型变量的定义 定义方法基本上与结构型相同,也存在以下三种方法,但不能在定义时进行初始化。 8.6.2 共用型变量的定义 定义方法基本上与结构型相同,也存在以下三种方法,但不能在定义时进行初始化。 1. 先定义共用型,然后定义变量与数组。 2. 定义共用型的同时定义变量与数组 3. 定义无名称的共用型同时定义变量与数组

1.先定义共用型,然后定义变量u1与数组u2[5]。 union u {int i_a[10]; /*该成员占用20个单元*/ char c_a[3][4]; /*该成员占用12个单元*/ long l; /*该成员占用4个单元*/ double d; /*该成员占用8个单元*/ }; /*该共用型数据共占用20个单元*/ union u u1,u2[5];

2.定义共用型的同时定义变量u1与数组u2[5] union u {int i_a[10]; /*该成员占用20个单元*/ char c_a[3][4]; /*该成员占用12个单元*/ long l; /*该成员占用4个单元*/ double d; /*该成员占用8个单元*/ } u1,u2[5];

3. 定义无名称的共用型同时定义变量u1与数组u2[5] union /*无名称*/ {int i_a[10]; /*该成员占用20个单元*/ char c_a[3][4]; /*该成员占用12个单元*/ long l; /*该成员占用4个单元*/ double d; /*该成员占用8个单元*/ } u1,u2[5];

8.6.3 共用型变量的引用 共用型变量或数组元素成员的引用格式如下: 共用型变量名.成员名 8.6.3 共用型变量的引用 共用型变量或数组元素成员的引用格式如下: 共用型变量名.成员名 共用型变量成员地址的引用和指针变量的使用格式如下: 指针变量=&共用型变量名.成员名 共用型变量地址的引用和指针变量的使用格式如下: 指针变量=&共用型变量名

8.7 枚举型 顾名思义,就是把有限的数据一一例举出来,例如: 一个星期7天 性别只有”男”和”女” 8.7 枚举型 顾名思义,就是把有限的数据一一例举出来,例如: 一个星期7天 性别只有”男”和”女” 中国有23个省,5个自治区,4个直辖市,2个特别行政区等。 如下图:在填写用户资料中的所在城市时,把中国的23个省,5个自治区,4个直辖市,2个特别行政区都列举出来,供注册者选择,这样有利于数据的规范且不会出错。枚举型和结构型、共用型一样,也是一种用户自定义的数据类型,在使用时必须先定义后使用。

8.7.1 枚举型的定义 enum 枚举型名 {枚举常量1,枚举常量2,…枚举常量n}; 注意在右花括号的后面有一个语句结束符分号。 8.7.1 枚举型的定义 enum 枚举型名 {枚举常量1,枚举常量2,…枚举常量n}; 注意在右花括号的后面有一个语句结束符分号。 其中:枚举型名是用户取的标识符; 枚举常量是用户给常量取的标识符。 该语句定义了一个名为“枚举型名”的枚举类型,该枚举型中含有n个枚举常量,每个枚举型常量均有值。C语言规定枚举常量的值依次等于0、1、2、…、n-1.

枚举型定义实例 例如:定义一个表示星期的枚举型: enum week {sun,mon,tue,wed,thu,fri,sat}; 定义的这个枚举型共有7个枚举常量,它们的值依次为0、1、2、3、4、5、6。 C语言规定,在定义枚举型时,可以给枚举常量赋初值,方法是在枚举常量的后面跟上“=整型常量”。 例如:表示三原色的枚举型可定义如下: enum color1 {red=2,yellow=4,blue=7}; 则枚举常量red的值为2,yellow的值为4,blue的值为7。

8.7.2 枚举型变量的定义 当某个枚举型定义后,可以用这种枚举型来定义变量、数组。定义的方法有三种。 8.7.2 枚举型变量的定义 当某个枚举型定义后,可以用这种枚举型来定义变量、数组。定义的方法有三种。 1. 先定义枚举型,后定义枚举型变量、数组 enum color {red,yellow,blue}; enum color color_1,color_2[2]; /*定义一个枚举型变量color1和具有两个元素的数组color_2*/ 2. 定义枚举型的同时定义枚举型变量、数组 {red,yellow,blue}enum color color_1,color_2[2]; 3. 定义无名称的枚举型的同时定义枚举型变量、数组 enum {red,yellow,blue} enum color color_1,color_2[2];

8.7.3 枚举型变量的引用 给变量或数组元素赋值,格式为: 枚举型变量或数组元素=同一种枚举型常量名 enum color 8.7.3 枚举型变量的引用 给变量或数组元素赋值,格式为: 枚举型变量或数组元素=同一种枚举型常量名 enum color {red,yellow,blue} c_1; c_1=yellow; /*赋值*/ 在循环中用枚举变量或数组元素控制循环 {red,yellow,blue}c_1; int k=0; for(c_1=red;c_1<=blue;c_1++) k++; printf(“k=%d\n”,k);

8.8 用户自定义类型 C语言允许用户定义自己习惯的数据类型名称,来替代系统默认的基本类型名称、数组类型名称、指针类型名称和用户自定义的结构型名称、共用型名称、枚举型名称等。 用户字定义类型名的方法是通过下列定义语句实现的: typedef 类型名1 类型名2;

1. 基本类型的自定义 对所有系统默认的基本来性可以利用下面的自定义类型语句来重新定义类型名。 【例 8.22】基本类型自定义例。 1. 基本类型的自定义 对所有系统默认的基本来性可以利用下面的自定义类型语句来重新定义类型名。 【例 8.22】基本类型自定义例。 typedef float REAL; /*定义单精度实型为REAL*/ typedef char CHARACTER /*定义字符型为GHARACTER*/ main() { REAL f1; /*相当于float f1;*/ CHARACTER c1; /*相当于char c1,*/ … }

2.数组类型的自定义 对数组类型可以利用下面的自定义类型语句来定义一个类型名 typedef 类型说明符 用户类型名[数组长度] 【例 8.23】数组类型自定义例。 typedef float F_ARRAY[20]; typedef char C_ARRAY[10]; main() { F_ARRAY f1,f2; /*相当于 float f1[20], f2[20]*/ C_ARRAY name,department; /*相当于char name[10],department[10]*/ … }

3.结构型、共用型的自定义 【例 8.24】结构型自定义例。 对程序中需要的结构型可以利用下面的自定义类型语句来定义一个类型名 typedef struct {类型说明符 成员名1; 类型说明符 成员名2;... }用户类型名; 【例 8.24】结构型自定义例。 typedef struct {long num; char name [10]; char sex; }STUDENT; main() {STUDENT stu1,stu[10]; /*相当于struct {long num; Char sex; }stu1,stu[10];*/ … }

4.指针型的自定义 对某种数据类型的指针型可以利用下面的自定义类型语句来定义一个类型名 typedef 类型说明符 *用户类型名; 【例 8.25】指针类型自定义例 typedef int *POINT_I; typedef char *POINT_C; main() { POINT_I p1,p2; /*相当于int *p1,*p2*/ POINT_C p3,p4; /*相当于char *p3,*p4*/ … }

小 结 本章详细介绍了结构型变量的定义、初始化、引用等方法,同时介绍了另外一种用于节省内存的构造型数据:共用型,最后简单介绍了枚举型数据的使用。 学习本章时应牢记,结构型、共用型是一种用户自定义类型,因此在使用前必须先定义。同时掌握其引用的格式。