java版数据结构 第2章 线性表

第二章 线性表,教学目标：掌握线性表的基本概念掌握顺序表和链表的存储原理线性表的应用重点：线性表的存储难点：线性表的操作及其应用,线性表的基本概念,线性表是最简单也是最常用的一种线性结构 。 线性表的定义：线性表是由同一类型数据元素组成的有限序列。其中第一个元素无前驱结点，最后一个元素无后继结点，除第一个和最后一个元素外其余元素均有且仅有一个直接前驱和直接后继结点。,线性表的基本概念,线性表中元素的个数称为该表的长度，如果长度值为0则称表为空表。线性表常见操作有插入、删除、查找、修改等操作。,线性表的逻辑结构,线性表(Linear List) ：是由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。A=(a1,a2,ai,ai+1,an) (n0)，其中称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。,线性表的逻辑结构,线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。线性表中的结点可以是单值元素(每个元素只有一个数据项) 。线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。,线性表的逻辑结构,例1: 26个英文字母组成的字母表： (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) ,若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 对线性表的数据元素可以访问、插入和删除。,线性表的抽象数据类型定义,ADT List数据对象：D = ai | aiElemSet, i=1,2,n, n0 数据关系：R = | ai-1, aiD, i=2,3,n 基本操作：InitList( &L )操作结果：构造一个空的线性表L；,length( L )初始条件：线性表L已存在；操作结果：返回表L中元素的个数；query( L, i, &e )初始条件：线性表L存在，1iListLength(L)；操作结果：用e返回L中第i个数据元素的值；Insert ( L, i, e )初始条件：线性表L存在，1iListLength(L)+1 ；操作结果：在线性表L中的第i个位置插入元素e； ADT List,线性表基本操作,isEmptylengthinsertdeletequery,线性表的存储结构,分为顺序存储结构和链式存储结构：顺序存储结构：顺序表链式存储结构：链表,顺序表,定义：顺序表是指按顺序存储结构存储的线性表，顺序表中的结点在内存中占用一段连续的存储单元。,顺序表存储结构如图所示：,Loc(ai)=add+(i-1)len (1in),顺序表定义实例,学生表的结构如下,2. 1.2顺序表定义实例,学生表的顺序表抽象定义：,ADT List/List为线性表名，ADT为abstrct data type的缩写 数据元素如下：Date=ai|i=1,2,n(n0)/表数据元素的描述 数据元素关系如下：Relation=|ai,ai+1Date/表元素间关系描述 表基本操作如下：/表的基本操作 boolean isEmpty(List ls)/判断表ls是否为空表，空表返回true,否则返回false int length(List ls)/返回表ls的元素的个数，即表的长度 insert(List ls,int i,Type data)/在表ls的第i个位置前插入新数据元素data Type delete(List ls,int i)/删除表ls第i个位置的数据元素，并返回该数据元素 Type query(List ls,int i)/查找表ls第i个位置的数据元素，并返回该数据元素,线性表的插入操作,在线性表 L= (a1，a i-1，ai， ai+1，an) 中的第i(1in)个位置上插入一个新结点e，使其成为线性表： L=(a1，a i-1，e，ai，ai+1，an) 实现步骤：(1) 将线性表L中的第i个至第n个结点后移一个位置。(2) 将结点e插入到结点ai-1之后。 (3) 线性表长度加1。,顺序表的插入（ insert(i, obj) ）,例在张阳同学前插入郑克龙学生信息的学生表如下图所示：,插入操作时间复杂度分析,时间复杂度分析： 在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。,插入操作时间复杂度分析,设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。总的平均移动次数： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。,插入操作时间复杂度分析,即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。,顺序表的删除,在线性表 L=(a1，a i-1，ai， ai+1，an) 中删除结点ai(1in)，使其成为线性表： L= (a1，ai-1，ai+1，an) 实现步骤：(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。(2) 线性表长度减1。,顺序表的删除（ delete(i) ）,删除王丽同学节点后的学生表如下图所示：,删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。,删除操作时间复杂度分析,设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。则总的平均移动次数： Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。,插入操作时间复杂度分析,即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。,插入操作时间复杂度分析,顺序表类 LineList代码 类包含成员变量和成员函数。成员变量用来表示抽象数据类型中定义的数据集合，成员函数用来表示抽象数据类型中定义的操作集合。,顺序表类的三个成员变量,data：存储数据元素的数组length：表示数组中当前存储的数据元素个数maxLength：表示数组允许的最大数据元素个数要求必须满足size<=maxSize,构造函数,public LineList()initiate(10);public LineList(int size)initiate(size);public void initiate(int size)maxLength=size;data=new ObjectmaxLength;length=0;,isEmpty,public boolean isEmpty()if (length=0)return true;elsereturn false;,query(int i),public Object query(int i)return datai-1;,length(),public int length()return length;,insert(int i,Object obj),public boolean insert(int i,Object obj)if (ilength+1)System.out.println("插入位置有误！");return false;for (int n=length-1;n>=i-1;n-)datan+1=datan;datai-1=obj;length+;return true;,delete(int i),public Object delete(int i)if (ilength)System.out.println("删除位置有误！");return null;Object temp=datai-1;for (int n=i;n<length;n+)datan-1=datan;datalength-1=null;length-;return temp;,2.2.2 链表：,链表：按链式存储结构存储的线性表。 链表是指线性表中的结点在内存中随机存放，即存储单元可以连续也可以不连续，因此为了保持链表中各结点逻辑相邻的关系，需要在各结点在存放值的同时还要存放下一个结点的地址。单链表：构成链表的每个结点只有一个指向直接后继结点的指针。,链表：,头结点：若第一个结点仅表示链表的起始位置，而无任何值和意义，则称为头结点。,data,链表：,链表中结点要用两个区域，一个表示结点数据信息，称为数据域，一个表示当前结点的后继结点的引用，称为地址域。,链表：,public class Node /节点类Student stu;/节点数据为学生对象Node next;/后继节点的地址,public class Node /节点类Object obj;/节点数据可以为任何对象Node next;/后继节点的地址,链表操作,链式结构存储对应的链表的建立和该表中数据元素的插入、删除、查找等运算的实现。链表中插入、删除、查找操作思想如下： 判断链表是否空表 ，表为空表，则链表除头结点外无其他结点 。在链表中某位置插入新节点，有以下两个操作：（1）找到插入前位置（2）插入新节点.例如在第i个位置前插入新节点node 在链表中删除某位置节点，有以下两个操作：（1）找到删除位置（2）删除对应位置节点.例如删除第i个位置节点。在链表中查找某位置节点，则链表第一个位置开始不断向下遍历链表，直到查找位置结束，返回查找结点。,在单链表非第一个结点前插入结点过程,图在带头结点单链表第一个结点前插入结点过程,单链表类 LinkedList代码 单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。,单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。,结点类,Node代码,public class Node Object element; /数据域Node next; /地址域public Node() element=null; next=null;public Node(Node nextNode) element=null; next=nextNode;public Node(Object obj) element=obj; next=null;public Node(Object obj,Node nextNode) element=obj; next=nextNode;,