数据结构(叶核亚)第02章线性表.ppt

叶核亚,数据结构（Java版）（第2版）,数据结构（Java版）（第2版）,第2章 线性表,2.1 线性表的抽象数据类型2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 目的：实现线性表抽象数据类型。要求：掌握两种存储结构实现线性表。重点：顺序表类，单链表类。难点：单链表，双链表。,2.1 线性表的抽象数据类型,LinearList=(a0，a1，an1)public interface LList/线性表接口 boolean isEmpty();/判断线性表是否为空 int length();/返回线性表长度 E get(int index);/返回序号为index的对象 E set(int index,E element);/设置序号为index对象为 boolean add(int index,E element);/在index处插入element对象 boolean add(E element);/在顺序表最后插入element对象 E remove(int index);/移去序号为index的对象并返回 void clear();/清空线性表,2.2 线性表的顺序表示和实现,线性表的顺序存储结构,2.顺序表的插入和删除操作,public class SeqList implements LList/顺序表类，实现线性表接口 private Object table;/对象数组，私有成员 private int n;/顺序表长度顺序表操作的效率分析 如果在各位置插入元素的概率相同，则有,3.顺序表类,【例2.1】使用顺序表类求解约瑟夫环问题。,2.3 线性表的链式表示和实现,2.3.1 线性表的链式存储结构2.3.2 单链表2.3.3 双链表,2.3.1 线性表的链式存储结构,单链表结点类 public class Node/单链表结点类 public E data;/数据域，保存数据元素 public Node next;/地址域，引用后继结点Node p,q;p=new Node(A);q=new Node(B);p.next=q;,2.3.2 单链表,2.单链表的遍历操作,Node p=head;while(p!=null)访问p结点;p=p.next;,3.单链表的插入操作,4.单链表的删除操作,头删除head=head.next;中间/尾删除if(p.next!=null)p.next=p.next.next;,5.单链表类,public class SinglyLinkedList implements LList/单链表类，实现线性表接口 protected Node head;/头指针 public SinglyLinkedList()/构造空单链表 this.head=null;（P59）单链表操作的效率分析,【例2.2】采用单链表求解约瑟夫环问题。,7.单链表是递归结构,public String toString()return(+this.toString(this.head)+);public String toString(Node p)/递归算法 if(p!=null)return p.data.toString()+,+this.toString(p.next);return;,【例2.3】单链表逆转。,8.带头结点的单链表,【例2.4】建立排序的单链表。,9.循环单链表,2.3.3 双链表,双链表结构p=p.next.prev=p.prev.next,2.双链表的插入和删除操作,(1)插入q=new DLinkNode(x);q.prev=p.prev;q.next=p;p.prev.next=q;p.prev=q;,（2）删除,p.prev.next=p.next;if(p.next!=null)(p.next).prev=p.prev;,3.循环双链表,4.双链表类,public class DLinkNode/双链表结点类 public E data;/数据元素 public DLinkNode prev,next;/前驱、后继结点public class CHDoublyLinkedList/带头结点的循环双链表类 protected DLinkNode head;/头指针,*2.4 迭代器（略）,