资源描述：
《第2章 线性表及线性表的顺序存储 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表及线性表的顺序存储问题思考：1、什么是线性表2、线性表结构特点3、如何利用线性表结构的知识解决实际问题，确定线性表逻辑结构的应用题目。上机：线性表结构案例理解，完成课程设计报告。考核方式：课程报告作业题目：依据选定的线性表结构实用案例题目，设计完成题目。例如：课程任务实例“学生名册信息管理“。主要知识点●线性表的定义、线性表中数据元素之间的逻辑关系，以及计算机中顺序存储结构。●顺序存储结构物理结构的C语言描述方法、特点，采用程序设计语言实现线性表结构基本操作，在实际应用中选用适合的线性表物理结构。●能够从时间和空间复杂
2、度的角度比较线性表不同存储结构的特点以及使用场合。教学重点与难点重点：熟练掌握顺序表的各种基本算法，以及相关的时间性能分析。难点：根据本章基本知识设计设计有效算法解决线性表相关实际问题。2.1线性表的定义2.1.1线性表实例案例：学生名册信息管理，数据信息特征由姓名、学院、所在专业、学号表示。需求分析：1、需要准备一张大小适当的记录纸。2、登记在册学生情况。3、取消登记（已调转）。4、将记录销毁或存档。表2.1学生名册表姓名学院所在专业学号聂洪波应院计算机20097554李豆豆应院计算机20097550王晓雪应院计算机200975
3、70肖瑶应院计算机20097585…2.1线性表的定义数据关系分析：学生名册数据表是（“聂洪波”，“李豆豆”，“王晓雪”，“肖瑶”)数据表三元组表示：名册表=(D,R,F)数据集合：D={“聂洪波”，“李豆豆”，“王晓雪”，“肖瑶”};数据关系集合：R={<“聂洪波”，“李豆豆”>,<“李豆豆”，“王晓雪”>,<“王晓雪”，“肖瑶”>}数据关系表示：聂洪波->李豆豆->王晓雪->肖瑶2.1.1线性表实例2.1.1线性表实例任务操作分析F的集合：创建一个空的线性表（准备一张白纸）插入一个新的元素（书写一个新学生的信息）删除一个元素（
4、划掉一个调转的学生的信息）查找指定的元素（在划掉的信息之前，需要查找有关的信息是否存在）清空线性表（将纸张销毁或存档）2.1.2线性表的定义线性表（LinearList）的定义：线性表是具有相同类型的n个数据元素组成的有限序列，通常记为(a1，a2，…ai-1，ai，ai+1，…an)。其中，ai是表中元素，n是表的长度，当n=0时线性表为空表。当n≠0时，a1是第一个元素，也称为表头元素，an是最后一个元素，也称为表尾元素。a1是a2的直接前驱元素，a2是a3的直接前驱元素，而a2是a1的直接后继元素，a3是a2的直接后继元素。
5、从集合论的观点出发，线性表是由三个集合构成的一个三元组。LinearList=(D,R,F)其中，D={ai
6、ai∈ElemSet,i=1,2,…,nn≥1}R={
7、ai,ai+1i∈D,i=1,2,…，n}F={操作1，操作2，操作3，…}Elemset为某一数据对象集；n为线性表的长度。n=0时，线性表为空表。2.1.2线性表的定义表2.1所示的学生名册表是一个线性表，其数据元素是由姓名、学院、所在专业、学号四个数据项构成，是复杂的结构类型。由26个英文字母构成的表（a,b,c,…,z）是一个线性表；由学生成
8、绩构成的表（99,100,88,76,89,56,96,98）是线性表。2.1.2线性表的定义表2.1学生名册表姓名学院所在专业学号聂洪波应院计算机20097554李豆豆应院计算机20097550王晓雪应院计算机20097570肖瑶应院计算机20097585…2.1线性表的定义2.1.3线性表的基本操作及基本运算的描述线性表的基本操作包括：1、创建空的线性表；2、求线性表的长度；3、插入一个新的元素；4、删除一个元素；5、求指定元素的位置6、查找指定的元素；7、清空线性表。(1)InitList(l)，初始化创建空的线性表线性表l
9、。(2)ListLength(l)，求线性表l的长度。(3)InsList(l,i,e)，在l中第i个元素(位置)之前插入数据元素e。(4)DelList(l,i)，删除l中的第i个数据元素。(5)Locate(l,e)，求线性表l中元素e的位置。(6)GetData(l,i)，返回线性表l中第i个元素的值。(7)EmptyList(l)，判断线性表l是否为空表，如果l为空表则返回1，否则返回0。线性表基本运算的描述注意：以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有待确
10、定了存储结构之后才考虑。2.1.3线性表的基本操作及基本运算的描述2.1线性表的定义及运算问题思考:（1）线性表的基本运算与实用任务案例功能需求的关系。（2）如何采用C语言程序设计实现线性表的基本运算。任务2-1：结合案例选定的线性表结构实用题目，
