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

第二章线性表,教学目标：掌握线性表的基本概念掌握顺序表和链表的存储原理线性表的应用重点：线性表的存储难点：线性表的操作及其应用,线性表的基本概念,线性表是最简单也是最常用的一种线性结构。线性表的定义：线性表是由同一类型数据元素组成的有限序列。其中第一个元素无前驱结点，最后一个元素无后继结点，除第一个和最后一个元素外其余元素均有且仅有一个直接前驱和直接后继结点。,线性表的基本概念,线性表中元素的个数称为该表的长度，如果长度值为0则称表为空表。线性表常见操作有插入、删除、查找、修改等操作。,线性表的逻辑结构,线性表(LinearList)：是由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),若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。对线性表的数据元素可以访问、插入和删除。,线性表的抽象数据类型定义,ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R=|ai-1,aiD,i=2,3,n基本操作：InitList(n-)datan+1=datan;datai-1=obj;length+;returntrue;,delete(inti),publicObjectdelete(inti)if(ilength)System.out.println(删除位置有误！);returnnull;Objecttemp=datai-1;for(intn=i;nlength;n+)datan-1=datan;datalength-1=null;length-;returntemp;,2.2.2链表：,链表：按链式存储结构存储的线性表。链表是指线性表中的结点在内存中随机存放，即存储单元可以连续也可以不连续，因此为了保持链表中各结点逻辑相邻的关系，需要在各结点在存放值的同时还要存放下一个结点的地址。单链表：构成链表的每个结点只有一个指向直接后继结点的指针。,链表：,头结点：若第一个结点仅表示链表的起始位置，而无任何值和意义，则称为头结点。,data,链表：,链表中结点要用两个区域，一个表示结点数据信息，称为数据域，一个表示当前结点的后继结点的引用，称为地址域。,链表：,publicclassNode/节点类Studentstu;/节点数据为学生对象Nodenext;/后继节点的地址,publicclassNode/节点类Objectobj;/节点数据可以为任何对象Nodenext;/后继节点的地址,链表操作,链式结构存储对应的链表的建立和该表中数据元素的插入、删除、查找等运算的实现。链表中插入、删除、查找操作思想如下：判断链表是否空表，表为空表，则链表除头结点外无其他结点。在链表中某位置插入新节点，有以下两个操作：（1）找到插入前位置（2）插入新节点.例如在第i个位置前插入新节点node在链表中删除某位置节点，有以下两个操作：（1）找到删除位置（2）删除对应位置节点.例如删除第i个位置节点。在链表中查找某位置节点，则链表第一个位置开始不断向下遍历链表，直到查找位置结束，返回查找结点。,在单链表非第一个结点前插入结点过程,图在带头结点单链表第一个结点前插入结点过程,单链表类LinkedList代码单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。,单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。,结点类,Node代码,publicclassNodeObjectelement;/数据域Nodenext;/地址域publicNode()element=null;next=null;publicNode(NodenextNode)element=null;next=nextNode;publicNode(Objectobj)element=obj;next=null;publicNode(Objectobj,NodenextNode)element=obj;next=nextNode;,publicObjectgetElement()returnelement;publicNodegetNext()returnnext;publicvoidsetElement(Objectelement)this.element=element;publicvoidsetNext(Nodenext)this.next=next;publicStringtoString()returnelement.toString();,单链表类的两个成员变量,head：头结点length：表示链表中结点的个数,构造函数,publicLinkedList()head=newNode();length=0;,isEmpty,publicbooleanisEmpty()if(head.next=null)returntrue;elsereturnfalse;,query(inti),publicNodequery(inti)Nodep=head;for(intj=1;j=i;j+)p=p.next;returnp;,length(),publicintlength()returnlength;,insert(inti,Nodenode),publicvoidinsert(inti,Nodenode)if(ilength+1)System.out.println(插入位置有误！);return;if(head=null)head.next=node;node.next=null;elseNodep=query(i-1);node.next=p.next;p.next=node;length+;,delete(inti),publicNodedelete(inti)if(ilength)System.out.println(删除位置有误！);returnnull;Nodep=query(i-1);Nodetemp=p.next;p.next=p.next.next;length-;returntemp;,顺序表和单链表的比较顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。,和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。,2.2.3循环链表,循环链表是另一种形式的链式存储结构，表中最后一个结点的指针域指向头结点，整个链表形成一个环，如下图为单链的循环链表。：,2.3.1问题描述,一堆猴子都有编号，编号是1，2，3.n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1开始数，每数到第M个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。算法思想：使用单循环链表数据结构模拟问题，每个结点是一个猴子，结点的值域为该结点的编号，总共n个结点。遇到出列的结点则删除该结点。如此循环，直到只剩下最后一个结点为止。最后输出该结点的数值。,2.3.2业务实现业务类初始化,该方法是在业务对象实例化时，实现调用，进行必要的初始化,classcirLinkedListNodefront;/循环链表头指针Noderear;/循环链表表尾指针intlength;/表长度publiccirLinkedList()/初始化循环链表this.rear=this.front=null;this.length=0;,2.3.3业务实现增加结点p,publicvoidadd(Nodep)/增加结点pif(this.length=0)front=rear=p;elserear.next=p;rear=p;rear.next=fron