第二章数据结构(JAVA版) 线性表(精品·公开课件).ppt

　　和单链表相同，循环单链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作时，算法实现较为方便。 带头结点的循环单链表结构如下： （a）空链表；（b）非空链表 　　带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于： 　　（1）在构造函数中，要加一条head.next = head 语句，把初始时的带头结点的循环单链表设计成图2-11 （a）所示的状态。 　　（2）在index(i)成员函数中，把循环结束判断条件current != null改为current != head。 　　双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。 　　 2.5 　双向链表 　在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，其中element域为数据元素域，next域为指向后继结点的对象引用，prior域为指向前驱结点的对象引用。图2-12为双向链表结点的图示结构。 　双向链表结点的图示结构 　图2-13是带头结点的循环双向链表的图示结构。从图2-13可见，循环双向链表的next和prior各自构成自己的循环单链表。 带头结点的循环双向链表 （a）空链表；（b）非空链表 　　　在双向链表中，有如下关系：设对象引用p表示双向链表中的第i个结点，则p.next表示第i+1个结点，p.next.prior仍表示第i个结点，即p.next.prior == p；同样地，p.prior表示第i-1个结点，p.prior.next仍表示第i个结点，即p.prior.next == p。图2-14是双向链表上述关系的图示。 图2-14　双向链表的关系 　　循环双向链表的插入过程如图2-15所示。图中的指针p表示要插入结点的位置，s表示要插入的结点，①、②、③、④表示实现插入过程的步骤。 图2-15 　循环双向链表的插入过程 　循环双向链表的删除过程如图2-16所示。图中的指针p表示要插入结点的位置，①、②表示实现删除过程的步骤。 　 循环双向链表的删除过程 2.6　仿真链表 　　　在链式存储结构中，我们实现数据元素之间的次序关系依靠指针。我们也可以用数组来构造仿真链表。方法是在数组中增加一个（或两个）int类型的变量域，这些变量用来表示后一个（或前一个）数据元素在数组中的下标。我们把这些int类型变量构造的指针称为仿真指针。这样，就可以用仿真指针构造仿真的单链表（或仿真的双向链表）。 （a）常规单链表；（b）仿真单链表一；（c）仿真单链表二 2.7　 面向对象的软件设计方法 面向对象软件设计方法是一种和人类认识事物、分析事物方法一致的软件设计方法。不仅如此，面向对象设计方法的模块化软件、数据封装、信息隐藏等特点，还可以使软件设计可以像其他工业产品一样，可以大规模协作开发。 模块化软件设计的基本思想是：把基础软件设计成可重复使用的模块，这些模块提供外部调用的接口，其他程序通过接口使用这些基础软件模块。这样，软件工业将摆脱了小作坊工作方式，像现代的其他工业一样，可以进行大规模的协作生产或开发。 * 最好情况（ i=n-1）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=0）： 基本语句执行n-1次，时间复杂度为O(n)。 平均情况（0≤i≤n-1）： 时间复杂度为O(n)。 时间性能分析 顺序表的实现——删除 顺序表的实现——按位查找 0 … i-1 i … n-1 Max-1 a1 … ai ai+1 … an 空闲 n public Object getData(int i) throws Exception{ if(i 0 || i = size){ throw new Exception(参数错误！); } return listArray[i]; } 算法描述——Java描述 顺序表的实现——求表长 public int size(){ return size; } 顺序表的实现——判表空 public boolean isEmpty(){ return size == 0; } 算法描述——Java描述 算法描述——Java描述 public int MoreDataDelete(SeqList L, Object x) throws E