第02章线性表(741KB).pptVIP

2.4.3 提供迭代器对象 顺序表类提供迭代器对象 public class SeqListE extends AbstractListE implements LListE { public IteratorE iterator() { return new Itr(); //返回一个迭代器对象 } private class Itr implements IteratorE //私有内部类，实现迭代器接口 } 《数据结构（Java版）（第2版）》 2. 单链表类提供迭代器对象 public class SinglyLinkedListE extends AbstractListE implements LListE { public IteratorE iterator() { return new Itr(); //返回一个迭代器对象 } private class Itr implements IteratorE //私有内部类，实现迭代器接口 } 《数据结构（Java版）（第2版）》 叶核亚 数据结构（Java版）（第2版） 数据结构（Java版）（第2版） 第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈与队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 第10章 综合应用设计 第11章 Java开发运行环境 第2章 线性表 2.1 线性表的抽象数据类型 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 目的：实现线性表抽象数据类型。 要求：掌握两种存储结构实现线性表。 重点：顺序表类，单链表类。 难点：单链表，双链表。 《数据结构（Java版）（第2版）》 2.1 线性表的抽象数据类型 LinearList=(a0，a1，…，an－1) public interface LListE //线性表接口 { boolean isEmpty(); //判断线性表是否为空 int length(); //返回线性表长度 E get(int index); //返回序号为index的对象 E set(int index, E element); //设置序号为index对象为 boolean add(int index, E element); //插入element对象，插入后对象序号为index boolean add(E element); //插入element对象，插入位置没有约定 E remove(int index); //移去序号为index的对象，返回被移去对象 void clear(); //清空线性表 } 《数据结构（Java版）（第2版）》 2.2 线性表的顺序表示和实现 线性表的顺序存储结构 《数据结构（Java版）（第2版）》 2. 顺序表的插入和删除操作 《数据结构（Java版）（第2版）》 3. 顺序表类 public class SeqListE implements LListE { //顺序表类，实现线性表接口 private Object[] table; //对象数组，私有成员 private int n; //顺序表长度 } 顺序表操作的效率分析 如果在各位置插入元素的概率相同，则有 《数据结构（Java版）（第2版）》 【例2.1】 使用顺序表类求解约瑟夫环问题。 《数据结构（Java版）（第2版）》 2.3 线性表的链式表示和实现 2.3.1 线性表的链式存储结构 2.3.2 单链表 2.3.3 双链表 《数据结构（Java版）（第2版）》 2.3.1 线性表的链式存储结构 《数据结构（Java版）（第