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

《java版数据结构 第2章 线性表.ppt》由会员分享，可在线阅读，更多相关《java版数据结构 第2章 线性表.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 线性表教学目标：教学目标：l掌握线性表的基本概念掌握线性表的基本概念l掌握顺序表和链表的存储原理掌握顺序表和链表的存储原理l线性表的应用线性表的应用重点：重点：l线性表的存储线性表的存储难点：难点：l线性表的操作及其应用线性表的操作及其应用线性表线性表的的基本概念基本概念线性表是最简单也是最常用的一种线性结构线性表是最简单也是最常用的一种线性结构。线性表的线性表的定义：定义：线性表是由同一类型数据元线性表是由同一类型数据元素组成的有限序列。其中第一个元素无前驱结点，素组成的有限序列。其中第一个元素无前驱结点，最后一个元素无后继结点，除第一个和最后一个最后一个元素无后继结点，除第一个和最

2、后一个元素外其余元素均有且仅有一个直接前驱和直接元素外其余元素均有且仅有一个直接前驱和直接后继结点。后继结点。线性表线性表的的基本概念基本概念线性表中元素的个数称为该表的长度，线性表中元素的个数称为该表的长度，如果长度值为如果长度值为0则称表为空表。则称表为空表。线性表常见操作有插入、删除、查找、线性表常见操作有插入、删除、查找、修改等操作。修改等操作。线性表的逻辑结构 线性表线性表(Linear List)：是由：是由n(n 0)个数个数据元素据元素(结点结点)a1，a2，an组成的有限序组成的有限序列。该序列中的所有结点具有相同的数据类列。该序列中的所有结点具有相同的数据类型。其中数据元素

3、的个数型。其中数据元素的个数n称为线性表的长度。称为线性表的长度。A=(a1,a2,ai,ai+1,an)(n 0)，其，其中称中称ai是是ai+1的直接前驱元素，的直接前驱元素，ai+1是是ai的直的直接后继元素。接后继元素。线性表的逻辑结构 线性表中的数据元素线性表中的数据元素ai所代表的具体含义所代表的具体含义随具体应用的不同而不同，在线性表的定义中，随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。只不过是一个抽象的表示符号。l线性表中的结点可以是线性表中的结点可以是单值元素单值元素(每个元素每个元素只有一个数据项只有一个数据项)。l线性表中的结点可以是线性表中的结

4、点可以是记录型记录型元素，每个元元素，每个元素含有多个数据项素含有多个数据项，每个项称为结点的一个，每个项称为结点的一个域域。每个元素有一个可以唯一标识每个结点。每个元素有一个可以唯一标识每个结点的的数据项组数据项组，称为，称为关键字关键字。线性表的逻辑结构例例1:26个英文字母组成的字母表：个英文字母组成的字母表：(A，B，C、Z）例例2：某校从某校从1978年到年到1983年各种型号的计年各种型号的计算机拥有量的变化情况：算机拥有量的变化情况：(6，17，28，50，92，188）例例3：一副扑克的点数一副扑克的点数 (2，3，4，J，Q，K，A)例例4 4：某校某校20012001级同学

5、的基本情况：级同学的基本情况：(20014141012001414101，张里户张里户，男男，06/24/1983)06/24/1983)，(20014141022001414102，张化司张化司，男男，08/12/1984)08/12/1984)，(20014141032001414103，李利辣李利辣，女女，08/12/1984)08/12/1984)l 若线性表中的结点是按值若线性表中的结点是按值(或按关键字值或按关键字值)由小到大由小到大(或由大到小或由大到小)排列的，称线性表是有排列的，称线性表是有序的。序的。l 线性表是一种相当灵活的数据结构，其长线性表是一种相当灵活的数据结构，其

6、长度可根据需要增长或缩短。度可根据需要增长或缩短。l 对线性表的数据元素可以访问、插入和删对线性表的数据元素可以访问、插入和删除。除。线性表的抽象数据类型定义ADT Listl数据对象：数据对象：D=ai|ai ElemSet,i=1,2,n,n 0 l数据关系：数据关系：R=|ai-1,ai D,i=2,3,n l基本操作：基本操作：lInitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L；llength(L)初始条件：线性表初始条件：线性表L已存在；已存在；操作结果：返回表操作结果：返回表L中元素的个数；中元素的个数；lquery(L,i,&e)初始条件：线性表

