资源描述：
《java版数据结构 第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章线性表教学目标：掌握线性表的基本概念掌握顺序表和链表的存储原理线性表的应用重点：线性表的存储难点：线性表的操作及其应用线性表的基本概念线性表是最简单也是最常用的一种线性结构。线性表的定义：线性表是由同一类型数据元素组成的有限序列。其中第一个元素无前驱结点，最后一个元素无后继结点，除第一个和最后一个元素外其余元素均有且仅有一个直接前驱和直接后继结点。线性表的基本概念线性表中元素的个数称为该表的长度，如果长度值为0则称表为空表。线性表常见操作有插入、删除、查找、修改等操作。线性表的逻辑结构线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成
2、的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。A=(a1,a2,…,ai,ai+1,…,an)(n≧0)，其中称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表的逻辑结构线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。线性表中的结点可以是单值元素(每个元素只有一个数据项)。线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。线性表的逻辑结构例1:26个英文字母组成的字母表：(
3、A，B，C、…、Z）例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188）例3：一副扑克的点数(2，3，4，…，J，Q，K，A)例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)…，(‘2001414103’，‘李利辣’，‘女’，08/12/1984)}若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。对
4、线性表的数据元素可以访问、插入和删除。线性表的抽象数据类型定义ADTList{数据对象：D={ai
5、ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R={
6、ai-1,ai∈D,i=2,3,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L；length(L)初始条件：线性表L已存在；操作结果：返回表L中元素的个数；query(L,i,&e)初始条件：线性表L存在，1≦i≦ListLength(L)；操作结果：用e返回L中第i个数据元素的值；Insert(L,i,e)初始条件：线性表L存在，1≦i≦ListLength(L)+1
7、；操作结果：在线性表L中的第i个位置插入元素e；……}ADTList线性表基本操作isEmptylengthinsertdeletequery线性表的存储结构分为顺序存储结构和链式存储结构：顺序存储结构：顺序表链式存储结构：链表顺序表定义：顺序表是指按顺序存储结构存储的线性表，顺序表中的结点在内存中占用一段连续的存储单元。顺序表存储结构如图所示：Loc(ai)=add+(i-1)len(1≤i≤n)顺序表定义实例学生表的结构如下2.1.2顺序表定义实例学生表的顺序表抽象定义：ADTList{//List为线性表名，ADT为abstrctdatatype的缩写数据元素如下：Dat
8、e={ai
9、i=1,2,……,n(n≧0)}//表数据元素的描述数据元素关系如下：Relation={
10、ai,ai+1∈Date}//表元素间关系描述表基本操作如下：//表的基本操作booleanisEmpty(Listls)//判断表ls是否为空表，空表返回true,否则返回falseintlength(Listls)//返回表ls的元素的个数，即表的长度insert(Listls,inti,Typedata)//在表ls的第i个位置前插入新数据元素dataTypedelete(Listls,inti)//删除表ls第i个位置的数据元素，并返回该数据元素Ty
11、pequery(Listls,inti)//查找表ls第i个位置的数据元素，并返回该数据元素}线性表的插入操作在线性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：L=(a1，…ai-1，e，ai，ai+1，…，an)实现步骤：(1)将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。(3)线性表长度加1。顺序表的插入（insert(i,obj)）例在张阳同学前插入郑克龙学生信息的学生表如下图
