第3章 线性表的链式存储ppt课件.ppt

《第3章 线性表的链式存储ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章线性表的链式存储主要知识点：●线性表的链式存储结构。●链表中有关概念的含义，如头结点、头指针，首元结点、尾元结点的区别，以及循环链表、双向链表的区别等。●各种链表上实现线性表各种操作的方法即有关算法的设计。●建立利用数据结构知识进行程序设计的思考方式。教学重点与难点重点：顺序表单链表结构的各种基本算法，以及相关的时间性能分析。难点：设计链表结构算法解决线性表相关实际问题。思考问题：1、线性表链式结构特点2、如何利用线性表链式结构的知识解决实际问题，确定线性表链式结构的应用题目。课程任务：线性表链式结构案例理解，完成课程任务

2、设计。1、考核方式：课程报告和程序设计2、作业题目：依据选定的线性表结构实用案例题目，设计完成课程任务。例如：课程任务实例“饮食中心订餐管理系统”。3、作业要求：分析案例实现方法，结合案例设计自己的作业任务。3.1线性表的链式存储结构3.1.1为什么要使用链式存储结构【案例】：饮食中心快餐配送餐管理。图3.1快餐配送信息需求分析：1、不需要事先准备一张足够大的纸；2、每张小纸条写完以后，把这张纸条排列到正确位置时，不会影响到其他的纸条；3、订餐顾客用完餐后，把记录该顾客信息的纸条抽出来销毁（或存档）。4、数据元素之间的逻辑关系为

3、线性关系。3.1线性表的链式存储结构问题思考：1、预定顺序如采用顺序表物理存储结构存在的问题。2、考虑采用链式物理存储结构的解决。3.1.2单链表的数据定义链表的存储特点（参见图3.2）：1、用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的），例如三个订餐顾客的订餐数据信息的存储空间是可以定义在任意的存储区域。2、链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（如图3.2B），三个订餐顾客的订餐

4、数据的逻辑次序与物理存储次序不相同。问题思考：总结链式存储结构的特点数据域指针域结点结构:数据域：存放结点数据信息值，例如订餐顾客数据信息。指针域：存放结点的直接后继的地址（位置）。注意：（1）、链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。（2）、每个结点只有一个链域的链表称为单链表（SingleLinkedList）。单链表定义的一般形式：由分别表示a1,a2,…,an,的n个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故称为单链表或线性链表。3.1.2

5、单链表的数据定义任务1：举例说明为什么要使用链式存储结构。3.1.3静态链的实现静态链表特点：●用数组来存储元素的值和地址。●程序运算过程中，数组元素的个数固定不变。例3-1：饮食中心快餐配送餐管理静态链表存储结构设计（1）存储结构分析（2）存储结构C语言定义如下：定义顾客信息数据类型:typedefstruct{charname[10];/*姓名*/chartime[10];/*时间*/intamount;/*份数*/charadress[17];/*地址*/}ElemType;定义结点类型:typedefstructnode

6、{ElemTypedata;/*数据域*/Intnext;/*指针域*/}SLNode;定义静态单链表：SLNodeletter[100]任务2：静态链表存储结构举例并采用C语言定义使用链表的原因：第一，如果系统不能提供足够大的地址连续的内存空间时，可以考虑使用链表；第二，需要对线性表频繁地进行插入和删除操作时，也考虑使用链表。3.1.4动态链表的实现动态链表结点定义一般形式：typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList

7、;typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList;（1）.定义元素数据类型typedefstruct{charnumber[7];/*序号*/charname[10];/*姓名*/chartime[10];/*时间*/intamount;/*人数*/}ElemType;3.1.4动态链表的实现例3-2：饮食中心快餐配送餐管理动态链表存储结构设计1．存储结构分析：而在C语言程序设计中，可以用malloc函数申请动态变量（存储

8、空间），用free释放变量（存储空间）。动态链表中的结点是以变量形式申请或者释放的。2.订餐顾客信息的动态链类型：（2）.定义链表及结点类型typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针