资源描述：
《数据结构java版第三版第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、詹华蕊zhan.huarui@163.com数据结构与算法DATASTRUCTURE ANDARITHMETIC复习回顾上节课我们学习了：数据结构中常用的基本概念和术语算法描述和分析方法通过上节课的学习，我们对数据、数据元素、数据结构等基本概念，以及算法的描述和算法的时间复杂度分析已经有了一个初步的掌握。21数据结构的基本概念什么是数据、数据元素、数据项和关键字？它们之间是怎样的关系？什么是数据结构？数据结构概念包括哪三部分？数据的逻辑结构主要有哪三种？各有何特点？三者之间存在怎样的联系？数据的存储结构主要有哪些？各有何特点？31数据结构的基本概念42算法什么是
2、算法？怎样描述算法？怎样衡量算法的性能？5第二章线性表6本章的重点内容线性表的相关概念线性表的顺序存储结构线性表的链式存储结构链表应用顺序表和链表的比较7本章的重点内容线性表的相关概念线性表的顺序存储结构线性表的链式存储结构链表应用顺序表和链表的比较81、线性表（Linearlist）的定义线性表是指n(n>=0)个相同类型的数据元素a0,a1,...an-1所构成的有限且有序的序列，其一般描述为：LinearList=（a0,a1,……an-1）其中LinearList称为线性表的名称每个ai（n-1≥i≥0）称为线性表的数据元素表中相邻元素之间存在着顺序关系
3、：将ai-1称为ai的直接前趋，ai+1称为ai的直接后继具体n的值称为线性表中包含有数据元素的个数，也称为线性表的长度当n的值等于0时，表示该线性表是空表9线性表的定义每个数据元素ai(0≤i≤n-1)只是一个抽象的符号，其具体含义在不同的情况下可以不同。它们可能是一个字母、一个数字、也可以是一条记录等。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）10…….…….…….……..……..神经衰弱17男790634张立立健康21男790633刘建平一
4、般20女790632陈红健康18男790631王小林健康情况年龄性别学号姓名例3、学生健康情况登记表如下：线性表的定义11线性表的定义线性表的离散定义如下：B=,其中A包含n个结点的集合(a0,a1,…an-1)，R是关系的集合{(ai-1,ai)
5、i=0,1,..n-1}，可见R只有一个关系，即线性关系。12线性表的定义线性表的抽象数据类型定义如下：ADTlist{数据对象:D＝{ai
6、ai∈元素集合,i=0,1,..n-1n>=0}数据关系:R={(ai-1,ai)
7、ai-1,ai∈元素集合,i=0,2,..n-1}基本操作：{插入，删除，查找等}
8、}ADTlist13从实例及线性表的定义可以看出线性表的特征：有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱;其它结点都有一个直接前驱和直接后继；元素之间为一对一的线性关系。线性表的特征线性表是一种典型的线性结构。14线性表的主要操作有如下几种：1．linklist()初始化：构造一个空的线性表。2．insert(index,element)插入：在给定的线性表中，在第index个元素后插入数据元素element。线性表长度加1。3．remove(index)删除
9、：在给定的线性表中，删除第index个元素。线性表的长度减1。4．index(x)查找定位：对给定的值x，若线性表中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。线性表的主要操作155．size()求长度：对给定的线性表，返回线性表的数据元素的个数。6．get(index)存取：对给定的线性表，返回第index（0≤index≤Length(L)-1）个数据元素，否则返回Null。7．Traverse(L)遍历：对给定的线性表L，依次输出L的每一个数据元素。8．Copy(L,C)复制：将给定的线性表L复制到线性表C中。9
10、．Merge(A,B,C)合并：将给定的线性表A和B合并为线性表C。线性表的主要操作16线性表的分类数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。线性表有两种存储方式，对应地把线性表分成了两类：顺序存储结构的顺序表（或称向量存储、一维数组存储）链式存储结构的链表17本章的重点内容线性表的相关概念线性表的顺序存储结构线性表的链式存储结构链表应用顺序表和链表的比较182、顺序表（SequentialList）的定义顺序存储方法：即用一组连续的存储单元顺序存储线性表中的元素在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表
11、的长度，然后让线性表中第
