数据结构(第二章 线性表)ppt课件.ppt

《数据结构(第二章 线性表)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第2章线性表线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。线性结构基本特征：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继。线性结构主要内容2.1线性表抽象数据类型2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用：多项式的表示及运算2.1线性表抽象数据类型线性表的定

2、义线性表是指n(n>=0)个类型相同的数据元素a0,a1,...an-1组成的有限序列，其一般描述为：LinearList=(a0，a1，…，an－1)。其中LinearList称为线性表的名称每个ai（n-1≥i≥0）称为线性表的数据元素，可以是整数、浮点数、字符或类表中相邻元素之间存在着顺序关系：将ai-1称为ai的前驱（Predecessor），ai+1称为ai的后继（Successor）。a0没有前驱元素，an-1没有后继元素具体n的值称为线性表中包含有数据元素的个数，也称为线性表的长度（Lengt

3、h）当n的值等于0时，表示该线性表是空表2.1线性表抽象数据类型线性表的定义线性表的定义中每个数据元素ai的含义在不同情况下各不相同，它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下，在线性表中每个ai描述的是一组相同属性的数据，例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素某公司2015年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素在一些复杂的线性表中，每一个数

4、据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），比如学生信息记录线性表的离散（数学）定义如下：B=,其中A包含n个结点的集合(a0，a1，…，an－1)，R是关系的集合{(ai-1,ai)

5、i=1,2,..n-1}，可见R只有一种类型的关系，即线性关系2.1线性表抽象数据类型线性表的定义2.1线性表抽象数据类型线性表的特征从线性表的定义可以看出线性表的特征：有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点)

6、an-1，它没有直接后继，只有一个直接前驱;其它结点都有一个直接前驱和直接后继；元素之间为一对一的线性关系。线性表的抽象数据类型定义如下：ADTLinearList{数据对象:D＝{ai

7、ai∈元素集合,i=0,1,2,..n-1n>=1}数据关系:R={

8、ai-1,ai∈元素集合,i=1,2,..n-1}基本操作：{插入，删除，查找等}}ADTlist2.1线性表抽象数据类型线性表的抽象数据类型线性表的基本操作求长度：求线性表的数据元素个数。访问：对线性表中指定位置的数据元素进行存取、替

9、换等操作。插入：在线性表指定位置上，插入一个新的数据元素，插入后仍为一个线性表。删除：删除线性表指定位置的数据元素，同时保证更改后的线性表仍然具有线性表的连续性。复制：重新复制一个线性表。合并：将两个或两个以上的线性表合并起来，形成一个新的线性表。查找：在线性表中查找满足某种条件的数据元素。排序：对线性表中的数据元素按关键字值，以递增或递减的次序进行排列。遍历：按次序访问线性表中的所有数据元素，并且每个数据元素恰好访问一次。2.1线性表抽象数据类型线性表的抽象数据类型2.1线性表抽象数据类型线性表的抽象数据

10、类型声明线性表抽象数据类型ADTList//线性表抽象数据类型，数据元素的数据类型为T{booleanisEmpty()//判断线性表是否为空intsize()//返回线性表长度Tget(inti)//返回第i个元素voidset(inti,Tx)//设置第i个元素为xStringtoString()//所有元素的描述字符串intinsert(inti,Tx)//插入x作为第i个元素2.1线性表抽象数据类型线性表的抽象数据类型intinsert(Tx)//在线性表最后插入x元素Tremove(inti

11、)//删除第i个元素voidclear()//删除所有元素intsearch(Tkey)//查找与key相等元素booleancontains(Tkey)//判断是否包含key元素intinsertDifferent(Tx)//插入不重复元素Tremove(Tkey)//删除与key相等元素booleanequals(Objectobj)//比较是否相等voidaddAll(Listlist)//添加lis