第8章 结构体与链表（课件）-《 C语言程序设计》同步教学（电子工业出版社）

第8章 结构体与链表 8.1 结构体 在处理大量有序数据时,使用数组是很方便的.但是,由于数组是由同一种类型数据组成的,这就带来很大的局限性。 例如:不能利用数组存放一个班级同学的全部资料,每个同学的资料包括:姓名、年龄、性别、身份证号等，因为这些数据的类型都不相同。然而利用用户定义的结构体类型就可以很好的解决这个问题。 姓名 年龄 性别 身份证号 民族 住址 电话号码 字符数组 整型 字符 字符数组 字符 字符数组 字符数组 8.1.1 结构体定义、引用和初始化 一、结构体类型定义的一般形式： struct 结构体名 { 数据类型 成员名1; 数据类型 成员名2; … 数据类型 成员名n; }; 其中： struct是关键字，作为定义结构体类型的标志；结构体名，由用户自行定义；花括号内是结构体的成员说明表，用来说明该结构体有哪些成员及它们的数据类型。 例如定义一个学生的结构体类型： struct student { char name[10];//姓名 int age;//年龄 char sex;//性别 char cardID[19];//身份证号 char nation;//民族 char address[40];//住址 char tel[20];//电话号码 }; 姓名 年龄 性别 身份证号 民族 住址 电话号码 字符数组 整型 字符 字符数组 字符 字符数组 字符数组 示例1：学生结构体类型1 结构体成员的类型可以是简单类型、数组类型或者是结构体类型等任何数据类型。 结构体类型的定义只是描述结构体的组织形式，并没有分配一段内存单元来存放各数据项成员。只有定义了这种类型的变量，系统才为变量分配内存空间，占据存储单元。 结构体类型定义可以在函数的内部，其作用域仅限于该函数内部；也可以定义在函数的外部，其作用域是从定义处开始到本文件结束。 在定义结构体类型时，数据类型相同的成员可以在一行中说明，成员间用逗号分开。 说明： 5 //定义出生日期为结构体类型日期型，结构体名为Date struct Date {int year; int month; int day; }; //定义学生结构体类型，结构体名为Student struct Student { char no[20]; //学号，类型字符串。 char name[20]; //学生姓名，类型字符串。 //出生日期，类型为已定义的结构体类型日期 struct Date date; char sex; //性别，类型字符型。 }; 示例2：学生结构体类型2 二、结构体类型变量的定义： 某个结构体一经定义，就可以指明该种结构体的具体对象，即定义该种类型的变量。 定义结构体类型的变量的三种方法： 先定义结构体类型，再定义该种类型的变量。 在定义结构体类型的同时定义结构体变量。 直接定义结构体类型变量。 1.先定义结构体类型，再定义该种类型的变量 格式：struct 结构体名 结构体变量名表； 如： struct date { int year; int month; int day; }; struct date Date1; struct date Date2; 二、结构体类型变量的定义： 2.在定义结构体类型的同时定义结构体变量 格式：struct 结构体名 {数据类型 成员名1; 数据类型 成员名2; … 数据类型 成员名n; }结构体变量名表； 如：struct date { int year; int month; int day; }Date1,Date2; 二、结构体类型变量的定义： 3.直接定义结构体类型变量 格式：struct { 数据类型 成员名1; 数据类型 成员名2; … 数据类型 成员名n; }结构体变量名表； 如：struct { int year; int month; int day; }Date1,Date2; 注意： 这种形式由于省略了结构体名，因此以后不能用它再来定义其它变量。 二、结构体类型变量的定义： 结构体变量的定义在函数的数据说明部分进行，也可以在函数的外部定义。但都必须是类型定义在前，变量定义在后。 结构体变量一经定义，在程序运行时，系统将按照结构体类型定义时的内存模式为结构体变量分配一定的存储单元。 结构体变量所占内存应该是结构体类型定义的所有成员所占内存之和。 说明： 1.引用结构体变量的成员项。 对结构体变量的引用，在一般情况下结构变量不作为一个整体参加数据处理，而是用结构体的变量各个成员项来参加各种运算和操作。格式：结构体变量名.成员项名 例如：将日期2002年10月19日赋给struct date型变量Date1可表示成： Date1.year=2002; Date1.month=10; Date1.day=19; 三、结构体类型变量的引用： 说明： “.”是一个运算符，表示对结构体变量的成员进行访问运算，它的优先级为最高级，结合方向是从左到右。 结构体成员项是结构体中的一个数据，对其进行何种运算是由它的类型决定，允许参加运算的种类与同类型的简单变量的种类相同。 如果一个结构体成员本身又是一个结构体类型变量，则要通过两个“.”运算符来访问该结构成员的结构成员。 三、结构体类型变量的引用： 2.一个结构体变量作为一个整体来引用。 C语言允许两个相同类型的结构体变量之间相互赋值，这种结构体变量之间赋值的过程是一个结构体变量的成员项的值赋给另一个结构体变量的相应部分。 如下面的赋值语句是合法的： wang=zhang; 注意： 不允许用赋值语句将一组常量直接赋值给一个结构体变量。如下面的赋值语句是不合法的： wang={2345678,“Li Qiang Zhuang”,2003,5,1, 23456.98 }； 三、结构体类型变量的引用： 同其他数据类型一样，结构体类型变量在定义时也可以直接进行初始化。 格式1： struct Student s1={"09001","lily",{1990,1,12},'w'}; 格式2： struct Student/*定义一个表示学生信息的结构体类型*/ { char *no; char *name; struct Date date; char sex; }s1={"09001","lily",{1990,1,12},'男'}; 这种结构体变量的初始化形式，只需要在结构体变量的后面加上赋值运算符，将成员项的对应值用一对花括号括起来，放在赋值运算符的后面即可。 四、结构体类型变量的初始化： 15 定义三个学生变量（学生信息，包括学号、姓名、年龄），其中第一个学生信息通过初始化赋值，第二个学生信息成员项依次赋值，第三个学生信息从键盘输入，并分别输出查看。 示例3：结构体变量应用综合示例 一、结构体数组： 当数组中的元素是结构体类型时，就构成了结构体数组。 结构体数组是具有相同结构体类型的变量集合。 8.1.2 结构体数组和结构体指针 结构体数组定义的三种方法： 1.先定义结构体类型，再定义该种类型的数组： struct 结构体名 结构体数组名； 例如： struct object { char name[16]; float high; float weight; }; struct object box[3]; 一.结构体数组 2.定义结构体类型的同时定义结构体变量： struct 结构体名 { 数据类型 成员名1; 数据类型 成员名2; … 数据类型 成员名n; }结构体数组名； 一.结构体数组 3.直接定义结构体类型变量： struct { 数据类型 成员名1; 数据类型 成员名2; … 数据类型 成员名n; }结构体数组名； 一.结构体数组 从键盘输入3个学生的信息，计算每个学生的总分，并输出所有学生的信息和总分。 运行界面如下: 示例4：结构体数组应用综合示例 指向结构体类型变量的指针称为指向结构体的指针或结构体指针。 例如：struct object *op; op为指向结构体变量的指针 结构体指针定义的一般形式： struct 结构体名 * 结构体指针名； 二、结构体指针 访问结构体指针所指向的结构体变量的成员可以采用以下两种方法： 方法1：(*结构体指针名).成员项名 方法2： 结构体指针名->成员项名 例如： (*p).name, (*p).high, (*p).weight 或者 p->name, p->high, p->weight 二、结构体指针 函数的形参与返回值的类型可以是基 本数据类型的变量、指针、数组，也可 以是一个结构体类型。结构体与函数的 关系主要分为3种： 结构体变量作为函数的参数 结构体数组作为函数的参数 函数的返回值为结构体类型 8.1.3 结构体与函数 结构体类型的变量同基本数据类型的变量一样，传递的是各成员的值（值传递）。 在调用函数输入结构体类型的变量的值时，必须通过指针实现地址传递方式。 当函数的参数设为结构体数组。此时参数传递的是结构体数组的首地址，传递方式为地址传递。 8.1.3 结构体与函数 示例5：结构体变量作为函数参数 利用函数从键盘输入3个学生的信息，计算学生成绩总分，并输出学生的信息及总分。 示例6：结构体数组作为函数参数 定义函数getStudent()，功能是从键盘输入所有学生的信息。 定义函数printStudent()，功能是输出所有学生的信息及总分 8.2 链表 大量数据存储时前面基本都采用数组方式。数组又称为顺序存储结构，数组元素按下标顺序依次排列。 优点：快速定位，方便查询。 缺点： 插入、删除需要大量移动元素。 数组内存固定 如何解决-链式存储 节点: 组成链表的基本存储单元。该存储单元有若干个数据和指针,称为数据域和指针域。 数据域：存放每个元素的值。 指针域：存放下一个节点的首地址。 数据域 指针域 节点类型定义: struct 类型名 { 数据域定义; struct 类型名 *指针域名; }; 简单节点 8.2.1 链表的概念 头节点:指向链表中第一个包含有数据的节点,本身并不包含数据. data3 2050 data4 null data1 2000 data2 1010 尾节点:不指向其他结点的节点,其指针域存放的地址为NULL. 1000 2000 1010 2050 1000 head 结点 尾结点 8.2.1 链表的概念 示例：struct student { int num; float score; struct student *next; } 1003 79 1004 92 NULL 1001 88 1002 65 num score next 链表示意图 8.2.1 链表的概念 链表和数组均可用来存放大量的相同数据类型的元素，但在以下几个方面有一定的区别： 数组的元素个数在数组定义时指定，数组长度固定，内存空间大小固定。链表的内存空间分配在执行过程中根据需要动态申请，链表的个数可以根据需要增加或减少。 数组元素的查找通过数组下标和数组首地址确定各元素的地址空间。链表的查找操作必须从第一个结点开始依次查找每个元素。 数组元素中的插入和删除操作必须通过大量移动数据实现。链表的插入和删除仅仅需要改变结点的指针的指向即可。 8.2.1 链表的概念 固定内存分配 : 在C语言中,用说明语句定义的各种存储类型的变量或数组,均由系统分配存储单元,程序员无法在函数的执行时，进行存储单元的分配与释放操作，称为固定内存分配,又称为系统存储分配. 动态内存分配 : C语言允许程序员在函数执行部分的任何地方使用动态存储分配函数开辟或回收存储单元,这样的存储分配形式称为动态存储分配. 8.2.2 链表的实现 链表是一种动态数据结构，因此，链表的内存空间是在执行过程中根据实际需要动态申请的。 一、C语言常用内存管理函数 malloc()函数： 原型：void *malloc(unsigned int size) 功能：在动态存储区中分配大小为size的内存空间，并返回指向该内存空间的首地址。 calloc()函数： 原型：void *calloc(unsigned int n, unsigned int size) 功能：分配n个同一类型的大小为size字节数的连续存储空间。 free()函数：释放指针p所指向的内存空间。 原型： void free(void *p) 8.2.2 链表的实现 二、单链表的操作 单链表：只包含一个指针域的节点组成的链表。 每个单向链表都有一个头节点，对链表的访问都是从头节点开始的，到最后一个节点（不指向其他节点的节点）。 链表的基本操作： 1.建立并初始化链表。 2.遍历访问链表（查找节点、输出节点等）。 3.删除链表中的节点。 4.在链表中插入节点。 8.2.2 链表的实现 1、链表节点的定义 单链表是由若干节点通过指针域的指向连接起来的一个链。每个节点可以包含若干数据项成员和指针域，可以看出，节点应该定义为结构体类型。 二、单链表的创建 struct Student { char no[20]; char name[20]; //数据域 float score; struct Student *next;//指针域 }; 2、链表的创建 链表的建立过程实际上就是不断地在已存在链表的尾部插入元素。每添加一个元素都需要动态分配所需的内存空间，在建立链表的过程中，需要设置3个指针变量。 head：头指针，指向第一个元素结点的首地址。当链表为空时，头指针为NULL。 �p：指向新分配节点内存空间的指针变量。 �tail：尾指针，指向链表的最后一个节点，tail->next为NULL。 二、单链表的创建 （1）建立初始链表（将头指针指向第一个节点的首地址）。 （2）循环地在链表尾部插入新节点。 二、单链表的创建 编写create()函数及print()函数，建立长度为3的学生信息链表并对该链表进行遍历，输出所有学生的信息。 示例7：链表的建立与遍历 1、删除链表中指定的节点 算法分析： 首先找到指定的节点，然后对指定节点进行删除。链表中的节点的删除并不是真正从内存中删除，仅仅是将该节点从链表中分离出来。删除链表中的指定节点需要两个指针变量。 �p：指向当前删除的节点，初始值指向第一个节点。 q：指向被删除节点的前一个节点。 三、单链表的删除与插入 删除实现步骤： a：找到要删除结点的前驱结点。 b：将后继结点的地址赋值给前驱结点的指针域。 c：将要删除的结点空间释放。 三、单链表的删除与插入 data3 2050 data4 null data1 2000 data2 1010 1000 head 结点 尾结点 要删除结点 前驱结点 后继结点 编写函数deleteStudent，删除指定学号的学生。如果找到，删除该学生，并输出查看；找不到，输出该学号的学生不存在。 示例8：链表的删除 2、插入节点到指定的位置 算法分析： 首先动态地分配内存，创建新节点，找到节点插入的位置，然后将已知节点插入指定的位置。插入节点需要用到3个指针变量。 p：指向插入位置当前的节点，初始值指向第一个节点。 q：指向插入位置的前一个节点，初始值指向第一个节点。 t：指向待插入的新分配节点。 三、单链表的删除与插入 data3 2050 data4 null data1 2000 data2 1010 1000 head 结点 尾结点 插入点结点 前驱结点 后继结点 x 1010 待插入结点 三、单链表的删除与插入 插入实现步骤： a：开辟一个新结点，并将数据存入到该结点的数据域。 b：找到插入点结点。 c：将新结点插入到链表中：将插入点结点的地址赋值给新结点的指针域，并将新结点的地址赋值给前驱结点的指针域。 已定义好一个学生链表，要求编写函数insertStudent，插入指定的学生，使其出入后保持学生成绩仍有序排列。 示例9：链表的插入 $$