7、初始条件：线性表L存在，存在，1 i ListLength(L)；操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值；个数据元素的值；lInsert(L,i,e)初始条件：线性表初始条件：线性表L存在，存在，1 i ListLength(L)+1；操作结果：在线性表操作结果：在线性表L中的第中的第i个位置插入元素个位置插入元素e；l ADT List线性表基本操作isEmptylengthinsertdeletequery线性表的存储结构分为顺序存储结构和链式存储结构：分为顺序存储结构和链式存储结构：l顺序存储结构：顺序表顺序存储结构：顺序表l链式存储结构：链表链式存储结构：链表顺序

8、表定义：定义：顺顺序表是指按序表是指按顺顺序存序存储结储结构存构存储储的的线线性表，性表，顺顺序表中的序表中的结结点在内存中占用一段点在内存中占用一段连连续续的存的存储单储单元。元。顺序表顺序表存储结存储结构如图构如图所示：所示：Loc(ai)=add+(i-1)len (1in)顺序表定义实例学生表的结构如下学生表的结构如下 2.1.2顺序表定义实例学生表的顺序表抽象定义：学生表的顺序表抽象定义：ADT List/List为线性表名，为线性表名，ADT为为abstrct data type的缩写的缩写 数据元素如下：数据元素如下：Date=ai|i=1,2,n(n 0)/表数据元素的描述表数

9、据元素的描述 数据元素关系如下：数据元素关系如下：Relation=|ai,ai+1 Date/表元素间关系描述表元素间关系描述 表基本操作如下：表基本操作如下：/表的基本操作表的基本操作 boolean isEmpty(List ls)/判断表判断表ls是否为空表，空表返回是否为空表，空表返回true,否则返回否则返回false int length(List ls)/返回表返回表ls的元素的个数，即表的长度的元素的个数，即表的长度 insert(List ls,int i,Type data)/在表在表ls的第的第i个位置前插入新数据元素个位置前插入新数据元素data Type delet

10、e(List ls,int i)/删除表删除表ls第第i个位置的数据元素，并返回该数据元素个位置的数据元素，并返回该数据元素 Type query(List ls,int i)/查找表查找表ls第第i个位置的数据元素，并返回该数据元素个位置的数据元素，并返回该数据元素 线性表的插入操作在线性表在线性表 L=(a1，a i-1，ai，ai+1，an)中中的第的第i(1 i n)个位置上插入一个新结点个位置上插入一个新结点e，使其，使其成为线性表成为线性表：L=(a1，a i-1，e，ai，ai+1，an)实现步骤：实现步骤：(1)(1)将线性表将线性表L中的中的第第i个至第个至第n个结点后移一个

11、个结点后移一个位置。位置。(2)(2)将结点将结点e插入到结点插入到结点ai-1之后之后。(3)(3)线性表长度加线性表长度加1。顺序表的插入（insert(i,obj)）例在张阳同学前插入郑克龙学生信息的学生表如下图所示：插入操作时间复杂度分析时间复杂度分析：时间复杂度分析：在线性表在线性表L中的中的第第i个个元素之前插入新结点，元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。可用结点的移动来估计算法的时间复杂度。插入操作时间复杂度分析 设设在线性表在线性表L中的中的第第i个个元素之前插入结点的

12、元素之前插入结点的概率为概率为Pi，不失一般性，设各个位置插入是等概率，不失一般性，设各个位置插入是等概率，则则Pi=1/(n+1)，而插入时移动结点的次数为，而插入时移动结点的次数为n-i+1。总的平均移动次数：总的平均移动次数：Einsert=pi*(n-i+1)(1 i n)Einsert=n/2。插入操作时间复杂度分析 即即在顺序表上做插入运算，平均要移动表上在顺序表上做插入运算，平均要移动表上一半结点。当表长一半结点。当表长n较大时，算法的效率相当低。较大时，算法的效率相当低。因此算法的平均时间复杂度为因此算法的平均时间复杂度为O(n)。顺序表的删除在线性表在线性表 L=(a1，a

13、i-1，ai，ai+1，an)中删除结点中删除结点ai(1 i n)，使其成为线性表，使其成为线性表：L=(a1，ai-1，ai+1，an)实现步骤：实现步骤：(1)(1)将线性表将线性表L中的中的第第i+1个至第个至第n个结点依个结点依此向前移动一个位置。此向前移动一个位置。(2)(2)线性表长度减线性表长度减1。顺序表的删除（delete(i)）删除王丽同学节点后的学生表如下图所示：删除线性表删除线性表L中的中的第第i个个元素，其时间元素，其时间主要耗费在表中结点的移动操作上，因此，主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。可用结点的移动来估计算法的时间复

