线性表Java学习教程.pptx

《线性表Java学习教程.pptx》由会员分享，可在线阅读，更多相关《线性表Java学习教程.pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（Java版）（第3版）目的和要求目的：实现线性表抽象数据类型。内容：将线性表的顺序存储结构和链式存储结构 实现分别封装成顺序表类、单链表类、循环 双链表类等，比较这两种实现的特点以及各 种基本操作算法的效率。要求：理解线性表抽象数据类型，掌握顺序和链式 存储结构实现线性表的方法。重点：顺序表、单链表、循环双链表等线性表的设 计训练。难点：使用指针实现链式存储结构，通过指针操作 改变结点间的链接关系。实验：掌握单链表的遍历、插入、删除、复制等操 作算法，熟悉循环单链表、双链表和循环双 链表的结构和基本操作。掌握MyEclipse集 成开发环境的程序调试技术。第1页/共50页数据结构（J

2、ava版）（第3版）2.1 线性表的抽象数据类型LinearList=(a0，a1，an1)public interface LList /线性表接口，泛型参数T表示数据元素的数据类型 boolean isEmpty();/判断线性表是否空 int length();/返回线性表长度 T get(int i);/返回第i（i0）个元素 void set(int i,T x);/设置第i个元素值为x void insert(int i,T x);/插入x作为第i个元素 void append(T x);/在线性表最后插入x元素 T remove(int i);/删除第i个元素并返回被删除对象 v

3、oid removeAll();/删除线性表所有元素 T search(T key);/查找，返回首次出现的关键字为key元素public class SeqList implements LList /顺序表类public class SinglyLinkedList implements LList/单链表类第2页/共50页数据结构（Java版）（第3版）2.2 线性表的顺序表示和实现线性表的顺序存储结构 第3页/共50页数据结构（Java版）（第3版）public class SeqList implements LList /顺序表类，实现线性表接口 protected Object

4、element;/对象数组 protected int len;/顺序表长度，记载元素个数2.顺序表类第4页/共50页数据结构（Java版）（第3版）4.顺序表的删除操作 3.顺序表的插入操作顺序表的插入操作 第5页/共50页数据结构（Java版）（第3版）【例2.1】使用顺序表类求解约瑟夫环问题。第6页/共50页数据结构（Java版）（第3版）顺序表的静态特性很好，动态特性很差，具体说明如下。顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。get()、set()方法时间复杂度是 O(1)。插入和删除操作效率很低。如果在各位置插入元素的概率相同，则有5.顺序表操

5、作的效率分析第7页/共50页数据结构（Java版）（第3版）6.顺序表的浅拷贝与深拷贝 一个类的拷贝构造方法声明格式如下：类(类 对象)（1）顺序表的浅拷贝public SeqList(SeqList list)/浅拷贝构造方法 this.element=list.element;/数组引用赋值，两个变量共用一个数组，错误 this.len=list.len;第8页/共50页数据结构（Java版）（第3版）执行拷贝构造方法SeqList listb=new SeqList(lista);第9页/共50页数据结构（Java版）（第3版）（2）顺序表的深拷贝 第10页/共50页数据结构（Java版

6、）（第3版）7.顺序表比较相等 两个顺序表相等是指，它们各对应元素相等并且长度相同。第11页/共50页数据结构（Java版）（第3版）2.3 线性表的链式表示和实现2.3.1 线性表的链式存储结构2.3.2 单链表2.3.3 双链表第12页/共50页数据结构（Java版）（第3版）2.3.1 线性表的链式存储结构第13页/共50页数据结构（Java版）（第3版）单链表结点类 public class Node /单链表结点类 public T data;/数据域，保存数据元素 public Node next;/地址域，引用后继结点Node p,q;p=new Node(A,null);q=n

7、ew Node(B,null);p.next=q;2.3.2 单链表第14页/共50页数据结构（Java版）（第3版）2.单链表的遍历操作 Node p=head;while(p!=null)System.out.print(p.data.toString()+);/执行访问p结点的相关操作 p=p.next;第15页/共50页数据结构（Java版）（第3版）如果语句p=p.next写成p.next=p第16页/共50页数据结构（Java版）（第3版）3.单链表的插入操作（1）空表插入/头插入if(head=null)/空表插入 head=new Node(x,null);else /头插入

8、Node q=new Node(x,null);q.next=head;head=q;即head=new Node(x,head);第17页/共50页数据结构（Java版）（第3版）（2）中间插入/尾插入Node q=new Node(x,null);q.next=p.next;/q的后继结点应是p的原后继结点p.next=q;/q作为p的后继结点即p.next=new Node(x,p.next);第18页/共50页数据结构（Java版）（第3版）如果上述后两条语句次序颠倒，则产生错误Node q=new Node(x,null);p.next=q;q.next=p.next;第19页/共5

