数据结构与算法分析2.ppt

第2章 线性表 2.1 线性表类型的定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.3.1 单向链表 2.3.2 单链表的基本运算 2.3.3 循环链表 2.3.4 双链表 2.4 链表应用举例 2.5 顺序表和链表的比较 2.1 线性表类型的定义 线性表是n个数据元素的有限序列。其一般描述为： A=（a1，a2，……an） 其中A称为线性表的名称， 每个ai（n≥i≥1）称为线性表的数据元素，具体n的值含义则称为线性表中包含有数据元素的个数，也称为线性表的长度；当n的值等于0时，表示该线性表是空表。每个数据元素的含义在不同情况下各不相同，它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下，在线性表中每个ai的描述的是一组相同属性的数据。 2.1 线性表类型的定义 线性表的离散定义是：B=A，R，其中A包含n个结点（a1，a2……an）， R只包含一个关系。 R={（ai-1，ai）| I=1，2，……n}，线性表中包含的数据元素个数为线性表的长度。 一个数据元素通常包含多个数据项，此时每个数据元素称为记录，含有大量的记录的线性表称为文件。 在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成。 线性表是一个比较灵活的数据结构，它的长度根据需要增长或缩短，也可以对线性表的数据元素进行不同的操作（如访问数据元素、插入、删除数据元素等）。 2.1 线性表类型的定义 使用抽象数据类型ADT定义线性表如下： ADT list{ 数据对象：D={ai | ai∈元素集合，i=1，2，……n，n≥0} 数据关系：R= {〈ai-1，ai〉 | ai-1，ai∈元素集合，i=1，2，……n} 基本操作： {将以上对线性表的操作搬下来，每个函数注明输入输出} }ADT list 2.2 线性表的顺序表示和实现 线性表的存储结构分为顺序存储和非顺序存储。其中顺序存储也称为向量存储或一维数组存储。 （1）顺序表 线性表的顺序存储，也称为向量存储，又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一致，它叫向量存储（一般指一维数组存储），与此同时对应A=（a1，a2，．．．an ）线性表而言。 实际上，数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为（假设每个数据元素占有c个存储单元）： LOC（ai+1）=LOC（ai）+ c 2.2 线性表的顺序表示和实现 （1）顺序表 对线性表的所有数据元素，假设已知第一个数据元素a1的地址为d1，每个结点占有c个存储单元， 则第i个数据元素ai的地址为： di=d1+（i-1）*c 线性表的第一个数据元素的位置通常称做起始位置或基地址。 线性表的这种机内表示称做线性表的顺序存储结构或顺序映象（Sequential mapping），使用这种存储结构存储的线性表又称做顺序表。其特点是，表中相邻的元素之间具有相邻的存储位置。 在使用一维数组时，数组的下标起始位置根据给定的问题确定，或者根据实际的高级语言的规定确定。 2.2 线性表的顺序表示和实现 （1）顺序表 顺序分配的线性表的可以直接使用一维数组描述为： type arraylist[]；//type的类型根据实际需要确定// 通常用在数组的元素个数不是很多且可以对数组元素“枚举”的情况下。也可以使用符合类型数组的动态进行动态定义。 type arrayname[]； 该代码只是对应用数组的声明，还没有对该数组分配空间，因此不能访问数组。只有对数组进行初始化并申请内存资源后，才能够对数组中元素进行使用和访问。 arrayname= new type[arraysize]； 其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间；其中arraysize表示数组的长度，它可以是整型的常量和变量；如果arraysize是常量，则分配固定大小的空间，如果是变量，则表示根据参数动态分配数组的空间。 2.2 线性表的顺序表示和实现 （2）顺序表基本运算的实现 线性表的顺序存储的结构，容易实现线性表的某些操作，如随机存取第i个数据元素等，但是在插入或删除数据元素时则是比较烦琐，所以顺序存储结构比较适合存取数据元素。应该注意java的数组下标从0开始。下面考虑线性表顺序存储的插入、删除和排序的实现方法。 顺序表的“求表长”和取第i个数据元素的时间复杂度均为O（1），因为可以直接求出线性表的长度，顺序存储下可可以实现随机存取，可以直接取得数据元素，而不需要移动元素。 2.3 线性表的链式存储结构 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此随机存取元素时比较简单，但是这个特点也使得在插入和删