14、杂度。删除操作时间复杂度分析 设设在线性表在线性表L中中删除第删除第i个个元素的概率为元素的概率为Pi，不失一般性，设删除各个位置是等概率，不失一般性，设删除各个位置是等概率，则则Pi=1/n，而删除时移动结点的次数为，而删除时移动结点的次数为n-i。则总的平均移动次数：则总的平均移动次数：Edelete=pi*(n-i)(1 i n)Edelete=(n-1)/2。插入操作时间复杂度分析 即即在顺序表上做删除运算，平均要移动在顺序表上做删除运算，平均要移动表上一半结点。当表长表上一半结点。当表长n较大时，算法的效较大时，算法的效率相当低。因此算法的平均时间复杂度为率相当低。因此算法的平均时间

15、复杂度为O(n)。插入操作时间复杂度分析顺序表类顺序表类 LineList代码代码 类包含成员变量和成员函数。成员变量用类包含成员变量和成员函数。成员变量用来表示抽象数据类型中定义的数据集合，成来表示抽象数据类型中定义的数据集合，成员函数用来表示抽象数据类型中定义的操作员函数用来表示抽象数据类型中定义的操作集合。集合。顺序表类的三个成员变量data：存储数据元素的数组：存储数据元素的数组length：表示数组中当前存储的数据元素个数：表示数组中当前存储的数据元素个数maxLength：表示数组允许的最大数据元素个数：表示数组允许的最大数据元素个数要求必须满足要求必须满足size=maxSize

16、构造函数public LineList()initiate(10);public LineList(int size)initiate(size);public void initiate(int size)maxLength=size;data=new ObjectmaxLength;length=0;isEmptypublic boolean isEmpty()if(length=0)return true;elsereturn false;query(int i)public Object query(int i)return datai-1;length()public int len

17、gth()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(删除位置有误！删除位置有误

18、！);return null;Object temp=datai-1;for(int n=i;nlength;n+)datan-1=datan;datalength-1=null;length-;return temp;2.2.2 链表：链表：按链式存储结构存储的线性表。链表：按链式存储结构存储的线性表。链表是指线性表中的结点在内存中随机存放，链表是指线性表中的结点在内存中随机存放，即存储单元可以连续也可以不连续，因此为了即存储单元可以连续也可以不连续，因此为了保持链表中各结点逻辑相邻的关系，需要在各保持链表中各结点逻辑相邻的关系，需要在各结点在存放值的同时还要存放下一个结点的地结点在存放值的

19、同时还要存放下一个结点的地址。址。单链表：构成链表的每个结点只有一个指向直单链表：构成链表的每个结点只有一个指向直接后继结点的指针。接后继结点的指针。链表：头结点：若第一个结点仅表示链表的头结点：若第一个结点仅表示链表的起始位置，而无任何值和意义，则称为头结起始位置，而无任何值和意义，则称为头结点。点。data.headnext12n链表：数据域数据域地址域地址域 链表中结点要用两个区域，一个表示链表中结点要用两个区域，一个表示结点数据信息，称为数据域，一个表示当前结点数据信息，称为数据域，一个表示当前结点的后继结点的引用，称为地址域。结点的后继结点的引用，称为地址域。链表：public cl

20、ass Node/节点类节点类Student stu;/节点数据为学生对象节点数据为学生对象Node next;/后继节点的地址后继节点的地址public class Node/节点类节点类Object obj;/节点数据可以为任何对象节点数据可以为任何对象Node next;/后继节点的地址后继节点的地址链表操作链式结构存储对应的链表的建立和该表中数据元素的插入、链式结构存储对应的链表的建立和该表中数据元素的插入、删除、查找等运算的实现。链表中插入、删除、查找操作删除、查找等运算的实现。链表中插入、删除、查找操作思想如下：思想如下：l判断链表是否空表判断链表是否空表，表为空表，则链表除头结点

21、外无其，表为空表，则链表除头结点外无其他结点他结点。l在链表中某位置插入新节点，有以下两个操作：（在链表中某位置插入新节点，有以下两个操作：（1）找到插入前位置（找到插入前位置（2）插入新节点）插入新节点.例如在第例如在第i个位置前插个位置前插入新节点入新节点node l在链表中删除某位置节点，有以下两个操作：（在链表中删除某位置节点，有以下两个操作：（1）找）找到删除位置（到删除位置（2）删除对应位置节点）删除对应位置节点.例如删除第例如删除第i个位置个位置节点。节点。l在链表中查找某位置节点，则链表第一个位置开始不断在链表中查找某位置节点，则链表第一个位置开始不断向下遍历链表，直到查找位置