9、0页数据结构（Java版）（第3版）4.单链表的删除操作 头删除head=head.next;中间/尾删除if(p.next!=null)p.next=p.next.next;第20页/共50页数据结构（Java版）（第3版）5.带头结点的单链表 第21页/共50页数据结构（Java版）（第3版）【例2.2】采用单链表求解约瑟夫环问题。第22页/共50页数据结构（Java版）（第3版）6.单链表操作的效率分析isEmpty()方法的时间复杂度是O(1)。length()方法要遍历单链表，时间复杂度是O(n)。get(i)和set(i)方法的时间复杂度是O(n)，不是随机存取结构。insert(

10、i,x)和remove(i)时间复杂度是O(n)。第23页/共50页数据结构（Java版）（第3版）在p结点之前插入结点q 删除结点p要寻找其前驱结点front 第24页/共50页数据结构（Java版）（第3版）7.提高单链表操作效率的措施 public boolean append(T x)return insert(this.length(),x);/需遍历单链表两次，效率较低return insert(Integer.MAX_VALUE,x);/遍历一次第25页/共50页数据结构（Java版）（第3版）作用于顺序表的时间复杂度是O(n)，但作用于单链表的时间复杂度则是public Str

11、ing toString()String str=(;if(this.length()!=0)for(int i=0;ithis.length()-1;i+)str+=this.get(i).toString()+,;str+=this.get(this.length()-1).toString();return str+);第26页/共50页数据结构（Java版）（第3版）例2.3 求整数单链表的平均值。第27页/共50页数据结构（Java版）（第3版）【例2.4】单链表逆转。第28页/共50页数据结构（Java版）（第3版）8.单链表的浅拷贝与深拷贝 public SinglyLinked

12、List(SinglyLinkedList list)/拷贝构造函数，浅拷贝 this.head=list.head;/导致两个引用变量指向同一个结点 第29页/共50页数据结构（Java版）（第3版）8.单链表的深拷贝 第30页/共50页数据结构（Java版）（第3版）9.9.单链表比较相等两条单链表相等是指，它们各对应元素相等并且长度相同。第31页/共50页数据结构（Java版）（第3版）10.排序单链表第32页/共50页数据结构（Java版）（第3版）11.循环单链表 第33页/共50页数据结构（Java版）（第3版）2.3.3 双链表双链表结构p=p.next.pred=p.pred.

13、next第34页/共50页数据结构（Java版）（第3版）2.双链表的插入和删除操作(1)插入在p结点之前插入值为x结点 q=new DLinkNode(x,p.pred,p);p.pred.next=q;p.pred=q;第35页/共50页数据结构（Java版）（第3版）在p结点之后插入值为x结点 q=new DLinkNode(x,p,p.next);/当p.next=null时，尾插入if(p.next!=null)p.next.pred=q;/中间插入时执行p.next=q;第36页/共50页数据结构（Java版）（第3版）（2）双链表的删除操作 p.pred.next=p.next;

14、/有p.pred!=nullif(p.next!=null)p.next.pred=p.pred;第37页/共50页数据结构（Java版）（第3版）3.循环双链表 第38页/共50页数据结构（Java版）（第3版）4.排序循环双链表第39页/共50页数据结构（Java版）（第3版）2.4 线性表的应用：多项式的表示及运算2.4.1 一元多项式的表示及运算2.4.2 二元多项式的表示及运算第40页/共50页数据结构（Java版）（第3版）2.4.1 一元多项式的表示及运算第41页/共50页数据结构（Java版）（第3版）1.一元多项式的顺序存储结构第42页/共50页数据结构（Java版）（第3版

15、）2.一元多项式的链式存储结构（1）一元多项式的项类（2）多项式单链表第43页/共50页数据结构（Java版）（第3版）（3）多项式类 多项式类Polynomial声明及相加运算第44页/共50页数据结构（Java版）（第3版）【例2.6】一元多项式的表示及相加运算。第45页/共50页数据结构（Java版）（第3版）多项式深度拷贝及应用第46页/共50页数据结构（Java版）（第3版）比较两个多项式是否相等public boolean equals(Object obj)/比较两个多项式是否相等 return this=obj|obj instanceof Polynomial&this.list.equals(Polynomial)obj).list);第47页/共50页数据结构（Java版）（第3版）2.4.2 二元多项式的表示及运算（1）二元多项式的项类TermXY（2）Polynomial可表示二元多项式 （3）PolySLinkedList类的作用第48页/共50页数据结构（Java版）（第3版）线性表接口和类的层次关系 第49页/共50页数据结构（Java版）（第3版）感谢您的观看！第50页/共50页