10.3 链表（课件）-《C语言程序设计》同步教学（西安电子科技大学出版社）

C 语言程序设计 2023 翻转课堂实用教程 10.4 链表 1 2 3 链表的链式存储 链表的节点 链表的组织形式 链表的基本操作 知识点 链表案例分析 案例分析 链表相关练习题 练习题 讲解本节的主要内容，方便学生的学习。 前面章节中，学生会候选人、应届毕业生的信息采用什么方式存储？ 若进行删除、插入的操作，会涉及到非常多移动的操作，降低了程序执行的效率。 C 语言提供了一种采用动态存储分配的构造数据类型——链表，大大提高了程序解决此类问题的时间效率。 10.4.1链表知识点 结构体数组的存储方式 优点：便于对信息进行查询、修改、输出操作。 如何更好解决删除、插入的问题？ 链条示意图 10.4.1链表知识点 先看下链条： 由多个金属环串联在一起的 前一个金属环扣住下一个金属环。 链表就是一种链式存储的结构， 由多个相同结构体类型的节点串联一起 节点之间相互关联 链表分为单向链表和双向链表，本节只讲解单向链表。 10.4.1链表知识点 每个节点都是一个结构体类型的变量，两部分组成： ① 节点本身的数据部分，称为数据域； ② 指向下一个节点的指针，称为指针域。 以保存29 47 84 90这4个数据为例。 链表的组织形式——节点 10.4.1链表知识点 例如：定义struct node结构体类型作为链表节点的类型名，定义如下： typedef struct node{ int data; //数据域的值 struct node* next; //指针域的值，next指向下一个链表节点 }Node; typedef用法？ next指针的类型？ 链表的组织形式——节点 data next 讲解typedef用法，以及为什么next的类型为 struct node * 10.4.1链表知识点 （1）头指针，链表一般使用头指针head来表示，方便后续对链表的访问和操作。 （2）节点，节点分为第一个节点和其他节点。 无头节点的单向链表： 带头节点的单向链表： 涉及的概念： 第一个节点，为头结点。 存储第一个实际数据的节点，为首元节点。 最后一个节点称为尾节点，尾节点后续没有节点，其指针域的值为NULL。 链表包括头指针和节点 了解单项链表中涉及的几个概念，对照这个无头节点的单链表来讲解概念。 引入单向链表的分类，分为无头节点的单向链表、带头结点的单向链表 无头节点的单向链表：第一个节点的数据域可以存储第一个实际数据，这样第一个节点便为首元节点 带头节点的单向链表：第一个节点的数据域也可以不存储实际数据，让其指针域指向首元节点，这样的第一个节点便为头节点 10.4.1链表知识点 （1）malloc和free函数 链表中的节点，逻辑上：连续的， 物理上：是随机存放的。 每个节点的内存空间，通过动态存储分配的。使用stdlib.h头文件中函数。 malloc：动态分配内存空间 free：释放用malloc动态分配的内存空间 链表的基本操作 10.4.1链表知识点 （1）malloc和free函数 malloc函数原型如下： void *malloc(unsigned int size); 在动态存储区分配一个大小为size字节的连续空间。 成功：返回分配好的存储空间的首地址； 失败：返回值NULL 链表的基本操作 举例： double *pd = (double *)malloc( sizieof (double)); 1、增加程序可移植性 2、强制转化为需要的类型 10.4.1链表知识点 （1）malloc和free函数 free函数原型如下： void free(void* p); 释放掉指针p指向的内容空间。free函数要和malloc函数成对使用。 链表的基本操作 举例： struct node *curNode = (struct node *)malloc( sizieof (struct node)); … free(curNode); maloc函数申请的空间，不会自动释放。 必须由free函数来释放。 10.4.1链表知识点 （2）单向链表的新建 链表的基本操作 创建单链表，保存29 47 84 90这4个数据。 头结点 head rear 29 首元结点 curNode rear->next 47 rear->next 用图示演示下新建链表的过程，然后再讲解代码 10.4.1链表知识点 //生成含头节点的单向链表 for (i=0; i<N; i++) { //创建新节点curNode，为其动态分配存储