22、结束，返回查找结点。向下遍历链表，直到查找位置结束，返回查找结点。在单链表非第一个结点前插入结点过程在单链表非第一个结点前插入结点过程 图在带头结点单链表第一个结点前插入结点过程图在带头结点单链表第一个结点前插入结点过程headhead单链表类单链表类 LinkedList代码代码 单链表类的成员变量至少要有两个：一个是单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。头指针，另一个是单链表中的数据元素个数。单单链链表表是是由由一一个个一一个个结结点点组组成成的的，因因此此，要要设设计计单单链链表表类类，必必须须先先设设计计结结点点类类。结结点点类类的的成成员员变变

23、量量有有两两个个：一一个个是是数数据据元元素素，另另一一个个是是表表示示下下一一个个结结点点的对象引用（即指针）。的对象引用（即指针）。结点类结点类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

24、 nextNode)element=obj;next=nextNode;public Object getElement()return element;public Node getNext()return next;public void setElement(Object element)this.element=element;public void setNext(Node next)this.next=next;public String toString()return element.toString();单链表类的两个成员变量head：头结点：头结点length：表示链表中结

25、点的个数：表示链表中结点的个数构造函数public LinkedList()head=new Node();length=0;isEmptypublic boolean isEmpty()if(head.next=null)return true;elsereturn false;query(int i)public Node query(int i)Node p=head;for(int j=1;j=i;j+)p=p.next;return p;length()public int length()return length;insert(int i,Node node)public voi

26、d insert(int i,Node node)if(ilength+1)System.out.println(插入位置有误！插入位置有误！);return;if(head=null)head.next=node;node.next=null;elseNode p=query(i-1);node.next=p.next;p.next=node;length+;delete(int i)public Node delete(int i)if(ilength)System.out.println(删除位置有误！删除位置有误！);return null;Node p=query(i-1);Node

27、 temp=p.next;p.next=p.next.next;length-;return temp;顺序表和单链表的比较顺序表和单链表的比较 顺序表的主要优点是支持随机读取，以及内顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。除操作时需

28、要移动较多的数据元素。和顺序表相比，单链表的主要优点是不需要预和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。入和删除操作时不需要移动数据元素。单链表的主要缺点是每个结点中要有一个指针，单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为素操作的时间复杂度为O（n）；而顺序表支）；而顺序表支持随机读取，顺序表取数据元素操作

29、的时间复持随机读取，顺序表取数据元素操作的时间复杂度为杂度为O（1）。）。2.2.3 循环链表循环链表是另一种形式的链式存储结构，表中循环链表是另一种形式的链式存储结构，表中最后一个结点的指针域指向头结点，整个链表最后一个结点的指针域指向头结点，整个链表形成一个环，如下图为单链的循环链表。形成一个环，如下图为单链的循环链表。：a1a1a2 a2 a3a3ananheadrear2.3.1问题描述 一一堆堆猴猴子子都都有有编编号号，编编号号是是1，2，3.n,这这群群猴猴子子（n个个）按按照照1-n的的顺顺序序围围坐坐一一圈圈，从从第第1开开始始数数，每每数数到到第第M个个，该该猴猴子子就就要要

30、离离开开此此圈圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。算算法法思思想想：使使用用单单循循环环链链表表数数据据结结构构模模拟拟问问题题，每每个个结结点点是是一一个个猴猴子子，结结点点的的值值域域为为该该结结点点的的编编号号，总总共共n个个结结点点。遇遇到到出出列列的的结结点点则则删删除除该该结结点点。如如此此循循环环，直直到到只只剩剩下下最最后后一一个个结结点点为为止止。最最后后输输出出该该结结点点的的数数值值。2.3.2业务实现业务类初始化该方法是在业务对象实例化时，实现调用，进行必要的初始化该方法是在业务对象实例

31、化时，实现调用，进行必要的初始化class cirLinkedListNode front;/循环链表头指针循环链表头指针Node rear;/循环链表表尾指针循环链表表尾指针int length;/表长度表长度 public cirLinkedList()/初始化循环链表初始化循环链表this.rear=this.front=null;this.length=0;2.3.3业务实现增加结点p public void add(Node p)/增加结点增加结点p if(this.length=0)front=rear=p;else rear.next=p;rear=p;rear.next=front;this.length+;2.4双链表的基本概念双链表的定义：对每个结点增加一个地址域，双链表的定义：对每个结点增加一个地址域，用来存放其前驱结点的引用，该表称为双链表用来存放其前驱结点的引用，该表称为双链表 双链表的结点定义如下：双链表的结点定义如下：priordatanext2.4.1双链表的结点定义u代码实现如下：public class Node Student data;/每个结点的数据域，为学生对象 Node next;/后继节点的引用 Node prior;/前驱结点的引用2.4.2双链表的插入操作2.4.2双链表的删除操作