模块十一 链表（ppt）-2022-2023学年高一《C语言程序设计》同步教学

YCF 正版可修改PPT （中职）C语言程序设计模块十一ppt电子课件 1 链表 模块11 LOGO 11.1链表的基本概念及要点 11.1.1链表的基本概念 （1）将若干数据项按一定的原则连接起来的表就称为链表。 （2）链表中的数据称为结点（或节点）。任何结点都由两部分组成： ①数据域（data）。 ②指针域（next）。 （3）链表的链接原则： ①前一个结点指向下一个结点，即前一个结点指针域保存下一个结点地址。 ②只有通过前一个结点才能找到下一个结点。 ① 头结点（也称头指针）一般不存放有效数据，只保存第1个结点的地址。 ② 头结点不存放有效数据，主要是为了方便插入和删除运算的实现。若头结点存放了有效数据，则其为事实上的第1个结点。 ③ 通常把除头结点外的其他结点称为数据结点，第1数据结点也称为首结点。 ④ 通常只对存放实际数据的数据结点进行编号（从1开始）。 11.1链表的基本概念及要点 11.1.1链表的基本概念 （4）头结点是链表的起始结点，结点标号为0。 4 11.1链表的基本概念及要点 11.1.1链表的基本概念 （5）最末结点指针域值为“^”，表示其指针值为空（NULL）。 （6）结点空间由malloc()函数动态获取并进行结点的创建。 （7）头结点是关键点，“抓住”了头结点，就“抓住”了整个链表。 链表示意图如图11-1所示。 图11-1链表 11.1链表的基本概念及要点 11.1.2链表结构的定义及内存空间的申请 struct LNode {int data;/*数据域*/ struct LNode *next;/*指针域*/ }; struct LNode *p,*t; /*定义了两个链表指针*/ p=(struct LNode *)malloc(sizeof(struct LNode));/*申请内存空间*/ t=(struct LNode *)malloc(sizeof(structLNode)); 链表结构（也称结点结构）定义示例。 示例1： 11.1链表的基本概念及要点 11.1.2链表结构的定义及内存空间的申请 typedef struct LNode {int data;/*数据域*/ struct LNode *next;/*指针域*/ }NODE;/*定义了一个链表结构类别名NODE*/ NODE *p,*t; /*用类别名定义两个链表指针*/ p=(NODE *)malloc(sizeof(NODE));/*申请内存空间*/ t=(NODE *)malloc(sizeof(NODE)); 示例2： 11.1链表的基本概念及要点 11.1.3链表的基本操作要点 链表的操作主要靠“->”运算符和指针域来实现。设若有模块11.1.2的示例1和示例2的链表结构，可以做以下简化的理解： （1）左为指针域，右为指向下一个结点： ①“t->next=p->next;”意为把p指向的下一个结点的地址保存到t的指针域。 ②“p=p->next;”意为指针p下移。 （2）当出现双重“->”运算符时： ①“p->next->data=3；”意为把常值3赋给p指向的下一结点的数据域。 ②“p->next->data<t->data;”意为p指向的下一结点的数据域值小于t指向结点的数据域值。 ③“p->next->data>t->next->data;”意为p指向的下一结点的数据域值大于t指向的下一结点的数据域值。 （3）链表操作往往须借助于多个链表指针，单一指针是不可能完成复杂操作的。 11.2单链表 11.2.1单链表的建立——尾插法 所谓尾插法，就是把刚创建的结点插入前一结点之后，最后给最末结点指针域赋空值即可。 为了便于读者学习、理解，在后面的学习中直接把链表指针称为结点，事实上是指针指向结点。 9 11.2单链表 11.2.1单链表的建立——尾插法 【例11-1】学生成绩链表——头结点为第1个数据结点。 #include <stdio.h> #include <malloc.h> struct LNode/*定义链表结构(也可称为结点结构体)，数据域有姓名、班级和成绩*/ {char name［8］; int class; int score［4］］; /*语数外加专业4科成绩*/ struct LNode *next; /*指针域,指针域存放下一个结点的存储位置(指针)*/ }; /*创建链表指针函数，返回链表指针，实际上是返回链表的头指针*/ struct LNode *create(int n) {struct LNode *h,*p,*t; /*链表的创建一般来说需3个链表指针，一个头（如h），一个尾（如t），一个动态指针（如p），用于动态获取内存空间*/ 11.2单链表 11.2.1单链表