《工学线性表》ppt课件

《《工学线性表》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表基本知识点：线性表的逻辑结构特点，线性表的两种存储结构以及在这两种存储结构下线性表基本运算的实现算法，顺序表与链表的优缺点比较。线性结构是一个数据元素的有限序列重点：掌握线性表的定义和特点，线性表的存储结构，顺序表和链表的组织方法和相关算法设计。难点：在单、双链表上的各种复杂算法设计。有序（次序）表，不是值有序第二章线性表考纲要求1.线性表的定义和基本操作2.线性表的实现:顺序存储结构链式存储结构线性表的应用第二章线性表考纲分析本章虽然讨论的是线性表，但涉及的许多问题具有一定的普遍性。因此，本章是本课

2、程的重点之一，也是其他后续章节的重要基础。换言之，本章是必考内容，而且可能会结合后续章节的相关内容出题。本章要求：线性表本章要求：1.识记线性表的相关概念，如前驱、后继、表长、空表、头指针、尾标志、头结点、开始结点（首结点）、终端结点（尾结点）等，理解开始结点、头结点和头指针三者之间的关系。2.掌握线性表的两种基本的存储方法（顺序表和单链表），两者优缺点的比较，各自适用的场合。3.掌握顺序表的随机存取特性、插入和删除算法及其时间性能分析。4.熟练掌握常用链表（单链表、循环单链表、双链表、循环双链表）的特点和基本操

3、作（查找、插入、删除）的实现。5.理解静态链表及其特点，静态链表与顺序表和链表的相同及不同之处。6.线性表的应用要求能够灵活运用线性表的存储结构和各种操作，例如多项式的表示和运算、集合的表示和运算等。顺序表的运算本质上是对数组进行操作，因此，可能会与排序、查找等内容结合出题。单链表由于结构简单、灵活应用、难度适中，是数据结构各类考试的重要考点，所以一定要深刻理解、熟练掌握、灵活运用。线性表的逻辑结构考核知识点1.线性表的定义(★)线性表简称为表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性

4、表的长度，长度等于零时称为空表。【说明】：线性表中的数据元素具有抽象（即不确定）的数据类型，在设计具体的应用程序时，数据元素的抽象类型将被具体的数据类型所取代。线性表的逻辑结构考核知识点2.线性表的逻辑关系(★★)在一个非空表L=（a1，a2,……an）中，任意一对相邻的数据元素ai-1和ai之间(1

5、内容比较简单，只需注意线性表的定义和逻辑特征。线性表的逻辑结构典型题解析选择题1：线性表是具有n个（）的有限序列。A．数据B．字符C．数据元素D．数据项【解答】C【分析】数据的逻辑结构是指数据元素之间逻辑关系的整体。线性表中数据元素之间的逻辑关系是线性的。线性表的逻辑结构典型题解析选择题2：线性表是（）A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空【解答】A【分析】:本课程涉及的所有数据结构都是对有限数据进行讨论：线性表可以为空表，即表中可以没有数据元素。

6、线性表的逻辑结构典型题解析选择题3：关于线性表，下列说法中正确的是（）。A．线性表中每个元素都有一个直接前驱和一个直接后继；B．线性表中的数据元素可以具有不同的数据类型；C．线性表中数据元素的类型是确定的；D．线性表中任意一对相邻的数据元素之间存在序偶关系；【解答】D【分析】线性表的第一个元素无前驱，最后一个元素无后继；线性表中的数据元素具有抽象（即不确定）的数据类型，但要求同一线性表中的数据元素具有相同的数据类型。线性表的逻辑结构典型题解析选择题4：()是一个线性表A．由n个实数组成的集合B．由所有实数组成的集

7、合C．由所有整数组成的序列D．由n个字符组成的序列【解答】D【分析】备选答案A和B的逻辑结构是集合，备选答案C的元素个数是无限的。线性表的顺序存储结构及其实现考核知识点1.顺序表的存储方法(★★★)线性表的顺序存储结构称为顺序表。顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。【说明】注意存储要点：连续空间、依次存储。线性表的顺序存储结构及其实现考核知识点2.顺序表的存储结构定义(★★★)顺序表通常用一维数组实现，也就是把线性表中相邻的元素存储在数组中相邻的位置，从而导致了数据元素的序号和存放它的数组下

8、标之间的一一对应关系。用MaxSize表示数组的长度。顺序表的存储结构定义如下：#defineMaxSize100typedefstruct{ElemTypedata[MaxSize];//ElemType表示不确定的类型intlength;//length是顺序表的长度}SeqList;【说明】：注意“数组”的长度和“线性表”的长度的区别。数组的长度是存放线性表的数组空